Annotation of src/lib/libc/stdlib/hcreate.c, Revision 1.8
1.8 ! christos 1: /* $NetBSD: hcreate.c,v 1.7 2011/09/14 23:33:51 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 ! christos 46: __RCSID("$NetBSD: hcreate.c,v 1.7 2011/09/14 23:33:51 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
144: hdestroy(void)
145: {
1.7 christos 146: _DIAGASSERT(htable.table != NULL);
147: hdestroy_r(&htable);
148: }
149:
150: void
151: hdestroy_r(struct hsearch_data *head)
152: {
1.1 cgd 153: struct internal_entry *ie;
154: size_t idx;
1.7 christos 155: void *p;
156: struct internal_head *table;
1.1 cgd 157:
1.7 christos 158: if (head == NULL)
1.1 cgd 159: return;
160:
1.7 christos 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);
1.1 cgd 169: free(ie->ent.key);
170: free(ie);
171: }
172: }
1.7 christos 173: free(table);
1.1 cgd 174: }
175:
176: ENTRY *
177: hsearch(ENTRY item, ACTION action)
178: {
1.7 christos 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;
1.1 cgd 189: struct internal_entry *ie;
190: uint32_t hashval;
191: size_t len;
1.7 christos 192: void *p;
1.1 cgd 193:
1.3 lukem 194: _DIAGASSERT(item.key != NULL);
195: _DIAGASSERT(action == ENTER || action == FIND);
1.1 cgd 196:
1.7 christos 197: p = head->table;
198: table = p;
199:
1.1 cgd 200: len = strlen(item.key);
201: hashval = (*__default_hash)(item.key, len);
202:
1.7 christos 203: chain = &table[hashval & (head->size - 1)];
204: ie = SLIST_FIRST(chain);
1.1 cgd 205: while (ie != NULL) {
206: if (strcmp(ie->ent.key, item.key) == 0)
207: break;
208: ie = SLIST_NEXT(ie, link);
209: }
210:
1.7 christos 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: }
1.1 cgd 219:
220: ie = malloc(sizeof *ie);
221: if (ie == NULL)
1.7 christos 222: return 0;
1.1 cgd 223: ie->ent.key = item.key;
224: ie->ent.data = item.data;
225:
1.7 christos 226: SLIST_INSERT_HEAD(chain, ie, link);
227: *itemp = &ie->ent;
228: head->filled++;
229: return 1;
1.1 cgd 230: }
CVSweb <webmaster@jp.NetBSD.org>
![[BACK]](/icons/back.gif){kind=icon}
Return to hcreate.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [cvs.NetBSD.org] / src / lib / libc / stdlib