hashtable.h File Reference

A configurable hashtable that maps K -> V. More...

Go to the source code of this file.

Data Structures
struct	cvx_container
struct	hashtable_vtabk
struct	hashtable_vtabv
struct	hashtable_entry
struct	hashtable
struct	hashtable_iter

Typedefs
typedef struct cvx_container	cvx_container

Enumerations
enum	cvx_flags {   CVX_FLAG_OK = 0 , CVX_FLAG_VTAB = 1 , CVX_FLAG_WRONG_TAG = 2 , CVX_FLAG_ALLOC = 3 ,   CVX_FLAG_EMPTY = 4 , CVX_FLAG_FULL = 5 , CVX_FLAG_RANGE = 6 , CVX_FLAG_NOT_FOUND = 7 ,   CVX_FLAG_INVALID = 8 , CVX_FLAG_DUPLICATE = 9 , CVX_FLAG_ERROR = 10 }
	Status and error flags for the CVX library. More...
enum	cvx_heap_order { CVX_MAX_HEAP = 1 , CVX_MIN_HEAP = -1 }
	enum cvx_heap_order More...
enum	hashtable_entry_state { hashtable_es_empty = 0 , hashtable_es_filled = 1 , hashtable_es_deleted = -1 }

Functions
void	ht_init (struct hashtable *self, struct hashtable_vtabk *vtabk, struct hashtable_vtabv *vtabv, size_t capacity)
	IMPLEMENTATIONS.
void	ht_clone (struct hashtable *orig, struct hashtable *clone)
void	ht_drop (struct hashtable *self)
enum cvx_flags	ht_flag (struct hashtable *_self_)
size_t	ht_count (struct hashtable *_self_)
size_t	ht_capacity (struct hashtable *_self_)
double	ht_load (struct hashtable *_self_)
_Bool	ht_empty (struct hashtable *_self_)
_Bool	ht_insert (struct hashtable *_self_, TKey _key_, TVal _val_)
_Bool	ht_update (struct hashtable *_self_, TKey _key_, TVal _new_, TVal *_old_)
_Bool	ht_remove (struct hashtable *_self_, TKey _key_, TVal *_out_)
TVal	ht_get (struct hashtable *_self_, TKey _key_)
TVal *	ht_get_ref (struct hashtable *_self_, TKey _key_)
_Bool	ht_contains (struct hashtable *_self_, TKey _key_)
struct hashtable_iter	ht_iter_init_start (struct hashtable *_target_)
	ITERATOR.
struct hashtable_iter	ht_iter_init_end (struct hashtable *_target_)
struct hashtable_iter *	ht_iter_start (struct hashtable *_target_)
struct hashtable_iter *	ht_iter_end (struct hashtable *_target_)
void	ht_iter_drop (struct hashtable_iter *_iter_)
_Bool	ht_iter_at_start (struct hashtable_iter *_iter_)
_Bool	ht_iter_at_end (struct hashtable_iter *_iter_)
size_t	ht_iter_count (struct hashtable_iter *_iter_)
void	ht_iter_to_start (struct hashtable_iter *_iter_)
void	ht_iter_to_end (struct hashtable_iter *_iter_)
void	ht_iter_next (struct hashtable_iter *_iter_)
void	ht_iter_prev (struct hashtable_iter *_iter_)
void	ht_iter_forward (struct hashtable_iter *_iter_, size_t _steps_)
void	ht_iter_backward (struct hashtable_iter *_iter_, size_t _steps_)
TKey	ht_iter_key (struct hashtable_iter *_iter_)
TVal	ht_iter_value (struct hashtable_iter *_iter_)
size_t	ht_iter_index (struct hashtable_iter *_iter_)
struct hashtable_entry *	ht__get_entry (struct hashtable *_self_, TKey _key_)
	PRIVATE FUNCTIONS.
size_t	ht__next_prime (size_t _required_)
_Bool	ht__resize (struct hashtable *_self_, size_t _new_cap_)
void	ht__iter_scan_bounds (struct hashtable *_target_, size_t *_first_, size_t *_last_)
void	ht__proxy_clone (cvx_container *_orig_, cvx_container *_clone_)
	PROXIES.
void	ht__proxy_drop (cvx_container *_col_)
size_t	ht__proxy_count (cvx_container *_col_)
size_t	ht__proxy_capacity (cvx_container *_col_)
_Bool	ht__proxy_empty (cvx_container *_col_)
_Bool	ht__proxy_insert (cvx_container *_col_, TKey _key_, TVal _val_)
_Bool	ht__proxy_update (cvx_container *_col_, TKey _key_, TVal _new_, TVal *_old_)
_Bool	ht__proxy_remove (cvx_container *_col_, TKey _key_, TVal *_out_)
TVal	ht__proxy_get (cvx_container *_col_, TKey _key_)
_Bool	ht__proxy_contains (cvx_container *_col_, TKey _key_)
cvx_container *	ht__proxy_iter_start (cvx_container *_col_)
cvx_container *	ht__proxy_iter_end (cvx_container *_col_)
void	ht__proxy_iter_drop (cvx_container *_col_)
_Bool	ht__proxy_iter_at_start (cvx_container *_col_)
_Bool	ht__proxy_iter_at_end (cvx_container *_col_)
size_t	ht__proxy_iter_count (cvx_container *_col_)
void	ht__proxy_iter_to_start (cvx_container *_col_)
void	ht__proxy_iter_to_end (cvx_container *_col_)
void	ht__proxy_iter_next (cvx_container *_col_)
void	ht__proxy_iter_prev (cvx_container *_col_)
void	ht__proxy_iter_forward (cvx_container *_col_, size_t _steps_)
void	ht__proxy_iter_backward (cvx_container *_col_, size_t _steps_)
TKey	ht__proxy_iter_key (cvx_container *_col_)
TVal	ht__proxy_iter_value (cvx_container *_col_)
size_t	ht__proxy_iter_index (cvx_container *_col_)

Detailed Description

A configurable hashtable that maps K -> V.

Author

Leonardo Vencovsky

Version

0.0.1

Required Macros

• K: Type name of keys in the map.
• V: Type name of values in the map.
• SNAME: Prefix of all declared structs (e.g. struct SNAME, struct SNAME_vtabv, etc.).
• PFX: Prefix of all functions, including implementation detail ones.
• TAG: A unique integer tag that identifies this data structure.

Implementation

Open-addressing, linear-probing hashtable with robin hood insertion.

Keys are hashed with vtabk->hash and compared with vtabk->comp. Both are required; vtabk->clone / vtabk->drop and vtabv->clone / vtabv->drop are optional.

Capacity is always a prime number. A resize is triggered whenever count >= capacity * load (default load = 0.7). Deletions use tombstones, which are purged on resize.

TO-DOs

• Implement OPTs, so the hashtable can be customized with linear-probing or separate chaining.

Typedef Documentation

cvx_container

typedef struct cvx_container cvx_container

Enumeration Type Documentation

cvx_flags

enum cvx_flags

Status and error flags for the CVX library.

Error Handling

Enumerator
CVX_FLAG_OK	No errors.
CVX_FLAG_VTAB	Required vtab function was not provided.
CVX_FLAG_WRONG_TAG	Tags are checked so you don't pass the wrong struct to a function.
CVX_FLAG_ALLOC	Allocation failed.
CVX_FLAG_EMPTY	Operation can not proceed because the container is empty.
CVX_FLAG_FULL	When a container that doesn't resize is full.
CVX_FLAG_RANGE	Index out of range.
CVX_FLAG_NOT_FOUND	Key or value not found.
CVX_FLAG_INVALID	Invalid argument or operation.
CVX_FLAG_DUPLICATE	Duplicate key or value.
CVX_FLAG_ERROR	Generic error, or unknown error.

cvx_heap_order

enum cvx_heap_order

enum cvx_heap_order

Defines the two possible heaps:

• Max Heap has the greatest element at the top
• Min Heap has the smallest element at the top

Enumerator
CVX_MAX_HEAP
CVX_MIN_HEAP

hashtable_entry_state

enum hashtable_entry_state

Enumerator
hashtable_es_empty
hashtable_es_filled
hashtable_es_deleted

Function Documentation

ht__get_entry()

struct hashtable_entry * ht__get_entry	(	struct hashtable *	_self_,
		TKey	_key_
	)

PRIVATE FUNCTIONS.

ht__iter_scan_bounds()

void ht__iter_scan_bounds	(	struct hashtable *	_target_,
		size_t *	_first_,
		size_t *	_last_
	)

ht__next_prime()

size_t ht__next_prime

(

size_t

_required_

)

ht__proxy_capacity()

size_t ht__proxy_capacity

(

cvx_container *

_col_

)

ht__proxy_clone()

void ht__proxy_clone	(	cvx_container *	_orig_,
		cvx_container *	_clone_
	)

PROXIES.

ht__proxy_contains()

_Bool ht__proxy_contains	(	cvx_container *	_col_,
		TKey	_key_
	)

ht__proxy_count()

size_t ht__proxy_count

(

cvx_container *

_col_

)

ht__proxy_drop()

void ht__proxy_drop

(

cvx_container *

_col_

)

ht__proxy_empty()

_Bool ht__proxy_empty

(

cvx_container *

_col_

)

ht__proxy_get()

TVal ht__proxy_get	(	cvx_container *	_col_,
		TKey	_key_
	)

ht__proxy_insert()

_Bool ht__proxy_insert	(	cvx_container *	_col_,
		TKey	_key_,
		TVal	_val_
	)

ht__proxy_iter_at_end()

_Bool ht__proxy_iter_at_end

(

cvx_container *

_col_

)

ht__proxy_iter_at_start()

_Bool ht__proxy_iter_at_start

(

cvx_container *

_col_

)

ht__proxy_iter_backward()

void ht__proxy_iter_backward	(	cvx_container *	_col_,
		size_t	_steps_
	)

ht__proxy_iter_count()

size_t ht__proxy_iter_count

(

cvx_container *

_col_

)

ht__proxy_iter_drop()

void ht__proxy_iter_drop

(

cvx_container *

_col_

)

ht__proxy_iter_end()

cvx_container * ht__proxy_iter_end

(

cvx_container *

_col_

)

ht__proxy_iter_forward()

void ht__proxy_iter_forward	(	cvx_container *	_col_,
		size_t	_steps_
	)

ht__proxy_iter_index()

size_t ht__proxy_iter_index

(

cvx_container *

_col_

)

ht__proxy_iter_key()

TKey ht__proxy_iter_key

(

cvx_container *

_col_

)

ht__proxy_iter_next()

void ht__proxy_iter_next

(

cvx_container *

_col_

)

ht__proxy_iter_prev()

void ht__proxy_iter_prev

(

cvx_container *

_col_

)

ht__proxy_iter_start()

cvx_container * ht__proxy_iter_start

(

cvx_container *

_col_

)

ht__proxy_iter_to_end()

void ht__proxy_iter_to_end

(

cvx_container *

_col_

)

ht__proxy_iter_to_start()

void ht__proxy_iter_to_start

(

cvx_container *

_col_

)

ht__proxy_iter_value()

TVal ht__proxy_iter_value

(

cvx_container *

_col_

)

ht__proxy_remove()

_Bool ht__proxy_remove	(	cvx_container *	_col_,
		TKey	_key_,
		TVal *	_out_
	)

ht__proxy_update()

_Bool ht__proxy_update	(	cvx_container *	_col_,
		TKey	_key_,
		TVal	_new_,
		TVal *	_old_
	)

ht__resize()

_Bool ht__resize	(	struct hashtable *	_self_,
		size_t	_new_cap_
	)

ht_capacity()

size_t ht_capacity

(

struct hashtable *

_self_

)

ht_clone()

void ht_clone	(	struct hashtable *	orig,
		struct hashtable *	clone
	)

ht_contains()

_Bool ht_contains	(	struct hashtable *	_self_,
		TKey	_key_
	)

ht_count()

size_t ht_count

(

struct hashtable *

_self_

)

ht_drop()

void ht_drop

(

struct hashtable *

self

)

ht_empty()

_Bool ht_empty

(

struct hashtable *

_self_

)

ht_flag()

enum cvx_flags ht_flag

(

struct hashtable *

_self_

)

ht_get()

TVal ht_get	(	struct hashtable *	_self_,
		TKey	_key_
	)

ht_get_ref()

TVal * ht_get_ref	(	struct hashtable *	_self_,
		TKey	_key_
	)

ht_init()

void ht_init	(	struct hashtable *	self,
		struct hashtable_vtabk *	vtabk,
		struct hashtable_vtabv *	vtabv,
		size_t	capacity
	)

IMPLEMENTATIONS.

ht_insert()

_Bool ht_insert	(	struct hashtable *	_self_,
		TKey	_key_,
		TVal	_val_
	)

ht_iter_at_end()

_Bool ht_iter_at_end

(

struct hashtable_iter *

_iter_

)

ht_iter_at_start()

_Bool ht_iter_at_start

(

struct hashtable_iter *

_iter_

)

ht_iter_backward()

void ht_iter_backward	(	struct hashtable_iter *	_iter_,
		size_t	_steps_
	)

ht_iter_count()

size_t ht_iter_count

(

struct hashtable_iter *

_iter_

)

ht_iter_drop()

void ht_iter_drop

(

struct hashtable_iter *

_iter_

)

ht_iter_end()

struct hashtable_iter * ht_iter_end

(

struct hashtable *

_target_

)

ht_iter_forward()

void ht_iter_forward	(	struct hashtable_iter *	_iter_,
		size_t	_steps_
	)

ht_iter_index()

size_t ht_iter_index

(

struct hashtable_iter *

_iter_

)

ht_iter_init_end()

struct hashtable_iter ht_iter_init_end

(

struct hashtable *

_target_

)

ht_iter_init_start()

struct hashtable_iter ht_iter_init_start

(

struct hashtable *

_target_

)

ITERATOR.

ht_iter_key()

TKey ht_iter_key

(

struct hashtable_iter *

_iter_

)

ht_iter_next()

void ht_iter_next

(

struct hashtable_iter *

_iter_

)

ht_iter_prev()

void ht_iter_prev

(

struct hashtable_iter *

_iter_

)

ht_iter_start()

struct hashtable_iter * ht_iter_start

(

struct hashtable *

_target_

)

ht_iter_to_end()

void ht_iter_to_end

(

struct hashtable_iter *

_iter_

)

ht_iter_to_start()

void ht_iter_to_start

(

struct hashtable_iter *

_iter_

)

ht_iter_value()

TVal ht_iter_value

(

struct hashtable_iter *

_iter_

)

ht_load()

double ht_load

(

struct hashtable *

_self_

)

ht_remove()

_Bool ht_remove	(	struct hashtable *	_self_,
		TKey	_key_,
		TVal *	_out_
	)

ht_update()

_Bool ht_update	(	struct hashtable *	_self_,
		TKey	_key_,
		TVal	_new_,
		TVal *	_old_
	)