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 <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::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(ctx, &h, &k, &d);
 
  void *dptr = hmap_lookup(ctx, &h1, &k, nullptr);
  TEST_CHECK(dptr != nullptr);
  TEST_CHECK(dptr == &d);
 
  int default_v      = 999;
  void *dptr_missing = hmap_lookup(ctx, &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;
 
  // IMPORTANT: hmap stores pointers to hmap_key_t, so these must outlive
  // inserts.
  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(ctx, &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(ctx, &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(ctx, &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(ctx, &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(ctx, &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(ctx, &h, &ka, &va);
  hmap_t h2 = hmap_insert(ctx, &h1, &kb, &vb);
 
  TEST_CHECK(h2.len == 2);
  TEST_CHECK(h2.root != nullptr);
  // TEST_CHECK(h2.maybe_error == nullptr);
 
  void *pa = hmap_lookup(ctx, &h2, &ka, nullptr);
  void *pb = hmap_lookup(ctx, &h2, &kb, nullptr);
 
  TEST_CHECK(pa == &va);
  TEST_CHECK(pb == &vb);
 
  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(ctx, &h, &ka, &va);
  hmap_t h2 = hmap_insert(ctx, &h1, &kb, &vb);
  hmap_t h3 = hmap_insert(ctx, &h2, &ka, &vc);
 
  TEST_CHECK(h3.len == 2);
  TEST_CHECK(h3.root != nullptr);
  // TEST_CHECK(h3.maybe_error == nullptr);
 
  void *pa = hmap_lookup(ctx, &h3, &ka, nullptr);
  void *pb = hmap_lookup(ctx, &h3, &kb, nullptr);
 
  TEST_CHECK(pa == &vc);
  TEST_CHECK(pb == &vb);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}