hash.h File Reference

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

#include <limits.h>
#include "rnr/rnrconfig.h"

Go to the source code of this file.

Classes
struct	hnode_t
	Hash chain node structure. More...
struct	hash_t
	Hash table control structure. More...
struct	hscan_t
	Hash scanner structure. More...

Macros
#define	HASH_IMPLEMENTATION
	Hash implementation (original source had different hash configs, we have one)
#define	HASHCOUNT_T_MAX   ULONG_MAX
	Maximum maximum hash table size.
#define	HASH_VAL_T_MAX   ULONG_MAX
	Maximum hashed value (a Mersenne number 2^N-1)
#define	HASH_MIN_SIZE   ((hashcount_t)4)
	Minimum and initial size of hash table. More...
#define	HASH_MAX_SIZE   ((hashcount_t)HASHCOUNT_T_MAX)
	Maximum size of hash table.
#define	hash_isfull(H)   ((H)->count == (H)->maxcount)
	Returns true if table is full, false otherwise. More...
#define	hash_isempty(H)   ((H)->count == 0)
	Returns true if table is empty, false otherwise. More...
#define	hash_count(H)   ((H)->count)
	Returns number of entires in hash table. More...
#define	hash_size(H)   ((H)->nchains)
	Returns size of hash table. More...
#define	hnode_get(N)   ((N)->data)
	Get hash node user data. More...
#define	hnode_getkey(N)   ((N)->key)
	Get hash node hash key. More...
#define	hnode_put(N, V)   ((N)->data = (V))
	Pet hash node user data. More...

Typedefs
typedef unsigned long	hashcount_t
	maximum hash table size type
typedef unsigned long	hash_val_t
	hashed value return type
typedef struct hnode_t	hnode_t
	Hash chain node structure. More...
typedef int(*	hash_comp_t) (const void *key1, const void *key2)
	User comparison function override type. More...
typedef hash_val_t(*	hash_fun_t) (const void *key)
	User hashing function type. More...
typedef void(*	hnode_data_free_t) (void *key, void *data)
	User node data deallocator function. More...
typedef struct hash_t	hash_t
	Hash table control structure. More...
typedef struct hscan_t	hscan_t
	Hash scanner structure. More...

Functions
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...
int	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...

Detailed Description

General purpose hash data and function declarations.

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

See also

example_hash under "Related Pages" for an example usage of hashing.

Package

RoadNarrows Robotics Common Library 1

Library

librnr

File

rnr/hash.h

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

License

MIT

EULA

See the README and EULA files for any copyright and licensing information.

—

---

Original Source Comment Block

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

* Hash Table Data Type
* Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
*
* Free Software License:
*
* All rights are reserved by the author, with the following exceptions:
* Permission is granted to freely reproduce and distribute this software,
* possibly in exchange for a fee, provided that this copyright notice appears
* intact. Permission is also granted to adapt this software to produce
* derivative works, as long as the modified versions carry this copyright
* notice and additional notices stating that the work has been modified.
* The copyright extends to translations of this work into other languages,
* including machine languages. 
* 

---

Definition in file hash.h.

Macro Definition Documentation

#define hash_count

(

H

)

((H)->count)

Returns number of entires in hash table.

Parameters

H	Hash table.

Definition at line 391 of file hash.h.

Referenced by force_grow(), force_shrink(), and main().

#define hash_isempty

(

H

)

((H)->count == 0)

Returns true if table is empty, false otherwise.

Parameters

H	Hash table.

Definition at line 385 of file hash.h.

Referenced by hash_table_delete().

#define hash_isfull

(

H

)

((H)->count == (H)->maxcount)

Returns true if table is full, false otherwise.

Parameters

H	Hash table.

Definition at line 379 of file hash.h.

#define HASH_MIN_SIZE   ((hashcount_t)4)

Minimum and initial size of hash table.

Warning

Must be a power of two.

Definition at line 104 of file hash.h.

Referenced by init_hash_sizes().

#define hash_size

(

H

)

((H)->nchains)

Returns size of hash table.

Parameters

H	Hash table.

Definition at line 397 of file hash.h.

Referenced by force_grow(), force_shrink(), and main().

#define hnode_get

(

N

)

((N)->data)

Get hash node user data.

Parameters

N	Hash node.

Definition at line 403 of file hash.h.

Referenced by ConfigDbPrint(), ConfigGetStr(), ConfigSectionAddPair(), ConfigSectionGet(), ConfigSectionPrint(), force_shrink(), main(), and test_hash().

#define hnode_getkey

(

N

)

((N)->key)

Get hash node hash key.

Parameters

N	Hash node.

Definition at line 409 of file hash.h.

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

#define hnode_put	(		N,
			V
	)		((N)->data = (V))

Pet hash node user data.

Parameters

N	Hash node.
V	User data.

Definition at line 416 of file hash.h.

Referenced by ConfigSectionAddPair().

Typedef Documentation

typedef int(* hash_comp_t) (const void *key1, const void *key2)

User comparison function override type.

A comparison function takes two keys and produces a value of -1 if the left key is less than the right key, a value of 0 if the keys are equal, and a value of 1 if the left key is greater than the right key.

Default:

Built-in wrapper to strcmp().

Parameters

key1	Key 1
key2	Key 2

See also

hash_table_create()

Definition at line 177 of file hash.h.

typedef hash_val_t(* hash_fun_t) (const void *key)

User hashing function type.

The hashing function performs some computation on a key and produces an integral value of type hash_val_t based on that key. For best results, the function should have a good randomness properties in all significant bits over the set of keys that are being inserted into a given hash table. In particular, the most significant bits of hash_val_t are most significant to the hash module. Only as the hash table expands are less significant bits examined. Thus a function that has good distribution in its upper bits but not lower is preferrable to one that has poor distribution in the upper bits but not the lower ones.

Default:

Built-in hashing function that hashes over string keys.

Parameters

key	Key to hash.

See also

hash_table_create()

Definition at line 199 of file hash.h.

typedef struct hash_t hash_t

Hash table control structure.

The hash table keeps track of information about a hash table, as well as the actual hash table itself.

Notes:

1. Pointer to the hash table proper. The table is an array of pointers to hash nodes (of type hnode_t). If the table is empty, every element of this table is a null pointer. A non-null entry points to the first element of a chain of nodes.
2. Minimum and initial size of the hash table (must be a power of two).
3. Maximum hash table size (must be >= minsize). The maximum size is the greatest number of nodes that can populate this table. If the table contains this many nodes, no more can be inserted, and the hash_isfull() function returns true.
4. The low mark is a minimum population threshold, measured as a number of nodes. If the table population drops below this value, a table shrinkage will occur. Only dynamic tables are subject to this reduction. No table will shrink beneath a certain absolute minimum number of nodes.
5. The high mark is a population threshold, measured as a number of nodes, which, if exceeded, will trigger a table expansion. Only dynamic hash tables are subject to this expansion.
6. This member keeps track of the size of the hash table—that is, the number of chain pointers.
7. The current hash table mask. If the size of the hash table is 2^N, this value has its low N bits set to 1, and the others clear. It is used to select bits from the result of the hashing function to compute an index into the table.
8. The count member maintains the number of elements that are presently in the hash table.
9. This is the a pointer to the hash table's comparison function. The function is set once at initialization or creation time.
10. Pointer to the table's hashing function, set once at creation or initialization time.
12. User data deallocator. Default is NULL. (i.e. nothing is done to data when hash node is deleted).
13. A flag which indicates whether the table is to be dynamically resized. It is set to 1 in dynamically allocated tables, 0 in tables that are statically allocated.

typedef void(* hnode_data_free_t) (void *key, void *data)

User node data deallocator function.

Default:

NULL (no user key and data are deallocated).

Parameters

key	Pointer to node key data.
key	Pointer to node user data.

See also

hash_table_create()

Definition at line 212 of file hash.h.

typedef struct hnode_t hnode_t

Hash chain node structure.

Notes:

1. This preprocessing directive is for debugging purposes. The effect is that if the preprocessor symbol KAZLIB_OPAQUE_DEBUG is defined prior to the inclusion of this header, then the structure shall be declared as having the single member int OPAQUE. This way, any attempts by the client code to violate the principles of information hiding (by accessing the structure directly) can be diagnosed at translation time. However, note the resulting compiled unit is not suitable for linking.
2. This is a pointer to the next node in the chain. In the last node of a chain, this pointer is null.
3. This is a back-pointer to the primary pointer to this node. The primary pointer is the previous node's next pointer to this node. If there is no previous node, the primary pointer is the pointer that resides in the hash table. This back-pointer lets us handle deletions easily without searching the chain.
4. The key is a pointer to some user supplied data that contains a unique identifier for each hash node in a given table. The interpretation of the data is up to the user. When creating or initializing a hash table, the user must supply a pointer to a function for comparing two keys, and a pointer to a function for hashing a key into a numeric value.
5. The value is a user-supplied pointer to void which may refer to any data object. It is not interpreted in any way by the hashing module.
6. The hashed key is stored in each node so that we don't have to rehash each key when the table must grow or shrink.

typedef struct hscan_t hscan_t

Hash scanner structure.

The scanner is used for traversals of the data structure.

Notes:

1. Pointer to the hash table that is being traversed.
2. Reference to the current chain in the table being traversed (the chain that contains the next node that shall be retrieved).
3. Pointer to the node that will be retrieved by the subsequent call to hash_scan_next().

Function Documentation

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

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

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