core/container/xar package | Odin Programming Language

Exponential Array (Xar). A dynamically growing array using exponentially-sized chunks, providing stable memory addresses for all elements. Unlike `[dynamic]T`, elements are never moved once allocated, making it safe to hold pointers to elements. For more information: https://azmr.uk/dyn/#exponential-arrayxar Example: import "core:container/xar" 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) ptr := xar.get_ptr(&x, 1) // ptr remains valid after more push_backs xar.push_back(&x, 40) fmt.println(ptr^) // prints 20 }

Collection Info

Collection: core
Path: container/xar
Entries: 71

Source Files

Constants

2

MAX_SHIFT #

MAX_SHIFT :: PLATFORM_BITS >> 1

PLATFORM_BITS #

PLATFORM_BITS :: 8 * size_of(uint)

Types

4

Array #

Array :: Array

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 Example: 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_Iterator #

Array_Iterator :: Array_Iterator

Iterator state for traversing a `Xar`. Fields: - `xar`: Pointer to the exponential array being iterated - `idx`: Current iteration index

Freelist_Array #

Freelist_Array :: Freelist_Array

Freelist_Iterator #

Freelist_Iterator :: Freelist_Iterator

Procedures

38

append_and_get_ptr #

@(require_results)

append_and_get_ptr :: proc(x: ^$X/Array($T, $SHIFT), value: $T, loc := #caller_location) -> (ptr: $$deferred_return, err: Allocator_Error) {…}

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 Example: 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 }

array_append_and_get_ptr #

@(require_results)

array_append_and_get_ptr :: proc(x: ^$X/Array($T, $SHIFT), value: $T, loc := #caller_location) -> (ptr: $$deferred_return, err: Allocator_Error) {…}

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 Example: 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 }

array_cap #

@(require_results)

array_cap :: proc "contextless" (x: $X/Array($T, $SHIFT)) -> int {…}

Returns the number of allocated elements

array_clear #

array_clear :: proc "contextless" (x: ^$X/Array($T, $SHIFT)) {…}

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

array_destroy #

array_destroy :: proc(x: ^$X/Array($T, $SHIFT)) {…}

Frees all allocated chunks and resets the exponential array. **Inputs** - `x`: Pointer to the exponential array to destroy

array_get #

@(require_results)

array_get :: proc(x: ^$X/Array($T, $SHIFT), #any_int index: int, loc := #caller_location) -> (val: $$deferred_return) {…}

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

array_get_ptr #

@(require_results)

array_get_ptr :: proc(x: ^$X/Array($T, $SHIFT), #any_int index: int, loc := #caller_location) -> (val: $$deferred_return) {…}

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 Example: 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 }

array_get_ptr_unsafe #

@(require_results)

array_get_ptr_unsafe :: proc "contextless" (x: ^$X/Array($T, $SHIFT), #any_int index: int) -> (val: $$deferred_return) {…}

No bounds checking

array_init #

array_init :: proc(x: ^$X/Array($T, $SHIFT), allocator := context.allocator) {…}

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)

array_iterate_by_ptr #

array_iterate_by_ptr :: proc(it: ^Array_Iterator($T, $SHIFT)) -> (val: $$deferred_return, idx: int, ok: bool) {…}

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

array_iterate_by_val #

array_iterate_by_val :: proc(it: ^Array_Iterator($T, $SHIFT)) -> (val: $$deferred_return, idx: int, ok: bool) {…}

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

array_iterator #

array_iterator :: proc(xar: ^$X/Array($T, $SHIFT)) -> $$deferred_return {…}

Create an iterator for traversing the exponential array. **Inputs** - `xar`: Pointer to the exponential array **Returns** - an iterator positioned at the start Example: 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^) } } Output: 10 20 30

array_len #

@(require_results)

array_len :: proc "contextless" (x: $X/Array($T, $SHIFT)) -> int {…}

Returns the length of the exponential-array

array_linear_search #

@(require_results)

array_linear_search :: proc(x: ^$X/Array($T, $SHIFT), elem: $T) -> (index: int, found: bool) {…}

array_pop #

array_pop :: proc(x: ^$X/Array($T, $SHIFT), loc := #caller_location) -> (val: $$deferred_return) {…}

`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.

array_pop_safe #

@(require_results)

array_pop_safe :: proc(x: ^$X/Array($T, $SHIFT)) -> (val: $$deferred_return, ok: bool) {…}

`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.

array_push_back_elem #

array_push_back_elem :: proc(x: ^$X/Array($T, $SHIFT), value: $T, loc := #caller_location) -> (n: int, err: Allocator_Error) {…}

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 Example: 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 }

array_push_back_elem_and_get_ptr #

@(require_results)

array_push_back_elem_and_get_ptr :: proc(x: ^$X/Array($T, $SHIFT), value: $T, loc := #caller_location) -> (ptr: $$deferred_return, err: Allocator_Error) {…}

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 Example: 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 }

array_push_back_elems #

array_push_back_elems :: proc(x: ^$X/Array($T, $SHIFT), values: ..$T, loc := #caller_location) -> (n: int, err: Allocator_Error) {…}

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)

array_set #

array_set :: proc(x: ^$X/Array($T, $SHIFT), #any_int index: int, value: $T, loc := #caller_location) {…}

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

array_unordered_remove #

array_unordered_remove :: proc(x: ^$X/Array($T, $SHIFT), #any_int index: int, loc := #caller_location) {…}

`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. Example: 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 }

freelist_cap #

@(require_results)

freelist_cap :: proc(x: $X/Freelist_Array($T, $SHIFT)) -> int {…}

freelist_clear #

freelist_clear :: proc(x: ^$X/Freelist_Array($T, $SHIFT)) {…}

freelist_destroy #

freelist_destroy :: proc(x: ^$X/Freelist_Array($T, $SHIFT)) {…}

freelist_get #

@(require_results)

freelist_get :: proc(x: ^$X/Freelist_Array($T, $SHIFT), #any_int index: int, loc := #caller_location) -> $$deferred_return {…}

freelist_get_ptr #

@(require_results)

freelist_get_ptr :: proc(x: ^$X/Freelist_Array($T, $SHIFT), #any_int index: int, loc := #caller_location) -> $$deferred_return {…}

freelist_init #

freelist_init :: proc(x: ^$X/Freelist_Array($T, $SHIFT), allocator := context.allocator) {…}

freelist_is_freed #

@(require_results)

freelist_is_freed :: proc(x: ^$X/Freelist_Array($T, $SHIFT), #any_int index: int) -> bool {…}

freelist_iterate_by_ptr #

@(require_results)

freelist_iterate_by_ptr :: proc(it: ^Freelist_Iterator($T, $SHIFT)) -> (val: $$deferred_return, idx: int, ok: bool) {…}

freelist_iterate_by_val #

@(require_results)

freelist_iterate_by_val :: proc(it: ^Freelist_Iterator($T, $SHIFT)) -> (val: $$deferred_return, idx: int, ok: bool) {…}

freelist_iterator #

freelist_iterator :: proc(x: ^$X/Freelist_Array($T, $SHIFT)) -> $$deferred_return {…}

freelist_len #

@(require_results)

freelist_len :: proc(x: $X/Freelist_Array($T, $SHIFT)) -> int {…}

freelist_linear_search #

@(require_results)

freelist_linear_search :: proc(x: ^$X/Freelist_Array($T, $SHIFT), ptr: ^$T) -> (index: int, found: bool) {…}

freelist_pop #

freelist_pop :: proc(x: ^$X/Freelist_Array($T, $SHIFT), #any_int index: int, loc := #caller_location) -> $$deferred_return {…}

freelist_push #

@(require_results)

freelist_push :: proc(x: ^$X/Freelist_Array($T, $SHIFT), value: $T, loc := #caller_location) -> (ptr: $$deferred_return, err: Allocator_Error) {…}

freelist_push_with_index #

@(require_results)

freelist_push_with_index :: proc(x: ^$X/Freelist_Array($T, $SHIFT), value: $T, loc := #caller_location) -> (ptr: $$deferred_return, index: int, err: Allocator_Error) {…}

freelist_release #

freelist_release :: proc(x: ^$X/Freelist_Array($T, $SHIFT), #any_int index: int, loc := #caller_location) {…}

freelist_set #

freelist_set :: proc(x: ^$X/Freelist_Array($T, $SHIFT), #any_int index: int, value: $T, loc := #caller_location) {…}

Procedure Groups

27

append #

append :: proc{
	array_push_back_elem,
	array_push_back_elems,
}

array_append #

array_append :: proc{
	array_push_back_elem,
	array_push_back_elems,
}

array_push_back #

array_push_back :: proc{
	array_push_back_elem,
	array_push_back_elems,
}

cap #

cap :: proc{
	array_cap,
	freelist_cap,
}

clear #

clear :: proc{
	array_clear,
	freelist_clear,
}

destroy #

destroy :: proc{
	array_destroy,
	freelist_destroy,
}

get #

get :: proc{
	array_get,
	freelist_get,
}

get_ptr #

get_ptr :: proc{
	array_get_ptr,
	freelist_get_ptr,
}

get_ptr_unsafe #

get_ptr_unsafe :: proc{
	array_get_ptr_unsafe,
}

init #

init :: proc{
	array_init,
	freelist_init,
}

is_freed #

is_freed :: proc{
	freelist_is_freed,
}

iterate_by_ptr #

iterate_by_ptr :: proc{
	array_iterate_by_ptr,
	freelist_iterate_by_ptr,
}

iterate_by_val #

iterate_by_val :: proc{
	array_iterate_by_val,
	freelist_iterate_by_val,
}

iterator #

iterator :: proc{
	array_iterator,
	freelist_iterator,
}

len #

len :: proc{
	array_len,
	freelist_len,
}

linear_search #

linear_search :: proc{
	array_linear_search,
	freelist_linear_search,
}

pop #

pop :: proc{
	array_pop,
	freelist_pop,
}

pop_safe #

pop_safe :: proc{
	array_pop_safe,
}

push #

push :: proc{
	freelist_push,
}

push_back #

push_back :: proc{
	array_push_back_elem,
	array_push_back_elems,
}

push_back_elem #

push_back_elem :: proc{
	array_push_back_elem,
}

push_back_elem_and_get_ptr #

push_back_elem_and_get_ptr :: proc{
	array_push_back_elem_and_get_ptr,
}

push_back_elems #

push_back_elems :: proc{
	array_push_back_elems,
}

push_with_index #

push_with_index :: proc{
	freelist_push_with_index,
}

release #

release :: proc{
	freelist_release,
}

set #

set :: proc{
	array_set,
	freelist_set,
}

unordered_remove #

unordered_remove :: proc{
	array_unordered_remove,
}