hash.c File Reference

General purpose hash data and function declarations. More...

#include <stdlib.h>
#include <stddef.h>
#include <assert.h>
#include <string.h>
#include "rnr/rnrconfig.h"
#include "rnr/new.h"
#include "rnr/log.h"
#include "rnr/hash.h"

Go to the source code of this file.

Functions
static void	compute_bits ()
	Compute the number of bits in the hash_val_t type. More...
static bool_t	is_power_of_two (hash_val_t arg)
	Verify whether the given argument is a power of two. More...
static hash_val_t	compute_mask (hashcount_t size)
	Compute a mask for a given table size. More...
static void	init_hash_sizes (hash_t *hash, hashcount_t minsize, hashcount_t maxsize)
	Initialize the table size values. More...
static hash_val_t	hash_fun_default (const void *key)
	Default hashing function over null-terminated string keys. More...
static int	hash_comp_default (const void *key1, const void *key2)
	Default hash key comparator function of null-terminated key strings. More...
static void	clear_table (hash_t *hash)
	Initialize the table of pointers to null. More...
static void	grow_table (hash_t *hash)
	Double the size of a dynamic table. More...
static void	shrink_table (hash_t *hash)
	Cut a dynamic table size in half. More...
hash_t *	hash_table_create (bool_t isdynamic, hashcount_t minsize, hashcount_t maxsize, hash_comp_t compfun, hash_fun_t hashfun, hnode_data_free_t freedatafun)
	Create a dynamic hash table. More...
void	hash_table_destroy (hash_t *hash)
	Delete the hash table, all of its entries, and all of the user data. More...
void	hash_table_delete (hash_t *hash)
	Frees a dynamic hash table structure. More...
hash_t *	hash_table_init (hash_t *hash, hashcount_t minsize, hashcount_t maxsize, hash_comp_t compfun, hash_fun_t hashfun, hnode_data_free_t freedatafun, hnode_t **table, hashcount_t nchains)
	Initialize a user supplied hash table. More...
bool_t	hash_table_verify (hash_t *hash)
	Verify hash table consistency. More...
void	hash_scan_begin (hscan_t *scan, hash_t *hash)
	Reset the hash scanner (iterator). More...
hnode_t *	hash_scan_next (hscan_t *scan)
	Retrieve the next node from the hash table. More...
void	hash_node_insert (hash_t *hash, hnode_t *node, void *key)
	Insert a node into the hash table. More...
hnode_t *	hash_node_unlink (hash_t *hash, hnode_t *node)
	Unlink the given node from the hash table. More...
hnode_t *	hash_node_fast_unlink (hash_t *hash, hnode_t *node)
	Fast version to unlink the given node from the hash table. More...
void	hash_node_delete (hash_t *hash, hnode_t *node)
	Unlink and delete a hash node from the hash table. More...
hnode_t *	hash_lookup (hash_t *hash, const void *key)
	Find a node in the hash table and return a pointer to it. More...
bool_t	hash_insert (hash_t *hash, void *key, void *data)
	Insert user data with the given key into the hash table. More...
bool_t	hash_delete (hash_t *hash, void *key)
	Unlink and delete a hash node with the given key from the hash table. More...
void	hash_set_self_verify (bool_t selfverify)
	Enable (disable) automatic self-checks during hash table modification operatations. More...
hnode_t *	hnode_create (void *data)
	Create a hash table node dynamically and assign it the given data. More...
hnode_t *	hnode_init (hnode_t *node, void *data)
	Initialize a client-supplied hash node. More...
void	hnode_destroy (hnode_t *node, hnode_data_free_t freedatafun)
	Hash node and user data deallocator. More...
void	hnode_delete (hnode_t *node)
	Destroy a dynamically allocated node. More...

Variables
static int	hash_val_t_bit = 0
	Number of bits in hashed value. Must be a power of 2.
static bool_t	hash_self_verify = false
	Do [not] perform auto-verification after hash table operations.

Detailed Description

General purpose hash data and function declarations.

LastChangedDate

2010-03-24 10:19:36 -0600 (Wed, 24 Mar 2010)

Rev

307

This file has been modified from the original source (see below).

Exceptons map to assert() calls that terminate the calling application.

Todo:

Convert the assert() error handling to appropriate return codes and librnr error handling.

Author

Robin Knight (robin.nosp@m..kni.nosp@m.ght@r.nosp@m.oadn.nosp@m.arrow.nosp@m.s.co.nosp@m.m)

Copyright

© 2005-2018. RoadNarrows LLC..
http://www.roadnarrows.com
All Rights Reserved

---

Original Source and Copyright:

Original Author:

Kaz Kylheku (kaz@a.nosp@m.shi..nosp@m.footp.nosp@m.rint.nosp@m.s.net)

Original Copyright:

(C) 1997

Original Header:

See "Original Source Header EULA" in source file.

---

Definition in file hash.c.

Function Documentation

static void clear_table ( hash_t *  hash )

static

Initialize the table of pointers to null.

Parameters

hash	Hash table.

Definition at line 307 of file hash.c.

References hash_t::nchains, NULL, and hash_t::table.

Referenced by hash_table_create(), and hash_table_init().

{
  hash_val_t i;

  for(i=0; i<hash->nchains; i++)
  {
    hash->table[i] = NULL;
  }
}

static void compute_bits ( )

static

Compute the number of bits in the hash_val_t type.

We know that hash_val_t is an unsigned integral type. Thus the highest value it can hold is a Mersenne number (power of two, less one). We initialize a hash_val_t object with this value and then shift bits out one by one while counting.

Notes & Steps:

1. HASH_VAL_T_MAX is a Mersenne number—one that is one less than a power of two. This means that its binary representation consists of all one bits, and hence ``val'' is initialized to all one bits.
2. We reset the bit count to zero in case this function is invoked more than once.
3. While bits remain in val, we increment the bit count and shift it to the right, replacing the topmost bit by zero.

Definition at line 141 of file hash.c.

References hash_val_t_bit, and HASH_VAL_T_MAX.

Referenced by hash_table_create(), and hash_table_init().

{
  hash_val_t val  = HASH_VAL_T_MAX;  // Steps 1
  int bits        = 0;

  // Steps 3
  while(val)
  {
    bits++;
    val >>= 1;
  }

  hash_val_t_bit = bits;
}

static hash_val_t compute_mask ( hashcount_t  size )

static

Compute a mask for a given table size.

Parameters

size	Table size.

Returns

Shift amount.

Definition at line 185 of file hash.c.

References is_power_of_two().

Referenced by hash_table_create(), and hash_table_init().

{
  hash_val_t mask = size;

  assert(is_power_of_two(size));
  assert(size >= 2);

  mask /= 2;

  while( (mask & 0x01) == 0 )
  {
    mask |= (mask >> 1);
  }

  return mask;
}

static void grow_table ( hash_t *  hash )

static

Double the size of a dynamic table.

This works as follows:

Each chain splits into two adjacent chains. The shift amount increases by one, exposing an additional bit of each hashed key. For each node in the original chain, the value of this newly exposed bit will decide which of the two new chains will receive the node: if the bit is 1, the chain with the higher index will have the node, otherwise the lower chain will receive the node. In this manner, the hash table will continue to function exactly as before without having to rehash any of the keys.

Notes & Steps:

1. Overflow check.
2. The new number of chains is twice the old number of chains.
3. The new mask is one bit wider than the previous, revealing a new bit in all hashed keys.
4. Allocate a new table of chain pointers that is twice as large as the previous one.
5. If the reallocation was successful, we perform the rest of the growth algorithm, otherwise we do nothing.
6. The exposed_bit variable holds a mask with which each hashed key can be AND-ed to test the value of its newly exposed bit.
7. Loop over the lower half of the table, which, at first, holds all of the chains.
8. Each chain from the original table must be split into two chains. The nodes of each chain are examined in turn. The ones whose key value's newly exposed bit is 1 are removed from the chain and put into newchain (Steps 9 through 14). After this separation, the new chain is assigned into its appropriate place in the upper half of the table (Step 15).
9. Since we have relocated the table of pointers, we have to fix the back-reference from the first node of each non-empty chain so it properly refers to the moved pointer.
10. We loop over the even chain looking for any nodes whose exposed bit is set. Such nodes are removed from the lower-half chain and put into its upper-half sister.
11. Before moving the node to the other chain, we remember what the next node is so we can coninue the loop. We have to do this because we will be overwriting the node's next pointer when we insert it to its new home.
12. The next node's back pointer must be updated to skip to the previous node.
13. The deleted node's back pointer must be updated to refer to the next node.
14. We insert the node at the beginning of the new chain.
15. Place the new chain into an upper-half slot.
16. We have finished dealing with the chains and nodes. We now update the various bookeeping fields of the hash structure.

Parameters

hash	Hash table.

Exceptions

Table Overflow	Reached system limits.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 388 of file hash.c.

References _TPTR, _VARFMT, hash_self_verify, hash_table_verify(), hash_t::highmark, hnode_t::hkey, LOGDIAG4, LOGDIAG4CALL, hash_t::lowmark, hash_t::mask, hash_t::nchains, new_overs(), hnode_t::next, NULL, hnode_t::pself, and hash_t::table.

Referenced by hash_node_insert().

{
  hnode_t     **newtable;
  size_t        size;

  LOGDIAG4CALL(_TPTR(hash));

  // Step 1
  assert(2 * hash->nchains > hash->nchains);

  // Step 4
  size = sizeof(hnode_t *) * hash->nchains;
  newtable = new_overs(hash->table, size, size *2);

  // Step 5
  if( newtable )
  {
    // Step 3
    hash_val_t mask = (hash->mask << 1) | 1;

    // Step 6
    hash_val_t exposed_bit = mask ^ hash->mask;

    hash_val_t chain;

    assert(mask != hash->mask);

    // Step 7
    for(chain = 0; chain < hash->nchains; chain++)
    {
      // Step 8
      hnode_t *hptr = newtable[chain];
      hnode_t *newchain = NULL;

      // Step 9
      if(hptr)
      {
        hptr->pself = &newtable[chain];
      }

      // Step 10
      while(hptr)
      {
        if((hptr->hkey & exposed_bit))
        {
          // Step 11
          hnode_t *next = hptr->next;

          // Step 12
          if(next)
          {
            next->pself = hptr->pself;
          }

          // Step 13
          *hptr->pself = next;

          // Step 14
          hptr->next = newchain;
          if(newchain)
          {
            newchain->pself = &hptr->next;
          }
          newchain = hptr;
          hptr->pself = &newchain;
          hptr = next;
        }
        else
        {
          hptr = hptr->next;
        }
      }
      // Step 15
      newtable[chain + hash->nchains] = newchain;
      if(newchain)
      {
        newchain->pself = &newtable[chain + hash->nchains];
      }
    }

    // Step 16
    hash->table     = newtable;
    hash->mask      = mask;
    hash->nchains  *= 2;
    hash->lowmark  *= 2;
    hash->highmark *= 2;
  }

  LOGDIAG4(_VARFMT(hash->nchains, "%lu") ", " _VARFMT(hash->lowmark, "%lu") ", "
      _VARFMT(hash->highmark, "%lu") ", " _VARFMT(hash->mask, "0x%lx"),
      hash->nchains, hash->lowmark, hash->highmark, hash->mask);

  if( hash_self_verify )
  {
    assert(hash_table_verify(hash));
  }
}

static int hash_comp_default ( const void *  key1, const void *  key2  )

static

Default hash key comparator function of null-terminated key strings.

Parameters

key1	Key string 1.
key2	Key string 2.

Returns

Returns <0, 0, >0 if key1 is lexigraphically less than key2, respectively.

Definition at line 297 of file hash.c.

Referenced by hash_table_create(), and hash_table_init().

{
  return strcmp((const char *)key1, (const char *)key2);
}

bool_t hash_delete	(	hash_t *	hash,
		void *	key
	)

Unlink and delete a hash node with the given key from the hash table.

The user data and key are deallocated as per the any user supplied data free function. The node is then deallocated.

Parameters

hash	Hash table.
key	Hash key.

Returns

Returns true if successful, else returns false.

Exceptions

Not Initialzed	Hashing not initialized.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 1310 of file hash.c.

References hash_t::freenodedata, hash_lookup(), hash_node_unlink(), hnode_destroy(), and NULL.

Referenced by ConfigDelete(), and ConfigSectionDelete().

{
  hnode_t *node;

  if( (node = hash_lookup(hash, key)) != NULL )
  {
    hash_node_unlink(hash, node);
    hnode_destroy(node, hash->freenodedata);
    return true;
  }
  return false;
}

static hash_val_t hash_fun_default ( const void *  key )

static

Default hashing function over null-terminated string keys.

Parameters

key	Null-terminated key string.

Returns

Hashed value.

Definition at line 263 of file hash.c.

Referenced by hash_table_create(), and hash_table_init().

{
  static unsigned long randbox[] =
  {
    0x49848f1bU, 0xe6255dbaU, 0x36da5bdcU, 0x47bf94e9U,
    0x8cbcce22U, 0x559fc06aU, 0xd268f536U, 0xe10af79aU,
    0xc1af4d69U, 0x1d2917b5U, 0xec4c304dU, 0x9ee5016cU,
    0x69232f74U, 0xfead7bb3U, 0xe9089ab6U, 0xf012f6aeU,
  };

  const unsigned char *str  = (const unsigned char *)key;
  hash_val_t           acc  = 0;

  while( *str )
  {
    acc ^= randbox[(*str + acc) & 0xf];
    acc = (acc << 1) | (acc >> 31);
    acc &= 0xffffffffU;
    acc ^= randbox[((*str++ >> 4) + acc) & 0xf];
    acc = (acc << 2) | (acc >> 30);
    acc &= 0xffffffffU;
  }
  return acc;
}

bool_t hash_insert	(	hash_t *	hash,
		void *	key,
		void *	data
	)

Insert user data with the given key into the hash table.

The data and key are attached to new hash node which is automatically allocated and the node is inserted into the hash table.

Parameters

hash	Hash table.
key	Hash key.
data	User data.

Returns

Returns true if successful, else returns false.

Exceptions

Not Initialzed	Hashing not initialized.
Too Big	Reached maximum table size.
Duplicate Key	Node with key already exists.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 1283 of file hash.c.

References hash_node_insert(), and hnode_create().

Referenced by ConfigSectionAddPair(), ConfigSectionNew(), force_grow(), main(), and test_hash().

{
  hnode_t *node = hnode_create(data);

  if (node)
  {
    hash_node_insert(hash, node, key);
    return true;
  }

  return false;
}

hnode_t* hash_lookup	(	hash_t *	hash,
		const void *	key
	)

Find a node in the hash table and return a pointer to it.

Notes & Steps:

1. We hash the key and keep the entire hash value. As an optimization, when we descend down the chain, we can compare hash values first and only if hash values match do we perform a full key comparison.
2. To locate the chain from among 2^N chains, we look at the lower N bits of the hash value by anding them with the current mask.
3. Looping through the chain, we compare the stored hash value inside each node against our computed hash. If they match, then we do a full comparison between the unhashed keys. If these match, we have located the entry.

Parameters

hash	Hash table.
key	Hash key.

Returns

Returns node with key on success, NULL if node not found.

Definition at line 1246 of file hash.c.

References hash_t::compare, hash_t::hash, hnode_t::hkey, hnode_t::key, hash_t::mask, hnode_t::next, NULL, and hash_t::table.

Referenced by ConfigGetStr(), ConfigSectionAddPair(), ConfigSectionDelete(), ConfigSectionGet(), ConfigSectionNew(), hash_delete(), hash_node_fast_unlink(), hash_node_insert(), hash_node_unlink(), and main().

{
  hash_val_t hkey, chain;
  hnode_t *nptr;

  hkey = hash->hash(key);       // Step 1
  chain = hkey & hash->mask;    // Step 2

  // Step 3
  for(nptr = hash->table[chain]; nptr; nptr = nptr->next)
  {
    if(nptr->hkey == hkey && hash->compare(nptr->key, key) == 0)
    {
      return nptr;
    }
  }

  return NULL;
}

void hash_node_delete	(	hash_t *	hash,
		hnode_t *	node
	)

Unlink and delete a hash node from the hash table.

The user data and key are deallocated as per the any user supplied data free function. The node is then deallocated.

Parameters

hash	Hash table.
node	Hash node to delete.

Exceptions

Not Initialzed	Hashing not initialized.
No Key	Hash key not found.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 1217 of file hash.c.

References hash_t::freenodedata, hash_node_unlink(), and hnode_destroy().

Referenced by force_shrink(), and main().

{
  hash_node_unlink(hash, node);
  hnode_destroy(node, hash->freenodedata);
}

hnode_t* hash_node_fast_unlink	(	hash_t *	hash,
		hnode_t *	node
	)

Fast version to unlink the given node from the hash table.

Same as hash_node_unlink() except does not trigger table shrinkage. This call is optimized for hash table scan operations.

See also

hash_node_unlink().

Parameters

hash	Hash table.
node	Node to unlink, typically found by scanning.

Returns

Unlinked node.

Exceptions

Not Initialzed	Hashing not initialized.
No Key	Hash key not found.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 1178 of file hash.c.

References _TPTR, hash_t::count, hash_lookup(), hash_self_verify, hash_table_verify(), hash_val_t_bit, hnode_t::key, LOGDIAG4CALL, hnode_t::next, and hnode_t::pself.

Referenced by hash_table_destroy().

{
  LOGDIAG4CALL(_TPTR(hash), _TPTR(node));

  assert(hash_val_t_bit != 0);
  assert(hash_lookup(hash, node->key) == node);  /* 1 */

  // Step 2 as in hash_node_inlink()
  if (node->next)
  {
    node->next->pself = node->pself;
  }

  // Step 3 as in hash_node_inlink()
  *node->pself = node->next;

  hash->count--;

  if( hash_self_verify )
  {
    assert(hash_table_verify(hash));
  }

  return node;
}

void hash_node_insert	(	hash_t *	hash,
		hnode_t *	node,
		void *	key
	)

Insert a node into the hash table.

Steps & Notes:

1. It's illegal to insert more than the maximum number of nodes. The client should verify that the hash table is not full before attempting an insertion.
2. The same key may not be inserted into a table twice.
3. If the table is dynamic and the load factor is already at >= 2, grow the table.
4. We take the top N bits of the hash value to derive the chain index, where N is the base 2 logarithm of the size of the hash table.

Parameters

hash	Hash table.
node	Node to insert.
key	Hash key.

Exceptions

Not Initialzed	Hashing not initialized.
Too Big	Reached maximum table size.
Duplicate Key	Node with key already exists.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 1063 of file hash.c.

References _TPTR, hash_t::count, hash_t::dynamic, grow_table(), hash_t::hash, hash_lookup(), hash_self_verify, hash_table_verify(), hash_val_t_bit, hash_t::highmark, hnode_t::hkey, hnode_t::key, LOGDIAG4CALL, hash_t::mask, hash_t::maxsize, hnode_t::next, NULL, hnode_t::pself, and hash_t::table.

Referenced by hash_insert().

{
  LOGDIAG4CALL(_TPTR(hash), _TPTR(node), _TPTR(key));

  hash_val_t hkey, chain;

  assert(hash_val_t_bit != 0);
  assert(hash->count < hash->maxsize);      // Step 1
  assert(hash_lookup(hash, key) == NULL);   // Step 2

  // Step 3
  if(hash->dynamic && (hash->count+1) >= hash->highmark)
  {
    grow_table(hash);
  }

  hkey  = hash->hash(key);
  chain = hkey & hash->mask;  // Step 4

  node->key   = key;
  node->hkey  = hkey;
  node->pself = hash->table + chain;
  node->next  = hash->table[chain];
  if (node->next)
  {
    node->next->pself = &node->next;
  }
  hash->table[chain] = node;
  hash->count++;

  if( hash_self_verify )
  {
    assert(hash_table_verify(hash));
  }
}

hnode_t* hash_node_unlink	(	hash_t *	hash,
		hnode_t *	node
	)

Unlink the given node from the hash table.

This is easy, because each node contains a back pointer to the previous node's next pointer.

No data are deleted.

Notes & Steps:

1. The node must belong to this hash table, and its key must not have been tampered with.
2. If there is a next node, then we must update its back pointer to skip this node.
3. We must update the pointer that is pointed at by the back-pointer to skip over the node that is being deleted and instead point to the successor (or to NULL if the node being deleted is the last one).

Parameters

hash	Hash table.
node	Hash node to unlink.

Returns

Unlinked node.

Exceptions

Not Initialzed	Hashing not initialized.
No Key	Hash key not found.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 1128 of file hash.c.

References _TPTR, hash_t::count, hash_t::dynamic, hash_lookup(), hash_self_verify, hash_table_verify(), hash_val_t_bit, hnode_t::key, LOGDIAG4CALL, hash_t::lowmark, hash_t::minsize, hnode_t::next, hnode_t::pself, and shrink_table().

Referenced by hash_delete(), and hash_node_delete().

{
  LOGDIAG4CALL(_TPTR(hash), _TPTR(node));

  assert(hash_val_t_bit != 0);
  assert(hash_lookup(hash, node->key) == node);  // Step 1

  if(hash->dynamic && (hash->count-1) <= hash->lowmark
      && hash->count > hash->minsize)
  {
    shrink_table(hash);
  }

  // Step 2
  if (node->next)
  {
    node->next->pself = node->pself;
  }

  // Step 3
  *node->pself = node->next;

  hash->count--;

  if( hash_self_verify )
  {
    assert(hash_table_verify(hash));
  }

  return node;
}

void hash_scan_begin	(	hscan_t *	scan,
		hash_t *	hash
	)

Reset the hash scanner (iterator).

After this call the next element retrieved by hash_scan_next() shall be the first element on the first non-empty chain.

Notes & Steps:

1. Locate the first non empty chain.
2. If an empty chain is found, remember which one it is and set the next pointer to refer to its first element.
3. Otherwise if a chain is not found, set the next pointer to NULL so that hash_scan_next() shall indicate failure.

Parameters

scan	Hash iterator.
hash	Hash table.

Definition at line 937 of file hash.c.

References hscan_t::chain, hscan_t::hash, hash_t::nchains, hscan_t::next, NULL, and hash_t::table.

Referenced by ConfigDbIterNew(), ConfigDbPrint(), ConfigSectionIterNew(), ConfigSectionPrint(), force_shrink(), hash_table_destroy(), main(), and test_hash().

{
  hash_val_t nchains = hash->nchains;
  hash_val_t chain;

  scan->hash = hash;

  // Step 1
  for(chain = 0; chain < nchains && hash->table[chain] == 0; chain++);

  // Step 2
  if(chain < nchains)
  {
    scan->chain = chain;
    scan->next = hash->table[chain];
  }

  // Step 3
  else
  {
    scan->next = NULL;
  }
}

hnode_t* hash_scan_next

(

hscan_t *

scan

)

Retrieve the next node from the hash table.

The scanner (iterator) updates the pointer for the next invocation of hash_scan_next().

Notes & Steps:

1. Remember the next pointer in a temporary value so that it can be returned.
2. This assertion essentially checks whether the module has been properly initialized. The first point of interaction with the module should be either hash_table_create() or hash_init(), both of which set hash_val_t_bit to a non zero value.
3. If the next pointer we are returning is not NULL, then the user is allowed to call hash_scan_next() again. We prepare the new next pointer for that call right now. That way the user is allowed to delete the node we are about to return, since we will no longer be needing it to locate the next node.
4. If there is a next node in the chain (next->next), then that becomes the new next node, otherwise ...
5. We have exhausted the current chain, and must locate the next subsequent non-empty chain in the table.
6. If a non-empty chain is found, the first element of that chain becomes the new next node. Otherwise there is no new next node and we set the pointer to NULL so that the next time hash_scan_next() is called, a null pointer shall be immediately returned.

Returns

Returns next node on success, NULL if no more nodes.

Exceptions

Not Initialzed

Hashing not initialized.

Definition at line 998 of file hash.c.

References hscan_t::chain, hscan_t::hash, hash_val_t_bit, hash_t::nchains, hnode_t::next, hscan_t::next, NULL, and hash_t::table.

Referenced by ConfigDbPrint(), ConfigIterNext(), ConfigSectionPrint(), force_shrink(), hash_table_destroy(), main(), and test_hash().

{
  hnode_t     *next     = scan->next;    // Step 1
  hash_t      *hash     = scan->hash;
  hash_val_t   chain    = scan->chain + 1;
  hash_val_t   nchains  = hash->nchains;

  assert(hash_val_t_bit != 0);  // Step 2

  // Step 3
  if(next)
  {
    // Step 4
    if(next->next)
    {
      scan->next = next->next;
    }
    else
    {
      // Step 5
      while(chain < nchains && hash->table[chain] == 0)
      {
        chain++;
      }
      // Step 6
      if (chain < nchains)
      {
        scan->chain = chain;
        scan->next = hash->table[chain];
      }
      else
      {
        scan->next = NULL;
      }
    }
  }
  return next;
}

void hash_set_self_verify

(

bool_t

selfverify

)

Enable (disable) automatic self-checks during hash table modification operatations.

Parameters

selfverify

True to enable, false to disable.

See also

hash_table_verify()

Definition at line 1331 of file hash.c.

References hash_self_verify.

Referenced by main(), and test_hash().

{
  hash_self_verify = selfverify;
}

hash_t* hash_table_create	(	bool_t	isdynamic,
		hashcount_t	minsize,
		hashcount_t	maxsize,
		hash_comp_t	compfun,
		hash_fun_t	hashfun,
		hnode_data_free_t	freedatafun
	)

Create a dynamic hash table.

Both the hash table structure and the table itself are dynamically allocated. Furthermore, the table is extendible in that it will automatically grow as its load factor increases beyond a certain threshold.

Notes & Steps:

1. If the number of bits in the hash_val_t type has not been computed yet, we do so here, because this is likely to be the first function that the user calls.
2. Allocate hash table.
3. Initialize hash table sizes. The minsize should be a power of two. The maxsize should be >= minsize. Both values will be adjusted. The high and low marks are always set to be twice the table size and half the table size respectively. When the number of nodes in the table grows beyond the high size (beyond load factor 2), it will double in size to cut the load factor down to about about 1. If the table shrinks down to or beneath load factor 0.5, it will shrink, bringing the load up to about 1. However, the table will never shrink beneath minsize even if it's emptied.
4. Allocate the table of hash chains.
5. Finish initializing the hash structure and the table. 6. This indicates that the table is dynamically allocated and dynamically resized on the fly. A table that has this value set to zero is assumed to be statically allocated and will not be resized.
7. The table of chains must be properly reset to all null pointers. 8. Verify table's correctness, if self-verification is true.

Parameters

isdynamic	The hash table is [not] automatically grow. If set to false, the hash table is initialized t be fixed at minsize and maxsize is ignored.
minsize	Minimum and initial number of hash entries that will be supported.
maxsize	Maximum number of hash entries that will be supported.
compfun	Hash key comparator function. NULL will use the default strcmp() wrapper.
hashfun	Hashing function. NULL will used the default string hashing function.
freedatafun	User key and data deallocator function. NULL will cause no user key or data to be deleted.

Returns

Newly created, empty hash table.

Exceptions

Verification Failed

Only if hash_self_verify enabled.

Definition at line 691 of file hash.c.

References _TBOOL, _TPTR, _TULONG, clear_table(), hash_t::compare, compute_bits(), compute_mask(), hash_t::count, hash_t::dynamic, hash_t::freenodedata, hash_t::hash, hash_comp_default(), hash_fun_default(), hash_self_verify, hash_table_verify(), hash_val_t_bit, hash_t::highmark, init_hash_sizes(), LOGDIAG4, LOGDIAG4CALL, hash_t::lowmark, hash_t::mask, hash_t::maxsize, hash_t::minsize, hash_t::nchains, NEW, and hash_t::table.

Referenced by ConfigDbNew(), ConfigSectionNew(), main(), and test_hash().

{
  hash_t *hash;

  LOGDIAG4CALL(_TBOOL(isdynamic), _TULONG(minsize), _TULONG(maxsize),
      _TPTR(compfun), _TPTR(hashfun), _TPTR(freedatafun));

  // Step 1
  if( hash_val_t_bit == 0 )
  {
    compute_bits();
  }

  // Step 2
  hash = NEW(hash_t);

  // Step 3
  init_hash_sizes(hash, minsize, maxsize);

  // Step 4
  hash->table = (hnode_t **)new(sizeof(hnode_t *) * hash->minsize);

  // Step 5
  hash->nchains       = minsize;
  hash->mask          = compute_mask(hash->nchains);
  hash->count         = 0;
  hash->compare       = compfun ? compfun : hash_comp_default;
  hash->hash          = hashfun ? hashfun : hash_fun_default;
  hash->freenodedata  = freedatafun;

  // Step 6
  hash->dynamic       = isdynamic;

  // Step 7
  clear_table(hash);

  // Step 8
  if( hash_self_verify )
  {
    assert(hash_table_verify(hash));
  }

  LOGDIAG4("min=%lu, max=%lu, high=%lu, low=%lu, nchains=%lu, mask=0x%lx\n",
      hash->minsize, hash->maxsize, hash->highmark,
      hash->lowmark, hash->nchains, hash->mask);

  return hash;
}

void hash_table_delete

(

hash_t *

hash

)

Frees a dynamic hash table structure.

Parameters

hash	Hash table.

Warning

The hash table must be empty.

Exceptions

Not Initialzed	Hashing not initialized.
Not Empty	Hash table not empty.

Definition at line 776 of file hash.c.

References hash_isempty, hash_val_t_bit, and hash_t::table.

Referenced by hash_table_destroy().

{
  assert(hash_val_t_bit != 0);
  assert(hash_isempty(hash));

  delete(hash->table);
  delete(hash);
}

void hash_table_destroy

(

hash_t *

hash

)

Delete the hash table, all of its entries, and all of the user data.

Parameters

hash	Hash table.

Definition at line 750 of file hash.c.

References _TPTR, hash_t::freenodedata, hash_node_fast_unlink(), hash_scan_begin(), hash_scan_next(), hash_table_delete(), hnode_destroy(), and LOGDIAG4CALL.

Referenced by ConfigDbDelete(), ConfigMainHashDeleteCb(), and main().

{
  hscan_t  hs;
  hnode_t *node;

  LOGDIAG4CALL(_TPTR(hash));

  hash_scan_begin(&hs, hash);
  while((node = hash_scan_next(&hs)))
  {
    hash_node_fast_unlink(hash, node);
    hnode_destroy(node, hash->freenodedata);
  }
  hash_table_delete(hash);
}

hash_t* hash_table_init	(	hash_t *	hash,
		hashcount_t	minsize,
		hashcount_t	maxsize,
		hash_comp_t	compfun,
		hash_fun_t	hashfun,
		hnode_data_free_t	freedatafun,
		hnode_t **	table,
		hashcount_t	nchains
	)

Initialize a user supplied hash table.

The user also supplies a table of chains which is assigned to the hash table . The table is static—it will not grow or shrink.

Notes & Steps:

1. Initialize hashing.
2. Assign hash chains. The user supplied array of pointers hopefully contains nchains nodes.
3. Fixed size. 4. We must dynamically compute the mask from the given power of two table size.
5. The user supplied table can't be assumed to contain null pointers, so we reset it here.

Warning

All data in destination hash table is overwritten.

See also

hash_table_create()

Parameters

hash	The destination hash table.
minsize	Minimum and initial number of hash entries that will be supported.
maxsize	Maximum number of hash entries that will be supported.
compfun	Hash key comparator function. NULL will use the default strcmp() wrapper.
hashfun	Hashing function. NULL will used the default string hashing function.
freedatafun	User key and data deallocator function. NULL will cause no user key or data to be deleted.
table	The actual hash chain table to attach.
nchains	Number of nodes in hash chain.

Returns

Hash table.

Exceptions

Bad Parameter	nchain not a power of 2.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 828 of file hash.c.

References _TPTR, _TULONG, clear_table(), hash_t::compare, compute_bits(), compute_mask(), hash_t::count, hash_t::dynamic, hash_t::freenodedata, hash_t::hash, hash_comp_default(), hash_fun_default(), hash_self_verify, hash_table_verify(), hash_val_t_bit, hash_t::highmark, init_hash_sizes(), is_power_of_two(), LOGDIAG4, LOGDIAG4CALL, hash_t::lowmark, hash_t::mask, hash_t::maxsize, hash_t::minsize, hash_t::nchains, and hash_t::table.

{
  LOGDIAG4CALL(_TPTR(hash), _TULONG(minsize), _TULONG(maxsize),
      _TPTR(compfun), _TPTR(hashfun), _TPTR(freedatafun),
      _TPTR(table), _TULONG(nchains));

  // Step 1
  if(hash_val_t_bit == 0)
  {
    compute_bits();
  }

  assert(is_power_of_two(nchains));

  init_hash_sizes(hash, minsize, maxsize);

  // Step 2
  hash->table         = table;
  hash->nchains       = nchains;
  hash->mask          = compute_mask(nchains);  // Step 4
  hash->count         = 0;
  hash->compare       = compfun ? compfun : hash_comp_default;
  hash->hash          = hashfun ? hashfun : hash_fun_default;
  hash->freenodedata  = freedatafun;
  hash->dynamic       = false;    // Step 3

  clear_table(hash);    // Step 5

  if( hash_self_verify )
  {
    assert (hash_table_verify(hash));
  }

  LOGDIAG4("min=%lu, max=%lu, high=%lu, low=%lu, nchains=%lu, mask=0x%lx\n",
      hash->minsize, hash->maxsize, hash->highmark,
      hash->lowmark, hash->nchains, hash->mask);

  return hash;
}

bool_t hash_table_verify

(

hash_t *

hash

)

Verify hash table consistency.

If hash_self_verify enabled (see hash_set_self_verify()), this call is automatically called during hash table modification operations.

Notes & Steps:

1. If the hash table is dynamic, verify whether the high and low expansion/shrinkage thresholds are powers of two. 2. For each chain, verify whether the back pointers are correctly set. Count all nodes in the table, and test each hash value to see whether it is correct for the node's chain.

Returns

Returns true is the table is okay, else returns false.

Definition at line 888 of file hash.c.

References CHKEXPR_PTR, CHKEXPR_ULONG, hash_t::count, hash_t::dynamic, hash_t::highmark, is_power_of_two(), hash_t::lowmark, hash_t::mask, hash_t::nchains, hnode_t::next, and hash_t::table.

Referenced by grow_table(), hash_node_fast_unlink(), hash_node_insert(), hash_node_unlink(), hash_table_create(), hash_table_init(), and shrink_table().

{
  hashcount_t count = 0;
  hash_val_t chain;
  hnode_t **npp;

  // Step 1
  if (hash->dynamic)
  {
    CHKEXPR_ULONG(hash->lowmark, (hash->lowmark < hash->highmark), false);
    CHKEXPR_ULONG(hash->lowmark, is_power_of_two(hash->lowmark), false);
    CHKEXPR_ULONG(hash->highmark, is_power_of_two(hash->highmark), false);
  }

  // Step 2
  for(chain = 0; chain < hash->nchains; chain++)
  {
    for(npp = hash->table + chain; *npp; npp = &(*npp)->next)
    {
      CHKEXPR_PTR(npp, ((*npp)->pself == npp), false);
      CHKEXPR_PTR(npp, (((*npp)->hkey & hash->mask) == chain), false);
      count++;
    }
  }

  CHKEXPR_ULONG(hash->count, (hash->count == count), false);

  return true;
}

hnode_t* hnode_create

(

void *

data

)

Create a hash table node dynamically and assign it the given data.

Parameters

data	User data.

Returns

New hash node.

Definition at line 1343 of file hash.c.

References hnode_t::data, NEW, hnode_t::next, NULL, and hnode_t::pself.

Referenced by hash_insert().

{
  hnode_t *node = NEW(hnode_t);

  node->data  = data;
  node->next  = NULL;
  node->pself = NULL;

  return node;
}

void hnode_delete

(

hnode_t *

node

)

Destroy a dynamically allocated node.

User data and key are not touched.

Parameters

node	Hash node.

Definition at line 1392 of file hash.c.

{
    delete(node);
}

void hnode_destroy	(	hnode_t *	node,
		hnode_data_free_t	freedatafun
	)

Hash node and user data deallocator.

Parameters

node	Node to deallocate.
freedatafun	User key and data deallocator. May be NULL.

Definition at line 1376 of file hash.c.

References hnode_t::data, hnode_t::key, and NULL.

Referenced by hash_delete(), hash_node_delete(), and hash_table_destroy().

{
  if( freedatafun != NULL )
  {
    freedatafun(node->key, node->data);
  }
  delete(node);
}

hnode_t* hnode_init	(	hnode_t *	node,
		void *	data
	)

Initialize a client-supplied hash node.

Parameters

node	Hash node.
data	User data.

Returns

Same hash node.

Definition at line 1362 of file hash.c.

References hnode_t::data, hnode_t::next, NULL, and hnode_t::pself.

{
  node->data  = data;
  node->next  = NULL;
  node->pself = NULL;
  return node;
}

static void init_hash_sizes ( hash_t *  hash, hashcount_t  minsize, hashcount_t  maxsize  )

static

Initialize the table size values.

The minimum size is adjusted to be a power of two and is guaranteed to be at least HASH_MIN_SIZE.

The maximum size adjusted to be >= minsize.

Parameters

hash	Hash table.
minsize	Desired minimum and initial size.
maxsize	Desired maximum size.

Definition at line 215 of file hash.c.

References HASH_MIN_SIZE, hash_t::highmark, LOGDIAG4, hash_t::lowmark, hash_t::maxsize, and hash_t::minsize.

Referenced by hash_table_create(), and hash_table_init().

{
  size_t    numbits, rshift, lshift;

  // number of bits in hashcount_t
  numbits = sizeof(hashcount_t) * 8;

  // round down to the closest power of two value
  for(rshift=0, lshift=0; rshift<numbits; ++rshift)
  {
    if( minsize & 0x01 )
    {
      lshift = rshift;
    }
    minsize >>= 1;
  }
  minsize = lshift>0? (((hashcount_t)(0x01)) << lshift):
                      (hashcount_t)HASH_MIN_SIZE;

  // absolute minimum
  if( minsize < HASH_MIN_SIZE )
  {
    minsize = HASH_MIN_SIZE;
  }

  if( maxsize < minsize )
  {
    maxsize = minsize;
  }

  hash->minsize       = minsize;
  hash->maxsize       = maxsize;
  hash->lowmark       = minsize / 2;
  hash->highmark      = minsize * 2;

  LOGDIAG4("minsize=%lu, maxsize=%lu, lowmark=%lu, highmark=%lu",
      hash->minsize, hash->maxsize, hash->lowmark, hash->highmark);
}

static bool_t is_power_of_two ( hash_val_t  arg )

static

Verify whether the given argument is a power of two.

Parameters

arg	Argument to test.

Returns

Returns true if arg is a power of 2, false otherwise.

Definition at line 163 of file hash.c.

Referenced by compute_mask(), hash_table_init(), and hash_table_verify().

{
  if( arg == 0 )
  {
    return false;
  }

  while( (arg & 0x01) == 0 )
  {
    arg >>= 1;
  }

 return arg == 1? true: false;
}

static void shrink_table ( hash_t *  hash )

static

Cut a dynamic table size in half.

This is done by folding together adjacent chains and populating the lower half of the table with these chains. The chains are simply spliced together. Once this is done, the whole table is reallocated to a smaller object.

Notes & Steps:

1. It is illegal to have a hash table with one slot. This would mean that hash->shift is equal to hash_val_t_bit, an illegal shift value. Also, other things could go wrong, such as hash->lowmark becoming zero.
2. Looping over each adjacent chain of pairs, the lo_chain is set to reference the lower-numbered member of the pair, whereas hi_chain is the index of the higher-numbered one.
3. The intent here is to compute a pointer to the last node of the lower chain into the lo_tail variable. If this chain is empty, lo_tail ends up with a null value.
4. If the lower chain is not empty, we have to merge chains, but only if the upper chain is also not empty. In either case, the lower chain will come first, with the upper one appended to it.
5. The first part of the join is done by having the tail node of the lower chain point to the head node of the upper chain. If the upper chain is empty, this is remains a null pointer.
6. If the upper chain is non-empty, we must do the additional house-keeping task of ensuring that the upper chain's first node's back-pointer references the tail node of the lower chain properly.
7. (defunct) 8. If the low chain is empty, but the high chain is not, then the high chain simply becomes the new chain.
9. Otherwise if both chains are empty, then the merged chain is also empty.
10. All the chain pointers are in the lower half of the table now, so we reallocate it to a smaller object. This, of course, invalidates all pointer-to-pointers which reference into the table from the first node of each chain.
11. Though it's unlikely, the reallocation may fail. In this case we pretend that the table was reallocated to a smaller object.
12. This loop performs the housekeeping task of updating the back pointers from the first node of each chain so that they reference their corresponding table entries.
13. Finally, update the various table parameters to reflect the new size.

Parameters

hash	Hash table.

Exceptions

Table Overflow	Reached system limits.
Verification Failed	Only if hash_self_verify enabled.

Definition at line 545 of file hash.c.

References _TPTR, _VARFMT, hash_self_verify, hash_table_verify(), hash_t::highmark, LOGDIAG4, LOGDIAG4CALL, hash_t::lowmark, hash_t::mask, hash_t::nchains, new_overs(), hnode_t::next, NULL, hnode_t::pself, and hash_t::table.

Referenced by hash_node_unlink().

{
  hashcount_t   chain, nchains;
  size_t        size;
  hnode_t     **newtable, *lo_tail, *lo_chain, *hi_chain;

  LOGDIAG4CALL(_TPTR(hash));

  // Step 1
  assert(hash->nchains >= 2);

  // downsize chains
  nchains = hash->nchains / 2;

  // Step 2
  for(chain = 0; chain < nchains; chain++)
  {
    lo_chain = hash->table[chain];
    hi_chain = hash->table[chain + nchains];

    // Step 3
    for(lo_tail=lo_chain; lo_tail && lo_tail->next; lo_tail=lo_tail->next)
    {
      ;
    }

    // Step 4
    if(lo_chain)
    {
      // Step 5
      lo_tail->next = hi_chain;

      // Step 6
      if(hi_chain)        
      {
        hi_chain->pself = &lo_tail->next;
      }
    }

    // Step 8
    else if(hi_chain)
    {
      hash->table[chain] = hi_chain;
    }

    // Step 9
    else
    {
      hash->table[chain] = NULL;
    }
  }

  // Step 10
  size = sizeof(hnode_t *) * nchains;             // downsized size
  newtable = new_overs(hash->table, size, size);

  // Step 11
  if(newtable)
  {
    hash->table = newtable;
  }

  // Step 12
  for(chain = 0; chain < nchains; chain++)
  {
    if(hash->table[chain])
    {
      hash->table[chain]->pself = &hash->table[chain];
    }
  }

  // Step 13
  hash->mask      >>= 1;
  hash->nchains     = nchains;
  hash->lowmark    /= 2;
  hash->highmark   /= 2;

  LOGDIAG4(_VARFMT(hash->nchains, "%lu") ", " _VARFMT(hash->lowmark, "%lu") ", "
      _VARFMT(hash->highmark, "%lu") ", " _VARFMT(hash->mask, "0x%lx"),
      hash->nchains, hash->lowmark, hash->highmark, hash->mask);

  if( hash_self_verify )
  {
    assert(hash_table_verify(hash));
  }
}