package core:container/xar

Source

An Exponential Array with stable element addresses.

Unlike [dynamic]T which reallocates and moves elements when growing, Array allocates separate chunks of exponentially increasing size. This guarantees that pointers to elements remain valid for the lifetime of the container.

Fields:

• chunks: Fixed array of multi-pointers to allocated chunks
• len: Number of elements currently stored
• allocator: Allocator used for chunk allocations

Type Parameters:

• T: The element type
• SHIFT: Controls initial chunk size (1 << SHIFT). Must be in range (0, MAX_SHIFT]. Larger values mean fewer, bigger chunks. Recommended: 4-8.

Chunk sizes grow as:

• chunks[0]: 1 << SHIFT elements
• chunks[1]: 1 << SHIFT elements
• chunks[2]: 1 << (SHIFT + 1) elements
• chunks[3]: 1 << (SHIFT + 2) elements
• chunks[4]: 1 << (SHIFT + 3) elements
• ...and so on

import "core:container/xar"

example :: proc() {
	// Xar with initial chunk size of 16 (1 << 4)
	x: xar.Array(My_Struct, 4)
	defer xar.destroy(&x)
}

• array_cap
• array_clear
• array_destroy
• array_get
• array_get_ptr
• array_get_ptr_unsafe
• array_init
• array_iterator
• array_len
• array_linear_search
• array_pop
• array_pop_safe
• array_push_back_elem
• array_push_back_elem_and_get_ptr
• array_push_back_elems
• array_set
• array_unordered_remove
• append (procedure groups)
• array_append (procedure groups)
• array_push_back (procedure groups)
• cap (procedure groups)
• clear (procedure groups)
• destroy (procedure groups)
• get (procedure groups)
• get_ptr (procedure groups)
• get_ptr_unsafe (procedure groups)
• init (procedure groups)
• iterator (procedure groups)
• len (procedure groups)
• linear_search (procedure groups)
• pop (procedure groups)
• pop_safe (procedure groups)
• push_back (procedure groups)
• push_back_elem (procedure groups)
• push_back_elem_and_get_ptr (procedure groups)
• push_back_elems (procedure groups)
• set (procedure groups)
• unordered_remove (procedure groups)

Iterator state for traversing a Xar.

Fields:

• xar: Pointer to the exponential array being iterated
• idx: Current iteration index

• array_iterate_by_ptr
• array_iterate_by_val
• iterate_by_ptr (procedure groups)
• iterate_by_val (procedure groups)

• freelist_cap
• freelist_clear
• freelist_destroy
• freelist_get
• freelist_get_ptr
• freelist_init
• freelist_is_freed
• freelist_iterator
• freelist_len
• freelist_linear_search
• freelist_pop
• freelist_push
• freelist_push_with_index
• freelist_release
• freelist_set
• cap (procedure groups)
• clear (procedure groups)
• destroy (procedure groups)
• get (procedure groups)
• get_ptr (procedure groups)
• init (procedure groups)
• is_freed (procedure groups)
• iterator (procedure groups)
• len (procedure groups)
• linear_search (procedure groups)
• pop (procedure groups)
• push (procedure groups)
• push_with_index (procedure groups)
• release (procedure groups)
• set (procedure groups)

• freelist_iterate_by_ptr
• freelist_iterate_by_val
• iterate_by_ptr (procedure groups)
• iterate_by_val (procedure groups)

Append an element and return a stable pointer to it. This is useful when you need to initialize a complex struct in-place or retain a reference to the newly added element.

Inputs

• x: Pointer to the exponential array
• value: The element to append

Returns

• a stable pointer to the newly added element
• allocation error if chunk allocation failed

import "core:container/xar"

push_back_and_get_ptr_example :: proc() {
	x: xar.Array(My_Struct, 4)
	defer xar.destroy(&x)

	ptr := xar.push_back_elem_and_get_ptr(&x, My_Struct{}) or_else panic("alloc failed")
	ptr.field = 42  // Initialize in-place
}

Append an element and return a stable pointer to it. This is useful when you need to initialize a complex struct in-place or retain a reference to the newly added element.

Inputs

• x: Pointer to the exponential array
• value: The element to append

Returns

• a stable pointer to the newly added element
• allocation error if chunk allocation failed

import "core:container/xar"

push_back_and_get_ptr_example :: proc() {
	x: xar.Array(My_Struct, 4)
	defer xar.destroy(&x)

	ptr := xar.push_back_elem_and_get_ptr(&x, My_Struct{}) or_else panic("alloc failed")
	ptr.field = 42  // Initialize in-place
}

Returns the number of allocated elements

Resets the array's length to zero without freeing memory. Allocated chunks are retained for reuse.

Frees all allocated chunks and resets the exponential array.

Inputs

• x: Pointer to the exponential array to destroy

Get a copy of the element at the specified index.

Inputs

• x: Pointer to the exponential array
• index: Position of the element (0-indexed)

Returns

• a copy of the element

Get a pointer to the element at the specified index.

The returned pointer remains valid even after additional elements are added, as long as the element is not removed and the array is not destroyed.

Inputs

• x: Pointer to the exponential array
• index: Position of the element (0-indexed)

Returns

• a stable pointer to the element

import "core:container/xar"

get_ptr_example :: proc() {
	x: xar.Array(int, 4)
	defer xar.destroy(&x)

	xar.push_back(&x, 100)
	ptr := xar.get_ptr(&x, 0)

	// Pointer remains valid after growing
	for i in 0..<1000 {
		xar.push_back(&x, i)
	}

	fmt.println(ptr^)  // Still prints 100
}

No bounds checking

Initializes an exponential array with the given allocator.

Inputs

• x: Pointer to the exponential array to initialize
• allocator: Allocator to use for chunk allocations (defaults to context.allocator)

Advance the iterator and returns a pointer to the next element.

Inputs

• it: Pointer to the iterator

Returns

• pointer to the current element
• true if an element was returned, false if iteration is complete

Advance the iterator and returns the next element.

Inputs

• it: Pointer to the iterator

Returns

• current element
• true if an element was returned, false if iteration is complete

Create an iterator for traversing the exponential array.

Inputs

• xar: Pointer to the exponential array

Returns

• an iterator positioned at the start

import "core:container/xar"
import "core:fmt"

iterator_example :: proc() {
	x: xar.Array(int, 4)
	defer xar.destroy(&x)

	xar.push_back(&x, 10)
	xar.push_back(&x, 20)
	xar.push_back(&x, 30)

	it := xar.iterator(&x)
	for val in xar.iterate_by_ptr(&it) {
		fmt.println(val^)
	}
}

10
20
30

Returns the length of the exponential-array

pop will remove and return the end value of an exponential array x and reduces the length of the array by 1.

Note: If the exponential array has no elements (xar.len(x) == 0), this procedure will panic.

pop_safe trys to remove and return the end value of dynamic array x and reduces the length of the array by 1. If the operation is not possible, it will return false.

Append an element to the end of the exponential array. Allocates a new chunk if necessary. Existing elements aren't moved, and their pointers remain stable.

Inputs

• x: Pointer to the exponential array
• value: The element to append

Returns

• number of elements added (always 1 on success)
• allocation error if chunk allocation failed

import "core:container/xar"

push_back_example :: proc() {
	x: xar.Array(string, 4)
	defer xar.destroy(&x)

	xar.push_back(&x, "hello")
	xar.push_back(&x, "world")

	fmt.println(xar.get(&x, 0))  // hello
	fmt.println(xar.get(&x, 1))  // world
}

• append
• array_append
• array_push_back
• push_back
• push_back_elem

Append an element and return a stable pointer to it. This is useful when you need to initialize a complex struct in-place or retain a reference to the newly added element.

Inputs

• x: Pointer to the exponential array
• value: The element to append

Returns

• a stable pointer to the newly added element
• allocation error if chunk allocation failed

import "core:container/xar"

push_back_and_get_ptr_example :: proc() {
	x: xar.Array(My_Struct, 4)
	defer xar.destroy(&x)

	ptr := xar.push_back_elem_and_get_ptr(&x, My_Struct{}) or_else panic("alloc failed")
	ptr.field = 42  // Initialize in-place
}

Append multiple elements to the end of the exponential array.

Inputs

• x: Pointer to the exponential array
• values: The elements to append

Returns

• number of elements successfully added
• allocation error if chunk allocation failed (partial append possible)

• append
• array_append
• array_push_back
• push_back
• push_back_elems

Set the element at the specified index to the given value.

Inputs

• x: Pointer to the exponential array
• index: Position of the element (0-indexed)
• value: The value to set

unordered_remove removed the element at the specified index. It does so by replacing the current end value with the old value, and reducing the length of the exponential array by 1.

Note: This is an O(1) operation. Note: This is currently no procedure that is the equivalent of an "ordered_remove" Note: If the index is out of bounds, this procedure will panic.

Note: Pointers to the last element become invalid (it gets moved). Pointers to other elements remain valid.

import "core:container/xar"

unordered_remove_example :: proc() {
	x: xar.Array(int, 4)
	defer xar.destroy(&x)

	xar.push_back(&x, 10)
	xar.push_back(&x, 20)
	xar.push_back(&x, 30)

	xar.unordered_remove(&x, 0)  // Removes 10, replaces with 30

	// Array now contains [30, 20]
	fmt.println(xar.get(&x, 0))  // 30
	fmt.println(xar.get(&x, 1))  // 20
}