The Singly Linked List Interface. More...

#include "private/private_singly_linked_list.h"
#include "types.h"

Include dependency graph for singly_linked_list.h:

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

Detailed Description

The Singly Linked List Interface.

A singly linked list is well suited for list or stack structures that only need access to the front or most recently added elements. When compared to a singly linked list, the memory overhead per node is smaller but some operations will have O(N) runtime implications when compared to a similar operation in a singly linked list. Review function documentation when unsure of the runtime of an singly linked list operation. The linked list does not track internal state other than the head of the list and type information about the user type stored in the list. Therefore, be aware that obtaining the count of nodes is an O(N) operation. Determining if the list is empty, however, is O(1).

This container offers pointer stability. Also, if a user forgoes passing an allocator to a function that accepts one, all insertion code assumes that the user has allocated memory appropriately for the element to be inserted; it will not allocate or free in this case. If an allocator is passed to a function that accepts one, the container will manage the memory as expected on insert or erase operations as defined by the interface. In this case memory is allocated for insertions and freed for removals.

To shorten names in the interface, define the following preprocessor directive at the top of your file.

#define SINGLY_LINKED_LIST_USING_NAMESPACE_CCC

All types and functions can then be written without the CCC_ prefix.

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	CCC_singly_linked_list_default(type_name, type_intruder_field) CCC_private_singly_linked_list_for(type_name, type_intruder_field)
	Initialize a singly linked list at compile or runtime.

#define	CCC_singly_linked_list_for(type_name, type_intruder_field) CCC_private_singly_linked_list_for(type_name, type_intruder_field)
	Initialize a singly linked list at compile or runtime.

#define	CCC_singly_linked_list_from( type_intruder_field, allocator, destructor, compound_literal_array...)
	Initialize a singly linked list at runtime from a compound literal array.

Insert and Remove Interface
Add or remove elements from the container.
#define	CCC_singly_linked_list_emplace_front( list_pointer, allocator_pointer, type_compound_literal...)
	Write a compound literal directly to allocated memory at the front. O(1).

void *	CCC_singly_linked_list_push_front (CCC_Singly_linked_list list, CCC_Singly_linked_list_node type_intruder, CCC_Allocator const *allocator)
	Push the type wrapping type_intruder to the front of the list. O(1).

CCC_Result	CCC_singly_linked_list_pop_front (CCC_Singly_linked_list list, CCC_Allocator const allocator)
	Pop the front element from the list. O(1).

CCC_Result	CCC_singly_linked_list_splice (CCC_Singly_linked_list position_list, CCC_Singly_linked_list_node type_intruder_position, CCC_Singly_linked_list splice_list, CCC_Singly_linked_list_node type_intruder_splice)
	Inserts splice element after the provided position. O(N).

CCC_Result	CCC_singly_linked_list_splice_range (CCC_Singly_linked_list position_list, CCC_Singly_linked_list_node type_intruder_position, CCC_Singly_linked_list to_cut_list, CCC_Singly_linked_list_node type_intruder_to_cut_begin, CCC_Singly_linked_list_node *type_intruder_to_cut_exclusive_end)
	Inserts the `[begin, end)` of spliced elements after the provided position. `O(N)`.

void *	CCC_singly_linked_list_erase (CCC_Singly_linked_list list, CCC_Singly_linked_list_node type_intruder, CCC_Allocator const *allocator)
	Erases type_intruder from the list returning the following element. O(N).

void *	CCC_singly_linked_list_erase_range (CCC_Singly_linked_list list, CCC_Singly_linked_list_node type_intruder_begin, CCC_Singly_linked_list_node type_intruder_end, CCC_Allocator const allocator)
	Erases a range from the list returning the element after end. O(N).

void *	CCC_singly_linked_list_extract (CCC_Singly_linked_list list, CCC_Singly_linked_list_node type_intruder)
	Extracts an element from the list without freeing it. O(N).

void *	CCC_singly_linked_list_extract_range (CCC_Singly_linked_list list, CCC_Singly_linked_list_node type_intruder_begin, CCC_Singly_linked_list_node *type_intruder_end)
	Extracts a range of elements from the list without freeing them. O(N).

Container Types
Types available in the container interface.
typedef struct CCC_Singly_linked_list	CCC_Singly_linked_list
	A low overhead front tracking container with efficient push and pop.

typedef struct CCC_Singly_linked_list_node	CCC_Singly_linked_list_node
	A singly linked list intrusive element to embedded in a user type.

Sorting Interface
Sort the container.
void *	CCC_singly_linked_list_insert_sorted (CCC_Singly_linked_list singly_linked_list, CCC_Singly_linked_list_node type_intruder, CCC_Order order, CCC_Comparator const comparator, CCC_Allocator const allocator)
	Inserts type_intruder in sorted position according to the non-decreasing order of the list determined by the user provided comparison function. `O(1)`.

CCC_Tribool	CCC_singly_linked_list_is_sorted (CCC_Singly_linked_list const singly_linked_list, CCC_Order order, CCC_Comparator const comparator)
	Returns true if the list is sorted in non-decreasing order according to the user provided comparison function.

Deallocation Interface
Deallocate the container.
CCC_Result	CCC_singly_linked_list_clear (CCC_Singly_linked_list list, CCC_Destructor const destructor, CCC_Allocator const *allocator)
	Clears the list freeing memory if needed. O(N).

Iteration Interface
Iterate through the singly linked list.
void *	CCC_singly_linked_list_begin (CCC_Singly_linked_list const *list)
	Return the user type at the front of the list. O(1).

CCC_Singly_linked_list_node *	CCC_singly_linked_list_node_begin (CCC_Singly_linked_list const *list)
	Return the list node type at the front of the list. O(1).

CCC_Singly_linked_list_node *	CCC_singly_linked_list_node_before_begin (CCC_Singly_linked_list const *list)
	Return the list node type before the starting node. O(1).

void *	CCC_singly_linked_list_end (CCC_Singly_linked_list const *list)
	Return the sentinel at the end of the list. Do not access sentinel. O(1).

void *	CCC_singly_linked_list_next (CCC_Singly_linked_list const list, CCC_Singly_linked_list_node const type_intruder)
	Return the user type following type_intruder in the list. O(1).

State Interface
Obtain state from the singly linked list.
void *	CCC_singly_linked_list_front (CCC_Singly_linked_list const *list)
	Return a pointer to the element at the front of the list. O(1).

CCC_Count	CCC_singly_linked_list_count (CCC_Singly_linked_list const *list)
	Return the count of nodes in the list. O(N).

CCC_Tribool	CCC_singly_linked_list_is_empty (CCC_Singly_linked_list const *list)
	Return true if the list is empty. O(1).

CCC_Tribool	CCC_singly_linked_list_validate (CCC_Singly_linked_list const *list)
	Returns true if the invariants of the list hold.

Macro Definition Documentation

◆ CCC_singly_linked_list_default

#define CCC_singly_linked_list_default	(	type_name,
		type_intruder_field
	)	CCC_private_singly_linked_list_for(type_name, type_intruder_field)

Initialize a singly linked list at compile or runtime.

Parameters

[in]	type_name	the user type wrapping the intrusive singly_linked_list elem.
[in]	type_intruder_field	the name of the field in the user type storing the intrusive list elem.

Returns: a list metadata struct on the right hand side of equality operator.

◆ CCC_singly_linked_list_emplace_front

#define CCC_singly_linked_list_emplace_front	(	list_pointer,
		allocator_pointer,
		type_compound_literal...
	)

Value:

    CCC_private_singly_linked_list_emplace_front(                              \
        list_pointer, allocator_pointer, type_compound_literal                 \
    )

Write a compound literal directly to allocated memory at the front. O(1).

Parameters

[in]	list_pointer	a pointer to the singly linked list.
[in]	type_compound_literal	a compound literal containing the elements to be written to a newly allocated node.
[in]	allocator_pointer	a pointer to the required allocator.

Returns: a reference to the element pushed to the front or NULL if allocation failed.

Note that it only makes sense to use this method when the container is given an allocator to copy in the provided compound literal. If an empty allocator is provided NULL is returned due to an inability for the container to allocate memory.

◆ CCC_singly_linked_list_for

#define CCC_singly_linked_list_for	(	type_name,
		type_intruder_field
	)	CCC_private_singly_linked_list_for(type_name, type_intruder_field)

Initialize a singly linked list at compile or runtime.

Parameters

[in]	type_name	the user type wrapping the intrusive singly_linked_list elem.
[in]	type_intruder_field	the name of the field in the user type storing the intrusive list elem.

Returns: a stuct initializer for the singly linked list to be assigned (e.g. CCC_Singly_linked_list l = CCC_singly_linked_list_for(...);).

◆ CCC_singly_linked_list_from

#define CCC_singly_linked_list_from	(	type_intruder_field,
		allocator,
		destructor,
		compound_literal_array...
	)

Value:

    CCC_private_singly_linked_list_from(                                       \
        type_intruder_field, allocator, destructor, compound_literal_array     \
    )

Initialize a singly linked list at runtime from a compound literal array.

Parameters

[in]	type_intruder_field	the name of the field intruding on user's type.
[in]	allocator	the allocation function required for construction.
[in]	destructor	the optional destructor to run if insertion fails.
[in]	compound_literal_array	the array of user types to insert into the map (e.g. (struct My_type[]){ {.val = 1}, {.val = 2}}).

Returns: the initialized singly linked list on the right side of an equality operator.

Note: The list is constructed as specified in the compound literal array provided. The list will be constructed with the element at index 0 of the array as the front of the list and the final index element at the back of the list.

Typedef Documentation

◆ CCC_Singly_linked_list

typedef struct CCC_Singly_linked_list CCC_Singly_linked_list

A low overhead front tracking container with efficient push and pop.

A singly linked list may be stored in the stack, heap, or data segment. Once Initialized it is passed by reference to all functions. A singly linked list can be initialized at compile time or runtime.

◆ CCC_Singly_linked_list_node

typedef struct CCC_Singly_linked_list_node CCC_Singly_linked_list_node

A singly linked list intrusive element to embedded in a user type.

It can be used in an allocating or non allocating container. If allocation is prohibited the container assumes the element is wrapped in pre-allocated memory with the appropriate lifetime and scope for the user's needs; the container does not allocate or free in this case. If allocation is allowed the container will handle copying the data wrapping the element to allocations and deallocating when necessary.

Function Documentation

◆ CCC_singly_linked_list_begin()

void * CCC_singly_linked_list_begin ( CCC_Singly_linked_list const * list )

Return the user type at the front of the list. O(1).

Parameters

[in] list a pointer to the singly linked list.

Returns: a pointer to the user type at the start of the list or the end sentinel. NULL is returned if list is NULL.

◆ CCC_singly_linked_list_clear()

CCC_Result CCC_singly_linked_list_clear	(	CCC_Singly_linked_list *	list,
		CCC_Destructor const *	destructor,
		CCC_Allocator const *	allocator
	)

Clears the list freeing memory if needed. O(N).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	destructor	a CCC_Destructor to call on every element if needed.
[in]	allocator	a CCC_Allocator to to free memory if needed.

Returns: ok if the clear succeeded or an input error if list or destroy are NULL.

Note that if an allocator is allowed, the container will free the user types wrapping each intrusive element in the list after calling the destructor, if provided.

If an allocator is not provided the user is responsible for the behavior of the destructor and any memory management.

◆ CCC_singly_linked_list_count()

CCC_Count CCC_singly_linked_list_count ( CCC_Singly_linked_list const * list )

Return the count of nodes in the list. O(N).

Parameters

[in] list a pointer to the singly linked list.

Returns: the size or an argument error is set if list is NULL.

◆ CCC_singly_linked_list_end()

void * CCC_singly_linked_list_end ( CCC_Singly_linked_list const * list )

Return the sentinel at the end of the list. Do not access sentinel. O(1).

Parameters

[in] list a pointer to the singly linked list.

Returns: a pointer to the sentinel at the end of the list. It is undefined to access the sentinel. NULL is returned if list is NULL.

◆ CCC_singly_linked_list_erase()

void * CCC_singly_linked_list_erase	(	CCC_Singly_linked_list *	list,
		CCC_Singly_linked_list_node *	type_intruder,
		CCC_Allocator const *	allocator
	)

Erases type_intruder from the list returning the following element. O(N).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	type_intruder	a handle to the intrusive element known to be in the list.
[in]	allocator	the CCC_Allocator to free memory if needed.

Returns: a pointer to the element following type_intruder in the list or NULL if the list is empty or any bad input is provided to the function.

Warning: type_intruder must be in the list.

Note that if allocation permission is given to the container it will free the element. Otherwise, it is the user's responsibility to free the type wrapping elem.

◆ CCC_singly_linked_list_erase_range()

void * CCC_singly_linked_list_erase_range	(	CCC_Singly_linked_list *	list,
		CCC_Singly_linked_list_node *	type_intruder_begin,
		CCC_Singly_linked_list_node *	type_intruder_end,
		CCC_Allocator const *	allocator
	)

Erases a range from the list returning the element after end. O(N).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	type_intruder_begin	the start of the range in the list.
[in]	type_intruder_end	the exclusive end of the range in the list.
[in]	allocator	the CCC_Allocator to free memory if needed.

Returns: a pointer to the element following the range in the list or NULL if the list is empty or any bad input is provided to the function.

Warning: the provided range must be in the list.

Note that if allocation permission is given to the container it will free the elements in the range. Otherwise, it is the user's responsibility to free the types wrapping the range of elements.

◆ CCC_singly_linked_list_extract()

void * CCC_singly_linked_list_extract	(	CCC_Singly_linked_list *	list,
		CCC_Singly_linked_list_node *	type_intruder
	)

Extracts an element from the list without freeing it. O(N).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	type_intruder	a handle to the intrusive element known to be in the list.

Returns: a pointer to the element following type_intruder in the list.

Note that regardless of allocation permission this method will not free the type wrapping elem. It only removes it from the list.

◆ CCC_singly_linked_list_extract_range()

void * CCC_singly_linked_list_extract_range	(	CCC_Singly_linked_list *	list,
		CCC_Singly_linked_list_node *	type_intruder_begin,
		CCC_Singly_linked_list_node *	type_intruder_end
	)

Extracts a range of elements from the list without freeing them. O(N).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	type_intruder_begin	the start of the range in the list.
[in]	type_intruder_end	the exclusive end of the range in the list.

Returns: a pointer to the element following the range of elements in the list.

Note that the range remains in tact and can be iterated as one would iterate a normal list. However, insertions and removals from a range are not possible as they no longer belong to any list.

◆ CCC_singly_linked_list_front()

void * CCC_singly_linked_list_front ( CCC_Singly_linked_list const * list )

Return a pointer to the element at the front of the list. O(1).

Parameters

[in] list a pointer to the singly linked list.

Returns: a reference to the front element or NULL if empty or singly_linked_list is NULL.

◆ CCC_singly_linked_list_insert_sorted()

void * CCC_singly_linked_list_insert_sorted	(	CCC_Singly_linked_list *	singly_linked_list,
		CCC_Singly_linked_list_node *	type_intruder,
		CCC_Order	order,
		CCC_Comparator const *	comparator,
		CCC_Allocator const *	allocator
	)

Inserts type_intruder in sorted position according to the non-decreasing order of the list determined by the user provided comparison function. O(1).

Parameters

[in]	singly_linked_list	a pointer to the singly linked list.
[in]	type_intruder	a pointer to the element to be inserted in order.
[in]	order	the order by which the list should be sorted. CCC_ORDER_LESSER means the list should be in non-increasing order from [0, count). CCC_ORDER_GREATER means the list should be in non-decreasing order from [0, count).
[in]	comparator	a CCC_Comparator for comparing user elements.
[in]	allocator	an optional CCC_Allocator for allocating a new element.

Returns: a pointer to the element that has been inserted or NULL if allocation is required and has failed. NULL is also returned if the list has never been formally sorted from sort.h.

Warning: This function assumes the list is sorted and inserts according to the last sorted ordering. If the list has never been sorted NULL is returned.

If a non-increasing order is desired, return opposite results from the user comparison function. If an element is CCC_ORDER_LESSERERS return CCC_ORDER_GREATER and vice versa. If elements are equal, return CCC_ORDER_EQUAL.

◆ CCC_singly_linked_list_is_empty()

CCC_Tribool CCC_singly_linked_list_is_empty ( CCC_Singly_linked_list const * list )

Return true if the list is empty. O(1).

Parameters

[in] list a pointer to the singly linked list.

Returns: true if size is 0 otherwise false. Error returned if singly_linked_list is NULL.

◆ CCC_singly_linked_list_is_sorted()

CCC_Tribool CCC_singly_linked_list_is_sorted	(	CCC_Singly_linked_list const *	singly_linked_list,
		CCC_Order	order,
		CCC_Comparator const *	comparator
	)

Returns true if the list is sorted in non-decreasing order according to the user provided comparison function.

Parameters

[in]	singly_linked_list	a pointer to the singly linked list.
[in]	order	the assumed order checked against last sorted order of list.
[in]	comparator	the comparator context for comparing list elements.

Returns: CCC_TRUE if the list has been previously sorted and all elements remain in the assumed input sorted order. CCC_FALSE is returned if the list is not completely sorted in the assumed input order. CCC_TRIBOOL_ERROR is returned if the input list pointer is NULL.

If a non-increasing order is desired, return opposite results from the user comparison function. If an element is CCC_ORDER_LESSER return CCC_ORDER_GREATER and vice versa. If elements are equal, return CCC_ORDER_EQUAL.

◆ CCC_singly_linked_list_next()

void * CCC_singly_linked_list_next	(	CCC_Singly_linked_list const *	list,
		CCC_Singly_linked_list_node const *	type_intruder
	)

Return the user type following type_intruder in the list. O(1).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	type_intruder	a pointer to the intrusive handle known to be in the list.

Returns: the user type following type_intruder or the end sentinel if none follow. NULL is returned if list or type_intruder are NULL.

◆ CCC_singly_linked_list_node_before_begin()

CCC_Singly_linked_list_node * CCC_singly_linked_list_node_before_begin ( CCC_Singly_linked_list const * list )

Return the list node type before the starting node. O(1).

Parameters

[in] list a pointer to the singly linked list.

Returns: a pointer to the list node type at the start of the list or NULL if empty.

◆ CCC_singly_linked_list_node_begin()

CCC_Singly_linked_list_node * CCC_singly_linked_list_node_begin ( CCC_Singly_linked_list const * list )

Return the list node type at the front of the list. O(1).

Parameters

[in] list a pointer to the singly linked list.

Returns: a pointer to the list node type at the start of the list or NULL if empty.

◆ CCC_singly_linked_list_pop_front()

CCC_Result CCC_singly_linked_list_pop_front	(	CCC_Singly_linked_list *	list,
		CCC_Allocator const *	allocator
	)

Pop the front element from the list. O(1).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	allocator	the CCC_Allocator to free if needed.

Returns: ok if the list is non-empty and the pop is successful. An input error is returned if list is NULL or the list is empty.

◆ CCC_singly_linked_list_push_front()

void * CCC_singly_linked_list_push_front	(	CCC_Singly_linked_list *	list,
		CCC_Singly_linked_list_node *	type_intruder,
		CCC_Allocator const *	allocator
	)

Push the type wrapping type_intruder to the front of the list. O(1).

Parameters

[in]	list	a pointer to the singly linked list.
[in]	type_intruder	a pointer to the intrusive handle in the user type.
[in]	allocator	the CCC_Allocator for memory allocation if needed.

Returns: a pointer to the inserted element or NULL if allocation failed.

Note that if an allocator is not provided, the container assumes the memory wrapping elem has been allocated appropriately and with the correct lifetime by the user.

If allocation is allowed the provided element is copied to a new allocation.

◆ CCC_singly_linked_list_splice()

CCC_Result CCC_singly_linked_list_splice	(	CCC_Singly_linked_list *	position_list,
		CCC_Singly_linked_list_node *	type_intruder_position,
		CCC_Singly_linked_list *	splice_list,
		CCC_Singly_linked_list_node *	type_intruder_splice
	)

Inserts splice element after the provided position. O(N).

Parameters

[in]	position_list	the list to which position belongs.
[in]	type_intruder_position	the position after which splice will be inserted.
[in]	splice_list	the list to which splice belongs.
[in]	type_intruder_splice	the element to be moved before pos.

Returns: OK if the operations is successful. An input error is provided if any input pointers are NULL.

Note that position_list and splice_singly_linked_list may be the same or different lists and the invariants of each or the same list will be maintained by the function.

◆ CCC_singly_linked_list_splice_range()

CCC_Result CCC_singly_linked_list_splice_range	(	CCC_Singly_linked_list *	position_list,
		CCC_Singly_linked_list_node *	type_intruder_position,
		CCC_Singly_linked_list *	to_cut_list,
		CCC_Singly_linked_list_node *	type_intruder_to_cut_begin,
		CCC_Singly_linked_list_node *	type_intruder_to_cut_exclusive_end
	)

Inserts the [begin, end) of spliced elements after the provided position. O(N).

Parameters

[in]	position_list	the list to which position belongs.
[in]	type_intruder_position	the position after which the range will be inserted.
[in]	to_cut_list	the list to which the range belongs.
[in]	type_intruder_to_cut_begin	the start of the range.
[in]	type_intruder_to_cut_exclusive_end	the exclusive end of the range.

Returns: OK if the operations is successful. An input error is provided if any input pointers are NULL.

Warning: position must not be inside of the range [begin, end) if position_list is the same list as splice_singly_linked_list.

Note that position_list and splice_singly_linked_list may be the same or different lists and the invariants of each or the same list will be maintained by the function.

◆ CCC_singly_linked_list_validate()

CCC_Tribool CCC_singly_linked_list_validate ( CCC_Singly_linked_list const * list )

Returns true if the invariants of the list hold.

Parameters

[in] list a pointer to the singly linked list.

Returns: true if list is valid, else false. Error returned if singly_linked_list is NULL.

Detailed Description

Initialization Interface

Insert and Remove Interface

Container Types

Sorting Interface

Deallocation Interface

Iteration Interface

State Interface

Macro Definition Documentation

◆ CCC_singly_linked_list_default

◆ CCC_singly_linked_list_emplace_front

◆ CCC_singly_linked_list_for

◆ CCC_singly_linked_list_from

Typedef Documentation

◆ CCC_Singly_linked_list

◆ CCC_Singly_linked_list_node

Function Documentation

◆ CCC_singly_linked_list_begin()

◆ CCC_singly_linked_list_clear()

◆ CCC_singly_linked_list_count()

◆ CCC_singly_linked_list_end()

◆ CCC_singly_linked_list_erase()

◆ CCC_singly_linked_list_erase_range()

◆ CCC_singly_linked_list_extract()

◆ CCC_singly_linked_list_extract_range()

◆ CCC_singly_linked_list_front()

◆ CCC_singly_linked_list_insert_sorted()

◆ CCC_singly_linked_list_is_empty()

◆ CCC_singly_linked_list_is_sorted()

◆ CCC_singly_linked_list_next()

◆ CCC_singly_linked_list_node_before_begin()

◆ CCC_singly_linked_list_node_begin()

◆ CCC_singly_linked_list_pop_front()

◆ CCC_singly_linked_list_push_front()

◆ CCC_singly_linked_list_splice()

◆ CCC_singly_linked_list_splice_range()

◆ CCC_singly_linked_list_validate()