phashtable.h File Reference

Hash table. More...

#include <pmacros.h>
#include <ptypes.h>
#include <plist.h>

Include dependency graph for phashtable.h:

Go to the source code of this file.

Typedefs
typedef typedefP_BEGIN_DECLS struct PHashTable_	PHashTable
	Opaque data structure for a hash table. More...

Functions
P_LIB_API PHashTable *	p_hash_table_new (void)
	Initializes a new hash table. More...
P_LIB_API void	p_hash_table_insert (PHashTable *table, ppointer key, ppointer value)
	Inserts a new key-value pair into a hash table. More...
P_LIB_API ppointer	p_hash_table_lookup (const PHashTable *table, pconstpointer key)
	Searches for a specifed key in the hash table. More...
P_LIB_API PList *	p_hash_table_keys (const PHashTable *table)
	Gives a list of all the stored keys in the hash table. More...
P_LIB_API PList *	p_hash_table_values (const PHashTable *table)
	Gives a list of all the stored values in the hash table. More...
P_LIB_API void	p_hash_table_free (PHashTable *table)
	Frees a previously initialized PHashTable. More...
P_LIB_API void	p_hash_table_remove (PHashTable *table, pconstpointer key)
	Removes key from a hash table. More...
P_LIB_API PList *	p_hash_table_lookup_by_value (const PHashTable *table, pconstpointer val, PCompareFunc func)
	Searches for a specifed key in the hash table by its value. More...

Detailed Description

Hash table.

Author

Alexander Saprykin

A hash table is a data structure used to map keys to values. The hash table consists of several internal slots which hold a list of values. A hash function is used to compute an index in the array of the slots from a given key. The hash function itself is fast and it takes a constant time to compute the internal slot index.

When the number of pairs in the hash table is small the lookup and insert (remove) operations are very fast and have average complexity O(1), because every slot holds almost the only one pair. As the number of internal slots is fixed, the increasing number of pairs will lead to degraded performance and the average complexity of the operations can drop to O(N) in the worst case. This is because the more pairs are inserted the more longer the list of values is placed in every slot.

This is a simple hash table implementation which is not intended for heavy usage (several thousands), see PTree if you need the best performance on large data sets. This implementation doesn't support multi-inserts when several values belong to the same key.

Note that PHashTable stores keys and values only as pointers, so you need to free used memory manually, p_hash_table_free() will not do it in any way.

Integers (up to 32 bits) can be stored in pointers using P_POINTER_TO_INT and P_INT_TO_POINTER macros.

Typedef Documentation

PHashTable

typedef typedefP_BEGIN_DECLS struct PHashTable_ PHashTable

Opaque data structure for a hash table.

Function Documentation

p_hash_table_free()

P_LIB_API void p_hash_table_free

(

PHashTable *

table

)

Frees a previously initialized PHashTable.

Parameters

table

Hash table to free.

Since

0.0.1

p_hash_table_insert()

P_LIB_API void p_hash_table_insert	(	PHashTable *	table,
		ppointer	key,
		ppointer	value
	)

Inserts a new key-value pair into a hash table.

Parameters

table	Initialized hash table.
key	Key to insert.
value	Value to insert.

Since

0.0.1

This function only stores pointers, so you need to manually free pointed data after using the hash table.

p_hash_table_keys()

P_LIB_API PList* p_hash_table_keys

(

const PHashTable *

table

)

Gives a list of all the stored keys in the hash table.

Parameters

table

Hash table to collect the keys from.

Returns

List of all the stored keys, the list can be empty if no keys were found.

Since

0.0.1

Note

You should manually free the returned list with p_list_free() after using it.

p_hash_table_lookup()

P_LIB_API ppointer p_hash_table_lookup	(	const PHashTable *	table,
		pconstpointer	key
	)

Searches for a specifed key in the hash table.

Parameters

table	Hash table to lookup in.
key	Key to lookup for.

Returns

Value related to its key pair (can be NULL), (ppointer) -1 if no value was found.

Since

0.0.1

p_hash_table_lookup_by_value()

P_LIB_API PList* p_hash_table_lookup_by_value	(	const PHashTable *	table,
		pconstpointer	val,
		PCompareFunc	func
	)

Searches for a specifed key in the hash table by its value.

Parameters

table	Hash table to lookup in.
val	Value to lookup keys for.
func	Function to compare table's values with val, if NULL then values will be compared as pointers.

Returns

List of the keys with val (can be NULL), NULL if no keys were found.

Since

0.0.1

Note

Caller is responsible to call p_list_free() on the returned list after usage.

The compare function should return 0 if a value from the hash table (the first parameter) is accepted related to the given lookup value (the second parameter), and -1 or 1 otherwise.

p_hash_table_new()

P_LIB_API PHashTable* p_hash_table_new

(

void

)

Initializes a new hash table.

Returns

Pointer to a newly initialized PHashTable structure in case of success, NULL otherwise.

Since

0.0.1

Note

Free with p_hash_table_free() after usage.

p_hash_table_remove()

P_LIB_API void p_hash_table_remove	(	PHashTable *	table,
		pconstpointer	key
	)

Removes key from a hash table.

Parameters

table	Hash table to remove the key from.
key	Key to remove (if exists).

Since

0.0.1

p_hash_table_values()

P_LIB_API PList* p_hash_table_values

(

const PHashTable *

table

)

Gives a list of all the stored values in the hash table.

Parameters

table

Hash table to collect the values from.

Returns

List of all the stored values, the list can be empty if no keys were found.

Since

0.0.1

Note

You should manually free the returned list with p_list_free() after using it.