seq_tests.h File Reference

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

Include dependency graph for seq_tests.h:

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

Go to the source code of this file.

Data Structures
struct	seq_dummy

Macros
#define	SEQ_TESTS(X)
#define	SEQ_TEST_LOG(...)

Typedefs
typedef struct seq_dummy	seq_dummy

Functions
static void	test_seq_empty ()
void	test_seq_push_less_than_32 ()
void	test_seq_push_more_than_32 ()
static void	test_seq_branching_push ()
	Two pushes branched off one head must not see each other's element.
static void	test_seq_branching_promotion ()
	Two branches that each promote their own diverging tail into the same root slot must not overwrite each other.

Macro Definition Documentation

SEQ_TEST_LOG

#define SEQ_TEST_LOG

(

...

)

Definition at line 37 of file seq_tests.h.

SEQ_TESTS

#define SEQ_TESTS

(

X

)

Value:

X("seq::empty", test_seq_empty), X("seq::push_less_than_32", test_seq_push_less_than_32), \
  X("seq::push_more_than_32", test_seq_push_more_than_32),                                \
  X("seq::branching_push", test_seq_branching_push),                                      \
  X("seq::branching_promotion", test_seq_branching_promotion)

Definition at line 28 of file seq_tests.h.

#define SEQ_TESTS(X)                                                                        \
  X("seq::empty", test_seq_empty), X("seq::push_less_than_32", test_seq_push_less_than_32), \
    X("seq::push_more_than_32", test_seq_push_more_than_32),                                \
    X("seq::branching_push", test_seq_branching_push),                                      \
    X("seq::branching_promotion", test_seq_branching_promotion)

Typedef Documentation

seq_dummy

typedef struct seq_dummy seq_dummy

Function Documentation

test_seq_branching_promotion()

void test_seq_branching_promotion ( )

static

Two branches that each promote their own diverging tail into the same root slot must not overwrite each other.

96 shared elements put the base at a 64 element tree plus a full tail; 33 pushes per branch force two promotions each, the second landing in the same fringe slot of a root that used to be shared.

Definition at line 170 of file seq_tests.h.

                                           {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  int *vals = ALLOCN(ctx, int, 96);
  seq_t s   = seq_empty(ctx);
  for (int i = 0; i < 96; i++) {
    vals[i] = i;
    s       = seq_push(&s, (seq_elem_t)&vals[i]);
  }
 
  int *b1_vals = ALLOCN(ctx, int, 33);
  int *b2_vals = ALLOCN(ctx, int, 33);
  seq_t b1     = s;
  seq_t b2     = s;
  for (int i = 0; i < 33; i++) {
    b1_vals[i] = 1000 + i;
    b2_vals[i] = 2000 + i;
    b1         = seq_push(&b1, (seq_elem_t)&b1_vals[i]);
    b2         = seq_push(&b2, (seq_elem_t)&b2_vals[i]);
  }
 
  TEST_CHECK(s.len == 96);
  TEST_CHECK(b1.len == 129);
  TEST_CHECK(b2.len == 129);
 
  // The shared prefix must read the same through every head.
  for (int i = 0; i < 96; i++) {
    TEST_CHECK(seq_get(&s, (size_t)i).data == (seq_elem_t)&vals[i]);
    TEST_CHECK(seq_get(&b1, (size_t)i).data == (seq_elem_t)&vals[i]);
    TEST_CHECK(seq_get(&b2, (size_t)i).data == (seq_elem_t)&vals[i]);
  }
 
  // Each branch must read only its own suffix.
  for (int i = 0; i < 33; i++) {
    TEST_CHECK(seq_get(&b1, (size_t)(96 + i)).data == (seq_elem_t)&b1_vals[i]);
    TEST_CHECK(seq_get(&b2, (size_t)(96 + i)).data == (seq_elem_t)&b2_vals[i]);
  }
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_seq_branching_push()

void test_seq_branching_push ( )

static

Two pushes branched off one head must not see each other's element.

The tail buffer is shared between versions, so without copy on write the second push clobbers the first branch's slot.

Definition at line 131 of file seq_tests.h.

                                      {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  seq_t s = seq_empty(ctx);
  for (int i = 0; i < 5; i++) {
    seq_dummy *d = ALLOC(ctx, seq_dummy);
    d->foo       = i;
    d->bar       = i;
    s            = seq_push(&s, (seq_elem_t)d);
  }
 
  seq_dummy da = {.foo = 100, .bar = 1};
  seq_dummy db = {.foo = 200, .bar = 2};
 
  seq_t b1 = seq_push(&s, (seq_elem_t)&da);
  seq_t b2 = seq_push(&s, (seq_elem_t)&db);
 
  TEST_CHECK(s.len == 5);
  TEST_CHECK(b1.len == 6);
  TEST_CHECK(b2.len == 6);
 
  seq_lookup_result_t r1 = seq_get(&b1, 5);
  TEST_CHECK(r1.maybe_error == nullptr);
  TEST_CHECK(r1.data == (seq_elem_t)&da);
 
  seq_lookup_result_t r2 = seq_get(&b2, 5);
  TEST_CHECK(r2.maybe_error == nullptr);
  TEST_CHECK(r2.data == (seq_elem_t)&db);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_seq_empty()

void test_seq_empty ( )

static

Definition at line 45 of file seq_tests.h.

                             {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
  auto s = seq_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_seq_push_less_than_32()

void test_seq_push_less_than_32

(

)

Definition at line 59 of file seq_tests.h.

                                  {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  seq_dummy d = {.foo = 10, .bar = 20}; // NOLINT
  auto s      = seq_empty(ctx);
  auto s1     = seq_push(&s, (seq_elem_t)&d);
  TEST_CHECK(s.len == 0);
  TEST_CHECK(s.tail_len == 0);
  TEST_CHECK(s.root == nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  TEST_CHECK(s1.len == 1);
  TEST_CHECK(s1.tail_len == 1);
  TEST_CHECK(s1.root == nullptr);
  TEST_CHECK(s1.maybe_error == nullptr);
  seq_dummy *d1 = (seq_dummy *)s1.tail[0];
  TEST_CHECK(d1->foo == 10);
  TEST_CHECK(d1->bar == 20);
 
  RELEASE_CONTEXT(ctx);
  SHUTDOWN_ENGINE(mm, engine);
}

Here is the call graph for this function:

test_seq_push_more_than_32()

void test_seq_push_more_than_32

(

)

Definition at line 83 of file seq_tests.h.

                                  {
  MAKE_ENGINE(mm, engine);
  MAKE_CONTEXT(engine, ctx);
 
  seq_t s = seq_empty(ctx);
 
  for (int i = 0; i < 2000; i++) {
 
    seq_dummy *d = ALLOC(ctx, seq_dummy);
    d->foo       = i;
    d->bar       = 3000 - i;
    s            = seq_push(&s, (seq_elem_t)d);
  }
 
  TEST_CHECK(s.len == 2000);
  TEST_CHECK(s.tail_len == 16);
  TEST_CHECK(s.root != nullptr);
  TEST_CHECK(s.maybe_error == nullptr);
 
  seq_dummy *d1 = (seq_dummy *)s.tail[0];
 
  ASSERT_NOT_NULL(d1);
  TEST_CHECK(d1->foo == 1984);
  TEST_CHECK(d1->bar == 3000 - d1->foo);
 
  seq_dummy *d2 = (seq_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++) {
    seq_lookup_result_t res = seq_get(&s, (size_t)i);
    TEST_CHECK(res.maybe_error == nullptr);
    ASSERT_NOT_NULL(res.data);
    seq_dummy *d = (seq_dummy *)res.data;
 
    SEQ_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: