Back to index

lightning-sunbird  0.9+nobinonly
Classes | Defines | Typedefs | Functions
patricia.c File Reference
#include <string.h>
#include <stdlib.h>
#include "patricia.h"
#include "nsAEDefs.h"

Go to the source code of this file.

Classes

struct  TNodeTag
struct  TPatriciaTree

Defines

#define TestKeyBit(key, bit)   ( (key[bit >> 3] & (1 << (bit & 7))) != 0 )
#define CompareKeyBits(key1, key2, bit)   ( (key1[bit >> 3] & (1 << (bit & 7))) == (key2[bit >> 3] & (1 << (bit & 7))) )

Typedefs

typedef struct TNodeTag TNode

Functions

static TNodeMakeNewNode (TPatriciaTree *tree, const unsigned char *key, short bit, void *nodeData)
static TNodeMakeHeadNode (TPatriciaTree *tree)
static TNodeInternalSearch (TPatriciaTree *tree, TNode *x, const unsigned char *key)
static int InternalTraverse (TPatriciaTree *tree, TNode *x, NodeTraverseFunction traverseFunc, void *arg1, void *arg2)
static int TraverseAndFree (TPatriciaTree *tree, TNode *x, NodeFreeFunction freeFunc, void *refCon)
PatriciaTreeRef PatriciaInitTree (long numKeyBits)
void PatriciaFreeTree (PatriciaTreeRef treeRef, NodeFreeFunction freeFunc, void *refCon)
int PatriciaSearch (PatriciaTreeRef treeRef, const unsigned char *key, void **data)
int PatriciaInsert (PatriciaTreeRef treeRef, NodeReplaceFunction replaceFunc, const unsigned char *key, void *data, void *refCon)
int PatriciaTraverse (PatriciaTreeRef treeRef, NodeTraverseFunction traverseFunc, void *arg, void *refCon)
long PatriciaGetNumNodes (PatriciaTreeRef treeRef)

Class Documentation

struct TNodeTag

Definition at line 83 of file patricia.c.

Collaboration diagram for TNodeTag:
Class Members
short bit
void * data
unsigned char * key
struct TNodeTag * left
long nodeID
struct TNodeTag * right
struct TPatriciaTree

Definition at line 93 of file patricia.c.

Collaboration diagram for TPatriciaTree:
Class Members
TNode * headNode
long keySize
long numKeyBits
long numNodes

Define Documentation

#define CompareKeyBits (   key1,
  key2,
  bit 
)    ( (key1[bit >> 3] & (1 << (bit & 7))) == (key2[bit >> 3] & (1 << (bit & 7))) )

Definition at line 104 of file patricia.c.

#define TestKeyBit (   key,
  bit 
)    ( (key[bit >> 3] & (1 << (bit & 7))) != 0 )

Definition at line 103 of file patricia.c.


Typedef Documentation

typedef struct TNodeTag TNode

Function Documentation

static TNode* InternalSearch ( TPatriciaTree tree,
TNode x,
const unsigned char *  key 
) [static]

Definition at line 200 of file patricia.c.

{
       TNode  *p;

       AE_ASSERT(x, "No node");

       do {
              p = x;
              
              if (TestKeyBit(key, x->bit))
                     x = x->right;
              else
                     x = x->left;
              
       } while (p->bit > x->bit);
       
       return x;
}

Here is the caller graph for this function:

static int InternalTraverse ( TPatriciaTree tree,
TNode x,
NodeTraverseFunction  traverseFunc,
void arg1,
void arg2 
) [static]

Definition at line 239 of file patricia.c.

{
       TNode  *p;
       int           err = 0;
       
       AE_ASSERT(x, "No node");
       AE_ASSERT(x->left && x->right, "Left or right child missing");

#ifdef VERBOSE
       printf("Visiting node %ld with left %ld and right %ld\n", x->nodeID, x->left->nodeID, x->right->nodeID);
#endif

       if (x != tree->headNode) {
              err = (*traverseFunc)(x->data, x->key, arg1, arg2);
              if (err != 0) return err;
       }
       
       p = x->left;
       if (p->bit < x->bit)
              err = InternalTraverse(tree, p, traverseFunc, arg1, arg2);

       if (err != 0) return err;
       
       p = x->right;
       if (p->bit < x->bit)
              err = InternalTraverse(tree, p, traverseFunc, arg1, arg2);
       
       return err;
}

Here is the caller graph for this function:

static TNode* MakeHeadNode ( TPatriciaTree tree) [static]

Definition at line 158 of file patricia.c.

{
       TNode         *newNode;
       
       newNode = (TNode *)calloc(1, sizeof(TNode));
       if (newNode == NULL) return NULL;

       newNode->key = (unsigned char *)calloc(tree->keySize + 1, 1);         //last bit must be zero
       if (newNode->key == NULL) {
              free(newNode);
              return NULL;
       }
       memset(newNode->key, 0, tree->keySize);
       newNode->bit = tree->numKeyBits;
       newNode->data = NULL;
       newNode->nodeID = -1;
       
       /* Both self-pointers for the head node */
       newNode->left = newNode;
       newNode->right = newNode;
       
       return newNode;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static TNode* MakeNewNode ( TPatriciaTree tree,
const unsigned char *  key,
short  bit,
void nodeData 
) [static]

Definition at line 121 of file patricia.c.

{
       static long          nodeID = 0;
       TNode         *newNode;
       
       newNode = (TNode *)calloc(1, sizeof(TNode));
       if (newNode == NULL) return NULL;

       newNode->key = (unsigned char *)calloc(tree->keySize + 1, 1);         //last bit must be zero
       if (newNode->key == NULL) {
              free(newNode);
              return NULL;
       }
       memcpy(newNode->key, key, tree->keySize);
       newNode->bit = bit;
       newNode->data = nodeData;
       newNode->nodeID = nodeID;
       nodeID ++;
       
       return newNode;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void PatriciaFreeTree ( PatriciaTreeRef  treeRef,
NodeFreeFunction  freeFunc,
void refCon 
)

Definition at line 376 of file patricia.c.

{
       TPatriciaTree *tree = (TPatriciaTree *)treeRef;

       if (tree == NULL) return;
       
       /* Traverse the tree and free the data */
       TraverseAndFree(tree, tree->headNode, freeFunc, refCon);
       
       free(tree);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 532 of file patricia.c.

{
       return ((TPatriciaTree *)treeRef)->numNodes;
}

Here is the caller graph for this function:

Definition at line 338 of file patricia.c.

{
       TPatriciaTree        *tree = NULL;

       tree = (TPatriciaTree *)calloc(1, sizeof(TPatriciaTree));
       if (tree == NULL) return NULL;
       
       tree->numKeyBits = numKeyBits;
       tree->keySize = (numKeyBits >> 3) + ((numKeyBits & 7) != 0);
       tree->numNodes = 0;
       
       tree->headNode = MakeHeadNode(tree);
       if (tree->headNode == NULL) {
              free(tree);
              return NULL;
       }
       
       return (PatriciaTreeRef)tree;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int PatriciaInsert ( PatriciaTreeRef  treeRef,
NodeReplaceFunction  replaceFunc,
const unsigned char *  key,
void data,
void refCon 
)

Definition at line 443 of file patricia.c.

{
       TPatriciaTree *tree = (TPatriciaTree *)treeRef;
       TNode         *x, *t, *p;
       short         i;

       x = tree->headNode;
       t = InternalSearch(tree, x, key);

       AE_ASSERT(t, "Should have found node");

       if (memcmp(t->key, key, tree->keySize) == 0) {
              if (replaceFunc) (*replaceFunc)(&t->data, t->key, data, refCon);
              return 1;                   /* It's already there */
       }
       
       i = tree->numKeyBits - 1;
       
       while (CompareKeyBits(key, t->key, i))
              i --;  
              
       do {
              p = x;
              x = (TestKeyBit(key, x->bit)) ? x->right : x->left;
       } while (x->bit > i && p->bit > x->bit);
       
       t = MakeNewNode(tree, key, i, data);
       if (t == NULL) return -1;
       
       if (TestKeyBit(key, t->bit)) {
              t->right = t;
              t->left = x;
       } else {
              t->right = x;
              t->left = t;
       }
              
       if (TestKeyBit(key, p->bit))
              p->right = t;
       else
              p->left = t;
       
#ifdef VERBOSE
       printf("Inserted node %ld with left %ld and right %ld\n", t->nodeID, t->left->nodeID, t->right->nodeID);
#endif

       tree->numNodes ++;
       
       return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int PatriciaSearch ( PatriciaTreeRef  treeRef,
const unsigned char *  key,
void **  data 
)

Definition at line 406 of file patricia.c.

{
       TPatriciaTree *tree = (TPatriciaTree *)treeRef;
       TNode         *foundNode;
       
       AE_ASSERT(tree, "Where is my tree?");

       foundNode = InternalSearch(tree, tree->headNode, key);
       AE_ASSERT(foundNode, "Should have found node");

       if (memcmp(foundNode->key, key, tree->keySize) == 0) {
              if (data != NULL)
                     *data = foundNode->data;
              return 1;
       } else
              return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int PatriciaTraverse ( PatriciaTreeRef  treeRef,
NodeTraverseFunction  traverseFunc,
void arg,
void refCon 
)

Definition at line 516 of file patricia.c.

{
       TPatriciaTree *tree = (TPatriciaTree *)treeRef;
       
       return InternalTraverse(tree, tree->headNode, traverseFunc, arg, refCon);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int TraverseAndFree ( TPatriciaTree tree,
TNode x,
NodeFreeFunction  freeFunc,
void refCon 
) [static]

Definition at line 289 of file patricia.c.

{
       TNode  *p;
       int           err = 0;
       
       AE_ASSERT(x, "No node");
       AE_ASSERT(x->left && x->right, "Left or right child missing");
              
       p = x->left;
       if (p->bit < x->bit) {
              err = TraverseAndFree(tree, p, freeFunc, refCon);
              if (err != 0) return err;
       }
       
       p = x->right;
       if (p->bit < x->bit) {
              err = TraverseAndFree(tree, p, freeFunc, refCon);
              if (err != 0) return err;
       }

       err = (*freeFunc)(x->data, x->key, refCon);
       
#ifdef VERBOSE
       printf("Freeing node %ld\n", x->nodeID);
#endif

       free(x->key);
       free(x);
       
       return err;
}

Here is the caller graph for this function: