1 #include <ccan/htable/htable_type.h>
2 #include <ccan/htable/htable.c>
3 #include <ccan/tap/tap.h>
8 #define NUM_VALS (1 << NUM_BITS)
11 /* Makes sure we don't try to treat and obj as a key or vice versa */
16 static const unsigned int *objkey(const struct obj *obj)
21 /* We use the number divided by two as the hash (for lots of
22 collisions), plus set all the higher bits so we can detect if they
23 don't get masked out. */
24 static size_t objhash(const unsigned int *key)
27 h |= -1UL << NUM_BITS;
31 static bool cmp(const struct obj *obj, const unsigned int *key)
33 return obj->key == *key;
36 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
38 static void add_vals(struct htable_obj *ht,
39 struct obj val[], unsigned int num)
43 for (i = 0; i < num; i++) {
44 if (htable_obj_get(ht, &i)) {
45 fail("%u already in hash", i);
48 htable_obj_add(ht, &val[i]);
49 if (htable_obj_get(ht, &i) != &val[i]) {
50 fail("%u not added to hash", i);
54 pass("Added %u numbers to hash", i);
57 static void find_vals(const struct htable_obj *ht,
58 const struct obj val[], unsigned int num)
62 for (i = 0; i < num; i++) {
63 if (htable_obj_get(ht, &i) != &val[i]) {
64 fail("%u not found in hash", i);
68 ok1(htable_obj_count(ht) == i);
71 static void del_vals(struct htable_obj *ht,
72 const struct obj val[], unsigned int num)
76 for (i = 0; i < num; i++) {
77 if (!htable_obj_delkey(ht, &val[i].key)) {
78 fail("%u not deleted from hash", i);
82 pass("Deleted %u numbers in hash", i);
85 static void del_vals_bykey(struct htable_obj *ht,
86 const struct obj val[] UNNEEDED, unsigned int num)
90 for (i = 0; i < num; i++) {
91 if (!htable_obj_delkey(ht, &i)) {
92 fail("%u not deleted by key from hash", i);
96 pass("Deleted %u numbers by key from hash", i);
99 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
103 for (i = 0; i < num; i++) {
104 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
113 struct htable_obj ht, ht2;
114 struct obj val[NUM_VALS], *result;
117 struct htable_obj_iter iter;
120 for (i = 0; i < NUM_VALS; i++)
124 htable_obj_init(&ht);
125 ok1(htable_obj_count(&ht) == 0);
126 ok1(ht_max(&ht.raw) == 0);
127 ok1(ht.raw.bits == 0);
129 /* We cannot find an entry which doesn't exist. */
130 ok1(!htable_obj_get(&ht, &dne));
131 ok1(!htable_obj_pick(&ht, 0, NULL));
133 /* Fill it, it should increase in size. */
134 add_vals(&ht, val, NUM_VALS);
135 ok1(ht.raw.bits == NUM_BITS + 1);
136 ok1(ht_max(&ht.raw) < (1 << ht.raw.bits));
138 /* Mask should be set. */
139 ok1(ht.raw.common_mask != 0);
140 ok1(ht.raw.common_mask != -1);
141 ok1(check_mask(&ht.raw, val, NUM_VALS));
144 find_vals(&ht, val, NUM_VALS);
145 ok1(!htable_obj_get(&ht, &dne));
146 ok1(htable_obj_pick(&ht, 0, NULL));
147 ok1(htable_obj_pick(&ht, 0, &iter));
149 /* Walk once, should get them all. */
151 for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
155 for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
160 del_vals(&ht, val, NUM_VALS);
161 ok1(!htable_obj_get(&ht, &val[0].key));
163 /* Worst case, a "pointer" which doesn't have any matching bits. */
164 htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
165 htable_obj_add(&ht, &val[NUM_VALS-1]);
166 ok1(ht.raw.common_mask == 0);
167 ok1(ht.raw.common_bits == 0);
168 /* Delete the bogus one before we trip over it. */
169 htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
172 add_vals(&ht, val, NUM_VALS-1);
174 /* Check we can find them all. */
175 find_vals(&ht, val, NUM_VALS);
176 ok1(!htable_obj_get(&ht, &dne));
179 ok1(htable_obj_copy(&ht2, &ht));
181 /* Delete them all by key. */
182 del_vals_bykey(&ht, val, NUM_VALS);
183 del_vals_bykey(&ht2, val, NUM_VALS);
185 /* Write two of the same value. */
187 htable_obj_add(&ht, &val[0]);
188 htable_obj_add(&ht, &val[1]);
191 result = htable_obj_getfirst(&ht, &i, &iter);
192 ok1(result == &val[0] || result == &val[1]);
193 if (result == &val[0]) {
194 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]);
195 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
197 /* Deleting first should make us iterate over the other. */
198 ok1(htable_obj_del(&ht, &val[0]));
199 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]);
200 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
202 ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]);
203 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
205 /* Deleting first should make us iterate over the other. */
206 ok1(htable_obj_del(&ht, &val[1]));
207 ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]);
208 ok1(htable_obj_getnext(&ht, &i, &iter) == NULL);
211 htable_obj_clear(&ht);
212 ok1(htable_obj_count(&ht) == 0);
213 htable_obj_clear(&ht2);
214 ok1(htable_obj_count(&ht2) == 0);
215 return exit_status();