Data Structures

---

Instruments process data at runtime -- queues of pending actions, lists of active voices, pools of routing slots. KSP has no built-in data structures beyond arrays, so IVLS provides a library of them. Each is implemented as a set of macros that generate the storage, pointers, and operations you need.

This chapter covers the three data structure families: the ADT collection (Queue, Stack, List, Heap), the FIFO linked list, and Dynabase (mixed-radix integer packing).

ADT: Queue, Stack, List, Heap

---

The ADT module provides four standard data structures, all created with a similar pattern: a creation macro in cb ICB or cb Init, and a functions macro in cb Functions.

Queue (Ring Buffer)

The Queue is a FIFO ring buffer with O(1) push and pop. It is the workhorse data structure in IVLS -- the type system uses it internally for free-block tracking, and the lookahead system uses it for action buffering.

cb ICB:
    adt.CreateQueue(my_queue, 1024)

cb Functions:
    adt.QueueFunctions(my_queue)

After creation, you get:

my_queue.push(42)
my_queue.push(99)

declare val := my_queue.pop.fast()   { val = 42 }
declare top := my_queue.peek.fast()  { top = 99 }

declare n := my_queue.count          { n = 1 }

The .fast() variants skip overflow checks for performance. Use the non-fast versions during development.

Stack

The Stack is a LIFO array with O(1) push and pop:

cb ICB:
    adt.CreateStack(my_stack, 256)

cb Functions:
    adt.StackFunctions(my_stack)

List

The List is a random-access array with O(1) append but O(N) insertion and deletion (elements shift):

cb ICB:
    adt.CreateList(my_list, 128)

cb Functions:
    adt.ListFunctions(my_list)

Lists support indexed access (my_list[i]), append, insert at index, remove at index, and search.

Heap

The Heap is a priority queue with O(log N) push and pop. You choose min-heap or max-heap at creation:

cb ICB:
    adt.CreateHeap(my_heap, 512, adt.HEAP_TYPE_MIN)

cb Functions:
    adt.HeapFunctions(my_heap)

All ADT structures also have 2D variants (adt.Create2DQueue, adt.Create2DStack, adt.Create2DList) that store rows of values per instance, useful for multi-dimensional data.

---

FIFO Linked List

---

The ADT Queue is a ring buffer -- fast, but you can't delete elements from the middle. When you need O(1) push, pop, and arbitrary delete, use the FIFO linked list.

The FIFO is built on the type system. It uses two types -- Entry (a doubly-linked node with prev, next, and data fields) and FIFO (a container with front and back pointers). Both are created by the Stl.Lists node, which is part of the standard library.

Basic Operations

{ Create a new FIFO }
declare my_list := FIFO.new()

{ Push data -- returns the Entry reference }
declare entry1 := FIFO.push(my_list, 42)
declare entry2 := FIFO.push(my_list, 99)
declare entry3 := FIFO.push(my_list, 7)

{ Pop from front -- returns the data }
declare val := FIFO.pop(my_list)    { val = 42 }

{ Delete a specific entry from anywhere in the list }
FIFO.delete_entry(my_list, entry2)

{ Peek at the front entry without removing it }
declare front := FIFO.peek_entry(my_list)

All three core operations -- push, pop, and delete -- are O(1). The Entry's destructor automatically reconnects the prev and next pointers of its neighbors when it is removed.

Iteration

The for_each_in_fifo macro provides safe forward iteration:

for_each_in_fifo(my_list, entry, data)
    { 'entry' is the Entry reference, 'data' is Entry[entry].data }
    if data = 99
        FIFO.delete_entry(my_list, entry)
    end if
end_for_each_fifo(entry)

The iteration macro handles the linked-list traversal for you, using a next pointer that is captured before your loop body runs -- so deleting the current entry during iteration is safe.

When to Use FIFO vs Queue

Use the Queue when you only need push and pop (the common case). Use the FIFO linked list when you need to delete arbitrary elements by reference -- for example, removing a specific voice's action from a buffer, or maintaining an ordered list where items can be cancelled mid-sequence.

---

Dynabase: Mixed-Radix Packing

---

Sometimes you need to pack several small values into a single integer -- a group index, a round-robin counter, a velocity layer -- to use as a compact key or to store multiple dimensions in one array slot.

Dynabase implements a mixed-radix (variable-base) number system. Each "place" in the packed integer has its own base (modulus), so you can pack values with different ranges efficiently.

Setup

Dynabase requires a two-step setup: create the storage in cb ICB, generate the functions in cb Functions:

cb ICB:
    declare my_bases[] := (4, 8, 128)
    dynabase.ICB(mypack, 3, my_bases)

cb Functions:
    dynabase.Functions(mypack)

This creates a 3-place number system where place 0 has base 4 (values 0-3), place 1 has base 8 (values 0-7), and place 2 has base 128 (values 0-127).

Usage

declare packed := 0

{ Set individual places }
mypack.set_place(packed, 0, 2)    { place 0 = 2 }
mypack.set_place(packed, 1, 5)    { place 1 = 5 }
mypack.set_place(packed, 2, 60)   { place 2 = 60 }

{ Read individual places }
declare p0 := mypack.get_place(packed, 0)   { p0 = 2 }
declare p1 := mypack.get_place(packed, 1)   { p1 = 5 }
declare p2 := mypack.get_place(packed, 2)   { p2 = 60 }

The encoding uses multiplication factors cached at setup time, so get and set operations are simple integer arithmetic -- no loops.

If you change the bases at runtime, call mypack.recache() to recompute the factor cache.

When to Use Dynabase

Use Dynabase when you need to:

• Pack a multi-dimensional index into a single integer for array lookup
• Store compact state in a voice field without adding multiple fields
• Create composite keys for hash-like lookups

For most instruments, you won't need Dynabase directly. It appears in systems like TACT where articulation state is packed into compact representations.

---

Choosing the Right Structure

---

Need	Structure	Complexity
FIFO push/pop only	Queue (ring buffer)	O(1) push, O(1) pop
LIFO push/pop	Stack	O(1) push, O(1) pop
Random access, search	List	O(1) append, O(N) insert/delete
Priority ordering	Heap	O(log N) push, O(log N) pop
FIFO with arbitrary delete	FIFO linked list	O(1) push, O(1) pop, O(1) delete
Pack multiple values in one int	Dynabase	O(1) get/set

The Queue and FIFO linked list are by far the most common in production instruments. Stacks appear in undo systems, Lists in UI rendering, Heaps in scheduling, and Dynabase in compact state encoding.