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);
}