Linked list implementation. More...

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

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

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

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

void *	cx_linked_list_find (const void start, ptrdiff_t loc_advance, ptrdiff_t loc_data, cx_compare_func cmp_func, const void elem, size_t *found_index)
	Finds the node containing an element within a linked list.

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

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

void *	cx_linked_list_prev (const void begin, ptrdiff_t loc_next, const void 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_insert_sorted (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *new_node, cx_compare_func cmp_func)
	Inserts a node into a sorted linked list.

void	cx_linked_list_insert_sorted_chain (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *insert_begin, cx_compare_func cmp_func)
	Inserts a chain of nodes into a sorted linked list.

size_t	cx_linked_list_remove_chain (void begin, void end, ptrdiff_t loc_prev, ptrdiff_t loc_next, void *node, size_t num)
	Removes a chain of nodes from the linked list.

static 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 (const void *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 (const void begin_left, const void 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.

Detailed Description

Linked list implementation.

Author: Mike Becker; Olaf Wintermann

Copyright: 2-Clause BSD License

Macro Definition Documentation

◆ cxLinkedListCreateSimple

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

Allocates a linked list for storing elements with elem_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 elem_size is CX_STORE_POINTERS, the created list stores pointers instead of copies of the added elements and the compare function will be automatically set to cx_cmp_ptr().

Parameters

elem_size (size_t) the size of each element in bytes

Returns: (CxList*) 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 beginning 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	(	const void *	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	(	const void *	begin_left,
		const void *	begin_right,
		ptrdiff_t	loc_advance,
		ptrdiff_t	loc_data,
		cx_compare_func	cmp_func )

Compares two lists element wise.

Attention: Both list must have the same structure.

Parameters

begin_left	the beginning of the left list (`NULL` denotes an empty list)
begin_right	the beginning 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()

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

Finds the node containing 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
found_index	an optional pointer where the index of the found node (given that `start` has index 0) is stored

Returns: the index of the element, if found - unspecified if not found

◆ cx_linked_list_first()

void * cx_linked_list_first	(	const void *	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 beginning 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 inserted

◆ 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 beginning 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_insert_sorted()

void cx_linked_list_insert_sorted	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	new_node,
		cx_compare_func	cmp_func )

Inserts a node into a sorted linked list.

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

If the list starting with the node pointed to by begin is not sorted already, the behavior is undefined.

Parameters

begin	a pointer to the beginning node pointer (required)
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 inserted
cmp_func	a compare function that will receive the node pointers

◆ cx_linked_list_insert_sorted_chain()

void cx_linked_list_insert_sorted_chain	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	insert_begin,
		cx_compare_func	cmp_func )

Inserts a chain of nodes into a sorted linked list.

The chain must not be part of any list already.

If either the list starting with the node pointed to by begin or the list starting with insert_begin is not sorted, the behavior is undefined.

Attention: In contrast to cx_linked_list_insert_chain(), the source chain will be broken and inserted into the target list so that the resulting list will be sorted according to cmp_func. That means, each node in the source chain may be re-linked with nodes from the target list.

Parameters

begin	a pointer to the beginning node pointer (required)
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)
insert_begin	a pointer to the first node of the chain that shall be inserted
cmp_func	a compare function that will receive the node pointers

◆ cx_linked_list_last()

void * cx_linked_list_last	(	const void *	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 beginning 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	(	const void *	begin,
		ptrdiff_t	loc_next,
		const void *	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()

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

inlinestatic

Removes a node from the linked list.

If the node to remove is the beginning (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 beginning 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_remove_chain()

size_t cx_linked_list_remove_chain	(	void **	begin,
		void **	end,
		ptrdiff_t	loc_prev,
		ptrdiff_t	loc_next,
		void *	node,
		size_t	num )

Removes a chain of nodes from the linked list.

If one of the nodes to remove is the beginning (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 chain are not cleared by this function and may still be used to traverse to a former adjacent node in the list, or within the chain.

Parameters

begin	a pointer to the beginning 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 start node of the chain
num	the number of nodes to remove

Returns: the actual number of nodes that were removed (can be less when the list did not have enough nodes)

◆ 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 beginning 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	(	const void *	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 beginning 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	(	const CxAllocator *	allocator,
		cx_compare_func	comparator,
		size_t	elem_size )

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

If elem_size is CX_STORE_POINTERS, the created list stores pointers instead of copies of the added elements and the compare function will be automatically set to cx_cmp_ptr(), if none is given.

Parameters

allocator	the allocator for allocating the list nodes (if `NULL`, a default stdlib allocator will be used)
comparator	the comparator for the elements (if `NULL`, and the list is not storing pointers, sort and find functions will not work)
elem_size	the size of each element in bytes

Returns: the created list

Macros

Functions

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_insert_sorted()

◆ cx_linked_list_insert_sorted_chain()

◆ cx_linked_list_last()

◆ cx_linked_list_link()

◆ cx_linked_list_prepend()

◆ cx_linked_list_prev()

◆ cx_linked_list_remove()

◆ cx_linked_list_remove_chain()

◆ cx_linked_list_reverse()

◆ cx_linked_list_size()

◆ cx_linked_list_sort()

◆ cx_linked_list_unlink()

◆ cxLinkedListCreate()