lib: import ccan modules for tdb2
[samba.git] / lib / ccan / hash / test / run.c
1 #include <ccan/hash/hash.h>
2 #include <ccan/tap/tap.h>
3 #include <ccan/hash/hash.c>
4 #include <stdbool.h>
5 #include <string.h>
6
7 #define ARRAY_WORDS 5
8
9 int main(int argc, char *argv[])
10 {
11         unsigned int i, j, k;
12         uint32_t array[ARRAY_WORDS], val;
13         char array2[sizeof(array) + sizeof(uint32_t)];
14         uint32_t results[256];
15
16         /* Initialize array. */
17         for (i = 0; i < ARRAY_WORDS; i++)
18                 array[i] = i;
19
20         plan_tests(39);
21         /* Hash should be the same, indep of memory alignment. */
22         val = hash(array, ARRAY_WORDS, 0);
23         for (i = 0; i < sizeof(uint32_t); i++) {
24                 memcpy(array2 + i, array, sizeof(array));
25                 ok(hash(array2 + i, ARRAY_WORDS, 0) != val,
26                    "hash matched at offset %i", i);
27         }
28
29         /* Hash of random values should have random distribution:
30          * check one byte at a time. */
31         for (i = 0; i < sizeof(uint32_t); i++) {
32                 unsigned int lowest = -1U, highest = 0;
33
34                 memset(results, 0, sizeof(results));
35
36                 for (j = 0; j < 256000; j++) {
37                         for (k = 0; k < ARRAY_WORDS; k++)
38                                 array[k] = random();
39                         results[(hash(array, ARRAY_WORDS, 0) >> i*8)&0xFF]++;
40                 }
41
42                 for (j = 0; j < 256; j++) {
43                         if (results[j] < lowest)
44                                 lowest = results[j];
45                         if (results[j] > highest)
46                                 highest = results[j];
47                 }
48                 /* Expect within 20% */
49                 ok(lowest > 800, "Byte %i lowest %i", i, lowest);
50                 ok(highest < 1200, "Byte %i highest %i", i, highest);
51                 diag("Byte %i, range %u-%u", i, lowest, highest);
52         }
53
54         /* Hash of random values should have random distribution:
55          * check one byte at a time. */
56         for (i = 0; i < sizeof(uint64_t); i++) {
57                 unsigned int lowest = -1U, highest = 0;
58
59                 memset(results, 0, sizeof(results));
60
61                 for (j = 0; j < 256000; j++) {
62                         for (k = 0; k < ARRAY_WORDS; k++)
63                                 array[k] = random();
64                         results[(hash64(array, sizeof(array)/sizeof(uint64_t),
65                                         0) >> i*8)&0xFF]++;
66                 }
67
68                 for (j = 0; j < 256; j++) {
69                         if (results[j] < lowest)
70                                 lowest = results[j];
71                         if (results[j] > highest)
72                                 highest = results[j];
73                 }
74                 /* Expect within 20% */
75                 ok(lowest > 800, "Byte %i lowest %i", i, lowest);
76                 ok(highest < 1200, "Byte %i highest %i", i, highest);
77                 diag("Byte %i, range %u-%u", i, lowest, highest);
78         }
79
80         /* Hash of pointer values should also have random distribution. */
81         for (i = 0; i < sizeof(uint32_t); i++) {
82                 unsigned int lowest = -1U, highest = 0;
83                 char *p = malloc(256000);
84
85                 memset(results, 0, sizeof(results));
86
87                 for (j = 0; j < 256000; j++)
88                         results[(hash_pointer(p + j, 0) >> i*8)&0xFF]++;
89                 free(p);
90
91                 for (j = 0; j < 256; j++) {
92                         if (results[j] < lowest)
93                                 lowest = results[j];
94                         if (results[j] > highest)
95                                 highest = results[j];
96                 }
97                 /* Expect within 20% */
98                 ok(lowest > 800, "hash_pointer byte %i lowest %i", i, lowest);
99                 ok(highest < 1200, "hash_pointer byte %i highest %i",
100                    i, highest);
101                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
102         }
103
104         if (sizeof(long) == sizeof(uint32_t))
105                 ok1(hashl(array, ARRAY_WORDS, 0)
106                     == hash(array, ARRAY_WORDS, 0));
107         else
108                 ok1(hashl(array, ARRAY_WORDS, 0)
109                     == hash64(array, ARRAY_WORDS, 0));
110
111         /* String hash: weak, so only test bottom byte */
112         for (i = 0; i < 1; i++) {
113                 unsigned int num = 0, cursor, lowest = -1U, highest = 0;
114                 char p[5];
115
116                 memset(results, 0, sizeof(results));
117
118                 memset(p, 'A', sizeof(p));
119                 p[sizeof(p)-1] = '\0';
120
121                 for (;;) {
122                         for (cursor = 0; cursor < sizeof(p)-1; cursor++) {
123                                 p[cursor]++;
124                                 if (p[cursor] <= 'z')
125                                         break;
126                                 p[cursor] = 'A';
127                         }
128                         if (cursor == sizeof(p)-1)
129                                 break;
130
131                         results[(hash_string(p) >> i*8)&0xFF]++;
132                         num++;
133                 }
134
135                 for (j = 0; j < 256; j++) {
136                         if (results[j] < lowest)
137                                 lowest = results[j];
138                         if (results[j] > highest)
139                                 highest = results[j];
140                 }
141                 /* Expect within 20% */
142                 ok(lowest > 35000, "hash_pointer byte %i lowest %i", i, lowest);
143                 ok(highest < 53000, "hash_pointer byte %i highest %i",
144                    i, highest);
145                 diag("hash_pointer byte %i, range %u-%u", i, lowest, highest);
146         }
147
148         return exit_status();
149 }