1#include "cunit/cyrunit.h"
2#include "strarray.h"
3#include "util.h"
4#include "hash.h"
5
6static void count_cb(const char *key __attribute__((unused)),
7                     void *data __attribute__((unused)),
8                     void *rock)
9{
10    unsigned int *countp = (unsigned int *)rock;
11    (*countp)++;
12}
13
14static void printer_cb(const char *key,
15                       void *data,
16                       void *rock)
17{
18    strarray_t *sa = (strarray_t *)rock;
19    struct buf buf = BUF_INITIALIZER;
20    buf_printf(&buf, "%s=%s", key, (char *)data);
21    strarray_appendm(sa, buf_release(&buf));
22}
23
24
25#define KEY0    "Yale"
26#define KEY1    "Lockwood"
27#define KEY2    "Skeleton"
28static const char * const values[] = {
29    "Paper", "Glass", "Wood", "Diamond"
30};
31#define VALUE0      ((void *)values[0])
32#define VALUE1      ((void *)values[1])
33#define VALUE2      ((void *)values[2])
34#define VALUE3      ((void *)values[3])
35
36static void test_old(void)
37{
38    /* this is the old test code in lib/hash.c converted to CUnit */
39    hash_table table;
40
41    static const char * const strings[] = {
42        "1","2","3","4","5","A decently long string",
43        NULL
44    };
45
46    static const char * const junk[] = {
47        "The first data",
48        "The second data",
49        "The third data",
50        "The fourth data",
51        "The fifth datum",
52        "The sixth piece of data"
53    };
54
55    int i;
56    void *j;
57    strarray_t sa = STRARRAY_INITIALIZER;
58
59    construct_hash_table(&table, 200, 1);
60
61    for (i = 0 ; NULL != strings[i] ; i++ ) {
62        j = hash_insert(strings[i], (void *)junk[i], &table);
63        CU_ASSERT_PTR_EQUAL((void *)junk[i], j);
64    }
65
66    for (i = 0 ; NULL != strings[i] ; i++) {
67        j = hash_lookup(strings[i], &table);
68        CU_ASSERT_PTR_NOT_NULL(j);
69        CU_ASSERT_PTR_EQUAL((void *)junk[i], j);
70    }
71
72    for (i = 0 ; NULL != strings[i] ; i++) {
73        strarray_truncate(&sa, 0);
74        hash_enumerate(&table, printer_cb, &sa);
75        CU_ASSERT_EQUAL(6-i, sa.count);
76        if (i < 1) CU_ASSERT(strarray_find(&sa, "1=The first data", 0) >= 0);
77        if (i < 2) CU_ASSERT(strarray_find(&sa, "2=The second data", 0) >= 0);
78        if (i < 3) CU_ASSERT(strarray_find(&sa, "3=The third data", 0) >= 0);
79        if (i < 4) CU_ASSERT(strarray_find(&sa, "4=The fourth data", 0) >= 0);
80        if (i < 5) CU_ASSERT(strarray_find(&sa, "5=The fifth datum", 0) >= 0);
81        if (i < 6) CU_ASSERT(strarray_find(&sa, "A decently long string=The sixth piece of data", 0) >= 0);
82        strarray_fini(&sa);
83
84        j = hash_del((char *)strings[i], &table);
85        CU_ASSERT_PTR_EQUAL((void *)junk[i], j);
86    }
87
88    for (i = 0 ; NULL != strings[i] ; i++) {
89        j = hash_lookup(strings[i], &table);
90        CU_ASSERT_PTR_NULL(j);
91    }
92
93    free_hash_table(&table, NULL);
94}
95
96static void test_empty(void)
97{
98    hash_table ht;
99    hash_table *h;
100    void *d;
101    unsigned int count;
102
103    /* construct an empty hash table */
104    h = construct_hash_table(&ht, 1024, 0);
105    CU_ASSERT_PTR_EQUAL(&ht, h);
106
107    /* lookup the empty hash table */
108    d = hash_lookup(KEY0, &ht);
109    CU_ASSERT_PTR_NULL(d);
110
111    /* delete from the empty hash table */
112    d = hash_del(KEY0, &ht);
113    CU_ASSERT_PTR_NULL(d);
114
115    /* enumerate the empty hash table */
116    count = 0;
117    hash_enumerate(&ht, count_cb, &count);
118    CU_ASSERT_EQUAL(0, count);
119
120    /* check hash_numrecords */
121    CU_ASSERT_EQUAL(0, hash_numrecords(&ht));
122
123    /* free the hash table */
124    free_hash_table(&ht, NULL);
125}
126
127static void test_reinsert(void)
128{
129    hash_table ht;
130    hash_table *h;
131    void *d;
132    unsigned int count;
133
134    /* construct an empty hash table */
135    h = construct_hash_table(&ht, 1024, 0);
136    CU_ASSERT_PTR_EQUAL(&ht, h);
137
138    /* insert into the table */
139    d = hash_insert(KEY0, VALUE0, &ht);
140    /* no old data so hash_insert() returns the new data pointer */
141    CU_ASSERT_PTR_EQUAL(VALUE0, d);
142
143    /* lookup the hash table */
144    d = hash_lookup(KEY0, &ht);
145    CU_ASSERT_PTR_EQUAL(VALUE0, d);
146
147    /* enumerate the hash table */
148    count = 0;
149    hash_enumerate(&ht, count_cb, &count);
150    CU_ASSERT_EQUAL(1, count);
151
152    /* check hash_numrecords */
153    CU_ASSERT_EQUAL(1, hash_numrecords(&ht));
154
155    /* re-insert into the hash table */
156    d = hash_insert(KEY0, VALUE1, &ht);
157    /* get the old value back */
158    CU_ASSERT_PTR_EQUAL(VALUE0, d);
159
160    /* lookup the hash table */
161    d = hash_lookup(KEY0, &ht);
162    CU_ASSERT_PTR_EQUAL(VALUE1, d);
163
164    /* enumerate the hash table */
165    count = 0;
166    hash_enumerate(&ht, count_cb, &count);
167    CU_ASSERT_EQUAL(1, count);
168
169    /* check hash_numrecords */
170    CU_ASSERT_EQUAL(1, hash_numrecords(&ht));
171
172    /* delete from the hash table */
173    d = hash_del(KEY0, &ht);
174    CU_ASSERT_PTR_EQUAL(VALUE1, d);
175
176    /* lookup the hash table */
177    d = hash_lookup(KEY0, &ht);
178    CU_ASSERT_PTR_NULL(d);
179
180    /* enumerate the hash table */
181    count = 0;
182    hash_enumerate(&ht, count_cb, &count);
183    CU_ASSERT_EQUAL(0, count);
184
185    /* check hash_numrecords */
186    CU_ASSERT_EQUAL(0, hash_numrecords(&ht));
187
188    /* free the hash table */
189    free_hash_table(&ht, NULL);
190}
191
192static const char *key(unsigned int i)
193{
194    static char buf[32];
195    snprintf(buf, sizeof(buf), "%u", i);
196    return buf;
197}
198
199static void *value(unsigned int i)
200{
201    return (void *)(unsigned long)(0xdead0000 + i);
202}
203
204static unsigned int freed_count = 0;
205static void lincoln(void *x __attribute__((unused)))
206{
207    ++freed_count;
208}
209
210/* test overloading a hash table with more
211 * entries than the configured number of buckets */
212static void test_many(void)
213{
214    hash_table ht;
215    hash_table *h;
216    void *d;
217    unsigned int count;
218#define N 2048
219    unsigned int i;
220
221    /* construct an empty hash table */
222    h = construct_hash_table(&ht, N/8, 0);
223    CU_ASSERT_PTR_EQUAL(&ht, h);
224
225    /* insert lots of entries into the table */
226    for (i = 0 ; i < N ; i++) {
227        d = hash_insert(key(i), value(i), &ht);
228        CU_ASSERT_PTR_EQUAL(value(i), d);
229    }
230
231    /* lookup all the entries in the hash table */
232    for (i = 0 ; i < N ; i++) {
233        d = hash_lookup(key(i), &ht);
234        CU_ASSERT_PTR_EQUAL(value(i), d);
235    }
236
237    /* lookup and delete entries that aren't there */
238    for (i = N ; i < 2*N ; i++) {
239        d = hash_lookup(key(i), &ht);
240        CU_ASSERT_PTR_NULL(d);
241        d = hash_del(key(i), &ht);
242        CU_ASSERT_PTR_NULL(d);
243    }
244    d = hash_del("Not here please stop looking", &ht);
245    CU_ASSERT_PTR_NULL(d);
246    d = hash_lookup("Not here please stop looking", &ht);
247    CU_ASSERT_PTR_NULL(d);
248
249    /* enumerate the hash table */
250    count = 0;
251    hash_enumerate(&ht, count_cb, &count);
252    CU_ASSERT_EQUAL(N, count);
253
254    /* check hash_numrecords */
255    CU_ASSERT_EQUAL(N, hash_numrecords(&ht));
256
257    /* delete from the hash table */
258    for (i = 0 ; i < N ; i++) {
259        d = hash_del(key(i), &ht);
260        CU_ASSERT_PTR_EQUAL(value(i), d);
261    }
262
263    /* all the entries should be gone */
264    for (i = 0 ; i < N ; i++) {
265        d = hash_lookup(key(i), &ht);
266        CU_ASSERT_PTR_NULL(d);
267    }
268
269    /* enumerate the hash table: should be empty now */
270    count = 0;
271    hash_enumerate(&ht, count_cb, &count);
272    CU_ASSERT_EQUAL(0, count);
273
274    /* check hash_numrecords */
275    CU_ASSERT_EQUAL(0, hash_numrecords(&ht));
276
277    /* free the hash table */
278    freed_count = 0;
279    free_hash_table(&ht, lincoln);
280    CU_ASSERT_EQUAL(0, freed_count);
281}
282
283static void test_freeing_nonempty(void)
284{
285    hash_table ht;
286    hash_table *h;
287    void *d;
288    unsigned int count;
289#define N 2048
290    unsigned int i;
291
292    /* construct an empty hash table */
293    h = construct_hash_table(&ht, N/8, 0);
294    CU_ASSERT_PTR_EQUAL(&ht, h);
295
296    /* insert lots of entries into the table */
297    for (i = 0 ; i < N ; i++) {
298        d = hash_insert(key(i), value(i), &ht);
299        CU_ASSERT_PTR_EQUAL(value(i), d);
300    }
301
302    /* enumerate the hash table */
303    count = 0;
304    hash_enumerate(&ht, count_cb, &count);
305    CU_ASSERT_EQUAL(N, count);
306
307    /* check hash_numrecords */
308    CU_ASSERT_EQUAL(N, hash_numrecords(&ht));
309
310    /* free the hash table */
311    freed_count = 0;
312    free_hash_table(&ht, lincoln);
313    CU_ASSERT_EQUAL(N, freed_count);
314}
315
316static void test_iter(void)
317{
318    hash_table ht;
319
320    /* construct an empty hash table */
321    construct_hash_table(&ht, 16, 0);
322
323    hash_insert("foo", (void*)1, &ht);
324    hash_insert("bar", (void*)2, &ht);
325    hash_insert("baz", (void*)3, &ht);
326
327    hash_iter *iter = hash_table_iter(&ht);
328
329    CU_ASSERT_PTR_NOT_NULL(iter);
330
331    /* run twice to test hash_iter_reset at end of first loop */
332    int i;
333    for (i = 0; i < 2; i++) {
334        strarray_t seen = STRARRAY_INITIALIZER;
335
336        CU_ASSERT(hash_iter_has_next(iter));
337        while (hash_iter_next(iter)) {
338            const char *key = hash_iter_key(iter);
339            CU_ASSERT_PTR_NOT_NULL(key);
340            strarray_append(&seen, key);
341
342            uintptr_t val = (uintptr_t) hash_iter_val(iter);
343            if (!strcmp(key, "foo")) {
344                CU_ASSERT_EQUAL(1, val);
345            }
346            else if (!strcmp(key, "bar")) {
347                CU_ASSERT_EQUAL(2, val);
348            }
349            else if (!strcmp(key, "baz")) {
350                CU_ASSERT_EQUAL(3, val);
351            }
352            else CU_ASSERT(0);
353
354            if (strarray_size(&seen) < 3) {
355                CU_ASSERT(hash_iter_has_next(iter));
356            }
357        }
358        CU_ASSERT(!hash_iter_has_next(iter));
359
360        CU_ASSERT_EQUAL(3, strarray_size(&seen));
361        CU_ASSERT(strarray_find(&seen, "foo", 0) >= 0);
362        CU_ASSERT(strarray_find(&seen, "bar", 0) >= 0);
363        CU_ASSERT(strarray_find(&seen, "baz", 0) >= 0);
364        strarray_fini(&seen);
365        hash_iter_reset(iter);
366    }
367
368    hash_iter_free(&iter);
369    free_hash_table(&ht, NULL);
370}
371/* vim: set ft=c: */
372