hashmap.c File Reference

Notes: More...

#include "serene/rt/impl/hashmap.h"
#include <stdint.h>
#include "serene/rt/context.h"
#include "serene/rt/engine.h"
#include "serene/utils.h"
#include <assert.h>
#include <string.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 (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, srn_context_t *ctx, 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 (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 (srn_context_t *ctx)
static hmap_node_t *	hmap_singleton_node (srn_context_t *ctx, hmap_hash_t hash, uint32_t shift, hmap_kv_entry_t *kv)
static hmap_data_t *	hmap_copy_entries (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 (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, srn_context_t *ctx, 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.
void *	hmap_lookup_in_collision (const hmap_control_t *ctl, srn_context_t *ctx, 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, srn_context_t *ctx, 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 (srn_context_t *ctx, const hmap_key_t *a, const hmap_key_t *b)
static hmap_hash_t	hmap_hash_internal (srn_context_t *ctx, const hmap_key_t *k)
hmap_t	hmap_insert_ctl (const hmap_control_t *ctl, srn_context_t *ctx, 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, srn_context_t *ctx, 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 (srn_context_t *ctx)
	Create, initialize and return a new hashmap.
hmap_t	hmap_insert (srn_context_t *ctx, 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 (srn_context_t *ctx, 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.

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 49 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()

static hmap_node_t * create_empty_node ( srn_context_t * ctx )

inlinestatic

Definition at line 195 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()

static bool hmap_at_max_depth ( uint32_t shift )

inlinestatic

Definition at line 180 of file hashmap.c.

                                                     {
  return shift + HMAP_SHIFT >= HMAP_HASH_SIZE;
}

Here is the caller graph for this function:

hmap_bitpos()

static hmap_bitmap_t hmap_bitpos ( hmap_hash_t hash, uint8_t shift )

inlinestatic

Bit position corresponding to this fragment.

Definition at line 136 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()

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

static

Copy entries array into a new one, returning pointer.

Definition at line 218 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_empty()

hmap_t hmap_empty ( srn_context_t * ctx )

nodiscard

Create, initialize and return a new hashmap.

Definition at line 612 of file hashmap.c.

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

Here is the caller graph for this function:

hmap_entry_index()

static 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 150 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()

static 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 175 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()

static 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 169 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()

static 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 158 of file hashmap.c.

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

Here is the caller graph for this function:

hmap_has_node_at()

static 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 163 of file hashmap.c.

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

Here is the caller graph for this function:

hmap_hash()

hmap_hash_t hmap_hash	(	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 78 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()

static 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 128 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()

static hmap_hash_t hmap_hash_internal ( srn_context_t * ctx, const hmap_key_t * k )

static

Definition at line 554 of file hashmap.c.

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

Here is the call graph for this function:

hmap_insert()

hmap_t hmap_insert ( srn_context_t * ctx, 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.

Definition at line 618 of file hashmap.c.

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

Here is the caller graph for this function:

hmap_insert_ctl()

hmap_t hmap_insert_ctl ( const hmap_control_t * ctl, srn_context_t * ctx, 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 559 of file hashmap.c.

                                               {
  PANIC_IF_NULL(ctl);
  PANIC_IF_NULL(ctx);
  PANIC_IF_NULL(hmap);
  PANIC_IF_NULL(k);
 
  hmap_hash_t hash = ctl->hash(ctx, 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(ctx, hash, k, v);
    hmap_node_t *root = hmap_singleton_node(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, ctx, hmap->root, hash, k, 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:

hmap_insert_node()

static hmap_node_t * hmap_insert_node ( const hmap_control_t * ctl, srn_context_t * ctx, 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 298 of file hashmap.c.

                                                                               {
  PANIC_IF_NULL(ctl);
  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, ctx, head, hash, k);
 
      // Since it's an alist, we just add the new value even if the key is
      // already here, on look up we always fetch the newer value
      hmap_collision_t *new_head = ALLOC(ctx, hmap_collision_t);
      hmap_kv_entry_t *new_kv = hmap_new_kv_entry(ctx, hash, k, v);
      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(ctx, 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, ctx, 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()

static bool hmap_internal_cmp ( srn_context_t * ctx, const hmap_key_t * a, const hmap_key_t * b )

static

Definition at line 548 of file hashmap.c.

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

Here is the call graph for this function:

hmap_key_equal()

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

inlinestatic

Compare key a with key b

Definition at line 88 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 ( srn_context_t * ctx, 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 622 of file hashmap.c.

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

Here is the caller graph for this function:

hmap_lookup_ctl()

void * hmap_lookup_ctl	(	const hmap_control_t *	ctl,
		srn_context_t *	ctx,
		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 597 of file hashmap.c.

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

Here is the call graph for this function:

hmap_lookup_in_collision()

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

Definition at line 484 of file hashmap.c.

                                                    {
  PANIC_IF_NULL(ctl);
  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(ctx, 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()

static void * hmap_lookup_in_node ( const hmap_control_t * ctl, srn_context_t * ctx, const hmap_node_t * node, hmap_hash_t hash, const hmap_key_t * k, uint32_t shift, void * default_value )

static

Definition at line 504 of file hashmap.c.

                                                                      {
  PANIC_IF_NULL(ctl);
  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, ctx, cnode, hash, k, default_value);
    }
    hmap_kv_entry_t *kv = (hmap_kv_entry_t *)ptr;
 
    if (kv->hash == hash && (int)ctl->cmp(ctx, 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, ctx, 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 627 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;
}

Here is the caller graph for this function:

hmap_merge_two_kv()

static hmap_node_t * hmap_merge_two_kv ( 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 230 of file hashmap.c.

                                                                            {
  PANIC_IF_NULL(kv1);
  PANIC_IF_NULL(kv2);
  if (shift + HMAP_SHIFT >= HMAP_HASH_SIZE) {
    // We've exhausted the hash bits and still collide, we should
    // 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;
 
    hmap_bitmap_t bit = hmap_bitpos(kv1->hash, shift);
    node->datamap = bit;
    node->entries = ALLOC(ctx, hmap_data_t);
 
    // Tag the pointer to indicate a collision node and dnsert the collision
    // node in the entries.
    size_t idx = hmap_entry_index(node, bit);
    node->entries[idx] = tag_ptr(c2);
    return node;
  }
 
  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.
    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;
  }
 
  // 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()

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

inlinestatic

Abstract away the kv entry allocation.

Definition at line 185 of file hashmap.c.

                                                                         {
  PANIC_IF_NULL(k);
  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()

static 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 144 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()

static size_t hmap_popcount ( hmap_bitmap_t bm )

inlinestatic

Definition at line 140 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()

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

static

Definition at line 204 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()

static bool is_collision_node ( void * p )

inlinestatic

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

Definition at line 62 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()

static bool is_key_in_collision_node ( const hmap_control_t * ctl, srn_context_t * ctx, hmap_collision_t * head, hmap_hash_t hash, hmap_key_t * k )

inlinestatic

Definition at line 110 of file hashmap.c.

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

Here is the caller graph for this function:

tag_ptr()

static void * tag_ptr ( void * ptr )

inlinestatic

Definition at line 71 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()

static 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 65 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,
}

Definition at line 636 of file hashmap.c.

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