aatree.c

Go to the documentation of this file.

#include "aatree.h"
#include <stdlib.h>
#include <assert.h>

#include "vector.h"

static Vector copout = { NULL, NULL, NULL, sizeof(AANode), 0, 0, 16 };

AANode aaTerminatorNode = { { NULL }, /* &aaTerminatorNode, &aaTerminatorNode, */
    0, -1 };

AANode *AATreeFind(AANode *tree, AATreeKeyLevelType key) {
    AANode *node;
    int loop;
    if (copout.array == NULL) return NULL;
    for (loop = copout.items, node = copout.array; loop > 0; loop--, node++) {
        if (node->key == key)
            return node;
    }
    // the item sought is not in the tree
    return NULL;
}

AANode *AATreeAdd(AANode **tree, AATreeKeyLevelType key) {
    AANode *node;
    // the key must not be the same as the terminator
    assert(key != 0xFFFF);
    if (copout.array == NULL) {
        VectorInit(&copout, 16);
    }
    // attempt to allocate a new node and check for success
    if ((node = VectorAdd(&copout)) != NULL) {
        // initialize the new node
        node->key = key;
        *tree = node;
        return node;
    }
    // failed
    return NULL;
}

AANode *_AATreeRemove(AANode *tree, AATreeRemovalData *rd) {
    AANode *node;
    unsigned int loop;
    if (copout.array == NULL) return NULL;
    for (loop = 0, node = copout.array; loop < copout.items; loop++, node++) {
        if (node->key == rd->key) {
            VectorRemove(&copout, loop);
            if (copout.items)
                return (AANode*)copout.array;
            return &aaTerminatorNode;
        }
    }
    // the item sought is not in the tree
    return NULL;
}

static Bool setExit = FALSE;

static void treeExit(void) {
    VectorDestroy(&copout);
}

void AATreeDestroy(AANode *tree) {
    VectorClear(&copout);
    if (!setExit) {
        atexit(treeExit);
        setExit = TRUE;
    }
}

---