src/hashtable.h File Reference

A simple hashtable that uses chaining for hash collisions. More...

#include <stdlib.h>
#include <stdbool.h>
#include "cdsa_types.h"

Include dependency graph for hashtable.h:

Go to the source code of this file.

Defines

#define DEFAULT_HASHTABLE_CAPACITY

The default size for the backing array of the hashtable, used when 0 is given as initial_capacity to ht_new.

#define DEFAULT_LOAD_FACTOR

The default load factor controlling when expansion of the backing array occurs, used when load_factor of 0.0 is given to ht_new.

Typedefs

typedef struct HashTable HashTable

The incomplete definition of the hashtable.

Functions

cdsa_status_t ht_new (HashTable **new_ht, size_t initial_capacity, float load_factor, size_t key_size, cdsa_compare_func_t compare, cdsa_destroy_map_func_t destroy)

Create a new hashtable, setting *new_ht to the new table.

cdsa_status_t ht_destroy (HashTable **ht)

Destroy the given hashtable pointer to by ht, calling the destroy function on every (key, value) pair in the table if a non-NULL function was given to ht_new, and set *ht to NULL.

cdsa_status_t ht_is_empty (const HashTable *const ht, bool *is_empty)

Answer whether hashtable is empty, recording result in is_empty.

cdsa_status_t ht_size (const HashTable *const ht, size_t *size)

Answer the size of the hashtable, recording answer in size var.

cdsa_status_t ht_capacity (const HashTable *const ht, size_t *capacity)

Answer the size of the backing array for the given hashtable, recording answer in capacity var.

cdsa_status_t ht_has_key (const HashTable *const ht, const void *const key, bool *has_key)

Answer whether hashtable contains the given key, recording answer in has_key var.

cdsa_status_t ht_get (const HashTable *const ht, const void *const key, void *ptr)

Answer the value in the table for the given key, if any, recording value in *ptr.

cdsa_status_t ht_put (HashTable *const ht, const void *const key, void *const value, void *prev_val)

Put the given (key, value) pair in the table, replacing any previous mapping for the given key, setting *prev_val to the previous value if there was one.

cdsa_status_t ht_remove (HashTable *const ht, const void *const key, void *prev_val)

Remove the (key, value) pair for the given key from the table, recording previous value for the key in *prev_val if there was an entry for the given key.

Detailed Description

A simple hashtable that uses chaining for hash collisions.

NULL keys are not permitted, but NULL values are permitted. The table automatically expands when necessary, according to the load_factor argument to ht_new and the current load (size/capacity).

All functions take a status_t parameter as their last parameter. If non-NULL, it will be set by the function to indicate success or failure of the function. For example, calling ht_remove returns the old value if any for the key being removed, but if the value itself was NULL, the two cases of no key found and key with NULL value being removed can be distinguished by checking the status variable after return, which would be set to false in the first case or true in the second case.

Definition in file hashtable.h.

Function Documentation

cdsa_status_t ht_new	(	HashTable **	new_ht,
		size_t	initial_capacity,
		float	load_factor,
		size_t	key_size,
		cdsa_compare_func_t	compare,
		cdsa_destroy_map_func_t	destroy
	)

Create a new hashtable, setting *new_ht to the new table.

Parameters:

	new_ht	A non-NULL pointer to a HashTable pointer, to be set to the new HashTable on success.
	initial_capacity	The initial size of the backing array (use 0 for default).
	load_factor	The threshold at which (size/capacity) should trigger an expansion of the backing array (use 0.0 for default).
	key_size	The size of the key pointers in bytes.
	compare	A non-NULL function pointer for comparing key values.
	destroy	A function to be applied to every (key, value) pair in the table when ht_destroy is called, or NULL.

cdsa_status_t ht_destroy ( HashTable ** ht )

Destroy the given hashtable pointer to by ht, calling the destroy function on every (key, value) pair in the table if a non-NULL function was given to ht_new, and set *ht to NULL.

Parameters:

ht

A non-NULL pointer to a non-NULL hashtable.

cdsa_status_t ht_is_empty	(	const HashTable *const	ht,
		bool *	is_empty
	)

Answer whether hashtable is empty, recording result in is_empty.

Parameters:

	ht	A non-NULL pointer to a non-NULL hashtable.
	is_empty	A non-NULL pointer to a bool variable for recording whether table is empty on success.

cdsa_status_t ht_size	(	const HashTable *const	ht,
		size_t *	size
	)

Answer the size of the hashtable, recording answer in size var.

Parameters:

	ht	A non-NULL pointer to a non-NULL hashtable.
	size	A non-NULL pointer to a size_t variable for recording the size of the table on success.

cdsa_status_t ht_capacity	(	const HashTable *const	ht,
		size_t *	capacity
	)

Answer the size of the backing array for the given hashtable, recording answer in capacity var.

Parameters:

	ht	A non-NULL pointer to a non-NULL hashtable.
	capacity	A non-NULL pointer to a size_t variable for recording the current capacity of table.

cdsa_status_t ht_has_key	(	const HashTable *const	ht,
		const void *const	key,
		bool *	has_key
	)

Answer whether hashtable contains the given key, recording answer in has_key var.

Parameters:

	ht	A non-NULL pointer to a non-NULL hashtable.
	key	A non-NULL pointer to key.
	has_key	A non-NULL pointer to a bool var for recording whether table contains key.

cdsa_status_t ht_get	(	const HashTable *const	ht,
		const void *const	key,
		void *	ptr
	)

Answer the value in the table for the given key, if any, recording value in *ptr.

Parameters:

	ht	A non-NULL pointer to a non-NULL hashtable.
	key	A non-NULL pointer to key.
	ptr	A non-NULL pointer to a client pointer for storing the value on success.

Returns:: If key was found in table, the return code is CDSA_SUCCESS; if there was no element in the table for the given key, the return code is CDSA_NO_RESULT. Other return codes indicate an error.

cdsa_status_t ht_put	(	HashTable *const	ht,
		const void *const	key,
		void *const	value,
		void *	prev_val
	)

Put the given (key, value) pair in the table, replacing any previous mapping for the given key, setting *prev_val to the previous value if there was one.

Parameters:

	ht	A non-NULL pointer to a non-NULL hashtable.
	key	A non-NULL pointer to key.
	value	Pointer to the value, or NULL.
	prev_val	A non-NULL pointer to a client pointer for recording the previous value for the given key on success if key was already in table.

Returns:: The previous value in the table for the given key, or NULL.

cdsa_status_t ht_remove	(	HashTable *const	ht,
		const void *const	key,
		void *	prev_val
	)

Remove the (key, value) pair for the given key from the table, recording previous value for the key in *prev_val if there was an entry for the given key.

Parameters:

	ht	A non-NULL pointer to a non-NULL hashtable.
	key	A non-NULL pointer to key.
	prev_val	A non-NULL pointer to a client pointer for storing the previous value in table for the given key.

Returns:: If a (key, value) pair was removed, the return code is CDSA_SUCCESS; if there was no element in the table for the given key, the return code is CDSA_NO_RESULT. Other return codes indicate an error.


Defines
#define	DEFAULT_HASHTABLE_CAPACITY
	The default size for the backing array of the hashtable, used when 0 is given as initial_capacity to ht_new.
#define	DEFAULT_LOAD_FACTOR
	The default load factor controlling when expansion of the backing array occurs, used when load_factor of 0.0 is given to ht_new.
Typedefs
typedef struct HashTable	HashTable
	The incomplete definition of the hashtable.
Functions
cdsa_status_t	ht_new (HashTable **new_ht, size_t initial_capacity, float load_factor, size_t key_size, cdsa_compare_func_t compare, cdsa_destroy_map_func_t destroy)
	Create a new hashtable, setting *new_ht to the new table.
cdsa_status_t	ht_destroy (HashTable **ht)
	Destroy the given hashtable pointer to by ht, calling the destroy function on every (key, value) pair in the table if a non-NULL function was given to ht_new, and set *ht to NULL.
cdsa_status_t	ht_is_empty (const HashTable const ht, bool is_empty)
	Answer whether hashtable is empty, recording result in is_empty.
cdsa_status_t	ht_size (const HashTable const ht, size_t size)
	Answer the size of the hashtable, recording answer in size var.
cdsa_status_t	ht_capacity (const HashTable const ht, size_t capacity)
	Answer the size of the backing array for the given hashtable, recording answer in capacity var.
cdsa_status_t	ht_has_key (const HashTable const ht, const void const key, bool *has_key)
	Answer whether hashtable contains the given key, recording answer in has_key var.
cdsa_status_t	ht_get (const HashTable const ht, const void const key, void *ptr)
	Answer the value in the table for the given key, if any, recording value in *ptr.
cdsa_status_t	ht_put (HashTable const ht, const void const key, void const value, void prev_val)
	Put the given (key, value) pair in the table, replacing any previous mapping for the given key, setting *prev_val to the previous value if there was one.
cdsa_status_t	ht_remove (HashTable const ht, const void const key, void *prev_val)
	Remove the (key, value) pair for the given key from the table, recording previous value for the key in *prev_val if there was an entry for the given key.