seq.h

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/>.
 */
 
#pragma once
 
/// @file
/// This is an implementation of bit - partitioned, persistent, immutable
/// sequence For more information, have a look at `Ideal hash trees` paper.
///
/// TL;DR:
///  - Every struct is immutable (from user perspective).
///  - Nodes are persistent and immutable.
///  - Nodes are heap allocated
///  - Heads can be stack allocated
///  - We create a new head for any change
///  - Heads contain a tail buffer that will be converted to a leaf node
///    when they are full
///  - This data structure is NOT effecient for extracting sub sequences
///  - This data structure is effecient for tail operations,
///  - If you need a subset of the elments in the sequence, create a list
///    view out of them instead of extracting them as a new seq.
///  - Deleting operation is O(N)
///
/// TODO:
///   - Create map and filter function or a generic fold
///   - Create a helper function to help creating list view from the seq
 
// clang-format off
/* AI Generated (🤦)
 ------------------------------------------------------------------------------
 Example (readable scale): B = 4, SHIFT = 2
 -------------------------------------------------------------------------------
 seq state:
   len      = 11
   tail_len = 3                         // last 3 elements live in tail
   depth    = 1                         // one internal level above leaves
   tree     = elements [0..7]           // first 8 elements in the tree
   tail     = elements [8, 9, 10]
 
 High-level view
 ┌────────────┐           ┌─────────────────────── Tree (0..7) ───────────────────────┐
 │   seq_t    │           │                                                           │
 │ len = 11   │           │                (depth = 1, B = 4, SHIFT = 2)              │
 │ tail_len=3 │           │                                                           │
 │ depth = 1  │           │  Root                                                     │
 │ root ──────┼──────────►│  child[0] ─┐       child[1] ─┐       child[2]   child[3]  │
 │ tail ──┐   │           │            ▼                ▼           (NULL)     (NULL) │
 └────────┴───┘           │           Node0            Node1                          │
          │               │          ┌───────┐        ┌───────┐                       │
          ▼               │          │c[0]   │        │c[0]   │                       │
   Tail (8..10)           │          │c[1]   │        │c[1]   │                       │
   [ 8 | 9 | 10 ]         │          │c[2]   │        │c[2]──► Leaf(4..7)             │
                          │          │c[3]   │        │c[3]   │                       │
                          │          └──┬────┘        └───────┘                       │
                          │             │                                     ┌───────┐
                          │             └────────────► Leaf(0..3)             │4 5 6 7│
                          │                                                   │^      │
                          │                Leaves hold up to B elements       └───────┘
                          └───────────────────────────────────────────────────────────┘
 
 Concrete leaf contents
   Leaf(0..3): [0, 1, 2, 3]
   Leaf(4..7): [4, 5, 6, 7]
   Tail(8..10): [8, 9, 10]
 
 Bit-partitioned indexing (tree part)
   For an index n in [0..7], with SHIFT=2:
     hi = (n >> 2) & 0b11   // selects Root child[hi]
     lo =  n       & 0b11   // selects leaf slot within that child’s leaf
 
   Example: n = 6  (binary 0b0110)
     hi = 0b01 = 1          → Root.child[1] → Node1
     lo = 0b10 = 2          → Node1.child[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 spine and tail change on push.
   • When tail_len hits B (here 4), the tail is promoted to a new leaf and
     spliced into the tree (cloning nodes along the modified path).
──────────────────────────────────────────────────────────────────────────────*/
// clang-format on
 
#include <stddef.h>
#include <stdint.h>
 
#include "serene/rt/errors.h"
 
typedef struct srn_context_t srn_context_t;
 
// -----------------------------------------------------------------------------
// Tunables
// -----------------------------------------------------------------------------
/// branching factor (power of two)
#define SEQ_BR 32u
 
/// log2(SEQ_BR)
#define SEQ_SHIFT 5u
#define SEQ_MASK  (SEQ_BR - 1u)
 
/// logical length. While techically this implementation will support up to
/// 2^85 elements in each seq, but we will limit it down to
/// (2^64-1)(UINT64_MAX)(on 64bit machines) in order to keep the `seq_t` as
/// small as possible. 12 is the magic number that we use to limit the depth
/// to. 32^11 = 1,152,921,504,606,846,976 elements
#define SEQ_MAX_DEPTH 11
 
/// 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. `seq_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 *seq_elem_t;
 
typedef struct seq_lookup_result_t {
  ERROR_HEADER;
  seq_elem_t data;
} seq_lookup_result_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 seq_node_t {
  /// We allocate `children` to be a buffer of SEQ_BR number of pointers
  seq_elem_t *children;
} seq_node_t;
 
// -----------------------------------------------------------------------------
// Seq
// -----------------------------------------------------------------------------
typedef struct seq_t {
  ERROR_HEADER;
  /// logical length. While techically this implementation will support up to
  /// 2^85 elements in each seq, but we will limit it down to
  /// (2^64-1)(UINT64_MAX)(on 64bit machines) in order to keep the `seq_t` as
  /// small as possible
  size_t len;
  /// 0..SEQ_BR
  uint16_t tail_len;
  /// tree depth in levels (0 == leaf level)
  uint8_t depth;
  /// NULL means “all data is in tail”
  seq_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.
  seq_elem_t *tail;
  /// The context that owns every allocation the seq retains. `seq_empty`
  /// sets it and every version returned by `seq_push` inherits it. Pushes
  /// allocate tail copies, leaves, and cloned nodes in this context's block
  /// chain, never in the pushing caller's, so every version stays valid for
  /// as long as this context lives. Elements are stored as is; the caller
  /// must allocate them with a lifetime at least as long as this context.
  const srn_context_t *seq_ctx;
} seq_t;
 
// -----------------------------------------------------------------------------
// Public API
// -----------------------------------------------------------------------------
/// Create an empty seq pinned to `ctx`. The pinned context owns every
/// allocation the seq (and all of its future versions) retains, so pick a
/// context that lives at least as long as the seq.
[[nodiscard]] [[gnu::nonnull(1)]]
seq_t seq_empty(const srn_context_t *ctx);
[[nodiscard]] [[gnu::nonnull(1)]]
seq_t seq_push(const seq_t *seq, seq_elem_t x);
 
[[nodiscard]] [[gnu::nonnull(1)]]
seq_lookup_result_t seq_get(const seq_t *seq, size_t n);