hash.h File Reference

#include <limits.h>
#include <stdint.h>

Go to the source code of this file.

Data Structures
struct	hnode_t
	Hash chain node structure. More...
struct	hash_t
struct	hscan_t

Macros
#define	HASHCOUNT_T_MAX   ULONG_MAX
#define	HASH_VAL_T_MAX   UINT32_MAX
#define	HASH_VAL_T_BIT   ((int) hash_val_t_bit)

Typedefs
typedef unsigned long	hashcount_t
typedef uint32_t	hash_val_t
typedef struct hnode_t	hnode_t
	Hash chain node structure.
typedef int(*	hash_comp_t) (const void *, const void *)
typedef hash_val_t(*	hash_fun_t) (const void *)
typedef hnode_t *(*	hnode_alloc_t) (void *)
typedef void(*	hnode_free_t) (hnode_t *, void *)
typedef struct hash_t	hash_t
typedef struct hscan_t	hscan_t

Variables
int	hash_val_t_bit

Macro Definition Documentation

HASH_VAL_T_BIT

#define HASH_VAL_T_BIT   ((int) hash_val_t_bit)

HASH_VAL_T_MAX

#define HASH_VAL_T_MAX   UINT32_MAX

HASHCOUNT_T_MAX

#define HASHCOUNT_T_MAX   ULONG_MAX

Typedef Documentation

hash_comp_t

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

The comparison function pointer 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.

hash_fun_t

typedef hash_val_t(* hash_fun_t) (const void *)

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.

hash_t

typedef struct hash_t hash_t

This is the hash table control structure. It keeps track of information about a hash table, as well as the 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. This member keeps track of the size of the hash table—that is, the number of chain pointers.
3. The count member maintains the number of elements that are presently in the hash table.
4. The maximum count 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.
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. 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.
7. This is the a pointer to the hash table's comparison function. The function is set once at initialization or creation time.
8. Pointer to the table's hashing function, set once at creation or initialization time.
9. 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.
10. 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.

hash_val_t

typedef uint32_t hash_val_t

hashcount_t

typedef unsigned long hashcount_t

hnode_alloc_t

typedef hnode_t *(* hnode_alloc_t) (void *)

hnode_free_t

typedef void(* hnode_free_t) (hnode_t *, void *)

hnode_t

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. 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.
4. 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.
5. 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.

hscan_t

typedef struct hscan_t hscan_t

Hash scanner structure, 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().

Variable Documentation

hash_val_t_bit

int hash_val_t_bit

extern