1 /* Key is an unsigned int, not a pointer. */
2 #include "config.h"
3 #if !defined(HAVE_TYPEOF) || !HAVE_TYPEOF
4 #define HTABLE_KTYPE(keyof, type) unsigned int
5 #endif
6 #include <ccan/htable/htable_type.h>
7 #include <ccan/htable/htable.c>
8 #include <ccan/tap/tap.h>
9 #include <stdbool.h>
10 #include <string.h>
11
12 #define NUM_BITS 7
13 #define NUM_VALS (1 << NUM_BITS)
14
15 struct obj {
16 /* Makes sure we don't try to treat and obj as a key or vice versa */
17 unsigned char unused;
18 unsigned int key;
19 };
20
objkey(const struct obj * obj)21 static const unsigned int objkey(const struct obj *obj)
22 {
23 return obj->key;
24 }
25
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. */
objhash(const unsigned int key)29 static size_t objhash(const unsigned int key)
30 {
31 size_t h = key / 2;
32 h |= -1UL << NUM_BITS;
33 return h;
34 }
35
cmp(const struct obj * obj,const unsigned int key)36 static bool cmp(const struct obj *obj, const unsigned int key)
37 {
38 return obj->key == key;
39 }
40
41 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
42
add_vals(struct htable_obj * ht,struct obj val[],unsigned int num)43 static void add_vals(struct htable_obj *ht,
44 struct obj val[], unsigned int num)
45 {
46 unsigned int i;
47
48 for (i = 0; i < num; i++) {
49 if (htable_obj_get(ht, i)) {
50 fail("%u already in hash", i);
51 return;
52 }
53 htable_obj_add(ht, &val[i]);
54 if (htable_obj_get(ht, i) != &val[i]) {
55 fail("%u not added to hash", i);
56 return;
57 }
58 }
59 pass("Added %u numbers to hash", i);
60 }
61
find_vals(const struct htable_obj * ht,const struct obj val[],unsigned int num)62 static void find_vals(const struct htable_obj *ht,
63 const struct obj val[], unsigned int num)
64 {
65 unsigned int i;
66
67 for (i = 0; i < num; i++) {
68 if (htable_obj_get(ht, i) != &val[i]) {
69 fail("%u not found in hash", i);
70 return;
71 }
72 }
73 pass("Found %u numbers in hash", i);
74 }
75
del_vals(struct htable_obj * ht,const struct obj val[],unsigned int num)76 static void del_vals(struct htable_obj *ht,
77 const struct obj val[], unsigned int num)
78 {
79 unsigned int i;
80
81 for (i = 0; i < num; i++) {
82 if (!htable_obj_delkey(ht, val[i].key)) {
83 fail("%u not deleted from hash", i);
84 return;
85 }
86 }
87 pass("Deleted %u numbers in hash", i);
88 }
89
del_vals_bykey(struct htable_obj * ht,const struct obj val[]UNNEEDED,unsigned int num)90 static void del_vals_bykey(struct htable_obj *ht,
91 const struct obj val[] UNNEEDED, unsigned int num)
92 {
93 unsigned int i;
94
95 for (i = 0; i < num; i++) {
96 if (!htable_obj_delkey(ht, i)) {
97 fail("%u not deleted by key from hash", i);
98 return;
99 }
100 }
101 pass("Deleted %u numbers by key from hash", i);
102 }
103
check_mask(struct htable * ht,const struct obj val[],unsigned num)104 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
105 {
106 uint64_t i;
107
108 for (i = 0; i < num; i++) {
109 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
110 return false;
111 }
112 return true;
113 }
114
main(void)115 int main(void)
116 {
117 unsigned int i;
118 struct htable_obj ht, ht2;
119 struct obj val[NUM_VALS], *result;
120 unsigned int dne;
121 void *p;
122 struct htable_obj_iter iter;
123
124 plan_tests(29);
125 for (i = 0; i < NUM_VALS; i++)
126 val[i].key = i;
127 dne = i;
128
129 htable_obj_init(&ht);
130 ok1(ht_max(&ht.raw) == 0);
131 ok1(ht.raw.bits == 0);
132
133 /* We cannot find an entry which doesn't exist. */
134 ok1(!htable_obj_get(&ht, dne));
135
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_max(&ht.raw) < (1 << ht.raw.bits));
140
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));
145
146 /* Find all. */
147 find_vals(&ht, val, NUM_VALS);
148 ok1(!htable_obj_get(&ht, dne));
149
150 /* Walk once, should get them all. */
151 i = 0;
152 for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
153 i++;
154 ok1(i == NUM_VALS);
155 i = 0;
156 for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
157 i++;
158 ok1(i == NUM_VALS);
159
160 /* Delete all. */
161 del_vals(&ht, val, NUM_VALS);
162 ok1(!htable_obj_get(&ht, val[0].key));
163
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]);
171
172 /* Add the rest. */
173 add_vals(&ht, val, NUM_VALS-1);
174
175 /* Check we can find them all. */
176 find_vals(&ht, val, NUM_VALS);
177 ok1(!htable_obj_get(&ht, dne));
178
179 /* Check copy. */
180 ok1(htable_obj_copy(&ht2, &ht));
181
182 /* Delete them all by key. */
183 del_vals_bykey(&ht, val, NUM_VALS);
184 del_vals_bykey(&ht2, val, NUM_VALS);
185
186 /* Write two of the same value. */
187 val[1] = val[0];
188 htable_obj_add(&ht, &val[0]);
189 htable_obj_add(&ht, &val[1]);
190 i = 0;
191
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);
197
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);
202 } else {
203 ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]);
204 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
205
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);
210 }
211
212 htable_obj_clear(&ht);
213 htable_obj_clear(&ht2);
214 return exit_status();
215 }
216