tests/lib/libc/stdlib/t_hsearch.c

   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);
  79 ATF_TC_HEAD(hsearch_basic, tc)
  80 {
  81
  82         atf_tc_set_md_var(tc, "descr", "Checks basic insertions and searching");
  83 }
  84
  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         hdestroy1(free, NULL);
 125 }
 126
 127 ATF_TC(hsearch_duplicate);
 128 ATF_TC_HEAD(hsearch_duplicate, tc)
 129 {
 130
 131         atf_tc_set_md_var(tc, "descr", "Checks that inserting duplicate "
 132             "doesn't overwrite existing data");
 133 }
 134
 135 ATF_TC_BODY(hsearch_duplicate, tc)
 136 {
 137         ENTRY e, *ep;
 138
 139         REQUIRE_ERRNO(hcreate(16));
 140
 141         e.key = __UNCONST("a");
 142         e.data = (void *)(intptr_t) 0;
 143
 144         ep = hsearch(e, ENTER);
 145
 146         ATF_REQUIRE(ep != NULL);
 147         ATF_REQUIRE_STREQ(ep->key, "a");
 148         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 149
 150         e.data = (void *)(intptr_t)12345;
 151
 152         ep = hsearch(e, ENTER);
 153         ep = hsearch(e, FIND);
 154
 155         ATF_REQUIRE(ep != NULL);
 156         ATF_REQUIRE_STREQ(ep->key, "a");
 157         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 158
 159         hdestroy();
 160 }
 161
 162 ATF_TC(hsearch_nonexistent);
 163 ATF_TC_HEAD(hsearch_nonexistent, tc)
 164 {
 165
 166         atf_tc_set_md_var(tc, "descr",
 167             "Checks searching for non-existent entry");
 168 }
 169
 170 ATF_TC_BODY(hsearch_nonexistent, tc)
 171 {
 172         ENTRY e, *ep;
 173
 174         REQUIRE_ERRNO(hcreate(16));
 175
 176         e.key = __UNCONST("A");
 177         ep = hsearch(e, FIND);
 178         ATF_REQUIRE_EQ(ep, NULL);
 179
 180         hdestroy();
 181 }
 182
 183 ATF_TC(hsearch_two);
 184 ATF_TC_HEAD(hsearch_two, tc)
 185 {
 186
 187         atf_tc_set_md_var(tc, "descr",
 188             "Checks that searching doesn't overwrite previous search results");
 189 }
 190
 191 ATF_TC_BODY(hsearch_two, tc)
 192 {
 193         ENTRY e, *ep, *ep2;
 194
 195         REQUIRE_ERRNO(hcreate(16));
 196
 197         e.key = __UNCONST("a");
 198         e.data = (void*)(intptr_t)0;
 199
 200         ep = hsearch(e, ENTER);
 201
 202         ATF_REQUIRE(ep != NULL);
 203         ATF_REQUIRE_STREQ(ep->key, "a");
 204         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 205
 206         e.key = __UNCONST("b");
 207         e.data = (void*)(intptr_t)1;
 208
 209         ep = hsearch(e, ENTER);
 210
 211         ATF_REQUIRE(ep != NULL);
 212         ATF_REQUIRE_STREQ(ep->key, "b");
 213         ATF_REQUIRE_EQ((intptr_t)ep->data, 1);
 214
 215         e.key = __UNCONST("a");
 216         ep = hsearch(e, FIND);
 217
 218         e.key = __UNCONST("b");
 219         ep2 = hsearch(e, FIND);
 220
 221         ATF_REQUIRE(ep != NULL);
 222         ATF_REQUIRE_STREQ(ep->key, "a");
 223         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 224
 225         ATF_REQUIRE(ep2 != NULL);
 226         ATF_REQUIRE_STREQ(ep2->key, "b");
 227         ATF_REQUIRE_EQ((intptr_t)ep2->data, 1);
 228
 229         hdestroy();
 230 }
 231
 232 ATF_TC(hsearch_r_basic);
 233 ATF_TC_HEAD(hsearch_r_basic, tc)
 234 {
 235
 236         atf_tc_set_md_var(tc, "descr", "Checks basic insertions and searching");
 237 }
 238
 239 ATF_TC_BODY(hsearch_r_basic, tc)
 240 {
 241         ENTRY e, *ep;
 242         char ch[2];
 243         int i;
 244         struct hsearch_data t;
 245
 246         REQUIRE_ERRNO(hcreate_r(16, &t) != 0);
 247
 248         /* ch[1] should be constant from here on down. */
 249         ch[1] = '\0';
 250
 251         /* Basic insertions.  Check enough that there'll be collisions. */
 252         for (i = 0; i < 26; i++) {
 253                 ch[0] = 'a' + i;
 254                 e.key = strdup(ch);     /* ptr to provided key is kept! */
 255                 ATF_REQUIRE(e.key != NULL);
 256                 e.data = (void *)(intptr_t)i;
 257
 258                 ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 259                 ATF_REQUIRE(ep != NULL);
 260                 ATF_REQUIRE_STREQ(ep->key, ch);
 261                 ATF_REQUIRE_EQ((intptr_t)ep->data, i);
 262         }
 263
 264         /* e.key should be constant from here on down. */
 265         e.key = ch;
 266
 267         /* Basic lookups. */
 268         for (i = 0; i < 26; i++) {
 269                 ch[0] = 'a' + i;
 270
 271                 ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 272                 ATF_REQUIRE(ep != NULL);
 273                 ATF_REQUIRE_STREQ(ep->key, ch);
 274                 ATF_REQUIRE_EQ((intptr_t)ep->data, i);
 275         }
 276
 277         hdestroy1_r(&t, free, NULL);
 278 }
 279
 280 ATF_TC(hsearch_r_duplicate);
 281 ATF_TC_HEAD(hsearch_r_duplicate, tc)
 282 {
 283
 284         atf_tc_set_md_var(tc, "descr", "Checks that inserting duplicate "
 285             "doesn't overwrite existing data");
 286 }
 287
 288 ATF_TC_BODY(hsearch_r_duplicate, tc)
 289 {
 290         ENTRY e, *ep;
 291         struct hsearch_data t;
 292
 293         REQUIRE_ERRNO(hcreate_r(16, &t));
 294
 295         e.key = __UNCONST("a");
 296         e.data = (void *)(intptr_t) 0;
 297
 298         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 299         ATF_REQUIRE(ep != NULL);
 300         ATF_REQUIRE_STREQ(ep->key, "a");
 301         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 302
 303         e.data = (void *)(intptr_t)12345;
 304
 305         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 306         ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 307
 308         ATF_REQUIRE(ep != NULL);
 309         ATF_REQUIRE_STREQ(ep->key, "a");
 310         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 311
 312         hdestroy_r(&t);
 313 }
 314
 315 ATF_TC(hsearch_r_nonexistent);
 316 ATF_TC_HEAD(hsearch_r_nonexistent, tc)
 317 {
 318
 319         atf_tc_set_md_var(tc, "descr",
 320             "Checks searching for non-existent entry");
 321 }
 322
 323 ATF_TC_BODY(hsearch_r_nonexistent, tc)
 324 {
 325         ENTRY e, *ep;
 326         struct hsearch_data t;
 327
 328         REQUIRE_ERRNO(hcreate_r(16, &t));
 329
 330         e.key = __UNCONST("A");
 331         ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 332         ATF_REQUIRE_EQ(ep, NULL);
 333
 334         hdestroy_r(&t);
 335 }
 336
 337 ATF_TC(hsearch_r_two);
 338 ATF_TC_HEAD(hsearch_r_two, tc)
 339 {
 340
 341         atf_tc_set_md_var(tc, "descr",
 342             "Checks that searching doesn't overwrite previous search results");
 343 }
 344
 345 ATF_TC_BODY(hsearch_r_two, tc)
 346 {
 347         ENTRY e, *ep, *ep2;
 348         struct hsearch_data t;
 349
 350         REQUIRE_ERRNO(hcreate_r(16, &t));
 351
 352         e.key = __UNCONST("a");
 353         e.data = (void*)(intptr_t)0;
 354
 355         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 356         ATF_REQUIRE(ep != NULL);
 357         ATF_REQUIRE_STREQ(ep->key, "a");
 358         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 359
 360         e.key = __UNCONST("b");
 361         e.data = (void*)(intptr_t)1;
 362
 363         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 364         ATF_REQUIRE(ep != NULL);
 365         ATF_REQUIRE_STREQ(ep->key, "b");
 366         ATF_REQUIRE_EQ((intptr_t)ep->data, 1);
 367
 368         e.key = __UNCONST("a");
 369         ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 370
 371         e.key = __UNCONST("b");
 372         ATF_REQUIRE(hsearch_r(e, FIND, &ep2, &t) == 1);
 373
 374         ATF_REQUIRE(ep != NULL);
 375         ATF_REQUIRE_STREQ(ep->key, "a");
 376         ATF_REQUIRE_EQ((intptr_t)ep->data, 0);
 377
 378         ATF_REQUIRE(ep2 != NULL);
 379         ATF_REQUIRE_STREQ(ep2->key, "b");
 380         ATF_REQUIRE_EQ((intptr_t)ep2->data, 1);
 381
 382         hdestroy_r(&t);
 383 }
 384
 385 ATF_TP_ADD_TCS(tp)
 386 {
 387
 388         ATF_TP_ADD_TC(tp, hsearch_basic);
 389         ATF_TP_ADD_TC(tp, hsearch_duplicate);
 390         ATF_TP_ADD_TC(tp, hsearch_nonexistent);
 391         ATF_TP_ADD_TC(tp, hsearch_two);
 392
 393         ATF_TP_ADD_TC(tp, hsearch_r_basic);
 394         ATF_TP_ADD_TC(tp, hsearch_r_duplicate);
 395         ATF_TP_ADD_TC(tp, hsearch_r_nonexistent);
 396         ATF_TP_ADD_TC(tp, hsearch_r_two);
 397
 398         return atf_no_error();
 399 }