lib/libc/stdlib/hcreate.c

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