Hash Tables

An implementation of hash tables. TODO - need much better discussion here. Key points: More...

Collaboration diagram for Hash Tables:

Files
file	hash.h

Typedefs
typedef struct bu_hash_entry	bu_hash_entry
typedef struct bu_hash_tbl	bu_hash_tbl

Functions
bu_hash_tbl *	bu_hash_create (unsigned long tbl_size)
void	bu_hash_destroy (bu_hash_tbl *t)
void *	bu_hash_get (const bu_hash_tbl *t, const uint8_t *key, size_t key_len)
int	bu_hash_set (bu_hash_tbl *t, const uint8_t *key, size_t key_len, void *val)
void	bu_hash_rm (bu_hash_tbl *t, const uint8_t *key, size_t key_len)
bu_hash_entry *	bu_hash_next (bu_hash_tbl *t, bu_hash_entry *p)
int	bu_hash_key (bu_hash_entry *e, uint8_t **key, size_t *key_len)
void *	bu_hash_value (bu_hash_entry *e, void *nval)

Detailed Description

An implementation of hash tables. TODO - need much better discussion here. Key points:

1. Keys are copied to the table and do not need to be maintained by the user
2. All keys, regardless of original type, are handled as byte arrays. Need examples of using strings and pointers as has keys
3. Void pointers sorted as values are not copies - the application must keep the data pointed to by the pointers intact and not rely on the table.
4. Performance is not currently a focus of bu_hash - it is not currently suitable for applications where high performance is critical.

Typedef Documentation

bu_hash_entry

typedef struct bu_hash_entry bu_hash_entry

Definition at line 46 of file hash.h.

bu_hash_tbl

typedef struct bu_hash_tbl bu_hash_tbl

Definition at line 47 of file hash.h.

Function Documentation

bu_hash_create()

bu_hash_tbl * bu_hash_create

(

unsigned long

tbl_size

)

Create and initialize a hash table. The input is the number of desired hash bins. This number will be rounded up to the nearest power of two, or a minimal size if tbl_size is smaller than the internal minimum bin count.

bu_hash_destroy()

void bu_hash_destroy

(

bu_hash_tbl *

t

)

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_get()

void * bu_hash_get	(	const bu_hash_tbl *	t,
		const uint8_t *	key,
		size_t	key_len
	)

Get the value stored in the hash table entry corresponding to the provided key

Parameters

[in]	t	- The hash table to look in
[in]	key	- the key to look for
[in]	key_len	- the length of the key in bytes

Returns

the void pointer stored in the hash table entry corresponding to key, or NULL if no entry corresponding to key exists.

bu_hash_set()

int bu_hash_set	(	bu_hash_tbl *	t,
		const uint8_t *	key,
		size_t	key_len,
		void *	val
	)

Set the value stored in the hash table entry corresponding to the provided key to val, or if no entry corresponding to the provided key exists create a new entry associating the key and value. The key value is stored in the hash entry, but the table does not maintain its own copy of val - ensuring the value pointer remains valid is the responsibility of the caller.

Null or zero length keys are not supported. The table will also not store a key/value combination where the value is NULL, but for random access with bu_hash_get get this won't matter because the return value for a key not in the table is NULL - i.e. the return will be the same as if the key/value pair had actually been added. The only use case where this property is observable is when a user iterates over the whole contents of a hash table - in that situation a key, NULL entry might be expected, but will not be present.

Parameters

[in]	t	- The hash table to look in
[in]	key	- the key to look for
[in]	key_len	- the length of the key in bytes
[in]	val	- the value to be associated with key

Returns

1 if a new entry is created, 0 if an existing value was updated, -1 on error.

bu_hash_rm()

void bu_hash_rm	(	bu_hash_tbl *	t,
		const uint8_t *	key,
		size_t	key_len
	)

Remove the hash table entry associated with key from the table.

Parameters

[in]	t	- The hash table to look in
[in]	key	- the key to look for
[in]	key_len	- the length of the key in bytes

bu_hash_next()

bu_hash_entry * bu_hash_next	(	bu_hash_tbl *	t,
		bu_hash_entry *	p
	)

Supports iteration of all the contents in a hash table.

Parameters

[in]	t	- The hash table to look in
[in]	p	- the previous entry in the iteration

This example prints all values in a hash table:

void print_vals(struct bu_hash_tbl *t) {
  struct bu_hash_entry *e = bu_hash_next(t, NULL);
  while (e) {
    bu_log("Value: %p\n", bu_hash_value(e, NULL));
    e = bu_hash_next(t, e);
  }
}

Returns

Either first entry (if p is NULL) or next entry (if p is NON-null). Returns NULL when p is last entry in table.

bu_hash_key()

int bu_hash_key	(	bu_hash_entry *	e,
		uint8_t **	key,
		size_t *	key_len
	)

Supports iteration of all the contents in a hash table.

Parameters

[in]	e	- The hash table to look in
[out]	key	- the entry's key
[out]	key_len	- the length of the entry's key

Returns

Returns 0 on success, 1 on failure.

bu_hash_value()

void * bu_hash_value	(	bu_hash_entry *	e,
		void *	nval
	)

Extracts or updates the void pointer value for a bu_hash_entry. If nval is not NULL the entry will be updated.

Parameters

[in]	e	- The hash table to look in
[in]	nval	- The new void pointer to assign to the entry's value slot, or NULL if no assignment is to be made.

Returns

Returns the hash entry's value pointer, or NULL on error.