1 #include <ccan/htable/htable.h>
2 #include <ccan/htable/htable.c>
3 #include <ccan/tap/tap.h>
8 #define NUM_VALS (1 << NUM_BITS)
10 /* We use the number divided by two as the hash (for lots of
11 collisions), plus set all the higher bits so we can detect if they
12 don't get masked out. */
13 static size_t hash(const void *elem, void *unused UNNEEDED)
15 size_t h = *(uint64_t *)elem / 2;
16 h |= -1UL << NUM_BITS;
20 static bool objcmp(const void *htelem, void *cmpdata)
22 return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
25 static void add_vals(struct htable *ht,
27 unsigned int off, unsigned int num)
31 for (i = off; i < off+num; i++) {
32 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
33 fail("%llu already in hash", (long long)i);
36 htable_add(ht, hash(&val[i], NULL), &val[i]);
37 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
38 fail("%llu not added to hash", (long long)i);
42 pass("Added %llu numbers to hash", (long long)i);
46 static void refill_vals(struct htable *ht,
47 const uint64_t val[], unsigned int num)
51 for (i = 0; i < num; i++) {
52 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
54 htable_add(ht, hash(&val[i], NULL), &val[i]);
59 static void find_vals(struct htable *ht,
60 const uint64_t val[], unsigned int num)
64 for (i = 0; i < num; i++) {
65 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
66 fail("%llu not found in hash", (long long)i);
70 ok1(htable_count(ht) == i);
73 static void del_vals(struct htable *ht,
74 const uint64_t val[], unsigned int num)
78 for (i = 0; i < num; i++) {
79 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
80 fail("%llu not deleted from hash", (long long)i);
84 pass("Deleted %llu numbers in hash", (long long)i);
87 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
91 for (i = 0; i < num; i++) {
92 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
100 unsigned int i, weight;
101 uintptr_t perfect_bit;
103 uint64_t val[NUM_VALS];
106 struct htable_iter iter;
109 for (i = 0; i < NUM_VALS; i++)
113 htable_init(&ht, hash, NULL);
114 ok1(htable_count(&ht) == 0);
115 ok1(ht_max(&ht) == 0);
118 /* We cannot find an entry which doesn't exist. */
119 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
121 /* This should increase it once. */
122 add_vals(&ht, val, 0, 1);
124 ok1(ht_max(&ht) == 1);
126 for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
127 if (ht.common_mask & ((uintptr_t)1 << i)) {
131 /* Only one bit should be clear. */
134 /* Mask should be set. */
135 ok1(check_mask(&ht, val, 1));
137 /* htable_pick should always return that value */
138 ok1(htable_pick(&ht, 0, NULL) == val);
139 ok1(htable_pick(&ht, 1, NULL) == val);
140 ok1(htable_pick(&ht, 0, &iter) == val);
141 ok1(get_raw_ptr(&ht, ht.table[iter.off]) == val);
143 /* This should increase it again. */
144 add_vals(&ht, val, 1, 1);
146 ok1(ht_max(&ht) == 3);
148 /* Mask should be set. */
149 ok1(ht.common_mask != 0);
150 ok1(ht.common_mask != -1);
151 ok1(check_mask(&ht, val, 2));
153 /* Now do the rest. */
154 add_vals(&ht, val, 2, NUM_VALS - 2);
157 find_vals(&ht, val, NUM_VALS);
158 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
160 /* Walk once, should get them all. */
162 for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
167 for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
172 del_vals(&ht, val, NUM_VALS);
173 ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
175 /* Worst case, a "pointer" which doesn't have any matching bits. */
176 htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
177 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
178 ok1(ht.common_mask == 0);
179 ok1(ht.common_bits == 0);
180 /* Get rid of bogus pointer before we trip over it! */
181 htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
184 add_vals(&ht, val, 0, NUM_VALS-1);
186 /* Check we can find them all. */
187 find_vals(&ht, val, NUM_VALS);
188 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
190 /* Corner cases: wipe out the perfect bit using bogus pointer. */
192 htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
193 ok1(ht_perfect_mask(&ht));
194 perfect_bit = ht_perfect_mask(&ht);
195 htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
197 ok1(ht_perfect_mask(&ht) == 0);
198 htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
200 /* Enlarging should restore it... */
201 add_vals(&ht, val, 0, NUM_VALS-1);
203 ok1(ht_perfect_mask(&ht) != 0);
206 ok1(htable_init_sized(&ht, hash, NULL, 1024));
207 ok1(ht_max(&ht) >= 1024);
210 ok1(htable_init_sized(&ht, hash, NULL, 1023));
211 ok1(ht_max(&ht) >= 1023);
214 ok1(htable_init_sized(&ht, hash, NULL, 1025));
215 ok1(ht_max(&ht) >= 1025);
218 ok1(htable_count(&ht) == 0);
219 ok1(htable_pick(&ht, 0, NULL) == NULL);
221 return exit_status();