"Fossies" - the Fresh Open Source Software Archive

Member "coda-6.9.5/coda-src/util/bstree.cc" (26 Jul 2006, 8823 Bytes) of package /linux/misc/old/coda-6.9.5.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "bstree.cc" see the Fossies "Dox" file reference documentation.

    1 /* BLURB gpl
    2 
    3                            Coda File System
    4                               Release 6
    5 
    6           Copyright (c) 1987-2003 Carnegie Mellon University
    7                   Additional copyrights listed below
    8 
    9 This  code  is  distributed "AS IS" without warranty of any kind under
   10 the terms of the GNU General Public Licence Version 2, as shown in the
   11 file  LICENSE.  The  technical and financial  contributors to Coda are
   12 listed in the file CREDITS.
   13 
   14                         Additional copyrights
   15                            none currently
   16 
   17 #*/
   18 
   19 /*
   20  *
   21  *    Implementation of binary search tree, based on example in "Data Structures and Algorithms" by AHU.
   22  *
   23  */
   24 
   25 
   26 #ifdef __cplusplus
   27 extern "C" {
   28 #endif
   29 
   30 #include <stdio.h>
   31 #include <unistd.h>
   32 #include <stdlib.h>
   33 #include <string.h>
   34 
   35 #ifdef __cplusplus
   36 }
   37 #endif
   38 
   39 #include "bstree.h"
   40 
   41 /* DEBUGGING! -JJK */
   42 /*
   43 extern FILE *logFile;
   44 extern void Die(char * ...);
   45 */
   46 
   47 
   48 /*  *****  Some Useful Macros  *****  */
   49 
   50 #define ZERONODE(n)\
   51 {\
   52     (n)->mytree = 0;\
   53     (n)->parent = 0;\
   54     (n)->leftchild = 0;\
   55     (n)->rightchild = 0;\
   56 }
   57 
   58 #define FIRST(r, n)\
   59 {\
   60     (n) = (r);\
   61     while ((n)->leftchild != 0)\
   62     (n) = (n)->leftchild;\
   63 }
   64 
   65 #define LAST(r, n)\
   66 {\
   67     (n) = (r);\
   68     while ((n)->rightchild != 0)\
   69     (n) = (n)->rightchild;\
   70 }
   71 
   72 #define SPLICE(n1, n2)\
   73 {\
   74     if ((n1)->parent == 0)\
   75     root = (n2);\
   76     else {\
   77     if (((n1)->parent)->leftchild == (n1))\
   78         ((n1)->parent)->leftchild = (n2);\
   79     else\
   80         ((n1)->parent)->rightchild = (n2);\
   81     }\
   82 \
   83     if ((n2) != 0)\
   84     (n2)->parent = (n1)->parent;\
   85 }
   86 
   87 
   88 /*  *****  Binary Search Tree  *****  */
   89 
   90 bstree::bstree(BSTCFN F) {
   91     root = 0;
   92     CmpFn = F;
   93     cnt = 0;
   94 
   95     inserts = 0;
   96     removes = 0;
   97     gets = 0;
   98 }
   99 
  100 
  101 bstree::bstree(bstree& bst) {
  102     abort();
  103 }
  104 
  105 
  106 int bstree::operator=(bstree& bst) {
  107     abort();
  108     return(0); /* keep C++ happy */
  109 }
  110 
  111 
  112 bstree::~bstree() {
  113     /* This is dangerous! */
  114     /* Perhaps we should abort() if count() != 0?  -JJK */
  115     clear();
  116 }
  117 
  118 
  119 /* Does NOT require uniqueness of keys. */
  120 void bstree::insert(bsnode *b) {
  121 /*
  122     if (!IsOrdered())
  123     { print(logFile); b->print(logFile); Die("bstree::insert: !ordered at entry"); }
  124 */
  125     if (b->tree() != 0) abort();
  126 /*  { print(logFile); b->print(logFile); Die("bstree::insert: already on %x", b->tree()); }*/
  127     inserts++;
  128 
  129     if (root == 0)
  130     root = b;
  131     else {
  132     bsnode *curr = root;
  133     for (;;) {
  134         int res = CmpFn(b, curr);
  135         if (res == 0) {
  136         /* Break ties using addresses. */
  137         if ((char *)b > (char *)curr) res = 1;
  138         else if ((char *)b < (char *)curr) res = -1;
  139         else abort();
  140 /*          { print(logFile); b->print(logFile); Die("bstree::insert: found in tree"); }*/
  141         }
  142 
  143         if (res < 0) {
  144         if (curr->leftchild == 0) {
  145             b->parent = curr;
  146             curr->leftchild = b;
  147             break;
  148         }
  149         curr = curr->leftchild;
  150         }
  151         else {  /* res > 0 */
  152         if (curr->rightchild == 0) {
  153             b->parent = curr;
  154             curr->rightchild = b;
  155             break;
  156         }
  157         curr = curr->rightchild;
  158         }
  159     }
  160     }
  161 
  162     b->mytree = this;
  163     cnt++;
  164 /*
  165     if (!IsOrdered())
  166     { print(logFile); b->print(logFile); Die("bstree::insert: !ordered at exit"); }
  167 */
  168 }
  169 
  170 
  171 bsnode *bstree::remove(bsnode *b) {
  172 /*
  173     if (!IsOrdered())
  174     { print(logFile); b->print(logFile); Die("bstree::remove: !ordered at entry"); }
  175 */
  176     if (b->tree() != this) return(0);
  177     removes++;
  178 
  179     if (b->leftchild == 0) {
  180     SPLICE(b, b->rightchild);
  181     }
  182     else if (b->rightchild == 0) {
  183     SPLICE(b, b->leftchild);
  184     }
  185     else {
  186     /* Find and remove node to be promoted. */
  187     bsnode *t;
  188     FIRST(b->rightchild, t);
  189     SPLICE(t, t->rightchild);
  190 
  191     /* Plug promoted node in for the one being removed. */
  192     SPLICE(b, t);
  193     t->leftchild = b->leftchild;
  194     if (t->leftchild != 0)
  195         (t->leftchild)->parent = t;
  196     t->rightchild = b->rightchild;
  197     if (t->rightchild != 0)
  198         (t->rightchild)->parent = t;
  199     }
  200 
  201     ZERONODE(b);
  202     cnt--;
  203 /*
  204     if (!IsOrdered())
  205     { print(logFile); b->print(logFile); Die("bstree::remove: !ordered at exit"); }
  206 */
  207     return(b);
  208 }
  209 
  210 
  211 bsnode *bstree::first() {
  212     if (root == 0) return(0);
  213 
  214     bsnode *b;
  215     FIRST(root, b);
  216     return(b);
  217 }
  218 
  219 
  220 bsnode *bstree::last() {
  221     if (root == 0) return(0);
  222 
  223     bsnode *b;
  224     LAST(root, b);
  225     return(b);
  226 }
  227 
  228 
  229 bsnode *bstree::get(BstGetType type) {
  230 /*
  231     if (!IsOrdered())
  232     { print(logFile); Die("bstree::get: !ordered at entry"); }
  233 */
  234     if (root == 0) return(0);
  235     gets++;
  236 
  237     bsnode *b;
  238     if (type == BstGetMin) {
  239     FIRST(root, b);
  240     SPLICE(b, b->rightchild);
  241     }
  242     else {
  243     LAST(root, b);
  244     SPLICE(b, b->leftchild);
  245     }
  246 
  247     ZERONODE(b);
  248     cnt--;
  249 /*
  250     if (!IsOrdered())
  251     { print(logFile); Die("bstree::get: !ordered at exit"); }
  252 */
  253     return(b);
  254 }
  255 
  256 
  257 void bstree::clear() {
  258     bsnode *b;
  259     while((b = get()))
  260     ;
  261     if (cnt != 0) abort();
  262 /*  { print(logFile); Die("bstree::clear: tree not empty"); }*/
  263 }
  264 
  265 
  266 int bstree::count() {
  267     return(cnt);
  268 }
  269 
  270 
  271 /* TRUE if node OR it's value is member of the tree! */
  272 int bstree::IsMember(bsnode *b) {
  273     if (b->mytree == this) return(1);
  274     if (b->mytree != 0) return(0);
  275 
  276     for (bsnode *curr = root; curr != 0;) {
  277     int res = CmpFn(b, curr);
  278     if (res == 0) {
  279         if ((char *)b == (char *)curr) abort();
  280 /*      { print(logFile); b->print(logFile); Die("bstree::IsMember: found in tree"); }*/
  281         return(1);
  282     }
  283 
  284     if (res < 0)
  285         curr = curr->leftchild;
  286     else    /* res > 0 */
  287         curr = curr->rightchild;
  288     }
  289 
  290     return(0);
  291 }
  292 
  293 
  294 /* Sanity checker. */
  295 int bstree::IsOrdered() {
  296     bstree_iterator next(*this);
  297     bsnode *curr = 0;
  298     bsnode *prev = 0;
  299     while ((curr = next())) {
  300     if (prev != 0) {
  301         int res = CmpFn(prev, curr);
  302 
  303         if (res > 0 || (res == 0 && (char *)prev >= (char *)curr)) {
  304 /*
  305         prev->print(logFile);
  306         curr->print(logFile);
  307 */
  308         return(0);
  309         }
  310     }
  311     if (curr->leftchild != 0) {
  312         int res = CmpFn(curr->leftchild, curr);
  313 
  314         if (res > 0 || (res == 0 && (char *)curr->leftchild >= (char *)curr)) {
  315 /*
  316          (curr->leftchild)->print(logFile);
  317          curr->print(logFile);
  318 */
  319         return(0);
  320         }
  321     }
  322     if (curr->rightchild != 0) {
  323         int res = CmpFn(curr, curr->rightchild);
  324 
  325         if (res > 0 || (res == 0 && (char *)curr >= (char *)curr->rightchild)) {
  326 /*
  327          curr->print(logFile);
  328          (curr->rightchild)->print(logFile);
  329 */
  330         return(0);
  331         }
  332     }
  333 
  334     prev = curr;
  335     }
  336     return(1);
  337 }
  338 
  339 
  340 void bstree::print() {
  341     print(stderr);
  342 }
  343 
  344 
  345 void bstree::print(FILE *fp) {
  346     fflush(fp);
  347     print(fileno(fp));
  348 }
  349 
  350 
  351 void bstree::print(int fd) {
  352     /* first print out the bstree header */
  353     char buf[160];
  354     sprintf(buf, "%p : root = %p, cnt = %d, inserts = %d, removes = %d, gets = %d\n",
  355         this, root, cnt, inserts, removes, gets);
  356     write(fd, buf, strlen(buf));
  357 
  358     /* then print out all of the bsnodes */
  359     bstree_iterator next(*this);
  360     bsnode *b;
  361     while ((b = next()))
  362     b->print(fd);
  363 }
  364 
  365 
  366 /*  ***** Binary Search Tree Nodes  *****  */
  367 
  368 bsnode::bsnode() {
  369     mytree = 0;
  370     parent = 0;
  371     leftchild = 0;
  372     rightchild = 0;
  373 }
  374 
  375 
  376 bsnode::bsnode(bsnode& b) {
  377     abort();
  378 }
  379 
  380 
  381 int bsnode::operator=(bsnode& b) {
  382     abort();
  383     return(0); /* keep C++ happy */
  384 }
  385 
  386 
  387 bsnode::~bsnode() {
  388 }
  389 
  390 
  391 bstree *bsnode::tree() {
  392     if (mytree == 0)
  393     if (parent != 0 || leftchild != 0 || rightchild != 0) abort();
  394 /*      { print(logFile); Die("bsnode::tree: tree = 0 && ptr != 0"); }*/
  395 
  396     return(mytree);
  397 }
  398 
  399 
  400 void bsnode::print() {
  401     print(stderr);
  402 }
  403 
  404 
  405 void bsnode::print(FILE *fp) {
  406     fflush(fp);
  407     print(fileno(fp));
  408 }
  409 
  410 
  411 void bsnode::print(int fd) {
  412     char buf[80];
  413     sprintf(buf, "%p : tree = %p, parent = %p, left = %p, right = %p\n",
  414         this, mytree, parent, leftchild, rightchild);
  415     write(fd, buf, strlen(buf));
  416 }
  417 
  418 
  419 /*  *****  Binary Search Tree Iterator  *****  */
  420 
  421 bstree_iterator::bstree_iterator(bstree& Bst, BstIterOrder Order) {
  422     cbstree = &Bst;
  423     cbsnode = (bsnode *)-1;
  424     order = Order;
  425 }
  426 
  427 
  428 bsnode *bstree_iterator::operator()() {
  429     bsnode *prev = cbsnode;
  430 
  431     switch((intptr_t)cbsnode) {
  432     case -1:        /* state == NOTSTARTED */
  433         if (order == BstAscending) {
  434         cbsnode = cbstree->first();
  435         }
  436         else {
  437         cbsnode = cbstree->last();
  438         }
  439         break;
  440 
  441     default:        /* state == INPROGRESS */
  442         if (order == BstAscending) {
  443         if (cbsnode->rightchild == 0) {
  444             bsnode *t;
  445             do {
  446             t = cbsnode;
  447             cbsnode = cbsnode->parent;
  448             } while (cbsnode != 0 && cbsnode->rightchild == t);
  449         }
  450         else {
  451             FIRST(cbsnode->rightchild, cbsnode);
  452         }
  453         }
  454         else {
  455         if (cbsnode->leftchild == 0) {
  456             bsnode *t;
  457             do {
  458             t = cbsnode;
  459             cbsnode = cbsnode->parent;
  460             } while (cbsnode != 0 && cbsnode->leftchild == t);
  461         }
  462         else {
  463             LAST(cbsnode->leftchild, cbsnode);
  464         }
  465         }
  466         break;
  467 
  468     case 0:         /* state == FINISHED */
  469         break;
  470     }
  471 
  472     /* DEBUG!  Prevent looping! */
  473     if (cbsnode != 0 && cbsnode == prev)
  474     cbsnode = 0;
  475 
  476     return(cbsnode);
  477 }