An intrusive doubly-linked list. The 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, } Output: Hello World

Collection Info

View Source
Collection
core
Path
container/intrusive/list
Entries
16
Constants 0
Types 3
Jump to Types
Iterator List Node
Procedures 13
Jump to Procedures
is_empty iterate_next iterate_prev iterator_from_node iterator_head iterator_tail pop_back pop_front push_back push_front remove remove_by_proc remove_by_proc_contextless
Procedure Groups 0
Variables 0

Source Files

Types

3

List #

Source 
List :: 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

Procedures

13

is_empty #

Source 
is_empty :: proc "contextless" (list: ^List) -> bool {…}

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 #

Source 
iterate_next :: proc "contextless" (it: ^Iterator($T)) -> (ptr: $$deferred_return, ok: bool) {…}

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_Next_Struct{value=1} two := My_Next_Struct{value=2} list.push_back(&l, &one.node) list.push_back(&l, &two.node) it := list.iterator_head(l, My_Next_Struct, "node") for num in list.iterate_next(&it) { fmt.println(num.value) } } My_Next_Struct :: struct { node : list.Node, value: int, } Output: 1 2

iterate_prev #

Source 
iterate_prev :: proc "contextless" (it: ^Iterator($T)) -> (ptr: $$deferred_return, ok: bool) {…}

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_prev_example :: proc() { l: list.List one := My_Prev_Struct{value=1} two := My_Prev_Struct{value=2} list.push_back(&l, &one.node) list.push_back(&l, &two.node) it := list.iterator_tail(l, My_Prev_Struct, "node") for num in list.iterate_prev(&it) { fmt.println(num.value) } } My_Prev_Struct :: struct { node : list.Node, value: int, } Output: 2 1

iterator_from_node #

Source 
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 #

Source 
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 #

Source 
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 #

Source 
pop_back :: proc "contextless" (list: ^List) -> ^Node {…}

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 #

Source 
pop_front :: proc "contextless" (list: ^List) -> ^Node {…}

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 #

Source 
push_back :: proc "contextless" (list: ^List, node: ^Node) {…}

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 #

Source 
push_front :: proc "contextless" (list: ^List, node: ^Node) {…}

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 #

Source 
remove :: proc "contextless" (list: ^List, node: ^Node) {…}

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 #

Source 
remove_by_proc :: proc(list: ^List, to_erase: proc(^Node) -> bool) {…}

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 #

Source 
remove_by_proc_contextless :: proc(list: ^List, to_erase: proc "contextless" (^Node) -> bool) {…}

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