Linked list implementation. More...

#include "common.h"
#include "list.h"

Macros
#define	cxLinkedListCreateSimple(item_size) cxLinkedListCreate(NULL, NULL, item_size)
	Allocates a linked list for storing elements with `item_size` bytes each.

Functions
CxList *	cxLinkedListCreate (CxAllocator const *allocator, cx_compare_func comparator, size_t item_size)
	Allocates a linked list for storing elements with `item_size` bytes each.

void *	cx_linked_list_at (void const *start, size_t start_index, ptrdiff_t loc_advance, size_t index)
	Finds the node at a certain index.

ssize_t	cx_linked_list_find (void const start, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func, void const elem)
	Finds the index of an element within a linked list.

void *	cx_linked_list_first (void const *node, ptrdiff_t loc_prev)
	Finds the first node in a linked list.

void *	cx_linked_list_last (void const *node, ptrdiff_t loc_next)
	Finds the last node in a linked list.

void *	cx_linked_list_prev (void const begin, ptrdiff_t loc_next, void const node)
	Finds the predecessor of a node in case it is not linked.

void	cx_linked_list_add (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node)
	Adds a new node to a linked list.

void	cx_linked_list_prepend (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node)
	Prepends a new node to a linked list.

void	cx_linked_list_link (void left, void right, ptrdiff_t loc_prev, ptrdiff_t loc_next)
	Links two nodes.

void	cx_linked_list_unlink (void left, void right, ptrdiff_t loc_prev, ptrdiff_t loc_next)
	Unlinks two nodes.

void	cx_linked_list_insert (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void node, void new_node)
	Inserts a new node after a given node of a linked list.

void	cx_linked_list_insert_chain (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void node, void insert_begin, void *insert_end)
	Inserts a chain of nodes after a given node of a linked list.

void	cx_linked_list_remove (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node)
	Removes a node from the linked list.

size_t	cx_linked_list_size (void const *node, ptrdiff_t loc_next)
	Determines the size of a linked list starting with `node`.

void	cx_linked_list_sort (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, ptrdiff_t loc_data, cx_compare_func cmp_func)
	Sorts a linked list based on a comparison function.

int	cx_linked_list_compare (void const begin_left, void const begin_right, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func)
	Compares two lists element wise.

void	cx_linked_list_reverse (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next)
	Reverses the order of the nodes in a linked list.

Variables
bool	CX_DISABLE_LINKED_LIST_SWAP_SBO
	Set this flag to true, if you want to disable the use of SBO for linked list swap operations.

Detailed Description

Linked list implementation.

Also provides several low-level functions for custom linked list implementations.

Author: Mike Becker; Olaf Wintermann

Version: 3.0

Copyright: 2-Clause BSD License

Macro Definition Documentation

◆ cxLinkedListCreateSimple

#define cxLinkedListCreateSimple ( item_size ) cxLinkedListCreate(NULL, NULL, item_size)

Allocates a linked list for storing elements with item_size bytes each.

The list will use cxDefaultAllocator and no comparator function. If you want to call functions that need a comparator, you must either set one immediately after list creation or use cxLinkedListCreate().

If item_size is CX_STORE_POINTERS, the created list will be created as if cxListStorePointers() was called immediately after creation.

Parameters

item_size the size of each element in bytes

Returns: the created list

Function Documentation

◆ cx_linked_list_add()

void cx_linked_list_add	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	new_node
	)

Adds a new node to a linked list.

The node must not be part of any list already.

Remarks: One of the pointers begin or end may be NULL, but not both.

Parameters

begin	a pointer to the begin node pointer (if your list has one)
end	a pointer to the end node pointer (if your list has one)
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)
new_node	a pointer to the node that shall be appended

◆ cx_linked_list_at()

void * cx_linked_list_at	(	void const *	start,
		size_t	start_index,
		ptrdiff_t	loc_advance,
		size_t	index
	)

Finds the node at a certain index.

This function can be used to start at an arbitrary position within the list. If the search index is large than the start index, loc_advance must denote the location of some sort of next pointer (i.e. a pointer to the next node). But it is also possible that the search index is smaller than the start index (e.g. in cases where traversing a list backwards is faster) in which case loc_advance must denote the location of some sort of prev pointer (i.e. a pointer to the previous node).

Parameters

start	a pointer to the start node
start_index	the start index
loc_advance	the location of the pointer to advance
index	the search index

Returns: the node found at the specified index

◆ cx_linked_list_compare()

int cx_linked_list_compare	(	void const *	begin_left,
		void const *	begin_right,
		ptrdiff_t	loc_advance,
		ptrdiff_t	loc_data,
		cx_compare_func	cmp_func
	)

Compares two lists element wise.

Note: Both list must have the same structure.

Parameters

begin_left	the begin of the left list (`NULL` denotes an empty list)
begin_right	the begin of the right list (`NULL` denotes an empty list)
loc_advance	the location of the pointer to advance
loc_data	the location of the `data` pointer within your node struct
cmp_func	the function to compare the elements

Returns: the first non-zero result of invoking cmp_func or: negative if the left list is smaller than the right list, positive if the left list is larger than the right list, zero if both lists are equal.

◆ cx_linked_list_find()

ssize_t cx_linked_list_find	(	void const *	start,
		ptrdiff_t	loc_advance,
		ptrdiff_t	loc_data,
		cx_compare_func	cmp_func,
		void const *	elem
	)

Finds the index of an element within a linked list.

Parameters

start	a pointer to the start node
loc_advance	the location of the pointer to advance
loc_data	the location of the `data` pointer within your node struct
cmp_func	a compare function to compare `elem` against the node data
elem	a pointer to the element to find

Returns: the index of the element or a negative value if it could not be found

◆ cx_linked_list_first()

void * cx_linked_list_first	(	void const *	node,
		ptrdiff_t	loc_prev
	)

Finds the first node in a linked list.

The function starts with the pointer denoted by node and traverses the list along a prev pointer whose location within the node struct is denoted by loc_prev.

Parameters

node	a pointer to a node in the list
loc_prev	the location of the `prev` pointer

Returns: a pointer to the first node

◆ cx_linked_list_insert()

void cx_linked_list_insert	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	node,
		void *	new_node
	)

Inserts a new node after a given node of a linked list.

The new node must not be part of any list already.

Note: If you specify NULL as the node to insert after, this function needs either the begin or the end pointer to determine the start of the list. Then the new node will be prepended to the list.

Parameters

begin	a pointer to the begin node pointer (if your list has one)
end	a pointer to the end node pointer (if your list has one)
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)
node	the node after which to insert (`NULL` if you want to prepend the node to the list)
new_node	a pointer to the node that shall be prepended

◆ cx_linked_list_insert_chain()

void cx_linked_list_insert_chain	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	node,
		void *	insert_begin,
		void *	insert_end
	)

Inserts a chain of nodes after a given node of a linked list.

The chain must not be part of any list already.

If you do not explicitly specify the end of the chain, it will be determined by traversing the next pointer.

Note: If you specify NULL as the node to insert after, this function needs either the begin or the end pointer to determine the start of the list. If only the end pointer is specified, you also need to provide a valid loc_prev location. Then the chain will be prepended to the list.

Parameters

begin	a pointer to the begin node pointer (if your list has one)
end	a pointer to the end node pointer (if your list has one)
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)
node	the node after which to insert (`NULL` to prepend the chain to the list)
insert_begin	a pointer to the first node of the chain that shall be inserted
insert_end	a pointer to the last node of the chain (or NULL if the last node shall be determined)

◆ cx_linked_list_last()

void * cx_linked_list_last	(	void const *	node,
		ptrdiff_t	loc_next
	)

Finds the last node in a linked list.

The function starts with the pointer denoted by node and traverses the list along a next pointer whose location within the node struct is denoted by loc_next.

Parameters

node	a pointer to a node in the list
loc_next	the location of the `next` pointer

Returns: a pointer to the last node

◆ cx_linked_list_link()

void cx_linked_list_link	(	void *	left,
		void *	right,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next
	)

Links two nodes.

Parameters

left	the new predecessor of `right`
right	the new successor of `left`
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)

◆ cx_linked_list_prepend()

void cx_linked_list_prepend	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	new_node
	)

Prepends a new node to a linked list.

The node must not be part of any list already.

Remarks: One of the pointers begin or end may be NULL, but not both.

Parameters

begin	a pointer to the begin node pointer (if your list has one)
end	a pointer to the end node pointer (if your list has one)
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)
new_node	a pointer to the node that shall be prepended

◆ cx_linked_list_prev()

void * cx_linked_list_prev	(	void const *	begin,
		ptrdiff_t	loc_next,
		void const *	node
	)

Finds the predecessor of a node in case it is not linked.

Remarks: If node is not contained in the list starting with begin, the behavior is undefined.

Parameters

begin	the node where to start the search
loc_next	the location of the `next` pointer
node	the successor of the node to find

Returns: the node or NULL if node has no predecessor

◆ cx_linked_list_remove()

void cx_linked_list_remove	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	node
	)

Removes a node from the linked list.

If the node to remove is the begin (resp. end) node of the list and if begin (resp. end) addresses are provided, the pointers are adjusted accordingly.

The following combinations of arguments are valid (more arguments are optional):

loc_next and loc_prev (ancestor node is determined by using the prev pointer, overall O(1) performance)
loc_next and begin (ancestor node is determined by list traversal, overall O(n) performance)

Remarks: The next and prev pointers of the removed node are not cleared by this function and may still be used to traverse to a former adjacent node in the list.

Parameters

begin	a pointer to the begin node pointer (optional)
end	a pointer to the end node pointer (optional)
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)
node	the node to remove

◆ cx_linked_list_reverse()

void cx_linked_list_reverse	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next
	)

Reverses the order of the nodes in a linked list.

Parameters

begin	a pointer to the begin node pointer (required)
end	a pointer to the end node pointer (optional)
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)

◆ cx_linked_list_size()

size_t cx_linked_list_size	(	void const *	node,
		ptrdiff_t	loc_next
	)

Determines the size of a linked list starting with node.

Parameters

node	the first node
loc_next	the location of the `next` pointer within the node struct

Returns: the size of the list or zero if node is NULL

◆ cx_linked_list_sort()

void cx_linked_list_sort	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		ptrdiff_t	loc_data,
		cx_compare_func	cmp_func
	)

Sorts a linked list based on a comparison function.

This function can work with linked lists of the following structure:

typedef struct node node;
struct node {
  node* prev;
  node* next;
  my_payload data;
}

Note: This is a recursive function with at most logarithmic recursion depth.

Parameters

begin	a pointer to the begin node pointer (required)
end	a pointer to the end node pointer (optional)
loc_prev	the location of a `prev` pointer within your node struct (negative if not present)
loc_next	the location of a `next` pointer within your node struct (required)
loc_data	the location of the `data` pointer within your node struct
cmp_func	the compare function defining the sort order

◆ cx_linked_list_unlink()

void cx_linked_list_unlink	(	void *	left,
		void *	right,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next
	)

Unlinks two nodes.

If right is not the successor of left, the behavior is undefined.

Parameters

left	the predecessor of `right`
right	the successor of `left`
loc_prev	the location of a `prev` pointer within your node struct (negative if your struct does not have one)
loc_next	the location of a `next` pointer within your node struct (required)

◆ cxLinkedListCreate()

CxList * cxLinkedListCreate	(	CxAllocator const *	allocator,
		cx_compare_func	comparator,
		size_t	item_size
	)

Allocates a linked list for storing elements with item_size bytes each.

If item_size is CX_STORE_POINTERS, the created list will be created as if cxListStorePointers() was called immediately after creation.

Parameters

allocator	the allocator for allocating the list nodes (if `NULL` the cxDefaultAllocator will be used)
comparator	the comparator for the elements (if `NULL` sort and find functions will not work)
item_size	the size of each element in bytes

Returns: the created list

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ cxLinkedListCreateSimple

Function Documentation

◆ cx_linked_list_add()

◆ cx_linked_list_at()

◆ cx_linked_list_compare()

◆ cx_linked_list_find()

◆ cx_linked_list_first()

◆ cx_linked_list_insert()

◆ cx_linked_list_insert_chain()

◆ cx_linked_list_last()

◆ cx_linked_list_link()

◆ cx_linked_list_prepend()

◆ cx_linked_list_prev()

◆ cx_linked_list_remove()

◆ cx_linked_list_reverse()

◆ cx_linked_list_size()

◆ cx_linked_list_sort()

◆ cx_linked_list_unlink()

◆ cxLinkedListCreate()