Table Of Contents

Previous topic

Doubly Linked List

Next topic

Buffer

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.

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.