lib/libc/stdlib/hcreate.c

   1 /* $NetBSD: hcreate.c,v 1.6 2008/07/21 12:05:43 lukem Exp $ */
   2
   3 /*
   4  * Copyright (c) 2001 Christopher G. Demetriou
   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  * 3. All advertising materials mentioning features or use of this software
  16  *    must display the following acknowledgement:
  17  *          This product includes software developed for the
  18  *          NetBSD Project.  See http://www.NetBSD.org/ for
  19  *          information about NetBSD.
  20  * 4. The name of the author may not be used to endorse or promote products
  21  *    derived from this software without specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  24  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  25  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  26  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  28  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  29  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  30  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  31  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  32  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>>
  35  */
  36
  37 /*
  38  * hcreate() / hsearch() / hdestroy()
  39  *
  40  * SysV/XPG4 hash table functions.
  41  *
  42  * Implementation done based on NetBSD manual page and Solaris manual page,
  43  * plus my own personal experience about how they're supposed to work.
  44  *
  45  * I tried to look at Knuth (as cited by the Solaris manual page), but
  46  * nobody had a copy in the office, so...
  47  */
  48
  49 #include <sys/cdefs.h>
  50 #if defined(LIBC_SCCS) && !defined(lint)
  51 __RCSID("$NetBSD: hcreate.c,v 1.6 2008/07/21 12:05:43 lukem Exp $");
  52 #endif /* LIBC_SCCS and not lint */
  53
  54 #if !defined(lint)
  55 __COPYRIGHT("@(#) Copyright (c) 2001\
  56  Christopher G. Demetriou.  All rights reserved.");
  57 #endif /* not lint */
  58
  59 #include "namespace.h"
  60 #include <assert.h>
  61 #include <errno.h>
  62 #include <inttypes.h>
  63 #include <search.h>
  64 #include <stdlib.h>
  65 #include <string.h>
  66 #include <sys/queue.h>
  67
  68 /*
  69  * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit
  70  * ptr machine) without adjusting MAX_BUCKETS_LG2 below.
  71  */
  72 struct internal_entry {
  73         SLIST_ENTRY(internal_entry) link;
  74         ENTRY ent;
  75 };
  76 SLIST_HEAD(internal_head, internal_entry);
  77
  78 #define MIN_BUCKETS_LG2 4
  79 #define MIN_BUCKETS     (1 << MIN_BUCKETS_LG2)
  80
  81 /*
  82  * max * sizeof internal_entry must fit into size_t.
  83  * assumes internal_entry is <= 32 (2^5) bytes.
  84  */
  85 #define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5)
  86 #define MAX_BUCKETS     ((size_t)1 << MAX_BUCKETS_LG2)
  87
  88 /* Default hash function, from db/hash/hash_func.c */
  89 extern u_int32_t (*__default_hash)(const void *, size_t);
  90
  91 static struct internal_head *htable;
  92 static size_t htablesize;
  93
  94 int
  95 hcreate(size_t nel)
  96 {
  97         size_t idx;
  98         unsigned int p2;
  99
 100         /* Make sure this isn't called when a table already exists. */
 101         _DIAGASSERT(htable == NULL);
 102         if (htable != NULL) {
 103                 errno = EINVAL;
 104                 return 0;
 105         }
 106
 107         /* If nel is too small, make it min sized. */
 108         if (nel < MIN_BUCKETS)
 109                 nel = MIN_BUCKETS;
 110
 111         /* If it's too large, cap it. */
 112         if (nel > MAX_BUCKETS)
 113                 nel = MAX_BUCKETS;
 114
 115         /* If it's is not a power of two in size, round up. */
 116         if ((nel & (nel - 1)) != 0) {
 117                 for (p2 = 0; nel != 0; p2++)
 118                         nel >>= 1;
 119                 _DIAGASSERT(p2 <= MAX_BUCKETS_LG2);
 120                 nel = 1 << p2;
 121         }
 122
 123         /* Allocate the table. */
 124         htablesize = nel;
 125         htable = malloc(htablesize * sizeof htable[0]);
 126         if (htable == NULL) {
 127                 errno = ENOMEM;
 128                 return 0;
 129         }
 130
 131         /* Initialize it. */
 132         for (idx = 0; idx < htablesize; idx++)
 133                 SLIST_INIT(&htable[idx]);
 134
 135         return 1;
 136 }
 137
 138 void
 139 hdestroy(void)
 140 {
 141         struct internal_entry *ie;
 142         size_t idx;
 143
 144         _DIAGASSERT(htable != NULL);
 145         if (htable == NULL)
 146                 return;
 147
 148         for (idx = 0; idx < htablesize; idx++) {
 149                 while (!SLIST_EMPTY(&htable[idx])) {
 150                         ie = SLIST_FIRST(&htable[idx]);
 151                         SLIST_REMOVE_HEAD(&htable[idx], link);
 152                         free(ie->ent.key);
 153                         free(ie);
 154                 }
 155         }
 156         free(htable);
 157         htable = NULL;
 158 }
 159
 160 ENTRY *
 161 hsearch(ENTRY item, ACTION action)
 162 {
 163         struct internal_head *head;
 164         struct internal_entry *ie;
 165         uint32_t hashval;
 166         size_t len;
 167
 168         _DIAGASSERT(htable != NULL);
 169         _DIAGASSERT(item.key != NULL);
 170         _DIAGASSERT(action == ENTER || action == FIND);
 171
 172         len = strlen(item.key);
 173         hashval = (*__default_hash)(item.key, len);
 174
 175         head = &htable[hashval & (htablesize - 1)];
 176         ie = SLIST_FIRST(head);
 177         while (ie != NULL) {
 178                 if (strcmp(ie->ent.key, item.key) == 0)
 179                         break;
 180                 ie = SLIST_NEXT(ie, link);
 181         }
 182
 183         if (ie != NULL)
 184                 return &ie->ent;
 185         else if (action == FIND)
 186                 return NULL;
 187
 188         ie = malloc(sizeof *ie);
 189         if (ie == NULL)
 190                 return NULL;
 191         ie->ent.key = item.key;
 192         ie->ent.data = item.data;
 193
 194         SLIST_INSERT_HEAD(head, ie, link);
 195         return &ie->ent;
 196 }