seq.c

Go to the documentation of this file.

/* -*- C -*-
 * Serene programming language
 * Copyright (C) 2019-2026 Sameer Rahmani <[email protected]>
 *
 * 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/seq.h"
 
#include <stdint.h>
#include <stdio.h>
 
#include "serene/rt/context.h"
#include "serene/utils.h"
 
#if defined(SEQ_DEBUG)
#  define SEQ_LOG(FMT, ...) DBG("SEQ", FMT __VA_OPT__(, ) __VA_ARGS__)
#else
#  define SEQ_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.
/// (SEQ_SHIFT is 5).
static inline uint16_t seq_depth_index(const uint8_t depth, const uint64_t index) {
  return (uint16_t)((index >> (uint8_t)(depth * SEQ_SHIFT)) & SEQ_MASK);
}
 
/// Create a PAGE (just slots for the data)
static inline seq_elem_t *seq_create_page(const srn_context_t *ctx) {
  seq_elem_t *p = ALLOCN(ctx, seq_elem_t, SEQ_BR);
  PANIC_IF_NULL((void *)p);
  for (size_t i = 0; i < SEQ_BR; i++) {
    p[i] = nullptr;
  }
  return p;
}
 
static inline seq_node_t *seq_new_node(const srn_context_t *ctx) {
  seq_node_t *n = ALLOC(ctx, seq_node_t);
  PANIC_IF_NULL(n);
  n->children = seq_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 seq_node_t *seq_new_path(const srn_context_t *ctx, uint8_t depth, seq_node_t *leaf) {
  if (depth == 0) {
    return leaf;
  }
 
  seq_node_t *n  = seq_new_node(ctx);
  n->children[0] = seq_new_path(ctx, depth - 1, leaf);
  return n;
}
 
/// Clone `n` into a fresh node with its own children page. Slots are copied
/// by reference, so one slot of the clone can change without touching the
/// original.
static seq_node_t *seq_clone_node(const srn_context_t *ctx, const seq_node_t *n) {
  seq_node_t *c = seq_new_node(ctx);
  for (size_t i = 0; i < SEQ_BR; i++) {
    c->children[i] = n->children[i];
  }
  return c;
}
 
/// Insert `leaf` below `node` at the position of logical index `index`,
/// cloning every node along the path. Nothing reachable from `node` is
/// written, so older versions sharing this subtree stay intact.
static seq_node_t *seq_push_leaf(
  const srn_context_t *ctx, const seq_node_t *node, uint8_t depth, uint64_t index, seq_node_t *leaf
) {
  seq_node_t *copy = seq_clone_node(ctx, node);
  uint16_t idx     = seq_depth_index(depth, index);
 
  if (depth == 1) {
    copy->children[idx] = (seq_elem_t)leaf;
    return copy;
  }
 
  seq_node_t *child   = (seq_node_t *)node->children[idx];
  copy->children[idx] = (child == nullptr)
                          ? (seq_elem_t)seq_new_path(ctx, depth - 1, leaf)
                          : (seq_elem_t)seq_push_leaf(ctx, child, depth - 1, index, leaf);
  return copy;
}
 
seq_t seq_empty(const srn_context_t *ctx) {
  PANIC_IF_NULL(ctx);
  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;
  seq.seq_ctx     = ctx;
  return seq;
}
 
seq_t seq_push(const seq_t *seq, seq_elem_t x) {
  const srn_context_t *ctx = seq->seq_ctx;
  PANIC_IF_NULL(ctx);
 
  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.len      = 0;
    failed_seq.tail_len = 0;
    failed_seq.depth    = 0;
    failed_seq.root     = nullptr;
    failed_seq.tail     = nullptr;
    failed_seq.seq_ctx  = seq->seq_ctx;
    return failed_seq;
  }
 
  if (seq->tail_len < SEQ_BR) {
    // The tail buffer is shared with every older version of this seq, so
    // the new version appends into its own copy.
    seq_t new_seq       = *seq;
    new_seq.maybe_error = nullptr;
    new_seq.tail        = seq_create_page(ctx);
 
    for (uint16_t i = 0; i < seq->tail_len; i++) {
      new_seq.tail[i] = seq->tail[i];
    }
 
    new_seq.tail[new_seq.tail_len++] = x;
    new_seq.len++;
    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 around the current tail buffer. Sharing the buffer is safe;
  // it is full, and a push onto any version holding it promotes instead of
  // writing into it.
  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.maybe_error   = nullptr;
    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;
  }
  // Insert the leaf at the right fringe, cloning the path from the root so
  // no node shared with older versions is written.
  seq_t new_seq       = *seq;
  new_seq.maybe_error = nullptr;
  new_seq.root        = seq_push_leaf(ctx, seq->root, seq->depth, (uint64_t)sz_without_tail, leaf);
  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;
}
 
/// Negative index is not supported
seq_lookup_result_t seq_get(const seq_t *seq, size_t n) {
  const srn_context_t *ctx = seq->seq_ctx;
  PANIC_IF_NULL(ctx);
  seq_lookup_result_t result = {.data = nullptr, .maybe_error = nullptr};
 
  if (n >= seq->len) {
    // Size the message by asking snprintf first; a fixed buffer sized from
    // sizeof(size_t) counts bytes, not digits, and overflows on large
    // indices.
    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);
 
    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;
    }
 
    // A read must not create nodes. Every index below the tail has a full
    // path, so a missing child is corruption, not laziness.
    node = (seq_node_t *)node->children[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;
}