seq.c File Reference

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

Include dependency graph for seq.c:

Go to the source code of this file.

Macros
#define	SEQ_LOG(FMT, ...)

Functions
static uint16_t	seq_depth_index (const uint8_t depth, const uint64_t index)
	Find the array index of the given index, considering the given depth.
static seq_elem_t *	seq_create_page (const srn_context_t *ctx)
	Create a PAGE (just slots for the data).
static seq_node_t *	seq_new_node (const srn_context_t *ctx)
static seq_node_t *	seq_new_path (const srn_context_t *ctx, uint8_t depth, seq_node_t *leaf)
	Walk from the root to a possible leaf node and create all the inner and leaf nodes if necessary.
static seq_node_t *	seq_clone_node (const srn_context_t *ctx, const seq_node_t *n)
	Clone n into a fresh node with its own children page.
static seq_node_t *	seq_push_leaf (const srn_context_t *ctx, const seq_node_t *node, uint8_t depth, uint64_t index, seq_node_t *leaf)
	Insert leaf below node at the position of logical index index, cloning every node along the path.
seq_t	seq_empty (const srn_context_t *ctx)
	Create an empty seq pinned to ctx.
seq_t	seq_push (const seq_t *seq, seq_elem_t x)
seq_lookup_result_t	seq_get (const seq_t *seq, size_t n)
	Negative index is not supported.

Macro Definition Documentation

SEQ_LOG

#define SEQ_LOG	(		FMT,
			... )

Definition at line 30 of file seq.c.

Function Documentation

seq_clone_node()

seq_node_t * seq_clone_node ( const srn_context_t * ctx, const seq_node_t * n )

static

Clone n into a fresh node with its own children page.

Slots are copied by reference, so one slot of the clone can change without touching the original.

Definition at line 71 of file seq.c.

                                                                                 {
  seq_node_t *c = seq_new_node(ctx);
  for (size_t i = 0; i < SEQ_BR; i++) {
    c->children[i] = n->children[i];
  }
  return c;
}

Here is the call graph for this function:

Here is the caller graph for this function:

seq_create_page()

seq_elem_t * seq_create_page ( const srn_context_t * ctx )

inlinestatic

Create a PAGE (just slots for the data).

Definition at line 40 of file seq.c.

                                                                    {
  seq_elem_t *p = ALLOCN(ctx, seq_elem_t, SEQ_BR);
  PANIC_IF_NULL((void *)p);
  for (size_t i = 0; i < SEQ_BR; i++) {
    p[i] = nullptr;
  }
  return p;
}

Here is the caller graph for this function:

seq_depth_index()

uint16_t seq_depth_index ( const uint8_t depth, const uint64_t index )

inlinestatic

Find the array index of the given index, considering the given depth.

depth can be thought of, as which 5 bits of the index are we looking at. (SEQ_SHIFT is 5).

Definition at line 35 of file seq.c.

                                                                                  {
  return (uint16_t)((index >> (uint8_t)(depth * SEQ_SHIFT)) & SEQ_MASK);
}

Here is the caller graph for this function:

seq_empty()

seq_t seq_empty ( const srn_context_t * ctx )

nodiscard

Create an empty seq pinned to ctx.

The pinned context owns every allocation the seq (and all of its future versions) retains, so pick a context that lives at least as long as the seq.

Definition at line 100 of file seq.c.

                                          {
  PANIC_IF_NULL(ctx);
  seq_t seq;
  seq.len         = 0;
  seq.tail_len    = 0;
  seq.tail        = seq_create_page(ctx);
  seq.maybe_error = nullptr;
  seq.root        = nullptr;
  seq.depth       = 0;
  seq.seq_ctx     = ctx;
  return seq;
}

Here is the call graph for this function:

Here is the caller graph for this function:

seq_get()

seq_lookup_result_t seq_get ( const seq_t * seq, size_t n )

nodiscard

Negative index is not supported.

Definition at line 205 of file seq.c.

                                                        {
  const srn_context_t *ctx = seq->seq_ctx;
  PANIC_IF_NULL(ctx);
  seq_lookup_result_t result = {.data = nullptr, .maybe_error = nullptr};
 
  if (n >= seq->len) {
    // Size the message by asking snprintf first; a fixed buffer sized from
    // sizeof(size_t) counts bytes, not digits, and overflows on large
    // indices.
    int msg_len = snprintf(nullptr, 0, "%zu", n);
    PANIC_IF(msg_len < 0, "index formatting failed");
    char *err_msg = srn_allocate(ctx, (size_t)msg_len + 1, alignof(char));
    (void)snprintf(err_msg, (size_t)msg_len + 1, "%zu", n);
 
    result.maybe_error = ERR(ctx, INDEX_OUT_OF_BOUND, err_msg);
    result.data        = nullptr;
    return result;
  }
 
  size_t tail_start = seq->len - (size_t)seq->tail_len;
  if (n >= tail_start) {
    // Tail lookup
    size_t off  = n - tail_start; // 0 .. tail_len-1
    result.data = seq->tail[off];
    return result;
  }
 
  SEQ_LOG("Looking up in trie: TL: %d, L: %zu N: %zu", seq->tail_len, seq->len, n);
  seq_node_t *node = seq->root;
  for (int16_t d = seq->depth; d >= 0; d--) {
    uint16_t index = seq_depth_index(d, n);
    SEQ_LOG("Looking up in trie: D: %d, I: %hu", d, index);
 
    if (d == 0) {
      SEQ_LOG("We're at depth zero");
      result.data = node->children[index];
      return result;
    }
 
    // A read must not create nodes. Every index below the tail has a full
    // path, so a missing child is corruption, not laziness.
    node = (seq_node_t *)node->children[index];
    if (!node) {
      result.maybe_error = ERR(ctx, CORRUPTED_SEQ, "missing child");
      result.data        = nullptr;
      return result;
    }
  }
 
  PANIC("It should never happen");
  // just a dummy return
  result.data        = nullptr;
  result.maybe_error = ERR(ctx, ABSURD, "");
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

seq_new_node()

seq_node_t * seq_new_node ( const srn_context_t * ctx )

inlinestatic

Definition at line 49 of file seq.c.

                                                                 {
  seq_node_t *n = ALLOC(ctx, seq_node_t);
  PANIC_IF_NULL(n);
  n->children = seq_create_page(ctx);
  return n;
}

Here is the call graph for this function:

Here is the caller graph for this function:

seq_new_path()

seq_node_t * seq_new_path ( const srn_context_t * ctx, uint8_t depth, seq_node_t * leaf )

static

Walk from the root to a possible leaf node and create all the inner and leaf nodes if necessary.

We use this only when we insert new data

Definition at line 58 of file seq.c.

                                                                                           {
  if (depth == 0) {
    return leaf;
  }
 
  seq_node_t *n  = seq_new_node(ctx);
  n->children[0] = seq_new_path(ctx, depth - 1, leaf);
  return n;
}

Here is the call graph for this function:

Here is the caller graph for this function:

seq_push()

seq_t seq_push ( const seq_t * seq, seq_elem_t x )

nodiscard

Definition at line 113 of file seq.c.

                                               {
  const srn_context_t *ctx = seq->seq_ctx;
  PANIC_IF_NULL(ctx);
 
  if (seq->len >= SIZE_MAX) {
    seq_t failed_seq;
    failed_seq.maybe_error =
      ERR(ctx, SEQ_LIMIT_REACHED, "Can't fit more elements in this sequence");
    failed_seq.len      = 0;
    failed_seq.tail_len = 0;
    failed_seq.depth    = 0;
    failed_seq.root     = nullptr;
    failed_seq.tail     = nullptr;
    failed_seq.seq_ctx  = seq->seq_ctx;
    return failed_seq;
  }
 
  if (seq->tail_len < SEQ_BR) {
    // The tail buffer is shared with every older version of this seq, so
    // the new version appends into its own copy.
    seq_t new_seq       = *seq;
    new_seq.maybe_error = nullptr;
    new_seq.tail        = seq_create_page(ctx);
 
    for (uint16_t i = 0; i < seq->tail_len; i++) {
      new_seq.tail[i] = seq->tail[i];
    }
 
    new_seq.tail[new_seq.tail_len++] = x;
    new_seq.len++;
    SEQ_LOG("Tail has space, TL: %d, L: %zu, D: %d", new_seq.tail_len, new_seq.len, new_seq.depth);
    return new_seq;
  }
 
  // elements already in the tree (multiple of SEQ_BR)
  size_t sz_without_tail = seq->len - (size_t)seq->tail_len;
  // Build a leaf around the current tail buffer. Sharing the buffer is safe;
  // it is full, and a push onto any version holding it promotes instead of
  // writing into it.
  seq_node_t *leaf = ALLOC(ctx, seq_node_t);
  leaf->children   = seq->tail;
 
  // Tail buffer is full and we need to to move it (no copy) inside the trie
  // and allocate a new tail
  if (seq->root == nullptr) {
    // This happens only once, at index
    // (SEQ_BR + 1) and technically we can just
    seq_t new_seq       = *seq;
    new_seq.maybe_error = nullptr;
    new_seq.tail_len    = 1;
    new_seq.len++;
    new_seq.tail                       = seq_create_page(ctx);
    new_seq.tail[new_seq.tail_len - 1] = x;
    new_seq.root                       = leaf;
    new_seq.depth                      = 0;
    SEQ_LOG("Root is null, TL: %d, L: %zu, D: %d", new_seq.tail_len, new_seq.len, new_seq.depth);
 
    return new_seq;
  }
  // Root is not Null, so we have inner children and we need to find the slot
  // which we need to move the tail into
 
  // If the tree is full at current depth, grow a new root
  if (sz_without_tail >> ((seq->depth + 1) * SEQ_SHIFT)) {
    // ^^ == floor(sz_without_tail / 2^(5*(d+1)))
 
    seq_node_t *new_root  = seq_new_node(ctx); // internal node
    new_root->children[0] = seq->root;
    new_root->children[1] = seq_new_path(ctx, seq->depth, leaf);
    seq_t new_seq         = *seq;
    new_seq.maybe_error   = nullptr;
    new_seq.root          = new_root;
    new_seq.depth         = seq->depth + 1;
    new_seq.tail          = seq_create_page(ctx);
    new_seq.tail_len      = 1;
    new_seq.len           = seq->len + 1;
    new_seq.tail[0]       = x;
    return new_seq;
  }
  // Insert the leaf at the right fringe, cloning the path from the root so
  // no node shared with older versions is written.
  seq_t new_seq       = *seq;
  new_seq.maybe_error = nullptr;
  new_seq.root        = seq_push_leaf(ctx, seq->root, seq->depth, (uint64_t)sz_without_tail, leaf);
  new_seq.tail        = seq_create_page(ctx);
  new_seq.tail_len    = 1;
  new_seq.len         = seq->len + 1;
  new_seq.tail[0]     = x;
  return new_seq;
}

Here is the call graph for this function:

Here is the caller graph for this function:

seq_push_leaf()

seq_node_t * seq_push_leaf ( const srn_context_t * ctx, const seq_node_t * node, uint8_t depth, uint64_t index, seq_node_t * leaf )

static

Insert leaf below node at the position of logical index index, cloning every node along the path.

Nothing reachable from node is written, so older versions sharing this subtree stay intact.

Definition at line 82 of file seq.c.

  {
  seq_node_t *copy = seq_clone_node(ctx, node);
  uint16_t idx     = seq_depth_index(depth, index);
 
  if (depth == 1) {
    copy->children[idx] = (seq_elem_t)leaf;
    return copy;
  }
 
  seq_node_t *child   = (seq_node_t *)node->children[idx];
  copy->children[idx] = (child == nullptr)
                          ? (seq_elem_t)seq_new_path(ctx, depth - 1, leaf)
                          : (seq_elem_t)seq_push_leaf(ctx, child, depth - 1, index, leaf);
  return copy;
}

Here is the call graph for this function:

Here is the caller graph for this function: