hashmap_tests.h File Reference

#include <stdio.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 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::update", test_hashmap_update)

Definition at line 29 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::update", test_hashmap_update)

Typedef Documentation

hashmap_dummy

typedef struct hashmap_dummy hashmap_dummy

Function Documentation

test_hashmap_collision_node_lookup()

static void test_hashmap_collision_node_lookup ( )

static

Definition at line 179 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(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);
}

Here is the call graph for this function:

test_hashmap_empty()

static 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(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);
}

Here is the call graph for this function:

test_hashmap_make_sure_hash_is_deterministic()

static 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()

static 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;
 
  // 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);
}

Here is the call graph for this function:

test_hashmap_update()

static void test_hashmap_update ( )

static

Definition at line 213 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(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);
}

Here is the call graph for this function: