|
Harlequin RIP SDK
|
|
|
|
Harlequin RIP SDK
|
|
Generic Robin Hood hash map. More...
Files | |
| file | rhhashmap.h |
| A generally useful Robin Hood hash map implementation. | |
Generic Robin Hood hash map.
A Robin Hood hash map is an open addressed hash map, which uses linear probing, but minimises the variance of the probe sequence. With a good hash function, the worst case probe length will be very short.
Robin Hood hash maps can operate at very high load factors without suffering significant performance loss.
This implementation allows the key and/or value to be simple values, or references managed by the caller. Memory allocation and deallocation functions for the hash map are supplied by the caller (rh_alloc_fn, rh_free_fn). The hashing function (rh_hash_fn) and a key comparison function (rh_key_equal_fn) may be supplied by the caller. Operations to insert, delete, search, iterate, and destroy the hash map are provided.
A Robin Hood hash map is represented by an rh_hashmap_t structure. This is created and returned by rh_hashmap_create(), and destroyed by rh_hashmap_destroy().
Insertion, deletion, and replacement of values in a hash map are supported by the rh_hashmap_replace() function. This function inserts a key and value into a hash map, returning the previous value associated with the key.
The rh_hashmap_search() function returns the associated value for a key, if present.
The entire hash map may be iterated using rh_hashmap_iterate(), supplying a callback function (rh_iterate_fn) to visit each key and value pair. The order in which values are iterated is not guaranteed to be predictable or remain the same between iterations.
Hash maps may be resized if a resize function (rh_resize_fn) is supplied on creation. The resize function is called to expand or contract the size of the hash map depending on the load factor of the hash map. The resize function sets how much to expand or reduce the hash map, and can enforce minimum and/or maximum sizes, cache line multiples, or ensure that the hashing strategy works with the new size good. There is some hysteresis in resizing hash maps. The implementation guarantees that expansion is called before the hash map is completely full, which allows lazy allocation strategies or insertion inside a lock where allocation is not allowed.
The key and/or value may be stored as references, rather than simple data. When inserting an entry into a hash map, the ownership of a reference is transferred to the hash map. When replacing the entry or destroying a hash map, a key or value release function (rh_release_key_fn, rh_release_value_fn) will be called to remove references from the hash map's ownership, if the function was supplied on hash map creation.