xref: /illumos-gate/usr/src/cmd/fs.d/nfs/mountd/hashset.c (revision 4a508a79352d55b18841bdb18d6d7b4153b6c03a)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include "hashset.h"
31 #include "mountd.h"
32 #include <sys/sdt.h>
33 
34 /*
35  * HASHSET is hash table managing pointers to a set of keys
36  * (set is a collection without duplicates). The public interface
37  * of the HASHSET is similar to the java.util.Set interface.
38  * Unlike the libc `hsearch' based hash table, this implementation
39  * does allow multiple instances of HASHSET within a single application,
40  * and the HASHSET_ITERATOR allows to iterate through the entire set
41  * using h_next().
42  *
43  * HASHSET does not store actual keys but only pointers to keys. Hence the
44  * data remains intact when HASHSET grows (resizes itself). HASHSET accesses
45  * the actual key data only through the hash and equal functions given
46  * as arguments to h_create.
47  *
48  * Hash collisions are resolved with linked lists.
49  */
50 
51 typedef struct HashSetEntry {
52 	uint_t e_hash;		/* Hash value */
53 	const void *e_key;	/* Pointer to a key */
54 	struct HashSetEntry *e_next;
55 } ENTRY;
56 
57 struct HashSet {
58 	ENTRY **h_table;	/* Pointer to an array of ENTRY'ies */
59 	uint_t h_tableSize;	/* Size of the array */
60 	uint_t h_count;		/* Current count */
61 	uint_t h_threshold;	/* loadFactor threshold */
62 	float  h_loadFactor;	/* Current loadFactor (h_count/h_tableSize( */
63 	uint_t (*h_hash) (const void *);
64 	int    (*h_equal) (const void *, const void *);
65 };
66 
67 struct HashSetIterator {
68 	HASHSET i_h;
69 	uint_t i_indx;
70 	ENTRY *i_e;
71 	uint_t i_coll;
72 };
73 
74 static void rehash(HASHSET h);
75 
76 #define	DEFAULT_INITIALCAPACITY	1
77 #define	DEFAULT_LOADFACTOR	0.75
78 
79 /*
80  *  Create a HASHSET
81  *  - HASHSET is a hash table of pointers to keys
82  *  - duplicate keys are not allowed
83  *  - the HASHSET is opaque and can be accessed only through the h_ functions
84  *  - two keys k1 and k2 are considered equal if the result of equal(k1, k2)
85  *    is non-zero
86  *  - the function hash(key) is used to compute hash values for keys; if
87  *    keys are "equal" the values returned by the hash function must be
88  *    identical.
89  */
90 
91 HASHSET
h_create(uint_t (* hash)(const void *),int (* equal)(const void *,const void *),uint_t initialCapacity,float loadFactor)92 h_create(uint_t (*hash) (const void *),
93     int    (*equal) (const void *, const void *),
94     uint_t initialCapacity,
95     float loadFactor)
96 {
97 	HASHSET h;
98 
99 	if (initialCapacity == 0)
100 		initialCapacity = DEFAULT_INITIALCAPACITY;
101 
102 	if (loadFactor < 0.0)
103 		loadFactor = DEFAULT_LOADFACTOR;
104 
105 	h = exmalloc(sizeof (*h));
106 
107 	if (h == NULL)
108 		return (NULL);
109 
110 	h->h_table = exmalloc(initialCapacity * sizeof (ENTRY *));
111 
112 	(void) memset(h->h_table, 0, initialCapacity * sizeof (ENTRY *));
113 
114 	if (h->h_table == NULL) {
115 		free(h);
116 		return (NULL);
117 	}
118 	h->h_tableSize = initialCapacity;
119 	h->h_hash = hash;
120 	h->h_equal = equal;
121 	h->h_loadFactor = loadFactor;
122 	h->h_threshold = (uint_t)(initialCapacity * loadFactor);
123 	h->h_count = 0;
124 
125 	return (h);
126 }
127 
128 /*
129  *  Return a pointer to a matching key
130  */
131 
132 const void *
h_get(const HASHSET h,void * key)133 h_get(const HASHSET h, void *key)
134 {
135 	uint_t hash = h->h_hash(key);
136 	uint_t i = hash % h->h_tableSize;
137 	ENTRY *e;
138 
139 	for (e = h->h_table[i]; e; e = e->e_next)
140 		if (e->e_hash == hash && h->h_equal(e->e_key, key))
141 			return (e->e_key);
142 
143 	return (NULL);
144 }
145 
146 /*
147  *  Rehash (grow) HASHSET
148  *  - called when loadFactor exceeds threshold
149  *  - new size is 2*old_size+1
150  */
151 
152 static void
rehash(HASHSET h)153 rehash(HASHSET h)
154 {
155 	uint_t i = h->h_tableSize;
156 	uint_t newtabSize = 2 * i + 1;
157 	ENTRY **newtab = exmalloc(newtabSize * sizeof (ENTRY *));
158 
159 	(void) memset(newtab, 0, newtabSize * sizeof (ENTRY *));
160 
161 	while (i--) {
162 		ENTRY *e, *next;
163 
164 		for (e = h->h_table[i]; e; e = next) {
165 			uint_t k = e->e_hash % newtabSize;
166 
167 			next = (ENTRY *) e->e_next;
168 			e->e_next = (ENTRY *) newtab[k];
169 			newtab[k] = e;
170 		}
171 	}
172 
173 	h->h_threshold = (uint_t)(newtabSize * h->h_loadFactor);
174 	h->h_tableSize = newtabSize;
175 	free(h->h_table);
176 	h->h_table = newtab;
177 }
178 
179 /*
180  *  Store a key into a HASHSET
181  *  - if there is already an "equal" key then the new key will not
182  *    be stored and the function returns a pointer to an existing key
183  *  - otherwise the function stores pointer to the new key and return NULL
184  */
185 
186 const void *
h_put(HASHSET h,const void * key)187 h_put(HASHSET h, const void *key)
188 {
189 	uint_t hash = h->h_hash(key);
190 	uint_t indx = hash % h->h_tableSize;
191 	ENTRY *e;
192 
193 	for (e = h->h_table[indx]; e; e = e->e_next)
194 		if (e->e_hash == hash && h->h_equal(e->e_key, key))
195 			return (key);
196 
197 	if (h->h_count >= h->h_threshold) {
198 		rehash(h);
199 
200 		indx = hash % h->h_tableSize;
201 	}
202 
203 	e = exmalloc(sizeof (ENTRY));
204 	e->e_hash = hash;
205 	e->e_key = (void *) key;
206 	e->e_next = h->h_table[indx];
207 
208 	h->h_table[indx] = e;
209 	h->h_count++;
210 
211 	DTRACE_PROBE2(mountd, hashset, h->h_count, h->h_loadFactor);
212 
213 	return (NULL);
214 }
215 
216 /*
217  *  Delete a key
218  *  - if there is no "equal" key in the HASHSET the fuction returns NULL
219  *  - otherwise the function returns a pointer to the deleted key
220  */
221 
222 const void *
h_delete(HASHSET h,const void * key)223 h_delete(HASHSET h, const void *key)
224 {
225 	uint_t hash = h->h_hash(key);
226 	uint_t indx = hash % h->h_tableSize;
227 	ENTRY *e, *prev;
228 
229 	for (e = h->h_table[indx], prev = NULL; e; prev = e, e = e->e_next) {
230 		if (e->e_hash == hash && h->h_equal(e->e_key, key)) {
231 			key = e->e_key;
232 			if (prev)
233 				prev->e_next = e->e_next;
234 			else
235 				h->h_table[indx] = e->e_next;
236 			free(e);
237 			return (key);
238 		}
239 	}
240 
241 	return (NULL);
242 }
243 
244 /*
245  *  Return an opaque HASHSET_ITERATOR (to be used in h_next())
246  */
247 
248 HASHSET_ITERATOR
h_iterator(HASHSET h)249 h_iterator(HASHSET h)
250 {
251 	HASHSET_ITERATOR i = exmalloc(sizeof (*i));
252 
253 	i->i_h = h;
254 	i->i_indx = h->h_tableSize;
255 	i->i_e = NULL;
256 	i->i_coll = 0;
257 
258 	return (i);
259 }
260 
261 /*
262  * Return a pointer to a next key
263  */
264 
265 const void *
h_next(HASHSET_ITERATOR i)266 h_next(HASHSET_ITERATOR i)
267 {
268 	const void *key;
269 
270 	while (i->i_e == NULL) {
271 		if (i->i_indx-- == 0)
272 			return (NULL);
273 
274 		i->i_e = i->i_h->h_table[i->i_indx];
275 	}
276 
277 	key = i->i_e->e_key;
278 	i->i_e = i->i_e->e_next;
279 
280 	if (i->i_e)
281 		i->i_coll++;
282 
283 	return (key);
284 }
285