The Singly Linked List Interface. More...

#include "impl/impl_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:

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	ccc_sll_init(list_name, struct_name, list_elem_field, alloc_fn, cmp_fn, aux_data)
	Initialize a singly linked list at compile or runtime.

Insert and Remove Interface
Add or remove elements from the container.
#define	ccc_sll_emplace_front(list_ptr, struct_initializer...) ccc_impl_sll_emplace_front(list_ptr, struct_initializer)
	Write a compound literal directly to allocated memory at the front. O(1).

void *	ccc_sll_push_front (ccc_singly_linked_list sll, ccc_sll_elem elem)
	Push the type wrapping elem to the front of the list. O(1).

ccc_result	ccc_sll_pop_front (ccc_singly_linked_list *sll)
	Pop the front element from the list. O(1).

ccc_result	ccc_sll_splice (ccc_singly_linked_list pos_sll, ccc_sll_elem pos, ccc_singly_linked_list splice_sll, ccc_sll_elem splice)
	Inserts splice element before pos. O(N).

ccc_result	ccc_sll_splice_range (ccc_singly_linked_list pos_sll, ccc_sll_elem pos, ccc_singly_linked_list splice_sll, ccc_sll_elem begin, ccc_sll_elem *end)
	Inserts the range of spliced elements before pos. O(N).

void *	ccc_sll_erase (ccc_singly_linked_list sll, ccc_sll_elem elem)
	Erases elem from the list returning the following element. O(N).

void *	ccc_sll_erase_range (ccc_singly_linked_list sll, ccc_sll_elem begin, ccc_sll_elem *end)
	Erases a range from the list returning the element after end. O(N).

void *	ccc_sll_extract (ccc_singly_linked_list sll, ccc_sll_elem elem)
	Extracts an element from the list without freeing it. O(N).

void *	ccc_sll_extract_range (ccc_singly_linked_list sll, ccc_sll_elem begin, ccc_sll_elem *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_sll_	ccc_singly_linked_list
	A low overhead front tracking container with efficient push and pop.

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

Deallocation Interface
Deallocate the container.
ccc_result	ccc_sll_clear (ccc_singly_linked_list sll, ccc_destructor_fn fn)
	Clears the list freeing memory if needed. O(N).

Iteration Interface
Iterate through the doubly linked list.
void *	ccc_sll_begin (ccc_singly_linked_list const *sll)
	Return the user type at the front of the list. O(1).

void *	ccc_sll_end (ccc_singly_linked_list const *sll)
	Return the sentinel at the end of the list. Do not access sentinel. O(1).

void *	ccc_sll_next (ccc_singly_linked_list const sll, ccc_sll_elem const elem)
	Return the user type following elem in the list. O(1).

State Interface
Obtain state from the doubly linked list.
void *	ccc_sll_front (ccc_singly_linked_list const *sll)
	Return a pointer to the element at the front of the list. O(1).

ccc_sll_elem *	ccc_sll_begin_elem (ccc_singly_linked_list const *sll)
	Return a pointer to the first intrusive handle in the list. O(1).

ccc_sll_elem *	ccc_sll_begin_sentinel (ccc_singly_linked_list const *sll)
	Return a pointer to the first list element in the list. O(1).

size_t	ccc_sll_size (ccc_singly_linked_list const *sll)
	Return the size of the list. O(1).

bool	ccc_sll_is_empty (ccc_singly_linked_list const *sll)
	Return true if the list is empty. O(1).

bool	ccc_sll_validate (ccc_singly_linked_list const *sll)
	Returns true if the invariants of the list hold.

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 doubly 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 doubly linked list. Review function documentation when unsure of the runtime of an sll operation.

This container offers pointer stability. Also, if the container is not permitted to allocate 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 allocation is permitted upon initialization the container will manage the memory as expected on insert or erase operations as defined by the interface; 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.

Macro Definition Documentation

◆ ccc_sll_emplace_front

#define ccc_sll_emplace_front	(	list_ptr,
		struct_initializer...
	)	ccc_impl_sll_emplace_front(list_ptr, struct_initializer)

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

Parameters

[in]	list_ptr	a pointer to the singly linked list.
[in]	struct_initializer	a compound literal containing the elements to be written to a newly allocated node.

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 allocation permission. Otherwise NULL is returned due to an inability for the container to allocate memory.

◆ ccc_sll_init

#define ccc_sll_init	(	list_name,
		struct_name,
		list_elem_field,
		alloc_fn,
		cmp_fn,
		aux_data
	)

Value:

ccc_impl_sll_init(list_name, struct_name, list_elem_field, alloc_fn, \

cmp_fn, aux_data)

Initialize a singly linked list at compile or runtime.

Parameters

[in]	list_name	the name the user has chosen for the list.
[in]	struct_name	the user type wrapping the intrusive sll elem.
[in]	list_elem_field	the name of the field in the user type storing the intrusive list elem.
[in]	alloc_fn	an allocation function if allocation is allowed.
[in]	cmp_fn	a comparison function for searching or sorting the list.
[in]	aux_data	a pointer to any auxiliary data needed for comparison or destruction.

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

Typedef Documentation

◆ ccc_singly_linked_list

typedef struct ccc_sll_ 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_sll_elem

typedef struct ccc_sll_elem_ ccc_sll_elem

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

void * ccc_sll_begin ( ccc_singly_linked_list const * sll )

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

Parameters

[in] sll 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 sll is NULL.

◆ ccc_sll_begin_elem()

ccc_sll_elem * ccc_sll_begin_elem ( ccc_singly_linked_list const * sll )

Return a pointer to the first intrusive handle in the list. O(1).

Parameters

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

Returns: a pointer to the first handle to a user type in the list or NULL if empty.

◆ ccc_sll_begin_sentinel()

ccc_sll_elem * ccc_sll_begin_sentinel ( ccc_singly_linked_list const * sll )

Return a pointer to the first list element in the list. O(1).

Parameters

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

Returns: a pointer to the first list element. This will never be NULL, even if the list is empty. If bad input is provided (sll is NULL) NULL is returned.

◆ ccc_sll_clear()

ccc_result ccc_sll_clear	(	ccc_singly_linked_list *	sll,
		ccc_destructor_fn *	fn
	)

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

Parameters

[in]	sll	a pointer to the singly linked list.
[in]	fn	a destructor function or NULL if not needed.

Returns: ok if the clear succeeded or an input error if sll or fn are NULL.

Note that if allocation is allowed, the container will free the user types wrapping each intrusive element in the list after calling fn. Therefore, fn should not free memory if the container has been given allocation permission. It should only perform other necessary cleanup or state management.

If allocation is not allowed fn may free memory or not as the user sees fit. The user is responsible for managing the memory that wraps each intrusive handle as the elements are simply removed from the list.

◆ ccc_sll_end()

void * ccc_sll_end ( ccc_singly_linked_list const * sll )

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

Parameters

[in] sll 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 sll is NULL.

◆ ccc_sll_erase()

void * ccc_sll_erase	(	ccc_singly_linked_list *	sll,
		ccc_sll_elem *	elem
	)

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

Parameters

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

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

Warning: elem 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_sll_erase_range()

void * ccc_sll_erase_range	(	ccc_singly_linked_list *	sll,
		ccc_sll_elem *	begin,
		ccc_sll_elem *	end
	)

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

Parameters

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

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

void * ccc_sll_extract	(	ccc_singly_linked_list *	sll,
		ccc_sll_elem *	elem
	)

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

Parameters

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

Returns: a pointer to the element following elem 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_sll_extract_range()

void * ccc_sll_extract_range	(	ccc_singly_linked_list *	sll,
		ccc_sll_elem *	begin,
		ccc_sll_elem *	end
	)

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

Parameters

[in]	sll	a pointer to the singly linked list.
[in]	begin	the start of the range in the list.
[in]	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_sll_front()

void * ccc_sll_front ( ccc_singly_linked_list const * sll )

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

Parameters

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

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

◆ ccc_sll_is_empty()

bool ccc_sll_is_empty ( ccc_singly_linked_list const * sll )

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

Parameters

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

Returns: true if the size is 0 or sll is NULL otherwise false.

◆ ccc_sll_next()

void * ccc_sll_next	(	ccc_singly_linked_list const *	sll,
		ccc_sll_elem const *	elem
	)

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

Parameters

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

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

◆ ccc_sll_pop_front()

ccc_result ccc_sll_pop_front ( ccc_singly_linked_list * sll )

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

Parameters

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

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

◆ ccc_sll_push_front()

void * ccc_sll_push_front	(	ccc_singly_linked_list *	sll,
		ccc_sll_elem *	elem
	)

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

Parameters

[in]	sll	a pointer to the singly linked list.
[in]	elem	a pointer to the intrusive handle in the user type.

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

Note that if allocation is not allowed 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_sll_size()

size_t ccc_sll_size ( ccc_singly_linked_list const * sll )

Return the size of the list. O(1).

Parameters

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

Returns: the size or 0 if the list is empty or sll is NULL.

◆ ccc_sll_splice()

ccc_result ccc_sll_splice	(	ccc_singly_linked_list *	pos_sll,
		ccc_sll_elem *	pos,
		ccc_singly_linked_list *	splice_sll,
		ccc_sll_elem *	splice
	)

Inserts splice element before pos. O(N).

Parameters

[in]	pos_sll	the list to which pos belongs.
[in]	pos	the position before which splice will be inserted.
[in]	splice_sll	the list to which splice belongs.
[in]	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 pos_sll and splice_sll may be the same or different lists and the invariants of each or the same list will be maintained by the function.

◆ ccc_sll_splice_range()

ccc_result ccc_sll_splice_range	(	ccc_singly_linked_list *	pos_sll,
		ccc_sll_elem *	pos,
		ccc_singly_linked_list *	splice_sll,
		ccc_sll_elem *	begin,
		ccc_sll_elem *	end
	)

Inserts the range of spliced elements before pos. O(N).

Parameters

[in]	pos_sll	the list to which pos belongs.
[in]	pos	the position before which the range will be inserted.
[in]	splice_sll	the list to which the range belongs.
[in]	begin	the start of the range.
[in]	end	the end of the range.

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

Warning: pos must not be inside of the range (begin, end) if pos_sll is the same list as splice_sll.

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

◆ ccc_sll_validate()

bool ccc_sll_validate ( ccc_singly_linked_list const * sll )

Returns true if the invariants of the list hold.

Parameters

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

Returns: true if the list is valid, else false.

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

Iteration Interface

State Interface

Detailed Description

Macro Definition Documentation

◆ ccc_sll_emplace_front

◆ ccc_sll_init

Typedef Documentation

◆ ccc_singly_linked_list

◆ ccc_sll_elem

Function Documentation

◆ ccc_sll_begin()

◆ ccc_sll_begin_elem()

◆ ccc_sll_begin_sentinel()

◆ ccc_sll_clear()

◆ ccc_sll_end()

◆ ccc_sll_erase()

◆ ccc_sll_erase_range()

◆ ccc_sll_extract()

◆ ccc_sll_extract_range()

◆ ccc_sll_front()

◆ ccc_sll_is_empty()

◆ ccc_sll_next()

◆ ccc_sll_pop_front()

◆ ccc_sll_push_front()

◆ ccc_sll_size()

◆ ccc_sll_splice()

◆ ccc_sll_splice_range()

◆ ccc_sll_validate()