vl_linked_list.c File Reference

#include "vl_linked_list.h"
#include <memory.h>
#include <stdlib.h>

Include dependency graph for vl_linked_list.c:

Functions
void	vlListInit (vl_linked_list *list, vl_uint16_t elementSize)
	Initializes the specified list instance.
vl_linked_list *	vlListNew (vl_uint16_t elementSize)
	Allocates on the heap, initializes, and returns a new list instance.
void	vlListDelete (vl_linked_list *list)
	Deletes the specified list instance and its internal pool.
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 *list, vl_compare_function compareFunction)
	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.
void *	vlListSample (vl_linked_list *list, vl_list_iter iter)
	Returns a pointer to the element data for the specified iterator.

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, including all element data and order.

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.

Contract

• Ownership: If dest is NULL, the caller owns the returned vl_linked_list. If dest is provided, ownership remains with the caller.
• Lifetime: Valid until deleted or freed.
• Thread Safety: Not thread-safe.
• Nullability: src must not be NULL. dest can be NULL.
• Error Conditions: Returns NULL if allocation fails.
• Undefined Behavior: Passing an uninitialized list.
• Memory Allocation Expectations: Allocates a new list struct (if dest is NULL) and multiple nodes.
• Return-value Semantics: Returns the pointer to the cloned list, or NULL on failure.

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.

Contract

• Ownership: Unchanged. dest maintains copies of the elements.
• Lifetime: Unchanged.
• Thread Safety: Not thread-safe.
• Nullability: src and dest must not be NULL.
• Error Conditions: Returns 0 if element sizes do not match.
• Undefined Behavior: Passing iterators from the wrong list or in the wrong order.
• Memory Allocation Expectations: May trigger node pool expansion in dest.
• Return-value Semantics: Returns the total number of elements successfully copied.

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 and its internal pool.

The specified list should be created via vlListNew.

Contract

• Ownership: Releases ownership of the internal node pool and the vl_linked_list struct.
• Lifetime: The list pointer and all its iterators become invalid.
• Thread Safety: Not thread-safe.
• Nullability: Safe to call if list is NULL.
• Error Conditions: None.
• Undefined Behavior: Double deletion.
• Memory Allocation Expectations: Deallocates the internal node pool and the list struct.
• Return-value Semantics: None (void).

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 using the default comparator.

Contract

• Ownership: Unchanged.
• Lifetime: Unchanged.
• Thread Safety: Safe for concurrent reads if no other thread is writing.
• Nullability: src must not be NULL. element must not be NULL.
• Error Conditions: Returns VL_LIST_ITER_INVALID if the element is not found.
• Undefined Behavior: Passing an uninitialized list.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns a vl_list_iter to the found element, or VL_LIST_ITER_INVALID.

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_uint16_t	elementSize
	)

Initializes the specified list instance.

The initialized list should be freed via vlListFree.

Contract

• Ownership: The caller maintains ownership of the list struct. The function initializes the internal node pool.
• Lifetime: The list is valid until vlListFree or vlListDelete.
• Thread Safety: Not thread-safe. Concurrent access must be synchronized.
• Nullability: list must not be NULL.
• Error Conditions: None.
• Undefined Behavior: Passing an already initialized list without first calling vlListFree (causes memory leak).
• Memory Allocation Expectations: Initializes an internal vl_pool which allocates management structures.
• Return-value Semantics: None (void).

See also

vlListFree

Parameters

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

Complexity of O(1) constant.

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.

Contract

• Ownership: Unchanged. The list maintains a copy.
• Lifetime: Valid until removed.
• Thread Safety: Not thread-safe.
• Nullability: list must not be NULL. target must not be VL_LIST_ITER_INVALID. elem can be NULL.
• Error Conditions: Returns VL_LIST_ITER_INVALID if allocation fails.
• Undefined Behavior: Passing an invalid iterator or an iterator from a different list.
• Memory Allocation Expectations: May trigger pool expansion.
• Return-value Semantics: Returns a vl_list_iter handle to the new element, or VL_LIST_ITER_INVALID.

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.

Contract

• Ownership: Unchanged. The list maintains a copy.
• Lifetime: Valid until removed.
• Thread Safety: Not thread-safe.
• Nullability: Same as vlListInsertAfter.
• Error Conditions: Same as vlListInsertAfter.
• Undefined Behavior: Same as vlListInsertAfter.
• Memory Allocation Expectations: May trigger pool expansion.
• Return-value Semantics: Returns a vl_list_iter handle to the new element, or VL_LIST_ITER_INVALID.

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_uint16_t

elementSize

)

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

Contract

• Ownership: The caller owns the returned vl_linked_list pointer and is responsible for calling vlListDelete.
• Lifetime: The list is valid until vlListDelete.
• Thread Safety: Not thread-safe.
• Nullability: Returns NULL if heap allocation for the list struct fails.
• Error Conditions: Returns NULL on allocation failure.
• Undefined Behavior: None.
• Memory Allocation Expectations: Allocates memory for the vl_linked_list struct and its internal pool.
• Return-value Semantics: Returns a pointer to the new list, or NULL.

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.

Contract

• Ownership: None.
• Lifetime: The returned iterator is valid as long as the element is not removed.
• Thread Safety: Safe for concurrent reads.
• Nullability: list must not be NULL.
• Error Conditions: Returns VL_LIST_ITER_INVALID if no next element.
• Undefined Behavior: Passing an invalid iterator.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns the next vl_list_iter in the sequence.

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 call graph for this function:

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.

Contract

• Ownership: Releases ownership of the back element node.
• Lifetime: Iterators to the former back element become invalid.
• Thread Safety: Not thread-safe.
• Nullability: list must not be NULL.
• Error Conditions: None.
• Undefined Behavior: Passing an uninitialized list.
• Memory Allocation Expectations: None.
• Return-value Semantics: None (void).

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.

Contract

• Ownership: Releases ownership of the front element node back to the pool.
• Lifetime: Iterators to the former front element become invalid.
• Thread Safety: Not thread-safe.
• Nullability: list must not be NULL.
• Error Conditions: None.
• Undefined Behavior: Passing an uninitialized list.
• Memory Allocation Expectations: None (returns node to pool).
• Return-value Semantics: None (void).

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.

Contract

• Ownership: None.
• Lifetime: Same as vlListNext.
• Thread Safety: Same as vlListNext.
• Nullability: Same as vlListNext.
• Error Conditions: Returns VL_LIST_ITER_INVALID if no previous element.
• Undefined Behavior: Same as vlListNext.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns the previous vl_list_iter in the sequence.

See also

vlListPrev

Parameters

list	pointer
iter	node iterator

Complexity of O(1) constant.

Returns

previous iterator, or VL_LIST_ITER_INVALID.

Here is the call graph for this function:

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.

Contract

• Ownership: Unchanged. The list maintains a copy.
• Lifetime: Valid until removed.
• Thread Safety: Not thread-safe.
• Nullability: list must not be NULL. elem can be NULL.
• Error Conditions: Returns VL_LIST_ITER_INVALID if allocation fails.
• Undefined Behavior: Passing an uninitialized list.
• Memory Allocation Expectations: May trigger pool expansion.
• Return-value Semantics: Returns a vl_list_iter handle to the new element, or VL_LIST_ITER_INVALID.

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.

Contract

• Ownership: Does not transfer ownership of elem. The list maintains a copy.
• Lifetime: The returned iterator is valid until the element is removed or the list is cleared/destroyed.
• Thread Safety: Not thread-safe.
• Nullability: list must not be NULL. elem can be NULL (initializes with zero/garbage depending on pool implementation).
• Error Conditions: Returns VL_LIST_ITER_INVALID if node allocation fails.
• Undefined Behavior: Passing an uninitialized list.
• Memory Allocation Expectations: May trigger expansion of the underlying node pool.
• Return-value Semantics: Returns a vl_list_iter handle to the new element, or VL_LIST_ITER_INVALID on failure.

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.

Contract

• Ownership: Releases ownership of the node back to the pool.
• Lifetime: The passed iterator becomes invalid.
• Thread Safety: Not thread-safe.
• Nullability: list must not be NULL. iter should not be VL_LIST_ITER_INVALID.
• Error Conditions: None.
• Undefined Behavior: Passing an invalid iterator or an iterator from a different list.
• Memory Allocation Expectations: None.
• Return-value Semantics: None (void).

Parameters

list	pointer
iter	node iterator.

Complexity of O(1) constant.

Here is the call graph for this function:

vlListSample()

void * vlListSample	(	vl_linked_list *	list,
		vl_list_iter	iter
	)

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

Contract

• Ownership: Ownership remains with the list. The caller must not free the returned pointer.
• Lifetime: The returned pointer is valid until the element is removed or the list is reallocated/destroyed.
• Thread Safety: Safe for concurrent reads.
• Nullability: Returns NULL if iter is VL_LIST_ITER_INVALID.
• Error Conditions: None.
• Undefined Behavior: Passing an invalid iterator.
• Memory Allocation Expectations: None.
• Return-value Semantics: Returns a pointer to the raw element data.

Parameters

list	pointer
iter	node iterator

Complexity of O(1) constant.

Returns

pointer to element data.

Here is the call graph for this function:

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.

Contract

• Ownership: Unchanged. Nodes are rearranged but stay in the same list and pool.
• Lifetime: All existing iterators remain valid but their logical order in the list may change.
• Thread Safety: Not thread-safe.
• Nullability: list and cmp must not be NULL.
• Error Conditions: None.
• Undefined Behavior: Passing a NULL comparator or an uninitialized list.
• Memory Allocation Expectations: None.
• Return-value Semantics: None (void).

Parameters

src	source list pointer
cmp	comparator function

Complexity of O(n log(n)).

Here is the call graph for this function: