OSDN Git Service

Daily bump.
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / testsuite / 20_util / hash / quality.cc
1 // { dg-options "-std=gnu++0x" }
2
3 // Copyright (C) 2010 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 //
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING3.  If not see
18 // <http://www.gnu.org/licenses/>.
19
20 #include <cstdlib>
21 #include <unordered_set>
22 #include <string>
23 #include <functional>
24 #include <vector>
25 #include <testsuite_hooks.h>
26
27 using namespace std;
28
29 // { dg-options "-DNTESTS=1 -DNSTRINGS=100 -DSTRSIZE=21" { target simulator } }
30 #ifndef NTESTS
31 #define NTESTS 5
32 #endif
33 #ifndef NSTRINGS
34 #define NSTRINGS 200
35 #endif
36 #ifndef STRSIZE
37 #define STRSIZE 42
38 #endif
39
40 const unsigned int num_quality_tests = NTESTS;
41 const unsigned int num_strings_for_quality_tests = NSTRINGS;
42 const unsigned int string_size = STRSIZE;
43
44 vector<string>
45 random_strings(unsigned int n, unsigned int len)
46 {
47   string s(len, '\0');
48   unordered_set<string> result_set;
49   while (result_set.size() < n)
50     {
51       result_set.insert(s);
52       unsigned int tmp = rand();
53       tmp %= len * 256;
54       s[tmp / 256] = tmp % 256;
55     }
56   return vector<string>(result_set.begin(), result_set.end());
57 }
58
59 double
60 score_from_varying_position(string s, unsigned int index)
61 {
62   bool test __attribute__((unused)) = true;
63   unsigned int bits_in_hash_code = sizeof(size_t) * 8;
64
65   // We'll iterate through all 256 vals for s[index], leaving the rest
66   // of s fixed.  Then, for example, out of the 128 times that
67   // s[index] has its 3rd bit equal to 0 we would like roughly half 1s
68   // and half 0s in bit 9 of the hash codes.
69   //
70   // Bookkeeping: Conceptually we want a 3D array of ints.  We want to
71   // count the number of times each output position (of which there are
72   // bits_in_hash_code) is 1 for each bit position within s[index] (of 
73   // which there are 8) and value of that bit (of which there are 2).
74   const unsigned int jj = 2;
75   const unsigned int kk = jj * bits_in_hash_code;
76   const unsigned int array_size = 8 * kk;
77   vector<int> ones(array_size, 0);
78
79   for (int i = 0; i < 256; i++)
80     {
81       s[index] = i;
82       size_t h = hash<string>()(s);
83       for (int j = 0; h != 0; j++, h >>= 1)
84         {
85           if (h & 1)
86             {
87               for (int k = 0; k < 8; k++)
88                 ++ones[k * kk + j * jj + ((i >> k) & 1)];
89             }
90         }
91     }
92
93   // At most, the innermost statement in the above loop nest can
94   // execute 256 * bits_in_hash_code * 8 times.  If the hash is good,
95   // it'll execute about half that many times, with a pretty even
96   // spread across the elements of ones[].
97   VERIFY( 256 * bits_in_hash_code * 8 / array_size == 128 );
98   int max_ones_possible = 128;
99   int good = 0, bad = 0;
100   for (int bit = 0; bit <= 1; bit++)
101     {
102       for (unsigned int j = 0; j < bits_in_hash_code; j++)
103         {
104           for (int bitpos = 0; bitpos < 8; bitpos++)
105             {
106               int z = ones[bitpos * kk + j * jj + bit];
107               if (z <= max_ones_possible / 6
108                   || z >= max_ones_possible * 5 / 6)
109                 {
110                   // The hash function screwed up, or was just unlucky,
111                   // as 128 flips of a perfect coin occasionally yield
112                   // far from 64 heads.
113                   bad++;
114                 }
115               else
116                 good++;
117             }
118         }
119     }
120   return good / (double)(good + bad);
121 }
122
123 double
124 score_from_varying_position(const vector<string>& v, unsigned int index)
125 {
126   double score = 0;
127   for (unsigned int i = 0; i < v.size(); i++)
128     score += score_from_varying_position(v[i], index);
129   return score / v.size();
130 }
131
132 double
133 quality_test(unsigned int num_strings, unsigned int string_size)
134 {
135   // Construct random strings.
136   vector<string> v = random_strings(num_strings, string_size);
137   double sum_of_scores = 0;
138   for (unsigned int i = 0; i < string_size; i++)
139     sum_of_scores += score_from_varying_position(v, i);
140
141   // A good hash function should have a score very close to 1, and a bad
142   // hash function will have a score close to 0.
143   return sum_of_scores / string_size;
144 }
145
146 void
147 quality_test()
148 {
149   bool test __attribute__((unused)) = true;
150   srand(137);
151   double sum_of_scores = 0;
152   for (unsigned int i = 0; i < num_quality_tests; i++)
153     {
154       double score = quality_test(num_strings_for_quality_tests,
155                                   string_size);
156       sum_of_scores += score;
157       VERIFY( score > 0.99 );
158     }
159
160   if (num_quality_tests > 1)
161     {
162       double mean_quality = sum_of_scores / num_quality_tests;
163       VERIFY( mean_quality > 0.9999 );
164     }
165 }
166
167 int
168 main()
169 {
170   quality_test();
171   return 0;
172 }