An opaque object that manage associations of fixed length key-value pairs. More...

Related Functions
(Note that these are not member functions.)
OPHashTable *	HTNew (OPHeap *heap, uint64_t num_objects, double load, size_t keysize, size_t valsize)
	Constructor for OPHashTable. More...

void	HTDestroy (OPHashTable *table)
	Destructor for OPHashTable. More...

bool	HTInsertCustom (OPHashTable table, OPHash hasher, void key, void *val)
	Associates the specified key with the specified value in OPHashTable with specified hash function. More...

bool	HTUpsertCustom (OPHashTable table, OPHash hasher, void key, void *val_ref, bool is_duplicate)
	Update or insert depends on whether the key already exists in the hash table using custom hash function. More...

void *	HTGetCustom (OPHashTable table, OPHash hasher, void key)
	Obtain the value associated with the specified key and hash function. Returns NULL if the key was not found. More...

void *	HTDeleteCustom (OPHashTable table, OPHash hasher, void key)
	Deletes the key-value entry in hash table with specified hasher. More...

static bool	HTInsert (OPHashTable table, void key, void *val)
	Associates the specified key with the specified value in OPHashTable using the default hash function. More...

static bool	HTUpsert (OPHashTable table, void key, void *val_ref, bool is_duplicate)
	Update or insert depends on whether the key already exists in the hash table. More...

static void *	HTGet (OPHashTable table, void key)
	Obtain the value associated with the specified key using the default hash function. Returns NULL if the key was not found. More...

static void *	HTDelete (OPHashTable table, void key)
	Deletes the key-value entry in hash table using the default hash function. More...

uint64_t	HTObjcnt (OPHashTable *table)
	Obtain the number of objects stored in this hash table.

uint64_t	HTCapacity (OPHashTable *table)
	Obtain the number of objects can be stored in this hash table.

size_t	HTKeySize (OPHashTable *table)
	Obtain the size of the key configured for this hash table.

size_t	HTValSize (OPHashTable *table)
	Obtain the size of the value configured for this hash table.

void	HTIterate (OPHashTable table, OPHashIterator iterator, void context)
	Iterates over all key-value pairs in this hash table with user specified context. More...

void	HTPrintStat (OPHashTable *table)
	Prints the accumulated count for each probing number. More...

Detailed Description

An opaque object that manage associations of fixed length key-value pairs.

The size of key and value is configured at the construction time of OPHashTable, and can not be changed later. This design is similar to fixed length fields CHAR(30) in SQL which improve both space and runtime efficiencies.

Note that user can spcify size of value to 0 to make OPHashTable as a hash set. Similarly, make value size sizeof(opref_t) and store a opref_t referencing another container (binary serach tree or whatever), can turn OPHashTable into a hash-multiset.

This object is not thread safe.

Friends And Related Function Documentation

◆ HTNew()

OPHashTable * HTNew	(	OPHeap *	heap,
		uint64_t	num_objects,
		double	load,
		size_t	keysize,
		size_t	valsize
	)

Parameters

heap	OPHeap instance.
num_objects	number of objects we decided to put in.
load	(0.0-1.0) how full the hash table could be before expansion.
keysize	length of key measured in bytes. Cannot be zero.
valsize	length of value measured in bytes. This vlaue can be zero and the hash table would work like a hash set.

Returns: OPHashTable instance if allocation succeeded, else return NULL.

◆ HTDestroy()

void HTDestroy ( OPHashTable * table )

Parameters

table the OPHashTable instance to destory.

◆ HTInsertCustom()

bool HTInsertCustom	(	OPHashTable *	table,
		OPHash	hasher,
		void *	key,
		void *	val
	)

Parameters

table	OPHashTable instance.
hasher	hash function.
key	pointer to the key.
val	pointer to the value.

Returns: true if the operation succeeded, false otherwise.

The content pointed by key and val will be copied into the hash table. If the value size were 0, only the key get copied. When there's a key collision, the coresponding value get replaced.

If the inserted key-value pairs exceeded the original size user configured, the hash table will resized with a larger capacity. If the resize failed, false is returned.

◆ HTUpsertCustom()

bool HTUpsertCustom	(	OPHashTable *	table,
		OPHash	hasher,
		void *	key,
		void **	val_ref,
		bool *	is_duplicate
	)

Parameters

table	OPHashTable instance.
hasher	hash function.
key	pointer to the key.
val_ref	reference of value pointer.
is_duplicate	reference of duplication boolean variable.

Returns: true if the operation succeeded, false otherwise.

This method does not insert the value automatically, instead it provides the pointer to the address where value can be inserted or overriden.

int key;
int* value;
bool is_duplicate;
OPHashTable *table;
// create a robin hood hash where key and value are both integers.
HTNew(heap, &table, 30, 0.8, sizeof(int), sizeof(int));
key = 5;
HTUpsert(table, OPDefaultHash, &key, (void**)&val, &is_duplicate);
// different logic depends on is_duplicate.
// User can use this interface to create a hash multimap.
if (is_duplicate)
  *value = 7;
else
  *value = 8;

If the inserted key-value pairs exceeded the original size user configured, the hash table will resized with a larger capacity. If the resize failed, false is returned.

◆ HTGetCustom()

void * HTGetCustom	(	OPHashTable *	table,
		OPHash	hasher,
		void *	key
	)

Parameters

table	OPHashTable instance.
hasher	hash function.
key	pointer to the key.

Returns: pointer to the value if found, else NULL.

If the value size were set to 0, HTGetCustom would still return a pointer to where it would store the value. User can still use the returned value to exam if the key were present in the hash table.

◆ HTDeleteCustom()

void * HTDeleteCustom	(	OPHashTable *	table,
		OPHash	hasher,
		void *	key
	)

Parameters

table	OPHashTable instance.
hasher	hash function.
key	pointer to the key.

Returns: pointer to the value if it found, else NULL.

The hash table may shrink if too many entries were deleted.

◆ HTInsert()

static bool HTInsert	(	OPHashTable *	table,
		void *	key,
		void *	val
	)

Parameters

table	OPHashTable instance.
key	pointer to the key.
val	pointer to the value.

Returns: true if the operation succeeded, false otherwise.

The content pointed by key and val will be copied into the hash table. If the value size were 0, only the key get copied. When there's a key collision, the coresponding value get replaced.

If the inserted key-value pairs exceeded the original size user configured, the hash table will resized with a larger capacity. If the resize failed, false is returned.

Definition at line 200 of file op_hash_table.h.

◆ HTUpsert()

static bool HTUpsert	(	OPHashTable *	table,
		void *	key,
		void **	val_ref,
		bool *	is_duplicate
	)

Parameters

table	OPHashTable instance.
key	pointer to the key.
val_ref	reference of value pointer.
is_duplicate	reference of duplication boolean variable.

Returns: true if the operation succeeded, false otherwise.

This method does not insert the value automatically, instead it provides the pointer to the address where value can be inserted or overriden.

int key;
int* value;
bool is_duplicate;
OPHashTable *table;
// create a robin hood hash where key and value are both integers.
HTNew(heap, &table, 30, 0.8, sizeof(int), sizeof(int));
key = 5;
HTUpsert(table, &key, (void**)&val, &is_duplicate);
// different logic depends on is_duplicate.
// User can use this interface to create a hash multimap.
if (is_duplicate)
  *value = 7;
else
  *value = 8;

If the inserted key-value pairs exceeded the original size user configured, the hash table will resized with a larger capacity. If the resize failed, false is returned.

Definition at line 241 of file op_hash_table.h.

◆ HTGet()

static void * HTGet	(	OPHashTable *	table,
		void *	key
	)

Parameters

table	OPHashTable instance.
key	pointer to the key.

Returns: pointer to the value if found, else NULL.

If the value size were set to 0, HTGetCustom would still return a pointer to where it would store the value. User can still use the returned value to exam if the key were present in the hash table.

Definition at line 260 of file op_hash_table.h.

◆ HTDelete()

static void * HTDelete	(	OPHashTable *	table,
		void *	key
	)

Parameters

table	OPHashTable instance.
key	pointer to the key.

Returns: pointer to the value if it found, else NULL.

The hash table may shrink if too many entries were deleted.

Definition at line 277 of file op_hash_table.h.

◆ HTIterate()

void HTIterate	(	OPHashTable *	table,
		OPHashIterator	iterator,
		void *	context
	)

Parameters

table	OPHashTable instance.
iterator	function pointer to user defined iterator function.
context	user defined context.

// Function interface matches OPHashIterator
void my_iterator(void* key, void* value,
                 size_t keysize, size_t valsize,
                 void* context)
{
  // Obtain the object we passed in.
  struct MyStruct* my_s = (struct MyStruct*) context;
  // assumes both key and value were null terminated string
  printf("key: %s, value: %s\n", key, value);
}
// User defined context
struct MyStruct my_s;
// HTIterate takes in a OPHashTable object, a fuction pointer
// OPHashIterator and a user defined context for iteration.
HTIterate(table, &my_iterator, &my_s);

◆ HTPrintStat()

void HTPrintStat ( OPHashTable * table )

Deprecated. Use HTProbeStat instead.

The documentation for this struct was generated from the following file:

opic/hash/op_hash_table.h

Related Functions

Detailed Description

Friends And Related Function Documentation

◆ HTNew()

◆ HTDestroy()

◆ HTInsertCustom()

◆ HTUpsertCustom()

◆ HTGetCustom()

◆ HTDeleteCustom()

◆ HTInsert()

◆ HTUpsert()

◆ HTGet()

◆ HTDelete()

◆ HTIterate()

◆ HTPrintStat()