containers/tests/map_container.c

#include "malunal/containers/map.h"
#include "malunal/containers/vector.h"
#include "malunal/microtest.h"

MICROTEST(map_container, can_init_and_free) {
  error_t         result    = {};
  map_container_t map       = {};
  malunal_size_t  temporary = 0;

  result = map_container_init(4, 8, libc_allocator(), &map);
  MICROTEST_EXPECT_NULL(result.domain);

  allocator_mptr_t allocator;
  result = map_container_allocator(&map, &allocator);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_PTR_EQ(allocator, libc_allocator());

  result = map_container_key_stride(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, 4);

  result = map_container_value_stride(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, 8);

  result = map_container_stride(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, 12);

  result = map_container_count(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, 0);

  result = map_container_capacity(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, MALUNAL_CONTAINERS_MAP_INIT_CAPACITY);

  result = map_container_free(&map);
  MICROTEST_EXPECT_NULL(result.domain);

  result = map_container_stride(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, 0);

  result = map_container_count(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, 0);

  result = map_container_capacity(&map, &temporary);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(temporary, 0);
}

MICROTEST(map_container, reports_a_null_map) {
  error_t        result    = {};
  malunal_size_t temporary = 0;

  result = map_container_count(null, &temporary);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  MICROTEST_EXPECT_EQ(result.code, CONTAINER_ERROR_NULL_CONTAINER);

  malunal_int32_t key   = 1;
  malunal_int32_t value = 2;
  result = map_container_insert(null, &key, &value);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  MICROTEST_EXPECT_EQ(result.code, CONTAINER_ERROR_NULL_CONTAINER);
}

MICROTEST(map_container, insert_then_get_round_trips_value) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key   = 42;
  malunal_int32_t value = 1337;
  result = map_container_insert(&map, &key, &value);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t count = 0;
  result = map_container_count(&map, &count);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(count, 1);

  malunal_int32_t out = 0;
  result = map_container_get(&map, &key, &out);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(out, 1337);

  map_container_free(&map);
}

MICROTEST(map_container, insert_of_existing_key_overwrites_value) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key    = 7;
  malunal_int32_t first  = 10;
  malunal_int32_t second = 20;
  map_container_insert(&map, &key, &first);
  result = map_container_insert(&map, &key, &second);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t count = 0;
  map_container_count(&map, &count);
  MICROTEST_EXPECT_EQ(count, 1);

  malunal_int32_t out = 0;
  map_container_get(&map, &key, &out);
  MICROTEST_EXPECT_EQ(out, 20);

  map_container_free(&map);
}

MICROTEST(map_container, append_inserts_the_pair) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key   = 3;
  malunal_int32_t value = 300;
  map_pair_t      pair  = { .key = &key, .value = &value };
  result = map_container_append(&map, &pair);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_int32_t out = 0;
  result = map_container_get(&map, &key, &out);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(out, 300);

  map_container_free(&map);
}

MICROTEST(map_container, get_reports_a_missing_key) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key   = 1;
  malunal_int32_t value = 100;
  map_container_insert(&map, &key, &value);

  malunal_int32_t missing = 404;
  malunal_int32_t out     = 0;
  result = map_container_get(&map, &missing, &out);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  MICROTEST_EXPECT_EQ(result.code, CONTAINER_ERROR_OUT_OF_BOUNDS);

  map_container_free(&map);
}

MICROTEST(map_container, set_overwrites_an_existing_key_only) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key   = 5;
  malunal_int32_t value = 50;
  map_container_insert(&map, &key, &value);

  malunal_int32_t replacement = 555;
  result = map_container_set(&map, &key, &replacement);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_int32_t out = 0;
  map_container_get(&map, &key, &out);
  MICROTEST_EXPECT_EQ(out, 555);

  malunal_int32_t missing = 404;
  result = map_container_set(&map, &missing, &replacement);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  MICROTEST_EXPECT_EQ(result.code, CONTAINER_ERROR_OUT_OF_BOUNDS);

  malunal_size_t count = 0;
  map_container_count(&map, &count);
  MICROTEST_EXPECT_EQ(count, 1);

  map_container_free(&map);
}

MICROTEST(map_container, contains_finds_a_present_key) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key   = 9;
  malunal_int32_t value = 90;
  map_container_insert(&map, &key, &value);

  result = map_container_contains(&map, &key);
  MICROTEST_EXPECT_NULL(result.domain);

  map_container_free(&map);
}

MICROTEST(map_container, contains_rejects_an_absent_key) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key   = 9;
  malunal_int32_t value = 90;
  map_container_insert(&map, &key, &value);

  malunal_int32_t missing = 404;
  result = map_container_contains(&map, &missing);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  MICROTEST_EXPECT_EQ(result.code, CONTAINER_ERROR_FAILURE);

  map_container_free(&map);
}

MICROTEST(map_container, remove_erases_the_key) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t keys[2] = { 1, 2 };
  malunal_int32_t vals[2] = { 10, 20 };
  map_container_insert(&map, &keys[0], &vals[0]);
  map_container_insert(&map, &keys[1], &vals[1]);

  result = map_container_remove(&map, &keys[0]);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t count = 0;
  map_container_count(&map, &count);
  MICROTEST_EXPECT_EQ(count, 1);

  result = map_container_contains(&map, &keys[0]);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);

  malunal_int32_t out = 0;
  result = map_container_get(&map, &keys[1], &out);
  MICROTEST_EXPECT_NULL(result.domain);
  MICROTEST_EXPECT_EQ(out, 20);

  map_container_free(&map);
}

MICROTEST(map_container, remove_of_absent_key_succeeds) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t key   = 1;
  malunal_int32_t value = 10;
  map_container_insert(&map, &key, &value);

  malunal_int32_t missing = 404;
  result = map_container_remove(&map, &missing);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t count = 0;
  map_container_count(&map, &count);
  MICROTEST_EXPECT_EQ(count, 1);

  map_container_free(&map);
}

MICROTEST(map_container, remove_keeps_the_other_keys_reachable) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  for (malunal_int32_t index = 0; index < 256; index++) {
    malunal_int32_t value = index * 3;
    map_container_insert(&map, &index, &value);
  }

  for (malunal_int32_t index = 0; index < 256; index += 2)
    map_container_remove(&map, &index);

  malunal_size_t count = 0;
  map_container_count(&map, &count);
  MICROTEST_EXPECT_EQ(count, 128);

  for (malunal_int32_t index = 1; index < 256; index += 2) {
    malunal_int32_t out = 0;
    result = map_container_get(&map, &index, &out);
    MICROTEST_EXPECT_NULL(result.domain);
    MICROTEST_EXPECT_EQ(out, index * 3);
  }

  for (malunal_int32_t index = 0; index < 256; index += 2) {
    result = map_container_contains(&map, &index);
    MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  }

  map_container_free(&map);
}

MICROTEST(map_container, remove_reuses_the_erased_slots) {
  map_container_t map = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_size_t oldcap = 0;
  map_container_capacity(&map, &oldcap);
  for (malunal_int32_t index = 0; index < 4096; index++) {
    malunal_int32_t value = index * 2;
    map_container_insert(&map, &index, &value);
    map_container_remove(&map, &index);
  }

  malunal_size_t newcap = 0;
  malunal_size_t count  = 0;
  map_container_capacity(&map, &newcap);
  map_container_count(&map, &count);
  MICROTEST_EXPECT_EQ(count, 0);
  MICROTEST_EXPECT_EQ(newcap, oldcap);

  map_container_free(&map);
}

MICROTEST(map_container, clear_resets_count_but_keeps_capacity) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_int32_t keys[2] = { 1, 2 };
  malunal_int32_t vals[2] = { 10, 20 };
  map_container_insert(&map, &keys[0], &vals[0]);
  map_container_insert(&map, &keys[1], &vals[1]);

  result = map_container_clear(&map);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t count    = 99;
  malunal_size_t capacity = 0;
  map_container_count(&map, &count);
  map_container_capacity(&map, &capacity);
  MICROTEST_EXPECT_EQ(count, 0);
  MICROTEST_EXPECT_EQ(capacity, MALUNAL_CONTAINERS_MAP_INIT_CAPACITY);

  result = map_container_contains(&map, &keys[0]);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);

  map_container_free(&map);
}

MICROTEST(map_container, insert_past_load_factor_grows_the_map) {
  map_container_t map = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  malunal_size_t capacity = 0;
  for (malunal_int32_t index = 0; index < 11; index++) {
    malunal_int32_t value = index * 10;
    map_container_insert(&map, &index, &value);
  }

  map_container_capacity(&map, &capacity);
  MICROTEST_EXPECT_EQ(capacity, MALUNAL_CONTAINERS_MAP_INIT_CAPACITY);

  malunal_int32_t key   = 11;
  malunal_int32_t value = 110;
  map_container_insert(&map, &key, &value);
  map_container_capacity(&map, &capacity);
  MICROTEST_EXPECT_EQ(capacity, MALUNAL_CONTAINERS_MAP_INIT_CAPACITY * 2);

  map_container_free(&map);
}

MICROTEST(map_container, growth_preserves_every_pair) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  for (malunal_int32_t index = 0; index < 1000; index++) {
    malunal_int32_t value = index * 7;
    result = map_container_insert(&map, &index, &value);
    MICROTEST_EXPECT_NULL(result.domain);
  }

  malunal_size_t count    = 0;
  malunal_size_t capacity = 0;
  map_container_count(&map, &count);
  map_container_capacity(&map, &capacity);
  MICROTEST_EXPECT_EQ(count, 1000);
  MICROTEST_EXPECT_GE(capacity, 1334);

  for (malunal_int32_t index = 0; index < 1000; index++) {
    malunal_int32_t out = 0;
    result = map_container_get(&map, &index, &out);
    MICROTEST_EXPECT_NULL(result.domain);
    MICROTEST_EXPECT_EQ(out, index * 7);
  }

  map_container_free(&map);
}

MICROTEST(map_container, resize_rounds_to_power_of_two) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  result = map_container_resize(&map, 24);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t capacity = 0;
  map_container_capacity(&map, &capacity);
  MICROTEST_EXPECT_EQ(capacity, 32);

  map_container_free(&map);
}

MICROTEST(map_container, resize_preserves_pairs_and_the_count) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  for (malunal_int32_t index = 0; index < 8; index++) {
    malunal_int32_t value = index * 11;
    map_container_insert(&map, &index, &value);
  }

  result = map_container_resize(&map, 128);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t count = 0;
  map_container_count(&map, &count);
  MICROTEST_EXPECT_EQ(count, 8);

  for (malunal_int32_t index = 0; index < 8; index++) {
    malunal_int32_t out = 0;
    result = map_container_get(&map, &index, &out);
    MICROTEST_EXPECT_NULL(result.domain);
    MICROTEST_EXPECT_EQ(out, index * 11);
  }

  map_container_free(&map);
}

MICROTEST(map_container, reserve_holds_the_pairs_without_regrowing) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);

  result = map_container_reserve(&map, 100);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t reserved = 0;
  map_container_capacity(&map, &reserved);
  MICROTEST_EXPECT_GE(reserved, 134);

  for (malunal_int32_t index = 0; index < 100; index++) {
    malunal_int32_t value = index;
    map_container_insert(&map, &index, &value);
  }

  malunal_size_t capacity = 0;
  map_container_capacity(&map, &capacity);
  MICROTEST_EXPECT_EQ(capacity, reserved);

  map_container_free(&map);
}

MICROTEST(map_container, keys_and_values_line_up_with_each_other) {
  error_t            result = {};
  map_container_t    map    = {};
  vector_container_t keys   = {};
  vector_container_t values = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);
  vector_container_init(sizeof(malunal_int32_t), libc_allocator(), &keys);
  vector_container_init(sizeof(malunal_int32_t), libc_allocator(), &values);

  for (malunal_int32_t index = 0; index < 50; index++) {
    malunal_int32_t value = index * 5;
    map_container_insert(&map, &index, &value);
  }

  result = map_container_keys(&map, (container_mptr_t)&keys);
  MICROTEST_EXPECT_NULL(result.domain);

  result = map_container_values(&map, (container_mptr_t)&values);
  MICROTEST_EXPECT_NULL(result.domain);

  malunal_size_t keycount = 0;
  malunal_size_t valcount = 0;
  vector_container_count(&keys, &keycount);
  vector_container_count(&values, &valcount);
  MICROTEST_EXPECT_EQ(keycount, 50);
  MICROTEST_EXPECT_EQ(valcount, 50);

  for (malunal_size_t index = 0; index < keycount; index++) {
    malunal_int32_t key      = 0;
    malunal_int32_t value    = 0;
    malunal_int32_t expected = 0;
    vector_container_get(&keys, index, &key);
    vector_container_get(&values, index, &value);
    map_container_get(&map, &key, &expected);
    MICROTEST_EXPECT_EQ(value, expected);
    MICROTEST_EXPECT_EQ(value, key * 5);
  }

  vector_container_free(&values);
  vector_container_free(&keys);
  map_container_free(&map);
}

MICROTEST(map_container, keys_rejects_a_mismatched_container) {
  error_t            result = {};
  map_container_t    map    = {};
  vector_container_t keys   = {};
  map_container_init(sizeof(malunal_int32_t), sizeof(malunal_int32_t),
                     libc_allocator(), &map);
  vector_container_init(sizeof(malunal_int64_t), libc_allocator(), &keys);

  result = map_container_keys(&map, (container_mptr_t)&keys);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  MICROTEST_EXPECT_EQ(result.code, CONTAINER_ERROR_FAILURE);

  result = map_container_keys(&map, null);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);
  MICROTEST_EXPECT_EQ(result.code, CONTAINER_ERROR_NULL_RECEIVER);

  vector_container_free(&keys);
  map_container_free(&map);
}

MICROTEST(map_container, handles_keys_which_are_not_scalars) {
  error_t         result = {};
  map_container_t map    = {};
  map_container_init(8, sizeof(malunal_int32_t), libc_allocator(), &map);

  malunal_char_t keys[3][8] = { "alpha", "beta", "gamma" };
  for (malunal_int32_t index = 0; index < 3; index++) {
    malunal_int32_t value = index + 1;
    result = map_container_insert(&map, keys[index], &value);
    MICROTEST_EXPECT_NULL(result.domain);
  }

  for (malunal_int32_t index = 0; index < 3; index++) {
    malunal_int32_t out = 0;
    result = map_container_get(&map, keys[index], &out);
    MICROTEST_EXPECT_NULL(result.domain);
    MICROTEST_EXPECT_EQ(out, index + 1);
  }

  malunal_char_t missing[8] = "delta";
  result = map_container_contains(&map, missing);
  MICROTEST_EXPECT_PTR_EQ(result.domain, &ERROR_DOMAIN_CONTAINER_T);

  map_container_free(&map);
}