Data Structures

IVLS ships two complementary data structure subsystems: the ADT library for typed, fixed-capacity containers, and the FIFO linked-list library for pointer-chained dynamic collections. Both live in std-library/ksp/data-structures/. The Dynabase utility provides mixed-radix integer packing for path and ID encoding.

Why This Exists

KSP provides arrays but no higher-level containers. The ADT and FIFO libraries fill this gap with queue, stack, list, and heap semantics — all backed by pre-allocated integer arrays with known memory costs and O(1) or O(log N) operations.

Key Concepts

Common Return Sentinels

Sentinel	Value	Meaning
adt.TASK_SUCCESS	123456789	Operation succeeded
adt.TASK_FAIL	-123456789	Operation failed (pop from empty queue, etc.)
adt.NULL	-39867414	Empty or invalid reference

ADT scratch variables (adt.arg1–adt.arg4, adt.list_i–adt.list_l) are internal. Do not read or write them from user code during ADT calls. ADT operations must be performed from a single execution context at a time — they are not polyphonic.

Queue (Ring Buffer)

A FIFO ring buffer with O(1) push and pop:

adt.CreateQueue(MyQueue, 10000)
adt.QueueFunctions(MyQueue)

MyQueue.push(value)            // with bounds check
MyQueue.push.fast(value)       // no bounds check
declare v := MyQueue.pop()
declare v := MyQueue.pop.fast()
declare n := MyQueue.count
declare v := MyQueue.peek()

.fast variants skip overflow/underflow checks. Use them in hot paths where you have already verified count > 0.

Production examples: the cluster dispatch queue (1,000,000 capacity) and the lookahead action buffer (10,000 capacity).

Stack (LIFO)

Last-in-first-out with O(1) push and pop:

adt.CreateStack(MyStack, 256)
adt.StackFunctions(MyStack)

MyStack.push(value)
declare v := MyStack.pop()
declare n := MyStack.count

Useful for operations that process items in reverse insertion order, such as unwinding a legato source chain.

List (Random Access)

Ordered array with O(1) indexed access and O(N) insertion/deletion:

adt.CreateList(MyList, 512)
adt.ListFunctions(MyList)

MyList.insert(idx, value)
MyList.remove(idx)
declare v := MyList.get(idx)
MyList.set(idx, value)
declare n := MyList.count

2D variants — adt.Create2DQueue, adt.Create2DStack, adt.Create2DList — store rows of values per slot. Used when each entry needs to carry multiple associated data fields. Stl.MonoLegato uses adt.Create2DList for the per-thread voice stack.

Heap (Priority Queue)

Binary heap with O(log N) push and pop:

adt.CreateHeap(MyHeap, 1024, adt.HEAP_TYPE_MIN)
adt.HeapFunctions(MyHeap)

MyHeap.push(element)         // the element IS the priority key
declare v := MyHeap.pop()    // removes and returns minimum priority item

push() takes one argument — the element value itself is used as the priority key for ordering. Useful for time-ordered event scheduling where the next item is always the earliest timestamp.

FIFO Linked List

The FIFO linked list from std-library/nodes/components/lists.ksp provides a doubly-linked list with O(1) push, pop, and deletion by reference. Unlike ADT structures, it is not fixed-capacity — it allocates Entry objects from the type-system pool.

declare my_fifo := FIFO.new()

declare entry := FIFO.push(my_fifo, some_data)
// entry is the Entry ref — store it if you need O(1) deletion later

declare data := FIFO.pop(my_fifo)

FIFO.delete_entry(my_fifo, entry_ref)  // O(1) deletion by reference

The key advantage over the ADT queue is O(1) mid-list deletion. When you store the entry reference returned by FIFO.push, you can remove that specific item in constant time without scanning the list.

Iteration:

for_each_in_fifo(my_fifo, entry_obj, data_name)
    call process(data_name)
end_for_each_fifo(entry_obj)

Deletion during iteration is safe if done via the current entry_obj.

When to use FIFO vs. ADT queue: - ADT queue: capacity known, only push/pop from ends needed, performance critical - FIFO: O(1) deletion of arbitrary entries by reference, work queue where completed items must be removed mid-list

array.Create — Pool-Backed Dynamic Arrays

For arrays whose effective size varies at runtime but whose maximum is known:

array.Create(MyArray, 1000)

array.Create generates the following functions: - MyArray.new() -> ref — allocates a new entry, returns a reference - MyArray.copy(src) -> ref — allocates a new entry and copies from src - MyArray.delete(ref) — frees a previously allocated entry - MyArray.init(ref) — resets fields to defaults - MyArray.copy_a_to_b(src, dst) — copies all fields from src to dst

Access fields via indexed notation: MyArray[ref].i[idx]

declare r := MyArray.new()
MyArray[r].i[0] := 42
declare v := MyArray[r].i[0]

modrix uses this pattern for routing and modulator cache lists.

Dynabase — Mixed-Radix Integer Packing

Dynabase encodes a multi-dimensional address into a single integer using mixed-radix arithmetic:

// ICB phase: declare namespace and per-dimension bases
dynabase.ICB(MyPath, places, bases)

// Functions phase: generate accessors
dynabase.Functions(MyPath)

// Write a value to one dimension:
MyPath.set_place(num, pl, v)

// Read a value from one dimension:
declare v := MyPath.get_place(num, pl)

// Recompute packed integer after set_place calls:
MyPath.recache()

Each dimension has its own independent base, so packing a (layer=4, param=32, subparam=2) address does not waste bits from a uniform base. Browser path IDs use Dynabase to encode column selection states as a single integer for storage and equality comparison.

Connections to Other Parts of IVLS

The ADT queue is used for the cluster dispatch queue. The lookahead engine uses it for lkh.ActionBuffer. stl-legato uses adt.Create2DList for the mono legato voice buffer and poly legato result lists. The FIFO linked list underlies the VMC modbit lists in vmc. modrix uses array.Create for cache lists. The type-system free block queue is an ADT queue.

Patterns and Caveats

• ADT operations are not polyphonic. Do not call MyQueue.push() from multiple concurrent taskfuncs on the same queue without synchronization.
• The .fast variants on push/pop bypass bounds checking. Only use them when you have already verified capacity with MyQueue.count.
• adt.NULL (-39867414), adt.TASK_FAIL (-123456789), and TYPE.MEM_CLEAR (-123547689) are different values. Confusing them is a source of subtle bugs.

Related

• type-system — the pool allocator that backs Entry and FIFO objects
• lookahead — uses the ring queue for the action buffer
• modrix — uses array-backed cache lists for routing dispatch