9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * CDDL HEADER START
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
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 *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * or http://www.opensolaris.org/os/licensing.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * See the License for the specific language governing permissions
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * and limitations under the License.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
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 *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * CDDL HEADER END
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Copyright (c) 2002-2003, Network Appliance, Inc. All rights reserved.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Use is subject to license terms.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * MODULE: dapl_hash.c
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * PURPOSE: Hash Table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Description:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Provides a generic hash table with chaining.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * $Id: dapl_hash.c,v 1.10 2003/07/11 18:42:17 hobie16 Exp $
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor#include "dapl_hash.h"
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Structures
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * A hash table element
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylortypedef struct DAPL_HASH_ELEM
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor struct DAPL_HASH_ELEM *next_element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_KEY key;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor void *datum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor} DAPL_HASH_ELEM;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * The hash table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylorstruct dapl_hash_table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor unsigned long num_entries;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor unsigned long tbl_size;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *table;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_BOOLEAN locking_required; /* internal locking reqd */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_OS_LOCK lock;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor unsigned long iterator_bucket;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *iterator;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
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 */
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_tbl_total; /* total in table */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor uint64_t hash_chn_max; /* longest chain */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor uint64_t hash_chn_total; /* total non-0 lenghts */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor};
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Defines
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/* The hash function */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor#define DAPL_DOHASH(key, hashsize) ((uint64_t)((key) % (hashsize)))
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/* datum value in empty table slots (use 0UL or ~0UL as appropriate) */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor#define NO_DATUM_VALUE ((void *) 0UL)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor#define NO_DATUM(value) ((value) == NO_DATUM_VALUE)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
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 { \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *element = \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor &((p_table)->table)[DAPL_DOHASH(in_key, (p_table)->tbl_size)]; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NO_DATUM(element->datum)) { \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (bucket_head) = (void *)0; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else if (element->key == (DAPL_HASH_KEY) (in_key)) { \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (out_datum) = element->datum; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (bucket_head) = (void *)element; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else if (element->next_element) { \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapli_hash_rehash(element, \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (in_key), \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (void **)&(out_datum), \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (DAPL_HASH_ELEM **)&(bucket_head)); \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else { \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (bucket_head) = (void *)0; \
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }\
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Internal Functions
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Rehash the key (used by add and lookup functions)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Inputs: element element to rehash key
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * key, datum datum for key head
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * head head for list
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylorstatic void
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapli_hash_rehash(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *element,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_KEY key,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor void **datum,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM ** head)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * assume we looked at the contents of element already,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * and start with the next element.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(element->next_element);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(!NO_DATUM(element->datum));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *head = element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*CONSTCOND*/
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor while (1) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor element = element->next_element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (!element) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor break;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (element->key == key) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *datum = element->datum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *head = 0;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Add a new key to the hash table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Inputs:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * table, key and datum to be added
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * allow_dup - DAT_TRUE if dups are allowed
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Outputs:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * report_dup - should you care to know
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Returns:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * DAT_TRUE on success
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylorstatic DAT_BOOLEAN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapli_hash_add(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_TABLEP p_table,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_KEY key,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor void *datum,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_BOOLEAN allow_dup,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_BOOLEAN *report_dup)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor void *olddatum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_KEY hashValue;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *found;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_BOOLEAN status = DAT_FALSE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor unsigned int chain_len = 0;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (report_dup) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor (*report_dup) = DAT_FALSE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NO_DATUM(datum)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Reserved value used for datum
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_dbg_log(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_DBG_TYPE_ERR,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapli_hash_add () called with magic NO_DATA value "
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "(%p) used as datum!\n", datum);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_FALSE);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASHLOOKUP(p_table, key, olddatum, found);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (found) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * key exists already
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (report_dup) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *report_dup = DAT_TRUE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (!allow_dup) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_dbg_log(DAPL_DBG_TYPE_ERR,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapli_hash_add () called with duplicate key "
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "(" F64x ")\n", key);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_FALSE);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor hashValue = DAPL_DOHASH(key, p_table->tbl_size);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NO_DATUM(p_table->table[hashValue].datum)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Empty head - just fill it in
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table[hashValue].key = key;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table[hashValue].datum = datum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table[hashValue].next_element = 0;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->num_entries++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor status = DAT_TRUE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *newelement = (DAPL_HASH_ELEM *)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_alloc(sizeof (DAPL_HASH_ELEM));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Add an element to the end of the chain
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (newelement) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *lastelement;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor newelement->key = key;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor newelement->datum = datum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor newelement->next_element = 0;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor for (lastelement = &p_table->table[hashValue];
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor lastelement->next_element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor lastelement = lastelement->next_element) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* Walk to the end of the chain */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor chain_len++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor lastelement->next_element = newelement;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->num_entries++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor status = DAT_TRUE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* allocation failed - should not happen */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor status = DAT_FALSE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Tally up our counters. chain_len is one less than current chain
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * length.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor chain_len++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->hash_tbl_inserts++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->hash_tbl_total += p_table->num_entries;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->hash_chn_total += chain_len;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->num_entries > p_table->hash_tbl_max) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->hash_tbl_max = p_table->num_entries;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (chain_len > p_table->hash_chn_max) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->hash_chn_max = chain_len;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (status);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Remove element from hash bucket
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Inputs:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * element, key to be deleted
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Returns:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * DAT_TRUE on success
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylorstatic DAT_BOOLEAN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapl_hash_delete_element(DAPL_HASH_ELEM * element,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_KEY key,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_DATA *p_datum)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *curelement;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *lastelement;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor lastelement = NULL;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor for (curelement = element; curelement;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor lastelement = curelement,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curelement = curelement->next_element) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (curelement->key == key) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_datum) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *p_datum = curelement->datum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (lastelement) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * curelement was malloc'd; free it
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor lastelement->next_element =
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curelement->next_element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_free((void *) curelement,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor sizeof (DAPL_HASH_ELEM));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * curelement is static list head
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *n = curelement->next_element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (n) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
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 */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curelement->key = n->key;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curelement->datum = n->datum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curelement->next_element =
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor n->next_element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_free((void *) n,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor sizeof (DAPL_HASH_ELEM));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curelement->datum = NO_DATUM_VALUE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor break;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (curelement != NULL ? DAT_TRUE : DAT_FALSE);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * External Functions
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Create a new hash table with at least 'table_size' hash buckets.
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill TaylorDAT_RETURN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapls_hash_create(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAT_COUNT table_size,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAT_BOOLEAN locking_required,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor OUT DAPL_HASH_TABLE **pp_table)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_TABLE *p_table;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_COUNT table_length = table_size * sizeof (DAPL_HASH_ELEM);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_RETURN dat_status;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_COUNT i;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(pp_table);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_SUCCESS;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* Allocate hash table */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table = dapl_os_alloc(sizeof (DAPL_HASH_TABLE));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NULL == p_table) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_RESOURCE_MEMORY);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor goto bail;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
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->tbl_size = table_size;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table = (DAPL_HASH_ELEM *)dapl_os_alloc(table_length);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NULL == p_table->table) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_RESOURCE_MEMORY);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor goto bail;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* Init the lock anyways */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_lock_init(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->locking_required = locking_required;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor for (i = 0; i < table_size; i++) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table[i].datum = NO_DATUM_VALUE;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table[i].key = 0;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->table[i].next_element = 0;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *pp_table = p_table;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylorbail:
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (dat_status);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Destroy a hash table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill TaylorDAT_RETURN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapls_hash_free(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_TABLE *p_table)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(p_table && p_table->table);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_lock_destroy(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_free(p_table->table,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor sizeof (DAPL_HASH_ELEM) * p_table->tbl_size);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_free(p_table, sizeof (DAPL_HASH_TABLE));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_SUCCESS);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * Returns the number of elements stored in the table
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill TaylorDAT_RETURN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapls_hash_size(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_TABLE *p_table,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor OUT DAT_COUNT *p_size)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(p_table && p_size);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *p_size = p_table->num_entries;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_SUCCESS);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
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 */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill TaylorDAT_RETURN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapls_hash_insert(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_TABLE *p_table,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_KEY key,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_DATA data)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_RETURN dat_status;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(p_table);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_SUCCESS;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->locking_required) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_lock(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (!dapli_hash_add(p_table, key, data, DAT_FALSE, NULL)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INSUFFICIENT_RESOURCES,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_RESOURCE_MEMORY);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->locking_required) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_unlock(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (dat_status);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
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 */
9e39c5ba00a55fa05777cc94b148296af305e135Bill TaylorDAT_RETURN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapls_hash_search(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_TABLE *p_table,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_KEY key,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor OUT DAPL_HASH_DATA *p_data)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_RETURN dat_status;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor void *olddatum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *found;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(p_table);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->locking_required) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_lock(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASHLOOKUP(p_table, key, olddatum, found);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_unlock(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASHLOOKUP(p_table, key, olddatum, found);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (found) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_data) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *p_data = olddatum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_SUCCESS;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (dat_status);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill TaylorDAT_RETURN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapls_hash_remove(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_TABLE *p_table,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_KEY key,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor OUT DAPL_HASH_DATA *p_data)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAT_RETURN dat_status;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_KEY hashValue;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(p_table);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_ERROR(DAT_INVALID_PARAMETER, 0);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->num_entries == 0) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_dbg_log(DAPL_DBG_TYPE_ERR,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapls_hash_remove () called on empty hash table!\n");
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (dat_status);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor hashValue = DAPL_DOHASH(key, p_table->tbl_size);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->locking_required) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_lock(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (dapl_hash_delete_element(&p_table->table[hashValue], key, p_data)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->num_entries--;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dat_status = DAT_SUCCESS;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->locking_required) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_unlock(&p_table->lock);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (dat_status);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor/*
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 */
9e39c5ba00a55fa05777cc94b148296af305e135Bill TaylorDAT_RETURN
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylordapls_hash_iterate(
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_TABLE *p_table,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor IN DAPL_HASH_ITERATOR op,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor OUT DAPL_HASH_DATA *p_data)
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor{
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor DAPL_HASH_ELEM *curr;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(p_table);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * sorry iterate is supported only for consumers that do their
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor * own locking
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->locking_required) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_ERROR(DAT_INVALID_PARAMETER, 0));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (op == DAPL_HASH_ITERATE_INIT) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* the hash table is empty */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->num_entries == 0) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *p_data = NULL;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_SUCCESS);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* find the first bucket with valid data */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator_bucket = 0;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor while (p_table->iterator_bucket < p_table->tbl_size) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curr = &p_table->table[p_table->iterator_bucket];
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NO_DATUM(curr->datum)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* empty bucket - move on */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator_bucket++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor break;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* should not be empty if num_entries is non-zero */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(!NO_DATUM(curr->datum));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->iterator_bucket == p_table->tbl_size) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator = NULL;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator = curr;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(op == DAPL_HASH_ITERATE_NEXT);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* iterator points to the element to be returned */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (p_table->iterator == NULL) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /* nothing more left in the hashtable */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *p_data = NULL;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_SUCCESS);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_dbg_log(DAPL_DBG_TYPE_EP,
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor "dapls_hash_iterate: entry found=(%p), bucket(%d)\n",
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator, p_table->iterator_bucket);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor *p_data = p_table->iterator->datum;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curr = p_table->iterator;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor
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 p_table->iterator = curr->next_element;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor dapl_os_assert(!NO_DATUM(p_table->iterator->datum));
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator = NULL;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor /*
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 */
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator_bucket++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor while (p_table->iterator_bucket < p_table->tbl_size) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor curr = &p_table->table[p_table->iterator_bucket];
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor if (NO_DATUM(curr->datum)) {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator_bucket++;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor } else {
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor p_table->iterator = curr;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor break;
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor }
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor return (DAT_SUCCESS);
9e39c5ba00a55fa05777cc94b148296af305e135Bill Taylor}