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_next_child (const srn_context_t *ctx, seq_node_t *n, uint16_t index)
	Get or create the next node of the tree.
seq_t	seq_empty (const srn_context_t *ctx)
seq_t	seq_push (const srn_context_t *ctx, const seq_t *seq, seq_elem_t x)
seq_lookup_result_t	seq_get (const srn_context_t *ctx, 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_create_page()

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

static 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

Definition at line 76 of file seq.c.

                                          {
  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;
  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 srn_context_t * ctx, const seq_t * seq, size_t n )

nodiscard

Negative index is not supported.

Definition at line 173 of file seq.c.

                                                                                  {
  seq_lookup_result_t result = {.data = nullptr, .maybe_error = nullptr};
 
  if (n >= seq->len) {
    char *err_msg = (char *)ALLOC(ctx, size_t);
    // +1 is due to null terminated strings
    SNPRINTF(err_msg, sizeof(size_t) + 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;
    }
 
    node = seq_next_child(ctx, node, 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()

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

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

static seq_node_t * seq_next_child ( const srn_context_t * ctx, seq_node_t * n, uint16_t index )

inlinestatic

Get or create the next node of the tree.

Definition at line 69 of file seq.c.

                                                                                                  {
  if (n->children[index] == nullptr) {
    n->children[index] = seq_new_node(ctx);
  }
  return n->children[index];
}

Here is the call graph for this function:

Here is the caller graph for this function:

seq_push()

seq_t seq_push ( const srn_context_t * ctx, const seq_t * seq, seq_elem_t x )

nodiscard

Definition at line 87 of file seq.c.

                                                                         {
  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.tail_len = 0;
    failed_seq.len = 0;
    return failed_seq;
  }
 
  if (seq->tail_len < SEQ_BR) {
    // Tail buffer has enough space
    seq_t new_seq = *seq;
    new_seq.maybe_error = nullptr;
    // new_seq.tail_len++;
    new_seq.len++;
    new_seq.tail[new_seq.tail_len++] = x;
    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 will own the current tail buffer.
  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.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;
  }
  // Otherwise insert the leaf at the right fringe under the parent (d==1)
  seq_node_t *parent = seq->root;
 
  for (uint8_t d = seq->depth; d > 1; --d) {
    uint16_t idx = seq_depth_index(d, (uint64_t)sz_without_tail);
    // ensures internal nodes exist
    parent = seq_next_child(ctx, parent, idx);
  }
 
  // Now at d == 1: use the correct child slot to insert the leaf
  uint16_t leaf_parent_idx = seq_depth_index(1, (uint64_t)sz_without_tail);
  parent->children[leaf_parent_idx] = (seq_elem_t)leaf;
 
  // Start a fresh tail with the pushed element
  seq_t new_seq = *seq;
  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: