array_list.c

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <lxsameer@lxsameer.com>
 *
 * This library is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#include "serene/rt/impl/array_list.h"
 
#include <stdint.h>
#include <stdio.h>
 
#include "serene/rt/context.h"
#include "serene/utils.h"
 
#if defined(AL_DEBUG)
#  define AL_LOG(FMT, ...) DBG("ARRAY_LIST", FMT __VA_OPT__(, ) __VA_ARGS__)
#else
#  define AL_LOG(FMT, ...)
#endif
 
/**
 * 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).
 */
static inline uint16_t array_list_depth_index(const uint8_t depth, const uint64_t index) {
  return (uint16_t)((index >> (uint8_t)(depth * AL_SHIFT)) & AL_MASK);
}
 
/// Create a PAGE (just slots for the data)
static inline array_list_elem_t *array_list_create_page(const srn_context_t *ctx) {
  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;
}
 
static inline array_list_node_t *array_list_new_node(const srn_context_t *ctx) {
  array_list_node_t *n = ALLOC(ctx, array_list_node_t);
  PANIC_IF_NULL(n);
  n->children = array_list_create_page(ctx);
  return n;
}
 
/**
 * 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
 */
static array_list_node_t *
array_list_new_path(const srn_context_t *ctx, uint8_t depth, array_list_node_t *leaf) {
  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;
}
 
/**
 * 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.
 */
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
) {
  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);
  }
}
 
// -----------------------------------------------------------------------------
// Public API
// -----------------------------------------------------------------------------
 
array_list_t array_list_empty(const srn_context_t *ctx) {
  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;
}
 
srn_error_t *array_list_push(array_list_t *al, array_list_elem_t x) {
  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;
}
 
/**
 * 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.
 */
static srn_error_t *
array_list_slot(const array_list_t *al, array_list_index_t n, array_list_elem_t **out_slot) {
  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, "");
}
 
/// Negative index is not supported
array_list_maybe_element_t array_list_get(const array_list_t *al, array_list_index_t n) {
  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;
}
 
srn_error_t *array_list_update(array_list_t *al, array_list_index_t n, array_list_elem_t x) {
  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;
}
 
/**
 * 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.
 */
static void array_list_pull_last_leaf(array_list_t *al) {
  // 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;
}
 
/// Drop the final element, keeping the tail as the physical end of the sequence.
static void array_list_drop_last(array_list_t *al) {
  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--;
}
 
srn_error_t *array_list_remove(array_list_t *al, array_list_index_t n) {
  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;
}