Hash Map

Hash Map. More...

Collaboration diagram for Hash Map:

Detailed Description

Hash Map.

Todo:

Dynamically sized keys without heap allocation?

Data Structures
struct	map_key_t
	Map key stucture. More...
struct	map_entry_t
	Map entry structure. More...
struct	map_t
	Hash map structure. More...

Macros
#define	MAP_MIN_CAPACITY   16
	The minimum capacity of a map.
#define	MAP_MAX_LOAD_PERCENTAGE   75
	The maximum load percentage of a map before it resizes.
#define	MAP_MIN_LOAD_PERCENTAGE   25
	The minimum load percentage of a map before it resizes down.
#define	MAP_TOMBSTONE   ((map_entry_t*)1)
	The value used to indicate a tombstone (removed entry).
#define	MAP_KEY_MAX_LENGTH   118
	The maximum length of a key in the map.
#define	MAP_ENTRY_PTR_IS_VALID(entryPtr)   ((entryPtr) != NULL && (entryPtr) != MAP_TOMBSTONE)
	Check if a map entry pointer is valid (not NULL or tombstone).
#define	MAP_CREATE()   {.entries = NULL, .capacity = 0, .length = 0, .tombstones = 0}
	Create a map initializer.

Functions
uint64_t	hash_object (const void *object, uint64_t length)
	Hash a object.
static map_key_t	map_key_buffer (const void *buffer, uint64_t length)
	Create a map key from a buffer.
static map_key_t	map_key_uint64 (uint64_t uint64)
	Create a map key from a uint64_t.
static map_key_t	map_key_string (const char *str)
	Create a map key from a string.
void	map_entry_init (map_entry_t *entry)
	Initialize a map entry.
void	map_init (map_t *map)
	Initialize a map.
void	map_deinit (map_t *map)
	Deinitialize a map.
uint64_t	map_insert (map_t *map, const map_key_t *key, map_entry_t *value)
	Insert a key-value pair into the map.
uint64_t	map_replace (map_t *map, const map_key_t *key, map_entry_t *entry)
	Replace a key-value pair in the map.
map_entry_t *	map_get (map_t *map, const map_key_t *key)
	Get a value from the map by key.
map_entry_t *	map_get_and_remove (map_t *map, const map_key_t *key)
	Get and remove a key-value pair from the map.
void	map_remove (map_t *map, map_entry_t *entry)
	Remove a entry from the map.
void	map_remove_key (map_t *map, const map_key_t *key)
	Remove a key-value pair from the map by key.
uint64_t	map_size (const map_t *map)
	Get the number of entries in the map.
uint64_t	map_capacity (const map_t *map)
	Get the capacity of the map.
bool	map_is_empty (const map_t *map)
	Check if the map is empty.
bool	map_contains (map_t *map, const map_key_t *key)
	Check if the map contains a key.
void	map_clear (map_t *map)
	Clear all entries from the map.
uint64_t	map_reserve (map_t *map, uint64_t minCapacity)
	Reserve space in the map for at least minCapacity entries.

Macro Definition Documentation

MAP_MIN_CAPACITY

#define MAP_MIN_CAPACITY   16

The minimum capacity of a map.

Definition at line 27 of file map.h.

MAP_MAX_LOAD_PERCENTAGE

#define MAP_MAX_LOAD_PERCENTAGE   75

The maximum load percentage of a map before it resizes.

Definition at line 32 of file map.h.

MAP_MIN_LOAD_PERCENTAGE

#define MAP_MIN_LOAD_PERCENTAGE   25

The minimum load percentage of a map before it resizes down.

Definition at line 37 of file map.h.

MAP_TOMBSTONE

#define MAP_TOMBSTONE   ((map_entry_t*)1)

The value used to indicate a tombstone (removed entry).

Definition at line 42 of file map.h.

MAP_KEY_MAX_LENGTH

#define MAP_KEY_MAX_LENGTH   118

The maximum length of a key in the map.

Definition at line 47 of file map.h.

MAP_ENTRY_PTR_IS_VALID

#define MAP_ENTRY_PTR_IS_VALID

(

entryPtr

)

((entryPtr) != NULL && (entryPtr) != MAP_TOMBSTONE)

Check if a map entry pointer is valid (not NULL or tombstone).

Parameters

entryPtr

The map entry pointer to check.

Returns

true if the entry pointer is valid, false otherwise.

Definition at line 81 of file map.h.

MAP_CREATE

#define MAP_CREATE

(

)

{.entries = NULL, .capacity = 0, .length = 0, .tombstones = 0}

Create a map initializer.

Returns

A map initializer.

Definition at line 161 of file map.h.

Function Documentation

hash_object()

uint64_t hash_object	(	const void *	object,
		uint64_t	length
	)

Hash a object.

Parameters

object	The object to hash.
length	The length of the object in bytes.

Returns

The hash of the object.

Definition at line 8 of file map.c.

Here is the caller graph for this function:

map_key_buffer()

static map_key_t map_key_buffer ( const void *  buffer, uint64_t  length  )

inlinestatic

Create a map key from a buffer.

Parameters

buffer	The buffer to create the key from.
length	The length of the buffer in bytes.

Returns

The map key.

Definition at line 113 of file map.h.

Here is the call graph for this function:

Here is the caller graph for this function:

map_key_uint64()

static map_key_t map_key_uint64 ( uint64_t  uint64 )

inlinestatic

Create a map key from a uint64_t.

Parameters

uint64

The uint64_t to create the key from.

Returns

The map key.

Definition at line 129 of file map.h.

Here is the call graph for this function:

Here is the caller graph for this function:

map_key_string()

static map_key_t map_key_string ( const char *  str )

inlinestatic

Create a map key from a string.

Parameters

str	The string to create the key from.

Returns

The map key.

Definition at line 144 of file map.h.

Here is the call graph for this function:

Here is the caller graph for this function:

map_entry_init()

void map_entry_init

(

map_entry_t *

entry

)

Initialize a map entry.

Parameters

entry

The map entry to initialize.

Definition at line 37 of file map.c.

Here is the call graph for this function:

Here is the caller graph for this function:

map_init()

void map_init

(

map_t *

map

)

Initialize a map.

Parameters

map	The map to initialize.

Definition at line 142 of file map.c.

Here is the caller graph for this function:

map_deinit()

void map_deinit

(

map_t *

map

)

Deinitialize a map.

Parameters

map	The map to deinitialize.

Definition at line 150 of file map.c.

Here is the call graph for this function:

Here is the caller graph for this function:

map_insert()

uint64_t map_insert	(	map_t *	map,
		const map_key_t *	key,
		map_entry_t *	value
	)

Insert a key-value pair into the map.

If the key already exists, then an EEXIST error is returned.

Parameters

map	The map to insert into.
key	The key to insert.
value	The value to insert.

Returns

On success, 0. On failure, ERR and errno is set.

Definition at line 170 of file map.c.

Here is the call graph for this function:

Here is the caller graph for this function:

map_replace()

uint64_t map_replace	(	map_t *	map,
		const map_key_t *	key,
		map_entry_t *	entry
	)

Replace a key-value pair in the map.

If the key does not exist, it is inserted.

Parameters

map	The map to replace in.
key	The key to replace.
value	The value to replace.

Returns

On success, 0. On failure, ERR and errno is set.

Definition at line 213 of file map.c.

Here is the call graph for this function:

map_get()

map_entry_t * map_get	(	map_t *	map,
		const map_key_t *	key
	)

Get a value from the map by key.

Parameters

map	The map to get from.
key	The key to get.

Returns

On success, the value. If the key does not exist, returns NULL.

Definition at line 253 of file map.c.

Here is the call graph for this function:

Here is the caller graph for this function:

map_get_and_remove()

map_entry_t * map_get_and_remove	(	map_t *	map,
		const map_key_t *	key
	)

Get and remove a key-value pair from the map.

Parameters

map	The map to get from.
key	The key to get and remove.

Returns

On success, the value. If the key does not exist, returns NULL.

Definition at line 301 of file map.c.

Here is the call graph for this function:

Here is the caller graph for this function:

map_remove()

void map_remove	(	map_t *	map,
		map_entry_t *	entry
	)

Remove a entry from the map.

If the entry does not exist, nothing happens.

Parameters

map	The map to remove from.
entry	The entry to remove.

Definition at line 319 of file map.c.

Here is the call graph for this function:

Here is the caller graph for this function:

map_remove_key()

void map_remove_key	(	map_t *	map,
		const map_key_t *	key
	)

Remove a key-value pair from the map by key.

If the key does not exist, nothing happens.

Parameters

map	The map to remove from.
key	The key to remove.

Definition at line 330 of file map.c.

Here is the call graph for this function:

map_size()

uint64_t map_size

(

const map_t *

map

)

Get the number of entries in the map.

Parameters

map	The map to get the size of.

Returns

The number of entries in the map.

Definition at line 347 of file map.c.

map_capacity()

uint64_t map_capacity

(

const map_t *

map

)

Get the capacity of the map.

Parameters

map	The map to get the capacity of.

Returns

The capacity of the map.

Definition at line 352 of file map.c.

map_is_empty()

bool map_is_empty

(

const map_t *

map

)

Check if the map is empty.

Parameters

map	The map to check.

Returns

true if the map is empty, false otherwise.

Definition at line 357 of file map.c.

Here is the caller graph for this function:

map_contains()

bool map_contains	(	map_t *	map,
		const map_key_t *	key
	)

Check if the map contains a key.

Parameters

map	The map to check.
key	The key to check for.

Returns

true if the map contains the key, false otherwise.

Definition at line 362 of file map.c.

Here is the call graph for this function:

map_clear()

void map_clear

(

map_t *

map

)

Clear all entries from the map.

Note that this does not free the entries themselves, only removes them from the map.

Parameters

map	The map to clear.

Definition at line 367 of file map.c.

Here is the caller graph for this function:

map_reserve()

uint64_t map_reserve	(	map_t *	map,
		uint64_t	minCapacity
	)

Reserve space in the map for at least minCapacity entries.

Parameters

map	The map to reserve space in.
minCapacity	The minimum capacity to reserve.

Returns

On success, 0. On failure, ERR and errno is set.

Definition at line 384 of file map.c.

Here is the call graph for this function: