array_list.c File Reference

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

Include dependency graph for array_list.c:

Go to the source code of this file.

Macros
#define	AL_LOG(FMT, ...)

Functions
static uint16_t	array_list_depth_index (const uint8_t depth, const uint64_t index)
	Find the array index of the given index, considering the given depth.
static array_list_elem_t *	array_list_create_page (const srn_context_t *ctx)
	Create a PAGE (just slots for the data).
static array_list_node_t *	array_list_new_node (const srn_context_t *ctx)
static array_list_node_t *	array_list_new_path (const srn_context_t *ctx, uint8_t depth, array_list_node_t *leaf)
	Walk from the root to a possible leaf node and create all the inner and leaf nodes if necessary.
static void	array_list_push_leaf (const srn_context_t *ctx, array_list_node_t *node, uint8_t depth, uint64_t index, array_list_node_t *leaf)
	Insert leaf below node at the position of logical index index, mutating node and its descendants in place.
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.
static srn_error_t *	array_list_slot (const array_list_t *al, array_list_index_t n, array_list_elem_t **out_slot)
	Resolve the address of the slot backing logical index n into *out_slot.
array_list_maybe_element_t	array_list_get (const array_list_t *al, array_list_index_t n)
	Negative index is not supported.
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.
static void	array_list_pull_last_leaf (array_list_t *al)
	Detach the rightmost leaf from the trie and hand its buffer back as the tail, the inverse of the promotion that array_list_push does.
static void	array_list_drop_last (array_list_t *al)
	Drop the final element, keeping the tail as the physical end of the sequence.
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.

Macro Definition Documentation

AL_LOG

#define AL_LOG	(		FMT,
			... )

Definition at line 30 of file array_list.c.

Function Documentation

array_list_create_page()

array_list_elem_t * array_list_create_page ( const srn_context_t * ctx )

inlinestatic

Create a PAGE (just slots for the data).

Definition at line 42 of file array_list.c.

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

Here is the caller graph for this function:

array_list_depth_index()

uint16_t array_list_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 (AL_SHIFT is 5).

Definition at line 37 of file array_list.c.

                                                                                         {
  return (uint16_t)((index >> (uint8_t)(depth * AL_SHIFT)) & AL_MASK);
}

Here is the caller graph for this function:

array_list_drop_last()

void array_list_drop_last ( array_list_t * al )

static

Drop the final element, keeping the tail as the physical end of the sequence.

Definition at line 288 of file array_list.c.

                                                   {
  if (al->tail_len == 0) {
    // Earlier removes drained the tail; refill it from the last trie leaf so
    // there is a physical slot to drop.
    array_list_pull_last_leaf(al);
    al->tail_len = AL_BR;
  }
 
  al->tail_len--;
  al->tail[al->tail_len] = nullptr;
  al->len--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Negative index is not supported.

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

array_list_node_t * array_list_new_node ( const srn_context_t * ctx )

inlinestatic

Definition at line 52 of file array_list.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

array_list_new_path()

array_list_node_t * array_list_new_path ( const srn_context_t * ctx, uint8_t depth, array_list_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 64 of file array_list.c.

                                                                                      {
  if (depth == 0) {
    return leaf;
  }
 
  array_list_node_t *n = array_list_new_node(ctx);
  n->children[0]       = array_list_new_path(ctx, depth - 1, leaf);
  return n;
}

Here is the call graph for this function:

Here is the caller graph for this function:

array_list_pull_last_leaf()

void array_list_pull_last_leaf ( array_list_t * al )

static

Detach the rightmost leaf from the trie and hand its buffer back as the tail, the inverse of the promotion that array_list_push does.

Only called when the tail has drained to empty while the trie still holds elements, so the trie holds whole leaves only and len is a multiple of AL_BR. The trie depth is left as is, an over-tall trie stays correct for reads, updates, and pushes.

Definition at line 264 of file array_list.c.

                                                        {
  // REVIEW: don't rely on 64bit stuff instead of this, use a size_t or something
  uint64_t last = al->len - 1;
 
  if (al->depth == 0) {
    // The root is the only leaf. Reclaiming it empties the trie.
    al->tail = al->root->children;
    al->root = nullptr;
    return;
  }
 
  // Walk to the inner node just above the leaves along the rightmost path.
  array_list_node_t *node = al->root;
  for (uint8_t d = al->depth; d > 1; d--) {
    node = (array_list_node_t *)node->children[array_list_depth_index(d, last)];
  }
 
  uint16_t idx            = array_list_depth_index(1, last);
  array_list_node_t *leaf = (array_list_node_t *)node->children[idx];
  al->tail                = leaf->children;
  node->children[idx]     = nullptr;
}

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

void array_list_push_leaf ( const srn_context_t * ctx, array_list_node_t * node, uint8_t depth, uint64_t index, array_list_node_t * leaf )

static

Insert leaf below node at the position of logical index index, mutating node and its descendants in place.

Missing inner nodes along the path are created on the way down.

Definition at line 78 of file array_list.c.

  {
  uint16_t idx = array_list_depth_index(depth, index);
 
  if (depth == 1) {
    node->children[idx] = (array_list_elem_t)leaf;
    return;
  }
 
  array_list_node_t *child = (array_list_node_t *)node->children[idx];
  if (child == nullptr) {
    node->children[idx] = (array_list_elem_t)array_list_new_path(ctx, depth - 1, leaf);
  } else {
    array_list_push_leaf(ctx, child, depth - 1, index, leaf);
  }
}

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

srn_error_t * array_list_slot ( const array_list_t * al, array_list_index_t n, array_list_elem_t ** out_slot )

static

Resolve the address of the slot backing logical index n into *out_slot.

Returns null on success and an error otherwise, leaving *out_slot null when it fails.

Definition at line 198 of file array_list.c.

                                                                                            {
  const srn_context_t *ctx = al->ctx;
  PANIC_IF_NULL(ctx);
  *out_slot = nullptr;
 
  if (n >= al->len) {
    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);
    return ERR(ctx, INDEX_OUT_OF_BOUND, err_msg);
  }
 
  size_t tail_start = al->len - (size_t)al->tail_len;
  if (n >= tail_start) {
    *out_slot = &al->tail[n - tail_start];
    return nullptr;
  }
 
  array_list_node_t *node = al->root;
  for (int16_t d = al->depth; d >= 0; d--) {
    uint16_t index = array_list_depth_index(d, n);
    if (d == 0) {
      *out_slot = &node->children[index];
      return nullptr;
    }
    node = (array_list_node_t *)node->children[index];
    if (!node) {
      return ERR(ctx, CORRUPTED_ARRAY_LIST, "missing child");
    }
  }
 
  PANIC("It should never happen");
  return ERR(ctx, ABSURD, "");
}

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: