#include "vl_fixed_pool.h"
#include "vl_compare.h"
#include "vl_memory.h"

Include dependency graph for vl_linked_list.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	vl_linked_list
	A doubly-linked list. More...

Macros
#define	VL_LIST_ITER_INVALID VL_FIXEDPOOL_INVALID_IDX

#define	VL_LIST_FOREACH(list, trackVar) for(vl_list_iter trackVar = (list)->head; (trackVar) != VL_LIST_ITER_INVALID; (trackVar) = vlListNext(list, trackVar))

#define	VL_LIST_FOREACH_REVERSE(list, trackVar) for(vl_list_iter trackVar = (list)->tail; (trackVar) != VL_LIST_ITER_INVALID; (trackVar) = vlListPrev(list, trackVar))

#define	vlListFree(listPtr) vlFixedPoolFree(&((listPtr)->nodePool))
	Frees the specified list instance.

#define	vlListSize(listPtr) (vl_dsidx_t)((listPtr)->length)
	Returns the total number of elements in the specified list.

#define	vlListReserve(listPtr, n) vlFixedPoolReserve(&((listPtr)->nodePool))
	Reserves space for n-many elements in the specified list.

#define	vlListClear(listPtr)
	Clears the specified list so it can be used as if it was just initialized.

Typedefs
typedef vl_fixedpool_idx	vl_list_iter
	List iterator type. Represents a location within a vl_linked_list.

Functions
void	vlListInit (vl_linked_list *list, vl_memsize_t elementSize)
	Initializes the specified list instance.

vl_linked_list *	vlListNew (vl_memsize_t elementSize)
	Allocates on the heap, initializes, and returns a list instance.

void	vlListDelete (vl_linked_list *list)
	Deletes the specified list instance.

vl_list_iter	vlListPushFront (vl_linked_list list, const void elem)
	Adds a new element to the front of the list.

void	vlListPopFront (vl_linked_list *list)
	Removes whatever element is at the front of the list.

vl_list_iter	vlListPushBack (vl_linked_list list, const void elem)
	Adds a new element to the end of the list.

void	vlListPopBack (vl_linked_list *list)
	Removes whatever element is at the end of the list.

vl_list_iter	vlListInsertAfter (vl_linked_list list, vl_list_iter target, const void elem)
	Inserts an element immediately after the specified target.

vl_list_iter	vlListInsertBefore (vl_linked_list list, vl_list_iter target, const void elem)
	Inserts an element immediately before the specified target.

vl_linked_list *	vlListClone (const vl_linked_list src, vl_linked_list dest)
	Clones the specified list to another.

int	vlListCopy (vl_linked_list src, vl_list_iter begin, vl_list_iter end, vl_linked_list dest, vl_list_iter after)
	Copies a range of elements from one list to another.

void	vlListSort (vl_linked_list *src, vl_compare_function cmp)
	Sorts the specified list in-place using the given comparator.

vl_list_iter	vlListFind (vl_linked_list src, const void element)
	Performs an iterative search on the specified list.

void	vlListRemove (vl_linked_list *list, vl_list_iter iter)
	Removes the specified element from the list.

vl_list_iter	vlListNext (vl_linked_list *list, vl_list_iter iter)
	Returns next adjacent iterator, or VL_LIST_ITER_INVALID if no such element exists.

vl_list_iter	vlListPrev (vl_linked_list *list, vl_list_iter iter)
	Returns the previous adjacent iterator, or VL_LIST_ITER_INVALID if no such element exists.

vl_transient *	vlListSample (vl_linked_list *list, vl_list_iter iter)
	Returns a pointer to the element data for the specified iterator.

Data Structure Documentation

◆ vl_linked_list

struct vl_linked_list

A doubly-linked list.

The vl_linked_list structure represents a doubly linked list with elements of a fixed size. This is implemented on top of vl_fixedpool, which is used to manage underlying memory. Due to using a pool, allocation should not occur frequently due to the larger pool of memory which is sliced into smaller pieces for individual nodes.

The vl_list_iter are simply vl_fixedpool indices, and thus, surrounding iterators are not invalidated when removing or inserting elements.

Pointers to list elements may never be invalidated due to using a fixed pool.

See also: vl_fixedpool

Collaboration diagram for vl_linked_list:

Data Fields
vl_memsize_t	elementSize
vl_list_iter	head
vl_dsidx_t	length
vl_fixedpool	nodePool
vl_list_iter	tail

Macro Definition Documentation

◆ VL_LIST_FOREACH

#define VL_LIST_FOREACH	(		list,
			trackVar ) for(vl_list_iter trackVar = (list)->head; (trackVar) != VL_LIST_ITER_INVALID; (trackVar) = vlListNext(list, trackVar))

This is a simple macro for iterating a list.

Parameters

list	pointer vl_list pointer
trackVar	identifier of the iterator. Always of type vl_list_iter.

See also: vl_list_iter

◆ VL_LIST_FOREACH_REVERSE

#define VL_LIST_FOREACH_REVERSE	(		list,
			trackVar ) for(vl_list_iter trackVar = (list)->tail; (trackVar) != VL_LIST_ITER_INVALID; (trackVar) = vlListPrev(list, trackVar))

This is a simple macro for iterating a list, in reverse.

Parameters

list	pointer vl_list pointer
trackVar	identifier of the iterator. Always of type vl_list_iter.

See also: vl_list_iter

◆ VL_LIST_ITER_INVALID

#define VL_LIST_ITER_INVALID VL_FIXEDPOOL_INVALID_IDX

◆ vlListClear

#define vlListClear ( listPtr )

Value:

(((listPtr)->head = (listPtr)->tail = VL_LIST_ITER_INVALID));\

vlFixedPoolClear(&((listPtr)->nodePool))

VL_LIST_ITER_INVALID

#define VL_LIST_ITER_INVALID

Definition vl_linked_list.h:8

Clears the specified list so it can be used as if it was just initialized.

This function does not touch any information in the underlying buffer, but rather resets some book-keeping variables.

Parameters

list pointer

Complexity of O(1) constant.

◆ vlListFree

#define vlListFree ( listPtr ) vlFixedPoolFree(&((listPtr)->nodePool))

Frees the specified list instance.

The specified list should be initialized via vlListInit.

See also: vlListInit

Parameters

list pointer

Complexity of O(1) constant.

◆ vlListReserve

#define vlListReserve	(		listPtr,
			n ) vlFixedPoolReserve(&((listPtr)->nodePool))

Reserves space for n-many elements in the specified list.

Parameters

list	pointer
n	number of elements to reserve space for.

◆ vlListSize

#define vlListSize ( listPtr ) (vl_dsidx_t)((listPtr)->length)

Returns the total number of elements in the specified list.

Parameters

list pointer

Complexity of O(1) constant.

Returns: total elements

Typedef Documentation

◆ vl_list_iter

typedef vl_fixedpool_idx vl_list_iter

List iterator type. Represents a location within a vl_linked_list.

Function Documentation

◆ vlListClone()

vl_linked_list * vlListClone	(	const vl_linked_list *	src,
		vl_linked_list *	dest )

Clones the specified list to another.

Clones the entirety of the src list to the dest list.

The 'src' list pointer must be non-null and initialized. The 'dest' list pointer may be null, but if it is not null it must be initialized.

If the 'dest' list pointer is null, a new list is created via vlListNew. Otherwise, its element size is set to the source's and all of its existing data is replaced.

Parameters

src
dest

Returns: pointer to list that was copied to or created.

Here is the call graph for this function:

◆ vlListCopy()

int vlListCopy	(	vl_linked_list *	src,
		vl_list_iter	begin,
		vl_list_iter	end,
		vl_linked_list *	dest,
		vl_list_iter	after )

Copies a range of elements from one list to another.

Both the src list and the dest list must have equivalent element sizes, otherwise this is a no-op.

This is an inclusive range, and as such, the elements referred to by the begin and end iterators are also copied to the target list.

The begin and end iterators are expected to be in logical iterative order, meaning that if iterating through the entire src list, begin would be found before end.

Parameters

src	source list pointer
begin	iterator to start the copy at, or VL_LIST_ITER_INVALID for the beginning of the list.
end	iterator to end the copy after, or VL_LIST_ITER_INVALID for the end of the list.
dest	destination buffer pointer
after	the iterator to insert elements after, or VL_LIST_ITER_INVALID for the end of the destination.

Complexity of O(n) linear.

Returns: number of elements copied

Here is the call graph for this function:

◆ vlListDelete()

void vlListDelete ( vl_linked_list * list )

Deletes the specified list instance.

The specified list should be created via vlListNew.

See also: vlListNew

Parameters

list pointer

Complexity of O(1) constant.

◆ vlListFind()

vl_list_iter vlListFind	(	vl_linked_list *	src,
		const void *	element )

Performs an iterative search on the specified list.

This will return an iterator to the first instance of the specified element that was found.

Returns VL_LIST_ITER_INVALID if the element could not be found.

Parameters

src	source list pointer
element	pointer to the element to compare against

Complexity of O(n) linear.

Returns: iterator to found element, or VL_LIST_ITER_INVALID on failure.

Here is the call graph for this function:

◆ vlListInit()

void vlListInit	(	vl_linked_list *	list,
		vl_memsize_t	elementSize )

Initializes the specified list instance.

The initialized list should be freed via vlListFree.

See also: vlListFree

Parameters

list	pointer
elementSize	size of a single list element, in bytes.

Complexity of O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlListInsertAfter()

vl_list_iter vlListInsertAfter	(	vl_linked_list *	list,
		vl_list_iter	target,
		const void *	elem )

Inserts an element immediately after the specified target.

Element data is copied to the internal pool allocator.

Parameters

list	pointer
target	iterator to element that will have something inserted after it.
elem	pointer

Complexity of O(1) constant.

Returns: iterator to inserted element.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlListInsertBefore()

vl_list_iter vlListInsertBefore	(	vl_linked_list *	list,
		vl_list_iter	target,
		const void *	elem )

Inserts an element immediately before the specified target.

Element data is copied to the internal pool allocator.

Parameters

list	pointer
target	iterator to element that will have something inserted before it.
elem

Complexity of O(1) constant.

Returns: iterator to inserted element.

Here is the call graph for this function:

◆ vlListNew()

vl_linked_list * vlListNew ( vl_memsize_t elementSize )

Allocates on the heap, initializes, and returns a list instance.

Parameters

elementSize size of a single list element, in bytes.

Complexity of O(1) constant.

Returns: pointer to created list

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlListNext()

vl_list_iter vlListNext	(	vl_linked_list *	list,
		vl_list_iter	iter )

Returns next adjacent iterator, or VL_LIST_ITER_INVALID if no such element exists.

See also: vlListPrev

Parameters

list	pointer
iter	node iterator

Complexity of O(1) constant.

Returns: next iterator, or VL_LIST_ITER_INVALID.

Here is the caller graph for this function:

◆ vlListPopBack()

void vlListPopBack ( vl_linked_list * list )

Removes whatever element is at the end of the list.

This is a no-op if the list is empty.

Parameters

list pointer

Complexity of O(1) constant.

Here is the call graph for this function:

◆ vlListPopFront()

void vlListPopFront ( vl_linked_list * list )

Removes whatever element is at the front of the list.

This is a no-op if the list is empty.

Parameters

list pointer

Complexity of O(1) constant.

Here is the call graph for this function:

◆ vlListPrev()

vl_list_iter vlListPrev	(	vl_linked_list *	list,
		vl_list_iter	iter )

Returns the previous adjacent iterator, or VL_LIST_ITER_INVALID if no such element exists.

See also: vlListPrev

Parameters

list	pointer
iter	node iterator

Complexity of O(1) constant.

Returns: previous iterator, or VL_LIST_ITER_INVALID.

◆ vlListPushBack()

vl_list_iter vlListPushBack	(	vl_linked_list *	list,
		const void *	elem )

Adds a new element to the end of the list.

Element data is copied to the internal pool allocator.

Parameters

list	pointer
elem	pointer to element data

Complexity of O(1) constant.

Returns: iterator referring to added element

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlListPushFront()

vl_list_iter vlListPushFront	(	vl_linked_list *	list,
		const void *	elem )

Adds a new element to the front of the list.

Element data is copied to the internal pool allocator.

Parameters

list	pointer
elem	pointer to element data

Complexity of O(1) constant.

Returns: iterator referring to added element

Here is the call graph for this function:

Here is the caller graph for this function:

◆ vlListRemove()

void vlListRemove	(	vl_linked_list *	list,
		vl_list_iter	iter )

Removes the specified element from the list.

The underlying node is returned to the underlying node pool for reuse, without modifying its discarded data.

Parameters

list	pointer
iter	node iterator.

Complexity of O(1) constant.

Here is the call graph for this function:

◆ vlListSample()

vl_transient * vlListSample	(	vl_linked_list *	list,
		vl_list_iter	iter )

Returns a pointer to the element data for the specified iterator.

Parameters

list	pointer
iter	node iterator

Complexity of O(1) constant.

Returns: pointer to element data.

Here is the caller graph for this function:

◆ vlListSort()

void vlListSort	(	vl_linked_list *	src,
		vl_compare_function	cmp )

Sorts the specified list in-place using the given comparator.

This function implements an iterative merge sort. Elements are not copied in this operation, but rather the links between them are modified.

The list is split into a "forest" in the underlying node pool, briefly holding a variety of sub-lists which are later merged back together.

Parameters

src	source list pointer
cmp	comparator function

Complexity of O(n log(n)).

Data Structures

Macros

Typedefs

Functions

Data Structure Documentation

◆ vl_linked_list

Macro Definition Documentation

◆ VL_LIST_FOREACH

◆ VL_LIST_FOREACH_REVERSE

◆ VL_LIST_ITER_INVALID

◆ vlListClear

◆ vlListFree

◆ vlListReserve

◆ vlListSize

Typedef Documentation

◆ vl_list_iter

Function Documentation

◆ vlListClone()

◆ vlListCopy()

◆ vlListDelete()

◆ vlListFind()

◆ vlListInit()

◆ vlListInsertAfter()

◆ vlListInsertBefore()

◆ vlListNew()

◆ vlListNext()

◆ vlListPopBack()

◆ vlListPopFront()

◆ vlListPrev()

◆ vlListPushBack()

◆ vlListPushFront()

◆ vlListRemove()

◆ vlListSample()

◆ vlListSort()