package core:container/intrusive/list
Overview
Package list implements an intrusive doubly-linked list.
An intrusive container requires a Node
to be embedded in your own structure, like this.
Example:
My_String :: struct {
node: list.Node,
value: string,
}
Embedding the members of a list.Node
in your structure with the using
keyword is also allowed.
Example:
My_String :: struct {
using node: list.Node,
value: string,
}
Here is a full example.
Example:
package test
import "core:fmt"
import "core:container/intrusive/list"
main :: proc() {
l: list.List
one := My_String{value="Hello"}
two := My_String{value="World"}
list.push_back(&l, &one.node)
list.push_back(&l, &two.node)
iter := list.iterator_head(l, My_String, "node")
for s in list.iterate_next(&iter) {
fmt.println(s.value)
}
}
My_String :: struct {
node: list.Node,
value: string,
}
Hello World
Index
Constants (0)
This section is empty.
Variables (0)
This section is empty.
Procedure Groups (0)
This section is empty.
Types
Iterator ¶
Iterator :: struct($Value: typeid) {}
Related Procedures With Parameters
Related Procedures With Returns
List ¶
An intrusive doubly-linked list
As this is an intrusive container, a Node
must be embedded in your own
structure which is conventionally called a "link". The use of push_front
and push_back
take the address of this node. Retrieving the data
associated with the node requires finding the relative offset of the node
of the parent structure. The parent type and field name are given to
iterator_*
procedures, or to the built-in container_of
procedure.
This data structure is two-pointers in size:
8 bytes on 32-bit platforms and 16 bytes on 64-bit platforms
Related Procedures With Parameters
Node ¶
The list link you must include in your own structure.
Related Procedures With Parameters
Related Procedures With Returns
Constants
This section is empty.
Variables
This section is empty.
Procedures
is_empty ¶
Checks whether the given list does not contain any element.
Inputs list: The container list
Returns true
if list
is empty, false
otherwise
iterate_next ¶
Retrieves the next element in a list and advances the iterator.
Inputs
it: The iterator
Returns
ptr: The next list element
ok: true
if the element is valid (the iterator could advance), false
otherwise
Example:
import "core:fmt"
import "core:container/intrusive/list"
iterate_next_example :: proc() {
l: list.List
one := My_Struct{value=1}
two := My_Struct{value=2}
list.push_back(&l, &one.node)
list.push_back(&l, &two.node)
it := list.iterator_head(l, My_Struct, "node")
for num in list.iterate_next(&it) {
fmt.println(num.value)
}
}
My_Struct :: struct {
node : list.Node,
value: int,
}
1 2
iterate_prev ¶
Retrieves the previous element in a list and recede the iterator.
Inputs
it: The iterator
Returns
ptr: The previous list element
ok: true
if the element is valid (the iterator could recede), false
otherwise
Example:
import "core:fmt"
import "core:container/intrusive/list"
iterate_next_example :: proc() {
l: list.List
one := My_Struct{value=1}
two := My_Struct{value=2}
list.push_back(&l, &one.node)
list.push_back(&l, &two.node)
it := list.iterator_tail(l, My_Struct, "node")
for num in list.iterate_prev(&it) {
fmt.println(num.value)
}
}
My_Struct :: struct {
node : list.Node,
value: int,
}
2 1
iterator_from_node ¶
iterator_from_node :: proc "contextless" (node: ^Node, $T: typeid, $field_name: string = ) -> Iterator($T=typeid) {…}
Creates an iterator pointing at the specified node of a list.
Inputs
node: a list node
T: The type of the list's elements
field_name: The name of the node field in the T
structure
Returns An iterator pointing at node
iterator_head ¶
iterator_head :: proc "contextless" (list: List, $T: typeid, $field_name: string = ) -> Iterator($T=typeid) {…}
Creates an iterator pointing at the head of the given list. For an example, see iterate_next
.
Inputs
list: The container list
T: The type of the list's elements
field_name: The name of the node field in the T
structure
Returns An iterator pointing at the head of list
iterator_tail ¶
iterator_tail :: proc "contextless" (list: List, $T: typeid, $field_name: string = ) -> Iterator($T=typeid) {…}
Creates an iterator pointing at the tail of the given list. For an example, see iterate_prev
.
Inputs
list: The container list
T: The type of the list's elements
field_name: The name of the node field in the T
structure
Returns An iterator pointing at the tail of list
pop_back ¶
Removes and returns the element at the back of the list with O(1) time complexity.
Inputs list: The container list
Returns The node member of the user-defined element structure, or nil
if the list is empty
pop_front ¶
Removes and returns the element at the front of the list with O(1) time complexity.
Inputs list: The container list
Returns The node member of the user-defined element structure, or nil
if the list is empty
push_back ¶
Inserts a new element at the back of the list with O(1) time complexity.
Inputs list: The container list node: The node member of the user-defined element structure
push_front ¶
Inserts a new element at the front of the list with O(1) time complexity.
Inputs list: The container list node: The node member of the user-defined element structure
remove ¶
Removes an element from a list with O(1) time complexity.
Inputs list: The container list node: The node member of the user-defined element structure to be removed
remove_by_proc ¶
Removes from the given list all elements that satisfy a condition with O(N) time complexity.
Inputs
list: The container list
to_erase: The condition procedure. It should return true
if a node should be removed, false
otherwise
remove_by_proc_contextless ¶
Removes from the given list all elements that satisfy a condition with O(N) time complexity.
Inputs
list: The container list
to_erase: The _contextless_ condition procedure. It should return true
if a node should be removed, false
otherwise
Procedure Groups
This section is empty.
Source Files
Generation Information
Generated with odin version dev-2024-12 (vendor "odin") Windows_amd64 @ 2024-12-06 21:12:12.381116200 +0000 UTC