Low Level

A binary tree node insertion function

Posted by Codehead on September 11, 2008 at 1:16 pm

I was working on this for a few days and came up with 3 versions of this function, don’t even ask for the first one.
Here is the second version which is inspired by K&R’s example:

(Just read BTree as Binary Tree)

/** First Version **/
void BTree_Store(BTree *t, char *key, void *elem)
{
       t->root = BTree_Install(t, t->root, key, elem);
}
 
Node *BTree_Install(BTree *t, Node *parent, char *key, void *elem)
{
       int cmpResult;
 
       if (parent == NULL)
              parent        = BTree_NewNode(t, key, elem);
       else {
              cmpResult = t->cmpfn(parent->key, key, BTREE_MAX_KEY_SIZE);
              if (cmpResult == 0) 
                     memcpy(parent->elem, elem, t->elemSize);
              else if (cmpResult < 0)
                     parent->lnode = BTree_Install(t, parent->lnode, key, elem);
              else
                     parent->rnode = BTree_Install(t, parent->rnode, key, elem);
       }
       return parent;
}

The problem with this (or my problem ;)) is that I don’t like creation of stack frames and local variables over and over here, it might need like 40 of them and I knew I could do better so I came up with this version:

/** Second Version **/
void BTree_Store(BTree *t, char *key, void *elem)
{
       Node **n;
       int cmpResult;
 
       n = &t->root;
       while (*n != NULL) {            
              cmpResult = t->cmpfn((*n)->key, key, BTREE_MAX_KEY_SIZE);
              if (cmpResult == 0) 
                     break;
              else if (cmpResult < 0)
                     n = &((*n)->lnode);
              else
                     n = &((*n)->rnode);
       }
 
       if (cmpResult == 0)
              memcpy((*n)->elem, elem, t->elemSize);
       else
              *n = BTree_NewNode(t, key, elem);
}

I actually love this version, it’s quick, compact and right to the point.
Here is how the node and the tree structures look like:

struct node {
       char   *key;         /* Owned by tree */
       void   *elem;        /* Owned by tree */
       struct node *lnode;
       struct node *rnode;
};
 
typedef struct node Node;
 
struct btree {
       Node   *root;
       int    elemSize;
       int    numNodes;
       int    memUsed;
       int    (*cmpfn)(const char *, const char *, size_t);
};
 
typedef struct btree BTree;

The cmpfn is strncmp by defaults because keys are char *, here are the tree & node construction and destruction functions:

void BTree_Init(BTree *t, int elemSize, int (*cmpfn)(const char *, const char *, size_t))
{
       t->elemSize = elemSize;
       t->cmpfn    = cmpfn != NULL ? cmpfn : BTREE_DFLT_CMP_FN;
       t->numNodes = 0;
       t->memUsed  = 0;
       t->root     = NULL;
}
 
void BTree_Dispose(BTree *t) 
{
       BTree_DisposeNodeRecursive(t, t->root);
}
 
static Node *BTree_NewNode(BTree *t, char *key, void *elem)
{
       Node *n;
 
       if (BTREE_NODE_SIZE(t, key) > BTREE_MEM_LIMIT) {
              printf("BTree Error: Not enough memory");
              BTree_Dispose(t);
              exit(0);
       }
 
       n             = (Node *) malloc(sizeof(Node));
       n->elem       = malloc(t->elemSize);
       memcpy(n->elem, elem, t->elemSize);
 
       n->key        = (char *) malloc(strlen(key) + 1); /* +1 for '\0' */
       strcpy(n->key, key);
 
       n->lnode      = NULL;
       n->rnode      = NULL;
 
       t->memUsed   += BTREE_NODE_SIZE(t, key);
       t->numNodes++;
 
       return n;
}
 
static void BTree_DisposeNode(BTree * t, Node *n) 
{
       t->memUsed  -= BTREE_NODE_SIZE(t, n->key);
       t->numNodes--;
       free(n->key);
       free(n->elem);
       free(n);
}
 
static void BTree_DisposeNodeRecursive(BTree *t, Node *n)
{
       if (n->lnode != NULL)
              BTree_DisposeNodeRecursive(t, n->lnode);
 
       if (n->rnode != NULL)
              BTree_DisposeNodeRecursive(t, n->rnode);
 
       BTree_DisposeNode(t, n);
}

Here is the BTREE_NODE_SIZE macro:

#define BTREE_NODE_SIZE(t, k)      sizeof(Node) + strlen(k) + 1 + t->elemSize

And here is the search function:

Node *BTree_FindNode(BTree *t, char *key) 
{
       Node *n;
       int cmpResult;
 
       n = t->root;
       while (n != NULL) {
              cmpResult = t->cmpfn(n->key, key, BTREE_MAX_KEY_SIZE);              
              if (cmpResult == 0)
                     return n;
              else if (cmpResult < 0 && n->lnode != NULL)
                     n = n->lnode;
              else if (n->rnode != NULL)
                     n = n->rnode;
              else
                     break;
       }
 
       return BTREE_KEY_NOT_FOUND;
}
 
void *BTree_Get(BTree *t, char *key)
{
       Node *n;
       n = BTree_FindNode(t, key);
       return n != BTREE_KEY_NOT_FOUND ? n->elem : BTREE_KEY_NOT_FOUND;
}

The only problem with this tree is that if you store sorted data you will end up with a linked list rather than a binary search tree so I’m working on a self balancing binary search tree which is very chalanging but I love chalanges ;)

Archived under C Programming, Low Level Comments