1 /* Key is an unsigned int, not a pointer. */
3 #if !defined(HAVE_TYPEOF) || !HAVE_TYPEOF
4 #define HTABLE_KTYPE(keyof, type) unsigned int
6 #include <ccan/htable/htable_type.h>
7 #include <ccan/htable/htable.c>
8 #include <ccan/tap/tap.h>
13 #define NUM_VALS (1 << NUM_BITS)
16 /* Makes sure we don't try to treat and obj as a key or vice versa */
21 static const unsigned int objkey(const struct obj *obj)
26 /* We use the number divided by two as the hash (for lots of
27 collisions), plus set all the higher bits so we can detect if they
28 don't get masked out. */
29 static size_t objhash(const unsigned int key)
32 h |= -1UL << NUM_BITS;
36 static bool cmp(const struct obj *obj, const unsigned int key)
38 return obj->key == key;
41 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
43 static void add_vals(struct htable_obj *ht,
44 struct obj val[], unsigned int num)
48 for (i = 0; i < num; i++) {
49 if (htable_obj_get(ht, i)) {
50 fail("%u already in hash", i);
53 htable_obj_add(ht, &val[i]);
54 if (htable_obj_get(ht, i) != &val[i]) {
55 fail("%u not added to hash", i);
59 pass("Added %u numbers to hash", i);
62 static void find_vals(const struct htable_obj *ht,
63 const struct obj val[], unsigned int num)
67 for (i = 0; i < num; i++) {
68 if (htable_obj_get(ht, i) != &val[i]) {
69 fail("%u not found in hash", i);
73 pass("Found %u numbers in hash", i);
76 static void del_vals(struct htable_obj *ht,
77 const struct obj val[], unsigned int num)
81 for (i = 0; i < num; i++) {
82 if (!htable_obj_delkey(ht, val[i].key)) {
83 fail("%u not deleted from hash", i);
87 pass("Deleted %u numbers in hash", i);
90 static void del_vals_bykey(struct htable_obj *ht,
91 const struct obj val[], unsigned int num)
95 for (i = 0; i < num; i++) {
96 if (!htable_obj_delkey(ht, i)) {
97 fail("%u not deleted by key from hash", i);
101 pass("Deleted %u numbers by key from hash", i);
104 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
108 for (i = 0; i < num; i++) {
109 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
115 int main(int argc, char *argv[])
118 struct htable_obj ht, ht2;
119 struct obj val[NUM_VALS], *result;
122 struct htable_obj_iter iter;
125 for (i = 0; i < NUM_VALS; i++)
129 htable_obj_init(&ht);
130 ok1(ht.raw.max == 0);
131 ok1(ht.raw.bits == 0);
133 /* We cannot find an entry which doesn't exist. */
134 ok1(!htable_obj_get(&ht, dne));
136 /* Fill it, it should increase in size. */
137 add_vals(&ht, val, NUM_VALS);
138 ok1(ht.raw.bits == NUM_BITS + 1);
139 ok1(ht.raw.max < (1 << ht.raw.bits));
141 /* Mask should be set. */
142 ok1(ht.raw.common_mask != 0);
143 ok1(ht.raw.common_mask != -1);
144 ok1(check_mask(&ht.raw, val, NUM_VALS));
147 find_vals(&ht, val, NUM_VALS);
148 ok1(!htable_obj_get(&ht, dne));
150 /* Walk once, should get them all. */
152 for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
156 for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
161 del_vals(&ht, val, NUM_VALS);
162 ok1(!htable_obj_get(&ht, val[0].key));
164 /* Worst case, a "pointer" which doesn't have any matching bits. */
165 htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
166 htable_obj_add(&ht, &val[NUM_VALS-1]);
167 ok1(ht.raw.common_mask == 0);
168 ok1(ht.raw.common_bits == 0);
169 /* Delete the bogus one before we trip over it. */
170 htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
173 add_vals(&ht, val, NUM_VALS-1);
175 /* Check we can find them all. */
176 find_vals(&ht, val, NUM_VALS);
177 ok1(!htable_obj_get(&ht, dne));
180 ok1(htable_obj_copy(&ht2, &ht));
182 /* Delete them all by key. */
183 del_vals_bykey(&ht, val, NUM_VALS);
184 del_vals_bykey(&ht2, val, NUM_VALS);
186 /* Write two of the same value. */
188 htable_obj_add(&ht, &val[0]);
189 htable_obj_add(&ht, &val[1]);
192 result = htable_obj_getfirst(&ht, i, &iter);
193 ok1(result == &val[0] || result == &val[1]);
194 if (result == &val[0]) {
195 ok1(htable_obj_getnext(&ht, i, &iter) == &val[1]);
196 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
198 /* Deleting first should make us iterate over the other. */
199 ok1(htable_obj_del(&ht, &val[0]));
200 ok1(htable_obj_getfirst(&ht, i, &iter) == &val[1]);
201 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
203 ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]);
204 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
206 /* Deleting first should make us iterate over the other. */
207 ok1(htable_obj_del(&ht, &val[1]));
208 ok1(htable_obj_getfirst(&ht, i, &iter) == &val[0]);
209 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
212 htable_obj_clear(&ht);
213 htable_obj_clear(&ht2);
214 return exit_status();