1 #include <ccan/htable/htable_type.h>
2 #include <ccan/htable/htable.c>
3 #include <ccan/tap/tap.h>
7 #define NUM_VALS (1 << HTABLE_BASE_BITS)
13 static const unsigned int *objkey(const struct obj *obj)
18 /* We use the number divided by two as the hash (for lots of
19 collisions), plus set all the higher bits so we can detect if they
20 don't get masked out. */
21 static size_t objhash(const unsigned int *key)
24 h |= -1UL << HTABLE_BASE_BITS;
28 static bool cmp(const unsigned int *key1, const unsigned int *key2)
30 return *key1 == *key2;
33 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, obj);
35 static void add_vals(struct htable_obj *ht,
36 struct obj val[], unsigned int num)
40 for (i = 0; i < num; i++) {
41 if (htable_obj_get(ht, &i)) {
42 fail("%u already in hash", i);
45 htable_obj_add(ht, &val[i]);
46 if (htable_obj_get(ht, &i) != &val[i]) {
47 fail("%u not added to hash", i);
51 pass("Added %u numbers to hash", i);
54 static void find_vals(const struct htable_obj *ht,
55 const struct obj val[], unsigned int num)
59 for (i = 0; i < num; i++) {
60 if (htable_obj_get(ht, &i) != &val[i]) {
61 fail("%u not found in hash", i);
65 pass("Found %u numbers in hash", i);
68 static void del_vals(struct htable_obj *ht,
69 const struct obj val[], unsigned int num)
73 for (i = 0; i < num; i++) {
74 if (!htable_obj_delkey(ht, &val[i].key)) {
75 fail("%u not deleted from hash", i);
79 pass("Deleted %u numbers in hash", i);
82 static void del_vals_bykey(struct htable_obj *ht,
83 const struct obj val[], unsigned int num)
87 for (i = 0; i < num; i++) {
88 if (!htable_obj_delkey(ht, &i)) {
89 fail("%u not deleted by key from hash", i);
93 pass("Deleted %u numbers by key from hash", i);
96 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
100 for (i = 0; i < num; i++) {
101 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
107 int main(int argc, char *argv[])
110 struct htable_obj *ht;
111 struct obj val[NUM_VALS];
114 struct htable_obj_iter iter;
117 for (i = 0; i < NUM_VALS; i++)
121 ht = htable_obj_new();
122 ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits));
123 ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS);
125 /* We cannot find an entry which doesn't exist. */
126 ok1(!htable_obj_get(ht, &dne));
128 /* Fill it, it should increase in size (once). */
129 add_vals(ht, val, NUM_VALS);
130 ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS + 1);
131 ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits));
133 /* Mask should be set. */
134 ok1(((struct htable *)ht)->common_mask != 0);
135 ok1(((struct htable *)ht)->common_mask != -1);
136 ok1(check_mask((struct htable *)ht, val, NUM_VALS));
139 find_vals(ht, val, NUM_VALS);
140 ok1(!htable_obj_get(ht, &dne));
142 /* Walk once, should get them all. */
144 for (p = htable_obj_first(ht,&iter); p; p = htable_obj_next(ht, &iter))
149 del_vals(ht, val, NUM_VALS);
150 ok1(!htable_obj_get(ht, &val[0].key));
152 /* Worst case, a "pointer" which doesn't have any matching bits. */
153 htable_add((struct htable *)ht, 0,
154 (void *)~(uintptr_t)&val[NUM_VALS-1]);
155 htable_obj_add(ht, &val[NUM_VALS-1]);
156 ok1(((struct htable *)ht)->common_mask == 0);
157 ok1(((struct htable *)ht)->common_bits == 0);
158 /* Delete the bogus one before we trip over it. */
159 htable_del((struct htable *)ht, 0,
160 (void *)~(uintptr_t)&val[NUM_VALS-1]);
163 add_vals(ht, val, NUM_VALS-1);
165 /* Check we can find them all. */
166 find_vals(ht, val, NUM_VALS);
167 ok1(!htable_obj_get(ht, &dne));
169 /* Delete them all by key. */
170 del_vals_bykey(ht, val, NUM_VALS);
173 return exit_status();