TscDeque

TscDeque is a generic double-ended queue library for C. It stores application-supplied element pointers while keeping the segmented storage, block linkage, indexes, allocation details, and bookkeeping private.

The API is designed to follow the same general style as the other TSC support libraries, including TscList, TscTree, and TscHash.

Features

• Generic void * elements
• Efficient insertion at both ends
• Efficient removal at both ends
• FIFO queue operation
• LIFO stack operation
• Double-ended queue operation
• Optional element destruction callback
• Front-to-back callback-based walk
• Element count and empty-state inspection
• Block-based internal element storage
• Configurable element block size before first allocation
• Internal block reuse after removal or clear
• Retained status information
• NULL elements permitted

Public Object

The deque itself is opaque:

typedef struct TscDeque TscDeque;

The library does not expose public nodes or internal element slots.

Applications interact with stored elements through the deque operations rather than navigating the physical storage structure.

This allows the implementation to use segmented storage internally without making applications dependent on block linkage, indexes, or allocation details.

Creating a Deque

Create a deque with:

TscDeque *deque =
    tscDequeCreate(freeElement);

The element free callback is optional and may be NULL.

Its type is:

typedef void (*TscDequeFreeFunction)(
    void *element);

When configured, the callback is used by operations that destroy elements, including delete, clear, and destroy.

For example:

TscDeque *deque =
    tscDequeCreate(free);

may be used when every non-NULL element stored in the deque is individually allocated with malloc().

A newly created deque is empty and does not allocate an element-storage block until one is needed.

Element Storage

The deque stores application-supplied pointers:

void *element;

The library stores the pointer itself and does not copy the object it references.

NULL is a valid element value.

This is important for operations such as:

tscDequeFront()
tscDequeBack()
tscDequePopFront()
tscDequePopBack()

because these functions also return NULL when the deque is empty.

When the distinction matters, the application should inspect the retained status with:

tscDequeGetStatus(deque);

A successfully accessed or removed NULL element leaves the status as:

TSC_DEQUE_STATUS_OK

An attempt to access or remove an element from an empty deque sets:

TSC_DEQUE_ERROR_EMPTY

Block Allocation

Element storage is allocated internally in blocks rather than with a separate allocation for every element.

The default block size is:

TSC_DEQUE_DEFAULT_BLOCK_ELEMENTS

which is currently 64 element slots.

An application that knows its expected usage may change the block size before the first storage block is allocated:

tscDequeSetBlockSize(deque, 256);

Any nonzero block size is valid.

Once the first storage block has been allocated, the block size is locked for the lifetime of the deque.

Removing all elements does not unlock the block size.

Calling tscDequeClear() also does not unlock the block size because allocated blocks are retained for reuse.

Segmented Storage

The deque uses segmented internal storage.

Each storage block contains a fixed number of element slots and is linked to neighboring blocks. Active elements occupy a range within each block.

The initial block begins near its center so the deque can grow efficiently toward either the front or the back.

When an active end reaches the boundary of its current block, another block is obtained and attached at that end.

No push or pop operation requires moving all existing elements.

Empty blocks are detached from the active deque and retained on an internal free-block list for later reuse.

The internal representation is deliberately private and should not be relied upon by applications.

Pushing Elements

Insert an element at the front with:

TscDequeStatus status =
    tscDequePushFront(deque, element);

Insert an element at the back with:

TscDequeStatus status =
    tscDequePushBack(deque, element);

Both operations permit element == NULL.

A successful push increases the deque count by one.

Insertion at either end is an O(1) operation except when a new internal storage block must be allocated.

If allocation fails, the existing contents and ordering of the deque remain unchanged.

Inspecting the Ends

Inspect the front element without removing it with:

void *element = tscDequeFront(deque);

Inspect the back element without removing it with:

void *element = tscDequeBack(deque);

These operations do not change the deque.

If the deque is empty, they return NULL and set:

TSC_DEQUE_ERROR_EMPTY

Because a stored element may itself be NULL, use tscDequeGetStatus() when it is necessary to distinguish the two cases.

For example:

void *element = tscDequeFront(deque);

if (element == NULL)
{
    if (tscDequeGetStatus(deque) == TSC_DEQUE_ERROR_EMPTY)
    {
        /* deque is empty */
    }
    else
    {
        /* the front element is NULL */
    }
}

Popping Elements

A pop removes an element without invoking the configured free callback.

Remove and return the front element with:

void *element =
    tscDequePopFront(deque);

Remove and return the back element with:

void *element =
    tscDequePopBack(deque);

Responsibility for the returned element remains with the application.

If the deque is empty, the operation returns NULL and sets:

TSC_DEQUE_ERROR_EMPTY

A successful pop of a stored NULL element also returns NULL, but the retained status is:

TSC_DEQUE_STATUS_OK

Deleting Elements

A delete removes an element and invokes the configured free callback when appropriate.

Delete the front element with:

tscDequeDeleteFront(deque);

Delete the back element with:

tscDequeDeleteBack(deque);

If a free callback was configured and the removed element is non-NULL, the callback is invoked.

If the deque is empty, the operation fails with:

TSC_DEQUE_ERROR_EMPTY

This preserves the TSC container convention that removal transfers an object back to the application while deletion destroys the stored object.

Queue Usage

TscDeque can be used directly as a FIFO queue.

Push new elements at the back:

tscDequePushBack(deque, element);

and remove the oldest element from the front:

element = tscDequePopFront(deque);

For example:

tscDequePushBack(deque, job1);
tscDequePushBack(deque, job2);
tscDequePushBack(deque, job3);

job = tscDequePopFront(deque);  /* job1 */
job = tscDequePopFront(deque);  /* job2 */
job = tscDequePopFront(deque);  /* job3 */

The opposite orientation is also valid: applications may push at the front and pop from the back.

Stack Usage

TscDeque can also be used directly as a LIFO stack.

For example, using the back as the top of the stack:

tscDequePushBack(deque, item1);
tscDequePushBack(deque, item2);
tscDequePushBack(deque, item3);

item = tscDequePopBack(deque);  /* item3 */
item = tscDequePopBack(deque);  /* item2 */
item = tscDequePopBack(deque);  /* item1 */

The front may instead be used consistently as the stack end.

A separate queue or stack container is therefore not required for normal use.

Walking the Deque

The library can walk every active element from front to back using a callback:

typedef int (*TscDequeWalkFunction)(
    void *element,
    void *context);

Call:

tscDequeWalk(deque, callback, context);

The callback returns zero to continue or nonzero to stop the walk successfully.

For example:

static int printElement(
    void *element,
    void *context)
{
    (void)context;

    printf("%s\n", (const char *)element);
    return 0;
}

Then:

tscDequeWalk(deque, printElement, NULL);

Walk order is significant and is always from the logical front of the deque toward the logical back.

Unlike the walk operations of some other TSC containers, modifying the deque during a deque walk is not supported.

The callback may stop the walk early by returning a nonzero value. Early termination is considered successful and tscDequeWalk() returns:

TSC_DEQUE_STATUS_OK

Count and Empty State

The current number of active elements is returned by:

size_t count =
    tscDequeCount(deque);

For a NULL deque pointer, tscDequeCount() returns zero.

The empty state can be tested directly with:

int empty =
    tscDequeIsEmpty(deque);

The function returns nonzero when the deque is empty and zero when at least one element is present.

A NULL deque pointer is also reported as empty.

Clearing a Deque

To remove all elements while retaining allocated storage for reuse:

tscDequeClear(deque);

The configured free callback is invoked for each non-NULL active element.

All active storage blocks are detached from the deque and retained internally for later reuse.

After a successful clear:

tscDequeCount(deque) == 0
tscDequeIsEmpty(deque) != 0

The deque remains valid and may immediately be reused.

Its configured block size remains locked if storage has previously been allocated.

Destroying a Deque

Destroy the complete deque with:

tscDequeDestroy(deque);

All remaining active elements are destroyed using the configured free callback when appropriate.

All active and retained storage blocks are released, followed by the deque object itself.

Passing NULL to tscDequeDestroy() is permitted.

Status

Operations retain their completion status in the deque object:

TscDequeStatus status =
    tscDequeGetStatus(deque);

A printable description is available with:

const char *message =
    tscDequeStatusString(status);

Status values currently include:

TSC_DEQUE_STATUS_OK
TSC_DEQUE_ERROR_INVALID_ARGUMENT
TSC_DEQUE_ERROR_OUT_OF_MEMORY
TSC_DEQUE_ERROR_EMPTY
TSC_DEQUE_ERROR_BLOCK_SIZE_LOCKED

Their meanings are:

Example

#include "tsc_deque.h"

#include <stdio.h>

int main(void)
{
    TscDeque *deque;
    const char *item;

    deque = tscDequeCreate(NULL);
    if (deque == NULL)
        return 1;

    tscDequePushBack(deque, "one");
    tscDequePushBack(deque, "two");
    tscDequePushFront(deque, "zero");

    printf("Count: %zu\n", tscDequeCount(deque));

    while (!tscDequeIsEmpty(deque))
    {
        item = (const char *)tscDequePopFront(deque);
        printf("%s\n", item);
    }

    tscDequeDestroy(deque);
    return 0;
}

Output:

Count: 3
zero
one
two

Complexity

The primary deque operations have the following expected complexity:

A push may additionally require allocation of a storage block.

Notes

TscDeque is intended as a general-purpose double-ended sequential container.

It is particularly appropriate when an application needs queue behavior, stack behavior, or efficient insertion and removal at both ends.

The library deliberately hides its physical storage structure so applications depend on logical deque operations rather than block linkage or internal indexes.

Unlike TscList, the deque does not expose nodes and does not support arbitrary insertion or removal in the middle of the sequence.

Unlike a future vector-style container, the deque does not provide indexed random access.

Applications requiring arbitrary linked-list insertion or node traversal should use TscList.

Applications requiring sorted associative lookup should use TscTree.

Applications requiring fast unordered keyed lookup should use TscHash.

The current implementation is not designed to provide synchronization between threads. Applications requiring concurrent access should provide appropriate external locking.