core/container/rbtree

container_rbtree

Types

Color :: enum uintptr {
	Black = 0,
	Red   = 1,
}

Source

Might store this in the node pointer in the future, but that'll require a decent amount of rework to pass ^^N instead of ^N

Direction :: enum i8 {
	// Backward is the in-order backwards direction.
	Backward = -1,
	// Forward is the in-order forwards direction.
	Forward  = 1,
}

Source

Originally based on the CC0 implementation from literateprograms.org But with API design mimicking core:container/avl for ease of use. Direction specifies the traversal direction for a tree iterator.

Iterator :: struct {}Source

Iterator is a tree iterator.

WARNING: It is unsafe to modify the tree while iterating, except via the iterator_remove method.

Node :: struct {}Source

Node is a red-black tree node.

WARNING: It is unsafe to mutate value if the node is part of a tree if doing so will alter the Node's sort position relative to other elements in the tree.

Ordering :: OrderingSource

Tree :: struct {}Source

Tree is a red-black tree

Procedures

destroy :: proc(t: ^T, call_on_remove: bool)Source

destroy de-initializes a tree.

find :: proc(t: T, key: Key) -> (node: ^Node(Key, Value))Source

find finds the key in the tree, and returns the corresponding node, or nil if and only if (⟺) the value is not present.

find_or_insert :: proc(t: ^T, key: Key, value: Value) -> (n: ^Node(Key, Value), inserted: bool, err: runtime.Allocator_Error)

Source

find_or_insert attempts to insert the key-value pair into the tree, and returns the node, a boolean indicating if a new node was inserted, and the node allocator error if relevant. If the key is already present, the existing node is updated and returned.

find_value :: proc(t: T, key: Key) -> (value: Value, ok: bool)Source

find_value finds the key in the tree, and returns the corresponding value, or nil if and only if (⟺) the value is not present.

first :: proc(t: ^T) -> (^Node(Key, Value))Source

first returns the first node in the tree (in-order) or nil if and only if (⟺) the tree is empty.

init_cmp :: proc(t: ^T, cmp_fn: proc(a: Key, b: Key) -> (Ordering), node_allocator: mem.Allocator = context.allocator)Source

init_cmp initializes a tree.

init_ordered :: proc(t: ^T, node_allocator: mem.Allocator = context.allocator)Source

init_ordered initializes a tree containing ordered keys, with a comparison function that results in an ascending order sort.

iterator :: proc(t: ^T, direction: Direction) -> (Iterator(Key, Value))Source

iterator returns a tree iterator in the specified direction.

iterator_from_pos :: proc(t: ^T, pos: ^Node(Key, Value), direction: Direction) -> (Iterator(Key, Value))Source

iterator_from_pos returns a tree iterator in the specified direction, spanning the range [pos, last] (inclusive).

iterator_get :: proc(it: ^I) -> (^Node(Key, Value))Source

iterator_get returns the node currently pointed to by the iterator, or nil if and only if (⟺) the node has been removed, the tree is empty, or the end of the tree has been reached.

iterator_next :: proc(it: ^I) -> (^Node(Key, Value), bool)Source

iterator_next advances the iterator and returns the (node, true) or or (nil, false) if and only if (⟺) the end of the tree has been reached.

Note: The first call to iterator_next will return the first node instead of advancing the iterator.

iterator_remove :: proc(it: ^I, call_on_remove: bool) -> (bool)Source

iterator_remove removes the node currently pointed to by the iterator, and returns true if and only if (⟺) the removal was successful. Semantics are the same as the Tree remove.

last :: proc(t: ^T) -> (^Node(Key, Value))Source

last returns the last element in the tree (in-order) or nil if and only if (⟺) the tree is empty.

len :: proc(t: T) -> (node_count: int)Source

node_color :: proc(n: ^N) -> (c: Color)Source

remove_key :: proc(t: ^T, key: Key, call_on_remove: untyped boolean = true) -> (bool)Source

remove_value removes a value from the tree, and returns true if and only if (⟺) the removal was successful. While the node's key + value will be left intact, the node itself will be freed via the tree's node allocator.

remove_node :: proc(t: ^T, node: ^N, call_on_remove: untyped boolean = true) -> (found: bool)Source

remove_node removes a node from the tree, and returns true if and only if (⟺) the removal was successful. While the node's key + value will be left intact, the node itself will be freed via the tree's node allocator.

Procedure Groups

init :: proc{init_ordered, init_cmp}Source

init initializes a tree.

remove :: proc{remove_key, remove_node}Source

remove removes a node or value from the tree, and returns true if and only if (⟺) the removal was successful. While the node's value will be left intact, the node itself will be freed via the tree's node allocator.

container_rbtree

Types

Procedures

Procedure Groups

Find anything

Settings