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)
10 /* Makes sure we don't try to treat and obj as a key or vice versa */
15 static const unsigned int *objkey(const struct obj *obj)
20 /* We use the number divided by two as the hash (for lots of
21 collisions), plus set all the higher bits so we can detect if they
22 don't get masked out. */
23 static size_t objhash(const unsigned int *key)
26 h |= -1UL << HTABLE_BASE_BITS;
30 static bool cmp(const struct obj *obj, const unsigned int *key)
32 return obj->key == *key;
35 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, obj);
37 static void add_vals(struct htable_obj *ht,
38 struct obj val[], unsigned int num)
42 for (i = 0; i < num; i++) {
43 if (htable_obj_get(ht, &i)) {
44 fail("%u already in hash", i);
47 htable_obj_add(ht, &val[i]);
48 if (htable_obj_get(ht, &i) != &val[i]) {
49 fail("%u not added to hash", i);
53 pass("Added %u numbers to hash", i);
56 static void find_vals(const struct htable_obj *ht,
57 const struct obj val[], unsigned int num)
61 for (i = 0; i < num; i++) {
62 if (htable_obj_get(ht, &i) != &val[i]) {
63 fail("%u not found in hash", i);
67 pass("Found %u numbers in hash", i);
70 static void del_vals(struct htable_obj *ht,
71 const struct obj val[], unsigned int num)
75 for (i = 0; i < num; i++) {
76 if (!htable_obj_delkey(ht, &val[i].key)) {
77 fail("%u not deleted from hash", i);
81 pass("Deleted %u numbers in hash", i);
84 static void del_vals_bykey(struct htable_obj *ht,
85 const struct obj val[], unsigned int num)
89 for (i = 0; i < num; i++) {
90 if (!htable_obj_delkey(ht, &i)) {
91 fail("%u not deleted by key from hash", i);
95 pass("Deleted %u numbers by key from hash", i);
98 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
102 for (i = 0; i < num; i++) {
103 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
109 int main(int argc, char *argv[])
112 struct htable_obj *ht;
113 struct obj val[NUM_VALS];
116 struct htable_obj_iter iter;
119 for (i = 0; i < NUM_VALS; i++)
123 ht = htable_obj_new();
124 ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits));
125 ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS);
127 /* We cannot find an entry which doesn't exist. */
128 ok1(!htable_obj_get(ht, &dne));
130 /* Fill it, it should increase in size (once). */
131 add_vals(ht, val, NUM_VALS);
132 ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS + 1);
133 ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits));
135 /* Mask should be set. */
136 ok1(((struct htable *)ht)->common_mask != 0);
137 ok1(((struct htable *)ht)->common_mask != -1);
138 ok1(check_mask((struct htable *)ht, val, NUM_VALS));
141 find_vals(ht, val, NUM_VALS);
142 ok1(!htable_obj_get(ht, &dne));
144 /* Walk once, should get them all. */
146 for (p = htable_obj_first(ht,&iter); p; p = htable_obj_next(ht, &iter))
151 del_vals(ht, val, NUM_VALS);
152 ok1(!htable_obj_get(ht, &val[0].key));
154 /* Worst case, a "pointer" which doesn't have any matching bits. */
155 htable_add((struct htable *)ht, 0,
156 (void *)~(uintptr_t)&val[NUM_VALS-1]);
157 htable_obj_add(ht, &val[NUM_VALS-1]);
158 ok1(((struct htable *)ht)->common_mask == 0);
159 ok1(((struct htable *)ht)->common_bits == 0);
160 /* Delete the bogus one before we trip over it. */
161 htable_del((struct htable *)ht, 0,
162 (void *)~(uintptr_t)&val[NUM_VALS-1]);
165 add_vals(ht, val, NUM_VALS-1);
167 /* Check we can find them all. */
168 find_vals(ht, val, NUM_VALS);
169 ok1(!htable_obj_get(ht, &dne));
171 /* Delete them all by key. */
172 del_vals_bykey(ht, val, NUM_VALS);
175 return exit_status();