Hashing
[libbu (utility functions)]

Collaboration diagram for Hashing:

Files
file	hash.c
	An implimentation of hash tables.
Data Structures
struct	bu_hash_entry
struct	bu_hash_tbl
struct	bu_hash_record
Defines
#define	BU_HASH_TBL_MAGIC   0x48415348
#define	BU_HASH_RECORD_MAGIC   0x68617368
#define	BU_HASH_ENTRY_MAGIC   0x48454E54
#define	BU_CK_HASH_TBL(_hp)   BU_CKMAG( _hp, BU_HASH_TBL_MAGIC, "bu_hash_tbl" )
#define	BU_CK_HASH_RECORD(_rp)   BU_CKMAG( _rp, BU_HASH_RECORD_MAGIC, "bu_hash_record" )
#define	BU_CK_HASH_ENTRY(_ep)   BU_CKMAG( _ep, BU_HASH_ENTRY_MAGIC, "bu_hash_entry" )
Functions
unsigned long	bu_hash (unsigned char *str, int len)
bu_hash_tbl *	bu_create_hash_tbl (unsigned long tbl_size)
	Create an empty hash table The input is the number of desired hash bins. This number will be rounded up to the nearest power of two.
bu_hash_entry *	bu_find_hash_entry (struct bu_hash_tbl *hsh_tbl, unsigned char *key, int key_len, struct bu_hash_entry **prev, unsigned long *index)
	Find the hash table entry corresponding to the provided key.
void	bu_set_hash_value (struct bu_hash_entry *hsh_entry, unsigned char *value)
	Set the value for a hash table entry.
unsigned char *	bu_get_hash_value (struct bu_hash_entry *hsh_entry)
unsigned char *	bu_get_hash_key (struct bu_hash_entry *hsh_entry)
bu_hash_entry *	bu_hash_add_entry (struct bu_hash_tbl *hsh_tbl, unsigned char *key, int key_len, int *new_entry)
void	bu_hash_tbl_pr (struct bu_hash_tbl *hsh_tbl, char *str)
	Print the specified hash table to stderr. (Note that the keys and values are printed as pointers).
void	bu_hash_tbl_free (struct bu_hash_tbl *hsh_tbl)
	Free all the memory associated with the specified hash table. Note that the keys are freed (they are copies), but the "values" are not freed. (The values are merely pointers).
bu_hash_entry *	bu_hash_tbl_first (struct bu_hash_tbl *hsh_tbl, struct bu_hash_record *rec)
	get the "first" entry in a hash table
bu_hash_entry *	bu_hash_tbl_next (struct bu_hash_record *rec)

---

Define Documentation

#define BU_HASH_TBL_MAGIC   0x48415348

Definition at line 2723 of file bu.h.

#define BU_HASH_RECORD_MAGIC   0x68617368

Definition at line 2724 of file bu.h. Referenced by bu_hash_tbl_first().

#define BU_HASH_ENTRY_MAGIC   0x48454E54

Definition at line 2725 of file bu.h. Referenced by bu_hash_add_entry().

#define BU_CK_HASH_TBL (  _hp   )     BU_CKMAG( _hp, BU_HASH_TBL_MAGIC, "bu_hash_tbl" )

Definition at line 2726 of file bu.h. Referenced by bu_find_hash_entry(), bu_hash_add_entry(), bu_hash_tbl_first(), bu_hash_tbl_free(), bu_hash_tbl_next(), and bu_hash_tbl_pr().

#define BU_CK_HASH_RECORD (  _rp   )     BU_CKMAG( _rp, BU_HASH_RECORD_MAGIC, "bu_hash_record" )

Definition at line 2727 of file bu.h. Referenced by bu_hash_tbl_next().

#define BU_CK_HASH_ENTRY (  _ep   )     BU_CKMAG( _ep, BU_HASH_ENTRY_MAGIC, "bu_hash_entry" )

Definition at line 2728 of file bu.h. Referenced by bu_get_hash_key(), bu_get_hash_value(), bu_hash_tbl_free(), bu_hash_tbl_pr(), and bu_set_hash_value().

---

Function Documentation

unsigned long bu_hash (  unsigned char *  str, int  len )

B U _ H A S H the hashing function Definition at line 52 of file hash.c. Referenced by bu_find_hash_entry().

struct bu_hash_tbl * bu_create_hash_tbl (  unsigned long  tbl_size  )

Create an empty hash table The input is the number of desired hash bins. This number will be rounded up to the nearest power of two. B U _ C R E A T E _ H A S H _ T B L Definition at line 74 of file hash.c. References malloc(), bu_hash_tbl::mask, NULL, and bu_hash_tbl::num_lists. Here is the call graph for this function:

struct bu_hash_entry * bu_find_hash_entry (  struct bu_hash_tbl *  hsh_tbl, unsigned char *  key, int  key_len, struct bu_hash_entry **  prev, unsigned long *  index )

Find the hash table entry corresponding to the provided key. B U _ F I N D _ H A S H _ E N T R Y Parameters: [in]  hsh_tbl  - The hash table to look in [in]  key  - the key to look for [in]  key_len  - the length of the key in bytes Output: Parameters: [out]  prev  - the previous hash table entry (non-null for entries that not the first in hash bin) [out]  index  - the index of the hash bin for this key Returns: the hash table entry corresponding to the provided key, or NULL if not found Definition at line 134 of file hash.c. References BU_CK_HASH_TBL, bu_hash(), bu_hash_entry::key, bu_hash_entry::key_len, bu_hash_tbl::lists, bu_hash_tbl::mask, bu_hash_entry::next, NULL, and bu_hash_tbl::num_lists. Referenced by bu_hash_add_entry(). Here is the call graph for this function:

void bu_set_hash_value (  struct bu_hash_entry *  hsh_entry, unsigned char *  value )

Set the value for a hash table entry. B U _ S E T _ H A S H _ V A L U E Note that this is just a pointer copy, the hash table does not maintain its own copy of this value. Definition at line 206 of file hash.c. References BU_CK_HASH_ENTRY, and bu_hash_entry::value.

unsigned char * bu_get_hash_value (  struct bu_hash_entry *  hsh_entry  )

B U _ G E T _ H A S H _ V A L U E get the value pointer stored for the specified hash table entry Definition at line 219 of file hash.c. References BU_CK_HASH_ENTRY, and bu_hash_entry::value.

unsigned char * bu_get_hash_key (  struct bu_hash_entry *  hsh_entry  )

B U _ G E T _ H A S H _ K E Y get the key pointer stored for the specified hash table entry Definition at line 231 of file hash.c. References BU_CK_HASH_ENTRY, and bu_hash_entry::key.

struct bu_hash_entry * bu_hash_add_entry (  struct bu_hash_tbl *  hsh_tbl, unsigned char *  key, int  key_len, int *  new )

B U _ H A S H _ A D D _ E N T R Y Add an new entry to a hash table Parameters: [in]  hsh_tbl  - the hash table to accept thye new entry [in]  key  - the key (any byte string) [in]  key_len  - the number of bytes in the key [out]  new  - a flag, non-zero indicates that a new entry was created. zero indicates that an entry already exists with the specified key and key length Returns: a hash table entry. If "new" is non-zero, a new, empty entry is returned. if "new" is zero, the returned entry is the one matching the specified key and key_len Definition at line 256 of file hash.c. References BU_CK_HASH_TBL, bu_find_hash_entry(), BU_HASH_ENTRY_MAGIC, calloc(), index, bu_hash_entry::key, bu_hash_entry::key_len, bu_hash_tbl::lists, bu_hash_entry::magic, malloc(), bu_hash_entry::next, NULL, bu_hash_tbl::num_entries, and bu_hash_entry::value. Here is the call graph for this function:

void bu_hash_tbl_pr (  struct bu_hash_tbl *  hsh_tbl, char *  str )

Print the specified hash table to stderr. (Note that the keys and values are printed as pointers). B U _ H A S H _ T B L _ P R Definition at line 308 of file hash.c. References BU_CK_HASH_ENTRY, BU_CK_HASH_TBL, index, bu_hash_tbl::lists, bu_hash_tbl::num_entries, and bu_hash_tbl::num_lists.

void bu_hash_tbl_free (  struct bu_hash_tbl *  hsh_tbl  )

Free all the memory associated with the specified hash table. Note that the keys are freed (they are copies), but the "values" are not freed. (The values are merely pointers). B U _ H A S H _ T B L _ F R E E Definition at line 336 of file hash.c. References BU_CK_HASH_ENTRY, BU_CK_HASH_TBL, free(), index, bu_hash_tbl::lists, bu_hash_entry::next, and bu_hash_tbl::num_lists. Here is the call graph for this function:

struct bu_hash_entry * bu_hash_tbl_first (  struct bu_hash_tbl *  hsh_tbl, struct bu_hash_record *  rec )

get the "first" entry in a hash table B U _ H A S H _ T B L _ F I R S T Parameters: [in]  hsh_tbl  - the hash table of interest [in]  rec  - an empty "bu_hash_record" structure for use by this routine and "bu_hash_tbl_next" Returns: the first non-null entry in the hash table, or NULL if there are no entries (Note that the order of enties is not likely to have any significance) Definition at line 381 of file hash.c. References BU_CK_HASH_TBL, BU_HASH_RECORD_MAGIC, bu_hash_record::hsh_entry, bu_hash_record::index, bu_hash_tbl::lists, bu_hash_record::magic, NULL, bu_hash_tbl::num_entries, bu_hash_tbl::num_lists, and bu_hash_record::tbl.

struct bu_hash_entry * bu_hash_tbl_next (  struct bu_hash_record *  rec  )

B U _ H A S H _ T B L _ N E X T get the "next" entry in a hash table input: rec - the "bu_hash_record" structure that was passed to "bu_hash_tbl_first" return: the "next" non-null hash entry in this hash table Definition at line 419 of file hash.c. References BU_CK_HASH_RECORD, BU_CK_HASH_TBL, bu_hash_record::hsh_entry, bu_hash_record::index, bu_hash_tbl::lists, bu_hash_entry::next, NULL, bu_hash_tbl::num_lists, and bu_hash_record::tbl.

---