tests/lib/libc/stdlib/t_hsearch.c

   1 /* $NetBSD: t_hsearch.c,v 1.3 2011/09/15 14:51:06 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.3 2011/09/15 14:51:06 christos Exp $");
  67
  68 #include <errno.h>
  69 #include <search.h>
  70 #include <string.h>
  71 #include <stdio.h>
  72
  73 #include <atf-c.h>
  74
  75 #define REQUIRE_ERRNO(x) ATF_REQUIRE_MSG(x, "%s", strerror(errno))
  76
  77 ATF_TC(hsearch_basic);
  78 ATF_TC_HEAD(hsearch_basic, tc)
  79 {
  80
  81         atf_tc_set_md_var(tc, "descr", "Checks basic insertions and searching");
  82 }
  83
  84 ATF_TC_BODY(hsearch_basic, tc)
  85 {
  86         ENTRY e, *ep;
  87         char ch[2];
  88         int i;
  89
  90         REQUIRE_ERRNO(hcreate(16) != 0);
  91
  92         /* ch[1] should be constant from here on down. */
  93         ch[1] = '\0';
  94
  95         /* Basic insertions.  Check enough that there'll be collisions. */
  96         for (i = 0; i < 26; i++) {
  97                 ch[0] = 'a' + i;
  98                 e.key = strdup(ch);     /* ptr to provided key is kept! */
  99                 ATF_REQUIRE(e.key != NULL);
 100                 e.data = (void *)(long)i;
 101
 102                 ep = hsearch(e, ENTER);
 103
 104                 ATF_REQUIRE(ep != NULL);
 105                 ATF_REQUIRE_STREQ(ep->key, ch);
 106                 ATF_REQUIRE_EQ((long)ep->data, i);
 107         }
 108
 109         /* e.key should be constant from here on down. */
 110         e.key = ch;
 111
 112         /* Basic lookups. */
 113         for (i = 0; i < 26; i++) {
 114                 ch[0] = 'a' + i;
 115
 116                 ep = hsearch(e, FIND);
 117
 118                 ATF_REQUIRE(ep != NULL);
 119                 ATF_REQUIRE_STREQ(ep->key, ch);
 120                 ATF_REQUIRE_EQ((long)ep->data, i);
 121         }
 122
 123         hdestroy();
 124 }
 125
 126 ATF_TC(hsearch_duplicate);
 127 ATF_TC_HEAD(hsearch_duplicate, tc)
 128 {
 129
 130         atf_tc_set_md_var(tc, "descr", "Checks that inserting duplicate "
 131             "doesn't overwrite existing data");
 132 }
 133
 134 ATF_TC_BODY(hsearch_duplicate, tc)
 135 {
 136         ENTRY e, *ep;
 137
 138         REQUIRE_ERRNO(hcreate(16));
 139
 140         e.key = strdup("a");
 141         ATF_REQUIRE(e.key != NULL);
 142         e.data = (void *)(long) 0;
 143
 144         ep = hsearch(e, ENTER);
 145
 146         ATF_REQUIRE(ep != NULL);
 147         ATF_REQUIRE_STREQ(ep->key, "a");
 148         ATF_REQUIRE_EQ((long)ep->data, 0);
 149
 150         e.data = (void *)(long)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((long)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 = strdup("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         char *sa, *sb;
 195
 196         ATF_REQUIRE((sa = strdup("a")) != NULL);
 197         ATF_REQUIRE((sb = strdup("b")) != NULL);
 198
 199         REQUIRE_ERRNO(hcreate(16));
 200
 201         e.key = sa;
 202         e.data = (void*)(long)0;
 203
 204         ep = hsearch(e, ENTER);
 205
 206         ATF_REQUIRE(ep != NULL);
 207         ATF_REQUIRE_STREQ(ep->key, "a");
 208         ATF_REQUIRE_EQ((long)ep->data, 0);
 209
 210         e.key = sb;
 211         e.data = (void*)(long)1;
 212
 213         ep = hsearch(e, ENTER);
 214
 215         ATF_REQUIRE(ep != NULL);
 216         ATF_REQUIRE_STREQ(ep->key, "b");
 217         ATF_REQUIRE_EQ((long)ep->data, 1);
 218
 219         e.key = sa;
 220         ep = hsearch(e, FIND);
 221
 222         e.key = sb;
 223         ep2 = hsearch(e, FIND);
 224
 225         ATF_REQUIRE(ep != NULL);
 226         ATF_REQUIRE_STREQ(ep->key, "a");
 227         ATF_REQUIRE_EQ((long)ep->data, 0);
 228
 229         ATF_REQUIRE(ep2 != NULL);
 230         ATF_REQUIRE_STREQ(ep2->key, "b");
 231         ATF_REQUIRE_EQ((long)ep2->data, 1);
 232
 233         hdestroy();
 234 }
 235
 236 ATF_TC(hsearch_r_basic);
 237 ATF_TC_HEAD(hsearch_r_basic, tc)
 238 {
 239
 240         atf_tc_set_md_var(tc, "descr", "Checks basic insertions and searching");
 241 }
 242
 243 ATF_TC_BODY(hsearch_r_basic, tc)
 244 {
 245         ENTRY e, *ep;
 246         char ch[2];
 247         int i;
 248         struct hsearch_data t;
 249
 250         REQUIRE_ERRNO(hcreate_r(16, &t) != 0);
 251
 252         /* ch[1] should be constant from here on down. */
 253         ch[1] = '\0';
 254
 255         /* Basic insertions.  Check enough that there'll be collisions. */
 256         for (i = 0; i < 26; i++) {
 257                 ch[0] = 'a' + i;
 258                 e.key = strdup(ch);     /* ptr to provided key is kept! */
 259                 ATF_REQUIRE(e.key != NULL);
 260                 e.data = (void *)(long)i;
 261
 262                 ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 263                 ATF_REQUIRE(ep != NULL);
 264                 ATF_REQUIRE_STREQ(ep->key, ch);
 265                 ATF_REQUIRE_EQ((long)ep->data, i);
 266         }
 267
 268         /* e.key should be constant from here on down. */
 269         e.key = ch;
 270
 271         /* Basic lookups. */
 272         for (i = 0; i < 26; i++) {
 273                 ch[0] = 'a' + i;
 274
 275                 ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 276                 ATF_REQUIRE(ep != NULL);
 277                 ATF_REQUIRE_STREQ(ep->key, ch);
 278                 ATF_REQUIRE_EQ((long)ep->data, i);
 279         }
 280
 281         hdestroy_r(&t);
 282 }
 283
 284 ATF_TC(hsearch_r_duplicate);
 285 ATF_TC_HEAD(hsearch_r_duplicate, tc)
 286 {
 287
 288         atf_tc_set_md_var(tc, "descr", "Checks that inserting duplicate "
 289             "doesn't overwrite existing data");
 290 }
 291
 292 ATF_TC_BODY(hsearch_r_duplicate, tc)
 293 {
 294         ENTRY e, *ep;
 295         struct hsearch_data t;
 296
 297         REQUIRE_ERRNO(hcreate_r(16, &t));
 298
 299         e.key = strdup("a");
 300         ATF_REQUIRE(e.key != NULL);
 301         e.data = (void *)(long) 0;
 302
 303         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 304         ATF_REQUIRE(ep != NULL);
 305         ATF_REQUIRE_STREQ(ep->key, "a");
 306         ATF_REQUIRE_EQ((long)ep->data, 0);
 307
 308         e.data = (void *)(long)12345;
 309
 310         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 311         ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 312
 313         ATF_REQUIRE(ep != NULL);
 314         ATF_REQUIRE_STREQ(ep->key, "a");
 315         ATF_REQUIRE_EQ((long)ep->data, 0);
 316
 317         hdestroy_r(&t);
 318 }
 319
 320 ATF_TC(hsearch_r_nonexistent);
 321 ATF_TC_HEAD(hsearch_r_nonexistent, tc)
 322 {
 323
 324         atf_tc_set_md_var(tc, "descr",
 325             "Checks searching for non-existent entry");
 326 }
 327
 328 ATF_TC_BODY(hsearch_r_nonexistent, tc)
 329 {
 330         ENTRY e, *ep;
 331         struct hsearch_data t;
 332
 333         REQUIRE_ERRNO(hcreate_r(16, &t));
 334
 335         e.key = strdup("A");
 336         ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 337         ATF_REQUIRE_EQ(ep, NULL);
 338
 339         hdestroy_r(&t);
 340 }
 341
 342 ATF_TC(hsearch_r_two);
 343 ATF_TC_HEAD(hsearch_r_two, tc)
 344 {
 345
 346         atf_tc_set_md_var(tc, "descr",
 347             "Checks that searching doesn't overwrite previous search results");
 348 }
 349
 350 ATF_TC_BODY(hsearch_r_two, tc)
 351 {
 352         ENTRY e, *ep, *ep2;
 353         char *sa, *sb;
 354         struct hsearch_data t;
 355
 356         ATF_REQUIRE((sa = strdup("a")) != NULL);
 357         ATF_REQUIRE((sb = strdup("b")) != NULL);
 358
 359         REQUIRE_ERRNO(hcreate_r(16, &t));
 360
 361         e.key = sa;
 362         e.data = (void*)(long)0;
 363
 364         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 365         ATF_REQUIRE(ep != NULL);
 366         ATF_REQUIRE_STREQ(ep->key, "a");
 367         ATF_REQUIRE_EQ((long)ep->data, 0);
 368
 369         e.key = sb;
 370         e.data = (void*)(long)1;
 371
 372         ATF_REQUIRE(hsearch_r(e, ENTER, &ep, &t) == 1);
 373         ATF_REQUIRE(ep != NULL);
 374         ATF_REQUIRE_STREQ(ep->key, "b");
 375         ATF_REQUIRE_EQ((long)ep->data, 1);
 376
 377         e.key = sa;
 378         ATF_REQUIRE(hsearch_r(e, FIND, &ep, &t) == 1);
 379
 380         e.key = sb;
 381         ATF_REQUIRE(hsearch_r(e, FIND, &ep2, &t) == 1);
 382
 383         ATF_REQUIRE(ep != NULL);
 384         ATF_REQUIRE_STREQ(ep->key, "a");
 385         ATF_REQUIRE_EQ((long)ep->data, 0);
 386
 387         ATF_REQUIRE(ep2 != NULL);
 388         ATF_REQUIRE_STREQ(ep2->key, "b");
 389         ATF_REQUIRE_EQ((long)ep2->data, 1);
 390
 391         hdestroy_r(&t);
 392 }
 393
 394 ATF_TP_ADD_TCS(tp)
 395 {
 396
 397         ATF_TP_ADD_TC(tp, hsearch_basic);
 398         ATF_TP_ADD_TC(tp, hsearch_duplicate);
 399         ATF_TP_ADD_TC(tp, hsearch_nonexistent);
 400         ATF_TP_ADD_TC(tp, hsearch_two);
 401
 402         ATF_TP_ADD_TC(tp, hsearch_r_basic);
 403         ATF_TP_ADD_TC(tp, hsearch_r_duplicate);
 404         ATF_TP_ADD_TC(tp, hsearch_r_nonexistent);
 405         ATF_TP_ADD_TC(tp, hsearch_r_two);
 406
 407         return atf_no_error();
 408 }