seq.h File Reference

This is an implementation of bit - partitioned, persistent, immutable sequence For more information, have a look at Ideal hash trees paper. More...

#include <stddef.h>
#include <stdint.h>
#include "serene/rt/errors.h"

Include dependency graph for seq.h:

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

Go to the source code of this file.

Data Structures
struct	seq_lookup_result_t
struct	seq_node_t
	We have two type of node that both are implemented using the same data structure. More...
struct	seq_t

Macros
#define	SEQ_BR   32u
	branching factor (power of two)
#define	SEQ_SHIFT   5u
	log2(SEQ_BR)
#define	SEQ_MASK   (SEQ_BR - 1u)
#define	SEQ_MAX_DEPTH   11
	logical length.

Typedefs
typedef void *	seq_elem_t
	We use generic pointers to refer to internal nodes, leaf nodes and even elements.
typedef struct seq_lookup_result_t	seq_lookup_result_t
typedef struct seq_node_t	seq_node_t
	We have two type of node that both are implemented using the same data structure.
typedef struct seq_t	seq_t

Functions
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.

Detailed Description

This is an implementation of bit - partitioned, persistent, immutable sequence For more information, have a look at Ideal hash trees paper.

TL;DR:

• Every struct is immutable (from user perspective).
• Nodes are persistent and immutable.
• Nodes are heap allocated
• Heads can be stack allocated
• We create a new head for any change
• Heads contain a tail buffer that will be converted to a leaf node when they are full
• This data structure is NOT effecient for extracting sub sequences
• This data structure is effecient for tail operations,
• If you need a subset of the elments in the sequence, create a list view out of them instead of extracting them as a new seq.
• Deleting operation is O(N)

TODO:

• Create map and filter function or a generic fold
• Create a helper function to help creating list view from the seq

Definition in file seq.h.

Macro Definition Documentation

SEQ_BR

#define SEQ_BR   32u

branching factor (power of two)

Definition at line 112 of file seq.h.

SEQ_MASK

#define SEQ_MASK   (SEQ_BR - 1u)

Definition at line 116 of file seq.h.

SEQ_MAX_DEPTH

#define SEQ_MAX_DEPTH   11

logical length.

While techically this implementation will support up to 2^85 elements in each seq, but we will limit it down to (2^64-1)(UINT64_MAX)(on 64bit machines) in order to keep the seq_t as small as possible. 12 is the magic number that we use to limit the depth to. 32^11 = 1,152,921,504,606,846,976 elements

Definition at line 123 of file seq.h.

SEQ_SHIFT

#define SEQ_SHIFT   5u

log2(SEQ_BR)

Definition at line 115 of file seq.h.

Typedef Documentation

seq_elem_t

typedef void* seq_elem_t

We use generic pointers to refer to internal nodes, leaf nodes and even elements.

It makes the calculation cruical to determining what type of data we are looking at, in each node. seq_elem_t will be pointing to actual user data when the node is a leaf node (depth == 0) and it will be pointing to the next node in the trie if the node is an inner node (depth != 0).

Definition at line 131 of file seq.h.

seq_lookup_result_t

typedef struct seq_lookup_result_t seq_lookup_result_t

seq_node_t

typedef struct seq_node_t seq_node_t

We have two type of node that both are implemented using the same data structure.

Inner nodes that point to other inner nodes or leaf nodes, and leaf nodes which points to actual elements of the sequence.

The main factor in determining the nature of the node is the depth of the trie. Depth zero, means a leaf node and an inner node otherwise.

seq_t

typedef struct seq_t seq_t

Function Documentation

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_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: