The Flat Double Ended Queue Interface. More...

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

Include dependency graph for flat_double_ended_queue.h:

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

Detailed Description

The Flat Double Ended Queue Interface.

An double ended queue offers contiguous storage and random access, push, and pop in constant time. The contiguous nature of the container makes it well-suited to dynamic or fixed size contexts where a double ended queue is needed.

If the container is initialized with allocation permission it will resize when needed but support constant time push and pop to the front and back when resizing is not required, resulting in amortized O(1) operations.

If the double ended queue is initialized without allocation permission its behavior is equivalent to a Ring Buffer. This is somewhat unique in that it does not fail to insert elements when size is equal to capacity. This means that push front, push back, pop front, and pop back are O(1) operations. However, if any push exceeds capacity an element where the push should occur is overwritten.

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

#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC

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

Initialization Interface
Initialize and create containers with memory, callbacks, and permissions.
#define	CCC_flat_double_ended_queue_initialize(data_pointer, type_name, allocate, context_data, capacity, optional_size...)
	Initialize the queue with memory and allocation permission.

#define	CCC_flat_double_ended_queue_from( allocate, context_data, optional_capacity, compound_literal_array...)
	Initialize a Flat_double_ended_queue from a compound literal array initializer.

#define	CCC_flat_double_ended_queue_with_capacity(type_name, allocate, context_data, capacity)
	Initialize a Flat_double_ended_queue with a capacity.

#define	CCC_flat_double_ended_queue_with_compound_literal( count, compound_literal_array...)
	Initialize the queue from a compound literal array with no allocation permissions or context data.

#define	CCC_flat_double_ended_queue_with_context_compound_literal( count, compound_literal_array...)
	Initialize the queue from a compound literal array with no allocation permissions.

CCC_Result	CCC_flat_double_ended_queue_copy (CCC_Flat_double_ended_queue destination, CCC_Flat_double_ended_queue const source, CCC_Allocator *allocate)
	Copy the queue from source to newly initialized destination.

CCC_Result	CCC_flat_double_ended_queue_reserve (CCC_Flat_double_ended_queue queue, size_t to_add, CCC_Allocator allocate)
	Reserves space for at least to_add more elements.

Insert and Remove Interface
Add or remove elements from the FDEQ.
#define	CCC_flat_double_ended_queue_emplace_back( flat_double_ended_queue_pointer, value...)
	Write an element directly to the back slot of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

#define	CCC_flat_double_ended_queue_emplace_front( flat_double_ended_queue_pointer, value...)
	Write an element directly to the front slot of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

void *	CCC_flat_double_ended_queue_push_back (CCC_Flat_double_ended_queue queue, void const type)
	Push the user type to the back of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

CCC_Result	CCC_flat_double_ended_queue_push_back_range (CCC_Flat_double_ended_queue queue, size_t count, void const type_array)
	Push the range of user types to the back of the flat_double_ended_queue. O(N).

void *	CCC_flat_double_ended_queue_push_front (CCC_Flat_double_ended_queue queue, void const type)
	Push the user type to the front of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

CCC_Result	CCC_flat_double_ended_queue_push_front_range (CCC_Flat_double_ended_queue queue, size_t count, void const type_array)
	Push the range of user types to the front of the flat_double_ended_queue. O(N).

void *	CCC_flat_double_ended_queue_insert_range (CCC_Flat_double_ended_queue queue, void position, size_t count, void const *type_array)
	Push the range of user types before position of the flat_double_ended_queue. O(N).

CCC_Result	CCC_flat_double_ended_queue_pop_front (CCC_Flat_double_ended_queue *queue)
	Pop an element from the front of the flat_double_ended_queue. O(1).

CCC_Result	CCC_flat_double_ended_queue_pop_back (CCC_Flat_double_ended_queue *queue)
	Pop an element from the back of the flat_double_ended_queue. O(1).

Container Types
Types available in the container interface.
typedef struct CCC_Flat_double_ended_queue	CCC_Flat_double_ended_queue
	A contiguous Buffer for O(1) push and pop from front and back.

Deallocation Interface
Destroy the container.
CCC_Result	CCC_flat_double_ended_queue_clear (CCC_Flat_double_ended_queue queue, CCC_Type_destructor destructor)
	Set size of queue to 0 and call destructor on each element if needed. O(1) if no destructor is provided, else O(N).

CCC_Result	CCC_flat_double_ended_queue_clear_and_free (CCC_Flat_double_ended_queue queue, CCC_Type_destructor destructor)
	Set size of queue to 0 and call destructor on each element if needed. Free the underlying Buffer setting the capacity to 0. O(1) if no destructor is provided, else O(N).

CCC_Result	CCC_flat_double_ended_queue_clear_and_free_reserve (CCC_Flat_double_ended_queue queue, CCC_Type_destructor destructor, CCC_Allocator *allocate)
	Frees all slots in the queue and frees the underlying Buffer that was previously dynamically reserved with the reserve function.

State Interface
Interact with the state of the FDEQ.
void *	CCC_flat_double_ended_queue_begin (CCC_Flat_double_ended_queue const *queue)
	Return a pointer to the front element of the flat_double_ended_queue. O(1).

void *	CCC_flat_double_ended_queue_reverse_begin (CCC_Flat_double_ended_queue const *queue)
	Return a pointer to the back element of the flat_double_ended_queue. O(1).

void *	CCC_flat_double_ended_queue_next (CCC_Flat_double_ended_queue const queue, void const iterator_pointer)
	Return the next element in the queue moving front to back. O(1).

void *	CCC_flat_double_ended_queue_reverse_next (CCC_Flat_double_ended_queue const queue, void const iterator_pointer)
	Return the next element in the queue moving back to front. O(1).

void *	CCC_flat_double_ended_queue_end (CCC_Flat_double_ended_queue const *queue)
	Return a pointer to the end element. It may not be accessed. O(1).

void *	CCC_flat_double_ended_queue_reverse_end (CCC_Flat_double_ended_queue const *queue)
	Return a pointer to the start element. It may not be accessed. O(1).

void *	CCC_flat_double_ended_queue_at (CCC_Flat_double_ended_queue const *queue, size_t i)
	Return a reference to the element at index position i. O(1).

void *	CCC_flat_double_ended_queue_front (CCC_Flat_double_ended_queue const *queue)
	Return a reference to the front of the flat_double_ended_queue. O(1).

void *	CCC_flat_double_ended_queue_back (CCC_Flat_double_ended_queue const *queue)
	Return a reference to the back of the flat_double_ended_queue. O(1).

CCC_Tribool	CCC_flat_double_ended_queue_is_empty (CCC_Flat_double_ended_queue const *queue)
	Return true if the size of the queue is 0. O(1).

CCC_Count	CCC_flat_double_ended_queue_count (CCC_Flat_double_ended_queue const *queue)
	Return the count of active queue slots. O(1).

CCC_Count	CCC_flat_double_ended_queue_capacity (CCC_Flat_double_ended_queue const *queue)
	Return the capacity representing total possible slots. O(1).

void *	CCC_flat_double_ended_queue_data (CCC_Flat_double_ended_queue const *queue)
	Return a reference to the base of backing array. O(1).

CCC_Tribool	CCC_flat_double_ended_queue_validate (CCC_Flat_double_ended_queue const *queue)
	Return true if the internal invariants of the flat_double_ended_queue.

Macro Definition Documentation

◆ CCC_flat_double_ended_queue_emplace_back

#define CCC_flat_double_ended_queue_emplace_back	(	flat_double_ended_queue_pointer,
		value...
	)

Value:

CCC_private_flat_double_ended_queue_emplace_back( \

flat_double_ended_queue_pointer, value)

Write an element directly to the back slot of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

Parameters

[in]	flat_double_ended_queue_pointer	a pointer to the flat_double_ended_queue.
[in]	value	for integral types, the direct value. For structs and unions use compound literal syntax.

Returns: a reference to the inserted element. If allocation is permitted and a resizing is required to insert the element but fails, NULL is returned.

◆ CCC_flat_double_ended_queue_emplace_front

#define CCC_flat_double_ended_queue_emplace_front	(	flat_double_ended_queue_pointer,
		value...
	)

Value:

CCC_private_flat_double_ended_queue_emplace_front( \

flat_double_ended_queue_pointer, value)

Write an element directly to the front slot of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

Parameters

[in]	flat_double_ended_queue_pointer	a pointer to the flat_double_ended_queue.
[in]	value	for integral types, the direct value. For structs and unions use compound literal syntax.

Returns: a reference to the inserted element. If allocation is permitted and a resizing is required to insert the element but fails, NULL is returned.

◆ CCC_flat_double_ended_queue_from

#define CCC_flat_double_ended_queue_from	(	allocate,
		context_data,
		optional_capacity,
		compound_literal_array...
	)

Value:

CCC_private_flat_double_ended_queue_from( \

allocate, context_data, optional_capacity, compound_literal_array)

Initialize a Flat_double_ended_queue from a compound literal array initializer.

Parameters

[in]	allocate	CCC_Allocator or NULL if no allocation is permitted.
[in]	context_data	any context data needed for managing Flat_double_ended_queue memory.
[in]	optional_capacity	optionally specify the capacity of the Flat_double_ended_queue if different from the size of the compound literal array initializer. If the capacity is greater than the size of the compound literal array initializer, it is respected and the capacity is reserved. If the capacity is less than the size of the compound array initializer, the compound literal array initializer size is set as the capacity. Therefore, 0 is valid if one is not concerned with the underlying reservation.
[in]	compound_literal_array	the initializer of the type stored in flat_double_ended_queue.

Returns: the initialized flat_double_ended_queue. Directly assign to Flat_double_ended_queue on the right hand side of the equality operator (e.g. CCC_Flat_double_ended_queue b = CCC_flat_double_ended_queue_from(...);).

Initialize a dynamic Flat_double_ended_queue with a compound literal array.

#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC
int
main(void)
{
    Flat_double_ended_queue f
        = flat_double_ended_queue_from(std_allocate, NULL, 0,
            (int[]){ 0, 1, 2, 3 });
    return 0;
}

Initialize a dynamic Flat_double_ended_queue with a compound literal array with capacity.

#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC
int
main(void)
{
    Flat_double_ended_queue f
        = flat_double_ended_queue_from(std_allocate, NULL, 4096,
            (int[]){ 0, 1, 2, 3 });
    return 0;
}

Only dynamic flat_double_ended_queues may be initialized this way. For static or stack based initialization of fixed flat_double_ended_queues with contents known at compile time, see the CCC_flat_double_ended_queue_initialize() macro.

◆ CCC_flat_double_ended_queue_initialize

#define CCC_flat_double_ended_queue_initialize	(	data_pointer,
		type_name,
		allocate,
		context_data,
		capacity,
		optional_size...
	)

Value:

    CCC_private_flat_double_ended_queue_initialize(data_pointer, type_name,    \
                                                   allocate, context_data,     \
                                                   capacity, optional_size)

Initialize the queue with memory and allocation permission.

Parameters

[in]	data_pointer	a pointer to existing memory or ((T *)NULL).
[in]	type_name	the name of the user type.
[in]	allocate	the allocator function, if allocation is allowed.
[in]	context_data	any context data needed for element destruction.
[in]	capacity	the number of contiguous elements at data_pointer
[in]	optional_size	an optional initial size between 1 and capacity.

Returns: the queue on the right hand side of an equality operator at runtime or compiletime (e.g. CCC_Flat_double_ended_queue q = CCC_flat_double_ended_queue_initialize(...);)

◆ CCC_flat_double_ended_queue_with_capacity

#define CCC_flat_double_ended_queue_with_capacity	(	type_name,
		allocate,
		context_data,
		capacity
	)

Value:

CCC_private_flat_double_ended_queue_with_capacity(type_name, allocate, \

context_data, capacity)

Initialize a Flat_double_ended_queue with a capacity.

Parameters

[in]	type_name	any user or language standard type name.
[in]	allocate	CCC_Allocator or NULL if no allocation is permitted.
[in]	context_data	any context data needed for managing Flat_double_ended_queue memory.
[in]	capacity	the capacity of the Flat_double_ended_queue to reserve.

Returns: the initialized flat_double_ended_queue. Directly assign to Flat_double_ended_queue on the right hand side of the equality operator (e.g. CCC_Flat_double_ended_queue b = CCC_Flat_double_ended_queue_with_capacity(...);).

Initialize a dynamic Flat_double_ended_queue.

#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC
int
main(void)
{
    Flat_double_ended_queue f
        = flat_double_ended_queue_from(std_allocate, NULL, 4096);
    return 0;
}

Only dynamic flat_double_ended_queues may be initialized this way. For static or stack based initialization of fixed flat_double_ended_queues with contents known at compile time, see the CCC_flat_double_ended_queue_initialize() macro.

◆ CCC_flat_double_ended_queue_with_compound_literal

#define CCC_flat_double_ended_queue_with_compound_literal	(	count,
		compound_literal_array...
	)

Value:

CCC_private_flat_double_ended_queue_with_compound_literal( \

count, compound_literal_array)

Initialize the queue from a compound literal array with no allocation permissions or context data.

Parameters

[in]	count	the count of elements to start.
[in]	compound_literal_array	the array of user types.

Returns: the queue on the right hand side of an equality operator at runtime or compiletime (e.g. CCC_Flat_double_ended_queue q = CCC_flat_double_ended_queue_with_compound_literal(...);)

◆ CCC_flat_double_ended_queue_with_context_compound_literal

#define CCC_flat_double_ended_queue_with_context_compound_literal	(	count,
		compound_literal_array...
	)

Value:

CCC_private_flat_double_ended_queue_with_context_compound_literal( \

count, compound_literal_array)

Initialize the queue from a compound literal array with no allocation permissions.

Parameters

[in]	context	any context needed for the flat double ended queue.
[in]	count	the count of elements to start.
[in]	compound_literal_array	the array of user types.

Returns: the queue on the right hand side of an equality operator at runtime or compiletime (e.g. CCC_Flat_double_ended_queue q = CCC_flat_double_ended_queue_with_context_compound_literal(...);)

Typedef Documentation

◆ CCC_Flat_double_ended_queue

typedef struct CCC_Flat_double_ended_queue CCC_Flat_double_ended_queue

A contiguous Buffer for O(1) push and pop from front and back.

Warning: it is undefined behavior to use an uninitialized flat double ended queue.

A flat double ended queue can be initialized on the stack, heap, or data segment at compile time or runtime.

Function Documentation

◆ CCC_flat_double_ended_queue_at()

void * CCC_flat_double_ended_queue_at	(	CCC_Flat_double_ended_queue const *	queue,
		size_t	i
	)

Return a reference to the element at index position i. O(1).

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	i	the 0 based index in the flat_double_ended_queue.

Returns: a reference to the element at i if 0 <= i < capacity.

Note that the front of the queue is considered index 0, so the user need not worry about where the front is for indexing purposes.

◆ CCC_flat_double_ended_queue_back()

void * CCC_flat_double_ended_queue_back ( CCC_Flat_double_ended_queue const * queue )

Return a reference to the back of the flat_double_ended_queue. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: a reference to the back element or NULL if queue is NULL or the queue is empty.

◆ CCC_flat_double_ended_queue_begin()

void * CCC_flat_double_ended_queue_begin ( CCC_Flat_double_ended_queue const * queue )

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

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: a pointer to the user type at the start of the flat_double_ended_queue. NULL if empty.

◆ CCC_flat_double_ended_queue_capacity()

CCC_Count CCC_flat_double_ended_queue_capacity ( CCC_Flat_double_ended_queue const * queue )

Return the capacity representing total possible slots. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: the capacity of the queue or an argument error is set if queue is NULL.

◆ CCC_flat_double_ended_queue_clear()

CCC_Result CCC_flat_double_ended_queue_clear	(	CCC_Flat_double_ended_queue *	queue,
		CCC_Type_destructor *	destructor
	)

Set size of queue to 0 and call destructor on each element if needed. O(1) if no destructor is provided, else O(N).

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	destructor	the destructor if needed or NULL.

Note that if destructor is non-NULL it will be called on each element in the flat_double_ended_queue. However, the underlying Buffer for the flat_double_ended_queue is not freed. If the destructor is NULL, setting the size to 0 is O(1).

◆ CCC_flat_double_ended_queue_clear_and_free()

CCC_Result CCC_flat_double_ended_queue_clear_and_free	(	CCC_Flat_double_ended_queue *	queue,
		CCC_Type_destructor *	destructor
	)

Set size of queue to 0 and call destructor on each element if needed. Free the underlying Buffer setting the capacity to 0. O(1) if no destructor is provided, else O(N).

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	destructor	the destructor if needed or NULL.

Note that if destructor is non-NULL it will be called on each element in the flat_double_ended_queue. After all elements are processed the Buffer is freed and capacity is 0. If destructor is NULL the Buffer is freed directly and capacity is 0.

◆ CCC_flat_double_ended_queue_clear_and_free_reserve()

CCC_Result CCC_flat_double_ended_queue_clear_and_free_reserve	(	CCC_Flat_double_ended_queue *	queue,
		CCC_Type_destructor *	destructor,
		CCC_Allocator *	allocate
	)

Frees all slots in the queue and frees the underlying Buffer that was previously dynamically reserved with the reserve function.

Parameters

[in]	queue	the queue to be cleared.
[in]	destructor	the destructor for each element. NULL can be passed if no maintenance is required on the elements in the queue before their slots are dropped.
[in]	allocate	the required allocation function to provide to a dynamically reserved flat_double_ended_queue. Any context data provided upon initialization will be passed to the allocation function when called.

Returns: the result of free operation. OK if success, or an error status to indicate the error.

Warning: It is an error to call this function on a queue that was not reserved with the provided CCC_Allocator. The flat_double_ended_queue must have existing memory to free.

This function covers the edge case of reserving a dynamic capacity for a flat_double_ended_queue at runtime but denying the flat_double_ended_queue allocation permission to resize. This can help prevent a flat_double_ended_queue from growing untree. The user in this case knows the flat_double_ended_queue does not have allocation permission and therefore no further memory will be dedicated to the flat_double_ended_queue.

However, to free the queue in such a case this function must be used because the queue has no ability to free itself. Just as the allocation function is required to reserve memory so to is it required to free memory.

This function will work normally if called on a queue with allocation permission however the normal CCC_flat_double_ended_queue_clear_and_free is sufficient for that use case.

◆ CCC_flat_double_ended_queue_copy()

CCC_Result CCC_flat_double_ended_queue_copy	(	CCC_Flat_double_ended_queue *	destination,
		CCC_Flat_double_ended_queue const *	source,
		CCC_Allocator *	allocate
	)

Copy the queue from source to newly initialized destination.

Parameters

[in]	destination	the destination that will copy the source flat_double_ended_queue.
[in]	source	the source of the flat_double_ended_queue.
[in]	allocate	the allocation function in case resizing of destination is needed.

Returns: the result of the copy operation. If the destination capacity is less than the source capacity and no allocation function is provided an input error is returned. If resizing is required and resizing of destination fails a memory error is returned.

Note: destination must have capacity greater than or equal to source. If destination capacity is less than source, an allocation function must be provided with the allocate argument.

Note that there are two ways to copy data from source to destination: provide sufficient memory and pass NULL as allocate, or allow the copy function to take care of allocation for the copy.

Manual memory management with no allocation function provided.

#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC
Flat_double_ended_queue source = flat_double_ended_queue_initialize(
    (int[10]){},
    int,
    NULL,
    NULL,
    10
);
int *new_data
    = malloc(sizeof(int) * flat_double_ended_queue_capacity(&source).count);
Flat_double_ended_queue destination = flat_double_ended_queue_initialize(
    new_data,
    int,
    NULL,
    NULL,
    flat_double_ended_queue_capacity(&source).count
);
CCC_Result res = flat_double_ended_queue_copy(&destination, &source, NULL);

The above requires destination capacity be greater than or equal to source capacity. Here is memory management handed over to the copy function.

#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC
Flat_double_ended_queue source = flat_double_ended_queue_initialize(
    NULL,
    int,
    std_allocate,
    NULL,
    0
);
(void)CCC_flat_double_ended_queue_push_back_range(
    &source,
    5,
    (int[5]){0,1,2,3,4}
);
Flat_double_ended_queue destination = flat_double_ended_queue_initialize(
    NULL,
    int,
    std_allocate,
    NULL,
    0
);
CCC_Result res = flat_double_ended_queue_copy(
    &destination,
    &source,
    std_allocate
);

The above allows destination to have a capacity less than that of the source as long as copy has been provided an allocation function to resize destination. Note that this would still work if copying to a destination that the user wants as a fixed size queue (ring buffer).

#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC
Flat_double_ended_queue source = flat_double_ended_queue_initialize(
    NULL,
    int,
    std_allocate,
    NULL,
    0
);
(void)CCC_flat_double_ended_queue_push_back_range(
    &source,
    5,
    (int[5]){0,1,2,3,4}
);
Flat_double_ended_queue destination = flat_double_ended_queue_initialize(
    NULL,
    int,
    NULL,
    NULL,
    0
);
CCC_Result res = flat_double_ended_queue_copy(
    &destination,
    &source,
    std_allocate
);

The above sets up destination as a ring Buffer while source is a dynamic flat_double_ended_queue. Because an allocation function is provided, the destination is resized once for the copy and retains its fixed size after the copy is complete. This would require the user to manually free the underlying Buffer at destination eventually if this method is used. Usually it is better to allocate the memory explicitly before the copy if copying between ring buffers.

These options allow users to stay consistent across containers with their memory management strategies.

◆ CCC_flat_double_ended_queue_count()

CCC_Count CCC_flat_double_ended_queue_count ( CCC_Flat_double_ended_queue const * queue )

Return the count of active queue slots. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: the size of the queue or an argument error is set if flat_double_ended_queue is NULL.

◆ CCC_flat_double_ended_queue_data()

void * CCC_flat_double_ended_queue_data ( CCC_Flat_double_ended_queue const * queue )

Return a reference to the base of backing array. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: a reference to the base of the backing array.

Note: the reference is to the base of the backing array at index 0 with no consideration to where the front index of the queue may be.

Warning: it is the users responsibility to ensure that access to any data is within the capacity of the backing buffer.

This method is exposed for serialization or writing purposes but the base of the array may not point to valid data in terms of organization of the flat_double_ended_queue.

◆ CCC_flat_double_ended_queue_end()

void * CCC_flat_double_ended_queue_end ( CCC_Flat_double_ended_queue const * queue )

Return a pointer to the end element. It may not be accessed. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: a pointer to the end sentinel element that may not be accessed.

◆ CCC_flat_double_ended_queue_front()

void * CCC_flat_double_ended_queue_front ( CCC_Flat_double_ended_queue const * queue )

Return a reference to the front of the flat_double_ended_queue. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

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

◆ CCC_flat_double_ended_queue_insert_range()

void * CCC_flat_double_ended_queue_insert_range	(	CCC_Flat_double_ended_queue *	queue,
		void *	position,
		size_t	count,
		void const *	type_array
	)

Push the range of user types before position of the flat_double_ended_queue. O(N).

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	position	the position in the queue before which to push the range.
[in]	count	the number of user types in the type_array range.
[in]	type_array	a pointer to the array of user types.

Returns: a pointer to the start of the inserted range or NULL if a resize was required and could not complete.

Note that if no allocation is permitted the queue behaves as a ring buffer. Therefore, pushing a range that will exceed capacity will overwrite elements at the start of the flat_double_ended_queue.

Pushing a range of elements prioritizes the range and allows the range to overwrite elements instead of pushing those elements over the start of the range. For example, push a range {3,4,5} over a queue with capacity 5 before position with value 6.

 front position        front
┌─┬┴┬─┬┴┬─┐    ┌─┬─┬┴┬─┬─┐
│ │1│2│6│ │ -> │5│6│2│3│4│
└─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┘

Notice that 1 and 2 were NOT moved to overwrite the start of the range, the values 3 and 4. The only way the start of a range will be overwritten is if the range itself is too large for the capacity. For example, push a range {0,0,3,3,4,4,5,5} over the same flat_double_ended_queue.

 front position    front
┌─┬┴┬─┬┴┬─┐    ┌┴┬─┬─┬─┬─┐
│ │1│2│6│ │ -> │3│4│4│5│5│
└─┴─┴─┴─┴─┘    └─┴─┴─┴─┴─┘

Notice that the start of the range, {0,0,3,...}, is overwritten.

◆ CCC_flat_double_ended_queue_is_empty()

CCC_Tribool CCC_flat_double_ended_queue_is_empty ( CCC_Flat_double_ended_queue const * queue )

Return true if the size of the queue is 0. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: true if the size is 0 or false. Error if queue is NULL.

◆ CCC_flat_double_ended_queue_next()

void * CCC_flat_double_ended_queue_next	(	CCC_Flat_double_ended_queue const *	queue,
		void const *	iterator_pointer
	)

Return the next element in the queue moving front to back. O(1).

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	iterator_pointer	the current element in the flat_double_ended_queue.

Returns: the element following iterator_pointer or NULL if no elements follow.

◆ CCC_flat_double_ended_queue_pop_back()

CCC_Result CCC_flat_double_ended_queue_pop_back ( CCC_Flat_double_ended_queue * queue )

Pop an element from the back of the flat_double_ended_queue. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: ok if the pop was successful. If queue is NULL or the flat_double_ended_queue is empty an input error is returned.

◆ CCC_flat_double_ended_queue_pop_front()

CCC_Result CCC_flat_double_ended_queue_pop_front ( CCC_Flat_double_ended_queue * queue )

Pop an element from the front of the flat_double_ended_queue. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: ok if the pop was successful. If queue is NULL or the flat_double_ended_queue is empty an input error is returned.

◆ CCC_flat_double_ended_queue_push_back()

void * CCC_flat_double_ended_queue_push_back	(	CCC_Flat_double_ended_queue *	queue,
		void const *	type
	)

Push the user type to the back of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	type	a pointer to the user type to insert into the flat_double_ended_queue.

Returns: a reference to the inserted element.

◆ CCC_flat_double_ended_queue_push_back_range()

CCC_Result CCC_flat_double_ended_queue_push_back_range	(	CCC_Flat_double_ended_queue *	queue,
		size_t	count,
		void const *	type_array
	)

Push the range of user types to the back of the flat_double_ended_queue. O(N).

Parameters

[in]	queue	pointer to the flat_double_ended_queue.
[in]	count	the number of user types in the type_array range.
[in]	type_array	a pointer to the array of user types.

Returns: ok if insertion was successful. If allocation is permitted and a resize is needed but fails an error is returned. If bad input is provided an input error is returned.

Note that if no allocation is permitted the queue behaves as a ring buffer. Therefore, pushing a range that will exceed capacity will overwrite elements at the beginning of the flat_double_ended_queue.

◆ CCC_flat_double_ended_queue_push_front()

void * CCC_flat_double_ended_queue_push_front	(	CCC_Flat_double_ended_queue *	queue,
		void const *	type
	)

Push the user type to the front of the flat_double_ended_queue. O(1) if no allocation permission amortized O(1) if allocation permission is given and a resize is required.

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	type	a pointer to the user type to insert into the flat_double_ended_queue.

Returns: a reference to the inserted element.

◆ CCC_flat_double_ended_queue_push_front_range()

CCC_Result CCC_flat_double_ended_queue_push_front_range	(	CCC_Flat_double_ended_queue *	queue,
		size_t	count,
		void const *	type_array
	)

Push the range of user types to the front of the flat_double_ended_queue. O(N).

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	count	the number of user types in the type_array range.
[in]	type_array	a pointer to the array of user types.

Returns: ok if insertion was successful. If allocation is permitted and a resize is needed but fails an error is returned. If bad input is provided an input error is returned.

Note that if no allocation is permitted the queue behaves as a ring buffer. Therefore, pushing a range that will exceed capacity will overwrite elements at the back of the flat_double_ended_queue.

◆ CCC_flat_double_ended_queue_reserve()

CCC_Result CCC_flat_double_ended_queue_reserve	(	CCC_Flat_double_ended_queue *	queue,
		size_t	to_add,
		CCC_Allocator *	allocate
	)

Reserves space for at least to_add more elements.

Parameters

[in]	queue	a pointer to the flat double ended queue.
[in]	to_add	the number of elements to add to the current size.
[in]	allocate	the allocation function to use to reserve memory.

Returns: the result of the reservation. OK if successful, otherwise an error status is returned.

Note: see the CCC_flat_double_ended_queue_clear_and_free_reserve function if this function is being used for a one-time dynamic reservation.

This function can be used for a dynamic queue with or without allocation permission. If the queue has allocation permission, it will reserve the required space and later resize if more space is needed.

If the queue has been initialized with no allocation permission and no memory this function can serve as a one-time reservation. The flat_double_ended_queue will then act as as ring Buffer when space runs out. This is helpful when a fixed size is needed but that size is only known dynamically at runtime. To free the queue in such a case see the CCC_flat_double_ended_queue_clear_and_free_reserve function.

◆ CCC_flat_double_ended_queue_reverse_begin()

void * CCC_flat_double_ended_queue_reverse_begin ( CCC_Flat_double_ended_queue const * queue )

Return a pointer to the back element of the flat_double_ended_queue. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

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

◆ CCC_flat_double_ended_queue_reverse_end()

void * CCC_flat_double_ended_queue_reverse_end ( CCC_Flat_double_ended_queue const * queue )

Return a pointer to the start element. It may not be accessed. O(1).

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: a pointer to the start sentinel element that may not be accessed.

◆ CCC_flat_double_ended_queue_reverse_next()

void * CCC_flat_double_ended_queue_reverse_next	(	CCC_Flat_double_ended_queue const *	queue,
		void const *	iterator_pointer
	)

Return the next element in the queue moving back to front. O(1).

Parameters

[in]	queue	a pointer to the flat_double_ended_queue.
[in]	iterator_pointer	the current element in the flat_double_ended_queue.

Returns: the element preceding iterator_pointer or NULL if no elements follow.

◆ CCC_flat_double_ended_queue_validate()

CCC_Tribool CCC_flat_double_ended_queue_validate ( CCC_Flat_double_ended_queue const * queue )

Return true if the internal invariants of the flat_double_ended_queue.

Parameters

[in] queue a pointer to the flat_double_ended_queue.

Returns: true if the internal invariants of the queue are held, else false. Error if queue is NULL.

Detailed Description

Initialization Interface

Insert and Remove Interface

Container Types

Deallocation Interface

State Interface

Macro Definition Documentation

◆ CCC_flat_double_ended_queue_emplace_back

◆ CCC_flat_double_ended_queue_emplace_front

◆ CCC_flat_double_ended_queue_from

◆ CCC_flat_double_ended_queue_initialize

◆ CCC_flat_double_ended_queue_with_capacity

◆ CCC_flat_double_ended_queue_with_compound_literal

◆ CCC_flat_double_ended_queue_with_context_compound_literal

Typedef Documentation

◆ CCC_Flat_double_ended_queue

Function Documentation

◆ CCC_flat_double_ended_queue_at()

◆ CCC_flat_double_ended_queue_back()

◆ CCC_flat_double_ended_queue_begin()

◆ CCC_flat_double_ended_queue_capacity()

◆ CCC_flat_double_ended_queue_clear()

◆ CCC_flat_double_ended_queue_clear_and_free()

◆ CCC_flat_double_ended_queue_clear_and_free_reserve()

◆ CCC_flat_double_ended_queue_copy()

◆ CCC_flat_double_ended_queue_count()

◆ CCC_flat_double_ended_queue_data()

◆ CCC_flat_double_ended_queue_end()

◆ CCC_flat_double_ended_queue_front()

◆ CCC_flat_double_ended_queue_insert_range()

◆ CCC_flat_double_ended_queue_is_empty()

◆ CCC_flat_double_ended_queue_next()

◆ CCC_flat_double_ended_queue_pop_back()

◆ CCC_flat_double_ended_queue_pop_front()

◆ CCC_flat_double_ended_queue_push_back()

◆ CCC_flat_double_ended_queue_push_back_range()

◆ CCC_flat_double_ended_queue_push_front()

◆ CCC_flat_double_ended_queue_push_front_range()

◆ CCC_flat_double_ended_queue_reserve()

◆ CCC_flat_double_ended_queue_reverse_begin()

◆ CCC_flat_double_ended_queue_reverse_end()

◆ CCC_flat_double_ended_queue_reverse_next()

◆ CCC_flat_double_ended_queue_validate()