xref: /freebsd/lib/libc/stdlib/hcreate.c (revision 39ee7a7a6bdd1557b1c3532abf60d139798ac88b)
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 }
219