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