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
51typedef 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
57struct 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
67struct HashSetIterator {
68	HASHSET i_h;
69	uint_t i_indx;
70	ENTRY *i_e;
71	uint_t i_coll;
72};
73
74static 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
91HASHSET
92h_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
132const void *
133h_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
152static void
153rehash(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
186const void *
187h_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
222const void *
223h_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
248HASHSET_ITERATOR
249h_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
265const void *
266h_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