9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * CDDL HEADER START
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * The contents of this file are subject to the terms of the
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Common Development and Distribution License (the "License").
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * You may not use this file except in compliance with the License.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * See the License for the specific language governing permissions
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * and limitations under the License.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * When distributing Covered Code, include this CDDL HEADER in each
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * If applicable, add the following below this CDDL HEADER, with the
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * fields enclosed by brackets "[]" replaced with your own identifying
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * information: Portions Copyright [yyyy] [name of copyright owner]
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * CDDL HEADER END
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Copyright (c) 2002-2003, Network Appliance, Inc. All rights reserved.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Use is subject to license terms.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * PURPOSE: Hash Table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Description:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Provides a generic hash table with chaining.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * $Id: dapl_hash.c,v 1.10 2003/07/11 18:42:17 hobie16 Exp $
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Structures
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * A hash table element
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * The hash table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_BOOLEAN locking_required; /* internal locking reqd */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * statistics - we tally on insert operations, counting
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * the number of entries in the whole hash table, as
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * well as the length of chains we walk to insert. This
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * ignores empty buckets, giving us data on overall table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * occupancy, as well as max/average chain length for
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * the buckets used. If our hash function results in
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * hot buckets, this will show it.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor uint64_t hash_tbl_inserts; /* total inserts ops */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor uint64_t hash_tbl_max; /* max in entire table */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor uint64_t hash_chn_total; /* total non-0 lenghts */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/* The hash function */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor#define DAPL_DOHASH(key, hashsize) ((uint64_t)((key) % (hashsize)))
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/* datum value in empty table slots (use 0UL or ~0UL as appropriate) */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor#define NO_DATUM(value) ((value) == NO_DATUM_VALUE)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/* Lookup macro (which falls back to function to rehash) */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor#define DAPL_HASHLOOKUP(p_table, in_key, out_datum, bucket_head) \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor &((p_table)->table)[DAPL_DOHASH(in_key, (p_table)->tbl_size)]; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (bucket_head) = (void *)0; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else if (element->key == (DAPL_HASH_KEY) (in_key)) { \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (void **)&(out_datum), \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (bucket_head) = (void *)0; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Internal Functions
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Rehash the key (used by add and lookup functions)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Inputs: element element to rehash key
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * key, datum datum for key head
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * head head for list
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * assume we looked at the contents of element already,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * and start with the next element.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*CONSTCOND*/
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Add a new key to the hash table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * table, key and datum to be added
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * allow_dup - DAT_TRUE if dups are allowed
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * report_dup - should you care to know
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * DAT_TRUE on success
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Reserved value used for datum
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapli_hash_add () called with magic NO_DATA value "
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * key exists already
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapli_hash_add () called with duplicate key "
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor hashValue = DAPL_DOHASH(key, p_table->tbl_size);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NO_DATUM(p_table->table[hashValue].datum)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Empty head - just fill it in
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Add an element to the end of the chain
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* Walk to the end of the chain */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* allocation failed - should not happen */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Tally up our counters. chain_len is one less than current chain
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->hash_tbl_total += p_table->num_entries;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->num_entries > p_table->hash_tbl_max) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Remove element from hash bucket
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * element, key to be deleted
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * DAT_TRUE on success
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapl_hash_delete_element(DAPL_HASH_ELEM * element,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * curelement was malloc'd; free it
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * curelement is static list head
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * If there is a next element, copy its
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * contents into the head and free the
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * original next element.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (curelement != NULL ? DAT_TRUE : DAT_FALSE);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * External Functions
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Create a new hash table with at least 'table_size' hash buckets.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_COUNT table_length = table_size * sizeof (DAPL_HASH_ELEM);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* Allocate hash table */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table = dapl_os_alloc(sizeof (DAPL_HASH_TABLE));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* Init hash table, allocate and init and buckets */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (void) dapl_os_memzero(p_table, sizeof (DAPL_HASH_TABLE));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table = (DAPL_HASH_ELEM *)dapl_os_alloc(table_length);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* Init the lock anyways */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor for (i = 0; i < table_size; i++) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Destroy a hash table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Returns the number of elements stored in the table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Inserts the specified data into the table with the given key.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Duplicates are not expected, and return in error, having done nothing.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (!dapli_hash_add(p_table, key, data, DAT_FALSE, NULL)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Searches for the given key. If found,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * DAT_SUCCESS is returned and the associated
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * data is returned in the DAPL_HASH_DATA
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * pointer if that pointer is not NULL.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapls_hash_remove () called on empty hash table!\n");
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor hashValue = DAPL_DOHASH(key, p_table->tbl_size);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (dapl_hash_delete_element(&p_table->table[hashValue], key, p_data)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Iterates through the entire hash table return one element at a time.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Note: this is not a threadsafe routine and hence consumers that
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * rely on the hash-tables internal locking are not allowed to use this.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * sorry iterate is supported only for consumers that do their
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * own locking
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* the hash table is empty */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* find the first bucket with valid data */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor while (p_table->iterator_bucket < p_table->tbl_size) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curr = &p_table->table[p_table->iterator_bucket];
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* empty bucket - move on */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* should not be empty if num_entries is non-zero */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->iterator_bucket == p_table->tbl_size) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* iterator points to the element to be returned */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* nothing more left in the hashtable */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapls_hash_iterate: entry found=(%p), bucket(%d)\n",
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* re-position iterator to point to the next valid element */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (curr->next_element != NULL) { /* found the next element */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(!NO_DATUM(p_table->iterator->datum));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * We are here means we've hit the end of the current bucket,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * so start searching for next bucket with a valid entry -
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * we only need to look at the head of the bucket
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor while (p_table->iterator_bucket < p_table->tbl_size) {