lib/libc/stdlib/hcreate.c

   1 /* $NetBSD: hcreate.c,v 1.7 2011/09/14 23:33:51 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 0
  46 #if defined(LIBC_SCCS) && !defined(lint)
  47 __RCSID("$NetBSD: hcreate.c,v 1.8 2011/09/17 16:54:39 christos Exp $");
  48 #endif /* LIBC_SCCS and not lint */
  49 #endif
  50 __FBSDID("$FreeBSD$");
  51
  52 #include <sys/types.h>
  53 #include <sys/queue.h>
  54 #include <errno.h>
  55 #include <search.h>
  56 #include <stdlib.h>
  57 #include <string.h>
  58
  59 /*
  60  * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit
  61  * ptr machine) without adjusting MAX_BUCKETS_LG2 below.
  62  */
  63 struct internal_entry {
  64         SLIST_ENTRY(internal_entry) link;
  65         ENTRY ent;
  66 };
  67 SLIST_HEAD(internal_head, internal_entry);
  68
  69 #define MIN_BUCKETS_LG2 4
  70 #define MIN_BUCKETS     (1 << MIN_BUCKETS_LG2)
  71
  72 /*
  73  * max * sizeof internal_entry must fit into size_t.
  74  * assumes internal_entry is <= 32 (2^5) bytes.
  75  */
  76 #define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5)
  77 #define MAX_BUCKETS     ((size_t)1 << MAX_BUCKETS_LG2)
  78
  79 /* Default hash function, from db/hash/hash_func.c */
  80 extern u_int32_t (*__default_hash)(const void *, size_t);
  81
  82 static struct hsearch_data htable;
  83
  84 int
  85 hcreate(size_t nel)
  86 {
  87
  88         /* Make sure this is not called when a table already exists. */
  89         if (htable.table != NULL) {
  90                 errno = EINVAL;
  91                 return 0;
  92         }
  93         return hcreate_r(nel, &htable);
  94 }
  95
  96 int
  97 hcreate_r(size_t nel, struct hsearch_data *head)
  98 {
  99         struct internal_head *table;
 100         size_t idx;
 101         unsigned int p2;
 102         void *p;
 103
 104         /* If nel is too small, make it min sized. */
 105         if (nel < MIN_BUCKETS)
 106                 nel = MIN_BUCKETS;
 107
 108         /* If it is too large, cap it. */
 109         if (nel > MAX_BUCKETS)
 110                 nel = MAX_BUCKETS;
 111
 112         /* If it is not a power of two in size, round up. */
 113         if ((nel & (nel - 1)) != 0) {
 114                 for (p2 = 0; nel != 0; p2++)
 115                         nel >>= 1;
 116                 nel = 1 << p2;
 117         }
 118
 119         /* Allocate the table. */
 120         head->size = nel;
 121         head->filled = 0;
 122         p = malloc(nel * sizeof table[0]);
 123         if (p == NULL) {
 124                 errno = ENOMEM;
 125                 return 0;
 126         }
 127         head->table = p;
 128         table = p;
 129
 130         /* Initialize it. */
 131         for (idx = 0; idx < nel; idx++)
 132                 SLIST_INIT(&table[idx]);
 133
 134         return 1;
 135 }
 136
 137 void
 138 hdestroy(void)
 139 {
 140         hdestroy_r(&htable);
 141 }
 142
 143 void
 144 hdestroy_r(struct hsearch_data *head)
 145 {
 146         struct internal_entry *ie;
 147         size_t idx;
 148         void *p;
 149         struct internal_head *table;
 150
 151         if (head == NULL)
 152                 return;
 153
 154         p = head->table;
 155         head->table = NULL;
 156         table = p;
 157
 158         for (idx = 0; idx < head->size; idx++) {
 159                 while (!SLIST_EMPTY(&table[idx])) {
 160                         ie = SLIST_FIRST(&table[idx]);
 161                         SLIST_REMOVE_HEAD(&table[idx], link);
 162                         free(ie);
 163                 }
 164         }
 165         free(table);
 166 }
 167
 168 ENTRY *
 169 hsearch(ENTRY item, ACTION action)
 170 {
 171         ENTRY *ep;
 172         (void)hsearch_r(item, action, &ep, &htable);
 173         return ep;
 174 }
 175
 176 int
 177 hsearch_r(ENTRY item, ACTION action, ENTRY **itemp, struct hsearch_data *head)
 178 {
 179         struct internal_head *table, *chain;
 180         struct internal_entry *ie;
 181         uint32_t hashval;
 182         size_t len;
 183         void *p;
 184
 185         p = head->table;
 186         table = p;
 187
 188         len = strlen(item.key);
 189         hashval = (*__default_hash)(item.key, len);
 190
 191         chain = &table[hashval & (head->size - 1)];
 192         ie = SLIST_FIRST(chain);
 193         while (ie != NULL) {
 194                 if (strcmp(ie->ent.key, item.key) == 0)
 195                         break;
 196                 ie = SLIST_NEXT(ie, link);
 197         }
 198
 199         if (ie != NULL) {
 200                 *itemp = &ie->ent;
 201                 return 1;
 202         } else if (action == FIND) {
 203                 *itemp = NULL;
 204                 errno = ESRCH;
 205                 return 1;
 206         }
 207
 208         ie = malloc(sizeof *ie);
 209         if (ie == NULL)
 210                 return 0;
 211         ie->ent.key = item.key;
 212         ie->ent.data = item.data;
 213
 214         SLIST_INSERT_HEAD(chain, ie, link);
 215         *itemp = &ie->ent;
 216         head->filled++;
 217         return 1;
 218 }