/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashset.h"
#include "mountd.h"
#include <sys/sdt.h>
/*
* HASHSET is hash table managing pointers to a set of keys
* (set is a collection without duplicates). The public interface
* of the HASHSET is similar to the java.util.Set interface.
* Unlike the libc `hsearch' based hash table, this implementation
* does allow multiple instances of HASHSET within a single application,
* and the HASHSET_ITERATOR allows to iterate through the entire set
* using h_next().
*
* HASHSET does not store actual keys but only pointers to keys. Hence the
* data remains intact when HASHSET grows (resizes itself). HASHSET accesses
* the actual key data only through the hash and equal functions given
* as arguments to h_create.
*
* Hash collisions are resolved with linked lists.
*/
typedef struct HashSetEntry {
uint_t e_hash; /* Hash value */
const void *e_key; /* Pointer to a key */
struct HashSetEntry *e_next;
} ENTRY;
struct HashSet {
ENTRY **h_table; /* Pointer to an array of ENTRY'ies */
uint_t h_tableSize; /* Size of the array */
uint_t h_count; /* Current count */
uint_t h_threshold; /* loadFactor threshold */
float h_loadFactor; /* Current loadFactor (h_count/h_tableSize( */
uint_t (*h_hash) (const void *);
int (*h_equal) (const void *, const void *);
};
struct HashSetIterator {
HASHSET i_h;
uint_t i_indx;
ENTRY *i_e;
uint_t i_coll;
};
static void rehash(HASHSET h);
#define DEFAULT_INITIALCAPACITY 1
#define DEFAULT_LOADFACTOR 0.75
/*
* Create a HASHSET
* - HASHSET is a hash table of pointers to keys
* - duplicate keys are not allowed
* - the HASHSET is opaque and can be accessed only through the h_ functions
* - two keys k1 and k2 are considered equal if the result of equal(k1, k2)
* is non-zero
* - the function hash(key) is used to compute hash values for keys; if
* keys are "equal" the values returned by the hash function must be
* identical.
*/
HASHSET
h_create(uint_t (*hash) (const void *),
int (*equal) (const void *, const void *),
uint_t initialCapacity,
float loadFactor)
{
HASHSET h;
if (initialCapacity == 0)
initialCapacity = DEFAULT_INITIALCAPACITY;
if (loadFactor < 0.0)
loadFactor = DEFAULT_LOADFACTOR;
h = exmalloc(sizeof (*h));
if (h == NULL)
return (NULL);
h->h_table = exmalloc(initialCapacity * sizeof (ENTRY *));
(void) memset(h->h_table, 0, initialCapacity * sizeof (ENTRY *));
if (h->h_table == NULL) {
free(h);
return (NULL);
}
h->h_tableSize = initialCapacity;
h->h_hash = hash;
h->h_equal = equal;
h->h_loadFactor = loadFactor;
h->h_threshold = (uint_t)(initialCapacity * loadFactor);
h->h_count = 0;
return (h);
}
/*
* Return a pointer to a matching key
*/
const void *
h_get(const HASHSET h, void *key)
{
uint_t hash = h->h_hash(key);
uint_t i = hash % h->h_tableSize;
ENTRY *e;
for (e = h->h_table[i]; e; e = e->e_next)
if (e->e_hash == hash && h->h_equal(e->e_key, key))
return (e->e_key);
return (NULL);
}
/*
* Rehash (grow) HASHSET
* - called when loadFactor exceeds threshold
* - new size is 2*old_size+1
*/
static void
rehash(HASHSET h)
{
uint_t i = h->h_tableSize;
uint_t newtabSize = 2 * i + 1;
ENTRY **newtab = exmalloc(newtabSize * sizeof (ENTRY *));
(void) memset(newtab, 0, newtabSize * sizeof (ENTRY *));
while (i--) {
ENTRY *e, *next;
for (e = h->h_table[i]; e; e = next) {
uint_t k = e->e_hash % newtabSize;
next = (ENTRY *) e->e_next;
e->e_next = (ENTRY *) newtab[k];
newtab[k] = e;
}
}
h->h_threshold = (uint_t)(newtabSize * h->h_loadFactor);
h->h_tableSize = newtabSize;
free(h->h_table);
h->h_table = newtab;
}
/*
* Store a key into a HASHSET
* - if there is already an "equal" key then the new key will not
* be stored and the function returns a pointer to an existing key
* - otherwise the function stores pointer to the new key and return NULL
*/
const void *
h_put(HASHSET h, const void *key)
{
uint_t hash = h->h_hash(key);
uint_t indx = hash % h->h_tableSize;
ENTRY *e;
for (e = h->h_table[indx]; e; e = e->e_next)
if (e->e_hash == hash && h->h_equal(e->e_key, key))
return (key);
if (h->h_count >= h->h_threshold) {
rehash(h);
indx = hash % h->h_tableSize;
}
e = exmalloc(sizeof (ENTRY));
e->e_hash = hash;
e->e_key = (void *) key;
e->e_next = h->h_table[indx];
h->h_table[indx] = e;
h->h_count++;
DTRACE_PROBE2(mountd, hashset, h->h_count, h->h_loadFactor);
return (NULL);
}
/*
* Delete a key
* - if there is no "equal" key in the HASHSET the fuction returns NULL
* - otherwise the function returns a pointer to the deleted key
*/
const void *
h_delete(HASHSET h, const void *key)
{
uint_t hash = h->h_hash(key);
uint_t indx = hash % h->h_tableSize;
ENTRY *e, *prev;
for (e = h->h_table[indx], prev = NULL; e; prev = e, e = e->e_next) {
if (e->e_hash == hash && h->h_equal(e->e_key, key)) {
key = e->e_key;
if (prev)
prev->e_next = e->e_next;
else
h->h_table[indx] = e->e_next;
free(e);
return (key);
}
}
return (NULL);
}
/*
* Return an opaque HASHSET_ITERATOR (to be used in h_next())
*/
HASHSET_ITERATOR
h_iterator(HASHSET h)
{
HASHSET_ITERATOR i = exmalloc(sizeof (*i));
i->i_h = h;
i->i_indx = h->h_tableSize;
i->i_e = NULL;
i->i_coll = 0;
return (i);
}
/*
* Return a pointer to a next key
*/
const void *
h_next(HASHSET_ITERATOR i)
{
const void *key;
while (i->i_e == NULL) {
if (i->i_indx-- == 0)
return (NULL);
i->i_e = i->i_h->h_table[i->i_indx];
}
key = i->i_e->e_key;
i->i_e = i->i_e->e_next;
if (i->i_e)
i->i_coll++;
return (key);
}