OpenSolaris_b135/lib/udapl/udapl_tavor/common/dapl_hash.c
/*
* 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 (c) 2002-2003, Network Appliance, Inc. All rights reserved.
*/
/*
* Copyright 2004 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/*
*
* MODULE: dapl_hash.c
*
* PURPOSE: Hash Table
* Description:
*
* Provides a generic hash table with chaining.
*
* $Id: dapl_hash.c,v 1.10 2003/07/11 18:42:17 hobie16 Exp $
*/
#include "dapl_hash.h"
/*
*
* Structures
*
*/
/*
* A hash table element
*/
typedef struct DAPL_HASH_ELEM
{
struct DAPL_HASH_ELEM *next_element;
DAPL_HASH_KEY key;
void *datum;
} DAPL_HASH_ELEM;
/*
* The hash table
*/
struct dapl_hash_table
{
unsigned long num_entries;
unsigned long tbl_size;
DAPL_HASH_ELEM *table;
DAT_BOOLEAN locking_required; /* internal locking reqd */
DAPL_OS_LOCK lock;
unsigned long iterator_bucket;
DAPL_HASH_ELEM *iterator;
/*
* statistics - we tally on insert operations, counting
* the number of entries in the whole hash table, as
* well as the length of chains we walk to insert. This
* ignores empty buckets, giving us data on overall table
* occupancy, as well as max/average chain length for
* the buckets used. If our hash function results in
* hot buckets, this will show it.
*/
uint64_t hash_tbl_inserts; /* total inserts ops */
uint64_t hash_tbl_max; /* max in entire table */
uint64_t hash_tbl_total; /* total in table */
uint64_t hash_chn_max; /* longest chain */
uint64_t hash_chn_total; /* total non-0 lenghts */
};
/*
*
* Defines
*
*/
/* The hash function */
#define DAPL_DOHASH(key, hashsize) ((uint64_t)((key) % (hashsize)))
/* datum value in empty table slots (use 0UL or ~0UL as appropriate) */
#define NO_DATUM_VALUE ((void *) 0UL)
#define NO_DATUM(value) ((value) == NO_DATUM_VALUE)
/* Lookup macro (which falls back to function to rehash) */
#define DAPL_HASHLOOKUP(p_table, in_key, out_datum, bucket_head) \
{ \
DAPL_HASH_ELEM *element = \
&((p_table)->table)[DAPL_DOHASH(in_key, (p_table)->tbl_size)]; \
if (NO_DATUM(element->datum)) { \
(bucket_head) = (void *)0; \
} else if (element->key == (DAPL_HASH_KEY) (in_key)) { \
(out_datum) = element->datum; \
(bucket_head) = (void *)element; \
} else if (element->next_element) { \
dapli_hash_rehash(element, \
(in_key), \
(void **)&(out_datum), \
(DAPL_HASH_ELEM **)&(bucket_head)); \
} else { \
(bucket_head) = (void *)0; \
}\
}
/*
*
* Internal Functions
*
*/
/*
* Rehash the key (used by add and lookup functions)
*
* Inputs: element element to rehash key
* key, datum datum for key head
* head head for list
*/
static void
dapli_hash_rehash(
DAPL_HASH_ELEM *element,
DAPL_HASH_KEY key,
void **datum,
DAPL_HASH_ELEM ** head)
{
/*
* assume we looked at the contents of element already,
* and start with the next element.
*/
dapl_os_assert(element->next_element);
dapl_os_assert(!NO_DATUM(element->datum));
*head = element;
/*CONSTCOND*/
while (1) {
element = element->next_element;
if (!element) {
break;
}
if (element->key == key) {
*datum = element->datum;
return;
}
}
*head = 0;
}
/*
* Add a new key to the hash table
*
* Inputs:
* table, key and datum to be added
* allow_dup - DAT_TRUE if dups are allowed
* Outputs:
* report_dup - should you care to know
* Returns:
* DAT_TRUE on success
*/
static DAT_BOOLEAN
dapli_hash_add(
DAPL_HASH_TABLEP p_table,
DAPL_HASH_KEY key,
void *datum,
DAT_BOOLEAN allow_dup,
DAT_BOOLEAN *report_dup)
{
void *olddatum;
DAPL_HASH_KEY hashValue;
DAPL_HASH_ELEM *found;
DAT_BOOLEAN status = DAT_FALSE;
unsigned int chain_len = 0;
if (report_dup) {
(*report_dup) = DAT_FALSE;
}
if (NO_DATUM(datum)) {
/*
* Reserved value used for datum
*/
dapl_dbg_log(
DAPL_DBG_TYPE_ERR,
"dapli_hash_add () called with magic NO_DATA value "
"(%p) used as datum!\n", datum);
return (DAT_FALSE);
}
DAPL_HASHLOOKUP(p_table, key, olddatum, found);
if (found) {
/*
* key exists already
*/
if (report_dup) {
*report_dup = DAT_TRUE;
}
if (!allow_dup) {
dapl_dbg_log(DAPL_DBG_TYPE_ERR,
"dapli_hash_add () called with duplicate key "
"(" F64x ")\n", key);
return (DAT_FALSE);
}
}
hashValue = DAPL_DOHASH(key, p_table->tbl_size);
if (NO_DATUM(p_table->table[hashValue].datum)) {
/*
* Empty head - just fill it in
*/
p_table->table[hashValue].key = key;
p_table->table[hashValue].datum = datum;
p_table->table[hashValue].next_element = 0;
p_table->num_entries++;
status = DAT_TRUE;
} else {
DAPL_HASH_ELEM *newelement = (DAPL_HASH_ELEM *)
dapl_os_alloc(sizeof (DAPL_HASH_ELEM));
/*
* Add an element to the end of the chain
*/
if (newelement) {
DAPL_HASH_ELEM *lastelement;
newelement->key = key;
newelement->datum = datum;
newelement->next_element = 0;
for (lastelement = &p_table->table[hashValue];
lastelement->next_element;
lastelement = lastelement->next_element) {
/* Walk to the end of the chain */
chain_len++;
}
lastelement->next_element = newelement;
p_table->num_entries++;
status = DAT_TRUE;
} else {
/* allocation failed - should not happen */
status = DAT_FALSE;
}
}
/*
* Tally up our counters. chain_len is one less than current chain
* length.
*/
chain_len++;
p_table->hash_tbl_inserts++;
p_table->hash_tbl_total += p_table->num_entries;
p_table->hash_chn_total += chain_len;
if (p_table->num_entries > p_table->hash_tbl_max) {
p_table->hash_tbl_max = p_table->num_entries;
}
if (chain_len > p_table->hash_chn_max) {
p_table->hash_chn_max = chain_len;
}
return (status);
}
/*
* Remove element from hash bucket
*
* Inputs:
* element, key to be deleted
* Returns:
* DAT_TRUE on success
*/
static DAT_BOOLEAN
dapl_hash_delete_element(DAPL_HASH_ELEM * element,
DAPL_HASH_KEY key,
DAPL_HASH_DATA *p_datum)
{
DAPL_HASH_ELEM *curelement;
DAPL_HASH_ELEM *lastelement;
lastelement = NULL;
for (curelement = element; curelement;
lastelement = curelement,
curelement = curelement->next_element) {
if (curelement->key == key) {
if (p_datum) {
*p_datum = curelement->datum;
}
if (lastelement) {
/*
* curelement was malloc'd; free it
*/
lastelement->next_element =
curelement->next_element;
dapl_os_free((void *) curelement,
sizeof (DAPL_HASH_ELEM));
} else {
/*
* curelement is static list head
*/
DAPL_HASH_ELEM *n = curelement->next_element;
if (n) {
/*
* If there is a next element, copy its
* contents into the head and free the
* original next element.
*/
curelement->key = n->key;
curelement->datum = n->datum;
curelement->next_element =
n->next_element;
dapl_os_free((void *) n,
sizeof (DAPL_HASH_ELEM));
} else {
curelement->datum = NO_DATUM_VALUE;
}
}
break;
}
}
return (curelement != NULL ? DAT_TRUE : DAT_FALSE);
}
/*
*
* External Functions
*
*/
/*
* Create a new hash table with at least 'table_size' hash buckets.
*/
DAT_RETURN
dapls_hash_create(
IN DAT_COUNT table_size,
IN DAT_BOOLEAN locking_required,
OUT DAPL_HASH_TABLE **pp_table)
{
DAPL_HASH_TABLE *p_table;
DAT_COUNT table_length = table_size * sizeof (DAPL_HASH_ELEM);
DAT_RETURN dat_status;
DAT_COUNT i;
dapl_os_assert(pp_table);
dat_status = DAT_SUCCESS;
/* Allocate hash table */
p_table = dapl_os_alloc(sizeof (DAPL_HASH_TABLE));
if (NULL == p_table) {
dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
DAT_RESOURCE_MEMORY);
goto bail;
}
/* Init hash table, allocate and init and buckets */
(void) dapl_os_memzero(p_table, sizeof (DAPL_HASH_TABLE));
p_table->tbl_size = table_size;
p_table->table = (DAPL_HASH_ELEM *)dapl_os_alloc(table_length);
if (NULL == p_table->table) {
dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
DAT_RESOURCE_MEMORY);
goto bail;
}
/* Init the lock anyways */
dapl_os_lock_init(&p_table->lock);
p_table->locking_required = locking_required;
for (i = 0; i < table_size; i++) {
p_table->table[i].datum = NO_DATUM_VALUE;
p_table->table[i].key = 0;
p_table->table[i].next_element = 0;
}
*pp_table = p_table;
bail:
return (dat_status);
}
/*
* Destroy a hash table
*/
DAT_RETURN
dapls_hash_free(
IN DAPL_HASH_TABLE *p_table)
{
dapl_os_assert(p_table && p_table->table);
dapl_os_lock_destroy(&p_table->lock);
dapl_os_free(p_table->table,
sizeof (DAPL_HASH_ELEM) * p_table->tbl_size);
dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
return (DAT_SUCCESS);
}
/*
* Returns the number of elements stored in the table
*/
DAT_RETURN
dapls_hash_size(
IN DAPL_HASH_TABLE *p_table,
OUT DAT_COUNT *p_size)
{
dapl_os_assert(p_table && p_size);
*p_size = p_table->num_entries;
return (DAT_SUCCESS);
}
/*
* Inserts the specified data into the table with the given key.
* Duplicates are not expected, and return in error, having done nothing.
*/
DAT_RETURN
dapls_hash_insert(
IN DAPL_HASH_TABLE *p_table,
IN DAPL_HASH_KEY key,
IN DAPL_HASH_DATA data)
{
DAT_RETURN dat_status;
dapl_os_assert(p_table);
dat_status = DAT_SUCCESS;
if (p_table->locking_required) {
dapl_os_lock(&p_table->lock);
}
if (!dapli_hash_add(p_table, key, data, DAT_FALSE, NULL)) {
dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
DAT_RESOURCE_MEMORY);
}
if (p_table->locking_required) {
dapl_os_unlock(&p_table->lock);
}
return (dat_status);
}
/*
* Searches for the given key. If found,
* DAT_SUCCESS is returned and the associated
* data is returned in the DAPL_HASH_DATA
* pointer if that pointer is not NULL.
*/
DAT_RETURN
dapls_hash_search(
IN DAPL_HASH_TABLE *p_table,
IN DAPL_HASH_KEY key,
OUT DAPL_HASH_DATA *p_data)
{
DAT_RETURN dat_status;
void *olddatum;
DAPL_HASH_ELEM *found;
dapl_os_assert(p_table);
dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
if (p_table->locking_required) {
dapl_os_lock(&p_table->lock);
DAPL_HASHLOOKUP(p_table, key, olddatum, found);
dapl_os_unlock(&p_table->lock);
} else {
DAPL_HASHLOOKUP(p_table, key, olddatum, found);
}
if (found) {
if (p_data) {
*p_data = olddatum;
}
dat_status = DAT_SUCCESS;
}
return (dat_status);
}
DAT_RETURN
dapls_hash_remove(
IN DAPL_HASH_TABLE *p_table,
IN DAPL_HASH_KEY key,
OUT DAPL_HASH_DATA *p_data)
{
DAT_RETURN dat_status;
DAPL_HASH_KEY hashValue;
dapl_os_assert(p_table);
dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
if (p_table->num_entries == 0) {
dapl_dbg_log(DAPL_DBG_TYPE_ERR,
"dapls_hash_remove () called on empty hash table!\n");
return (dat_status);
}
hashValue = DAPL_DOHASH(key, p_table->tbl_size);
if (p_table->locking_required) {
dapl_os_lock(&p_table->lock);
}
if (dapl_hash_delete_element(&p_table->table[hashValue], key, p_data)) {
p_table->num_entries--;
dat_status = DAT_SUCCESS;
}
if (p_table->locking_required) {
dapl_os_unlock(&p_table->lock);
}
return (dat_status);
}
/*
* Iterates through the entire hash table return one element at a time.
* Note: this is not a threadsafe routine and hence consumers that
* rely on the hash-tables internal locking are not allowed to use this.
*/
DAT_RETURN
dapls_hash_iterate(
IN DAPL_HASH_TABLE *p_table,
IN DAPL_HASH_ITERATOR op,
OUT DAPL_HASH_DATA *p_data)
{
DAPL_HASH_ELEM *curr;
dapl_os_assert(p_table);
/*
* sorry iterate is supported only for consumers that do their
* own locking
*/
if (p_table->locking_required) {
return (DAT_ERROR(DAT_INVALID_PARAMETER, 0));
}
if (op == DAPL_HASH_ITERATE_INIT) {
/* the hash table is empty */
if (p_table->num_entries == 0) {
*p_data = NULL;
return (DAT_SUCCESS);
}
/* find the first bucket with valid data */
p_table->iterator_bucket = 0;
while (p_table->iterator_bucket < p_table->tbl_size) {
curr = &p_table->table[p_table->iterator_bucket];
if (NO_DATUM(curr->datum)) {
/* empty bucket - move on */
p_table->iterator_bucket++;
} else {
break;
}
}
/* should not be empty if num_entries is non-zero */
dapl_os_assert(!NO_DATUM(curr->datum));
if (p_table->iterator_bucket == p_table->tbl_size) {
p_table->iterator = NULL;
} else {
p_table->iterator = curr;
}
} else {
dapl_os_assert(op == DAPL_HASH_ITERATE_NEXT);
}
/* iterator points to the element to be returned */
if (p_table->iterator == NULL) {
/* nothing more left in the hashtable */
*p_data = NULL;
return (DAT_SUCCESS);
}
dapl_dbg_log(DAPL_DBG_TYPE_EP,
"dapls_hash_iterate: entry found=(%p), bucket(%d)\n",
p_table->iterator, p_table->iterator_bucket);
*p_data = p_table->iterator->datum;
curr = p_table->iterator;
/* re-position iterator to point to the next valid element */
if (curr->next_element != NULL) { /* found the next element */
p_table->iterator = curr->next_element;
dapl_os_assert(!NO_DATUM(p_table->iterator->datum));
} else {
p_table->iterator = NULL;
/*
* We are here means we've hit the end of the current bucket,
* so start searching for next bucket with a valid entry -
* we only need to look at the head of the bucket
*/
p_table->iterator_bucket++;
while (p_table->iterator_bucket < p_table->tbl_size) {
curr = &p_table->table[p_table->iterator_bucket];
if (NO_DATUM(curr->datum)) {
p_table->iterator_bucket++;
} else {
p_table->iterator = curr;
break;
}
}
}
return (DAT_SUCCESS);
}