Skip to content

Add isc_hashmap API that implements Robin Hood hashing

Ondřej Surý requested to merge ondrej-add-isc_hashmap into main

Add new isc_hashmap API that differs from the current isc_ht API in several aspects:

  1. It implements Robin Hood Hashing which is open-addressing hash table algorithm (e.g. no linked-lists)

  2. No memory allocations - the isc_hashmap_node_t structure MUST be part of the stored value and the isc_hashmap_add() function takes the offset of the isc_hashmap_node_t in the value.

  3. The key must be also stored in the stored value or elsewhere, it's not copied into the isc_hashmap_node_t, but rather only pointer is stored.

This makes the isc_hashmap_t less universal because of the constraints put on the stored data, but it's blazingly fast because it doesn't require memory allocation on isc_hashmap_add() and memory deallocation on isc_hashmap_delete().

Edited by Ondřej Surý

Merge request reports