hashmap.c

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * This library is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library.  If not, see <https://www.gnu.org/licenses/>.
 */
 
/// @file
/// 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.
 
#include "serene/rt/impl/hashmap.h"
 
#include <stdint.h>
 
#include "serene/rt/context.h"
#include "serene/rt/engine.h" // for HMAP_HASH_FN
#include "serene/utils.h"
 
#include <assert.h>
#include <string.h>
 
#if defined(HMAP_DEBUG)
#define HMAP_LOG(...) DBG("HMAP", __VA_ARGS__)
#else
#define HMAP_LOG(...)
#endif
 
// -----------------------------------------------------------------------------
// Collisions
// -----------------------------------------------------------------------------
/// A simple alist to manage collision nodes
typedef struct hmap_collision_t {
  struct hmap_collision_t *next;
  hmap_kv_entry_t *kv;
} hmap_collision_t;
 
/// Return true if the pointer's LSB is 1 indicating a collision.
static inline bool is_collision_node(void *p) { return ((uintptr_t)p & (uintptr_t)1) != 0; }
 
/// Since for non collision nodes the LSB is 0 then we don't need to untag it.
static inline hmap_collision_t *untag_ptr(void *ptr) {
  // NOLINTBEGIN(performance-no-int-to-ptr)
  return (hmap_collision_t *)(((uintptr_t)(ptr)) & ~(uintptr_t)1);
  // NOLINTEND(performance-no-int-to-ptr)
}
 
static inline void *tag_ptr(void *ptr) {
  // NOLINTBEGIN(performance-no-int-to-ptr)
  return (void *)(((uintptr_t)(ptr)) | (uintptr_t)1);
  // NOLINTEND(performance-no-int-to-ptr)
}
 
#if !defined(SERENE_TESTS)
hmap_hash_t hmap_hash(srn_context_t *ctx, const void *data, size_t len) {
  return srn_hash(ctx->engine, data, len);
}
#endif
 
// -----------------------------------------------------------------------------
// helpers
// -----------------------------------------------------------------------------
 
/// Compare key `a` with key `b`
static inline bool hmap_key_equal(const hmap_key_t *a, const hmap_key_t *b) {
  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;
}
 
static inline 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) {
  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;
}
 
/// Extract a `HMAP_MAK`-bit chunk from the hash at the given shift.
static inline uint32_t hmap_hash_fragment(hmap_hash_t hash, uint8_t shift) {
  /* if (shift > 32) { */
  /*   PANIC("'shift' should be less than 32\n"); */
  /* } */
  return (hash >> shift) & HMAP_MASK;
}
 
/// Bit position corresponding to this fragment.
static inline hmap_bitmap_t hmap_bitpos(hmap_hash_t hash, uint8_t shift) {
  return (hmap_bitmap_t)1U << hmap_hash_fragment(hash, shift);
}
 
static inline size_t hmap_popcount(hmap_bitmap_t bm) { return srn_popcnt32(bm); }
 
/// Number of entries (data + node) in a node regardless of a data pointer
/// or a node pointer
static inline size_t hmap_number_of_entries(const hmap_node_t *node) {
  return hmap_popcount(node->datamap | node->nodemap);
}
 
/// Index in the packed `entries` array for a given bitpos (either datamap or
/// nodemap).
static inline size_t hmap_entry_index(const hmap_node_t *node, hmap_bitmap_t bitpos) {
  // 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);
}
 
/// Is this bitpos occupied by a data (kv) entry?
static inline bool hmap_has_data_at(const hmap_node_t *node, hmap_bitmap_t bitpos) {
  return (node->datamap & bitpos) != 0;
}
 
/// Is this bitpos occupied by a child node?
static inline bool hmap_has_node_at(const hmap_node_t *node, hmap_bitmap_t bitpos) {
  return (node->nodemap & bitpos) != 0;
}
 
/// Make sure the result with `is_collision_node` and case the
/// result to either an entry or a collision node
static inline void *hmap_get_entry_at(const hmap_node_t *node, hmap_bitmap_t bitpos) {
  return node->entries[hmap_entry_index(node, bitpos)];
}
 
/// Fetch the child node pointer at a given bitpos;
/// we must ensure nodemap has this bit.
static inline hmap_node_t *hmap_get_child_at(const hmap_node_t *node, hmap_bitmap_t bitpos) {
  size_t idx = hmap_entry_index(node, bitpos);
  return (hmap_node_t *)node->entries[idx];
}
 
static inline bool hmap_at_max_depth(uint32_t shift) {
  return shift + HMAP_SHIFT >= HMAP_HASH_SIZE;
}
 
/// Abstract away the kv entry allocation.
static inline hmap_kv_entry_t *hmap_new_kv_entry(srn_context_t *ctx, hmap_hash_t hash,
                                                 hmap_key_t *k, void *v) {
  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;
}
 
static inline hmap_node_t *create_empty_node(srn_context_t *ctx) {
  assert(ctx != nullptr);
  hmap_node_t *n = ALLOC(ctx, hmap_node_t);
  n->nodemap = 0;
  n->datamap = 0;
  n->entries = nullptr;
  return n;
}
 
static hmap_node_t *hmap_singleton_node(srn_context_t *ctx, hmap_hash_t hash, uint32_t shift,
                                        hmap_kv_entry_t *kv) {
  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;
}
 
/// Copy entries array into a new one, returning pointer.
static hmap_data_t *hmap_copy_entries(srn_context_t *ctx, hmap_data_t *entries, size_t count) {
  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;
}
/// Merge two distinct kv entries into a sub-trie. `kv1` and `kv2` assumed to
/// share either the full hash or a prefix
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) {
  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;
}
 
/// 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.
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) {
  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;
}
 
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) {
  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;
}
 
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) {
  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;
}
// -----------------------------------------------------------------------------
// Public API
// -----------------------------------------------------------------------------
static bool hmap_internal_cmp(srn_context_t *ctx, const hmap_key_t *a, const hmap_key_t *b) {
  UNUSED(ctx);
  return hmap_key_equal(a, b);
}
 
[[gnu::nonnull(1)]]
static hmap_hash_t hmap_hash_internal(srn_context_t *ctx, const hmap_key_t *k) {
  PANIC_IF_NULL(k);
  return hmap_hash(ctx, k->data, k->len);
}
 
hmap_t hmap_insert_ctl(const hmap_control_t *ctl, srn_context_t *ctx, const hmap_t *hmap,
                       hmap_key_t *k, void *v) {
  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;
}
 
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) {
  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);
}
 
hmap_t hmap_empty(srn_context_t *ctx) {
  UNUSED(ctx);
  hmap_t map = {.len = 0, .root = nullptr};
  return map;
}
 
hmap_t hmap_insert(srn_context_t *ctx, const hmap_t *hmap, hmap_key_t *k, void *v) {
  return hmap_default_control.insert(&hmap_default_control, ctx, hmap, k, v);
}
 
void *hmap_lookup(srn_context_t *ctx, const hmap_t *hmap, const hmap_key_t *k,
                  void *default_value) {
  return hmap_default_control.lookup(&hmap_default_control, ctx, hmap, k, default_value);
}
 
hmap_key_t *hmap_make_key(srn_context_t *ctx, void *data, size_t len) {
  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_control_t hmap_default_control = {
    .cmp = &hmap_internal_cmp,
    .hash = &hmap_hash_internal,
    .insert = &hmap_insert_ctl,
    .lookup = &hmap_lookup_ctl,
};