container_intrusive_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

The list link you must include in your own structure.

Checks whether the given list does not contain any element.

Inputs

• list: The container list

Returns true if list is empty, false otherwise

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

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

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

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

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

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

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

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

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

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

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

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