The Doubly Linked List Interface. More...

#include "impl/impl_doubly_linked_list.h"
#include "types.h"

Include dependency graph for doubly_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_dll_init(list_name, struct_name, list_elem_field, alloc_fn, cmp_fn, aux_data)
	Initialize a doubly linked list with its l-value name, type containing the dll elems, the field of the dll elem, allocation function, compare function and any auxilliary data needed for comparison, printing, or destructors.

Insert and Remove Interface
Add or remove elements from the doubly linked list.
#define	ccc_dll_emplace_back(list_ptr, type_initializer...) ccc_impl_dll_emplace_back(list_ptr, type_initializer)
	writes contents of type initializer directly to allocated memory at the back of the list. O(1).

#define	ccc_dll_emplace_front(list_ptr, type_initializer...) ccc_impl_dll_emplace_front(list_ptr, type_initializer)
	writes contents of type initializer directly to allocated memory at the front of the list. O(1).

void *	ccc_dll_push_front (ccc_doubly_linked_list l, ccc_dll_elem elem)
	Push user type wrapping elem to the front of the list. O(1).

void *	ccc_dll_push_back (ccc_doubly_linked_list l, ccc_dll_elem elem)
	Push user type wrapping elem to the back of the list. O(1).

void *	ccc_dll_insert (ccc_doubly_linked_list l, ccc_dll_elem pos_elem, ccc_dll_elem *elem)
	Insert user type wrapping elem before pos_elem. O(1).

ccc_result	ccc_dll_pop_front (ccc_doubly_linked_list *l)
	Pop the user type at the front of the list. O(1).

ccc_result	ccc_dll_pop_back (ccc_doubly_linked_list *l)
	Pop the user type at the back of the list. O(1).

void *	ccc_dll_extract (ccc_doubly_linked_list l, ccc_dll_elem elem)
	Returns the element following an extracted element from the list without deallocating regardless of allocation permission provided to the container. O(1).

void *	ccc_dll_erase (ccc_doubly_linked_list l, ccc_dll_elem elem)
	Returns the element following an erased element from the list. O(1).

void *	ccc_dll_erase_range (ccc_doubly_linked_list l, ccc_dll_elem elem_begin, ccc_dll_elem *elem_end)
	Returns the element following an extracted range of elements from the list. O(N).

void *	ccc_dll_extract_range (ccc_doubly_linked_list l, ccc_dll_elem elem_begin, ccc_dll_elem *elem_end)
	Returns the element following an extracted range of elements from the list without deallocating regardless of allocation permission provided to the container. O(N).

ccc_result	ccc_dll_splice (ccc_doubly_linked_list pos_sll, ccc_dll_elem pos, ccc_doubly_linked_list to_cut_sll, ccc_dll_elem to_cut)
	Repositions to_cut before pos. Only list pointers are modified. O(1).

ccc_result	ccc_dll_splice_range (ccc_doubly_linked_list pos_sll, ccc_dll_elem pos, ccc_doubly_linked_list to_cut_sll, ccc_dll_elem begin, ccc_dll_elem *end)
	Repositions begin to end before pos. Only list pointers are modified O(N).

Container Types
Types available in the container interface.
typedef struct ccc_dll_	ccc_doubly_linked_list
	A container offering bidirectional, insert, removal, and iteration.

typedef struct ccc_dll_elem_	ccc_dll_elem
	A doubly linked list intrusive element to embedded in a user type.

Deallocation Interface
Deallocate the container.
ccc_result	ccc_dll_clear (ccc_doubly_linked_list l, ccc_destructor_fn fn)
	Clear the contents of the list freeing elements, if given allocation permission. O(N).

Iteration Interface
Iterate through the doubly linked list.
void *	ccc_dll_begin (ccc_doubly_linked_list const *l)
	Return the user type at the start of the list or NULL if empty. O(1).

void *	ccc_dll_rbegin (ccc_doubly_linked_list const *l)
	Return the user type at the end of the list or NULL if empty. O(1).

void *	ccc_dll_next (ccc_doubly_linked_list const l, ccc_dll_elem const elem)
	Return the user type following the element known to be in the list. O(1).

void *	ccc_dll_rnext (ccc_doubly_linked_list const l, ccc_dll_elem const elem)
	Return the user type following the element known to be in the list moving from back to front. O(1).

void *	ccc_dll_end (ccc_doubly_linked_list const *l)
	Return the end sentinel with no accessible fields. O(1).

void *	ccc_dll_rend (ccc_doubly_linked_list const *l)
	Return the start sentinel with no accessible fields. O(1).

State Interface
Obtain state from the doubly linked list.
void *	ccc_dll_front (ccc_doubly_linked_list const *l)
	Returns the user type at the front of the list. O(1).

void *	ccc_dll_back (ccc_doubly_linked_list const *l)
	Returns the user type at the back of the list. O(1).

ccc_dll_elem *	ccc_dll_begin_elem (ccc_doubly_linked_list const *l)
	Return a handle to the list element at the front of the list which may be the sentinel. O(1).

ccc_dll_elem *	ccc_dll_end_elem (ccc_doubly_linked_list const *l)
	Return a handle to the list element at the back of the list which may be the sentinel. O(1).

ccc_dll_elem *	ccc_dll_end_sentinel (ccc_doubly_linked_list const *l)
	Return a handle to the sentinel at the back of the list. O(1).

size_t	ccc_dll_size (ccc_doubly_linked_list const *l)
	Return the size of the list. O(1).

bool	ccc_dll_is_empty (ccc_doubly_linked_list const *l)
	Return if the size of the list is equal to 0. O(1).

bool	ccc_dll_validate (ccc_doubly_linked_list const *l)
	Validates internal state of the list.

Detailed Description

The Doubly Linked List Interface.

A doubly linked list offers efficient push, pop, extract, and erase operations for elements stored in the list. Notably, for single elements the list can offer O(1) push front/back, pop front/back, and removal of elements in arbitrary positions in the list. The cost of this efficiency is higher memory footprint.

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 DOUBLY_LINKED_LIST_USING_NAMESPACE_CCC

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

Macro Definition Documentation

◆ ccc_dll_emplace_back

#define ccc_dll_emplace_back	(	list_ptr,
		type_initializer...
	)	ccc_impl_dll_emplace_back(list_ptr, type_initializer)

writes contents of type initializer directly to allocated memory at the back of the list. O(1).

Parameters

[in]	list_ptr	the address of the doubly linked list.
[in]	type_initializer	the r-value initializer of the type to be inserted in the list. This should match the type containing dll elements as a struct member for this list.

Returns: a reference to the inserted element or NULL if allocation is not allowed or fails.

Note that it does not make sense to use this method if the list has been initialized without an allocation function. If the user does not allow allocation, the contents of new elements to be inserted has been determined by the user prior to any inserts into the list.

◆ ccc_dll_emplace_front

#define ccc_dll_emplace_front	(	list_ptr,
		type_initializer...
	)	ccc_impl_dll_emplace_front(list_ptr, type_initializer)

writes contents of type initializer directly to allocated memory at the front of the list. O(1).

Parameters

[in]	list_ptr	the address of the doubly linked list.
[in]	type_initializer	the r-value initializer of the type to be inserted in the list. This should match the type containing dll elements as a struct member for this list.

Returns: a reference to the inserted element or NULL if allocation is not allowed or fails.

Note that it does not make sense to use this method if the list has been initialized without an allocation function. If the user does not allow allocation, the contents of new elements to be inserted has been determined by the user prior to any inserts into the list.

◆ ccc_dll_init

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

Value:

ccc_impl_dll_init(list_name, struct_name, list_elem_field, alloc_fn, \

cmp_fn, aux_data)

Initialize a doubly linked list with its l-value name, type containing the dll elems, the field of the dll elem, allocation function, compare function and any auxilliary data needed for comparison, printing, or destructors.

Parameters

[in]	list_name	the name of the list being initialized.
[in]	struct_name	the type containing the intrusive dll element.
[in]	list_elem_field	name of the dll element in the containing type.
[in]	alloc_fn	the optional allocation function or NULL.
[in]	cmp_fn	the ccc_cmp_fn used to compare list elements.
[in]	aux_data	any auxilliary data that will be needed for comparison, printing, or destruction of elements.

Returns: the initialized list. Assign to the list directly on the right hand side of an equality operator. Initialization can occur at runtime or compile time (e.g. ccc_doubly_linked l = ccc_dll_init(...);).

Typedef Documentation

◆ ccc_dll_elem

typedef struct ccc_dll_elem_ ccc_dll_elem

A doubly 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.

◆ ccc_doubly_linked_list

typedef struct ccc_dll_ ccc_doubly_linked_list

A container offering bidirectional, insert, removal, and iteration.

Warning: it is undefined behavior to use an uninitialized container.

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

Function Documentation

◆ ccc_dll_back()

void * ccc_dll_back ( ccc_doubly_linked_list const * l )

Returns the user type at the back of the list. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the user type at the back of the list. NULL if empty.

◆ ccc_dll_begin()

void * ccc_dll_begin ( ccc_doubly_linked_list const * l )

Return the user type at the start of the list or NULL if empty. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the user type or NULL if empty or bad input.

◆ ccc_dll_begin_elem()

ccc_dll_elem * ccc_dll_begin_elem ( ccc_doubly_linked_list const * l )

Return a handle to the list element at the front of the list which may be the sentinel. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the list element at the beginning of the list which may be the sentinel but will not be NULL unless a NULL pointer is provided as l.

◆ ccc_dll_clear()

ccc_result ccc_dll_clear	(	ccc_doubly_linked_list *	l,
		ccc_destructor_fn *	fn
	)

Clear the contents of the list freeing elements, if given allocation permission. O(N).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	fn	a destructor function to run on each element.

Returns: ok if the clearing was a success or an input error if l or fn is NULL.

Note that if the list is initialized with allocation permission it will free elements for the user and the destructor function should only perform auxiliary cleanup, otherwise a double free will occur.

If the list has not been given allocation permission the user should free the list elements with the destructor if they wish to do so. The implementation ensures the function is called after the element is removed. Otherwise, the user must manage their elements at their discretion after the list is emptied in this function.

◆ ccc_dll_end()

void * ccc_dll_end ( ccc_doubly_linked_list const * l )

Return the end sentinel with no accessible fields. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the end sentinel with no accessible fields.

◆ ccc_dll_end_elem()

ccc_dll_elem * ccc_dll_end_elem ( ccc_doubly_linked_list const * l )

Return a handle to the list element at the back of the list which may be the sentinel. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the list element at the end of the list which may be the sentinel but will not be NULL unless a NULL pointer is provided as l.

◆ ccc_dll_end_sentinel()

ccc_dll_elem * ccc_dll_end_sentinel ( ccc_doubly_linked_list const * l )

Return a handle to the sentinel at the back of the list. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the sentinel at the end of the list which will not be NULL unless a NULL pointer is provided as l.

◆ ccc_dll_erase()

void * ccc_dll_erase	(	ccc_doubly_linked_list *	l,
		ccc_dll_elem *	elem
	)

Returns the element following an erased element from the list. O(1).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem	the handle of an element known to be in the list.

Returns: a reference to the element in the list following elem or NULL if the element is the last. NULL is returned if bad input is provided or the elem is not in the list.

◆ ccc_dll_erase_range()

void * ccc_dll_erase_range	(	ccc_doubly_linked_list *	l,
		ccc_dll_elem *	elem_begin,
		ccc_dll_elem *	elem_end
	)

Returns the element following an extracted range of elements from the list. O(N).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem_begin	the handle of an element known to be in the list at the start of the range.
[in]	elem_end	the handle of an element known to be in the list at the end of the range following elem_begin.

Returns: a reference to the element in the list following elem_end or NULL if the element is the last. NULL is returned if bad input is provided or the elem is not in the list.

Note that if the user does not permit the container to allocate they may iterate through the extracted range in the same way one iterates through a normal list using the iterator function. If allocation is allowed, all elements from elem_begin to elem_end will be erased and references invalidated.

◆ ccc_dll_extract()

void * ccc_dll_extract	(	ccc_doubly_linked_list *	l,
		ccc_dll_elem *	elem
	)

Returns the element following an extracted element from the list without deallocating regardless of allocation permission provided to the container. O(1).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem	the handle of an element known to be in the list.

Returns: a reference to the element in the list following elem or NULL if the element is the last. NULL is returned if bad input is provided or the elem is not in the list.

◆ ccc_dll_extract_range()

void * ccc_dll_extract_range	(	ccc_doubly_linked_list *	l,
		ccc_dll_elem *	elem_begin,
		ccc_dll_elem *	elem_end
	)

Returns the element following an extracted range of elements from the list without deallocating regardless of allocation permission provided to the container. O(N).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem_begin	the handle of an element known to be in the list at the start of the range.
[in]	elem_end	the handle of an element known to be in the list at the end of the range following elem_begin.

Returns: a reference to the element in the list following elem_end or NULL if the element is the last. NULL is returned if bad input is provided or the elem is not in the list.

Note that the user may iterate through the extracted range in the same way one iterates through a normal list using the iterator function.

◆ ccc_dll_front()

void * ccc_dll_front ( ccc_doubly_linked_list const * l )

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

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the user type at the front of the list. NULL if empty.

◆ ccc_dll_insert()

void * ccc_dll_insert	(	ccc_doubly_linked_list *	l,
		ccc_dll_elem *	pos_elem,
		ccc_dll_elem *	elem
	)

Insert user type wrapping elem before pos_elem. O(1).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	pos_elem	a pointer to the list element before which elem inserts.
[in]	elem	a pointer to the list element.

Returns: a pointer to the element inserted or NULL if bad input is provided or allocation fails.

◆ ccc_dll_is_empty()

bool ccc_dll_is_empty ( ccc_doubly_linked_list const * l )

Return if the size of the list is equal to 0. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: true if the size is 0 or l is NULL, else false.

◆ ccc_dll_next()

void * ccc_dll_next	(	ccc_doubly_linked_list const *	l,
		ccc_dll_elem const *	elem
	)

Return the user type following the element known to be in the list. O(1).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem	a handle to the list element known to be in the list.

Returns: a pointer to the element following elem or NULL if no elements follow or bad input is provided.

◆ ccc_dll_pop_back()

ccc_result ccc_dll_pop_back ( ccc_doubly_linked_list * l )

Pop the user type at the back of the list. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: an ok result if the pop was successful or an error if bad input is provided or the list is empty.

◆ ccc_dll_pop_front()

ccc_result ccc_dll_pop_front ( ccc_doubly_linked_list * l )

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

Parameters

[in] l a pointer to the doubly linked list.

Returns: an ok result if the pop was successful or an error if bad input is provided or the list is empty.

◆ ccc_dll_push_back()

void * ccc_dll_push_back	(	ccc_doubly_linked_list *	l,
		ccc_dll_elem *	elem
	)

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

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem	a pointer to the list element.

Returns: a pointer to the element inserted or NULL if bad input is provided or allocation fails.

◆ ccc_dll_push_front()

void * ccc_dll_push_front	(	ccc_doubly_linked_list *	l,
		ccc_dll_elem *	elem
	)

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

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem	a pointer to the list element.

Returns: a pointer to the element inserted or NULL if bad input is provided or allocation fails.

◆ ccc_dll_rbegin()

void * ccc_dll_rbegin ( ccc_doubly_linked_list const * l )

Return the user type at the end of the list or NULL if empty. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the user type or NULL if empty or bad input.

◆ ccc_dll_rend()

void * ccc_dll_rend ( ccc_doubly_linked_list const * l )

Return the start sentinel with no accessible fields. O(1).

Parameters

[in] l a pointer to the doubly linked list.

Returns: a pointer to the start sentinel with no accessible fields.

◆ ccc_dll_rnext()

void * ccc_dll_rnext	(	ccc_doubly_linked_list const *	l,
		ccc_dll_elem const *	elem
	)

Return the user type following the element known to be in the list moving from back to front. O(1).

Parameters

[in]	l	a pointer to the doubly linked list.
[in]	elem	a handle to the list element known to be in the list.

Returns: a pointer to the element following elem from back to front or NULL if no elements follow or bad input is provided.

◆ ccc_dll_size()

size_t ccc_dll_size ( ccc_doubly_linked_list const * l )

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

Parameters

[in] l a pointer to the doubly linked list.

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

◆ ccc_dll_splice()

ccc_result ccc_dll_splice	(	ccc_doubly_linked_list *	pos_sll,
		ccc_dll_elem *	pos,
		ccc_doubly_linked_list *	to_cut_sll,
		ccc_dll_elem *	to_cut
	)

Repositions to_cut before pos. Only list pointers are modified. O(1).

Parameters

[in]	pos_sll	the list to which pos belongs.
[in]	pos	the position before which to_cut will be moved.
[in]	to_cut_sll	the list to which to_cut belongs.
[in]	to_cut	the element to cut.

Returns: ok if the splice is successful or an error if bad input is provided.

◆ ccc_dll_splice_range()

ccc_result ccc_dll_splice_range	(	ccc_doubly_linked_list *	pos_sll,
		ccc_dll_elem *	pos,
		ccc_doubly_linked_list *	to_cut_sll,
		ccc_dll_elem *	begin,
		ccc_dll_elem *	end
	)

Repositions begin to end before pos. Only list pointers are modified O(N).

Parameters

[in]	pos_sll	the list to which pos belongs.
[in]	pos	the position before which to_cut will be moved.
[in]	to_cut_sll	the list to which the range belongs.
[in]	begin	the start of the list to splice.
[in]	end	the end of the list to splice.

Returns: ok if the splice is successful or an error if bad input is provided.

◆ ccc_dll_validate()

bool ccc_dll_validate ( ccc_doubly_linked_list const * l )

Validates internal state of the list.

Parameters

[in] l a pointer to the doubly linked list.

Returns: true if invariants hold, false if not.

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

Iteration Interface

State Interface

Detailed Description

Macro Definition Documentation

◆ ccc_dll_emplace_back

◆ ccc_dll_emplace_front

◆ ccc_dll_init

Typedef Documentation

◆ ccc_dll_elem

◆ ccc_doubly_linked_list

Function Documentation

◆ ccc_dll_back()

◆ ccc_dll_begin()

◆ ccc_dll_begin_elem()

◆ ccc_dll_clear()

◆ ccc_dll_end()

◆ ccc_dll_end_elem()

◆ ccc_dll_end_sentinel()

◆ ccc_dll_erase()

◆ ccc_dll_erase_range()

◆ ccc_dll_extract()

◆ ccc_dll_extract_range()

◆ ccc_dll_front()

◆ ccc_dll_insert()

◆ ccc_dll_is_empty()

◆ ccc_dll_next()

◆ ccc_dll_pop_back()

◆ ccc_dll_pop_front()

◆ ccc_dll_push_back()

◆ ccc_dll_push_front()

◆ ccc_dll_rbegin()

◆ ccc_dll_rend()

◆ ccc_dll_rnext()

◆ ccc_dll_size()

◆ ccc_dll_splice()

◆ ccc_dll_splice_range()

◆ ccc_dll_validate()