TscVector

TscVector is a generic dynamic vector library for C. It stores application-supplied element pointers in a contiguous array while keeping allocation, capacity management, growth policy, and bookkeeping private.

The API follows the same general style and ownership conventions as the other TSC container libraries, including TscList, TscTree, TscHash, and TscDeque.

Features

• Generic void * elements
• Contiguous pointer storage
• O(1) indexed access
• Efficient append and removal from the back
• Arbitrary indexed insertion and removal
• Explicit logical size and allocated capacity
• Automatic capacity growth
• Explicit capacity reservation
• Explicit shrink-to-fit support
• Vector resizing with NULL initialization
• Optional element destruction callback
• Front-to-back callback-based walk
• Retained status information
• NULL elements permitted

Public Object

The vector itself is opaque:

typedef struct TscVector TscVector;

Applications do not have access to the internal element array, capacity, growth policy, or bookkeeping.

The logical vector consists of every index from zero through count - 1.

Each logical position contains a void * value and may contain either a non-NULL pointer or NULL.

Allocated capacity beyond count is internal storage and is not part of the logical vector.

For example:

count = 4
capacity = 8

index       0       1       2       3
          +-------+-------+-------+-------+-------+-------+-------+-------+
elements  |   A   |   B   | NULL  |   D   |       |       |       |       |
          +-------+-------+-------+-------+-------+-------+-------+-------+
             logical vector              |       unused capacity         |

Index 2 exists and contains NULL.

Indexes 4 through 7 do not logically exist even though storage has been allocated for them.

Creating a Vector

Create a vector with:

TscVector *vector =
    tscVectorCreate(freeElement);

The element free callback is optional and may be NULL.

Its type is:

typedef void (*TscVectorFreeFunction)(
    void *element);

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

For example:

TscVector *vector =
    tscVectorCreate(free);

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

A newly created vector is empty:

count    = 0
capacity = 0

The element array is allocated only when storage is required.

Element Storage

The vector stores application-supplied pointers:

void *element;

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

NULL is a valid logical element value.

This creates an important distinction between a logical position containing NULL and an index that does not exist.

For example, if:

count = 3

index       0       1       2
          +-------+-------+-------+
elements  |   A   | NULL  |   C   |
          +-------+-------+-------+

then:

tscVectorGet(vector, 1);

returns NULL with status:

TSC_VECTOR_STATUS_OK

because index 1 exists and contains a NULL element.

However:

tscVectorGet(vector, 3);

returns NULL with status:

TSC_VECTOR_ERROR_OUT_OF_RANGE

because index 3 does not exist.

When the distinction matters, inspect the retained status with:

tscVectorGetStatus(vector);

Count and Capacity

TscVector maintains two separate sizes.

The logical number of elements is returned by:

size_t count =
    tscVectorCount(vector);

The number of currently allocated element slots is returned by:

size_t capacity =
    tscVectorCapacity(vector);

The following relationship is always maintained:

count <= capacity

Only indexes less than count are valid logical vector positions.

Capacity beyond count is an implementation resource and must not be interpreted as containing vector elements.

For a NULL vector pointer:

tscVectorCount(NULL)

and:

tscVectorCapacity(NULL)

return zero.

The empty state can be tested with:

int empty =
    tscVectorIsEmpty(vector);

The function returns nonzero when count is zero and zero when at least one logical element exists.

A NULL vector pointer is also reported as empty.

Automatic Capacity Growth

When an operation requires more element slots than the current capacity, the vector automatically grows its internal element array.

The exact growth policy is private to the implementation and is not part of the public API contract.

Applications should therefore not depend on a particular capacity after an automatic growth operation.

The only guarantee is:

capacity >= count

after a successful operation.

Applications that know their expected storage requirements may use tscVectorReserve() to reduce repeated reallocations.

Reserving Capacity

Ensure capacity for at least a specified number of elements with:

tscVectorReserve(vector, capacity);

For example:

tscVectorReserve(vector, 1000);

ensures that the vector can hold at least 1000 logical elements before another capacity increase is required.

Reserve does not change the logical element count.

For example:

before:

count    = 3
capacity = 8

after tscVectorReserve(vector, 1000):

count    = 3
capacity >= 1000

Calling reserve with a value less than or equal to the existing capacity is successful and leaves the allocation unchanged.

tscVectorReserve() never shrinks the vector.

Appending Elements

Append an element to the logical end of the vector with:

TscVectorStatus status =
    tscVectorAppend(vector, element);

The new element is placed at the previous value of count.

For example:

before:

count = 3

[ A ][ B ][ C ]

tscVectorAppend(vector, D);

after:

count = 4

[ A ][ B ][ C ][ D ]

NULL elements are permitted:

tscVectorAppend(vector, NULL);

If additional capacity is required, the vector grows automatically.

Append is an amortized O(1) operation.

Inserting Elements

Insert an element at an arbitrary logical position with:

TscVectorStatus status =
    tscVectorInsert(vector, index, element);

Valid insertion indexes are:

0 through count inclusive

The existing element at index and all later elements are shifted one position toward the end.

For example:

before:

[ A ][ B ][ C ][ D ]

tscVectorInsert(vector, 2, X);

after:

[ A ][ B ][ X ][ C ][ D ]

Insertion at index zero inserts at the beginning.

Insertion at:

tscVectorCount(vector)

is equivalent to append.

An insertion index greater than count fails with:

TSC_VECTOR_ERROR_OUT_OF_RANGE

NULL elements are permitted.

Because later elements may need to be shifted, arbitrary insertion is O(n).

Indexed Access

Return the element stored at an existing logical position with:

void *element =
    tscVectorGet(vector, index);

Valid indexes are:

0 through count - 1

The vector is not modified.

If the index is outside the logical vector, NULL is returned and status is set to:

TSC_VECTOR_ERROR_OUT_OF_RANGE

Because a valid vector element may itself contain NULL, applications should inspect status when the distinction is important.

For example:

void *element =
    tscVectorGet(vector, index);

if (element == NULL)
{
    if (tscVectorGetStatus(vector) ==
        TSC_VECTOR_ERROR_OUT_OF_RANGE)
    {
        /* index does not exist */
    }
    else
    {
        /* index exists and contains NULL */
    }
}

Indexed access is O(1).

Setting an Element

Change the element stored at an existing logical position with:

tscVectorSet(vector, index, element);

Set() does not insert a new position and does not change count.

For example:

before:

[ A ][ B ][ C ][ D ]

tscVectorSet(vector, 2, X);

after:

[ A ][ B ][ X ][ D ]

Valid indexes are:

0 through count - 1

If the previous element is non-NULL, differs from the new pointer, and a free callback was configured, the previous element is destroyed using that callback.

For example:

tscVectorSet(vector, 2, newObject);

replaces the previous object at index 2 and transfers ownership of newObject to the vector under the normal ownership rules.

Setting an element to the same pointer already stored at that index is a successful no-op.

This rule prevents the vector from freeing an object and then retaining the same now-invalid pointer.

Setting an element to NULL is permitted.

For example:

tscVectorSet(vector, 2, NULL);

leaves index 2 as a valid logical position containing a NULL element.

Removing Elements

A remove deletes a logical position and returns its element without invoking the configured free callback.

Remove an arbitrary element with:

void *element =
    tscVectorRemove(vector, index);

Later elements are shifted one position toward the beginning.

For example:

before:

[ A ][ B ][ C ][ D ]

element = tscVectorRemove(vector, 1);

returned:

B

after:

[ A ][ C ][ D ]

Ownership of the returned element belongs to the application.

If the index is outside the logical vector, the function returns NULL and sets:

TSC_VECTOR_ERROR_OUT_OF_RANGE

Because a successfully removed element may itself be NULL, use tscVectorGetStatus() when the distinction matters.

Arbitrary removal is O(n) because later elements may need to be shifted.

Deleting Elements

A delete removes a logical position and destroys its element using the configured free callback when appropriate.

Delete an arbitrary element with:

tscVectorDelete(vector, index);

Later elements are shifted one position toward the beginning.

The distinction between remove and delete follows the normal TSC container ownership convention:

Remove  -> return the element to the application
Delete  -> destroy the element

If the index is outside the logical vector, delete fails with:

TSC_VECTOR_ERROR_OUT_OF_RANGE

Removing from the Back

The final logical element can be removed efficiently with:

void *element =
    tscVectorPopBack(vector);

This removes and returns the element without invoking the configured free callback.

Because no remaining elements need to be shifted, tscVectorPopBack() is O(1).

If the vector is empty, it returns NULL and sets:

TSC_VECTOR_ERROR_EMPTY

A successfully removed NULL element also returns NULL, but status remains:

TSC_VECTOR_STATUS_OK

To remove and destroy the final element instead, use:

tscVectorDeleteBack(vector);

This invokes the configured free callback for the removed non-NULL element when appropriate.

First and Last Elements

Inspect the first logical element without removing it with:

void *element =
    tscVectorFirst(vector);

Inspect the last logical element with:

void *element =
    tscVectorLast(vector);

Neither operation changes the vector.

If the vector is empty, the function returns NULL and sets:

TSC_VECTOR_ERROR_EMPTY

Because a valid first or last element may itself be NULL, inspect the retained status when the distinction matters.

Both operations are O(1).

Resizing the Vector

Change the logical number of vector positions with:

tscVectorResize(vector, count);

Resize changes the logical element count rather than merely changing allocation capacity.

Growing

When the vector grows, every newly created logical position is initialized to NULL.

For example:

before:

count = 3

[ A ][ B ][ C ]

tscVectorResize(vector, 6);

after:

count = 6

[ A ][ B ][ C ][NULL][NULL][NULL]

Indexes 3, 4, and 5 now exist and may be accessed with tscVectorGet() or changed with tscVectorSet().

If additional capacity is required, the internal array grows automatically.

Shrinking

When the vector shrinks, positions beyond the new count cease to exist.

For example:

before:

count = 6

[ A ][ B ][ C ][ D ][ E ][ F ]

tscVectorResize(vector, 3);

after:

count = 3

[ A ][ B ][ C ]

Discarded non-NULL elements are destroyed using the configured free callback when appropriate.

Shrinking the logical vector does not reduce allocated capacity.

Shrinking Capacity

Unused allocated capacity can be explicitly released with:

tscVectorShrinkToFit(vector);

This reduces capacity to the minimum required for the current logical element count.

For example:

before:

count    = 20
capacity = 128

after tscVectorShrinkToFit(vector):

count    = 20
capacity = 20

The logical elements and their order are unchanged.

If the vector is empty, shrink-to-fit may release the element array completely:

count    = 0
capacity = 0

Normal remove, delete, pop, resize, and clear operations do not automatically shrink capacity.

This allows allocated storage to be reused efficiently.

Walking the Vector

The library can walk every logical element in increasing index order using a callback:

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

Call:

tscVectorWalk(vector, callback, context);

Traversal order is:

0, 1, 2, ... count - 1

The callback receives the stored element pointer, including NULL if the logical position contains a NULL element.

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

For example:

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

    if (element == NULL)
        printf("(null)\n");
    else
        printf("%s\n", (const char *)element);

    return 0;
}

Then:

tscVectorWalk(vector, printElement, NULL);

Early termination is considered successful and tscVectorWalk() returns:

TSC_VECTOR_STATUS_OK

Modifying the vector during a walk is not supported.

Clearing a Vector

Remove all logical elements while retaining allocated capacity with:

tscVectorClear(vector);

The configured free callback is invoked for every non-NULL logical element when appropriate.

After a successful clear:

count = 0

but capacity is retained.

For example:

before:

count    = 100
capacity = 128

after tscVectorClear(vector):

count    = 0
capacity = 128

The vector remains valid and may immediately be reused without reallocating until the retained capacity is exceeded.

To also release unused element-array storage, call:

tscVectorShrinkToFit(vector);

after clearing.

Destroying a Vector

Destroy the complete vector with:

tscVectorDestroy(vector);

All remaining non-NULL logical elements are destroyed using the configured free callback when appropriate.

The internal element array is released, followed by the vector object itself.

Passing NULL to tscVectorDestroy() is permitted.

Status

Operations retain their completion status in the vector object:

TscVectorStatus status =
    tscVectorGetStatus(vector);

A printable description is available with:

const char *message =
    tscVectorStatusString(status);

Status values currently include:

TSC_VECTOR_STATUS_OK
TSC_VECTOR_ERROR_INVALID_ARGUMENT
TSC_VECTOR_ERROR_OUT_OF_MEMORY
TSC_VECTOR_ERROR_OUT_OF_RANGE
TSC_VECTOR_ERROR_EMPTY

Their meanings are:

Example

#include "tsc_vector.h"

#include <stdio.h>

int main(void)
{
    TscVector *vector;
    size_t index;

    vector = tscVectorCreate(NULL);
    if (vector == NULL)
        return 1;

    tscVectorAppend(vector, "one");
    tscVectorAppend(vector, "two");
    tscVectorAppend(vector, "three");

    tscVectorInsert(vector, 1, "one and a half");

    for (index = 0;
         index < tscVectorCount(vector);
         ++index)
    {
        printf(
            "%zu: %s\n",
            index,
            (const char *)tscVectorGet(vector, index));
    }

    tscVectorDestroy(vector);
    return 0;
}

Output:

0: one
1: one and a half
2: two
3: three

Stack Usage

Because append and pop-back are efficient, TscVector can also be used as a simple LIFO stack.

Push elements with:

tscVectorAppend(vector, item);

and pop them with:

item = tscVectorPopBack(vector);

For example:

tscVectorAppend(vector, item1);
tscVectorAppend(vector, item2);
tscVectorAppend(vector, item3);

item = tscVectorPopBack(vector);  /* item3 */
item = tscVectorPopBack(vector);  /* item2 */
item = tscVectorPopBack(vector);  /* item1 */

For applications requiring efficient insertion and removal at both ends, TscDeque is generally a better choice.

Complexity

The primary vector operations have the following expected complexity:

Choosing TscVector

TscVector is intended for ordered collections where indexed access and compact contiguous pointer storage are important.

Use TscVector when:

• elements are naturally identified by numeric position;
• frequent indexed access is required;
• most additions occur at the end;
• compact pointer storage is desirable;
• traversal in insertion/index order is useful.

Other TSC containers may be more appropriate for different access patterns.

Use TscList when arbitrary insertion and removal through linked structure is more important than indexed access.

Use TscDeque when efficient insertion and removal are required at both ends.

Use TscTree when ordered key-based lookup is required.

Use TscHash when fast unordered key-based lookup is required.

Notes

TscVector is a dynamic contiguous array of pointers, not an array of application objects.

The vector stores void * values supplied by the application.

Every index less than count is a valid logical position, including positions containing NULL.

Allocated slots at indexes greater than or equal to count are unused capacity and are not logical vector elements.

The distinction between logical size and capacity is fundamental to the API.

The vector does not automatically shrink its allocation as elements are removed. This allows storage to be reused efficiently and avoids repeated allocation activity. Applications that need to return unused storage to the allocator may explicitly call tscVectorShrinkToFit().

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