Annotation of src/lib/libc/stdlib/hcreate.c, Revision 1.8.18.1
1.8.18.1! tls 1: /* $NetBSD: hcreate.c,v 1.10 2014/07/20 20:17:21 christos Exp $ */
1.1 cgd 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.
1.8 christos 15: * 3. The name of the author may not be used to endorse or promote products
1.1 cgd 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)
1.8.18.1! tls 46: __RCSID("$NetBSD: hcreate.c,v 1.10 2014/07/20 20:17:21 christos Exp $");
1.1 cgd 47: #endif /* LIBC_SCCS and not lint */
48:
49: #if !defined(lint)
1.6 lukem 50: __COPYRIGHT("@(#) Copyright (c) 2001\
51: Christopher G. Demetriou. All rights reserved.");
1.1 cgd 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)
1.2 ross 81: #define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2)
1.1 cgd 82:
83: /* Default hash function, from db/hash/hash_func.c */
84: extern u_int32_t (*__default_hash)(const void *, size_t);
85:
1.7 christos 86: static struct hsearch_data htable;
1.1 cgd 87:
88: int
89: hcreate(size_t nel)
90: {
1.7 christos 91: _DIAGASSERT(htable.table == NULL);
1.1 cgd 92:
1.5 simonb 93: /* Make sure this isn't called when a table already exists. */
1.7 christos 94: if (htable.table != NULL) {
1.1 cgd 95: errno = EINVAL;
96: return 0;
97: }
1.7 christos 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;
1.1 cgd 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. */
1.7 christos 126: head->size = nel;
127: head->filled = 0;
128: p = malloc(nel * sizeof table[0]);
129: if (p == NULL) {
1.1 cgd 130: errno = ENOMEM;
131: return 0;
132: }
1.7 christos 133: head->table = p;
134: table = p;
1.1 cgd 135:
136: /* Initialize it. */
1.7 christos 137: for (idx = 0; idx < nel; idx++)
138: SLIST_INIT(&table[idx]);
1.1 cgd 139:
140: return 1;
141: }
142:
143: void
1.8.18.1! tls 144: hdestroy1(void (*freekey)(void *), void (*freedata)(void *))
1.1 cgd 145: {
1.7 christos 146: _DIAGASSERT(htable.table != NULL);
1.8.18.1! tls 147: hdestroy1_r(&htable, freekey, freedata);
1.7 christos 148: }
149:
150: void
1.8.18.1! tls 151: hdestroy(void)
! 152: {
! 153: hdestroy1(NULL, NULL);
! 154: }
! 155:
! 156: void
! 157: hdestroy1_r(struct hsearch_data *head, void (*freekey)(void *),
! 158: void (*freedata)(void *))
1.7 christos 159: {
1.1 cgd 160: struct internal_entry *ie;
161: size_t idx;
1.7 christos 162: void *p;
163: struct internal_head *table;
1.1 cgd 164:
1.7 christos 165: if (head == NULL)
1.1 cgd 166: return;
167:
1.7 christos 168: p = head->table;
169: head->table = NULL;
170: table = p;
171:
172: for (idx = 0; idx < head->size; idx++) {
173: while (!SLIST_EMPTY(&table[idx])) {
174: ie = SLIST_FIRST(&table[idx]);
175: SLIST_REMOVE_HEAD(&table[idx], link);
1.8.18.1! tls 176: if (freekey)
! 177: (*freekey)(ie->ent.key);
! 178: if (freedata)
! 179: (*freedata)(ie->ent.data);
1.1 cgd 180: free(ie);
181: }
182: }
1.7 christos 183: free(table);
1.1 cgd 184: }
185:
1.8.18.1! tls 186: void
! 187: hdestroy_r(struct hsearch_data *head)
! 188: {
! 189: hdestroy1_r(head, NULL, NULL);
! 190: }
! 191:
1.1 cgd 192: ENTRY *
193: hsearch(ENTRY item, ACTION action)
194: {
1.7 christos 195: ENTRY *ep;
196: _DIAGASSERT(htable.table != NULL);
197: (void)hsearch_r(item, action, &ep, &htable);
198: return ep;
199: }
200:
201: int
202: hsearch_r(ENTRY item, ACTION action, ENTRY **itemp, struct hsearch_data *head)
203: {
204: struct internal_head *table, *chain;
1.1 cgd 205: struct internal_entry *ie;
206: uint32_t hashval;
207: size_t len;
1.7 christos 208: void *p;
1.1 cgd 209:
1.3 lukem 210: _DIAGASSERT(item.key != NULL);
211: _DIAGASSERT(action == ENTER || action == FIND);
1.1 cgd 212:
1.7 christos 213: p = head->table;
214: table = p;
215:
1.1 cgd 216: len = strlen(item.key);
217: hashval = (*__default_hash)(item.key, len);
218:
1.7 christos 219: chain = &table[hashval & (head->size - 1)];
220: ie = SLIST_FIRST(chain);
1.1 cgd 221: while (ie != NULL) {
222: if (strcmp(ie->ent.key, item.key) == 0)
223: break;
224: ie = SLIST_NEXT(ie, link);
225: }
226:
1.7 christos 227: if (ie != NULL) {
228: *itemp = &ie->ent;
229: return 1;
230: } else if (action == FIND) {
231: *itemp = NULL;
232: errno = ESRCH;
233: return 1;
234: }
1.1 cgd 235:
236: ie = malloc(sizeof *ie);
237: if (ie == NULL)
1.7 christos 238: return 0;
1.1 cgd 239: ie->ent.key = item.key;
240: ie->ent.data = item.data;
241:
1.7 christos 242: SLIST_INSERT_HEAD(chain, ie, link);
243: *itemp = &ie->ent;
244: head->filled++;
245: return 1;
1.1 cgd 246: }
CVSweb <webmaster@jp.NetBSD.org>