array_list.h File Reference

A bit-partitioned trie with a tail buffer, used as a growable indexed sequence in the runtime. More...

#include "serene/rt/errors.h"
#include "serene/utils.h"

Include dependency graph for array_list.h:

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

Go to the source code of this file.

Data Structures
struct	array_list_maybe_element_t
struct	array_list_node_t
	We have two type of node that both are implemented using the same data structure. More...
struct	array_list_t

Macros
#define	AL_BR   32U
	branching factor (power of two)
#define	AL_SHIFT   5U
	log2(AL_BR)
#define	AL_MASK   (AL_BR - 1u)
#define	AL_MAX_DEPTH   11
	Maximum trie depth, meaning the level of the root.
#define	AL_MAX_ELEMENTS   (((size_t)1 << (AL_SHIFT * (AL_MAX_DEPTH + 1))) + AL_BR)
	Maximum number of elements an array list can hold: a full trie at AL_MAX_DEPTH plus a full tail.

Typedefs
typedef size_t	array_list_index_t
typedef void *	array_list_elem_t
	We use generic pointers to refer to internal nodes, leaf nodes and even elements.
typedef struct array_list_maybe_element_t	array_list_maybe_element_t
typedef struct array_list_node_t	array_list_node_t
	We have two type of node that both are implemented using the same data structure.
typedef struct array_list_t	array_list_t

Functions
array_list_t	array_list_empty (const srn_context_t *ctx)
	Create an empty array list in the given context ctx.
srn_error_t *	array_list_push (array_list_t *al, array_list_elem_t x)
	Push the given element x to the end of array_list al.
srn_error_t *	array_list_update (array_list_t *al, array_list_index_t n, array_list_elem_t x)
	Update the given index n of the array list al with the new element x.
array_list_maybe_element_t	array_list_get (const array_list_t *al, array_list_index_t n)
	Look up the element at the given index n in the given array list al.
srn_error_t *	array_list_remove (array_list_t *al, array_list_index_t n)
	Remove the element at the given index n from the array list al, shifting every later element down one to keep the sequence contiguous.

Detailed Description

A bit-partitioned trie with a tail buffer, used as a growable indexed sequence in the runtime.

It has the same shape as the persistent seq (see seq.h and the Ideal hash trees paper), but this one is mutable.

TL;DR

• A wide trie (branching factor AL_BR) holds the bulk of the elements, and a small tail buffer holds the most recently pushed ones.
• Elements are stored by reference as opaque void *. The caller owns their lifetime.
• Every node lives in the owning context's memory, so nothing is freed until that context is released.
• It is mutable in place. array_list_push updates the struct and the trie nodes directly. Copying the struct yields an alias that shares storage, not an independent snapshot.
• Appends are fast. The tail absorbs pushes until it fills, then it becomes a leaf in the trie and a fresh tail starts.
• Random access is shallow, at most AL_MAX_DEPTH + 1 pointer hops.
• The maximum number of elements is AL_MAX_ELEMENTS.
• THIS IS NOT THREAD SAFE. Operating on the array or the values has to be synchronized with a lock or something.

Definition in file array_list.h.

Macro Definition Documentation

AL_BR

#define AL_BR   32U

branching factor (power of two)

Definition at line 103 of file array_list.h.

AL_MASK

#define AL_MASK   (AL_BR - 1u)

Definition at line 107 of file array_list.h.

AL_MAX_DEPTH

#define AL_MAX_DEPTH   11

Maximum trie depth, meaning the level of the root.

At this depth the trie holds AL_BR^(AL_MAX_DEPTH + 1) = 32^12 = 1,152,921,504,606,846,976 elements, which is the hard capacity ceiling of an array list. The bound also keeps the level shift (depth + 1) * AL_SHIFT below the width of size_t, so the index math never shifts by 64 or more.

Definition at line 116 of file array_list.h.

AL_MAX_ELEMENTS

#define AL_MAX_ELEMENTS   (((size_t)1 << (AL_SHIFT * (AL_MAX_DEPTH + 1))) + AL_BR)

Maximum number of elements an array list can hold: a full trie at AL_MAX_DEPTH plus a full tail.

Definition at line 121 of file array_list.h.

AL_SHIFT

#define AL_SHIFT   5U

log2(AL_BR)

Definition at line 106 of file array_list.h.

Typedef Documentation

array_list_elem_t

typedef void* array_list_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. array_list_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 138 of file array_list.h.

array_list_index_t

typedef size_t array_list_index_t

Definition at line 96 of file array_list.h.

array_list_maybe_element_t

typedef struct array_list_maybe_element_t array_list_maybe_element_t

array_list_node_t

typedef struct array_list_node_t array_list_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.

array_list_t

typedef struct array_list_t array_list_t

Function Documentation

array_list_empty()

array_list_t array_list_empty ( const srn_context_t * ctx )

nodiscard

Create an empty array list in the given context ctx.

Definition at line 101 of file array_list.c.

                                                        {
  PANIC_IF_NULL(ctx);
  array_list_t al;
  al.len         = 0;
  al.tail_len    = 0;
  al.tail        = array_list_create_page(ctx);
  al.maybe_error = nullptr;
  al.root        = nullptr;
  al.depth       = 0;
  al.ctx         = ctx;
  return al;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_list_get()

array_list_maybe_element_t array_list_get ( const array_list_t * al, array_list_index_t n )

nodiscard

Look up the element at the given index n in the given array list al.

Look up the element at the given index n in the given array list al.

Definition at line 235 of file array_list.c.

                                                                                        {
  array_list_maybe_element_t result = {.data = nullptr, .maybe_error = nullptr};
 
  array_list_elem_t *slot = nullptr;
  result.maybe_error      = array_list_slot(al, n, &slot);
  if (slot) {
    result.data = *slot;
  }
  return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_list_push()

srn_error_t * array_list_push ( array_list_t * al, array_list_elem_t x )

nodiscard

Push the given element x to the end of array_list al.

Definition at line 114 of file array_list.c.

                                                                    {
  const srn_context_t *ctx = al->ctx;
  PANIC_IF_NULL(ctx);
 
  if (al->len >= AL_MAX_ELEMENTS) {
    return ERR(ctx, AL_LIMIT_REACHED, "Can't fit more elements in this sequence");
  }
 
  if (al->tail_len < AL_BR) {
    // There is room in the tail. Insert the element and we're done.
    al->tail[al->tail_len++] = x;
    al->len++;
    AL_LOG("Tail has space, TL: %d, L: %zu, D: %d", al->tail_len, al->len, al->depth);
    return nullptr;
  }
 
  // We need a new tail node. Move the current tail to an inner node, and create a new one.
 
  size_t sz_without_tail = al->len - (size_t)al->tail_len;
 
  // Build a leaf around the current tail buffer. Sharing the buffer is safe.
  array_list_node_t *leaf = ALLOC(ctx, array_list_node_t);
  PANIC_IF_NULL(leaf);
 
  leaf->children = al->tail;
 
  // Tail buffer is full and we need to to move it (no copy) inside the trie
  // and allocate a new tail
  if (al->root == nullptr) {
    // This happens only once, at index (AL_BR + 1) and technically we can just
    al->maybe_error = nullptr;
    al->tail_len    = 1;
    al->len++;
    al->tail                   = array_list_create_page(ctx);
    al->tail[al->tail_len - 1] = x;
    al->root                   = leaf;
    al->depth                  = 0;
    AL_LOG("Root is null, TL: %d, L: %zu, D: %d", al->tail_len, al->len, al->depth);
 
    return nullptr;
  }
 
  // 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 >> ((al->depth + 1) * AL_SHIFT)) {
    // ^^ == floor(sz_without_tail / 2^(5*(d+1)))
 
    // A deeper root would push the level shift (depth+1)*AL_SHIFT up to the
    // width of size_t, so AL_MAX_DEPTH is the hard capacity ceiling.
    if (al->depth >= AL_MAX_DEPTH) {
      return ERR(ctx, AL_LIMIT_REACHED, "Can't fit more elements in this sequence");
    }
 
    array_list_node_t *new_root = array_list_new_node(ctx); // internal node
    new_root->children[0]       = al->root;
    new_root->children[1]       = array_list_new_path(ctx, al->depth, leaf);
    al->root                    = new_root;
    al->tail                    = array_list_create_page(ctx);
    al->tail_len                = 1;
    al->tail[0]                 = x;
    al->len++;
    al->depth++;
 
    return nullptr;
  }
 
  // Insert the leaf at the right fringe of the trie, mutating it in place.
  array_list_push_leaf(ctx, al->root, al->depth, (uint64_t)sz_without_tail, leaf);
 
  al->tail     = array_list_create_page(ctx);
  al->tail_len = 1;
  al->tail[0]  = x;
  al->len++;
  return nullptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_list_remove()

srn_error_t * array_list_remove ( array_list_t * al, array_list_index_t n )

nodiscard

Remove the element at the given index n from the array list al, shifting every later element down one to keep the sequence contiguous.

Returns null on success, or an error when n is out of bounds.

Definition at line 301 of file array_list.c.

                                                                       {
  PANIC_IF_NULL(al);
 
  array_list_elem_t *dst = nullptr;
  srn_error_t *err       = array_list_slot(al, n, &dst);
  if (err != nullptr) {
    return err;
  }
 
  // Slide every later element down one slot, overwriting `n`. The slot just read
  // becomes the next write target, so each step costs a single lookup. Indices
  // stay in [0, len), so none of these lookups can fail.
  for (array_list_index_t i = n; i + 1 < al->len; i++) {
    array_list_elem_t *src = nullptr;
    auto err               = array_list_slot(al, i + 1, &src);
    // At this point an error screws the entire array list, it's better to PANIC
    PANIC_IF(err != nullptr, "array_list_remove failed. This should not happen");
    *dst = *src;
    dst  = src;
  }
 
  // The last physical element is now a duplicate of the previous one.
  array_list_drop_last(al);
  return nullptr;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_list_update()

srn_error_t * array_list_update ( array_list_t * al, array_list_index_t n, array_list_elem_t x )

nodiscard

Update the given index n of the array list al with the new element x.

Returns null on success, or an error when n is out of bounds.

Definition at line 246 of file array_list.c.

                                                                                            {
  PANIC_IF_NULL(al);
 
  array_list_elem_t *slot = nullptr;
  srn_error_t *err        = array_list_slot(al, n, &slot);
  if (slot) {
    *slot = x;
  }
  return err;
}

Here is the call graph for this function:

Here is the caller graph for this function: