1 #define CCAN_HTABLE_DEBUG
2 #include <ccan/htable/htable.h>
3 #include <ccan/htable/htable.c>
4 #include <ccan/tap/tap.h>
5 #include <stdbool.h>
6 #include <string.h>
7
8 #define NUM_BITS 7
9 #define NUM_VALS (1 << NUM_BITS)
10
11 static void *bad_pointer;
12
13 /* We use the number divided by two as the hash (for lots of
14 collisions), plus set all the higher bits so we can detect if they
15 don't get masked out. */
hash(const void * elem,void * unused UNNEEDED)16 static size_t hash(const void *elem, void *unused UNNEEDED)
17 {
18 size_t h;
19
20 /* With CCAN_HTABLE_DEBUG enabled, it will try to hash each element,
21 * including this one... */
22 if (elem == bad_pointer)
23 return 0;
24
25 h = *(uint64_t *)elem / 2;
26 h |= -1UL << NUM_BITS;
27 return h;
28 }
29
objcmp(const void * htelem,void * cmpdata)30 static bool objcmp(const void *htelem, void *cmpdata)
31 {
32 return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
33 }
34
add_vals(struct htable * ht,const uint64_t val[],unsigned int off,unsigned int num)35 static void add_vals(struct htable *ht,
36 const uint64_t val[],
37 unsigned int off, unsigned int num)
38 {
39 uint64_t i;
40
41 for (i = off; i < off+num; i++) {
42 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
43 fail("%llu already in hash", (long long)i);
44 return;
45 }
46 htable_add(ht, hash(&val[i], NULL), &val[i]);
47 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
48 fail("%llu not added to hash", (long long)i);
49 return;
50 }
51 }
52 pass("Added %llu numbers to hash", (long long)i);
53 }
54
55 #if 0
56 static void refill_vals(struct htable *ht,
57 const uint64_t val[], unsigned int num)
58 {
59 uint64_t i;
60
61 for (i = 0; i < num; i++) {
62 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
63 continue;
64 htable_add(ht, hash(&val[i], NULL), &val[i]);
65 }
66 }
67 #endif
68
find_vals(struct htable * ht,const uint64_t val[],unsigned int num)69 static void find_vals(struct htable *ht,
70 const uint64_t val[], unsigned int num)
71 {
72 uint64_t i;
73
74 for (i = 0; i < num; i++) {
75 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
76 fail("%llu not found in hash", (long long)i);
77 return;
78 }
79 }
80 pass("Found %llu numbers in hash", (long long)i);
81 }
82
del_vals(struct htable * ht,const uint64_t val[],unsigned int num)83 static void del_vals(struct htable *ht,
84 const uint64_t val[], unsigned int num)
85 {
86 uint64_t i;
87
88 for (i = 0; i < num; i++) {
89 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
90 fail("%llu not deleted from hash", (long long)i);
91 return;
92 }
93 }
94 pass("Deleted %llu numbers in hash", (long long)i);
95 }
96
check_mask(struct htable * ht,uint64_t val[],unsigned num)97 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
98 {
99 uint64_t i;
100
101 for (i = 0; i < num; i++) {
102 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
103 return false;
104 }
105 return true;
106 }
107
main(void)108 int main(void)
109 {
110 unsigned int i, weight;
111 uintptr_t perfect_bit;
112 struct htable ht;
113 uint64_t val[NUM_VALS];
114 uint64_t dne;
115 void *p;
116 struct htable_iter iter;
117
118 plan_tests(36);
119 for (i = 0; i < NUM_VALS; i++)
120 val[i] = i;
121 dne = i;
122
123 htable_init(&ht, hash, NULL);
124 ok1(ht_max(&ht) == 0);
125 ok1(ht.bits == 0);
126
127 /* We cannot find an entry which doesn't exist. */
128 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
129
130 /* This should increase it once. */
131 add_vals(&ht, val, 0, 1);
132 ok1(ht.bits == 1);
133 ok1(ht_max(&ht) == 1);
134 weight = 0;
135 for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
136 if (ht.common_mask & ((uintptr_t)1 << i)) {
137 weight++;
138 }
139 }
140 /* Only one bit should be clear. */
141 ok1(weight == i-1);
142
143 /* Mask should be set. */
144 ok1(check_mask(&ht, val, 1));
145
146 /* This should increase it again. */
147 add_vals(&ht, val, 1, 1);
148 ok1(ht.bits == 2);
149 ok1(ht_max(&ht) == 3);
150
151 /* Mask should be set. */
152 ok1(ht.common_mask != 0);
153 ok1(ht.common_mask != -1);
154 ok1(check_mask(&ht, val, 2));
155
156 /* Now do the rest. */
157 add_vals(&ht, val, 2, NUM_VALS - 2);
158
159 /* Find all. */
160 find_vals(&ht, val, NUM_VALS);
161 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
162
163 /* Walk once, should get them all. */
164 i = 0;
165 for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
166 i++;
167 ok1(i == NUM_VALS);
168
169 i = 0;
170 for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
171 i++;
172 ok1(i == NUM_VALS);
173
174 /* Delete all. */
175 del_vals(&ht, val, NUM_VALS);
176 ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
177
178 /* Worst case, a "pointer" which doesn't have any matching bits. */
179 bad_pointer = (void *)~(uintptr_t)&val[NUM_VALS-1];
180 htable_add(&ht, 0, bad_pointer);
181 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
182 ok1(ht.common_mask == 0);
183 ok1(ht.common_bits == 0);
184 /* Get rid of bogus pointer before we trip over it! */
185 htable_del(&ht, 0, bad_pointer);
186
187 /* Add the rest. */
188 add_vals(&ht, val, 0, NUM_VALS-1);
189
190 /* Check we can find them all. */
191 find_vals(&ht, val, NUM_VALS);
192 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
193
194 /* Corner cases: wipe out the perfect bit using bogus pointer. */
195 htable_clear(&ht);
196 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
197 ok1(ht_perfect_mask(&ht));
198 perfect_bit = ht_perfect_mask(&ht);
199 bad_pointer = (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit);
200 htable_add(&ht, 0, bad_pointer);
201 ok1(ht_perfect_mask(&ht) == 0);
202 htable_del(&ht, 0, bad_pointer);
203
204 /* Enlarging should restore it... */
205 add_vals(&ht, val, 0, NUM_VALS-1);
206
207 ok1(ht_perfect_mask(&ht) != 0);
208 htable_clear(&ht);
209
210 ok1(htable_init_sized(&ht, hash, NULL, 1024));
211 ok1(ht_max(&ht) >= 1024);
212 htable_clear(&ht);
213
214 ok1(htable_init_sized(&ht, hash, NULL, 1023));
215 ok1(ht_max(&ht) >= 1023);
216 htable_clear(&ht);
217
218 ok1(htable_init_sized(&ht, hash, NULL, 1025));
219 ok1(ht_max(&ht) >= 1025);
220 htable_clear(&ht);
221
222 return exit_status();
223 }
224