Hash Table

A Hash Table data structure definition and functions. Also see Hash Table Example.

Summary

s_hash_table_new	Create a new hash table.
s_hash_table_delete	Delete a hash table.
s_hash_table_add	Add an element to a hash table.
s_hash_element_unlink	Unlink the given hash table element from the hash table.
s_hash_element_delete	Delete the given hash table element.
s_hash_table_size	Get the number of elements in the hash table.
s_hash_table_resize	Resize the hash table to a specific size.
s_hash_table_find	Find a hash table element in the hash table.
s_hash_table_first	Get the first hash table element of the given hash table.
s_hash_element_next	Get the next hash table element relative to the given one.
s_hash_element_key	Get the key of the given hash table element.
s_hash_element_key_length	Get the key length (bytes) of the given hash table element.
s_hash_element_get_data	Get the data of the given hash table element.
s_hash_element_set_data	Set the data of the given hash table element.
s_hash_table_stats	Print statistics about the hash table to a buffer that is returned.
s_hash_element_pos	Get the position of the given hash table element in the hash table array.

Definition

typedef struct s_hash_table s_hash_table

Opaque hash table.

The hash table grows automatically, albeit the grow function is slow as elements already in the hash table need to be rehashed. Therefore it is desirable to select the hash table size as optimal as possible during creation with s_hash_table_new.

typedef struct s_hash_element s_hash_element

Opaque hash table element.

The hash table element represents one element in a hash table.

Create/Delete

s_hash_table *s_hash_table_new(s_hash_table_free_fp free_func, size_t size, s_erc *error)

Create a new hash table.

Creates a new hash table and initializes the size of the table to 2 ^size.

Parameters:

• free_func –

  A memory free callback function. Used to free element data from the hash table.

• size –

  The initial size of the table will be 2 ^size.

• error –

  Error code.

Return:

The newly created hash table.

void s_hash_table_delete(s_hash_table *self, s_erc *error)

Delete a hash table.

Delete a hash table and all it’s elements. If the s_hash_table_free_fp is NULL then the elements memory wont be freed.

Parameters:

• self –

  The hash table.

• error –

  Error code.

Function Pointers

typedef void(*s_hash_table_free_fp)(void *key, void *data, s_erc *error)

The s_hash_table element free function callback typedef.

A pointer to a function that frees the dynamically allocated memory of a hash table element.

Parameters:

• key –

  Hash table element key to free.

• data –

  Hash table element data to free.

• error –

  Error code.

Adding/Removing

void s_hash_table_add(s_hash_table *self, void *key, size_t key_length, void *data, s_erc *error)

Add an element to a hash table.

Hash table element keys must be unique.

Parameters:

• self –

  The hash table.

• key –

  The key of the element to add to the hash table.

• key_length –

  The length of the key.

• data –

  The data to associate with the key.

• error –

  Error code.

Note:

The newly created hash table element takes hold of the memory of the key.

void s_hash_element_unlink(s_hash_element *self, s_erc *error)

Unlink the given hash table element from the hash table.

Parameters:

• self –

  The hash table element.

• error –

  Error code.

Note:

The caller must take care of the memory of the key and data of the given hash table element before unlinking, otherwise the references to the key and data are lost as the element is freed with this call.

void s_hash_element_delete(s_hash_element *self, s_erc *error)

Delete the given hash table element.

If the s_hash_table_free_fp function pointer is NULL then the memory of the key and data of the element will not be freed.

Parameters:

• self –

  The hash table element.

• error –

  Error code.

Size/Resize

uint32 s_hash_table_size(const s_hash_table *self, s_erc *error)

Get the number of elements in the hash table.

Parameters:

• self –

  The hash table.

• error –

  Error code.

Return:

Returns the number of elements of the hash table.

void s_hash_table_resize(s_hash_table *self, sint32 size, s_erc *error)

Resize the hash table to a specific size.

The hash table can be resized to any size as long as it can still contain all the existing elements in it. There are a few outcomes based on the given size and the elements contained in the hash table:

Parameters:

• self –

  The hash table.

• size –

  Required size of the table (2 ^size).

• error –

  Error code.

Note:

This function is relatively slow, as rehashing a table takes time. However, if there are no elements in the list it is quite fast.

Accessing

const s_hash_element *s_hash_table_find(const s_hash_table *self, const void *key, size_t key_length, s_erc *error)

Find a hash table element in the hash table.

Parameters:

• self –

  The hash table.

• key –

  The key to look for.

• key_length –

  The length of the key in bytes.

• error –

  Error code.

Return:

Pointer to the hash table element or NULL if the given key does not have an associated hash table element.

const s_hash_element *s_hash_table_first(const s_hash_table *self, s_erc *error)

Get the first hash table element of the given hash table.

Parameters:

• self –

  The hash table.

• error –

  Error code.

Return:

Pointer to the first hash table element, or NULL if not found or the hash table is empty.

const s_hash_element *s_hash_element_next(const s_hash_element *self, s_erc *error)

Get the next hash table element relative to the given one.

Parameters:

• self –

  The hash table element.

• error –

  Error code.

Return:

Pointer to next hash table element relative to given one, or NULL if none.

Element Key/Data

const void *s_hash_element_key(const s_hash_element *self, s_erc *error)

Get the key of the given hash table element.

Parameters:

• self –

  The hash table element.

• error –

  Error code.

Return:

The key of the given hash table element.

size_t s_hash_element_key_length(const s_hash_element *self, s_erc *error)

Get the key length (bytes) of the given hash table element.

Parameters:

• self –

  The hash table element.

• error –

  Error code.

Return:

The key length (bytes) of the given hash table element.

const void *s_hash_element_get_data(const s_hash_element *self, s_erc *error)

Get the data of the given hash table element.

Parameters:

• self –

  The hash table element.

• error –

  Error code.

Return:

The data of the given hash table element.

void s_hash_element_set_data(s_hash_element *self, void *data, s_erc *error)

Set the data of the given hash table element.

Parameters:

• self –

  The hash table element.

• data –

  The data to set the given hash element data to.

• error –

  Error code.

Note:

If the hash element has some data it will be lost.

Miscellaneous

char *s_hash_table_stats(const s_hash_table *self, s_erc *error)

Print statistics about the hash table to a buffer that is returned.

Parameters:

• self –

  The hash table.

• error –

  Error code.

Return:

Character buffer with Hash Table stats in.

Note:

Prints out information as follows:

 s_hash_table_stats:
 items 0: <number of buckets with 0 items> buckets
 items 1: <number of buckets with 1 item> buckets
 ...

 buckets: <number of buckets> items: <number of items> existing: <x>

( x is the average length of the list when you look for an item that exists. When the item does not exists, the average length is (number of items)/(number of buckets).)

The caller is responsible for the memory of the returned buffer.

uint32 s_hash_element_pos(const s_hash_element *self, s_erc *error)

Get the position of the given hash table element in the hash table array.

Parameters:

• self –

  The hash table element.

• error –

  Error code.

Return:

The position of the given hash table element in the hash table array.