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