The Doubly Linked List Interface. More...

#include "private/private_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:

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. 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. The linked list does not track internal state other than the head and tail 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 the container function requesting an allocator is not provided 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 requesting one, 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.

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	CCC_doubly_linked_list_default(type_name, type_intruder_field) CCC_private_doubly_linked_list_for(type_name, type_intruder_field)
	Initialize an intrusive doubly linked list for a type with a user specified intruder field.

#define	CCC_doubly_linked_list_for(type_name, type_intruder_field) CCC_private_doubly_linked_list_for(type_name, type_intruder_field)
	Initialize an intrusive doubly linked list for a type with a user specified intruder field.

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

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

#define	CCC_doubly_linked_list_emplace_front( list_pointer, allocator_pointer, type_compound_literal...)
	writes contents of type initializer directly to allocated memory at the front of the list. O(1).

void *	CCC_doubly_linked_list_push_front (CCC_Doubly_linked_list list, CCC_Doubly_linked_list_node type_intruder, CCC_Allocator const *allocator)
	Push user type wrapping type_intruder to the front of the list. O(1).

void *	CCC_doubly_linked_list_push_back (CCC_Doubly_linked_list list, CCC_Doubly_linked_list_node type_intruder, CCC_Allocator const *allocator)
	Push user type wrapping type_intruder to the back of the list. O(1).

void *	CCC_doubly_linked_list_insert (CCC_Doubly_linked_list list, CCC_Doubly_linked_list_node position_node, CCC_Doubly_linked_list_node type_intruder, CCC_Allocator const allocator)
	Insert user type wrapping type_intruder before position_node. O(1).

CCC_Result	CCC_doubly_linked_list_pop_front (CCC_Doubly_linked_list list, CCC_Allocator const allocator)
	Pop the user type at the front of the list. O(1).

CCC_Result	CCC_doubly_linked_list_pop_back (CCC_Doubly_linked_list list, CCC_Allocator const allocator)
	Pop the user type at the back of the list. O(1).

void *	CCC_doubly_linked_list_extract (CCC_Doubly_linked_list list, CCC_Doubly_linked_list_node type_intruder)
	Returns the element following an extracted element from the list without deallocating regardless of allocation permission provided to the container. O(1).

void *	CCC_doubly_linked_list_erase (CCC_Doubly_linked_list list, CCC_Doubly_linked_list_node type_intruder, CCC_Allocator const *allocator)
	Returns the element following an erased element from the list. O(1).

void *	CCC_doubly_linked_list_erase_range (CCC_Doubly_linked_list list, CCC_Doubly_linked_list_node type_intruder_begin, CCC_Doubly_linked_list_node type_intruder_end, CCC_Allocator const allocator)
	Returns the element following an extracted range of elements from the list. O(N).

void *	CCC_doubly_linked_list_extract_range (CCC_Doubly_linked_list list, CCC_Doubly_linked_list_node type_intruder_begin, CCC_Doubly_linked_list_node *type_intruder_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_doubly_linked_list_splice (CCC_Doubly_linked_list position_doubly_linked_list, CCC_Doubly_linked_list_node type_intruder_position, CCC_Doubly_linked_list to_cut_doubly_linked_list, CCC_Doubly_linked_list_node type_intruder_to_cut)
	Repositions to_cut before pos. Only list pointers are modified. O(1).

CCC_Result	CCC_doubly_linked_list_splice_range (CCC_Doubly_linked_list position_doubly_linked_list, CCC_Doubly_linked_list_node type_intruder_position, CCC_Doubly_linked_list to_cut_doubly_linked_list, CCC_Doubly_linked_list_node type_intruder_to_cut_begin, CCC_Doubly_linked_list_node *type_intruder_to_cut_exclusive_end)
	Splices the list to cut before the specified position. The range being cut is exclusive from [start, end), meaning the final element provided is not move. This is an O(N) operation.

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

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

Sorting Interface
Sort the container.
void *	CCC_doubly_linked_list_insert_sorted (CCC_Doubly_linked_list doubly_linked_list, CCC_Doubly_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_doubly_linked_list_is_sorted (CCC_Doubly_linked_list const doubly_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_doubly_linked_list_clear (CCC_Doubly_linked_list list, CCC_Destructor const destructor, CCC_Allocator const *allocator)
	Clear the contents of the list freeing elements, if given allocation permission. O(N).

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

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

void *	CCC_doubly_linked_list_next (CCC_Doubly_linked_list const list, CCC_Doubly_linked_list_node const type_intruder)
	Return the user type following the element known to be in the list. O(1).

void *	CCC_doubly_linked_list_reverse_next (CCC_Doubly_linked_list const list, CCC_Doubly_linked_list_node const type_intruder)
	Return the user type following the element known to be in the list moving from back to front. O(1).

void *	CCC_doubly_linked_list_end (CCC_Doubly_linked_list const *list)
	Return the end sentinel with no accessible fields. O(1).

void *	CCC_doubly_linked_list_reverse_end (CCC_Doubly_linked_list const *list)
	Return the start sentinel with no accessible fields. O(1).

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

void *	CCC_doubly_linked_list_back (CCC_Doubly_linked_list const *list)
	Returns the user type at the back of the list. O(1).

CCC_Doubly_linked_list_node *	CCC_doubly_linked_list_node_begin (CCC_Doubly_linked_list const *list)
	Return a handle to the list element at the front of the list which may be the sentinel. O(1).

CCC_Count	CCC_doubly_linked_list_count (CCC_Doubly_linked_list const *list)
	Return the count of elements in the list. O(N).

CCC_Tribool	CCC_doubly_linked_list_is_empty (CCC_Doubly_linked_list const *list)
	Return if the size of the list is equal to 0. O(1).

CCC_Tribool	CCC_doubly_linked_list_validate (CCC_Doubly_linked_list const *list)
	Validates internal state of the list.

Macro Definition Documentation

◆ CCC_doubly_linked_list_default

#define CCC_doubly_linked_list_default	(	type_name,
		type_intruder_field
	)	CCC_private_doubly_linked_list_for(type_name, type_intruder_field)

Initialize an intrusive doubly linked list for a type with a user specified intruder field.

Parameters

[in]	type_name	the type containing the intrusive doubly_linked_list element.
[in]	type_intruder_field	name of the Doubly_linked_list element in the containing type.

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.

◆ CCC_doubly_linked_list_emplace_back

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

Value:

    CCC_private_doubly_linked_list_emplace_back(                               \
        list_pointer, allocator_pointer, type_compound_literal                 \
    )

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

Parameters

[in]	list_pointer	the address of the doubly linked list.
[in]	allocator_pointer	the required CCC_Allocator for allocation.
[in]	type_compound_literal	the r-value initializer of the type to be inserted in the list. This should match the type containing Doubly_linked_list 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_doubly_linked_list_emplace_front

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

Value:

    CCC_private_doubly_linked_list_emplace_front(                              \
        list_pointer, allocator_pointer, type_compound_literal                 \
    )

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

Parameters

[in]	list_pointer	the address of the doubly linked list.
[in]	allocator_pointer	the required CCC_Allocator for allocation.
[in]	type_compound_literal	the r-value initializer of the type to be inserted in the list. This should match the type containing Doubly_linked_list 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_doubly_linked_list_for

#define CCC_doubly_linked_list_for	(	type_name,
		type_intruder_field
	)	CCC_private_doubly_linked_list_for(type_name, type_intruder_field)

Initialize an intrusive doubly linked list for a type with a user specified intruder field.

Parameters

[in]	type_name	the type containing the intrusive doubly_linked_list element.
[in]	type_intruder_field	name of the Doubly_linked_list element in the containing type.

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.

◆ CCC_doubly_linked_list_from

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

Value:

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

Initialize a doubly 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 required CCC_Allocator for allocation.
[in]	destructor	the optional destructor to run over all allocated elements if memory exhaustion occurs at any point during construction.
[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 doubly linked list on the right side of an equality operator.

Note: The list is constructed to the specification of 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_Doubly_linked_list

typedef struct CCC_Doubly_linked_list 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.

◆ CCC_Doubly_linked_list_node

typedef struct CCC_Doubly_linked_list_node CCC_Doubly_linked_list_node

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.

Function Documentation

◆ CCC_doubly_linked_list_back()

void * CCC_doubly_linked_list_back ( CCC_Doubly_linked_list const * list )

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

Parameters

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

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

◆ CCC_doubly_linked_list_begin()

void * CCC_doubly_linked_list_begin ( CCC_Doubly_linked_list const * list )

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

Parameters

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

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

◆ CCC_doubly_linked_list_clear()

CCC_Result CCC_doubly_linked_list_clear	(	CCC_Doubly_linked_list *	list,
		CCC_Destructor const *	destructor,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	destructor	an optional CCC_Destructor to run on each element.
[in]	allocator	the CCC_Allocator for freeing a user type.

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

Note that if an allocator is provided it will be called to free each element in the list. Be mindful that the destructor does not free as well, instead taking care of any destructor-like book keeping. If no destructor is needed provide the default destructor &(CCC_Destructor){}.

If the list is not provided with an allocator, &(CCC_Allocator){}, 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_doubly_linked_list_count()

CCC_Count CCC_doubly_linked_list_count ( CCC_Doubly_linked_list const * list )

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

Parameters

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

Returns: the size of the list. An argument error is set if list is NULL.

◆ CCC_doubly_linked_list_end()

void * CCC_doubly_linked_list_end ( CCC_Doubly_linked_list const * list )

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

Parameters

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

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

◆ CCC_doubly_linked_list_erase()

void * CCC_doubly_linked_list_erase	(	CCC_Doubly_linked_list *	list,
		CCC_Doubly_linked_list_node *	type_intruder,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	type_intruder	the handle of an element known to be in the list.
[in]	allocator	the CCC_Allocator for freeing a user type.

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

◆ CCC_doubly_linked_list_erase_range()

void * CCC_doubly_linked_list_erase_range	(	CCC_Doubly_linked_list *	list,
		CCC_Doubly_linked_list_node *	type_intruder_begin,
		CCC_Doubly_linked_list_node *	type_intruder_end,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	type_intruder_begin	the handle of an element known to be in the list at the start of the range.
[in]	type_intruder_end	the handle of an element known to be in the list at the end of the range following type_intruder_begin.
[in]	allocator	the CCC_Allocator for freeing a user type.

Returns: a reference to the element in the list following type_intruder_end or NULL if the element is the last. NULL is returned if bad input is provided or the type_intruder 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 type_intruder_begin to type_intruder_end will be erased and references invalidated.

◆ CCC_doubly_linked_list_extract()

void * CCC_doubly_linked_list_extract	(	CCC_Doubly_linked_list *	list,
		CCC_Doubly_linked_list_node *	type_intruder
	)

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

Parameters

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

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

◆ CCC_doubly_linked_list_extract_range()

void * CCC_doubly_linked_list_extract_range	(	CCC_Doubly_linked_list *	list,
		CCC_Doubly_linked_list_node *	type_intruder_begin,
		CCC_Doubly_linked_list_node *	type_intruder_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]	list	a pointer to the doubly linked list.
[in]	type_intruder_begin	the handle of an element known to be in the list at the start of the range.
[in]	type_intruder_end	the handle of an element known to be in the list at the end of the range following type_intruder_begin.

Returns: a reference to the element in the list following type_intruder_end or NULL if the element is the last. NULL is returned if bad input is provided or the type_intruder 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_doubly_linked_list_front()

void * CCC_doubly_linked_list_front ( CCC_Doubly_linked_list const * list )

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

Parameters

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

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

◆ CCC_doubly_linked_list_insert()

void * CCC_doubly_linked_list_insert	(	CCC_Doubly_linked_list *	list,
		CCC_Doubly_linked_list_node *	position_node,
		CCC_Doubly_linked_list_node *	type_intruder,
		CCC_Allocator const *	allocator
	)

Insert user type wrapping type_intruder before position_node. O(1).

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	position_node	a pointer to the list element before which type_intruder inserts.
[in]	type_intruder	a pointer to the list element.
[in]	allocator	the CCC_Allocator for allocating a user type.

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

◆ CCC_doubly_linked_list_insert_sorted()

void * CCC_doubly_linked_list_insert_sorted	(	CCC_Doubly_linked_list *	doubly_linked_list,
		CCC_Doubly_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]	doubly_linked_list	a pointer to the doubly 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	the CCC_Comparator for comparing list elements.
[in]	allocator	the CCC_Allocator for allocating a user type.

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, CCC_ORDER_EQUAL.

◆ CCC_doubly_linked_list_is_empty()

CCC_Tribool CCC_doubly_linked_list_is_empty ( CCC_Doubly_linked_list const * list )

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

Parameters

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

Returns: true if the size is 0, else false. Error if list is NULL.

◆ CCC_doubly_linked_list_is_sorted()

CCC_Tribool CCC_doubly_linked_list_is_sorted	(	CCC_Doubly_linked_list const *	doubly_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]	doubly_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_doubly_linked_list_next()

void * CCC_doubly_linked_list_next	(	CCC_Doubly_linked_list const *	list,
		CCC_Doubly_linked_list_node const *	type_intruder
	)

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

Parameters

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

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

◆ CCC_doubly_linked_list_node_begin()

CCC_Doubly_linked_list_node * CCC_doubly_linked_list_node_begin ( CCC_Doubly_linked_list const * list )

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

Parameters

[in] list 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_doubly_linked_list_pop_back()

CCC_Result CCC_doubly_linked_list_pop_back	(	CCC_Doubly_linked_list *	list,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	allocator	the CCC_Allocator for freeing a user type.

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

◆ CCC_doubly_linked_list_pop_front()

CCC_Result CCC_doubly_linked_list_pop_front	(	CCC_Doubly_linked_list *	list,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	allocator	the CCC_Allocator for freeing a user type.

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

◆ CCC_doubly_linked_list_push_back()

void * CCC_doubly_linked_list_push_back	(	CCC_Doubly_linked_list *	list,
		CCC_Doubly_linked_list_node *	type_intruder,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	type_intruder	a pointer to the list element.
[in]	allocator	the CCC_Allocator for allocating a user type.

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

◆ CCC_doubly_linked_list_push_front()

void * CCC_doubly_linked_list_push_front	(	CCC_Doubly_linked_list *	list,
		CCC_Doubly_linked_list_node *	type_intruder,
		CCC_Allocator const *	allocator
	)

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

Parameters

[in]	list	a pointer to the doubly linked list.
[in]	type_intruder	a pointer to the list element.
[in]	allocator	the CCC_Allocator for allocating a user type.

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

◆ CCC_doubly_linked_list_reverse_begin()

void * CCC_doubly_linked_list_reverse_begin ( CCC_Doubly_linked_list const * list )

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

Parameters

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

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

◆ CCC_doubly_linked_list_reverse_end()

void * CCC_doubly_linked_list_reverse_end ( CCC_Doubly_linked_list const * list )

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

Parameters

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

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

◆ CCC_doubly_linked_list_reverse_next()

void * CCC_doubly_linked_list_reverse_next	(	CCC_Doubly_linked_list const *	list,
		CCC_Doubly_linked_list_node const *	type_intruder
	)

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

Parameters

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

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

◆ CCC_doubly_linked_list_splice()

CCC_Result CCC_doubly_linked_list_splice	(	CCC_Doubly_linked_list *	position_doubly_linked_list,
		CCC_Doubly_linked_list_node *	type_intruder_position,
		CCC_Doubly_linked_list *	to_cut_doubly_linked_list,
		CCC_Doubly_linked_list_node *	type_intruder_to_cut
	)

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

Parameters

[in]	position_doubly_linked_list	the list to which position belongs.
[in]	type_intruder_position	the position before which to_cut will be moved.
[in]	to_cut_doubly_linked_list	the list to which to_cut belongs.
[in]	type_intruder_to_cut	the element to cut.

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

◆ CCC_doubly_linked_list_splice_range()

CCC_Result CCC_doubly_linked_list_splice_range	(	CCC_Doubly_linked_list *	position_doubly_linked_list,
		CCC_Doubly_linked_list_node *	type_intruder_position,
		CCC_Doubly_linked_list *	to_cut_doubly_linked_list,
		CCC_Doubly_linked_list_node *	type_intruder_to_cut_begin,
		CCC_Doubly_linked_list_node *	type_intruder_to_cut_exclusive_end
	)

Splices the list to cut before the specified position. The range being cut is exclusive from [start, end), meaning the final element provided is not move. This is an O(N) operation.

Parameters

[in]	position_doubly_linked_list	the list to which position belongs.
[in]	type_intruder_position	the position before which the list is moved.
[in]	to_cut_doubly_linked_list	the list to which the range belongs.
[in]	type_intruder_to_cut_begin	the start of the list to splice.
[in]	type_intruder_to_cut_exclusive_end	the exclusive end of the list to splice, not included in the splice operation.

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

◆ CCC_doubly_linked_list_validate()

CCC_Tribool CCC_doubly_linked_list_validate ( CCC_Doubly_linked_list const * list )

Validates internal state of the list.

Parameters

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

Returns: true if invariants hold, false if not. Error if 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_doubly_linked_list_default

◆ CCC_doubly_linked_list_emplace_back

◆ CCC_doubly_linked_list_emplace_front

◆ CCC_doubly_linked_list_for

◆ CCC_doubly_linked_list_from

Typedef Documentation

◆ CCC_Doubly_linked_list

◆ CCC_Doubly_linked_list_node

Function Documentation

◆ CCC_doubly_linked_list_back()

◆ CCC_doubly_linked_list_begin()

◆ CCC_doubly_linked_list_clear()

◆ CCC_doubly_linked_list_count()

◆ CCC_doubly_linked_list_end()

◆ CCC_doubly_linked_list_erase()

◆ CCC_doubly_linked_list_erase_range()

◆ CCC_doubly_linked_list_extract()

◆ CCC_doubly_linked_list_extract_range()

◆ CCC_doubly_linked_list_front()

◆ CCC_doubly_linked_list_insert()

◆ CCC_doubly_linked_list_insert_sorted()

◆ CCC_doubly_linked_list_is_empty()

◆ CCC_doubly_linked_list_is_sorted()

◆ CCC_doubly_linked_list_next()

◆ CCC_doubly_linked_list_node_begin()

◆ CCC_doubly_linked_list_pop_back()

◆ CCC_doubly_linked_list_pop_front()

◆ CCC_doubly_linked_list_push_back()

◆ CCC_doubly_linked_list_push_front()

◆ CCC_doubly_linked_list_reverse_begin()

◆ CCC_doubly_linked_list_reverse_end()

◆ CCC_doubly_linked_list_reverse_next()

◆ CCC_doubly_linked_list_splice()

◆ CCC_doubly_linked_list_splice_range()

◆ CCC_doubly_linked_list_validate()