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