]> git.proxmox.com Git - rustc.git/blob - src/jemalloc/test/unit/ckh.c
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / jemalloc / test / unit / ckh.c
1 #include "test/jemalloc_test.h"
2
3 TEST_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, ckh_string_keycomp),
11 "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 }
18 TEST_END
19
20 TEST_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, ckh_string_keycomp),
36 "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 }
106 TEST_END
107
108 TEST_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 }
204 TEST_END
205
206 int
207 main(void)
208 {
209
210 return (test(
211 test_new_delete,
212 test_count_insert_search_remove,
213 test_insert_iter_remove));
214 }