RobinHoodHash Struct Reference

RobinHoodHash is an opaque object that manage associations of fixed length key-value pairs. More...

Related Functions
(Note that these are not member functions.)
bool	RHHNew (OPHeap *heap, RobinHoodHash **rhh_ref, uint64_t num_objects, double load, size_t keysize, size_t valsize)
	Constructor for RobinHoodHash. More...
void	RHHDestroy (RobinHoodHash *rhh)
	Destructor for RobinHoodHash. More...
bool	RHHInsertCustom (RobinHoodHash *rhh, OPHash hasher, void *key, void *val)
	Associates the specified key with the specified value in RobinHoodHash with specified hash function. More...
bool	RHHUpsertCustom (RobinHoodHash *rhh, 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 *	RHHGetCustom (RobinHoodHash *rhh, 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 *	RHHDeleteCustom (RobinHoodHash *rhh, OPHash hasher, void *key)
	Deletes the key-value entry in hash table with specified hasher. More...
static bool	RHHInsert (RobinHoodHash *rhh, void *key, void *val)
	Associates the specified key with the specified value in RobinHoodHash using the default hash function. More...
static bool	RHHUpsert (RobinHoodHash *rhh, 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 *	RHHGet (RobinHoodHash *rhh, 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 *	RHHDelete (RobinHoodHash *rhh, void *key)
	Deletes the key-value entry in hash table using the default hash function. More...
uint64_t	RHHObjcnt (RobinHoodHash *rhh)
	Obtain the number of objects stored in this hash table.
uint64_t	RHHCapacity (RobinHoodHash *rhh)
	Obtain the number of objects can be stored in this hash table.
size_t	RHHKeysize (RobinHoodHash *rhh)
	Obtain the size of the key configured for this hash table.
size_t	RHHValsize (RobinHoodHash *rhh)
	Obtain the size of the value configured for this hash table.
void	RHHIterate (RobinHoodHash *rhh, OPHashIterator iterator, void *context)
	Iterates over all key-value pairs in this hash table with user specified context. More...
void	RHHPrintStat (RobinHoodHash *rhh)
	Prints the accumulated count for each probing number. More...

Detailed Description

RobinHoodHash is 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 RobinHoodHash, 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 RobinHoodHash 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 RobinHoodHash into a hash-multiset.

This object is not thread safe.

Friends And Related Function Documentation

RHHNew()

bool RHHNew ( OPHeap *  heap, RobinHoodHash **  rhh_ref, uint64_t  num_objects, double  load, size_t  keysize, size_t  valsize  )

related

Constructor for RobinHoodHash.

Parameters

heap	OPHeap instance.
rhh_ref	reference to the RobinHoodHash pointer for assigining RobinHoodHash 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

true when the allocation succeeded, false otherwise.

Definition at line 115 of file robin_hood.c.

RHHDestroy()

void RHHDestroy ( RobinHoodHash *  rhh )

related

Destructor for RobinHoodHash.

Parameters

rhh	the RobinHoodHash instance to destory.

Definition at line 156 of file robin_hood.c.

RHHInsertCustom()

bool RHHInsertCustom ( RobinHoodHash *  rhh, OPHash  hasher, void *  key, void *  val  )

related

Associates the specified key with the specified value in RobinHoodHash with specified hash function.

Parameters

rhh	RobinHoodHash 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.

Definition at line 615 of file robin_hood.c.

RHHUpsertCustom()

bool RHHUpsertCustom ( RobinHoodHash *  rhh, OPHash  hasher, void *  key, void **  val_ref, bool *  is_duplicate  )

related

Update or insert depends on whether the key already exists in the hash table using custom hash function.

Parameters

rhh	RobinHoodHash 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;
RobinHoodHash *rhh;
// create a robin hood hash where key and value are both integers.
RHHNew(heap, &rhh, 30, 0.8, sizeof(int), sizeof(int));
key = 5;
RHHUpsert(rhh, 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.

Definition at line 622 of file robin_hood.c.

RHHGetCustom()

void * RHHGetCustom ( RobinHoodHash *  rhh, OPHash  hasher, void *  key  )

related

Obtain the value associated with the specified key and hash function. Returns NULL if the key was not found.

Parameters

rhh	RobinHoodHash 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, RHHGetCustom 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 702 of file robin_hood.c.

RHHDeleteCustom()

void * RHHDeleteCustom ( RobinHoodHash *  rhh, OPHash  hasher, void *  key  )

related

Deletes the key-value entry in hash table with specified hasher.

Parameters

rhh	RobinHoodHash 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.

Definition at line 830 of file robin_hood.c.

RHHInsert()

static bool RHHInsert ( RobinHoodHash *  rhh, void *  key, void *  val  )

related

Associates the specified key with the specified value in RobinHoodHash using the default hash function.

Parameters

rhh	RobinHoodHash 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 199 of file robin_hood.h.

RHHUpsert()

static bool RHHUpsert ( RobinHoodHash *  rhh, void *  key, void **  val_ref, bool *  is_duplicate  )

related

Update or insert depends on whether the key already exists in the hash table.

Parameters

rhh	RobinHoodHash 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;
RobinHoodHash *rhh;
// create a robin hood hash where key and value are both integers.
RHHNew(heap, &rhh, 30, 0.8, sizeof(int), sizeof(int));
key = 5;
RHHUpsert(rhh, &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 240 of file robin_hood.h.

RHHGet()

static void * RHHGet ( RobinHoodHash *  rhh, void *  key  )

related

Obtain the value associated with the specified key using the default hash function. Returns NULL if the key was not found.

Parameters

rhh	RobinHoodHash instance.
key	pointer to the key.

Returns

pointer to the value if found, else NULL.

If the value size were set to 0, RHHGetCustom 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 259 of file robin_hood.h.

RHHDelete()

static void * RHHDelete ( RobinHoodHash *  rhh, void *  key  )

related

Deletes the key-value entry in hash table using the default hash function.

Parameters

rhh	RobinHoodHash 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 276 of file robin_hood.h.

RHHIterate()

void RHHIterate ( RobinHoodHash *  rhh, OPHashIterator  iterator, void *  context  )

related

Iterates over all key-value pairs in this hash table with user specified context.

Parameters

rhh	RobinHoodHash 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;

// RHHIterate takes in a RobinHoodHash object, a fuction pointer
// OPHashIterator and a user defined context for iteration.
RHHIterate(rhh, &my_iterator, &my_s);

Definition at line 837 of file robin_hood.c.

RHHPrintStat()

void RHHPrintStat ( RobinHoodHash *  rhh )

related

Prints the accumulated count for each probing number.

Definition at line 856 of file robin_hood.c.

---

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

• opic/hash/robin_hood.h