TscTree

TscTree is a generic AVL-balanced binary search tree library for C. It stores application-supplied key and element pointers while keeping the tree structure, balancing information, and node allocation details private.

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

Features

• Generic void * keys and elements
• Application-supplied key comparison callback
• Optional separate key and element destruction callbacks
• AVL balancing
• Exact, less-than-or-equal, and greater-than-or-equal searches
• Ordered forward and reverse traversal
• Ordered callback-based walk
• Insert, replace, and upsert operations
• Remove or delete by node or by key
• Node count and tree-level statistics
• Block-based internal node allocation
• Configurable node block size before first allocation
• Retained status information

Public Objects

The tree itself is opaque:

typedef struct TscTree TscTree;

A tree node exposes only the application data:

typedef struct TscTreeNode
{
    void *key;
    void *element;
} TscTreeNode;

Tree linkage, parent pointers, AVL height information, ownership information, and pool-management fields are private implementation details.

Applications may read node->key and node->element. The key should not be changed directly because doing so could invalidate the ordering of the tree.

Creating a Tree

A tree requires a key comparison callback:

int compare(const void *key1, const void *key2);

The callback returns:

• a value less than zero if key1 sorts before key2
• zero if the keys are equal
• a value greater than zero if key1 sorts after key2

For example:

static int compareInt(const void *a, const void *b)
{
    int av = *(const int *)a;
    int bv = *(const int *)b;

    return (av > bv) - (av < bv);
}

Create the tree with:

TscTree *tree = tscTreeCreate(compareInt, freeKey, freeElement);

The key and element free callbacks are optional and may independently be NULL.

This is useful when, for example, the key points into storage owned by the element. In that case the key free callback can be NULL and the element callback can release the complete object.

Node Allocation

Tree nodes are allocated internally in blocks rather than with a separate malloc() for every node.

The default block size is:

TSC_TREE_DEFAULT_BLOCK_NODES

which is currently 64 nodes.

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

tscTreeSetBlockSize(tree, 256);

Once the first node block has been allocated, the block size is locked for the lifetime of the tree.

tscTreeClear() returns nodes to the tree’s internal free pool and retains the allocated blocks for reuse.

Inserting Nodes

Insert a key and element with:

TscTreeNode *node = tscTreeInsert(tree, key, element);

Keys must not be NULL. Elements may be NULL.

Duplicate keys are rejected with:

TSC_TREE_ERROR_DUPLICATE_KEY

Finding Nodes

Three search operations are provided:

node = tscTreeFind(tree, key);
node = tscTreeFindLE(tree, key);
node = tscTreeFindGE(tree, key);

Their meanings are:

A search that finds no qualifying node returns NULL. This is a normal search result and does not set a NOT_FOUND error.

Ordered Traversal

The first and last nodes are available with:

TscTreeNode *node = tscTreeFirst(tree);
TscTreeNode *node = tscTreeLast(tree);

Forward traversal:

for (node = tscTreeFirst(tree);
     node != NULL;
     node = tscTreeNext(node))
{
    /* use node->key and node->element */
}

Reverse traversal:

for (node = tscTreeLast(tree);
     node != NULL;
     node = tscTreePrevious(node))
{
    /* use node->key and node->element */
}

Applications do not navigate the physical tree structure directly.

Walking the Tree

The library can walk the tree in ascending key order using a callback:

typedef int (*TscTreeWalkFunction)(
    TscTreeNode *node,
    void *context);

Call:

tscTreeWalk(tree, callback, context);

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

The library determines the next node before calling the callback. This means the callback may safely delete the current node.

Deleting or modifying unrelated nodes during the walk is not supported.

Replace and Upsert

tscTreeReplace() replaces an existing entry:

node = tscTreeReplace(tree, newKey, newElement);

The replacement key must compare equal to an existing key.

Replacement is treated as a logical delete and reinsert. Both the key pointer and element pointer are replaced. This is important when a key is embedded in the element storage.

The implementation can reuse the existing internal node, so replacing an existing entry does not require allocation of another node.

tscTreeUpsert() combines insert and replace:

node = tscTreeUpsert(tree, key, element);

If the key does not exist, it is inserted. If an equal key already exists, the existing entry is replaced.

Removing and Deleting

A remove operation removes an entry from the tree without calling the configured free callbacks:

TscTreeStatus status =
    tscTreeRemove(tree, node, &key, &element);

or:

TscTreeStatus status =
    tscTreeRemoveKey(tree, searchKey, &key, &element);

This transfers responsibility for the returned key and element pointers back to the application.

A delete operation removes the entry and invokes the configured free callbacks:

tscTreeDelete(tree, node);

or:

tscTreeDeleteKey(tree, searchKey);

Clearing and Destroying

To empty a tree while retaining its allocated node blocks:

tscTreeClear(tree);

The configured key and element free callbacks are invoked for the active entries.

To destroy the complete tree:

tscTreeDestroy(tree);

This deletes all remaining entries, invokes the configured callbacks, releases the node blocks, and releases the tree object.

Passing NULL to tscTreeDestroy() is permitted.

Statistics

The current number of nodes is returned by:

size_t count = tscTreeCount(tree);

The current number of tree levels is returned by:

size_t levels = tscTreeLevels(tree);

The level convention is:

• empty tree: 0
• root only: 1
• root plus a child: 2

Because the implementation is AVL balanced, tree depth remains logarithmic as entries are inserted and removed.

Status

Operations retain their completion status in the tree object:

TscTreeStatus status = tscTreeGetStatus(tree);

A printable description is available with:

const char *message = tscTreeStatusString(status);

Status values currently include:

TSC_TREE_STATUS_OK
TSC_TREE_ERROR_INVALID_ARGUMENT
TSC_TREE_ERROR_OUT_OF_MEMORY
TSC_TREE_ERROR_WRONG_TREE
TSC_TREE_ERROR_DUPLICATE_KEY
TSC_TREE_ERROR_NOT_FOUND
TSC_TREE_ERROR_BLOCK_SIZE_LOCKED

Example

#include "tsc_tree.h"

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

static int compareInt(const void *a, const void *b)
{
    int av = *(const int *)a;
    int bv = *(const int *)b;

    return (av > bv) - (av < bv);
}

int main(void)
{
    TscTree *tree;
    TscTreeNode *node;
    int a = 30;
    int b = 10;
    int c = 20;

    tree = tscTreeCreate(compareInt, NULL, NULL);
    if (tree == NULL)
        return 1;

    tscTreeInsert(tree, &a, &a);
    tscTreeInsert(tree, &b, &b);
    tscTreeInsert(tree, &c, &c);

    for (node = tscTreeFirst(tree);
         node != NULL;
         node = tscTreeNext(node))
    {
        printf("%d\n", *(int *)node->key);
    }

    printf("Nodes:  %zu\n", tscTreeCount(tree));
    printf("Levels: %zu\n", tscTreeLevels(tree));

    tscTreeDestroy(tree);
    return 0;
}

Output:

10
20
30
Nodes:  3
Levels: 2

Notes

TscTree is intended as a general-purpose ordered container. The library deliberately hides the physical tree structure so applications depend on the supported search and navigation operations rather than AVL implementation details.

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