hashmap_tests.h

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#pragma once
 
#include <stdio.h>
#include <string.h>
 
#include <serene/rt/context.h>
#include <serene/rt/impl/hashmap.h>
 
#include "acutest.h"
#include "base.h"
 
#define HMAP_TESTS(X)                                                                  \
  X("hashmap::empty", test_hashmap_empty),                                             \
    X("hashmap::deterministic_hash_fn", test_hashmap_make_sure_hash_is_deterministic), \
    X("hashmap::insert_new_kv", test_hashmap_insert_kv),                               \
    X("hashmap::many_insert_and_lookup", test_hashmap_many_insert_and_lookup),         \
    X("hashmap::collision_lookup", test_hashmap_collision_node_lookup),                \
    X("hashmap::max_depth_divergence", test_hashmap_max_depth_divergence),             \
    X("hashmap::update", test_hashmap_update)
 
#define HMAP_TEST_LOG(...) DBG("HMAP_TEST", __VA_ARGS__)
 
typedef struct hashmap_dummy {
  int foo;
  int bar;
} hashmap_dummy;
 
static void test_hashmap_empty() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = hmap_empty(ctx);
 
  TEST_CHECK(s.len == 0);
  TEST_CHECK(s.root == nullptr);
  // TEST_CHECK(s.maybe_error == nullptr);
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
void test_hashmap_insert_kv() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  hashmap_dummy d = {.foo = 10, .bar = 20}; // NOLINT
  hmap_t h        = hmap_empty(ctx);
 
  int key         = 1236;
  int key_missing = 342;
 
  hmap_key_t k         = {.data = &key, .len = sizeof(key)};
  hmap_key_t k_missing = {.data = &key_missing, .len = sizeof(key_missing)};
 
  hmap_t h1 = hmap_insert(&h, &k, &d);
 
  void *dptr = hmap_lookup(&h1, &k, nullptr);
  TEST_CHECK(dptr != nullptr);
  TEST_CHECK(dptr == &d);
 
  int default_v      = 999;
  void *dptr_missing = hmap_lookup(&h1, &k_missing, &default_v);
  TEST_CHECK(dptr_missing != nullptr);
  TEST_CHECK(*(int *)dptr_missing == 999);
 
  (void)h1;
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
static void test_hashmap_make_sure_hash_is_deterministic() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  int x = 10;
 
  for (int i = 0; i < 100; i++) {
    uint32_t h1 = hmap_hash(ctx, &x, sizeof(x));
    uint32_t h2 = hmap_hash(ctx, &x, sizeof(x));
    TEST_CHECK(h1 == h2);
  }
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
static void test_hashmap_many_insert_and_lookup() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  constexpr int N = 4096;
 
  int *keys           = ALLOCN(ctx, int, N);
  hmap_key_t *ks      = ALLOCN(ctx, hmap_key_t, N);
  hashmap_dummy *vals = ALLOCN(ctx, hashmap_dummy, N);
 
  hmap_t h = hmap_empty(ctx);
 
  for (int i = 0; i < N; ++i) {
    keys[i]    = i;
    ks[i].data = &keys[i];
    ks[i].len  = sizeof(keys[i]);
 
    vals[i].foo = i;
    vals[i].bar = i * 10;
 
    h = hmap_insert(&h, &ks[i], &vals[i]);
  }
 
  TEST_CHECK(h.len == (size_t)N);
  TEST_CHECK(h.root != nullptr);
  // TEST_CHECK(h.maybe_error == nullptr);
 
  // Lookup everything
  for (int i = 0; i < N; ++i) {
    void *p = hmap_lookup(&h, &ks[i], nullptr);
    TEST_CHECK(p != nullptr);
 
    hashmap_dummy *d = (hashmap_dummy *)p;
    TEST_ASSERT(d != nullptr);
    TEST_CHECK(d->foo == i);
    TEST_CHECK(d->bar == i * 10);
  }
 
  // update the keys (effectively inserting new keys)
  for (int i = 0; i < N; ++i) {
    vals[i].foo = i + i;
    vals[i].bar = i * 10 + i;
 
    h = hmap_insert(&h, &ks[i], &vals[i]);
  }
 
  TEST_CHECK(h.len == (size_t)N);
  TEST_CHECK(h.root != nullptr);
  // TEST_CHECK(h.maybe_error == nullptr);
 
  // Lookup everything again!
  for (int i = 0; i < N; ++i) {
    void *p = hmap_lookup(&h, &ks[i], nullptr);
    TEST_CHECK(p != nullptr);
 
    hashmap_dummy *d = (hashmap_dummy *)p;
    TEST_CHECK(d->foo == i + i);
    TEST_CHECK(d->bar == i * 10 + i);
  }
 
  // Missing key returns default value (since nullptr can be a legit value).
  int missing_key  = 0x7fffff;
  hmap_key_t kmiss = {.data = &missing_key, .len = sizeof(missing_key)};
 
  int default_v = 999;
  void *p       = hmap_lookup(&h, &kmiss, &default_v);
  TEST_CHECK(p == &default_v);
  TEST_CHECK(*(int *)p == 999);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
static void test_hashmap_collision_node_lookup() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  hmap_t h = hmap_empty(ctx);
 
  int a = 111;
  int b = 222;
 
  hmap_key_t ka = {.data = &a, .len = sizeof(a)};
  hmap_key_t kb = {.data = &b, .len = sizeof(b)};
 
  hashmap_dummy va = {.foo = 1, .bar = 10};
  hashmap_dummy vb = {.foo = 2, .bar = 20};
 
  // Insert two distinct keys that will almost certainly share the same mocked
  // hash.
  hmap_t h1 = hmap_insert(&h, &ka, &va);
  hmap_t h2 = hmap_insert(&h1, &kb, &vb);
 
  TEST_CHECK(h2.len == 2);
  TEST_CHECK(h2.root != nullptr);
  // TEST_CHECK(h2.maybe_error == nullptr);
 
  void *pa = hmap_lookup(&h2, &ka, nullptr);
  void *pb = hmap_lookup(&h2, &kb, nullptr);
 
  TEST_CHECK(pa == &va);
  TEST_CHECK(pb == &vb);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
/// Hash hook that reads the hash straight from the key's first four bytes,
/// so a test can craft hashes with an exact bit pattern.
static hmap_hash_t test_hash_from_key_bytes(const hmap_t *hmap, const hmap_key_t *k) {
  (void)hmap;
  hmap_hash_t h = 0;
  memcpy(&h, k->data, sizeof(h));
  return h;
}
 
/// Two keys whose hashes agree on bits 0-29 (every full 5 bit fragment) and
/// differ only in bits 30-31 diverge at the trie's maximum depth. They must
/// end up in separate data slots, not in one collision node keyed by a single
/// bit position. A third key with a fully identical hash must still land in a
/// real collision node next to them.
static void test_hashmap_max_depth_divergence() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  hmap_control_t ctl = hmap_default_control;
  ctl.hash           = test_hash_from_key_bytes;
 
  // First four bytes are the crafted hash; the tag makes each key distinct.
  struct crafted_key {
    uint32_t hash;
    uint32_t tag;
  };
 
  struct crafted_key ka_bytes = {.hash = 0x00000001U, .tag = 1};
  struct crafted_key kb_bytes = {.hash = 0x00000001U | (1U << 30U), .tag = 2};
  struct crafted_key kc_bytes = {.hash = 0x00000001U, .tag = 3};
 
  hmap_key_t ka = {.data = &ka_bytes, .len = sizeof(ka_bytes)};
  hmap_key_t kb = {.data = &kb_bytes, .len = sizeof(kb_bytes)};
  hmap_key_t kc = {.data = &kc_bytes, .len = sizeof(kc_bytes)};
 
  int va = 1;
  int vb = 2;
  int vc = 3;
 
  hmap_t h0 = hmap_empty(ctx);
  // Inserting kb forces the merge at maximum depth with divergent final
  // fragments; inserting kc forces a genuine full collision with ka.
  hmap_t h1 = hmap_insert_ctl(&ctl, &h0, &ka, &va);
  hmap_t h2 = hmap_insert_ctl(&ctl, &h1, &kb, &vb);
  hmap_t h3 = hmap_insert_ctl(&ctl, &h2, &kc, &vc);
 
  TEST_CHECK(h3.len == 3);
 
  TEST_CHECK(hmap_lookup_ctl(&ctl, &h3, &ka, nullptr) == &va);
  TEST_CHECK(hmap_lookup_ctl(&ctl, &h3, &kb, nullptr) == &vb);
  TEST_CHECK(hmap_lookup_ctl(&ctl, &h3, &kc, nullptr) == &vc);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}
 
static void test_hashmap_update() {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  hmap_t h = hmap_empty(ctx);
 
  int a = 111;
  int b = 222;
 
  hmap_key_t ka = {.data = &a, .len = sizeof(a)};
  hmap_key_t kb = {.data = &b, .len = sizeof(b)};
 
  hashmap_dummy va = {.foo = 1, .bar = 10};
  hashmap_dummy vb = {.foo = 2, .bar = 20};
  hashmap_dummy vc = {.foo = 200, .bar = 400};
 
  // Insert two distinct keys that will almost certainly share the same mocked
  // hash.
  hmap_t h1 = hmap_insert(&h, &ka, &va);
  hmap_t h2 = hmap_insert(&h1, &kb, &vb);
  hmap_t h3 = hmap_insert(&h2, &ka, &vc);
 
  TEST_CHECK(h3.len == 2);
  TEST_CHECK(h3.root != nullptr);
  // TEST_CHECK(h3.maybe_error == nullptr);
 
  void *pa = hmap_lookup(&h3, &ka, nullptr);
  void *pb = hmap_lookup(&h3, &kb, nullptr);
 
  TEST_CHECK(pa == &vc);
  TEST_CHECK(pb == &vb);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}