hashmap.h

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/>.
 */
 
#pragma once
 
/// @file
/// This is an implementation of Compressed Hash-Array Mapped Prefix-tree,
/// which is a bit-partitioned, persistent, immutable Hashed array mapped trie.
///
/// For more information, have a look at the `Optimizing Hash-Array Mapped Tries
/// for Fast and Lean Immutable JVM Collections` paper.
///
///
/// TL;DR:
///  - Every struct is immutable
///  - Nodes are persistent and immutable.
///  - Nodes are heap allocated
///  - Heads can be stack allocated
///  - We create a new head for any change and probably will create inner nodes
///    as well depending on the change
///  - New heads will share structure with the older version
///  - This is not a ordered hashmap
///  - The hashing function HAS TO BE DETERMINISTIC
///  - Don't use pointers value as the data to hash, use the data that they
///  point
///    to instead.
 
#include <stddef.h>
#include <stdint.h>
 
#include "serene/rt/errors.h"
 
typedef struct srn_context_t srn_context_t;
 
// -----------------------------------------------------------------------------
// Tunables
// -----------------------------------------------------------------------------
/// branching factor (power of two)
#define HMAP_BR          32u
#define HMAP_SHIFT       5u
#define HMAP_MASK        (HMAP_BR - 1u)
#define HMAP_HASH_SIZE   32u ///< By default we use 32bit hashes
#define HMAP_HASH_TYPE   uint32_t
#define HMAP_BITMAP_TYPE uint32_t
 
typedef HMAP_HASH_TYPE hmap_hash_t;
typedef HMAP_BITMAP_TYPE hmap_bitmap_t;
typedef void *hmap_data_t;
 
/// Note: For key equality we use the memcpy function
typedef struct hmap_key_t {
  /// len 0 -> data == nullptr
  void *data;
  size_t len;
} hmap_key_t;
 
typedef struct hmap_kv_entry_t {
  hmap_hash_t hash;
  hmap_key_t *k;
  void *v;
} hmap_kv_entry_t;
 
typedef struct hmap_node_t {
  hmap_bitmap_t datamap;
  hmap_bitmap_t nodemap;
  /// This is really a (void **) which each entry in the array
  /// will be either (mutually exclusive):
  /// - A pointer to a hmap_kv_entry_t (or a collision node), which mean the
  /// actual key/value is in that slot.
  /// - A pointer to the next hmap_node_t (a child of the current node)
  /// that is determined by the corresponding bit in the `datamap` and `nodemap`
  /// bitmaps.
  ///
  /// For example, if datamap is `0b...110` and nodemap is `0b...001` then
  /// the first entry, is a child node (a pointer to hmap_node_t) and second and
  /// third entries are pointers to `hmap_kv_entry_t` or simply the key/value
  hmap_data_t *entries;
} hmap_node_t;
 
typedef struct hmap_t {
  /// Number of key/value pairs in the map
  size_t len;
  hmap_node_t *root;
} hmap_t;
 
/// If we ever want to modify some of these behaviours for a new instance
/// of hashmap, we should use this control type.
typedef struct hmap_control_t {
  bool (*cmp)(srn_context_t *ctx, const hmap_key_t *a, const hmap_key_t *b);
  hmap_hash_t (*hash)(srn_context_t *ctx, const hmap_key_t *k);
  hmap_t (*insert)(const struct hmap_control_t *ctl, srn_context_t *ctx,
                   const hmap_t *hmap, hmap_key_t *k, void *v);
  void *(*lookup)(const struct hmap_control_t *ctl, srn_context_t *ctx,
                  const hmap_t *hmap, const hmap_key_t *k, void *default_value);
 
} hmap_control_t;
 
extern hmap_control_t hmap_default_control;
 
/// Create, initialize and return a new hashmap
[[nodiscard]] [[gnu::nonnull(1)]] hmap_t hmap_empty(srn_context_t *ctx);
/// 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.
[[nodiscard]] [[gnu::nonnull(1, 2, 3)]] hmap_t
hmap_insert(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.
[[nodiscard]] [[gnu::nonnull(1, 2, 3)]]
hmap_t hmap_insert_ctl(const hmap_control_t *ctl, srn_context_t *ctx,
                       const hmap_t *hmap, hmap_key_t *k, void *v);
 
/// 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.
[[nodiscard]] [[gnu::nonnull(1, 2, 3)]]
void *hmap_lookup(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.
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);
/// 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`.
[[gnu::nonnull(1)]]
hmap_hash_t hmap_hash(srn_context_t *ctx, const void *data, size_t len);
 
/// Create a new key out of the given `data`, with the given len.
[[gnu::nonnull(1, 2)]]
hmap_key_t *hmap_make_key(srn_context_t *ctx, void *data, size_t len);