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;
}
 
/// Get or create the next node of the tree
static inline seq_node_t *seq_next_child(const srn_context_t *ctx, seq_node_t *n, uint16_t index) {
  if (n->children[index] == nullptr) {
    n->children[index] = seq_new_node(ctx);
  }
  return n->children[index];
}
 
seq_t seq_empty(const srn_context_t *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;
  return seq;
}
 
seq_t seq_push(const srn_context_t *ctx, const seq_t *seq, seq_elem_t x) {
  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.tail_len = 0;
    failed_seq.len = 0;
    return failed_seq;
  }
 
  if (seq->tail_len < SEQ_BR) {
    // Tail buffer has enough space
    seq_t new_seq = *seq;
    new_seq.maybe_error = nullptr;
    // new_seq.tail_len++;
    new_seq.len++;
    new_seq.tail[new_seq.tail_len++] = x;
    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 will own the current tail buffer.
  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.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;
  }
  // Otherwise insert the leaf at the right fringe under the parent (d==1)
  seq_node_t *parent = seq->root;
 
  for (uint8_t d = seq->depth; d > 1; --d) {
    uint16_t idx = seq_depth_index(d, (uint64_t)sz_without_tail);
    // ensures internal nodes exist
    parent = seq_next_child(ctx, parent, idx);
  }
 
  // Now at d == 1: use the correct child slot to insert the leaf
  uint16_t leaf_parent_idx = seq_depth_index(1, (uint64_t)sz_without_tail);
  parent->children[leaf_parent_idx] = (seq_elem_t)leaf;
 
  // Start a fresh tail with the pushed element
  seq_t new_seq = *seq;
  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 srn_context_t *ctx, const seq_t *seq, size_t n) {
  seq_lookup_result_t result = {.data = nullptr, .maybe_error = nullptr};
 
  if (n >= seq->len) {
    char *err_msg = (char *)ALLOC(ctx, size_t);
    // +1 is due to null terminated strings
    SNPRINTF(err_msg, sizeof(size_t) + 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;
    }
 
    node = seq_next_child(ctx, node, 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;
}