xref: /illumos-gate/usr/src/cmd/fs.d/nfs/mountd/hashset.c (revision 4a508a79)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
5*4a508a79SThomas Haynes  * Common Development and Distribution License (the "License").
6*4a508a79SThomas Haynes  * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate  * and limitations under the License.
127c478bd9Sstevel@tonic-gate  *
137c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate  *
197c478bd9Sstevel@tonic-gate  * CDDL HEADER END
207c478bd9Sstevel@tonic-gate  */
21*4a508a79SThomas Haynes 
227c478bd9Sstevel@tonic-gate /*
23*4a508a79SThomas Haynes  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
24*4a508a79SThomas Haynes  * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate  */
267c478bd9Sstevel@tonic-gate 
277c478bd9Sstevel@tonic-gate #include <stdio.h>
287c478bd9Sstevel@tonic-gate #include <stdlib.h>
297c478bd9Sstevel@tonic-gate #include <string.h>
307c478bd9Sstevel@tonic-gate #include "hashset.h"
317c478bd9Sstevel@tonic-gate #include "mountd.h"
32*4a508a79SThomas Haynes #include <sys/sdt.h>
337c478bd9Sstevel@tonic-gate 
347c478bd9Sstevel@tonic-gate /*
357c478bd9Sstevel@tonic-gate  * HASHSET is hash table managing pointers to a set of keys
367c478bd9Sstevel@tonic-gate  * (set is a collection without duplicates). The public interface
377c478bd9Sstevel@tonic-gate  * of the HASHSET is similar to the java.util.Set interface.
387c478bd9Sstevel@tonic-gate  * Unlike the libc `hsearch' based hash table, this implementation
397c478bd9Sstevel@tonic-gate  * does allow multiple instances of HASHSET within a single application,
407c478bd9Sstevel@tonic-gate  * and the HASHSET_ITERATOR allows to iterate through the entire set
417c478bd9Sstevel@tonic-gate  * using h_next().
427c478bd9Sstevel@tonic-gate  *
437c478bd9Sstevel@tonic-gate  * HASHSET does not store actual keys but only pointers to keys. Hence the
447c478bd9Sstevel@tonic-gate  * data remains intact when HASHSET grows (resizes itself). HASHSET accesses
457c478bd9Sstevel@tonic-gate  * the actual key data only through the hash and equal functions given
467c478bd9Sstevel@tonic-gate  * as arguments to h_create.
477c478bd9Sstevel@tonic-gate  *
487c478bd9Sstevel@tonic-gate  * Hash collisions are resolved with linked lists.
497c478bd9Sstevel@tonic-gate  */
507c478bd9Sstevel@tonic-gate 
517c478bd9Sstevel@tonic-gate typedef struct HashSetEntry {
527c478bd9Sstevel@tonic-gate 	uint_t e_hash;		/* Hash value */
537c478bd9Sstevel@tonic-gate 	const void *e_key;	/* Pointer to a key */
547c478bd9Sstevel@tonic-gate 	struct HashSetEntry *e_next;
557c478bd9Sstevel@tonic-gate } ENTRY;
567c478bd9Sstevel@tonic-gate 
577c478bd9Sstevel@tonic-gate struct HashSet {
587c478bd9Sstevel@tonic-gate 	ENTRY **h_table;	/* Pointer to an array of ENTRY'ies */
597c478bd9Sstevel@tonic-gate 	uint_t h_tableSize;	/* Size of the array */
607c478bd9Sstevel@tonic-gate 	uint_t h_count;		/* Current count */
617c478bd9Sstevel@tonic-gate 	uint_t h_threshold;	/* loadFactor threshold */
627c478bd9Sstevel@tonic-gate 	float  h_loadFactor;	/* Current loadFactor (h_count/h_tableSize( */
637c478bd9Sstevel@tonic-gate 	uint_t (*h_hash) (const void *);
647c478bd9Sstevel@tonic-gate 	int    (*h_equal) (const void *, const void *);
657c478bd9Sstevel@tonic-gate };
667c478bd9Sstevel@tonic-gate 
677c478bd9Sstevel@tonic-gate struct HashSetIterator {
687c478bd9Sstevel@tonic-gate 	HASHSET i_h;
697c478bd9Sstevel@tonic-gate 	uint_t i_indx;
707c478bd9Sstevel@tonic-gate 	ENTRY *i_e;
717c478bd9Sstevel@tonic-gate 	uint_t i_coll;
727c478bd9Sstevel@tonic-gate };
737c478bd9Sstevel@tonic-gate 
747c478bd9Sstevel@tonic-gate static void rehash(HASHSET h);
757c478bd9Sstevel@tonic-gate 
767c478bd9Sstevel@tonic-gate #define	DEFAULT_INITIALCAPACITY	1
777c478bd9Sstevel@tonic-gate #define	DEFAULT_LOADFACTOR	0.75
787c478bd9Sstevel@tonic-gate 
797c478bd9Sstevel@tonic-gate /*
807c478bd9Sstevel@tonic-gate  *  Create a HASHSET
817c478bd9Sstevel@tonic-gate  *  - HASHSET is a hash table of pointers to keys
827c478bd9Sstevel@tonic-gate  *  - duplicate keys are not allowed
837c478bd9Sstevel@tonic-gate  *  - the HASHSET is opaque and can be accessed only through the h_ functions
847c478bd9Sstevel@tonic-gate  *  - two keys k1 and k2 are considered equal if the result of equal(k1, k2)
857c478bd9Sstevel@tonic-gate  *    is non-zero
867c478bd9Sstevel@tonic-gate  *  - the function hash(key) is used to compute hash values for keys; if
877c478bd9Sstevel@tonic-gate  *    keys are "equal" the values returned by the hash function must be
887c478bd9Sstevel@tonic-gate  *    identical.
897c478bd9Sstevel@tonic-gate  */
907c478bd9Sstevel@tonic-gate 
917c478bd9Sstevel@tonic-gate HASHSET
h_create(uint_t (* hash)(const void *),int (* equal)(const void *,const void *),uint_t initialCapacity,float loadFactor)927c478bd9Sstevel@tonic-gate h_create(uint_t (*hash) (const void *),
937c478bd9Sstevel@tonic-gate     int    (*equal) (const void *, const void *),
947c478bd9Sstevel@tonic-gate     uint_t initialCapacity,
957c478bd9Sstevel@tonic-gate     float loadFactor)
967c478bd9Sstevel@tonic-gate {
977c478bd9Sstevel@tonic-gate 	HASHSET h;
987c478bd9Sstevel@tonic-gate 
997c478bd9Sstevel@tonic-gate 	if (initialCapacity == 0)
1007c478bd9Sstevel@tonic-gate 		initialCapacity = DEFAULT_INITIALCAPACITY;
1017c478bd9Sstevel@tonic-gate 
1027c478bd9Sstevel@tonic-gate 	if (loadFactor < 0.0)
1037c478bd9Sstevel@tonic-gate 		loadFactor = DEFAULT_LOADFACTOR;
1047c478bd9Sstevel@tonic-gate 
1057c478bd9Sstevel@tonic-gate 	h = exmalloc(sizeof (*h));
1067c478bd9Sstevel@tonic-gate 
1077c478bd9Sstevel@tonic-gate 	if (h == NULL)
1087c478bd9Sstevel@tonic-gate 		return (NULL);
1097c478bd9Sstevel@tonic-gate 
1107c478bd9Sstevel@tonic-gate 	h->h_table = exmalloc(initialCapacity * sizeof (ENTRY *));
1117c478bd9Sstevel@tonic-gate 
1127c478bd9Sstevel@tonic-gate 	(void) memset(h->h_table, 0, initialCapacity * sizeof (ENTRY *));
1137c478bd9Sstevel@tonic-gate 
1147c478bd9Sstevel@tonic-gate 	if (h->h_table == NULL) {
1157c478bd9Sstevel@tonic-gate 		free(h);
1167c478bd9Sstevel@tonic-gate 		return (NULL);
1177c478bd9Sstevel@tonic-gate 	}
1187c478bd9Sstevel@tonic-gate 	h->h_tableSize = initialCapacity;
1197c478bd9Sstevel@tonic-gate 	h->h_hash = hash;
1207c478bd9Sstevel@tonic-gate 	h->h_equal = equal;
1217c478bd9Sstevel@tonic-gate 	h->h_loadFactor = loadFactor;
1227c478bd9Sstevel@tonic-gate 	h->h_threshold = (uint_t)(initialCapacity * loadFactor);
1237c478bd9Sstevel@tonic-gate 	h->h_count = 0;
1247c478bd9Sstevel@tonic-gate 
1257c478bd9Sstevel@tonic-gate 	return (h);
1267c478bd9Sstevel@tonic-gate }
1277c478bd9Sstevel@tonic-gate 
1287c478bd9Sstevel@tonic-gate /*
1297c478bd9Sstevel@tonic-gate  *  Return a pointer to a matching key
1307c478bd9Sstevel@tonic-gate  */
1317c478bd9Sstevel@tonic-gate 
1327c478bd9Sstevel@tonic-gate const void *
h_get(const HASHSET h,void * key)1337c478bd9Sstevel@tonic-gate h_get(const HASHSET h, void *key)
1347c478bd9Sstevel@tonic-gate {
1357c478bd9Sstevel@tonic-gate 	uint_t hash = h->h_hash(key);
1367c478bd9Sstevel@tonic-gate 	uint_t i = hash % h->h_tableSize;
1377c478bd9Sstevel@tonic-gate 	ENTRY *e;
1387c478bd9Sstevel@tonic-gate 
1397c478bd9Sstevel@tonic-gate 	for (e = h->h_table[i]; e; e = e->e_next)
1407c478bd9Sstevel@tonic-gate 		if (e->e_hash == hash && h->h_equal(e->e_key, key))
1417c478bd9Sstevel@tonic-gate 			return (e->e_key);
1427c478bd9Sstevel@tonic-gate 
1437c478bd9Sstevel@tonic-gate 	return (NULL);
1447c478bd9Sstevel@tonic-gate }
1457c478bd9Sstevel@tonic-gate 
1467c478bd9Sstevel@tonic-gate /*
1477c478bd9Sstevel@tonic-gate  *  Rehash (grow) HASHSET
1487c478bd9Sstevel@tonic-gate  *  - called when loadFactor exceeds threshold
1497c478bd9Sstevel@tonic-gate  *  - new size is 2*old_size+1
1507c478bd9Sstevel@tonic-gate  */
1517c478bd9Sstevel@tonic-gate 
1527c478bd9Sstevel@tonic-gate static void
rehash(HASHSET h)1537c478bd9Sstevel@tonic-gate rehash(HASHSET h)
1547c478bd9Sstevel@tonic-gate {
1557c478bd9Sstevel@tonic-gate 	uint_t i = h->h_tableSize;
1567c478bd9Sstevel@tonic-gate 	uint_t newtabSize = 2 * i + 1;
1577c478bd9Sstevel@tonic-gate 	ENTRY **newtab = exmalloc(newtabSize * sizeof (ENTRY *));
1587c478bd9Sstevel@tonic-gate 
1597c478bd9Sstevel@tonic-gate 	(void) memset(newtab, 0, newtabSize * sizeof (ENTRY *));
1607c478bd9Sstevel@tonic-gate 
1617c478bd9Sstevel@tonic-gate 	while (i--) {
1627c478bd9Sstevel@tonic-gate 		ENTRY *e, *next;
1637c478bd9Sstevel@tonic-gate 
1647c478bd9Sstevel@tonic-gate 		for (e = h->h_table[i]; e; e = next) {
1657c478bd9Sstevel@tonic-gate 			uint_t k = e->e_hash % newtabSize;
1667c478bd9Sstevel@tonic-gate 
1677c478bd9Sstevel@tonic-gate 			next = (ENTRY *) e->e_next;
1687c478bd9Sstevel@tonic-gate 			e->e_next = (ENTRY *) newtab[k];
1697c478bd9Sstevel@tonic-gate 			newtab[k] = e;
1707c478bd9Sstevel@tonic-gate 		}
1717c478bd9Sstevel@tonic-gate 	}
1727c478bd9Sstevel@tonic-gate 
1737c478bd9Sstevel@tonic-gate 	h->h_threshold = (uint_t)(newtabSize * h->h_loadFactor);
1747c478bd9Sstevel@tonic-gate 	h->h_tableSize = newtabSize;
1757c478bd9Sstevel@tonic-gate 	free(h->h_table);
1767c478bd9Sstevel@tonic-gate 	h->h_table = newtab;
1777c478bd9Sstevel@tonic-gate }
1787c478bd9Sstevel@tonic-gate 
1797c478bd9Sstevel@tonic-gate /*
1807c478bd9Sstevel@tonic-gate  *  Store a key into a HASHSET
1817c478bd9Sstevel@tonic-gate  *  - if there is already an "equal" key then the new key will not
1827c478bd9Sstevel@tonic-gate  *    be stored and the function returns a pointer to an existing key
1837c478bd9Sstevel@tonic-gate  *  - otherwise the function stores pointer to the new key and return NULL
1847c478bd9Sstevel@tonic-gate  */
1857c478bd9Sstevel@tonic-gate 
1867c478bd9Sstevel@tonic-gate const void *
h_put(HASHSET h,const void * key)1877c478bd9Sstevel@tonic-gate h_put(HASHSET h, const void *key)
1887c478bd9Sstevel@tonic-gate {
1897c478bd9Sstevel@tonic-gate 	uint_t hash = h->h_hash(key);
1907c478bd9Sstevel@tonic-gate 	uint_t indx = hash % h->h_tableSize;
1917c478bd9Sstevel@tonic-gate 	ENTRY *e;
1927c478bd9Sstevel@tonic-gate 
1937c478bd9Sstevel@tonic-gate 	for (e = h->h_table[indx]; e; e = e->e_next)
1947c478bd9Sstevel@tonic-gate 		if (e->e_hash == hash && h->h_equal(e->e_key, key))
1957c478bd9Sstevel@tonic-gate 			return (key);
1967c478bd9Sstevel@tonic-gate 
1977c478bd9Sstevel@tonic-gate 	if (h->h_count >= h->h_threshold) {
1987c478bd9Sstevel@tonic-gate 		rehash(h);
1997c478bd9Sstevel@tonic-gate 
2007c478bd9Sstevel@tonic-gate 		indx = hash % h->h_tableSize;
2017c478bd9Sstevel@tonic-gate 	}
2027c478bd9Sstevel@tonic-gate 
2037c478bd9Sstevel@tonic-gate 	e = exmalloc(sizeof (ENTRY));
2047c478bd9Sstevel@tonic-gate 	e->e_hash = hash;
2057c478bd9Sstevel@tonic-gate 	e->e_key = (void *) key;
2067c478bd9Sstevel@tonic-gate 	e->e_next = h->h_table[indx];
2077c478bd9Sstevel@tonic-gate 
2087c478bd9Sstevel@tonic-gate 	h->h_table[indx] = e;
2097c478bd9Sstevel@tonic-gate 	h->h_count++;
2107c478bd9Sstevel@tonic-gate 
211*4a508a79SThomas Haynes 	DTRACE_PROBE2(mountd, hashset, h->h_count, h->h_loadFactor);
212*4a508a79SThomas Haynes 
2137c478bd9Sstevel@tonic-gate 	return (NULL);
2147c478bd9Sstevel@tonic-gate }
2157c478bd9Sstevel@tonic-gate 
2167c478bd9Sstevel@tonic-gate /*
2177c478bd9Sstevel@tonic-gate  *  Delete a key
2187c478bd9Sstevel@tonic-gate  *  - if there is no "equal" key in the HASHSET the fuction returns NULL
2197c478bd9Sstevel@tonic-gate  *  - otherwise the function returns a pointer to the deleted key
2207c478bd9Sstevel@tonic-gate  */
2217c478bd9Sstevel@tonic-gate 
2227c478bd9Sstevel@tonic-gate const void *
h_delete(HASHSET h,const void * key)2237c478bd9Sstevel@tonic-gate h_delete(HASHSET h, const void *key)
2247c478bd9Sstevel@tonic-gate {
2257c478bd9Sstevel@tonic-gate 	uint_t hash = h->h_hash(key);
2267c478bd9Sstevel@tonic-gate 	uint_t indx = hash % h->h_tableSize;
2277c478bd9Sstevel@tonic-gate 	ENTRY *e, *prev;
2287c478bd9Sstevel@tonic-gate 
2297c478bd9Sstevel@tonic-gate 	for (e = h->h_table[indx], prev = NULL; e; prev = e, e = e->e_next) {
2307c478bd9Sstevel@tonic-gate 		if (e->e_hash == hash && h->h_equal(e->e_key, key)) {
2317c478bd9Sstevel@tonic-gate 			key = e->e_key;
2327c478bd9Sstevel@tonic-gate 			if (prev)
2337c478bd9Sstevel@tonic-gate 				prev->e_next = e->e_next;
2347c478bd9Sstevel@tonic-gate 			else
2357c478bd9Sstevel@tonic-gate 				h->h_table[indx] = e->e_next;
2367c478bd9Sstevel@tonic-gate 			free(e);
2377c478bd9Sstevel@tonic-gate 			return (key);
2387c478bd9Sstevel@tonic-gate 		}
2397c478bd9Sstevel@tonic-gate 	}
2407c478bd9Sstevel@tonic-gate 
2417c478bd9Sstevel@tonic-gate 	return (NULL);
2427c478bd9Sstevel@tonic-gate }
2437c478bd9Sstevel@tonic-gate 
2447c478bd9Sstevel@tonic-gate /*
2457c478bd9Sstevel@tonic-gate  *  Return an opaque HASHSET_ITERATOR (to be used in h_next())
2467c478bd9Sstevel@tonic-gate  */
2477c478bd9Sstevel@tonic-gate 
2487c478bd9Sstevel@tonic-gate HASHSET_ITERATOR
h_iterator(HASHSET h)2497c478bd9Sstevel@tonic-gate h_iterator(HASHSET h)
2507c478bd9Sstevel@tonic-gate {
2517c478bd9Sstevel@tonic-gate 	HASHSET_ITERATOR i = exmalloc(sizeof (*i));
2527c478bd9Sstevel@tonic-gate 
2537c478bd9Sstevel@tonic-gate 	i->i_h = h;
2547c478bd9Sstevel@tonic-gate 	i->i_indx = h->h_tableSize;
2557c478bd9Sstevel@tonic-gate 	i->i_e = NULL;
2567c478bd9Sstevel@tonic-gate 	i->i_coll = 0;
2577c478bd9Sstevel@tonic-gate 
2587c478bd9Sstevel@tonic-gate 	return (i);
2597c478bd9Sstevel@tonic-gate }
2607c478bd9Sstevel@tonic-gate 
2617c478bd9Sstevel@tonic-gate /*
2627c478bd9Sstevel@tonic-gate  * Return a pointer to a next key
2637c478bd9Sstevel@tonic-gate  */
2647c478bd9Sstevel@tonic-gate 
2657c478bd9Sstevel@tonic-gate const void *
h_next(HASHSET_ITERATOR i)2667c478bd9Sstevel@tonic-gate h_next(HASHSET_ITERATOR i)
2677c478bd9Sstevel@tonic-gate {
2687c478bd9Sstevel@tonic-gate 	const void *key;
2697c478bd9Sstevel@tonic-gate 
2707c478bd9Sstevel@tonic-gate 	while (i->i_e == NULL) {
2717c478bd9Sstevel@tonic-gate 		if (i->i_indx-- == 0)
2727c478bd9Sstevel@tonic-gate 			return (NULL);
2737c478bd9Sstevel@tonic-gate 
2747c478bd9Sstevel@tonic-gate 		i->i_e = i->i_h->h_table[i->i_indx];
2757c478bd9Sstevel@tonic-gate 	}
2767c478bd9Sstevel@tonic-gate 
2777c478bd9Sstevel@tonic-gate 	key = i->i_e->e_key;
2787c478bd9Sstevel@tonic-gate 	i->i_e = i->i_e->e_next;
2797c478bd9Sstevel@tonic-gate 
2807c478bd9Sstevel@tonic-gate 	if (i->i_e)
2817c478bd9Sstevel@tonic-gate 		i->i_coll++;
2827c478bd9Sstevel@tonic-gate 
2837c478bd9Sstevel@tonic-gate 	return (key);
2847c478bd9Sstevel@tonic-gate }
285