package core:container/intrusive/list
Source

⌘K
Ctrl+K
or
/

    Overview

    Package list implements an intrusive doubly-linked list.

    An intrusive container requires a Node to be embedded in your own structure, like this:

    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:

    My_String :: struct {
	using node: list.Node,
	value: string,
}

    Here is a full 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,
}

    Index

    Types (3)
    Constants (0)

    This section is empty.

    Variables (0)

    This section is empty.

    Procedure Groups (0)

    This section is empty.

    Types

    Iterator ¶
    Source

    Iterator :: struct($Value: typeid) {}
    Related Procedures With Parameters
    Related Procedures With Returns

    List ¶
    Source

    List :: struct {
	head: ^Node,
	tail: ^Node,
}
     

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

    Node :: struct {
	prev: ^Node,
	next: ^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 ¶
    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: ^$T, 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_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,
}
    Output: 
    1
2

    iterate_prev ¶
    Source

    iterate_prev :: proc "contextless" (it: ^Iterator($T)) -> (ptr: ^$T, 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_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,
}
    Output: 
    2
1

    iterator_from_node ¶
    Source

    iterator_from_node :: proc "contextless" (node: ^Node, $T: typeid, $field_name: string = ) -> Iterator($T) {…}
     

    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) {…}
     

    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) {…}
     

    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(_: ) -> 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" (_: ) -> 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

    Procedure Groups

    This section is empty.

    Source Files

    Generation Information

    Generated with odin version dev-2024-07 (vendor "odin") Windows_amd64 @ 2024-07-26 21:10:24.191712200 +0000 UTC