TscList

TscList is a small generic doubly linked-list library for C.

The library keeps list linkage separate from application data. Each list node contains forward and backward links, a pointer to the owning list, and a void * pointer to the application element.

TscList itself is opaque. Applications work with a TscList * returned by tscListCreate() and use the public TscListNode structure for traversal.

Features

• Doubly linked list with direct access to both head and tail
• Public list nodes that naturally serve as iterators
• O(1) append, prepend, insertion, and removal when the node is known
• Optional callback for freeing application element storage
• Separate remove and delete operations
• In-place list reversal
• Pointer-identity search
• Node ownership checking to detect use of a node with the wrong list
• Retained status from the most recent operation
• Block allocation and recycling of fixed-size linkage nodes
• Configurable node-block size before the first node allocation

Basic use

#include "tsc_list.h"

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    TscList *list;
    TscListNode *node;
    int a = 10;
    int b = 20;
    int c = 30;

    list = tscListCreate(NULL);
    if (list == NULL)
        return 1;

    if (tscListAppend(list, &a) == NULL ||
        tscListAppend(list, &b) == NULL ||
        tscListAppend(list, &c) == NULL)
    {
        tscListDestroy(list);
        return 1;
    }

    for (node = tscListHead(list);
         node != NULL;
         node = node->forward)
    {
        printf("%d\n", *(int *)node->element);
    }

    tscListDestroy(list);
    return 0;
}

Because the free callback is NULL in this example, destroying the list frees only the internal list storage. It does not attempt to free a, b, or c.

Element ownership

The list owns its internal linkage nodes. Application data remains separate.

An optional element-free callback is supplied when the list is created:

TscList *list = tscListCreate(free);

When a callback is configured, tscListDelete(), tscListClear(), and tscListDestroy() invoke it for each non-NULL element being destroyed.

tscListRemove() is intentionally different: it removes the linkage node but returns the element pointer without calling the free callback.

For example:

void *element = tscListRemove(list, node);

if (tscListGetStatus(list) == TSC_LIST_STATUS_OK)
{
    /* The application still owns element. */
}

NULL element pointers are permitted.

Traversal

TscListNode is public and serves as the iterator.

Forward traversal:

for (TscListNode *node = tscListHead(list);
     node != NULL;
     node = node->forward)
{
    /* use node->element */
}

Reverse traversal:

for (TscListNode *node = tscListTail(list);
     node != NULL;
     node = node->backward)
{
    /* use node->element */
}

A node pointer becomes invalid immediately after that node is removed or deleted. The library may recycle its storage for a later insertion.

When deleting while traversing, save the next node before deleting the current one:

TscListNode *node = tscListHead(list);

while (node != NULL)
{
    TscListNode *next = node->forward;

    if (/* delete this element */)
        tscListDelete(list, node);

    node = next;
}

Insertion and removal

The primary modification functions are:

TscListNode *tscListAppend(
    TscList *list,
    void *element);

TscListNode *tscListPrepend(
    TscList *list,
    void *element);

TscListNode *tscListInsertBefore(
    TscList *list,
    TscListNode *position,
    void *element);

TscListNode *tscListInsertAfter(
    TscList *list,
    TscListNode *position,
    void *element);

void *tscListRemove(
    TscList *list,
    TscListNode *node);

TscListStatus tscListDelete(
    TscList *list,
    TscListNode *node);

A position or node supplied to an operation must belong to the specified list. The library retains an owner pointer in each active node and reports TSC_LIST_ERROR_WRONG_LIST when this check fails.

Head, tail, count, and find

TscListNode *tscListHead(const TscList *list);
TscListNode *tscListTail(const TscList *list);
size_t tscListCount(const TscList *list);

TscListNode *tscListFind(
    TscList *list,
    const void *element);

tscListFind() compares element pointers, not the contents of the objects to which they point.

A NULL result from tscListFind() simply means that no matching element pointer was found; it is not an error.

Reversing a list

TscListStatus tscListReverse(TscList *list);

This reverses the list in place. No nodes are allocated or freed.

Clearing and destroying

TscListStatus tscListClear(TscList *list);
void tscListDestroy(TscList *list);

tscListClear() removes all active nodes but leaves the list object and its allocated node blocks available for reuse.

tscListDestroy() destroys the active elements as appropriate, releases all node blocks, and frees the list object itself.

Passing NULL to tscListDestroy() is permitted.

Node allocation

TscList does not normally call malloc() and free() for every individual linkage node. Nodes are allocated internally in blocks and recycled through a private free-node pool.

The default block size is:

TSC_LIST_DEFAULT_BLOCK_NODES

which is currently 64 nodes.

An application that knows its expected usage pattern may override this before the first node block is allocated:

TscList *list = tscListCreate(NULL);

if (list != NULL)
    tscListSetBlockSize(list, 256);

Once the first node block has been allocated, the block size is locked for the lifetime of that list. Clearing the list does not unlock it.

Node blocks are allocated lazily, so creating an empty list does not allocate a block of nodes.

Status handling

Each valid TscList retains the status of the most recent list operation.

TscListStatus status = tscListGetStatus(list);

Current status values are:

TSC_LIST_STATUS_OK
TSC_LIST_ERROR_INVALID_ARGUMENT
TSC_LIST_ERROR_OUT_OF_MEMORY
TSC_LIST_ERROR_WRONG_LIST
TSC_LIST_ERROR_BLOCK_SIZE_LOCKED

A printable description is available through:

const char *tscListStatusString(TscListStatus status);

Functions that naturally return a pointer use NULL to indicate either an error or, where documented, a normal empty/not-found result. tscListGetStatus() can be used when the distinction matters.

Current scope

The initial TscList API intentionally remains small. It does not currently provide sorting, comparison-based searches, separate iterator objects, or direct cross-list node movement.

The public node representation provides straightforward forward and backward iteration while the opaque list object allows the internal allocation and bookkeeping implementation to change without exposing those details to applications.