hashmap.c File Reference

Notes: More...

#include "serene/rt/impl/hashmap.h"
#include <assert.h>
#include <stdint.h>
#include <string.h>
#include "serene/rt/context.h"
#include "serene/rt/engine.h"
#include "serene/utils.h"

Include dependency graph for hashmap.c:

Go to the source code of this file.

Data Structures
struct	hmap_collision_t
	A simple alist to manage collision nodes. More...

Macros
#define	HMAP_LOG(...)

Typedefs
typedef struct hmap_collision_t	hmap_collision_t
	A simple alist to manage collision nodes.

Functions
static bool	is_collision_node (void *p)
	Return true if the pointer's LSB is 1 indicating a collision.
static hmap_collision_t *	untag_ptr (void *ptr)
	Since for non collision nodes the LSB is 0 then we don't need to untag it.
static void *	tag_ptr (void *ptr)
hmap_hash_t	hmap_hash (const srn_context_t *ctx, const void *data, size_t len)
	This is a simple hack to mock the hash function during tests to force a high collision hashing function.
static bool	hmap_key_equal (const hmap_key_t *a, const hmap_key_t *b)
	Compare key a with key b.
static bool	is_key_in_collision_node (const hmap_control_t *ctl, const hmap_t *hmap, hmap_collision_t *head, hmap_hash_t hash, hmap_key_t *k)
static uint32_t	hmap_hash_fragment (hmap_hash_t hash, uint8_t shift)
	Extract a HMAP_MAK-bit chunk from the hash at the given shift.
static hmap_bitmap_t	hmap_bitpos (hmap_hash_t hash, uint8_t shift)
	Bit position corresponding to this fragment.
static size_t	hmap_popcount (hmap_bitmap_t bm)
static size_t	hmap_number_of_entries (const hmap_node_t *node)
	Number of entries (data + node) in a node regardless of a data pointer or a node pointer.
static size_t	hmap_entry_index (const hmap_node_t *node, hmap_bitmap_t bitpos)
	Index in the packed entries array for a given bitpos (either datamap or nodemap).
static bool	hmap_has_data_at (const hmap_node_t *node, hmap_bitmap_t bitpos)
	Is this bitpos occupied by a data (kv) entry?
static bool	hmap_has_node_at (const hmap_node_t *node, hmap_bitmap_t bitpos)
	Is this bitpos occupied by a child node?
static void *	hmap_get_entry_at (const hmap_node_t *node, hmap_bitmap_t bitpos)
	Make sure the result with is_collision_node and case the result to either an entry or a collision node.
static hmap_node_t *	hmap_get_child_at (const hmap_node_t *node, hmap_bitmap_t bitpos)
	Fetch the child node pointer at a given bitpos; we must ensure nodemap has this bit.
static bool	hmap_at_max_depth (uint32_t shift)
static hmap_kv_entry_t *	hmap_new_kv_entry (const srn_context_t *ctx, hmap_hash_t hash, hmap_key_t *k, void *v)
	Abstract away the kv entry allocation.
static hmap_node_t *	create_empty_node (const srn_context_t *ctx)
static hmap_node_t *	hmap_singleton_node (const srn_context_t *ctx, hmap_hash_t hash, uint32_t shift, hmap_kv_entry_t *kv)
static hmap_data_t *	hmap_copy_entries (const srn_context_t *ctx, hmap_data_t *entries, size_t count)
	Copy entries array into a new one, returning pointer.
static hmap_node_t *	hmap_merge_two_kv (const srn_context_t *ctx, hmap_kv_entry_t *kv1, hmap_kv_entry_t *kv2, uint32_t shift)
	Merge two distinct kv entries into a sub-trie.
static hmap_node_t *	hmap_insert_node (const hmap_control_t *ctl, const hmap_t *hmap, const hmap_node_t *node, hmap_hash_t hash, hmap_key_t *k, void *v, uint32_t shift, bool *out_added)
	Recursively insert a new node containing the k and v.
static void *	hmap_lookup_in_collision (const hmap_control_t *ctl, const hmap_t *hmap, hmap_collision_t *cnode, hmap_hash_t hash, const hmap_key_t *k, void *default_value)
static void *	hmap_lookup_in_node (const hmap_control_t *ctl, const hmap_t *hmap, const hmap_node_t *node, hmap_hash_t hash, const hmap_key_t *k, uint32_t shift, void *default_value)
static bool	hmap_internal_cmp (const hmap_t *hmap, const hmap_key_t *a, const hmap_key_t *b)
static hmap_hash_t	hmap_hash_internal (const hmap_t *hmap, const hmap_key_t *k)
hmap_t	hmap_insert_ctl (const hmap_control_t *ctl, const hmap_t *hmap, hmap_key_t *k, void *v)
	Just like the hmap_insert function but, it receives a hmap_control_t to customize the comparison and hashing function.
void *	hmap_lookup_ctl (const hmap_control_t *ctl, const hmap_t *hmap, const hmap_key_t *k, void *default_value)
	Just like the hmap_lookup function but, it receives a hmap_control_t to customize the comparison and hashing function.
hmap_t	hmap_empty (const srn_context_t *ctx)
	Create, initialize and return a new hashmap pinned to ctx.
hmap_t	hmap_insert (const hmap_t *hmap, hmap_key_t *k, void *v)
	Insert the given key k with the value v in the given hash hmap and return the new map.
void *	hmap_lookup (const hmap_t *hmap, const hmap_key_t *k, void *default_value)
	Lookup the given k in the given hmap and return the value if it's been found.
hmap_key_t *	hmap_make_key (srn_context_t *ctx, void *data, size_t len)
	Create a new key out of the given data, with the given len.
hmap_key_t *	hmap_copy_key (const hmap_t *hmap, const hmap_key_t *k)
	The default copy_key hook.

Variables
hmap_control_t	hmap_default_control

Detailed Description

Notes:

• Persistent, old nodes are never mutated.
• hmap_node_t->entries is a single mixed array. Positions are determined by the ascending order of set bits in (datamap | nodemap). For a given bit:
  • if bit ∈ datamap -> entries[idx] is (hmap_kv_entry_t*) OR a tagged collision*
  • if bit ∈ nodemap -> entries[idx] is (hmap_node_t*)
• Collision lists are stored in data positions (datamap bit set) by tagging the pointer's LSB = 1. Normal child nodes have LSB = 0.
  • Collisions are linked lists that form an associated list.

Safety: pointers returned by srn_allocate are naturally aligned. We only use LSB tagging for child pointers (never for kv pointers). Untag before deref.

Definition in file hashmap.c.

Macro Definition Documentation

HMAP_LOG

#define HMAP_LOG

(

...

)

Definition at line 48 of file hashmap.c.

Typedef Documentation

hmap_collision_t

typedef struct hmap_collision_t hmap_collision_t

A simple alist to manage collision nodes.

Function Documentation

create_empty_node()

hmap_node_t * create_empty_node ( const srn_context_t * ctx )

inlinestatic

Definition at line 196 of file hashmap.c.

                                                                       {
  assert(ctx != nullptr);
  hmap_node_t *n = ALLOC(ctx, hmap_node_t);
  n->nodemap     = 0;
  n->datamap     = 0;
  n->entries     = nullptr;
  return n;
}

Here is the caller graph for this function:

hmap_at_max_depth()

bool hmap_at_max_depth ( uint32_t shift )

inlinestatic

Definition at line 181 of file hashmap.c.

                                                     {
  return shift + HMAP_SHIFT >= HMAP_HASH_SIZE;
}

Here is the caller graph for this function:

hmap_bitpos()

hmap_bitmap_t hmap_bitpos ( hmap_hash_t hash, uint8_t shift )

inlinestatic

Bit position corresponding to this fragment.

Definition at line 137 of file hashmap.c.

                                                                         {
  return (hmap_bitmap_t)1U << hmap_hash_fragment(hash, shift);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_copy_entries()

hmap_data_t * hmap_copy_entries ( const srn_context_t * ctx, hmap_data_t * entries, size_t count )

static

Copy entries array into a new one, returning pointer.

Definition at line 221 of file hashmap.c.

                                                                                {
  if (count == 0) {
    return nullptr;
  }
  hmap_data_t *new_entries = ALLOCN(ctx, hmap_data_t, count);
  for (size_t i = 0; i < count; ++i) {
    new_entries[i] = entries[i];
  }
  return new_entries;
}

Here is the caller graph for this function:

hmap_copy_key()

hmap_key_t * hmap_copy_key	(	const hmap_t *	hmap,
		const hmap_key_t *	k )

The default copy_key hook.

Clone the key struct and its bytes into the map's map_ctx so the map never retains pointers into a caller's block.

Definition at line 678 of file hashmap.c.

                                                                   {
  PANIC_IF_NULL(hmap);
  PANIC_IF_NULL(k);
  PANIC_IF_NULL(hmap->map_ctx);
 
  hmap_key_t *copy = ALLOC(hmap->map_ctx, hmap_key_t);
  copy->len        = k->len;
  copy->data =
    (k->len == 0) ? nullptr : srn_copy_bytes(hmap->map_ctx, k->data, k->len, alignof(char));
  return copy;
}

Here is the call graph for this function:

hmap_empty()

hmap_t hmap_empty ( const srn_context_t * ctx )

nodiscard

Create, initialize and return a new hashmap pinned to ctx.

The pinned context owns every allocation the map (and all of its future versions) retains, so pick a context that lives at least as long as the map.

Definition at line 655 of file hashmap.c.

                                            {
  PANIC_IF_NULL(ctx);
  hmap_t map = {.len = 0, .root = nullptr, .map_ctx = ctx};
  return map;
}

Here is the caller graph for this function:

hmap_entry_index()

size_t hmap_entry_index ( const hmap_node_t * node, hmap_bitmap_t bitpos )

inlinestatic

Index in the packed entries array for a given bitpos (either datamap or nodemap).

Definition at line 151 of file hashmap.c.

                                                                                     {
  // Basically we're trying to count the set bits befor `before`
  // and use it as the index in the packed entries
  hmap_bitmap_t before = (node->datamap | node->nodemap) & (bitpos - 1U);
  return hmap_popcount(before);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_get_child_at()

hmap_node_t * hmap_get_child_at ( const hmap_node_t * node, hmap_bitmap_t bitpos )

inlinestatic

Fetch the child node pointer at a given bitpos; we must ensure nodemap has this bit.

Definition at line 176 of file hashmap.c.

                                                                                            {
  size_t idx = hmap_entry_index(node, bitpos);
  return (hmap_node_t *)node->entries[idx];
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_get_entry_at()

void * hmap_get_entry_at ( const hmap_node_t * node, hmap_bitmap_t bitpos )

inlinestatic

Make sure the result with is_collision_node and case the result to either an entry or a collision node.

Definition at line 170 of file hashmap.c.

                                                                                     {
  return node->entries[hmap_entry_index(node, bitpos)];
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_has_data_at()

bool hmap_has_data_at ( const hmap_node_t * node, hmap_bitmap_t bitpos )

inlinestatic

Is this bitpos occupied by a data (kv) entry?

Definition at line 159 of file hashmap.c.

                                                                                   {
  return (node->datamap & bitpos) != 0;
}

Here is the caller graph for this function:

hmap_has_node_at()

bool hmap_has_node_at ( const hmap_node_t * node, hmap_bitmap_t bitpos )

inlinestatic

Is this bitpos occupied by a child node?

Definition at line 164 of file hashmap.c.

                                                                                   {
  return (node->nodemap & bitpos) != 0;
}

Here is the caller graph for this function:

hmap_hash()

hmap_hash_t hmap_hash	(	const srn_context_t *	ctx,
		const void *	data,
		size_t	len )

This is a simple hack to mock the hash function during tests to force a high collision hashing function.

Outside of tests, this will be a wrapper around srn_hash.

Definition at line 77 of file hashmap.c.

                                                                              {
  return srn_hash(ctx->engine, data, len);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_hash_fragment()

uint32_t hmap_hash_fragment ( hmap_hash_t hash, uint8_t shift )

inlinestatic

Extract a HMAP_MAK-bit chunk from the hash at the given shift.

Definition at line 129 of file hashmap.c.

                                                                           {
  /* if (shift > 32) { */
  /*   PANIC("'shift' should be less than 32\n"); */
  /* } */
  return (hash >> shift) & HMAP_MASK;
}

Here is the caller graph for this function:

hmap_hash_internal()

hmap_hash_t hmap_hash_internal ( const hmap_t * hmap, const hmap_key_t * k )

static

Definition at line 589 of file hashmap.c.

                                                                               {
  PANIC_IF_NULL(k);
  return hmap_hash(hmap->map_ctx, k->data, k->len);
}

Here is the call graph for this function:

hmap_insert()

hmap_t hmap_insert ( const hmap_t * hmap, hmap_key_t * k, void * v )

nodiscard

Insert the given key k with the value v in the given hash hmap and return the new map.

The new map will share parts of its structure with the old map and never mutate the old map. All retained allocations go through the map's map_ctx. The control's copy_key clones the key into it, so k may point at stack or transient memory. The value v is stored as is and must outlive the map.

Definition at line 661 of file hashmap.c.

                                                               {
  return hmap_default_control.insert(&hmap_default_control, hmap, k, v);
}

Here is the caller graph for this function:

hmap_insert_ctl()

hmap_t hmap_insert_ctl ( const hmap_control_t * ctl, const hmap_t * hmap, hmap_key_t * k, void * v )

nodiscard

Just like the hmap_insert function but, it receives a hmap_control_t to customize the comparison and hashing function.

Definition at line 594 of file hashmap.c.

                                                                                              {
  PANIC_IF_NULL(ctl);
  PANIC_IF_NULL(hmap);
  PANIC_IF_NULL(k);
  PANIC_IF_NULL(ctl->copy_key);
 
  // Everything the map retains has to live in the map's context, so the map
  // survives the release of the inserting caller's context. A null map_ctx
  // means the map was zero-initialized instead of created with hmap_empty.
  const srn_context_t *map_ctx = hmap->map_ctx;
  PANIC_IF_NULL(map_ctx);
 
  hmap_hash_t hash = ctl->hash(hmap, k);
  hmap_key_t *key  = ctl->copy_key(hmap, k);
  hmap_t new_map   = *hmap;
 
  HMAP_LOG("Trying to insert a key with the hash: %x", hash);
 
  if (hmap->root == nullptr) {
    // First insertion, just create a singleton node.
    HMAP_LOG("First insertion on an empty map");
    hmap_kv_entry_t *kv = hmap_new_kv_entry(map_ctx, hash, key, v);
    hmap_node_t *root   = hmap_singleton_node(map_ctx, hash, 0, kv);
 
    new_map.root = root;
    new_map.len  = hmap->len + 1;
    return new_map;
  }
  HMAP_LOG("Find the correct node to insert the key");
  // Create the intermediate nodes recursively
  bool added            = false;
  hmap_node_t *new_root = hmap_insert_node(ctl, hmap, hmap->root, hash, key, v, 0, &added);
 
  new_map.root = new_root;
  if (added) {
    HMAP_LOG("The key was added successfully");
    new_map.len = hmap->len + 1;
  } else {
    HMAP_LOG("The key existed, just updated the value");
    new_map.len = hmap->len;
  }
  return new_map;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_insert_node()

hmap_node_t * hmap_insert_node ( const hmap_control_t * ctl, const hmap_t * hmap, const hmap_node_t * node, hmap_hash_t hash, hmap_key_t * k, void * v, uint32_t shift, bool * out_added )

static

Recursively insert a new node containing the k and v.

out_addad is a output parameter. If set to true by the function. I indicates that there is a new node made by the function. Otherwise the returning node is the old node.

Definition at line 304 of file hashmap.c.

  {
  PANIC_IF_NULL(ctl);
 
  const srn_context_t *ctx = hmap->map_ctx;
  hmap_bitmap_t bit        = hmap_bitpos(hash, shift);
  bool has_data            = hmap_has_data_at(node, bit);
  bool has_child           = hmap_has_node_at(node, bit);
 
  HMAP_LOG(
    "Recursive insert with: (bit %u) (shift %u) (has_data %s) (has_child %s)", bit, shift,
    has_data ? "yes" : "no", has_child ? "yes" : "no"
  );
  PANIC_IF(shift >= HMAP_HASH_SIZE, "'shift' is not within the boundaries");
  // Without the new entry
  size_t count = hmap_number_of_entries(node);
 
  //= Case A
  if (!has_data && !has_child) {
    HMAP_LOG("Case A");
    // Neither data nor node. Insert a new kv entry here.
    hmap_kv_entry_t *new_kv = hmap_new_kv_entry(ctx, hash, k, v);
 
    hmap_node_t *new_node = create_empty_node(ctx);
    new_node->datamap     = node->datamap | bit;
    new_node->nodemap     = node->nodemap;
 
    new_node->entries = ALLOCN(ctx, hmap_data_t, count + 1);
 
    size_t insert_idx = hmap_entry_index(new_node, bit);
 
    // Copy old entries (pointer copy), inserting the new kv at insert_idx.
    size_t src = 0;
 
    for (size_t dst = 0; dst <= count; ++dst) {
      if (dst == insert_idx) {
        new_node->entries[dst] = new_kv;
      } else {
        new_node->entries[dst] = node->entries[src++];
      }
    }
 
    *out_added = true;
    return new_node;
  }
 
  //= Case B
  if (has_data) {
    HMAP_LOG("Case B");
    // There is a data (kv or collision node) at this position.
    size_t idx = hmap_entry_index(node, bit);
    void *ptr  = node->entries[idx];
    PANIC_IF_NULL(ptr);
 
    //== Case B.1 -- Collision node
    if (is_collision_node(ptr)) {
      HMAP_LOG("Case B: Hit a collision node");
      // The pointer is taggend. So we have a collision node at hand. we need
      // to insert the new entry in the collision node.
      hmap_collision_t *head = untag_ptr(ptr);
 
      // first we have to check whether the key is already in the collision node
      // or not.
      bool key_exist = is_key_in_collision_node(ctl, hmap, head, hash, k);
 
      hmap_kv_entry_t *new_kv    = hmap_new_kv_entry(ctx, hash, k, v);
      hmap_collision_t *new_head = nullptr;
 
      if (key_exist) {
        // Rebuild the list with the matching entry replaced. Prepending a
        // shadowing entry instead would grow the list by one on every update
        // of the same key, without bound.
        hmap_collision_t **link = &new_head;
        for (hmap_collision_t *n = head; n != nullptr; n = n->next) {
          hmap_collision_t *copy = ALLOC(ctx, hmap_collision_t);
          bool match             = n->kv->hash == hash && (int)ctl->cmp(hmap, n->kv->k, k);
          copy->kv               = match ? new_kv : n->kv;
          copy->next             = nullptr;
          *link                  = copy;
          link                   = &copy->next;
        }
      } else {
        // A genuinely new key is prepended in front of the shared old list.
        new_head       = ALLOC(ctx, hmap_collision_t);
        new_head->next = head;
        new_head->kv   = new_kv;
      }
 
      hmap_node_t *new_node = create_empty_node(ctx);
      new_node->datamap     = node->datamap;
      new_node->nodemap     = node->nodemap;
      new_node->entries     = hmap_copy_entries(ctx, node->entries, count);
 
      // Put back the new collision node
      new_node->entries[idx] = tag_ptr(new_head);
      *out_added             = ((!key_exist) != 0);
      return new_node;
    }
 
    // LSB is 0 so we can just cast it
    hmap_kv_entry_t *existing_kv = (hmap_kv_entry_t *)ptr;
 
    //== Case B.2 -- Same key exists
    if (existing_kv->hash == hash && (int)ctl->cmp(hmap, existing_kv->k, k)) {
      HMAP_LOG("Case B: The key already exist");
      // We need to replace the entry with the new value in the new node
      hmap_kv_entry_t *new_kv = hmap_new_kv_entry(ctx, hash, k, v);
 
      hmap_node_t *new_node  = create_empty_node(ctx);
      new_node->datamap      = node->datamap;
      new_node->nodemap      = node->nodemap;
      new_node->entries      = hmap_copy_entries(ctx, node->entries, count);
      new_node->entries[idx] = new_kv;
 
      // The key existed, we just replaced it
      *out_added = false;
      return new_node;
    }
 
    hmap_kv_entry_t *new_kv = hmap_new_kv_entry(ctx, hash, k, v);
 
    //== Case B.3 -- We're at the leaf nodes and have to create a collision
    if (hmap_at_max_depth(shift)) {
      // Eventhough we are not sure that we're fully colliding, since only two
      // more bits left and we're at the max depth, we just treat it as a full
      // collision
      HMAP_LOG("Case B: Partial collision at maximum depth");
      hmap_collision_t *c1 = ALLOC(ctx, hmap_collision_t);
      c1->next             = nullptr;
      c1->kv               = existing_kv;
 
      hmap_collision_t *c2 = ALLOC(ctx, hmap_collision_t);
      c2->next             = c1;
      c2->kv               = new_kv;
 
      hmap_node_t *new_node = create_empty_node(ctx);
      // keeping it a data slot
      new_node->datamap      = node->datamap;
      new_node->nodemap      = node->nodemap;
      new_node->entries      = hmap_copy_entries(ctx, node->entries, count);
      new_node->entries[idx] = tag_ptr(c2);
 
      *out_added = true;
      return new_node;
    }
 
    //== Case B.4
    HMAP_LOG("Case B: Partial collision");
    // Collision on this position for the current node. Not a full-fledge
    // collision though. We have to create a new node and move both entries
    // to the new node.
 
    hmap_node_t *sub_node = hmap_merge_two_kv(ctx, existing_kv, new_kv, shift + HMAP_SHIFT);
 
    // Now build a new node where this bit in datamap is moved into nodemap.
    hmap_node_t *new_node = ALLOC(ctx, hmap_node_t);
 
    hmap_bitmap_t new_datamap = node->datamap & ~bit;
    hmap_bitmap_t new_nodemap = node->nodemap | bit;
 
    new_node->datamap = new_datamap;
    new_node->nodemap = new_nodemap;
 
    // We replace one data entry with one node, so count unchanged.
    new_node->entries = ALLOCN(ctx, hmap_data_t, count);
 
    for (size_t i = 0; i < count; ++i) {
      new_node->entries[i] = node->entries[i];
    }
 
    new_node->entries[idx] = sub_node;
 
    *out_added = true;
    return new_node;
  }
 
  //= Case C
  // There is a child node, so we have to keep chasing and creating new nodes
  // as we move further down
  size_t idx               = hmap_entry_index(node, bit);
  const hmap_node_t *child = (const hmap_node_t *)node->entries[idx];
  HMAP_LOG("Case C");
  bool child_added = false;
  hmap_node_t *new_child =
    hmap_insert_node(ctl, hmap, child, hash, k, v, shift + HMAP_SHIFT, &child_added);
 
  // If nothing changed below, we can just reuse this node (like an update)
  if (new_child == child) {
    *out_added = false;
    // Just reusing the old node as nothing happened
    return (hmap_node_t *)node;
  }
 
  // Otherwise allocate a new node with updated child pointer.
  hmap_node_t *new_node  = create_empty_node(ctx);
  new_node->datamap      = node->datamap;
  new_node->nodemap      = node->nodemap;
  new_node->entries      = hmap_copy_entries(ctx, node->entries, count);
  new_node->entries[idx] = new_child;
 
  //*out_added = true;
  *out_added = child_added;
  return new_node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_internal_cmp()

bool hmap_internal_cmp ( const hmap_t * hmap, const hmap_key_t * a, const hmap_key_t * b )

static

Definition at line 583 of file hashmap.c.

                                                                                            {
  UNUSED(hmap);
  return hmap_key_equal(a, b);
}

Here is the call graph for this function:

hmap_key_equal()

bool hmap_key_equal ( const hmap_key_t * a, const hmap_key_t * b )

inlinestatic

Compare key a with key b.

Definition at line 87 of file hashmap.c.

                                                                            {
  if (a == b) {
    // Same pointers are definitely the same object in memory regardless
    // of what compiler might see
    return true;
  }
 
  if (a == nullptr || b == nullptr || (a->len != b->len)) {
    return false;
  }
 
  if (a->len == 0 && b->len == 0) {
    return true;
  }
 
  if (a->len == 0) {
    return false;
  }
 
  return memcmp(a->data, b->data, a->len) == 0;
}

Here is the caller graph for this function:

hmap_lookup()

void * hmap_lookup ( const hmap_t * hmap, const hmap_key_t * k, void * default_value )

nodiscard

Lookup the given k in the given hmap and return the value if it's been found.

Otherwise return the default_value value. Since a nullptr is a valid value for any keys, returning a nullptr is not a good option to indicate that the key does not exist, So it's safer to use explicit values to differenciate between a missing key and a legit nullptr as a value.

Definition at line 665 of file hashmap.c.

                                                                                {
  return hmap_default_control.lookup(&hmap_default_control, hmap, k, default_value);
}

Here is the caller graph for this function:

hmap_lookup_ctl()

void * hmap_lookup_ctl	(	const hmap_control_t *	ctl,
		const hmap_t *	hmap,
		const hmap_key_t *	k,
		void *	default_value )

Just like the hmap_lookup function but, it receives a hmap_control_t to customize the comparison and hashing function.

Definition at line 638 of file hashmap.c.

  {
  PANIC_IF_NULL(ctl);
  PANIC_IF_NULL(hmap);
  PANIC_IF_NULL(k);
 
  PANIC_IF_NULL(hmap->map_ctx);
 
  if (hmap->root == nullptr) {
    return default_value;
  }
 
  hmap_hash_t hash = ctl->hash(hmap, k);
  return hmap_lookup_in_node(ctl, hmap, hmap->root, hash, k, 0, default_value);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_lookup_in_collision()

void * hmap_lookup_in_collision ( const hmap_control_t * ctl, const hmap_t * hmap, hmap_collision_t * cnode, hmap_hash_t hash, const hmap_key_t * k, void * default_value )

static

Definition at line 511 of file hashmap.c.

  {
  assert(ctl != nullptr);
  assert(hmap != nullptr);
  assert(hmap->map_ctx != nullptr);
 
  hmap_collision_t *n = cnode;
  for (;;) {
    if (n == nullptr) {
      // Didn't found the key
      return default_value;
    }
 
    PANIC_IF_NULL(n->kv);
    if ((n->kv->hash == hash) && (int)ctl->cmp(hmap, n->kv->k, k)) {
      return n->kv->v;
    }
    n = n->next;
  }
  return default_value;
}

Here is the caller graph for this function:

hmap_lookup_in_node()

void * hmap_lookup_in_node ( const hmap_control_t * ctl, const hmap_t * hmap, const hmap_node_t * node, hmap_hash_t hash, const hmap_key_t * k, uint32_t shift, void * default_value )

static

Definition at line 535 of file hashmap.c.

  {
  assert(ctl != nullptr);
  assert(hmap != nullptr);
  assert(hmap->map_ctx != nullptr);
 
  HMAP_LOG("Looking up in for haha %x at shift %u", hash, shift);
  PANIC_IF(shift >= HMAP_HASH_SIZE, "'shift' is not within the boundaries");
  if (node == nullptr) {
    return default_value;
  }
 
  hmap_bitmap_t bit = hmap_bitpos(hash, shift);
 
  // Check for a data (kv) entry at current bitpos.
  if (hmap_has_data_at(node, bit)) {
    void *ptr = hmap_get_entry_at(node, bit);
    if (is_collision_node(ptr)) {
      HMAP_LOG("Hit a collision node");
      hmap_collision_t *cnode = untag_ptr(ptr);
      return hmap_lookup_in_collision(ctl, hmap, cnode, hash, k, default_value);
    }
    hmap_kv_entry_t *kv = (hmap_kv_entry_t *)ptr;
 
    if (kv->hash == hash && (int)ctl->cmp(hmap, kv->k, k)) {
      return kv->v;
    }
 
    // If it's not a collision node, nor a match, then we have a key with the
    // same hash that is not in the map, so treat it as any none existing key
    return default_value;
  }
 
  // Otherwise, if there is a child node at this bit position, recurse.
  if (hmap_has_node_at(node, bit)) {
    PANIC_IF(hmap_at_max_depth(shift), "hmap should not have nodes at max level.");
    const hmap_node_t *child = hmap_get_child_at(node, bit);
    return hmap_lookup_in_node(ctl, hmap, child, hash, k, shift + HMAP_SHIFT, default_value);
  }
 
  // No data, no child, not found.
  return default_value;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_make_key()

hmap_key_t * hmap_make_key	(	srn_context_t *	ctx,
		void *	data,
		size_t	len )

Create a new key out of the given data, with the given len.

Definition at line 669 of file hashmap.c.

                                                                      {
  PANIC_IF_NULL(ctx);
  PANIC_IF_NULL(data);
  hmap_key_t *key = ALLOC(ctx, hmap_key_t);
  key->data       = data;
  key->len        = len;
  return key;
}

hmap_merge_two_kv()

hmap_node_t * hmap_merge_two_kv ( const srn_context_t * ctx, hmap_kv_entry_t * kv1, hmap_kv_entry_t * kv2, uint32_t shift )

static

Merge two distinct kv entries into a sub-trie.

kv1 and kv2 assumed to share either the full hash or a prefix

Definition at line 233 of file hashmap.c.

  {
  assert(kv1 != nullptr);
  assert(kv2 != nullptr);
 
  hmap_bitmap_t bit1 = hmap_bitpos(kv1->hash, shift);
  hmap_bitmap_t bit2 = hmap_bitpos(kv2->hash, shift);
 
  if (bit1 != bit2) {
    // They diverge at this level; we can store both as data entries in one
    // node. This branch also covers the deepest level, two keys whose
    // hashes agree on every fragment except the last one are not a
    // collision, and lookup probes each key's own bit position.
    hmap_node_t *node = create_empty_node(ctx);
    node->nodemap     = 0;
    node->datamap     = bit1 | bit2;
 
    size_t count  = 2;
    node->entries = ALLOCN(ctx, hmap_data_t, count);
 
    // Determine ordering by bit value.
    size_t idx1 = (bit1 < bit2) ? 0 : 1;
    size_t idx2 = 1 - idx1;
 
    node->entries[idx1] = kv1;
    node->entries[idx2] = kv2;
 
    return node;
  }
 
  if (shift + HMAP_SHIFT >= HMAP_HASH_SIZE) {
    // Same final fragment and no hash bits left, a genuine full collision.
    // Create an explicit collision node. Tag the pointer to indicate the
    // collision and insert it in the datamap.
    hmap_node_t *node = create_empty_node(ctx);
 
    hmap_collision_t *c1 = ALLOC(ctx, hmap_collision_t);
    c1->next             = nullptr;
    c1->kv               = kv1;
 
    hmap_collision_t *c2 = ALLOC(ctx, hmap_collision_t);
    c2->next             = c1;
    c2->kv               = kv2;
 
    node->datamap = bit1;
    node->entries = ALLOC(ctx, hmap_data_t);
 
    // Tag the pointer to indicate a collision node and insert the collision
    // node in the entries.
    size_t idx         = hmap_entry_index(node, bit1);
    node->entries[idx] = tag_ptr(c2);
    return node;
  }
 
  // Same fragment at this level; we need a deeper node.
  hmap_node_t *child = hmap_merge_two_kv(ctx, kv1, kv2, shift + HMAP_SHIFT);
 
  hmap_node_t *node = create_empty_node(ctx);
  node->datamap     = 0;
  node->nodemap     = bit1;
  // Only one entry
  node->entries    = ALLOC(ctx, hmap_data_t);
  node->entries[0] = child;
  return node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_new_kv_entry()

hmap_kv_entry_t * hmap_new_kv_entry ( const srn_context_t * ctx, hmap_hash_t hash, hmap_key_t * k, void * v )

inlinestatic

Abstract away the kv entry allocation.

Definition at line 187 of file hashmap.c.

                                                                                      {
  assert(k != nullptr);
  hmap_kv_entry_t *kv = ALLOC(ctx, hmap_kv_entry_t);
  kv->hash            = hash;
  kv->k               = k;
  kv->v               = v;
  return kv;
}

Here is the caller graph for this function:

hmap_number_of_entries()

size_t hmap_number_of_entries ( const hmap_node_t * node )

inlinestatic

Number of entries (data + node) in a node regardless of a data pointer or a node pointer.

Definition at line 145 of file hashmap.c.

                                                                     {
  return hmap_popcount(node->datamap | node->nodemap);
}

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_popcount()

size_t hmap_popcount ( hmap_bitmap_t bm )

inlinestatic

Definition at line 141 of file hashmap.c.

{ return srn_popcnt32(bm); }

Here is the call graph for this function:

Here is the caller graph for this function:

hmap_singleton_node()

hmap_node_t * hmap_singleton_node ( const srn_context_t * ctx, hmap_hash_t hash, uint32_t shift, hmap_kv_entry_t * kv )

static

Definition at line 205 of file hashmap.c.

  {
  hmap_node_t *node = ALLOC(ctx, hmap_node_t);
  hmap_bitmap_t bit = hmap_bitpos(hash, shift);
 
  node->datamap = bit;
  node->nodemap = 0U;
  node->entries = ALLOCN(ctx, hmap_data_t, 1);
  // No need to tag since LSB will be 0 anyway
  node->entries[0] = kv;
  return node;
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_collision_node()

bool is_collision_node ( void * p )

inlinestatic

Return true if the pointer's LSB is 1 indicating a collision.

Definition at line 61 of file hashmap.c.

{ return ((uintptr_t)p & (uintptr_t)1) != 0; }

Here is the caller graph for this function:

is_key_in_collision_node()

bool is_key_in_collision_node ( const hmap_control_t * ctl, const hmap_t * hmap, hmap_collision_t * head, hmap_hash_t hash, hmap_key_t * k )

inlinestatic

Definition at line 109 of file hashmap.c.

  {
  assert(ctl != nullptr);
  assert(hmap != nullptr);
  assert(hmap->map_ctx != nullptr);
 
  hmap_collision_t *n = head;
  while (n != nullptr) {
    hmap_kv_entry_t *existing_kv = n->kv;
    if (existing_kv->hash == hash && (int)ctl->cmp(hmap, existing_kv->k, k)) {
      return true;
    }
    n = n->next;
  }
  return false;
}

Here is the caller graph for this function:

tag_ptr()

void * tag_ptr ( void * ptr )

inlinestatic

Definition at line 70 of file hashmap.c.

                                       {
  // NOLINTBEGIN(performance-no-int-to-ptr)
  return (void *)(((uintptr_t)(ptr)) | (uintptr_t)1);
  // NOLINTEND(performance-no-int-to-ptr)
}

Here is the caller graph for this function:

untag_ptr()

hmap_collision_t * untag_ptr ( void * ptr )

inlinestatic

Since for non collision nodes the LSB is 0 then we don't need to untag it.

Definition at line 64 of file hashmap.c.

                                                     {
  // NOLINTBEGIN(performance-no-int-to-ptr)
  return (hmap_collision_t *)(((uintptr_t)(ptr)) & ~(uintptr_t)1);
  // NOLINTEND(performance-no-int-to-ptr)
}

Here is the caller graph for this function:

Variable Documentation

hmap_default_control

hmap_control_t hmap_default_control

Initial value:

                                    = {
  .cmp      = &hmap_internal_cmp,
  .hash     = &hmap_hash_internal,
  .insert   = &hmap_insert_ctl,
  .lookup   = &hmap_lookup_ctl,
  .copy_key = &hmap_copy_key,
}

Definition at line 690 of file hashmap.c.

                                    {
  .cmp      = &hmap_internal_cmp,
  .hash     = &hmap_hash_internal,
  .insert   = &hmap_insert_ctl,
  .lookup   = &hmap_lookup_ctl,
  .copy_key = &hmap_copy_key,
};