hashmap_tests.h File Reference

#include <stdio.h>
#include <string.h>
#include <serene/rt/context.h>
#include <serene/rt/impl/hashmap.h>
#include "acutest.h"
#include "base.h"

Include dependency graph for hashmap_tests.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	hashmap_dummy

Macros
#define	HMAP_TESTS(X)
#define	HMAP_TEST_LOG(...)

Typedefs
typedef struct hashmap_dummy	hashmap_dummy

Functions
static void	test_hashmap_empty ()
void	test_hashmap_insert_kv ()
static void	test_hashmap_make_sure_hash_is_deterministic ()
static void	test_hashmap_many_insert_and_lookup ()
static void	test_hashmap_collision_node_lookup ()
static hmap_hash_t	test_hash_from_key_bytes (const hmap_t *hmap, const hmap_key_t *k)
	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 void	test_hashmap_max_depth_divergence ()
	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.
static void	test_hashmap_update ()

Macro Definition Documentation

HMAP_TEST_LOG

#define HMAP_TEST_LOG

(

...

)

Value:

DBG("HMAP_TEST", __VA_ARGS__)

Definition at line 39 of file hashmap_tests.h.

HMAP_TESTS

#define HMAP_TESTS

(

X

)

Value:

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)

Definition at line 30 of file hashmap_tests.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)

Typedef Documentation

hashmap_dummy

typedef struct hashmap_dummy hashmap_dummy

Function Documentation

test_hash_from_key_bytes()

hmap_hash_t test_hash_from_key_bytes ( const hmap_t * hmap, const hmap_key_t * k )

static

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.

Definition at line 213 of file hashmap_tests.h.

                                                                                     {
  (void)hmap;
  hmap_hash_t h = 0;
  memcpy(&h, k->data, sizeof(h));
  return h;
}

Here is the caller graph for this function:

test_hashmap_collision_node_lookup()

void test_hashmap_collision_node_lookup ( )

static

Definition at line 177 of file hashmap_tests.h.

                                                 {
  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);
}

Here is the call graph for this function:

test_hashmap_empty()

void test_hashmap_empty ( )

static

Definition at line 46 of file hashmap_tests.h.

                                 {
  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);
}

Here is the call graph for this function:

test_hashmap_insert_kv()

void test_hashmap_insert_kv

(

)

Definition at line 59 of file hashmap_tests.h.

                              {
  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);
}

Here is the call graph for this function:

test_hashmap_make_sure_hash_is_deterministic()

void test_hashmap_make_sure_hash_is_deterministic ( )

static

Definition at line 89 of file hashmap_tests.h.

                                                           {
  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);
}

Here is the call graph for this function:

test_hashmap_many_insert_and_lookup()

void test_hashmap_many_insert_and_lookup ( )

static

Definition at line 104 of file hashmap_tests.h.

                                                  {
  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);
}

Here is the call graph for this function:

test_hashmap_max_depth_divergence()

void test_hashmap_max_depth_divergence ( )

static

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.

Definition at line 225 of file hashmap_tests.h.

                                                {
  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);
}

Here is the call graph for this function:

test_hashmap_update()

void test_hashmap_update ( )

static

Definition at line 267 of file hashmap_tests.h.

                                  {
  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);
}

Here is the call graph for this function: