array_list.h

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/>.
 */
 
#pragma once
 
/** @file
 * 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.
 *
 */
 
// clang-format off
/* AI Generated (🤦)
 ------------------------------------------------------------------------------
 Example at a readable scale, with AL_BR = 4 and AL_SHIFT = 2
 ------------------------------------------------------------------------------
 array_list state:
   len      = 11
   tail_len = 3                     // last 3 elements live in the tail
   depth    = 1                     // one inner level above the leaves
   trie     = elements [0..7]       // first 8 elements live in the trie
   tail     = elements [8, 9, 10]
 
 High-level view
 ┌──────────────┐        ┌───────────── Trie (elements 0..7) ─────────────┐
 │ array_list_t │        │          (depth = 1, AL_BR = 4, AL_SHIFT = 2)   │
 │ len = 11     │        │                                                 │
 │ tail_len = 3 │        │   Root (inner node, level 1)                    │
 │ depth = 1    │        │   ┌───────────────────────────────┐            │
 │ root ────────┼───────►│   │ c[0]   c[1]   c[2]     c[3]    │            │
 │ tail ──┐     │        │   └──┬──────┬───── (NULL)  (NULL)──┘            │
 └────────┴─────┘        │      ▼      ▼                                   │
          │              │  Leaf(0..3) Leaf(4..7)                          │
          ▼              │  [0 1 2 3]  [4 5 6 7]                           │
   Tail (8..10)          └─────────────────────────────────────────────────┘
   [ 8 | 9 | 10 ]                  Leaves hold up to AL_BR elements
 
 Bit-partitioned indexing of the trie
   For an index n in [0..7], with AL_SHIFT = 2:
     hi = (n >> 2) & 0b11    // selects Root.c[hi]
     lo =  n       & 0b11    // selects the leaf slot within that child
 
   Example, n = 6 (binary 0b0110)
     hi = 0b01 = 1           -> Root.c[1] -> Leaf(4..7)
     lo = 0b10 = 2           -> Leaf(4..7)[2] = 6
 
 Tail indexing
   For n in [8..10], use tail[n - (len - tail_len)]
     n = 9 -> tail[9 - (11 - 3)] = tail[1] = 9
 
 Notes
   * Only the right fringe and the tail change on a push.
   * When tail_len reaches AL_BR the tail is promoted to a leaf and spliced
     into the trie, updating the nodes on that path in place.
 ------------------------------------------------------------------------------
*/
// clang-format on
 
#include "serene/rt/errors.h"
#include "serene/utils.h"
 
typedef struct srn_context_t srn_context_t;
typedef size_t array_list_index_t;
 
// -----------------------------------------------------------------------------
// Tunables
// -----------------------------------------------------------------------------
 
/// branching factor (power of two)
#define AL_BR 32U
 
/// log2(AL_BR)
#define AL_SHIFT 5U
#define AL_MASK  (AL_BR - 1u)
 
/**
 * 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.
 */
#define AL_MAX_DEPTH 11
 
/**
 * Maximum number of elements an array list can hold: a full trie at AL_MAX_DEPTH plus a full tail.
 */
#define AL_MAX_ELEMENTS (((size_t)1 << (AL_SHIFT * (AL_MAX_DEPTH + 1))) + AL_BR)
 
// TODO(lxsameer): The current values of tunables are tuned for a 64bit systems. Since size_t is
// smaller in a 32bit or 16bit systme, we need to retune them based on the platfrom. We are not
// there but we have to eventually do it
static_assert(
  (size_t)AL_SHIFT * (AL_MAX_DEPTH + 1) < sizeof(size_t) * CHAR_BIT,
  "AL_MAX_DEPTH exceeds what size_t can address on this platform"
);
 
/**
 * 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).
 */
typedef void *array_list_elem_t;
 
typedef struct array_list_maybe_element_t {
  ERROR_HEADER;
  array_list_elem_t data;
} array_list_maybe_element_t;
 
// -----------------------------------------------------------------------------
// Node
// -----------------------------------------------------------------------------
 
/**
 * 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.
 */
typedef struct array_list_node_t {
  /// We allocate `children` to be a buffer of AL_BR number of pointers
  array_list_elem_t *children;
} array_list_node_t;
 
typedef struct array_list_t {
  ERROR_HEADER;
  /// logical length. While techically this implementation will support up to
  /// 2^85 elements in each array_list, but we will limit it down to
  /// (2^64-1)(UINT64_MAX)(on 64bit machines) in order to keep the `array_list_t` as
  /// small as possible
  size_t len;
  /// 0..AL_BR
  uint16_t tail_len;
  /// tree depth in levels (0 == leaf level)
  uint8_t depth;
  /// NULL means “all data is in tail”
  array_list_node_t *root;
  /// small tail array for fast push/pop. We allocate this in heap with SEQ_BR
  /// size and move it later to the inner Nodes.
  array_list_elem_t *tail;
 
  /// The context that owns every allocation the array list retains. `array_list_empty`
  /// sets it. Pushes allocate new tail pages, leaves, and inner nodes in this
  /// context's block chain. Elements are stored as is; the caller must
  /// allocate them with a lifetime at least as long as this context.
  const srn_context_t *ctx;
} array_list_t;
 
// -----------------------------------------------------------------------------
// Public API
// -----------------------------------------------------------------------------
 
/**
 * Create an empty array list in the given context `ctx`.
 */
[[nodiscard]] [[gnu::nonnull(1)]]
array_list_t array_list_empty(const srn_context_t *ctx);
 
/**
 * Push the given element `x` to the end of array_list `al`.
 */
[[nodiscard]] [[gnu::nonnull(1)]]
srn_error_t *array_list_push(array_list_t *al, array_list_elem_t x);
 
/**
 * 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.
 */
[[nodiscard]] [[gnu::nonnull(1)]]
srn_error_t *array_list_update(array_list_t *al, array_list_index_t n, array_list_elem_t x);
 
/**
 * Look up the element at the given index `n` in the given array list `al`.
 */
[[nodiscard]] [[gnu::nonnull(1)]]
array_list_maybe_element_t array_list_get(const 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. Returns null on success, or an error when `n` is out of
 * bounds.
 */
[[nodiscard]] [[gnu::nonnull(1)]]
srn_error_t *array_list_remove(array_list_t *al, array_list_index_t n);