1 /*
2 * Copyright (C) 2014 Intel Corporation. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include <errno.h>
19 #include <stddef.h>
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <string.h>
23 #include <unistd.h>
24
25 #include <shared/hash.h>
26 #include <shared/util.h>
27
28 #include "testsuite.h"
29
30 static int freecount;
31
countfreecalls(void * v)32 static void countfreecalls(void *v)
33 {
34 freecount++;
35 }
36
test_hash_new(const struct test * t)37 static int test_hash_new(const struct test *t)
38 {
39 struct hash *h = hash_new(8, NULL);
40 assert_return(h != NULL, EXIT_FAILURE);
41 hash_free(h);
42 return 0;
43 }
44 DEFINE_TEST(test_hash_new,
45 .description = "test hash_new");
46
47
test_hash_get_count(const struct test * t)48 static int test_hash_get_count(const struct test *t)
49 {
50 struct hash *h = hash_new(8, NULL);
51 const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
52 const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
53
54 hash_add(h, k1, v1);
55 hash_add(h, k2, v2);
56 hash_add(h, k3, v3);
57
58 assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
59
60 hash_free(h);
61 return 0;
62 }
63 DEFINE_TEST(test_hash_get_count,
64 .description = "test hash_add / hash_get_count");
65
66
test_hash_replace(const struct test * t)67 static int test_hash_replace(const struct test *t)
68 {
69 struct hash *h = hash_new(8, countfreecalls);
70 const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
71 const char *v1 = "v1", *v2 = "v2", *v3 = "v3", *v4 = "v4";
72 const char *v;
73 int r = 0;
74
75 r |= hash_add(h, k1, v1);
76 r |= hash_add(h, k2, v2);
77 r |= hash_add(h, k3, v3);
78
79 /* replace v1 */
80 r |= hash_add(h, k1, v4);
81
82 assert_return(r == 0, EXIT_FAILURE);
83 assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
84
85 v = hash_find(h, "k1");
86 assert_return(streq(v, v4), EXIT_FAILURE);
87
88 assert_return(freecount == 1, EXIT_FAILURE);
89
90 hash_free(h);
91 return 0;
92 }
93 DEFINE_TEST(test_hash_replace,
94 .description = "test hash_add replacing existing value");
95
96
test_hash_replace_failing(const struct test * t)97 static int test_hash_replace_failing(const struct test *t)
98 {
99 struct hash *h = hash_new(8, countfreecalls);
100 const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
101 const char *v1 = "v1", *v2 = "v2", *v3 = "v3", *v4 = "v4";
102 const char *v;
103 int r = 0;
104
105 r |= hash_add(h, k1, v1);
106 r |= hash_add(h, k2, v2);
107 r |= hash_add(h, k3, v3);
108
109 assert_return(r == 0, EXIT_FAILURE);
110
111 /* replace v1 */
112 r = hash_add_unique(h, k1, v4);
113 assert_return(r != 0, EXIT_FAILURE);
114 assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
115
116 v = hash_find(h, "k1");
117 assert_return(streq(v, v1), EXIT_FAILURE);
118
119 assert_return(freecount == 0, EXIT_FAILURE);
120
121 hash_free(h);
122 return 0;
123 }
124 DEFINE_TEST(test_hash_replace_failing,
125 .description = "test hash_add_unique failing to replace existing value");
126
127
test_hash_iter(const struct test * t)128 static int test_hash_iter(const struct test *t)
129 {
130 struct hash *h = hash_new(8, NULL);
131 struct hash *h2 = hash_new(8, NULL);
132 const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
133 const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
134 struct hash_iter iter;
135 const char *k, *v;
136
137 hash_add(h, k1, v1);
138 hash_add(h2, k1, v1);
139 hash_add(h, k2, v2);
140 hash_add(h2, k2, v2);
141 hash_add(h, k3, v3);
142 hash_add(h2, k3, v3);
143
144 for (hash_iter_init(h, &iter);
145 hash_iter_next(&iter, &k, (const void **) &v);) {
146 v2 = hash_find(h2, k);
147 assert_return(v2 != NULL, EXIT_FAILURE);
148 hash_del(h2, k);
149 }
150
151 assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
152 assert_return(hash_get_count(h2) == 0, EXIT_FAILURE);
153
154 hash_free(h);
155 hash_free(h2);
156 return 0;
157 }
158 DEFINE_TEST(test_hash_iter,
159 .description = "test hash_iter");
160
161
test_hash_iter_after_del(const struct test * t)162 static int test_hash_iter_after_del(const struct test *t)
163 {
164 struct hash *h = hash_new(8, NULL);
165 struct hash *h2 = hash_new(8, NULL);
166 const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
167 const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
168 struct hash_iter iter;
169 const char *k, *v;
170
171 hash_add(h, k1, v1);
172 hash_add(h2, k1, v1);
173 hash_add(h, k2, v2);
174 hash_add(h2, k2, v2);
175 hash_add(h, k3, v3);
176 hash_add(h2, k3, v3);
177
178 hash_del(h, k1);
179
180 for (hash_iter_init(h, &iter);
181 hash_iter_next(&iter, &k, (const void **) &v);) {
182 v2 = hash_find(h2, k);
183 assert_return(v2 != NULL, EXIT_FAILURE);
184 hash_del(h2, k);
185 }
186
187 assert_return(hash_get_count(h) == 2, EXIT_FAILURE);
188 assert_return(hash_get_count(h2) == 1, EXIT_FAILURE);
189
190 hash_free(h);
191 hash_free(h2);
192 return 0;
193 }
194 DEFINE_TEST(test_hash_iter_after_del,
195 .description = "test hash_iter, after deleting element");
196
197
test_hash_free(const struct test * t)198 static int test_hash_free(const struct test *t)
199 {
200 struct hash *h = hash_new(8, countfreecalls);
201 const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
202 const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
203
204 hash_add(h, k1, v1);
205 hash_add(h, k2, v2);
206 hash_add(h, k3, v3);
207
208 hash_del(h, k1);
209
210 assert_return(freecount == 1, EXIT_FAILURE);
211
212 assert_return(hash_get_count(h) == 2, EXIT_FAILURE);
213
214 hash_free(h);
215
216 assert_return(freecount == 3, EXIT_FAILURE);
217
218 return 0;
219 }
220 DEFINE_TEST(test_hash_free,
221 .description = "test hash_free calling free function for all values");
222
223
test_hash_add_unique(const struct test * t)224 static int test_hash_add_unique(const struct test *t)
225 {
226 const char *k[] = { "k1", "k2", "k3", "k4", "k5" };
227 const char *v[] = { "v1", "v2", "v3", "v4", "v5" };
228 unsigned int i, j, N;
229
230 N = ARRAY_SIZE(k);
231 for (i = 0; i < N; i++) {
232 /* With N - 1 buckets, there'll be a bucket with more than one key. */
233 struct hash *h = hash_new(N - 1, NULL);
234
235 /* Add the keys in different orders. */
236 for (j = 0; j < N; j++) {
237 unsigned int idx = (j + i) % N;
238 hash_add_unique(h, k[idx], v[idx]);
239 }
240
241 assert_return(hash_get_count(h) == N, EXIT_FAILURE);
242 hash_free(h);
243 }
244 return 0;
245 }
246 DEFINE_TEST(test_hash_add_unique,
247 .description = "test hash_add_unique with different key orders")
248
249
test_hash_massive_add_del(const struct test * t)250 static int test_hash_massive_add_del(const struct test *t)
251 {
252 char buf[1024 * 8];
253 char *k;
254 struct hash *h;
255 unsigned int i, N = 1024;
256
257 h = hash_new(8, NULL);
258
259 k = &buf[0];
260 for (i = 0; i < N; i++) {
261 snprintf(k, 8, "k%d", i);
262 hash_add(h, k, k);
263 k += 8;
264 }
265
266 assert_return(hash_get_count(h) == N, EXIT_FAILURE);
267
268 k = &buf[0];
269 for (i = 0; i < N; i++) {
270 hash_del(h, k);
271 k += 8;
272 }
273
274 assert_return(hash_get_count(h) == 0, EXIT_FAILURE);
275
276 hash_free(h);
277 return 0;
278 }
279 DEFINE_TEST(test_hash_massive_add_del,
280 .description = "test multiple adds followed by multiple dels")
281
282 TESTSUITE_MAIN();
283