1#include "test/jemalloc_test.h"
2
3TEST_BEGIN(test_new_delete)
4{
5	ckh_t ckh;
6
7	assert_false(ckh_new(&ckh, 2, ckh_string_hash, ckh_string_keycomp),
8	    "Unexpected ckh_new() error");
9	ckh_delete(&ckh);
10
11	assert_false(ckh_new(&ckh, 3, ckh_pointer_hash, ckh_pointer_keycomp),
12	    "Unexpected ckh_new() error");
13	ckh_delete(&ckh);
14}
15TEST_END
16
17TEST_BEGIN(test_count_insert_search_remove)
18{
19	ckh_t ckh;
20	const char *strs[] = {
21	    "a string",
22	    "A string",
23	    "a string.",
24	    "A string."
25	};
26	const char *missing = "A string not in the hash table.";
27	size_t i;
28
29	assert_false(ckh_new(&ckh, 2, ckh_string_hash, ckh_string_keycomp),
30	    "Unexpected ckh_new() error");
31	assert_zu_eq(ckh_count(&ckh), 0,
32	    "ckh_count() should return %zu, but it returned %zu", ZU(0),
33	    ckh_count(&ckh));
34
35	/* Insert. */
36	for (i = 0; i < sizeof(strs)/sizeof(const char *); i++) {
37		ckh_insert(&ckh, strs[i], strs[i]);
38		assert_zu_eq(ckh_count(&ckh), i+1,
39		    "ckh_count() should return %zu, but it returned %zu", i+1,
40		    ckh_count(&ckh));
41	}
42
43	/* Search. */
44	for (i = 0; i < sizeof(strs)/sizeof(const char *); i++) {
45		union {
46			void *p;
47			const char *s;
48		} k, v;
49		void **kp, **vp;
50		const char *ks, *vs;
51
52		kp = (i & 1) ? &k.p : NULL;
53		vp = (i & 2) ? &v.p : NULL;
54		k.p = NULL;
55		v.p = NULL;
56		assert_false(ckh_search(&ckh, strs[i], kp, vp),
57		    "Unexpected ckh_search() error");
58
59		ks = (i & 1) ? strs[i] : (const char *)NULL;
60		vs = (i & 2) ? strs[i] : (const char *)NULL;
61		assert_ptr_eq((void *)ks, (void *)k.s,
62		    "Key mismatch, i=%zu", i);
63		assert_ptr_eq((void *)vs, (void *)v.s,
64		    "Value mismatch, i=%zu", i);
65	}
66	assert_true(ckh_search(&ckh, missing, NULL, NULL),
67	    "Unexpected ckh_search() success");
68
69	/* Remove. */
70	for (i = 0; i < sizeof(strs)/sizeof(const char *); i++) {
71		union {
72			void *p;
73			const char *s;
74		} k, v;
75		void **kp, **vp;
76		const char *ks, *vs;
77
78		kp = (i & 1) ? &k.p : NULL;
79		vp = (i & 2) ? &v.p : NULL;
80		k.p = NULL;
81		v.p = NULL;
82		assert_false(ckh_remove(&ckh, strs[i], kp, vp),
83		    "Unexpected ckh_remove() error");
84
85		ks = (i & 1) ? strs[i] : (const char *)NULL;
86		vs = (i & 2) ? strs[i] : (const char *)NULL;
87		assert_ptr_eq((void *)ks, (void *)k.s,
88		    "Key mismatch, i=%zu", i);
89		assert_ptr_eq((void *)vs, (void *)v.s,
90		    "Value mismatch, i=%zu", i);
91		assert_zu_eq(ckh_count(&ckh),
92		    sizeof(strs)/sizeof(const char *) - i - 1,
93		    "ckh_count() should return %zu, but it returned %zu",
94		    sizeof(strs)/sizeof(const char *) - i - 1,
95		    ckh_count(&ckh));
96	}
97
98	ckh_delete(&ckh);
99}
100TEST_END
101
102TEST_BEGIN(test_insert_iter_remove)
103{
104#define	NITEMS ZU(1000)
105	ckh_t ckh;
106	void **p[NITEMS];
107	void *q, *r;
108	size_t i;
109
110	assert_false(ckh_new(&ckh, 2, ckh_pointer_hash, ckh_pointer_keycomp),
111	    "Unexpected ckh_new() error");
112
113	for (i = 0; i < NITEMS; i++) {
114		p[i] = mallocx(i+1, 0);
115		assert_ptr_not_null(p[i], "Unexpected mallocx() failure");
116	}
117
118	for (i = 0; i < NITEMS; i++) {
119		size_t j;
120
121		for (j = i; j < NITEMS; j++) {
122			assert_false(ckh_insert(&ckh, p[j], p[j]),
123			    "Unexpected ckh_insert() failure");
124			assert_false(ckh_search(&ckh, p[j], &q, &r),
125			    "Unexpected ckh_search() failure");
126			assert_ptr_eq(p[j], q, "Key pointer mismatch");
127			assert_ptr_eq(p[j], r, "Value pointer mismatch");
128		}
129
130		assert_zu_eq(ckh_count(&ckh), NITEMS,
131		    "ckh_count() should return %zu, but it returned %zu",
132		    NITEMS, ckh_count(&ckh));
133
134		for (j = i + 1; j < NITEMS; j++) {
135			assert_false(ckh_search(&ckh, p[j], NULL, NULL),
136			    "Unexpected ckh_search() failure");
137			assert_false(ckh_remove(&ckh, p[j], &q, &r),
138			    "Unexpected ckh_remove() failure");
139			assert_ptr_eq(p[j], q, "Key pointer mismatch");
140			assert_ptr_eq(p[j], r, "Value pointer mismatch");
141			assert_true(ckh_search(&ckh, p[j], NULL, NULL),
142			    "Unexpected ckh_search() success");
143			assert_true(ckh_remove(&ckh, p[j], &q, &r),
144			    "Unexpected ckh_remove() success");
145		}
146
147		{
148			bool seen[NITEMS];
149			size_t tabind;
150
151			memset(seen, 0, sizeof(seen));
152
153			for (tabind = 0; ckh_iter(&ckh, &tabind, &q, &r) ==
154			    false;) {
155				size_t k;
156
157				assert_ptr_eq(q, r, "Key and val not equal");
158
159				for (k = 0; k < NITEMS; k++) {
160					if (p[k] == q) {
161						assert_false(seen[k],
162						    "Item %zu already seen", k);
163						seen[k] = true;
164						break;
165					}
166				}
167			}
168
169			for (j = 0; j < i + 1; j++)
170				assert_true(seen[j], "Item %zu not seen", j);
171			for (; j < NITEMS; j++)
172				assert_false(seen[j], "Item %zu seen", j);
173		}
174	}
175
176	for (i = 0; i < NITEMS; i++) {
177		assert_false(ckh_search(&ckh, p[i], NULL, NULL),
178		    "Unexpected ckh_search() failure");
179		assert_false(ckh_remove(&ckh, p[i], &q, &r),
180		    "Unexpected ckh_remove() failure");
181		assert_ptr_eq(p[i], q, "Key pointer mismatch");
182		assert_ptr_eq(p[i], r, "Value pointer mismatch");
183		assert_true(ckh_search(&ckh, p[i], NULL, NULL),
184		    "Unexpected ckh_search() success");
185		assert_true(ckh_remove(&ckh, p[i], &q, &r),
186		    "Unexpected ckh_remove() success");
187		dallocx(p[i], 0);
188	}
189
190	assert_zu_eq(ckh_count(&ckh), 0,
191	    "ckh_count() should return %zu, but it returned %zu", ZU(0),
192	    ckh_count(&ckh));
193	ckh_delete(&ckh);
194#undef NITEMS
195}
196TEST_END
197
198int
199main(void)
200{
201
202	return (test(
203	    test_new_delete,
204	    test_count_insert_search_remove,
205	    test_insert_iter_remove));
206}
207