A red-black tree with the same API as our AVL tree.

Collection Info

View Source
Collection
core
Path
container/rbtree
Entries
25
Constants 0
Types 6
Jump to Types
Color Direction Iterator Node Ordering Tree
Procedures 17
Jump to Procedures
destroy find find_or_insert find_value first init_cmp init_ordered iterator iterator_from_pos iterator_get iterator_next iterator_remove last len node_color remove_key +1 more
Procedure Groups 2
Jump to Procedure Groups
init remove
Variables 0

Source Files

Types

6

Color #

Source 
Color :: Color

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

Iterator #

Source 
Iterator :: Iterator

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

Node #

Source 
Node :: Node

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.

Procedures

17

destroy #

Source 
destroy :: proc(t: ^$T/Tree($Key, $Value), call_on_remove: bool = true) {…}

destroy de-initializes a tree.

find #

Source 
find :: proc(t: $T/Tree($Key, $Value), key: $Key) -> (node: $$deferred_return) {…}

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 #

Source 
find_or_insert :: proc(t: ^$T/Tree($Key, $Value), key: $Key, value: $Value) -> (n: $$deferred_return, inserted: bool, err: Allocator_Error) {…}

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 #

Source 
find_value :: proc(t: $T/Tree($Key, $Value), key: $Key) -> (value: $$deferred_return, ok: bool) #optional_ok {…}

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 #

Source 
first :: proc "contextless" (t: ^$T/Tree($Key, $Value)) -> $$deferred_return {…}

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

init_cmp #

Source 
init_cmp :: proc(t: ^$T/Tree($Key, $Value), cmp_fn: proc(a, b: $Key) -> Ordering, node_allocator := context.allocator) {…}

init_cmp initializes a tree.

init_ordered #

Source 
init_ordered :: proc(t: ^$T/Tree($Key, $Value), node_allocator := context.allocator) {…}

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

iterator #

Source 
iterator :: proc "contextless" (t: ^$T/Tree($Key, $Value), direction: Direction) -> $$deferred_return {…}

iterator returns a tree iterator in the specified direction.

iterator_from_pos #

Source 
iterator_from_pos :: proc "contextless" (t: ^$T/Tree($Key, $Value), pos: ^Node($Key, $Value), direction: Direction) -> $$deferred_return {…}

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

iterator_get #

Source 
iterator_get :: proc "contextless" (it: ^$I/Iterator($Key, $Value)) -> $$deferred_return {…}

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 #

Source 
iterator_next :: proc "contextless" (it: ^$I/Iterator($Key, $Value)) -> ($$deferred_return, bool) {…}

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 #

Source 
iterator_remove :: proc(it: ^$I/Iterator($Key, $Value), call_on_remove: bool = true) -> bool {…}

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 #

Source 
last :: proc "contextless" (t: ^$T/Tree($Key, $Value)) -> $$deferred_return {…}

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

remove_key #

Source 
remove_key :: proc(t: ^$T/Tree($Key, $Value), key: $Key, call_on_remove: bool = true) -> bool {…}

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 #

Source 
remove_node :: proc(t: ^$T/Tree($Key, $Value), node: ^$N/Node($Key, $Value), call_on_remove: bool = true) -> (found: bool) {…}

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

2

remove #

Source 
remove :: proc{
	remove_key,
	remove_node,
}

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.