Back to index

lightning-sunbird  0.9+nobinonly
Typedefs | Functions
patricia.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef voidPatriciaTreeRef
typedef int(* NodeReplaceFunction )(void **nodeDataPtr, unsigned char *key, void *replaceData, void *refCon)
typedef int(* NodeTraverseFunction )(void *nodeData, unsigned char *key, void *arg, void *refCon)
typedef int(* NodeFreeFunction )(void *nodeData, unsigned char *key, void *refCon)

Functions

PatriciaTreeRef PatriciaInitTree (long numKeyBits)
void PatriciaFreeTree (PatriciaTreeRef treeRef, NodeFreeFunction freeFunc, void *refCon)
int PatriciaInsert (PatriciaTreeRef treeRef, NodeReplaceFunction replaceFunc, const unsigned char *key, void *data, void *refCon)
int PatriciaSearch (PatriciaTreeRef treeRef, const unsigned char *key, void **data)
int PatriciaTraverse (PatriciaTreeRef treeRef, NodeTraverseFunction traverseFunc, void *arg, void *refCon)
long PatriciaGetNumNodes (PatriciaTreeRef treeRef)

Typedef Documentation

typedef int(* NodeFreeFunction)(void *nodeData, unsigned char *key, void *refCon)

Definition at line 80 of file patricia.h.

typedef int(* NodeReplaceFunction)(void **nodeDataPtr, unsigned char *key, void *replaceData, void *refCon)

Definition at line 78 of file patricia.h.

typedef int(* NodeTraverseFunction)(void *nodeData, unsigned char *key, void *arg, void *refCon)

Definition at line 79 of file patricia.h.

Definition at line 71 of file patricia.h.


Function Documentation

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: