sopc_dict.h File Reference

A dictionary implementation. More...

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

Go to the source code of this file.

Typedefs
typedef struct _SOPC_Dict	SOPC_Dict
typedef void	SOPC_Dict_Free_Fct(uintptr_t data)
	Type of functions used to free keys and values.
typedef uint64_t	SOPC_Dict_KeyHash_Fct(const uintptr_t data)
	Type of hash functions.
typedef bool	SOPC_Dict_KeyEqual_Fct(const uintptr_t a, const uintptr_t b)
	Type of functions used when checking two keys for equality. The function should return TRUE if and only if both keys are equal, FALSE otherwise.
typedef void	SOPC_Dict_ForEach_Fct(const uintptr_t key, uintptr_t value, uintptr_t user_data)
	Type of callback functions for SOPC_Dict_ForEach. Both the key and value belong to the dictionary. The parameter value can be modified but not reallocated nor deleted. The value of user_data is set when calling SOPC_Dict_ForEach.

Functions
SOPC_Dict *	SOPC_Dict_Create (uintptr_t empty_key, SOPC_Dict_KeyHash_Fct *key_hash, SOPC_Dict_KeyEqual_Fct *key_equal, SOPC_Dict_Free_Fct *key_free, SOPC_Dict_Free_Fct *value_free)
	Creates a new, empty dictionary.
void	SOPC_Dict_Delete (SOPC_Dict *d)
	Deletes a dictionary.
bool	SOPC_Dict_Reserve (SOPC_Dict *d, size_t n_items)
	Reserve space for a given number of items in a dictionary.
void	SOPC_Dict_SetTombstoneKey (SOPC_Dict *d, uintptr_t tombstone_key)
	Set the key used to mark removed values.
bool	SOPC_Dict_Insert (SOPC_Dict *d, uintptr_t key, uintptr_t value)
	Inserts a new key and value in the dictionary.
uintptr_t	SOPC_Dict_Get (const SOPC_Dict *d, const uintptr_t key, bool *found)
	Looks up the value associated with a key in the dictionary.
uintptr_t	SOPC_Dict_GetKey (const SOPC_Dict *d, const uintptr_t key, bool *found)
	Looks up a given key in the dictionary.
void	SOPC_Dict_Remove (SOPC_Dict *d, const uintptr_t key)
	Removes a values from the dictionary.
SOPC_Dict_Free_Fct *	SOPC_Dict_GetKeyFreeFunc (const SOPC_Dict *d)
	Retrieves the free function for this dictionary's keys.
void	SOPC_Dict_SetKeyFreeFunc (SOPC_Dict *d, SOPC_Dict_Free_Fct *func)
	Sets the free function for this dictionary's keys.
SOPC_Dict_Free_Fct *	SOPC_Dict_GetValueFreeFunc (const SOPC_Dict *d)
	Retrieves the free function for this dictionary's values.
void	SOPC_Dict_SetValueFreeFunc (SOPC_Dict *d, SOPC_Dict_Free_Fct *func)
	Sets the free function for this dictionary's values.
size_t	SOPC_Dict_Size (const SOPC_Dict *d)
	Returns the number of items in this dictionary.
size_t	SOPC_Dict_Capacity (const SOPC_Dict *d)
	Returns the number if items this dictionary can hold.
void	SOPC_Dict_ForEach (SOPC_Dict *d, SOPC_Dict_ForEach_Fct *func, uintptr_t user_data)
	Iterates over the dictionary, calling the given function for each (key, value) pair.

Detailed Description

A dictionary implementation.

Typedef Documentation

SOPC_Dict

typedef struct _SOPC_Dict SOPC_Dict

SOPC_Dict_Free_Fct

typedef void SOPC_Dict_Free_Fct(uintptr_t data)

Type of functions used to free keys and values.

SOPC_Dict_KeyHash_Fct

typedef uint64_t SOPC_Dict_KeyHash_Fct(const uintptr_t data)

Type of hash functions.

SOPC_Dict_KeyEqual_Fct

typedef bool SOPC_Dict_KeyEqual_Fct(const uintptr_t a, const uintptr_t b)

Type of functions used when checking two keys for equality. The function should return TRUE if and only if both keys are equal, FALSE otherwise.

SOPC_Dict_ForEach_Fct

typedef void SOPC_Dict_ForEach_Fct(const uintptr_t key, uintptr_t value, uintptr_t user_data)

Type of callback functions for SOPC_Dict_ForEach. Both the key and value belong to the dictionary. The parameter value can be modified but not reallocated nor deleted. The value of user_data is set when calling SOPC_Dict_ForEach.

Function Documentation

SOPC_Dict_Create()

SOPC_Dict * SOPC_Dict_Create	(	uintptr_t	empty_key,
		SOPC_Dict_KeyHash_Fct *	key_hash,
		SOPC_Dict_KeyEqual_Fct *	key_equal,
		SOPC_Dict_Free_Fct *	key_free,
		SOPC_Dict_Free_Fct *	value_free )

Creates a new, empty dictionary.

Parameters

empty_key	The key used to mark empty buckets. When using pointers as keys (for example char* ), NULL is a good choice.
key_hash	A function to calculate the hash from a key.
key_equal	A function to compare two keys for equality.
key_free	A function to free the keys when the dictionary is freed. Can be NULL if the keys should not be freed.
value_free	A function to free the values when the dictionary is freed. Can be NULL if the values should not be freed.

Returns

The created dictionary in case of success, or NULL on memory allocation failure.

Removal of values is not supported by default. To enable removing values from the dictionary, set a tombstone key using SOPC_Dict_SetTombstoneKey.

SOPC_Dict_Delete()

void SOPC_Dict_Delete

(

SOPC_Dict *

d

)

Deletes a dictionary.

Parameters

d	The dictionary.

The keys and/or values will also be freed if the corresponding key_free and/or value_free parameters were passed to SOPC_Dict_Create , or set via SOPC_Dict_SetKeyFreeFunc and SOPC_Dict_SetValueFreeFunc .

SOPC_Dict_Reserve()

bool SOPC_Dict_Reserve	(	SOPC_Dict *	d,
		size_t	n_items )

Reserve space for a given number of items in a dictionary.

Parameters

d	The dictionary.
n_items	The minimum capacity to ensure.

Returns

TRUE in case of success, or FALSE in case of memory allocation failure.

SOPC_Dict_SetTombstoneKey()

void SOPC_Dict_SetTombstoneKey	(	SOPC_Dict *	d,
		uintptr_t	tombstone_key )

Set the key used to mark removed values.

Parameters

d	The dictionary.
tombstone_key	The key used to mark removed values.

When removing values from the dictionary, this key will be used to indicate that the bucket is now empty. This means that after this function is called, the tombstone key cannot be used for normal values anymore. If the tombstone key is not set, removals of values is not supported by the dictionary.

The tombstone key MUST be different from the empty key. Otherwise an assertion failure will occur.

As a safeguard, calling this function is only allowed when the dictionary is completely empty (including tombstones), like right after its creation.

SOPC_Dict_Insert()

bool SOPC_Dict_Insert	(	SOPC_Dict *	d,
		uintptr_t	key,
		uintptr_t	value )

Inserts a new key and value in the dictionary.

Parameters

d	The dictionary.
key	The key to insert (using empty or tombstone key will fail)
value	The value to insert.

Returns

TRUE in case of success, or FALSE in case of use of empty key or tombstone key, or memory allocation failure.

The dictionary takes ownership of the key and value, those should not be modified after insertion. If an item with the same key was already inserted, it is overwritten.

SOPC_Dict_Get()

uintptr_t SOPC_Dict_Get	(	const SOPC_Dict *	d,
		const uintptr_t	key,
		bool *	found )

Looks up the value associated with a key in the dictionary.

Parameters

d	The dictionary.
key	The key to search for.
found	Out parameter, set to TRUE if the key is found. Can be NULL if the information is not required.

Returns

The associated value, or NULL if no matching key is found.

The returned value belongs to the dictionary and should not be modified.

SOPC_Dict_GetKey()

uintptr_t SOPC_Dict_GetKey	(	const SOPC_Dict *	d,
		const uintptr_t	key,
		bool *	found )

Looks up a given key in the dictionary.

Parameters

d	The dictionary.
key	The key to search for.
found	Out parameter, set to TRUE if the key is found. Can be NULL if the information is not required.

Returns

The key stored in the dictionary, or NULL if no such key is found.

The returned value belongs to the dictionary and should not be modified.

This function is useful for example when "interning" values: one can look up the stored copy of the key passed as a parameter and use it, freeing the original.

SOPC_Dict_Remove()

void SOPC_Dict_Remove	(	SOPC_Dict *	d,
		const uintptr_t	key )

Removes a values from the dictionary.

Parameters

d	The dictionary.
key	The key to remove.

For removals to be supported, a tombstone key MUST have been set before using SOPC_Dict_SetTombstoneKey. Otherwise an assertion failure will occur.

SOPC_Dict_GetKeyFreeFunc()

SOPC_Dict_Free_Fct * SOPC_Dict_GetKeyFreeFunc

(

const SOPC_Dict *

d

)

Retrieves the free function for this dictionary's keys.

Parameters

d	The dictionary.

Returns

The function used to free the keys, or NULL if no such function was set.

SOPC_Dict_SetKeyFreeFunc()

void SOPC_Dict_SetKeyFreeFunc	(	SOPC_Dict *	d,
		SOPC_Dict_Free_Fct *	func )

Sets the free function for this dictionary's keys.

Parameters

d	The dictionary.
func	The function to use when freeing keys.

SOPC_Dict_GetValueFreeFunc()

SOPC_Dict_Free_Fct * SOPC_Dict_GetValueFreeFunc

(

const SOPC_Dict *

d

)

Retrieves the free function for this dictionary's values.

Parameters

d	The dictionary.

Returns

The function used to free the values, or NULL if no such function was set.

SOPC_Dict_SetValueFreeFunc()

void SOPC_Dict_SetValueFreeFunc	(	SOPC_Dict *	d,
		SOPC_Dict_Free_Fct *	func )

Sets the free function for this dictionary's values.

Parameters

d	The dictionary.
func	The function to use when freeing values.

SOPC_Dict_Size()

size_t SOPC_Dict_Size

(

const SOPC_Dict *

d

)

Returns the number of items in this dictionary.

Parameters

d	The dictionary.

Returns

The number of items in the dictionary.

SOPC_Dict_Capacity()

size_t SOPC_Dict_Capacity

(

const SOPC_Dict *

d

)

Returns the number if items this dictionary can hold.

Parameters

d	The dictionary.

Returns

The number of items the dictionary can hold.

The dictionary will grow its capacity as needed when inserting new items, and reduce it after enough items are removed.

SOPC_Dict_ForEach()

void SOPC_Dict_ForEach	(	SOPC_Dict *	d,
		SOPC_Dict_ForEach_Fct *	func,
		uintptr_t	user_data )

Iterates over the dictionary, calling the given function for each (key, value) pair.

Parameters

d	The dictionary.
func	The function to call on each (key, value) pair.
user_data	A user chose pointer to pass as last parameter to the callback function.

The order of the iteration is implementation defined, and should not be relied on.