Hash Table

A simple hash table and string hash function.

Author
Stephen Brennan
Date
Created Sunday, 3 August 2014
Copyright
Copyright (c) 2013-2016, Stephen Brennan. Released under the Revised BSD License. See the LICENSE.txt file for details.

Defines

HASH_TABLE_INITIAL_SIZE

An initial amount of rows in the hash table. Something just off of a power of 2.

HASH_TABLE_MAX_LOAD_FACTOR

The maximum load factor that can be allowed in the hash table.

Typedefs

typedef (* HASH_FUNCTION)(DATA toHash)

A hash function declaration.

Return
The hash value
Parameters
  • toHash: The data that will be passed to the hash function.

typedef smb_ht_mark

This mark goes in each table cell.

In order for probing to work properly, you need to be able to tell whether or not a cell is empty because something was deleted out of it, or whether it has always been empty. So, the “GRAVE” mark is a grave stone. When you delete a key from a cell, you mark it with a grave stone. And when you’re searching for a key, you continue when you find a grave marker.

typedef smb_ht_bckt

The bucket of a hash table. Contains key,value pairs, and is a singly linked list.

typedef smb_ht

A hash table data structure.

Enums

enum smb_ht_mark

This mark goes in each table cell.

In order for probing to work properly, you need to be able to tell whether or not a cell is empty because something was deleted out of it, or whether it has always been empty. So, the “GRAVE” mark is a grave stone. When you delete a key from a cell, you mark it with a grave stone. And when you’re searching for a key, you continue when you find a grave marker.

Values:

HT_EMPTY = 0
HT_FULL
HT_GRAVE

Functions

void ht_init(smb_ht * table, HASH_FUNCTION hash_func, DATA_COMPARE equal)

Initialize a hash table in memory already allocated.

Parameters
  • table: A pointer to the table to initialize.
  • hash_func: A hash function for the table.
  • equal: A comparison function for DATA.

smb_ht* ht_create(HASH_FUNCTION hash_func, DATA_COMPARE equal)

Allocate and initialize a hash table.

Return
A pointer to the new hash table.
Parameters
  • hash_func: A function that takes one DATA and returns a hash value generated from it. It should be a good hash function.
  • equal: A comparison function for DATA.

void ht_destroy_act(smb_ht * table, DATA_ACTION deleter)

Free resources used by the hash table, but does not free the pointer itself. Perform an action on the data as it is deleted.

Useful for stack valued hash tables. A deleter must be specified in this function call.

Parameters
  • table: The table to destroy.
  • deleter: The deletion action on the data.

void ht_destroy(smb_ht * table)

Free any resources used by the hash table, but doesn’t free the pointer. Doesn’t perform any actions on the data as it is deleted.

If pointers are contained within the hash table, they are not freed. Use ht_destroy_act() to specify a deletion action on the hash table.

Parameters
  • table: The table to destroy.

void ht_delete_act(smb_ht * table, DATA_ACTION deleter)

Free the hash table and its resources. Perform an action on each data before freeing the table. Useful for freeing pointers stored in the table.

Parameters
  • table: The table to free.
  • deleter: The action to perform on each value in the hash table before deletion.

void ht_delete(smb_ht * table)

Free the hash table and its resources. No pointers contained in the table will be freed.

Parameters
  • table: The table to free.

void ht_insert(smb_ht * table, DATA key, DATA value)

Insert data into the hash table.

Expands the hash table if the load factor is below a threshold. If the key already exists in the table, then the function will overwrite it with the new data provided.

Parameters
  • table: A pointer to the hash table.
  • key: The key to insert.
  • value: The value to insert at the key.

void ht_remove_act(smb_ht * table, DATA key, DATA_ACTION deleter, smb_status * status)

Remove the key, value pair stored in the hash table.

Parameters
  • table: A pointer to the hash table.
  • key: The key to delete.
  • deleter: The action to perform on the value before removing it.
  • status: Status variable.
Exceptions
  • SMB_NOT_FOUND_ERROR: If an item with the given key is not found.

void ht_remove(smb_ht * table, DATA key, smb_status * status)

Remove the key, value pair stored in the hash table.

This function does not call a deleter on the stored data.

Parameters
  • table: A pointer to the hash table.
  • key: The key to delete.
  • status: Status variable.
Exceptions
  • SMB_NOT_FOUND_ERROR: If an item with the given key is not found.

DATA ht_get(smb_ht const * table, DATA key, smb_status * status)

Return the value associated with the key provided.

Return
The value associated the key.
Parameters
  • table: A pointer to the hash table.
  • key: The key whose value to retrieve.
  • status: Status variable.
Exceptions
  • NOT_FOUND_ERROR:

bool ht_contains(smb_ht const * table, DATA key)

Return true when a key is contained in the table.

Return
Whether the key is present.
Parameters
  • table: A pointer to the hash table.
  • key: The key to search for.

smb_iter ht_get_iter(const smb_ht * ht)

Return an iterator over the keys of the table.

Return
An iterator struct.
Parameters
  • ht: A pointer to the hash table.

unsigned int ht_string_hash(DATA data)

Return the hash of the data, interpreting it as a string.

Return
The hash value of the string.
Parameters
  • data: The string to hash, assuming that the value contained is a char*.

void ht_print(smb_ht const * table, int full_mode)

Print the entire hash table.

This function is useful for diagnostics. It can show every row in the table (with full_mode) so you can see how well entries are distributed in the table. Or, it can be compact and show just the rows with data.

Parameters
  • table: The table to print.
  • full_mode: Whether to print every row in the hash table.

int ht_next_size(int current)

The next hash table size. Not really public, but shared for hta.

struct smb_ht_bckt
#include <ht.h>

The bucket of a hash table. Contains key,value pairs, and is a singly linked list.

Public Members

DATA key

The key of this entry.

DATA value

The value of this entry.

smb_ht_mark mark

Marker for whether or not the table is full or empty.

struct smb_ht
#include <ht.h>

A hash table data structure.

Public Members

unsigned int length

The number of items in the hash table.

unsigned int allocated

The number of slots allocated in the hash table.

HASH_FUNCTION hash

The hash function for this hash table.

DATA_COMPARE equal

Function to use to compare equality.

struct smb_ht_bckt* table

Pointer to the data of the table.