array_list_tests.h File Reference

#include <stdio.h>
#include <serene/rt/context.h>
#include <serene/rt/impl/array_list.h>
#include "base.h"

Include dependency graph for array_list_tests.h:

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

Go to the source code of this file.

Data Structures
struct	al_dummy

Macros
#define	AL_TESTS(X)
#define	AL_TEST_LOG(...)

Typedefs
typedef struct al_dummy	al_dummy

Functions
static void	test_al_empty ()
static void	test_al_push_less_than_32 ()
static void	test_al_push_more_than_32 ()
static void	test_al_push_tail_to_trie_boundary ()
static void	test_al_get_out_of_bounds ()
static void	test_al_update ()
static void	test_al_remove ()
static void	test_al_remove_out_of_bounds ()
static void	test_al_remove_drain_and_push ()
static srn_error_t *	fe_all_visitor (array_list_t *al, size_t n, void *data)
static srn_error_t *	fe_early_exit_visitor (array_list_t *al, size_t n, void *data)
static void	test_al_for_each ()
static void	test_al_for_each_early_exit ()
static void	test_al_for_each_empty ()

Variables
static size_t	g_fe_count
static bool	g_fe_order_ok
static size_t	g_fe_stop_at

Macro Definition Documentation

AL_TEST_LOG

#define AL_TEST_LOG

(

...

)

Definition at line 44 of file array_list_tests.h.

AL_TESTS

#define AL_TESTS

(

X

)

Value:

X("array_list::empty", test_al_empty),                                              \
  X("array_list::push_less_than_32", test_al_push_less_than_32),                    \
  X("array_list::push_more_than_32", test_al_push_more_than_32),                    \
  X("array_list::tail_to_trie_boundary", test_al_push_tail_to_trie_boundary),       \
  X("array_list::get_out_of_bounds", test_al_get_out_of_bounds),                    \
  X("array_list::update", test_al_update), X("array_list::remove", test_al_remove), \
  X("array_list::remove_out_of_bounds", test_al_remove_out_of_bounds),              \
  X("array_list::remove_drain_and_push", test_al_remove_drain_and_push),            \
  X("array_list::for_each", test_al_for_each),                                      \
  X("array_list::for_each_early_exit", test_al_for_each_early_exit),                \
  X("array_list::for_each_empty", test_al_for_each_empty)

Definition at line 28 of file array_list_tests.h.

#define AL_TESTS(X)                                                                   \
  X("array_list::empty", test_al_empty),                                              \
    X("array_list::push_less_than_32", test_al_push_less_than_32),                    \
    X("array_list::push_more_than_32", test_al_push_more_than_32),                    \
    X("array_list::tail_to_trie_boundary", test_al_push_tail_to_trie_boundary),       \
    X("array_list::get_out_of_bounds", test_al_get_out_of_bounds),                    \
    X("array_list::update", test_al_update), X("array_list::remove", test_al_remove), \
    X("array_list::remove_out_of_bounds", test_al_remove_out_of_bounds),              \
    X("array_list::remove_drain_and_push", test_al_remove_drain_and_push),            \
    X("array_list::for_each", test_al_for_each),                                      \
    X("array_list::for_each_early_exit", test_al_for_each_early_exit),                \
    X("array_list::for_each_empty", test_al_for_each_empty)

Typedef Documentation

al_dummy

typedef struct al_dummy al_dummy

Function Documentation

fe_all_visitor()

srn_error_t * fe_all_visitor ( array_list_t * al, size_t n, void * data )

static

Definition at line 420 of file array_list_tests.h.

                                                                           {
  UNUSED(al);
  g_fe_count++;
 
  if (((al_dummy *)data)->foo != (int)n) {
    g_fe_order_ok = false;
  }
 
  return nullptr;
}

Here is the caller graph for this function:

fe_early_exit_visitor()

srn_error_t * fe_early_exit_visitor ( array_list_t * al, size_t n, void * data )

static

Definition at line 431 of file array_list_tests.h.

                                                                                  {
  UNUSED(data);
  g_fe_count++;
 
  if (n == g_fe_stop_at) {
    return ERR(al->ctx, INDEX_OUT_OF_BOUND, "stop");
  }
 
  return nullptr;
}

Here is the caller graph for this function:

test_al_empty()

void test_al_empty ( )

static

Definition at line 52 of file array_list_tests.h.

                            {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  TEST_CHECK(s.len == 0);
  TEST_CHECK(s.tail_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_al_for_each()

void test_al_for_each ( )

static

Definition at line 444 of file array_list_tests.h.

                               {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (int i = 0; i < 100; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    d->bar      = 3000 - i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  g_fe_count    = 0;
  g_fe_order_ok = true;
 
  auto err = array_list_for_each(&s, fe_all_visitor);
  ASSERT_NULL(err);
  TEST_CHECK(g_fe_count == 100);
  TEST_CHECK(g_fe_order_ok);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_for_each_early_exit()

void test_al_for_each_early_exit ( )

static

Definition at line 471 of file array_list_tests.h.

                                          {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (int i = 0; i < 20; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  g_fe_count   = 0;
  g_fe_stop_at = 5;
 
  auto err = array_list_for_each(&s, fe_early_exit_visitor);
  ASSERT_NOT_NULL(err);
  TEST_CHECK(err->tag == INDEX_OUT_OF_BOUND);
  // The callback ran for indices 0..5 inclusive, so 6 calls total.
  TEST_CHECK(g_fe_count == 6);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_for_each_empty()

void test_al_for_each_empty ( )

static

Definition at line 497 of file array_list_tests.h.

                                     {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  g_fe_count = 0;
 
  auto err = array_list_for_each(&s, fe_all_visitor);
  ASSERT_NULL(err);
  TEST_CHECK(g_fe_count == 0);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_get_out_of_bounds()

void test_al_get_out_of_bounds ( )

static

Definition at line 207 of file array_list_tests.h.

                                        {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  // Empty list: index 0 is already out of bounds.
  auto empty = array_list_get(&s, 0);
  ASSERT_NOT_NULL(empty.maybe_error);
  TEST_CHECK(empty.maybe_error->tag == INDEX_OUT_OF_BOUND);
  ASSERT_NULL(empty.data);
 
  for (int i = 0; i < 40; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    d->bar      = 3000 - i;
    auto err    = array_list_push(&s, d);
    ASSERT_NULL(err);
  }
 
  // The first invalid index is exactly len.
  auto at_len = array_list_get(&s, s.len);
  ASSERT_NOT_NULL(at_len.maybe_error);
  TEST_CHECK(at_len.maybe_error->tag == INDEX_OUT_OF_BOUND);
  ASSERT_NULL(at_len.data);
 
  // A far larger index fails the same way and exercises the message sizing path.
  auto far = array_list_get(&s, s.len + 1000);
  ASSERT_NOT_NULL(far.maybe_error);
  TEST_CHECK(far.maybe_error->tag == INDEX_OUT_OF_BOUND);
  ASSERT_NULL(far.data);
 
  // The last valid index still succeeds.
  auto last = array_list_get(&s, s.len - 1);
  TEST_NO_ERROR(last);
  ASSERT_NOT_NULL(last.data);
  TEST_CHECK(((al_dummy *)last.data)->foo == 39);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_push_less_than_32()

void test_al_push_less_than_32 ( )

static

Definition at line 67 of file array_list_tests.h.

                                        {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (size_t i = 0; i < 31; i++) {
    auto g   = ALLOC(ctx, al_dummy);
    g->bar   = (int)i + 1;
    g->foo   = (int)i + 2;
    auto err = array_list_push(&s, g);
    ASSERT_NULL(err);
 
    TEST_CHECK(s.len == i + 1);
    TEST_CHECK(s.tail_len == i + 1);
    TEST_CHECK(s.root == nullptr);
    TEST_CHECK(s.maybe_error == nullptr);
  }
 
  for (size_t i = 0; i < 30; i++) {
    auto res = array_list_get(&s, i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
 
    al_dummy *d = res.data;
    TEST_CHECK(d->foo == (int)(i + 2));
    TEST_CHECK(d->bar == (int)(i + 1));
  }
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_push_more_than_32()

void test_al_push_more_than_32 ( )

static

Definition at line 100 of file array_list_tests.h.

                                        {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (int i = 0; i < 2000; i++) {
 
    al_dummy *d = ALLOC(ctx, al_dummy);
    ASSERT_NOT_NULL(d);
    d->foo   = i;
    d->bar   = 3000 - i;
    auto err = array_list_push(&s, d);
    ASSERT_NULL(err);
  }
 
  TEST_CHECK(s.len == 2000);
  TEST_CHECK(s.tail_len == 16);
  TEST_CHECK(s.root != nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  al_dummy *d1 = (al_dummy *)s.tail[0];
 
  ASSERT_NOT_NULL(d1);
  TEST_CHECK(d1->foo == 1984);
  TEST_CHECK(d1->bar == 3000 - d1->foo);
 
  al_dummy *d2 = (al_dummy *)s.tail[s.tail_len - 1];
  ASSERT_NOT_NULL(d2);
  TEST_CHECK(d2->foo == 1999);
  TEST_CHECK(d2->bar == 3000 - d2->foo);
 
  for (int i = 0; i < 2000; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
 
    al_dummy *d = res.data;
 
    // AL_TEST_LOG("%d %d %d", i, d->foo, d->bar);
    TEST_CHECK(d->foo == i);
    TEST_CHECK(d->bar == 3000 - i);
  };
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_push_tail_to_trie_boundary()

void test_al_push_tail_to_trie_boundary ( )

static

Definition at line 151 of file array_list_tests.h.

                                                 {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  // Fill the tail exactly to AL_BR. Everything still lives in the tail.
  for (int i = 0; i < 32; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    d->bar      = 3000 - i;
    auto err    = array_list_push(&s, d);
    ASSERT_NULL(err);
  }
 
  TEST_CHECK(s.len == 32);
  TEST_CHECK(s.tail_len == 32);
  TEST_CHECK(s.root == nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  // One more push moves the full tail into the trie and starts a fresh tail.
  al_dummy *d = ALLOC(ctx, al_dummy);
  d->foo      = 32;
  d->bar      = 3000 - 32;
  auto err    = array_list_push(&s, d);
  ASSERT_NULL(err);
 
  TEST_CHECK(s.len == 33);
  TEST_CHECK(s.tail_len == 1);
  TEST_CHECK(s.root != nullptr);
  TEST_CHECK(s.depth == 0);
  TEST_CHECK(s.maybe_error == nullptr);
 
  // The last element of the old tail now lives in the trie, the new one in the
  // fresh tail, and the first element is still reachable.
  auto first = array_list_get(&s, 0);
  TEST_NO_ERROR(first);
  ASSERT_NOT_NULL(first.data);
  TEST_CHECK(((al_dummy *)first.data)->foo == 0);
 
  auto last_moved = array_list_get(&s, 31);
  TEST_NO_ERROR(last_moved);
  ASSERT_NOT_NULL(last_moved.data);
  TEST_CHECK(((al_dummy *)last_moved.data)->foo == 31);
 
  auto in_tail = array_list_get(&s, 32);
  TEST_NO_ERROR(in_tail);
  ASSERT_NOT_NULL(in_tail.data);
  TEST_CHECK(((al_dummy *)in_tail.data)->foo == 32);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_remove()

void test_al_remove ( )

static

Definition at line 286 of file array_list_tests.h.

                             {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  // foo carries the logical index so a shift is visible after removal.
  for (int i = 0; i < 100; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    d->bar      = 3000 - i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  auto err = array_list_remove(&s, 50);
  ASSERT_NULL(err);
  TEST_CHECK(s.len == 99);
 
  // Elements before the hole are untouched, everything after slid down one.
  for (int i = 0; i < 99; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
    int expected = i < 50 ? i : i + 1;
    TEST_CHECK(((al_dummy *)res.data)->foo == expected);
  }
 
  // The old last index is now out of bounds.
  auto gone = array_list_get(&s, 99);
  ASSERT_NOT_NULL(gone.maybe_error);
  TEST_CHECK(gone.maybe_error->tag == INDEX_OUT_OF_BOUND);
 
  // Removing the final element is the pop case: no shift, just a shrink.
  ASSERT_NULL(array_list_remove(&s, s.len - 1));
  TEST_CHECK(s.len == 98);
  auto last = array_list_get(&s, s.len - 1);
  TEST_NO_ERROR(last);
  // Index 97 held foo 98 after the first removal, and dropping the final
  // element does not disturb it.
  TEST_CHECK(((al_dummy *)last.data)->foo == 98);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_remove_drain_and_push()

void test_al_remove_drain_and_push ( )

static

Definition at line 362 of file array_list_tests.h.

                                            {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  for (int i = 0; i < 2000; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  // Drop the front 1990 times; the survivors are the original 1990..1999.
  for (int i = 0; i < 1990; i++) {
    ASSERT_NULL(array_list_remove(&s, 0));
  }
  TEST_CHECK(s.len == 10);
 
  for (int i = 0; i < 10; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    ASSERT_NOT_NULL(res.data);
    TEST_CHECK(((al_dummy *)res.data)->foo == 1990 + i);
  }
 
  // Push a fresh batch into the shrunken trie.
  for (int i = 0; i < 2000; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = 10000 + i;
    ASSERT_NULL(array_list_push(&s, d));
  }
  TEST_CHECK(s.len == 2010);
 
  // The ten survivors are still first, the new batch follows in order.
  for (int i = 0; i < 10; i++) {
    auto res = array_list_get(&s, (size_t)i);
    TEST_NO_ERROR(res);
    TEST_CHECK(((al_dummy *)res.data)->foo == 1990 + i);
  }
  for (int i = 0; i < 2000; i++) {
    auto res = array_list_get(&s, (size_t)(10 + i));
    TEST_NO_ERROR(res);
    TEST_CHECK(((al_dummy *)res.data)->foo == 10000 + i);
  }
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_remove_out_of_bounds()

void test_al_remove_out_of_bounds ( )

static

Definition at line 333 of file array_list_tests.h.

                                           {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  auto empty = array_list_remove(&s, 0);
  ASSERT_NOT_NULL(empty);
  TEST_CHECK(empty->tag == INDEX_OUT_OF_BOUND);
  TEST_CHECK(s.len == 0);
 
  for (int i = 0; i < 40; i++) {
    al_dummy *d = ALLOC(ctx, al_dummy);
    d->foo      = i;
    ASSERT_NULL(array_list_push(&s, d));
  }
 
  auto at_len = array_list_remove(&s, s.len);
  ASSERT_NOT_NULL(at_len);
  TEST_CHECK(at_len->tag == INDEX_OUT_OF_BOUND);
  TEST_CHECK(s.len == 40);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_al_update()

void test_al_update ( )

static

Definition at line 249 of file array_list_tests.h.

                             {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  auto s = array_list_empty(ctx);
 
  al_dummy *a = ALLOC(ctx, al_dummy);
  a->foo      = 1;
  a->bar      = 1;
  ASSERT_NULL(array_list_push(&s, a));
 
  al_dummy *b = ALLOC(ctx, al_dummy);
  b->foo      = 2;
  b->bar      = 2;
 
  // a and b are distinct allocations, so distinct pointers.
  TEST_CHECK(a != b);
 
  // Precondition: slot 0 holds `a`.
  auto before = array_list_get(&s, 0);
  TEST_NO_ERROR(before);
  TEST_CHECK(before.data == a);
 
  // Update slot 0 to point at `b`.
  ASSERT_NULL(array_list_update(&s, 0, b));
 
  // Postcondition: a fresh fetch must now yield `b`, not `a`.
  auto after = array_list_get(&s, 0);
  TEST_NO_ERROR(after);
  TEST_CHECK(after.data == b);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

Variable Documentation

g_fe_count

size_t g_fe_count

static

Definition at line 416 of file array_list_tests.h.

g_fe_order_ok

bool g_fe_order_ok

static

Definition at line 417 of file array_list_tests.h.

g_fe_stop_at

size_t g_fe_stop_at

static

Definition at line 418 of file array_list_tests.h.