1 /* $NetBSD: t_hsearch.c,v 1.4 2014/07/20 20:17:21 christos Exp $ */
2
3 /*-
4 * Copyright (c) 2008 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29 /*
30 * Copyright (c) 2001 Christopher G. Demetriou
31 * All rights reserved.
32 *
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
35 * are met:
36 * 1. Redistributions of source code must retain the above copyright
37 * notice, this list of conditions and the following disclaimer.
38 * 2. Redistributions in binary form must reproduce the above copyright
39 * notice, this list of conditions and the following disclaimer in the
40 * documentation and/or other materials provided with the distribution.
41 * 3. All advertising materials mentioning features or use of this software
42 * must display the following acknowledgement:
43 * This product includes software developed for the
44 * NetBSD Project. See http://www.NetBSD.org/ for
45 * information about NetBSD.
46 * 4. The name of the author may not be used to endorse or promote products
47 * derived from this software without specific prior written permission.
48 *
49 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
50 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
51 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
52 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
53 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
54 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
55 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
56 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
57 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
58 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
59 *
60 * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>>
61 */
62
63 #include <sys/cdefs.h>
64 __COPYRIGHT("@(#) Copyright (c) 2008\
65 The NetBSD Foundation, inc. All rights reserved.");
66 __RCSID("$NetBSD: t_hsearch.c,v 1.4 2014/07/20 20:17:21 christos Exp $");
67
68 #include <errno.h>
69 #include <search.h>
70 #include <string.h>
71 #include <stdio.h>
72 #include <stdlib.h>
73
74 #include <atf-c.h>
75
76 #define REQUIRE_ERRNO(x) ATF_REQUIRE_MSG(x, "%s", strerror(errno))
77
78 ATF_TC(hsearch_basic);
ATF_TC_HEAD(hsearch_basic,tc)79 ATF_TC_HEAD(hsearch_basic, tc)
80 {
81
82 atf_tc_set_md_var(tc, "descr", "Checks basic insertions and searching");
83 }
84
ATF_TC_BODY(hsearch_basic,tc)85 ATF_TC_BODY(hsearch_basic, tc)
86 {
87 ENTRY e, *ep;
88 char ch[2];
89 int i;
90
91 REQUIRE_ERRNO(hcreate(16) != 0);
92
93 /* ch[1] should be constant from here on down. */
94 ch[1] = '\0';
95
96 /* Basic insertions. Check enough that there'll be collisions. */
97 for (i = 0; i < 26; i++) {
98 ch[0] = 'a' + i;
99 e.key = strdup(ch); /* ptr to provided key is kept! */
100 ATF_REQUIRE(e.key != NULL);
101 e.data = (void *)(intptr_t)i;
102
103 ep = hsearch(e, ENTER);
104
105 ATF_REQUIRE(ep != NULL);
106 ATF_REQUIRE_STREQ(ep->key, ch);
107 ATF_REQUIRE_EQ((intptr_t)ep->data, i);
108 }
109
110 /* e.key should be constant from here on down. */
111 e.key = ch;
112
113 /* Basic lookups. */
114 for (i = 0; i < 26; i++) {
115 ch[0] = 'a' + i;
116
117 ep = hsearch(e, FIND);
118
119 ATF_REQUIRE(ep != NULL);
120 ATF_REQUIRE_STREQ(ep->key, ch);
121 ATF_REQUIRE_EQ((intptr_t)ep->data, i);
122 }
123
124 #ifdef __NetBSD__
125 hdestroy1(free, NULL);
126 #else
127 hdestroy();
128 #endif
129 }
130
131 ATF_TC(hsearch_duplicate);
ATF_TC_HEAD(hsearch_duplicate,tc)132 ATF_TC_HEAD(hsearch_duplicate, tc)
133 {
134
135 atf_tc_set_md_var(tc, "descr", "Checks that inserting duplicate "
136 "doesn't overwrite existing data");
137 }
138
ATF_TC_BODY(hsearch_duplicate,tc)139 ATF_TC_BODY(hsearch_duplicate, tc)
140 {
141 ENTRY e, *ep;
142
143 REQUIRE_ERRNO(hcreate(16));
144
145 e.key = __UNCONST("a");
146 e.data = (void *)(intptr_t) 0;
147
148 ep = hsearch(e, ENTER);
149
150 ATF_REQUIRE(ep != NULL);
151 ATF_REQUIRE_STREQ(ep->key, "a");
152 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
153
154 e.data = (void *)(intptr_t)12345;
155
156 ep = hsearch(e, ENTER);
157 ep = hsearch(e, FIND);
158
159 ATF_REQUIRE(ep != NULL);
160 ATF_REQUIRE_STREQ(ep->key, "a");
161 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
162
163 hdestroy();
164 }
165
166 ATF_TC(hsearch_nonexistent);
ATF_TC_HEAD(hsearch_nonexistent,tc)167 ATF_TC_HEAD(hsearch_nonexistent, tc)
168 {
169
170 atf_tc_set_md_var(tc, "descr",
171 "Checks searching for non-existent entry");
172 }
173
ATF_TC_BODY(hsearch_nonexistent,tc)174 ATF_TC_BODY(hsearch_nonexistent, tc)
175 {
176 ENTRY e, *ep;
177
178 REQUIRE_ERRNO(hcreate(16));
179
180 e.key = __UNCONST("A");
181 ep = hsearch(e, FIND);
182 ATF_REQUIRE_EQ(ep, NULL);
183
184 hdestroy();
185 }
186
187 ATF_TC(hsearch_two);
ATF_TC_HEAD(hsearch_two,tc)188 ATF_TC_HEAD(hsearch_two, tc)
189 {
190
191 atf_tc_set_md_var(tc, "descr",
192 "Checks that searching doesn't overwrite previous search results");
193 }
194
ATF_TC_BODY(hsearch_two,tc)195 ATF_TC_BODY(hsearch_two, tc)
196 {
197 ENTRY e, *ep, *ep2;
198
199 REQUIRE_ERRNO(hcreate(16));
200
201 e.key = __UNCONST("a");
202 e.data = (void*)(intptr_t)0;
203
204 ep = hsearch(e, ENTER);
205
206 ATF_REQUIRE(ep != NULL);
207 ATF_REQUIRE_STREQ(ep->key, "a");
208 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
209
210 e.key = __UNCONST("b");
211 e.data = (void*)(intptr_t)1;
212
213 ep = hsearch(e, ENTER);
214
215 ATF_REQUIRE(ep != NULL);
216 ATF_REQUIRE_STREQ(ep->key, "b");
217 ATF_REQUIRE_EQ((intptr_t)ep->data, 1);
218
219 e.key = __UNCONST("a");
220 ep = hsearch(e, FIND);
221
222 e.key = __UNCONST("b");
223 ep2 = hsearch(e, FIND);
224
225 ATF_REQUIRE(ep != NULL);
226 ATF_REQUIRE_STREQ(ep->key, "a");
227 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
228
229 ATF_REQUIRE(ep2 != NULL);
230 ATF_REQUIRE_STREQ(ep2->key, "b");
231 ATF_REQUIRE_EQ((intptr_t)ep2->data, 1);
232
233 hdestroy();
234 }
235
236 #if defined(__FreeBSD__) && 1100027 <= __FreeBSD_version
237 ATF_TC(hsearch_r_basic);
ATF_TC_HEAD(hsearch_r_basic,tc)238 ATF_TC_HEAD(hsearch_r_basic, tc)
239 {
240
241 atf_tc_set_md_var(tc, "descr", "Checks basic insertions and searching");
242 }
243
ATF_TC_BODY(hsearch_r_basic,tc)244 ATF_TC_BODY(hsearch_r_basic, tc)
245 {
246 ENTRY e, *ep;
247 char ch[2];
248 int i;
249 struct hsearch_data t;
250
251 REQUIRE_ERRNO(hcreate_r(16, &t) != 0);
252
253 /* ch[1] should be constant from here on down. */
254 ch[1] = '\0';
255
256 /* Basic insertions. Check enough that there'll be collisions. */
257 for (i = 0; i < 26; i++) {
258 ch[0] = 'a' + i;
259 e.key = strdup(ch); /* ptr to provided key is kept! */
260 ATF_REQUIRE(e.key != NULL);
261 e.data = (void *)(intptr_t)i;
262
263 ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
264 ATF_REQUIRE(ep != NULL);
265 ATF_REQUIRE_STREQ(ep->key, ch);
266 ATF_REQUIRE_EQ((intptr_t)ep->data, i);
267 }
268
269 /* e.key should be constant from here on down. */
270 e.key = ch;
271
272 /* Basic lookups. */
273 for (i = 0; i < 26; i++) {
274 ch[0] = 'a' + i;
275
276 ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
277 ATF_REQUIRE(ep != NULL);
278 ATF_REQUIRE_STREQ(ep->key, ch);
279 ATF_REQUIRE_EQ((intptr_t)ep->data, i);
280 }
281
282 #ifdef __NetBSD__
283 hdestroy1_r(&t, free, NULL);
284 #else
285 hdestroy_r(&t);
286 #endif
287 }
288 #endif
289
290 #if defined(__FreeBSD__) && 1100027 <= __FreeBSD_version
291 ATF_TC(hsearch_r_duplicate);
ATF_TC_HEAD(hsearch_r_duplicate,tc)292 ATF_TC_HEAD(hsearch_r_duplicate, tc)
293 {
294
295 atf_tc_set_md_var(tc, "descr", "Checks that inserting duplicate "
296 "doesn't overwrite existing data");
297 }
298
ATF_TC_BODY(hsearch_r_duplicate,tc)299 ATF_TC_BODY(hsearch_r_duplicate, tc)
300 {
301 ENTRY e, *ep;
302 struct hsearch_data t;
303
304 REQUIRE_ERRNO(hcreate_r(16, &t));
305
306 e.key = __UNCONST("a");
307 e.data = (void *)(intptr_t) 0;
308
309 ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
310 ATF_REQUIRE(ep != NULL);
311 ATF_REQUIRE_STREQ(ep->key, "a");
312 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
313
314 e.data = (void *)(intptr_t)12345;
315
316 ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
317 ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
318
319 ATF_REQUIRE(ep != NULL);
320 ATF_REQUIRE_STREQ(ep->key, "a");
321 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
322
323 hdestroy_r(&t);
324 }
325
326 ATF_TC(hsearch_r_nonexistent);
ATF_TC_HEAD(hsearch_r_nonexistent,tc)327 ATF_TC_HEAD(hsearch_r_nonexistent, tc)
328 {
329
330 atf_tc_set_md_var(tc, "descr",
331 "Checks searching for non-existent entry");
332 }
333
ATF_TC_BODY(hsearch_r_nonexistent,tc)334 ATF_TC_BODY(hsearch_r_nonexistent, tc)
335 {
336 ENTRY e, *ep;
337 struct hsearch_data t;
338
339 REQUIRE_ERRNO(hcreate_r(16, &t));
340
341 #ifdef __FreeBSD__
342 atf_tc_expect_fail("behavior doesn't match docs; see bug # 216872");
343 #endif
344 e.key = __UNCONST("A");
345 ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
346 ATF_REQUIRE_EQ(ep, NULL);
347
348 hdestroy_r(&t);
349 }
350
351 ATF_TC(hsearch_r_two);
ATF_TC_HEAD(hsearch_r_two,tc)352 ATF_TC_HEAD(hsearch_r_two, tc)
353 {
354
355 atf_tc_set_md_var(tc, "descr",
356 "Checks that searching doesn't overwrite previous search results");
357 }
358
ATF_TC_BODY(hsearch_r_two,tc)359 ATF_TC_BODY(hsearch_r_two, tc)
360 {
361 ENTRY e, *ep, *ep2;
362 struct hsearch_data t;
363
364 REQUIRE_ERRNO(hcreate_r(16, &t));
365
366 e.key = __UNCONST("a");
367 e.data = (void*)(intptr_t)0;
368
369 ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
370 ATF_REQUIRE(ep != NULL);
371 ATF_REQUIRE_STREQ(ep->key, "a");
372 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
373
374 e.key = __UNCONST("b");
375 e.data = (void*)(intptr_t)1;
376
377 ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
378 ATF_REQUIRE(ep != NULL);
379 ATF_REQUIRE_STREQ(ep->key, "b");
380 ATF_REQUIRE_EQ((intptr_t)ep->data, 1);
381
382 e.key = __UNCONST("a");
383 ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
384
385 e.key = __UNCONST("b");
386 ATF_REQUIRE(hsearch_r(e, FIND, &ep2, &t) == 1);
387
388 ATF_REQUIRE(ep != NULL);
389 ATF_REQUIRE_STREQ(ep->key, "a");
390 ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
391
392 ATF_REQUIRE(ep2 != NULL);
393 ATF_REQUIRE_STREQ(ep2->key, "b");
394 ATF_REQUIRE_EQ((intptr_t)ep2->data, 1);
395
396 hdestroy_r(&t);
397 }
398 #endif
399
ATF_TP_ADD_TCS(tp)400 ATF_TP_ADD_TCS(tp)
401 {
402
403 ATF_TP_ADD_TC(tp, hsearch_basic);
404 ATF_TP_ADD_TC(tp, hsearch_duplicate);
405 ATF_TP_ADD_TC(tp, hsearch_nonexistent);
406 ATF_TP_ADD_TC(tp, hsearch_two);
407
408 #if defined(__FreeBSD__) && 1100027 <= __FreeBSD_version
409 ATF_TP_ADD_TC(tp, hsearch_r_basic);
410 ATF_TP_ADD_TC(tp, hsearch_r_duplicate);
411 ATF_TP_ADD_TC(tp, hsearch_r_nonexistent);
412 ATF_TP_ADD_TC(tp, hsearch_r_two);
413 #endif
414
415 return atf_no_error();
416 }
417