searchtree.c

/* Notice of Copyright, License and Warranty
**
** This software is Copyright 1999, 2001 Jeffrey S. Dutky
** This software is licensed for use under the terms of the GNU Library
** General Public License (also called the LGPL), a copy of which must
** be included with any distribution of this software. You may also find
** a copy of the LGPL at the Free Software Foundation's web site at
** http://www.fsf.org/ or http://www.gnu.org.
**
** This software is provided "as is" and without any express or implied
** warranties, including, without limitation, the implied waranties of
** merchantability and fitness for a particular purpose.
*/

/*
** Jeffrey S. Dutky, August 1999, June 2001
**
** The search tree library implements a straight forward binary search
** tree using an AVL tree. The keys and data in the tree are user defined
** and require the user to provide comparisson and deallocation routines.
** The tree also has a simple optimization in the form of a one element
** cache that holds that last node searched for in the tree. This should
** speed up search-and-update operations by a fair degree on large trees,
** while only intruducing a minute delay into all other operations. For
** large trees that exhibit a high locality of access, this should be a
** big win.
**
** Note: it would be just as good, if not better, to use a self optimizing
** tree where the most common keys are moved to the top of the tree when
** they are accessed (is that a splay tree?) but I didn't feel like writing
** it. In any case, future versions of this library may be rewritten to use
** a splay tree instead of my caching AVL tree.
**
** Note Also: the current version of this code uses lazy deletion, meaning
** that deleted nodes are not actually deleted, but simply have their data
** deleted (if the user defined a dfree method) and are marked deleted by
** the remove routine. If the search routine finds a deleted node, it will
** act as if it didn't find anything. If the insert routine finds a deleted
** node with the same key as the one being inserted, it will delete the old
** key and put the new data and key into the existing node, finally setting
** the deleted flag to false. I intend to replace this system with a real
** removal routine at some later date, but, for the moment, this will work
** almost as well. (the current implementation of lazy delete isn't quite
** as lazy as it could be: it will actually delete leaf nodes when they
** are encountered during the removal routine. Again, better could be done,
** but this will work for now)
*/

#define SEARCHTREE_C

typedef struct SEARCHNODE SearchNode;

typedef struct {
   long tag;
   int (*cmp)(void *k1, void *l2);
   int (*kfree)(void *k);
   int (*dfree)(void *d);
   int ncache;
   SearchNode *root, *cache, *link;
   int nodes;
   int rot;
   SearchNode *nod;
} SearchTree;

struct SEARCHNODE {
   long tag;
   SearchNode *parent, *greater, *lesser, *next, *prev;
   SearchTree *tree;
   void *key, *data;
   int child;
   int lesserdepth, greaterdepth;
   int deleted;
};

#include <stdlib.h>
#include "searchtree.h"

/* #define SEARCHTREE_TAG 'TREE' */
#define SEARCHTREE_TAG 0x54524545L
/* #define SEARCHNODE_TAG 'NODE' */
#define SEARCHNODE_TAG 0x4E4F4445L

#define MAX(A,B) ((A>B)?(A):(B))
#define MAXDEPTH(A) ((A->lesserdepth>A->greaterdepth)?A->lesserdepth:A->greaterdepth)

/*
** the following two rotation routines are pretty obscure, and I don't see
** any very good way of explaining what they do, or of commenting them well
** except by putting some diagrams in here that shows what they are SUPPOSED
** to achieve. Other than those diagrams, and some carefull analysis on the
** part of the reader, you are on your own with this code. Sorry.
**
** Note: the rotation routines adjust the ballance information (in this case
** I use depth values rather than ballance factors, which make later updates
** much easier) but I also have code in the avlBallance routine that tries
** to adjust the ballance factors. This shouldn't cause a problem, but I
** should probably have avlBallance start at the parent node (if one exists)
** rather than at the current node, since the rotations fix up everyone's
** depths up to the parent.
*/

/*
**        single right rotation
**
**        P                  P           P=parent (node or tree)
**        :                  :           N=node
**        N     right(N)     C           n=node subtree
**       / \    ------->    / \          C=child
**      C   n              G   N         G=grandchild
**     / \                / \ / \        x=grandchild subtree
**    G   x              g  g x  n       g=great-grandchild subtrees
**   / \
**  g   g
*/

static void right1(SearchNode *n){
   SearchNode *p, *c, *g, *x;
   SearchTree *t;
   
   t=n->tree;
   p=n->parent;
   c=n->lesser;
   g=c->lesser;
   x=c->greater;
   
   if(p){
       if(n->child==GREATER){
           p->greater=c;
           c->child=GREATER;
       }else{
           p->lesser=c;
           c->child=LESSER;
       }
   }else{ /* n is the root node */
       t->root=c;
       c->child=NONE;
   }
   c->parent=p;
   c->greater=n;
   n->parent=c;
   n->child=GREATER;
   c->lesser=g;
   g->parent=c;
   g->child=LESSER;
   n->lesser=x;
   if(x){
       x->parent=n;
       x->child=LESSER;
   }
   
   /* adjust the depths of the moved nodes (n, c, and p) */
   n->lesserdepth=c->greaterdepth;
   c->greaterdepth=MAXDEPTH(n)+1;
   while(p){
       n=p->lesser;
       if(n) p->lesserdepth=MAXDEPTH(n)+1;
       else p->lesserdepth=0;
       n=p->greater;
       if(n) p->greaterdepth=MAXDEPTH(n)+1;
       else p->greaterdepth=0;
       p=p->parent;
   }
}

/*
**       single left rotation
**
**       P                   P           P=parent (node or tree)
**       :                   :           N=node
**       N       left(N)     C           n=node subtree
**      / \     ------->    / \          C=child
**     n   C               N   G         G=grandchild
**        / \             / \ / \        x=grandchild subtree
**       x   G           n  x g  g       g=great-grandchild subtrees
**          / \
**         g   g
*/

static void left1(SearchNode *n){
   SearchNode *p, *c, *g, *x;
   SearchTree *t;
   
   t=n->tree;
   p=n->parent;
   c=n->greater;
   g=c->greater;
   x=c->lesser;
   
   if(p){
       if(n->child==GREATER){
           p->greater=c;
           c->child=GREATER;
       }else{
           p->lesser=c;
           c->child=LESSER;
       }
   }else{ /* n is the root node */
       t->root=c;
       c->child=NONE;
   }
   c->parent=p;
   c->lesser=n;
   n->parent=c;
   n->child=LESSER;
   c->greater=g;
   g->parent=c;
   g->child=GREATER;
   n->greater=x;
   if(x){
       x->parent=n;
       x->child=GREATER;
   }
   
   /* adjust the depths of the moved nodes (n, c, and p) */
   n->greaterdepth=c->lesserdepth;
   c->lesserdepth=MAXDEPTH(n)+1;
   while(p){
       n=p->lesser;
       if(n) p->lesserdepth=MAXDEPTH(n)+1;
       else p->lesserdepth=0;
       n=p->greater;
       if(n) p->greaterdepth=MAXDEPTH(n)+1;
       else p->greaterdepth=0;
       p=p->parent;
   }
}

static void rotate1(int dir, SearchNode *n){
   if(dir!=GREATER && dir!=LESSER)
       return;
   n->tree->rot=dir;
   n->tree->nod=n;
   if(dir==GREATER)
       right1(n);
   else
       left1(n);
   return;
}

/*
**             double right rotation
**
**     P                P               P           P=parent (node or tree)
**     :                :               :           N=node
**     N    left(C)     N    right(N)   G           n=node subtree
**    / \    ---->     / \    ---->    / \          C=child
**   C   n            G   n           C   N         c=child subtree
**  / \              / \             / \ / \        G=grandchild
** c   G            C   y           c  x y  n       x,y=grandchild subtrees
**    / \          / \
**   x   y        c   x
*/

static void right2(SearchNode *n){
   SearchNode *p, *c, *g, *x, *y;
   SearchTree *t;
   
   p=n->parent;
   c=n->lesser;
   g=c->greater;
   x=g->lesser;
   y=g->greater;
   t=n->tree;
   
   if(p){
       if(n->child==LESSER)
           p->lesser=g;
       else
           p->greater=g;
   }else
       t->root=g;
   g->child=n->child;
   g->parent=n->parent;
   
   n->lesser=y;
   if(y){
       y->parent=n;
       y->child=LESSER;
   }
   g->greater=n;
   n->parent=g;
   n->child=GREATER;
   
   c->greater=x;
   if(x){
       x->parent=c;
       x->child=GREATER;
   }
   g->lesser=c;
   c->parent=g;
   c->child=LESSER;
   
   /* recalculate depths of modified nodes (p, g, c, and n) */
   n->lesserdepth=g->greaterdepth;
   c->greaterdepth=g->lesserdepth;
   g->lesserdepth=MAXDEPTH(c)+1;
   g->greaterdepth=MAXDEPTH(n)+1;
   while(p){
       n=p->lesser;
       if(n)
           p->lesserdepth=MAXDEPTH(n)+1;
       else
           p->lesserdepth=0;
       n=p->greater;
       if(n)
           p->greaterdepth=MAXDEPTH(n)+1;
       else
           p->greaterdepth=0;
       p=p->parent;
   }
}

/*
**             double left rotation
**
**     P               P                P           P=parent (node or tree)
**     :               :                :           N=node
**     N    right(C)   N     left(N)    G           n=node subtree
**    / \    ---->    / \     ---->    / \          C=child
**   n   C           n   G            N   C         c=child subtree
**      / \             / \          / \ / \        G=grandchild
**     G   c           x   C        n  x y  c       x,y=grandchild subtrees
**    / \                 / \
**   x   y               y   c
*/

static void left2(SearchNode *n){
   SearchNode *p, *c, *g, *x, *y;
   SearchTree *t;
   
   p=n->parent;
   c=n->greater;
   g=c->lesser;
   x=g->lesser;
   y=g->greater;
   t=n->tree;
   
   if(p){
       if(n->child==LESSER)
           p->lesser=g;
       else
           p->greater=g;
   }else
       t->root=g;
   g->child=n->child;
   g->parent=p;
   
   n->greater=x;
   if(x){
       x->parent=n;
       x->child=GREATER;
   }
   g->lesser=n;
   n->parent=g;
   n->child=LESSER;
   
   c->lesser=y;
   if(y){
       y->parent=c;
       y->child=LESSER;
   }
   g->greater=c;
   c->parent=g;
   c->child=GREATER;
   
   /* recalculate depths for modified nodes (p, g, n, and c) */
   n->greaterdepth=g->lesserdepth;
   c->lesserdepth=g->greaterdepth;
   g->lesserdepth=MAXDEPTH(n)+1;
   g->greaterdepth=MAXDEPTH(c)+1;
   while(p){
       n=p->lesser;
       if(n)
           p->lesserdepth=MAXDEPTH(n)+1;
       else
           p->lesserdepth=0;
       n=p->greater;
       if(n)
           p->greaterdepth=MAXDEPTH(n)+1;
       else
           p->greaterdepth=0;
       p=p->parent;
   }
}

static void rotate2(int dir, SearchNode *n){
   if(dir!=GREATER && dir!=LESSER)
       return;
   n->tree->rot=2*dir;
   n->tree->nod=n;
   if(dir==GREATER)
       right2(n);
   else
       left2(n);
   return;
}

SearchTree *createTree(int (*cmp)(void *l1, void *l2),
   int (*kfree)(void *k), int (*dfree)(void *d)){
   SearchTree *st=NULL;
   
   if(cmp==NULL)
       return NULL;
   st=(SearchTree*)malloc(sizeof(SearchTree));
   if(st){
       st->tag=SEARCHTREE_TAG;
       st->cmp=cmp;
       st->kfree=kfree;
       st->dfree=dfree;
       st->root=NULL;
       st->ncache=1;
       st->cache=NULL;
       st->link=NULL;
       st->nodes=0;
       st->rot=0;
       st->nod=NULL;
   }
   return st;
}

int deleteTree(SearchTree *st){
   SearchNode *node, *next;
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   node=st->link;
   while(node){
       if(node->tag!=SEARCHNODE_TAG || st->nodes<=0)
           return STERR_CORRUPTNODE;
       if(st->dfree && node->data)
           st->dfree(node->data);
       if(st->kfree && node->key)
           st->kfree(node->key);
       next=node->next;
       node->tag=0;
       free(node);
       node=next;
       st->nodes--;
   }
   st->tag=0;
   free(st);
   return 0;
}

/*
** ballance the tree starting at the specified node. Climb the tree until
** either an unballanced node is found, or the root of  the tree is reached.
** When an unballanced node is found, a single or double roation is
** performed on that node in order to ballance the tree. Finally, the
** ballance factors are updated from the rotated node upwards toward
** the root.
*/
static int avlBalance(SearchNode *n){
   int diff, cdiff, ldepth=0, gdepth=0;
   SearchNode *t;
   
   t=n;
   while(t){
       if(t->lesser)
           t->lesserdepth=MAXDEPTH(t->lesser)+1;
       else
           t->lesserdepth=0;
       if(t->greater)
           t->greaterdepth=MAXDEPTH(t->greater)+1;
       else
           t->greaterdepth=0;
       t=t->parent;
   }
   
   /* look for an unbalanced node */
   while(n){
       diff=n->lesserdepth - n->greaterdepth;
       if(diff*diff>1)
           break;
       n=n->parent;
   }
   if(n==NULL)
       return 0;
   
   /* calculate balance factor for unbalanced child */
   if(diff>0){
       if(n->lesser){
           ldepth=n->lesser->lesserdepth;
           gdepth=n->lesser->greaterdepth;
       }else
           ldepth=gdepth=0;
   }else{
       if(n->greater){
           ldepth=n->greater->lesserdepth;
           gdepth=n->greater->greaterdepth;
       }else
           ldepth=gdepth=0;
   }
   cdiff=ldepth-gdepth;
   
   /* rotate unbalanced node accordingly to node and child balances */
   if(diff*cdiff<0)
       rotate2(((diff<0)?LESSER:GREATER),n);
   else
       rotate1(((diff<0)?LESSER:GREATER),n);
   return 1;
}

int insertNode(SearchTree *st, void *k, void *d){
   SearchNode *n, *p;
   int ch, cmp, lazy=0;
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   st->rot=NONE;
   st->nod=NULL;
   
   /* find the node under which to insert the new data */
   p=n=st->root;
   ch=NONE;
   while(n){
       cmp=st->cmp(k,n->key);
       if(cmp==0 && n->deleted==0)
           return STERR_KEYEXISTS;
       if(cmp==0 && n->deleted){
           lazy=1;
           break;
       }
       p=n;
       if(cmp<0){
           ch=LESSER;
           n=n->lesser;
       }else{
           ch=GREATER;
           n=n->greater;
       }
   }
   
   /* create the new data node, initialize it, and insert it */
   if(!lazy){
       n=(SearchNode*)malloc(sizeof(SearchNode));
       if(n==NULL)
           return STERR_BADMEMALLOC;
       n->tag=SEARCHNODE_TAG;
       n->parent=p;
       n->lesser=n->greater=NULL;
       n->next=st->link;
       n->prev=NULL;
       n->tree=st;
       n->child=ch;
       n->lesserdepth=n->greaterdepth=0;
       if(p){
           if(ch==GREATER)
               p->greater=n;
           else
               p->lesser=n;
       }else
           st->root=n;
       if(st->link)
           st->link->prev=n;
       st->link=n;
       st->nodes++;
   }else if(st->kfree && n->key)
       st->kfree(n->key);
   n->key=k;
   n->data=d;
   n->deleted=0;
   
   avlBalance(n);
   if(st->ncache)
       st->cache=n;
   return 0;
}

static SearchNode *getNodeByKey(SearchTree *st, void *k){
   SearchNode *node;
   int cmp;
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return NULL;
   if(st->ncache && st->cache && st->cmp(k,st->cache->key)==0)
       return st->cache;
   node=st->root;
   while(node){
       if(node->tag!=SEARCHNODE_TAG)
           return NULL;
       cmp=st->cmp(k,node->key);
       if(cmp==0)
           break;
       if(cmp<0)
           node=node->lesser;
       else
           node=node->greater;
   }
   if(node && node->deleted)
       node=NULL;
   if(node && st->ncache)
       st->cache=node;
   return node;
}

/*
** this is a lazy remove function, all it does is mark the nodes as
** 'deleted' but leaves them in place. I'm only doing this for the
** moment because it is a real pain to write a proper remove function
** that can handle interior nodes.
*/
int lazy_removeNode(SearchTree *st, void *k){
   SearchNode *n, *p;
   int diff;
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   n=st->root;
   while(n){
       diff=st->cmp(k, n->key);
       if(diff==0)
           break;
       if(diff>0)
           n=n->greater;
       else
           n=n->lesser;
   }
   if(n==NULL || n->deleted)
       return STERR_KEYNOTFOUND;
   if(n->lesser==NULL && n->greater==NULL){
       if(st->dfree && n->data)
           st->dfree(n->data);
       if(st->kfree && n->key)
           st->kfree(n->key);
       if(n->prev)
           n->prev->next=n->next;
       else
           st->link=n->next;
       if(n->next)
           n->next->prev=n->prev;
       if(n->child==LESSER)
           n->parent->lesser=NULL;
       if(n->child==GREATER)
           n->parent->greater=NULL;
       st->nodes--;
       p=n->parent;
       n->tag=0;
       free(n);
       while(avlBalance(p));
   }else{
       if(st->dfree && n->data){
           st->dfree(n->data);
           n->data=NULL;
       }
       n->deleted=1;
   }
   if(st->ncache && st->cache==n)
       st->cache=NULL;
   return 0;
}

/*
** here is a non-lazy removal function. It uses the same kind of analysis as
** the rotation routines (name all involved nodes before we do anything) and
** it's not too much longer than the old, lazy, removal function.
*/

int removeNode(SearchTree *st, void *k){
   SearchNode *n=NULL; /* the node to be deleted */
   SearchNode *p=NULL; /* the node's parent, if any */
   SearchNode *t=NULL; /* the target node to replace the node */
   SearchNode *c=NULL; /* the target node's child, if any */
   SearchNode *x=NULL; /* the target node's parent */
   SearchNode *r=NULL; /* node at which to start rebalancing */
   int diff; /* used during node search to compare value */
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   
   /* find the node to be deleted */
   n=st->root;
   while(n){
       diff=st->cmp(k, n->key);
       if(diff==0)
           break;
       if(diff>0)
           n=n->greater;
       else
           n=n->lesser;
   }
   if(n==NULL)
       return STERR_KEYNOTFOUND;
   
   p=n->parent;
   
   if(n->lesser==NULL || n->greater==NULL){
       /* if n has no children, or only one child, everything is easy */
       if(n->lesser || n->greater){
           if(n->lesser)
               c=n->lesser;
           else
               c=n->greater;
           c->parent=n->parent;
           c->child=n->child;
       }
       if(p){
           if(n->child==LESSER)
               p->lesser=c;
           else
               p->greater=c;
       }else
           st->root=c;
       r=p;
   }else{
       /* if n has two children, we need to do a lot more work */
       
       if(n->child==LESSER){
           t=n->lesser;
           while(t->greater)
               t=t->greater;
           c=t->lesser;
       }else{
           t=n->greater;
           while(t->lesser)
               t=t->lesser;
           c=t->greater;
       }
       x=t->parent;
       
       /* remove the target node from the tree */
       if(t->child==LESSER)
           x->lesser=c;
       else
           x->greater=c;
       if(c){
           c->parent=x;
           c->child=t->child;
       }
       
       /* replace the deleted node (n) with the target node (t) */
       t->lesser=n->lesser;
       t->lesserdepth=n->lesserdepth;
       if(t->lesser)
           t->lesser->parent=t;
       t->greater=n->greater;
       t->greaterdepth=n->greaterdepth;
       if(t->greater)
           t->greater->parent=t;
       t->parent=p;
       t->child=n->child;
       if(p){
           if(t->child==LESSER)
               p->lesser=t;
           else
               p->greater=t;
       }else
           st->root=t;
       if(x==n)
           r=t;
       else
           r=x;
   }
   
   /* remove the node from the tree's node list */
   if(n->next)
       n->next->prev=n->prev;
   if(n->prev)
       n->prev->next=n->next;
   else
       st->link=n->next;
   st->nodes--;
   
   /* finally, we can delete the node itself */
   if(st->kfree)
       st->kfree(n->key);
   if(st->dfree)
       st->dfree(n->data);
   n->tag=0L;
   free(n);
   
   /* balance the tree, starting from the lowest affected node */
   while(avlBalance(r));
   if(st->ncache && st->cache==n)
       st->cache=c;
   
   return 0;
}

int findNode(SearchTree *st, void *k, void **d){
   SearchNode *n;
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   st->rot=0;
   n=getNodeByKey(st,k);
   if(n){
       *d=n->data;
       return 1;
   }
   return 0;
}

/* #define NODESEEN_TAG 'SEEN' */
#define NODESEEN_TAG 0x5345454EL

static int verifyNode(SearchNode *n, int *nodecount, SearchTree *st, SearchNode *p){
   int ldepth, gdepth;
   
   st->nod=n;
   if(n==NULL)
       return 0;
   if(n->tag==NODESEEN_TAG)
       return STERR_NODECYCLE;
   if(n->tag!=SEARCHNODE_TAG)
       return STERR_CORRUPTNODE;
   if(n->parent!=p || n->tree!=st)
       return STERR_ORPHANEDNODE;
   if(n->next && n->next->prev!=n)
       return STERR_UNLINKEDNODE;
   if(n->prev && n->prev->next!=n)
       return STERR_UNLINKEDNODE;
   if(n->prev==NULL && st->link!=n)
       return STERR_BADTREELINK;
   if(p && p->lesser!=n && p->greater!=n)
       return STERR_ORPHANEDNODE;
   (*nodecount)++;
   ldepth=verifyNode(n->lesser, nodecount, st, n);
   if(ldepth<0)
       return ldepth;
   st->nod=n;
   if(ldepth!=n->lesserdepth)
       return STERR_BADNODEDEPTH;
   gdepth=verifyNode(n->greater, nodecount, st, n);
   if(gdepth<0)
       return gdepth;
   st->nod=n;
   if(gdepth!=n->greaterdepth)
       return STERR_BADNODEDEPTH;
   if(abs(ldepth-gdepth)>1)
       return STERR_UNBALANCED;
   n->tag=SEARCHNODE_TAG;
   st->nod=NULL;
   return MAX(ldepth,gdepth)+1;
}

int verifyTree(SearchTree *st){
   int nodes=0;
   int depth=0;
   SearchNode *n=NULL;
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   if(st->nodes>0 && (st->link==NULL || st->root==NULL))
       return STERR_BADTREELINK;
   if(st->link && st->link->prev!=NULL)
       return STERR_BADTREELINK;
   if(st->nodes<0)
       return STERR_CORRUPTTREE;
   depth=verifyNode(st->root, &nodes, st, NULL);
   if(depth<0)
       return depth;
   if(st->nodes!=nodes)
       return STERR_BADNODECOUNT;
   n=st->link;
   while(n){
       st->nod=n;
       if(n->tag!=SEARCHNODE_TAG)
           return STERR_CORRUPTNODE;
       if(n->next && n->next->prev!=n)
           return STERR_UNLINKEDNODE;
       if(n->prev && n->prev->next!=n)
           return STERR_UNLINKEDNODE;
       nodes--;
       n=n->next;
   }
   st->nod=NULL;
   if(nodes)
       return STERR_BADNODECOUNT;
   return 0;
}

static int treedumplite(FILE *f, SearchTree *t){
   SearchNode *n;
   void *lk, *gk, *pk;
   void *prk, *nxk;
   int i;
   char *child[3]={"left","","right"}, c;
   
   fprintf(f, "tree=(%p) root=%x  link=%x  nodes=%d\n", t, t->root->key,
       t->link->key, t->nodes);
   fflush(f);
   n=t->link;
   i=1;
   while(n){
       lk=gk=pk=NULL;
       c=' ';
       if(n->lesser)
           lk=n->lesser->key;
       if(n->greater)
           gk=n->greater->key;
       if(n->parent)
           pk=n->parent->key;
       else
           c='>';
       if(n->prev)
           prk=n->prev->key;
       else
           prk=NULL;
       if(n->next)
           nxk=n->next->key;
       else
           nxk=NULL;
       fprintf(f, "  %3d: %c[%-2x]  P=%-2x   L=%-2x R=%-2x   "
           "balance: % d (%d,%d)  [P=%-2x, N=%-2x] %s %s\n", i++, c, n->key,
           pk, lk, gk, n->lesserdepth-n->greaterdepth, n->lesserdepth,
           n->greaterdepth, prk, nxk, child[n->child+1],
           ((n->deleted)?"deleted":""));
       fflush(f);
       n=n->next;
   }
   return 0;
}

int treeDump(FILE *f, SearchTree *st, int mode){
   SearchNode *n;
   void *k;
   int i;
   char *childarray[3]={"LESSER","NONE","GREATER"};
   
   if(mode==BRIEF)
       return treedumplite(f, st);
   
   fprintf(f,"\ntree structure @%p\n",st);
   if(st->tag!=SEARCHTREE_TAG)
       fprintf(f,"Invalid Tag Value in Tree Structure\n");
   fflush(f);
   fprintf(f,"cmp=%p\nkfree=%p\ndfree=%p\n", st->cmp, st->kfree, st->dfree);
   fflush(f);
   if(st->root) k=st->root->key; else k=NULL;
   fprintf(f,"root=%p (%p)\n", st->root, k);
   fflush(f);
   if(st->cache) k=st->cache->key; else k=NULL;
   fprintf(f,"cache=%p (%p)\n", st->cache, k);
   fflush(f);
   if(st->link) k=st->link->key; else k=NULL;
   fprintf(f,"link=%p (%p)\n", st->link, k);
   fprintf(f,"nodes=%d\n",st->nodes);
   if(st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   fflush(f);
   n=st->link;
   i=0;
   while(n){
       fprintf(f,"\nnode structure #%d @%p",i++,n);
       if(n->tag!=SEARCHNODE_TAG)
           fprintf(f,"\n  Invalid Tag Value in Tree Node\n");
       fflush(f);
       fprintf(f," (%p)\n",n->key);
       fflush(f);
       fprintf(f,"  tree=%p",n->tree);
       fflush(f);
       if(n->parent) k=n->parent->key; else k=NULL;
       fprintf(f,"  parent=%p (%p)",n->parent,k);
       fflush(f);
       fprintf(f,"  child=%s\n",childarray[(n->child+1)%3]);
       fflush(f);
       if(n->lesser) k=n->lesser->key; else k=NULL;
       fprintf(f,"  lesser=%p (%p)",n->lesser,k);
       fflush(f);
       if(n->greater) k=n->greater->key; else k=NULL;
       fprintf(f,"  greater=%p (%p)\n",n->greater,k);
       fflush(f);
       fprintf(f,"  lesserdepth=%d",n->lesserdepth);
       fflush(f);
       fprintf(f,"  greaterdepth=%d\n",n->greaterdepth);
       fflush(f);
       if(n->prev) k=n->prev->key; else k=NULL;
       fprintf(f,"  prev=%p (%p)",n->prev,k);
       fflush(f);
       if(n->next) k=n->next->key; else k=NULL;
       fprintf(f,"  next=%p (%p)\n",n->next,k);
       fflush(f);
       fprintf(f,"  key=%p",n->key);
       fflush(f);
       fprintf(f,"  data=%p\n",n->data);
       fflush(f);
       fprintf(f,"  lesserdepth=%d",n->lesserdepth);
       fflush(f);
       fprintf(f,"  greaterdepth=%d\n",n->greaterdepth);
       fflush(f);
       if(n->tag!=SEARCHNODE_TAG)
           return STERR_CORRUPTNODE;
       n=n->next;
   }
   return 0;
}

static char *errstr[]={
   "No Error",
   "NULL Tree Pointer or Corrupt Tree Tag",
   "Corrupt Tree Node or Tree Node Tag",
   "Failed to Allocate Memory",
   "Couldn't Find Specified Key Value in Tree",
   "The AVL Tree is Not Balanced",
   "A Cycle was Found in the Tree Nodes",
   "Incorrect Node Count in Tree",
   "An Orphan Node was Found in the Tree",
   "An Unlinked Node was Found in the Tree",
   "Incorrect Depth Value in Node",
   "Invalid Tree Link in Tree",
   "Specified Key Already Exists in the Tree",
   "Corrupt Tree Structure, Negative Node Count",
   "A NULL Comparisson Function was Specified",
   "An Illegal Parameter Value was Specified",
   NULL
};

static int errcount=0;

const char *treeError(int e){
   if(errcount==0){
       while(errstr[errcount])
           errcount++;
   }
   if(e>0 || abs(e)>=errcount)
       return "BAD ERROR CODE";
   return errstr[abs(e)];
}

SearchNode *rotatedNode(SearchTree *st){
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return 0;
   return st->nod;
}

void *nodeKey(SearchNode *node){
   if(node && node->tag==SEARCHNODE_TAG)
       return node->key;
   return NULL;
}

void *nodeData(SearchNode *node){
   if(node && node->tag==SEARCHNODE_TAG)
       return node->data;
   return NULL;
}

int treeRotated(SearchTree *st){
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return 0;
   return st->rot;
}

int deadNodes(SearchTree *st){
   SearchNode *n;
   int dn=0;
   
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return 0;
   
   n=st->link;
   while(n){
       if(n->deleted)
           dn++;
       n=n->next;
   }
   return dn;
}

int treeNodes(SearchTree *st){
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return 0;
   return st->nodes;
}

static int tree_climb(FILE *f, SearchNode *n, int ord, int(*print)(FILE *f, void *k, void *d, void *n)){
   int err=0;
   
   if(n==NULL)
       return print(f,NULL,NULL,NULL);
   if(ord==PREORDER)
       err=print(f,n->key,n->data,n);
   if(err)
       return err;
   err=tree_climb(f,n->lesser,ord,print);
   if(err)
       return err;
   if(ord==INORDER)
       err=print(f,n->key,n->data,n);
   if(err)
       return err;
   err=tree_climb(f,n->greater,ord,print);
   if(err)
       return err;
   if(ord==POSTORDER)
       err=print(f,n->key,n->data,n);
   return err;
}

int traverseTree(FILE *f, SearchTree *st, int ord, int(*print)(FILE *f, void *k, void *d, void *n)){
   if(f==NULL||print==NULL||ord!=PREORDER||ord!=INORDER||ord!=POSTORDER)
       return STERR_BADPARAM;
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   return tree_climb(f,st->root,ord,print);
}

int setCache(SearchTree *st, unsigned n){
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   if(n<0)
       st->ncache=-n;
   else
       st->ncache=n;
   return st->ncache;
}

int getCache(SearchTree *st){
   if(st==NULL || st->tag!=SEARCHTREE_TAG)
       return STERR_BADTREEPTR;
   return st->ncache;
}