Hash Table

Collaboration diagram for Hash Table:

Modules
	Hash Table Iterator

Data Structures
struct	_amxc_htable
	The hash table structure. More...

Macros
#define	amxc_htable_for_each(it, htable)
	Loops over items in the hash table. More...
#define	amxc_htable_iterate(it, htable)
	Loops over items in the hash table. More...
#define	AMXC_HTABLE_RANGE   UINT32_MAX
	Out of range indicator. More...

Typedefs
typedef unsigned int(*	amxc_htable_hash_func_t) (const char *key, const unsigned int len)
	Definition of the hash function. More...
typedef void(*	amxc_htable_it_delete_t) (const char *key, amxc_htable_it_t *it)
	Definition of the hash table item delete function. More...
typedef struct _amxc_htable	amxc_htable_t
	The hash table structure. More...

Functions
int	amxc_htable_new (amxc_htable_t **htable, const size_t reserve)
	Allocates a hash table. More...
void	amxc_htable_delete (amxc_htable_t **htable, amxc_htable_it_delete_t func)
	Frees the previously allocated hash table. More...
int	amxc_htable_init (amxc_htable_t *const htable, const size_t reserve)
	Initializes a hash table. More...
void	amxc_htable_clean (amxc_htable_t *const htable, amxc_htable_it_delete_t func)
	Removes all items from the hash table. More...
void	amxc_htable_set_hash_func (amxc_htable_t *const htable, amxc_htable_hash_func_t func)
	Sets the hash function for the hash table. More...
unsigned int	amxc_htable_key2index (const amxc_htable_t *const htable, const char *const key)
	Converts a key into an index. More...
AMXC_INLINE bool	amxc_htable_is_empty (const amxc_htable_t *const htable)
	Checks that the hash table is empty. More...
AMXC_INLINE size_t	amxc_htable_size (const amxc_htable_t *const htable)
	Calculates the size of the hash table. More...
AMXC_INLINE size_t	amxc_htable_capacity (const amxc_htable_t *const htable)
	Calculates the capacity of the hash table. More...
int	amxc_htable_insert (amxc_htable_t *const htable, const char *const key, amxc_htable_it_t *const it)
	Inserts an item in the hash table. More...
amxc_htable_it_t *	amxc_htable_get (const amxc_htable_t *const htable, const char *const key)
	Gets a hash table iterator from the hash table. More...
amxc_htable_it_t *	amxc_htable_take (amxc_htable_t *const htable, const char *const key)
	Removes a hash table iterator from the hash table. More...
amxc_htable_it_t *	amxc_htable_get_first (const amxc_htable_t *const htable)
	Gets the first item stored in the table. More...
amxc_htable_it_t *	amxc_htable_get_last (const amxc_htable_t *const htable)
	Gets the last item stored in the table. More...
amxc_array_t *	amxc_htable_get_sorted_keys (const amxc_htable_t *const htable)
	Creates an array containing all keys of the hash table. More...
AMXC_INLINE bool	amxc_htable_contains (const amxc_htable_t *const htable, const char *const key)
	Verifies that a key is in the hash table. More...
int	amxc_htable_move (amxc_htable_t *const dest, amxc_htable_t *const src)
	Moves all items from one hash table to another hash table. More...
AMXC_INLINE amxc_htable_it_t *	amxc_htable_take_first (const amxc_htable_t *const htable)
	Removes the first item stored in the table. More...

Detailed Description

Macro Definition Documentation

amxc_htable_for_each

#define amxc_htable_for_each	(		it,
			htable
	)

Value:

    for(amxc_htable_it_t* it = amxc_htable_get_first(htable), \
        * it ## _next = amxc_htable_it_get_next(it); \
        it; \
        it = it ## _next, \
        it ## _next = amxc_htable_it_get_next(it))

Loops over items in the hash table.

Iterates over the hash table and updates the iterator each time.

Warning

Do not modify the hash table itself while using this macro. It is possible to nest this macro It is allowed to delete or remove the current iterator from the hash table.

Definition at line 102 of file amxc_htable.h.

amxc_htable_iterate

#define amxc_htable_iterate	(		it,
			htable
	)

Value:

    for(amxc_htable_it_t* it = amxc_htable_get_first(htable); \
        it; \
        it = amxc_htable_it_get_next(it))

Loops over items in the hash table.

Iterates over the hash table and updates the iterator each time.

Warning

Do not modify the hash table itself while using this macro.

Definition at line 119 of file amxc_htable.h.

AMXC_HTABLE_RANGE

#define AMXC_HTABLE_RANGE   UINT32_MAX

Out of range indicator.

Definition at line 129 of file amxc_htable.h.

Typedef Documentation

amxc_htable_hash_func_t

typedef unsigned int(* amxc_htable_hash_func_t) (const char *key, const unsigned int len)

Definition of the hash function.

The hash function calculates a hash from the key. A custom hash function can be implemented and set on the hash table using amxc_htable_set_hash_func.

A set of hash functions is already available in see amxc_hash.h.

The calculated hash is used to calculate the index of the position of the key in the array.

Definition at line 158 of file amxc_htable.h.

amxc_htable_it_delete_t

typedef void(* amxc_htable_it_delete_t) (const char *key, amxc_htable_it_t *it)

Definition of the hash table item delete function.

A pointer to a delete function is used in the following functions amxc_htable_delete, amxc_htable_clean, amxc_htable_it_clean.

Definition at line 168 of file amxc_htable.h.

amxc_htable_t

typedef struct _amxc_htable amxc_htable_t

The hash table structure.

Function Documentation

amxc_htable_capacity()

AMXC_INLINE size_t amxc_htable_capacity

(

const amxc_htable_t *const

htable

)

Calculates the capacity of the hash table.

The capacity is the number of items that is reserved

Parameters

htable

a pointer to the hash table structure

Returns

returns the number of reserved item positions in hash table

Definition at line 351 of file amxc_htable.h.

                                                               {
    return htable != NULL ? htable->table.items : 0;
}

amxc_htable_clean()

void amxc_htable_clean	(	amxc_htable_t *const	htable,
		amxc_htable_it_delete_t	func
	)

Removes all items from the hash table.

Removes all items from the hash table, if a delete function is provided, it is called for each item after it was removed from the table. The buffer used to store the items is freed as well.

Parameters

htable	a pointer to the htable structure
func	pointer to a function that is called to free each item in the hash table

Definition at line 200 of file amxc_htable.c.

                                                                                  {
    when_null(htable, exit);
 
    htable->it_del = func;
    amxc_array_clean(&htable->table, amxc_htable_it_delete_func);
    htable->items = 0;
 
exit:
    return;
}

amxc_htable_contains()

AMXC_INLINE bool amxc_htable_contains	(	const amxc_htable_t *const	htable,
		const char *const	key
	)

Verifies that a key is in the hash table.

Parameters

htable	a pointer to the hash table structure
key	the key

Returns

True when the key is at least once found in the table, false otherwise.

Definition at line 512 of file amxc_htable.h.

                                                                                    {
    return amxc_htable_get(htable, key) ? true : false;
}

amxc_htable_delete()

void amxc_htable_delete	(	amxc_htable_t **	htable,
		amxc_htable_it_delete_t	func
	)

Frees the previously allocated hash table.

Removes all items from the hash table, if a delete function is provided, it is called for each item after it was removed from the hash table.

Frees the allocated memory and sets the pointer to NULL.

Note

Only call this function for hash tables that are allocated on the heap using amxc_htable_new

Parameters

htable	a pointer to the location where the pointer to the hash table is be stored
func	pointer to a function that is called to free each item in the hash table

Definition at line 172 of file amxc_htable.c.

                                                                              {
    when_null(htable, exit);
    when_null(*htable, exit);
 
    (*htable)->it_del = func;
    amxc_array_clean(&(*htable)->table, amxc_htable_it_delete_func);
    free(*htable);
    *htable = NULL;
 
exit:
    return;
}

amxc_htable_get()

amxc_htable_it_t* amxc_htable_get	(	const amxc_htable_t *const	htable,
		const char *const	key
	)

Gets a hash table iterator from the hash table.

The key provided is converted into an index using amxc_htable_key2index. If multiple items are available at the calculated position with the same key, the first one is returned. The next item can be retrieved with amxc_htable_it_get_next or with amxc_htable_it_get_next_key if it must have the same key.

Note

The item is not removed from the hash table. To remove the item use amxc_htable_take

Parameters

htable	a pointer to the hash table structure
key	the item key

Returns

Pointer to the hash table iterator or NULL if no iterator was stored with the given key. The pointer can be converted to the real data pointer using amxc_htable_it_get_data

Definition at line 278 of file amxc_htable.c.

                                                         {
    amxc_htable_it_t* it = NULL;
    unsigned int index = 0;
    amxc_array_it_t* ait = NULL;
 
    when_null(htable, exit);
    when_null(key, exit);
    when_true(*key == 0, exit);
 
    when_true(htable->table.items == 0, exit);
 
    index = amxc_htable_key2index(htable, key);
    // the index is always in array bounderies.
    // the following line is always returning a valid array iterator pointer
    ait = amxc_array_get_at(&htable->table, index);
 
    it = ait == NULL? NULL:(amxc_htable_it_t*) ait->data;
    while(it != NULL && strcmp(key, it->key) != 0) {
        it = it->next;
    }
 
exit:
    return it;
}

amxc_htable_get_first()

amxc_htable_it_t* amxc_htable_get_first

(

const amxc_htable_t *const

htable

)

Gets the first item stored in the table.

This function iterates the table from the beginning and returns the first item encounter.

Note

The order of the items in the table is not the same as the order they were inserted in the table. So the first item found can be different then the first item inserted.

Parameters

htable

a pointer to the hash table structure

Returns

Pointer to the hash table iterator or NULL if no items were stored in the hash table.

Definition at line 313 of file amxc_htable.c.

                                                                           {
    amxc_htable_it_t* it = NULL;
    amxc_array_it_t* ait = NULL;
    when_null(htable, exit);
 
    ait = amxc_array_get_first(&htable->table);
    when_null(ait, exit);
    it = (amxc_htable_it_t*) ait->data;
 
exit:
    return it;
}

amxc_htable_get_last()

amxc_htable_it_t* amxc_htable_get_last

(

const amxc_htable_t *const

htable

)

Gets the last item stored in the table.

This function iterates the table from the end and returns the last item encounter.

Note

The order of the items in the table is not the same as the order they were inserted in the table. So the last item found can be different then the last item inserted.

Parameters

htable

a pointer to the hash table structure

Returns

Pointer to the hash table iterator or NULL if no items were stored in the hash table.

Definition at line 326 of file amxc_htable.c.

                                                                          {
    amxc_htable_it_t* it = NULL;
    amxc_array_it_t* ait = NULL;
    when_null(htable, exit);
 
    ait = amxc_array_get_last(&htable->table);
    when_null(ait, exit);
    it = (amxc_htable_it_t*) ait->data;
 
exit:
    return it;
}

amxc_htable_get_sorted_keys()

amxc_array_t* amxc_htable_get_sorted_keys

(

const amxc_htable_t *const

htable

)

Creates an array containing all keys of the hash table.

The array will be sorted in ascending order. If the hash table contains duplicate keys, the sorted array will contain duplicate keys as well.

The array will not contain empty items and the size is matching the number of items in the hash table.

The returned array should be deleted when not used anymore using amxc_array_delete, no delete function is needed.

Warning

Never delete the strings in the array, as these strings are no copies of the keys in the hash table. The array contains pointers to the keys in the hash table. Deleting them will render the hash table unusable and could lead to undefined behavior.

Parameters

htable

a pointer to the hash table structure

Returns

A pointer to an amxc_array_t or NULL when the hash table is empty.

Definition at line 339 of file amxc_htable.c.

                                                                             {
    amxc_array_t* keys = NULL;
    uint32_t size = 0;
    uint32_t index = 0;
    when_null(htable, exit);
 
    size = amxc_htable_size(htable);
    when_true(size == 0, exit);
 
    amxc_array_new(&keys, size);
    when_null(keys, exit);
 
    amxc_htable_for_each(it, htable) {
        const char* key = amxc_htable_it_get_key(it);
        amxc_array_set_data_at(keys, index, (void*) key);
        index++;
    }
 
    amxc_array_sort(keys, amxc_htable_cmp_keys);
 
exit:
    return keys;
}

amxc_htable_init()

int amxc_htable_init	(	amxc_htable_t *const	htable,
		const size_t	reserve
	)

Initializes a hash table.

Initializes the hash table structure. All pointers are reset to NULL. This function is typically called for hash tables that are on the stack. Allocating and initializing a hash table on the heap can be done using amxc_htable_new

Note

When calling this function on an already initialized hash table, that contains items, the hash table is reset and all items in the table are lost (Could potentially lead to memory leaks). Use amxc_htable_clean to remove all items from the table.

Parameters

htable	a pointer to the hash table structure.
reserve	Number of items that needs to be reserved

Returns

0 on success. -1 if a NULL pointer is given.

Definition at line 185 of file amxc_htable.c.

                                                                        {
    int retval = -1;
    when_null(htable, exit);
 
    htable->items = 0;
    htable->hfunc = amxc_BKDR_hash;
 
    when_failed(amxc_array_init(&htable->table, reserve != 0 ? reserve : 64), exit);
 
    retval = 0;
 
exit:
    return retval;
}

amxc_htable_insert()

int amxc_htable_insert	(	amxc_htable_t *const	htable,
		const char *const	key,
		amxc_htable_it_t *const	it
	)

Inserts an item in the hash table.

The key provided is converted into an index using amxc_htable_key2index. When an position is already taken the items on that position are chained. The same key can be used for different items. When the number of items in the hash table is above 75% of the capacity, the table grows. The number of items that are reserved will be doubled with a maximum of 1024 items each time.

Parameters

htable	a pointer to the hash table structure
key	the item key
it	the item htable iterator

Returns

0 when the item is inserted, -1 when an error occured

Definition at line 237 of file amxc_htable.c.

                                                   {
    int retval = -1;
 
    when_null(htable, exit);
    when_null(key, exit);
    when_true(*key == 0, exit);
    when_null(it, exit);
 
    // remove the iterator first
    amxc_htable_it_take(it);
    // no side effects here, strcmp does not modify the content of the string
    // for performance reasons the pointer check is done first
    if((it->key != NULL) && (strcmp(it->key, key) != 0)) {
        free(it->key);
        it->key = NULL;
    }
 
    if((htable->table.items == 0) ||
       (((htable->items + 1) * 100) / htable->table.items >= 75)) {
        // time to grow the table
        when_failed(amxc_htable_grow(htable, 0), exit);
    }
 
    // update htable iterator
    if(it->key == NULL) {
        size_t length = strlen(key);
        it->key = (char*) calloc(length + 1, sizeof(char));
        when_null(it->key, exit);
        memcpy(it->key, key, length);
    }
 
    amxc_htable_insert_it(htable, it);
 
    retval = 0;
 
exit:
    return retval;
}

amxc_htable_is_empty()

AMXC_INLINE bool amxc_htable_is_empty

(

const amxc_htable_t *const

htable

)

Checks that the hash table is empty.

Parameters

htable

a pointer to the hash table structure

Returns

returns true when the hash table contains no items, false when there is at least one item in the table.

Definition at line 311 of file amxc_htable.h.

                                                             {
    return htable != NULL ? (htable->items == 0) : true;
}

amxc_htable_key2index()

unsigned int amxc_htable_key2index	(	const amxc_htable_t *const	htable,
		const char *const	key
	)

Converts a key into an index.

This function converts a key into an index using the hash function and the reserved size of the table

Parameters

htable	a pointer to the htable structure
key	the key for which an index must be calculated

Returns

The calculated index or AMXC_HTABLE_RANGE if no reserved items are available in the table

Definition at line 225 of file amxc_htable.c.

                                                          {
    unsigned int hash = AMXC_HTABLE_RANGE;
    when_null(htable, exit);
    when_true(htable->table.items == 0, exit);
 
    hash = htable->hfunc(key, strlen(key)) % htable->table.items;
 
exit:
    return hash;
}

amxc_htable_move()

int amxc_htable_move	(	amxc_htable_t *const	dest,
		amxc_htable_t *const	src
	)

Moves all items from one hash table to another hash table.

After the move the source hash table will be empty.

If the destination hash table already contained items, the items of the source hash table are added to the destination.

Note

if moving fails, the source is not changed and the destination will be an ampty hash table

Parameters

dest	a pointer to the destination hash table structure
src	a pointer to the source hash table structure

Returns

0 on success any other return value indicates failure.

Definition at line 363 of file amxc_htable.c.

                                                                          {
    int retval = -1;
    size_t needed_items = 0;
    size_t needed_cap = 0;
    size_t dest_cap = 0;
 
    when_null(dest, exit);
    when_null(src, exit);
 
    needed_items = amxc_htable_size(src) + amxc_htable_size(dest);
    needed_cap = ((needed_items + 1) * 100) / 75;
    dest_cap = amxc_htable_capacity(dest);
 
    retval = 0;
    if(dest_cap < needed_cap) {
        retval = amxc_htable_grow(dest, needed_cap - dest_cap);
    }
    when_failed(retval, exit);
 
    amxc_htable_for_each(it, src) {
        amxc_htable_insert_it(dest, it);
    }
 
    retval = 0;
 
exit:
    return retval;
}

amxc_htable_new()

int amxc_htable_new	(	amxc_htable_t **	htable,
		const size_t	reserve
	)

Allocates a hash table.

Allocates and initializes memory to store a hash table. This function allocates memory from the heap, if a hash table is on the stack, it can be initialized using function amxc_htable_init

Note

The allocated memory must be freed when not used anymore, use amxc_htable_delete to free the memory

Parameters

htable	a pointer to the location where the pointer to the new hash table can be stored
reserve	Number of items that needs to be reserved

Returns

-1 if an error occurred. 0 on success

Definition at line 148 of file amxc_htable.c.

                                                                  {
    int retval = -1;
    when_null(htable, exit);
 
    *htable = (amxc_htable_t*) calloc(1, sizeof(amxc_htable_t));
    when_null(*htable, exit);
 
    retval = amxc_htable_init(*htable, reserve);
    if(retval == -1) {
        free(*htable);
        *htable = NULL;
    }
 
exit:
    return retval;
}

amxc_htable_set_hash_func()

void amxc_htable_set_hash_func	(	amxc_htable_t *const	htable,
		amxc_htable_hash_func_t	func
	)

Sets the hash function for the hash table.

A custom implementation for hash calculation function can be set on the hash table. By default the amxc_BKDR_hash function is set to calculate the hashes. Other hash functions are available, see Hash functions

Parameters

htable	a pointer to the htable structure
func	pointer to a function that is called for each hash that needs be calculated

Definition at line 211 of file amxc_htable.c.

                                                             {
    when_null(htable, exit);
 
    if(func != NULL) {
        htable->hfunc = func;
    } else {
        htable->hfunc = amxc_BKDR_hash;
    }
 
exit:
    return;
}

amxc_htable_size()

AMXC_INLINE size_t amxc_htable_size

(

const amxc_htable_t *const

htable

)

Calculates the size of the hash table.

The size of the hash table is expressed in items.

Note

Use amxc_htable_is_empty to check if a hash table is empty, do not use this function to check if the hash table is empty. This function will iterate over all pre-allocated buckets, and could have a performance impact for large hash tables.

Parameters

htable

a pointer to the hash table structure

Returns

returns the number of items in hash table

Definition at line 334 of file amxc_htable.h.

                                                           {
    return htable != NULL ? htable->items : 0;
}

amxc_htable_take()

amxc_htable_it_t* amxc_htable_take	(	amxc_htable_t *const	htable,
		const char *const	key
	)

Removes a hash table iterator from the hash table.

The key provided is converted into an index using amxc_htable_key2index. If multiple items are available at the calculated position with the same key, (collision) the first one is removed and returned.

Note

The item is removed from the hash table. To fetch the next item in the hash table with the same key, call this function again.

Use amxc_htable_it_clean to clean up the iterator.

Parameters

htable	a pointer to the hash table structure
key	the item key

Returns

Pointer to the hash table iterator or NULL if no iterator was stored with the given key. The pointer can be converted to the real data pointer using amxc_htable_it_get_data

Definition at line 304 of file amxc_htable.c.

                                                          {
    amxc_htable_it_t* it = amxc_htable_get(htable, key);
    if(it != NULL) {
        amxc_htable_it_take(it);
    }
    return it;
}

amxc_htable_take_first()

AMXC_INLINE amxc_htable_it_t* amxc_htable_take_first

(

const amxc_htable_t *const

htable

)

Removes the first item stored in the table.

This function iterates the table from the beginning and removes and returns the first one encounter.

Note

The order of the items in the table is not the same as the order they were inserted in the table. So the first item found can be different then the first item inserted.

Parameters

htable

a pointer to the hash table structure

Returns

Pointer to the hash table iterator or NULL if no items were stored in the hash table.

Definition at line 696 of file amxc_htable.h.

                                                                            {
    amxc_htable_it_t* it = amxc_htable_get_first(htable);
    amxc_htable_it_take(it);
    return it;
}