Annotation of src/lib/libc/stdlib/hcreate.c, Revision 1.4
1.4 ! salo 1: /* $NetBSD: hcreate.c,v 1.3 2001/02/21 16:31:01 lukem 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.
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
1.4 ! salo 18: * NetBSD Project. See http://www.NetBSD.org/ for
1.1 cgd 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)
1.4 ! salo 51: __RCSID("$NetBSD: hcreate.c,v 1.3 2001/02/21 16:31:01 lukem Exp $");
1.1 cgd 52: #endif /* LIBC_SCCS and not lint */
53:
54: #if !defined(lint)
55: __COPYRIGHT(
56: "@(#) Copyright (c) 2001 Christopher G. Demetriou. All rights reserved.\n");
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)
1.2 ross 86: #define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2)
1.1 cgd 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 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);
1.3 lukem 169: _DIAGASSERT(item.key != NULL);
170: _DIAGASSERT(action == ENTER || action == FIND);
1.1 cgd 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: }
CVSweb <webmaster@jp.NetBSD.org>