BasedList

BasedList — a high-performance RRB-tree list for Odin.

Package	based
Type	BasedList($T)
License	MIT

Generational copy-on-write, arena node pools, strict radix indexing when the tree is dense, and Elias–Fano size tables on relaxed (post-concat) nodes.

Docs

Doc	Content
Explainer	Linked list → buckets → bit-indexed list → RRB → BasedList (Handmade-style)
Public API	Store, gen, list ops, iteration, contracts
Benchmarks	Current numbers vs immer (u8, Apple Silicon)
RRB test catalog	Historical cases from core.rrb-vector / etc.

Quick start

import bl "path/to/based"

main :: proc() {
    store := bl.create_store(u8)
    defer bl.destroy_store(&store)

    gen := bl.gen_begin(&store)
    list := bl.create(u8, &store, gen)

    bl.push(&list, 'a')
    bl.push(&list, 'b')
    assert(bl.get(&list, 0) == 'a')
    assert(bl.length(&list) == 2)
}

Smaller virtual reservation (still grows by committing pages as needed):

store := bl.create_store_opts(u8, { pool_reserve = 64 * mem.Megabyte })

Features

• Branching factor M=32, inline tail for fast append
• Arena pools (virtual.Arena) + generation COW
• Ops: push, append_slice / from_slice, get, set, take / drop / split, concat, insert_at
• chunk_iterator / walk_leaves / fold_leaves for bulk scans
• Exclusive same-gen insert path for single-writer workloads (e.g. editor buffers)

Ownership model

Read this before integrating.

Store vs handle

• A Store owns branch/leaf pools (virtual-reserved, demand-committed).
• A BasedList is a handle into a store (root offset, gen, tail, length).
• Destroying or resetting a store invalidates all handles into it.

Generations

• gen_begin(store) mints a Gen_Id (u16, max 65 536 per store life).
• Nodes carry a gen; exclusive mutation is allowed when node.gen == tree.gen.id.
• Single mutator: do not shallow-copy a handle and mutate both copies.
  Snapshots need a new gen and COW (or treat the old handle as immutable and never write through it).
• Stale-gen mutation asserts in ODIN_DEBUG, or always with -define:BASED_STRICT_GEN=true.

Consuming operations

These empty their input handles (inputs become empty lists; do not use them again):

Op	Consumes
take, drop	the source tree
split	the source tree
concat	both left and right

right := bl.drop(&list, n)   // list is empty afterward; use `right`

Memory (arena lifetime)

Handmade / Odin-style: the store is the arena. There is no per-node GC.

• Pools reserve address space (POOL_RESERVE = 1 GiB each by default; override with Store_Options).
• Resident memory grows as nodes are allocated; a freelist reuses slots within a live store.
• End a lifetime with:
  • destroy_store — tear down pools, or
  • store_reset — re-init pools, invalidate all handles, reset gen counter.
• Pattern: one store per document / job / session. When the session ends, destroy or reset. Do not expect mid-session “collect unreachable versions.”

Bounds & asserts

Public ops assert on out-of-bounds indices, pool exhaust, and gen wrap — the Odin default, not a temporary stand-in for try_* APIs.
Release builds that pass -disable-assert must guarantee valid inputs themselves (clamp untrusted indices at the call site).

Limits

Limit	Value
Branching factor M	32
Max shift	25 (~1G elements)
Gens per store	65 536 (u16)
Threading	single-threaded store

Iteration

Use case	API
Full scan / reduce	walk_leaves or fold_leaves
Ranged / resumable	chunk_iterator + next_chunk
Random access	get
Mid insert	insert_at (exclusive-gen spine when unshared)

Prefer leaf/chunk APIs for sequential scans — they are ~10–50× faster than per-element get on large trees.

Build & test

# Correctness (debug + release-shaped)
./scripts/test.sh

# Or manually
odin run smoke/ -out:/tmp/based_smoke && /tmp/based_smoke

Benchmarks (optional; not required for correctness):

# Point these at your local third-party checkouts (no machine-local defaults)
export IMMER_INC=/path/to/immer          # dir containing immer/
export FREDBUF_DIR=/path/to/fredbuf      # dir containing fredbuf.h
export PIECE_DIR=/path/to/piece-table    # optional, some older benches
./scripts/build-competitors.sh

# vs immer
odin build bench/ef_vs_immer_full -o:speed -disable-assert -no-bounds-check \
  -extra-linker-flags:"-lc++ -lc++abi" -out:/tmp/bench_based
/tmp/bench_based

# vs fredbuf (piece-tree text buffer)
odin build bench/based_vs_fredbuf -o:speed -disable-assert -no-bounds-check \
  -extra-linker-flags:"-lc++ -lc++abi" -out:/tmp/bench_based_vs_fredbuf
/tmp/bench_based_vs_fredbuf

Layout

Path	Role
based/	Library (package based, split by subsystem — see header in based.odin)
smoke/	Smoke + internal tests
bench/	Benchmarks
vendor/	immer / c-rrb / … (bench only)
scripts/	test + competitor builds

based/ implementation files

File	Contents
based.odin	Package contracts, constants, public/private types
store.odin	Pools, store lifecycle, gen, COW accessors
ef.odin	Elias–Fano size tables + node builders
list.odin	create / length / sizing
get.odin	Descent + get
push.odin	push / append_slice / from_slice
set.odin	set
slice.odin	take / drop / split
insert.odin	insert_at + exclusive owned-spine path
concat.odin / concat_pack.odin	Height-aware concat + densify pack
iter.odin	walk_leaves / fold_leaves / chunk_iterator

Compile-time knobs

Define	Default	Meaning
BASED_INSERT_OWNED_SPINE	true	Exclusive in-place insert
BASED_INSERT_LEAF_SPLICE	true	COW leaf splice fallback
BASED_SPLIT_DUAL	true	One-pass split
BASED_SLICE_STEAL	false	Experimental steal take/drop
BASED_STRICT_GEN	false	Always check gen on mutations

Who this is for

• Good fit: single-writer lists/buffers (editors, append-heavy builders), exclusive-gen mutation, session-scoped arena store (destroy_store / store_reset when the document or job ends).
• Not a fit: multi-threaded mutation; immer-style long multi-snapshot heaps with automatic node reclaim.

Production checklist

• Single package + documented public surface
• Ownership / consuming / gen contracts documented
• Arena lifetime model (destroy_store / store_reset only — no GC API)
• Configurable pool reserve + store_stats
• Smoke in debug and -o:speed -disable-assert
• MIT license
• Clone-friendly tests (no third-party deps for ./scripts/test.sh)
• Multi-platform CI matrix (Linux/Windows) if you ship cross-platform

License

MIT — see LICENSE.