"Fossies" - the Fresh Open Source Software Archive

Member "ncc-2.8/inttree.C" (17 May 2003, 3206 Bytes) of package /linux/privat/old/ncc-2.8.tar.gz:

    1 /******************************************************************************
    2 
    3     The Integer Tree
    4 
    5     We want to store things whos comparison key is an integer value.
    6 
    7     Whether a node is less or more compared to another node will be
    8     just a matter of the n-th bit of the integer, where n the current
    9     depth. For example the Least Significant Bit will be used to
   10     specify less (0) or more (1) for the comparison with the root node.
   11 
   12     Each integer therefore carries its tree path (0 - go less, 1 - go more)
   13 
   14     For any possible order of the nodes the tree will NEVER exceed the
   15     depth of 33 (for 32-bit integers).
   16 
   17     Even though it could be unbalanced, its logarithmic unbalance.
   18     We will always be able to find something in less than 32 steps.
   19         O(32)=O(1) < O(log(n)) < O(n) < O(n^2) < O(\infty)
   20 
   21     Moverover, if the numbers are in a range 0..2^n the depth will
   22     always be <= n+1. For a database with 65536 ID-elements, finds will
   23     be a matter of 17 steps.
   24 
   25     In order to remove an element from the tree any node can replace
   26     the node to be removed as long as:
   27         - It is below it
   28         - It is a terminal node
   29     Because it has the same path and no other node's postition is
   30     changed in the tree.
   31 
   32 ******************************************************************************/
   33 /**************************************************************************
   34  Copyright (C) 2000, 2001, 2002 Stelios Xanthakis
   35 **************************************************************************/
   36 
   37 #include <stdio.h>
   38 
   39 #include "inttree.h"
   40 
   41 unsigned int intTree::Query;
   42 intNode **intTree::FoundSlot;
   43 
   44 intTree::intTree ()
   45 {
   46     cnt = 0;
   47     root = NULL;
   48     FoundSlot = NULL;
   49 }
   50 
   51 intNode::~intNode ()
   52 {
   53     if (less) delete less;
   54     if (more) delete more;
   55 }
   56 
   57 intNode *intTree::intFind (unsigned int q)
   58 {
   59     Query = q;
   60 
   61     intNode *n;
   62 
   63     if (!(n = root)) {
   64         FoundSlot = &root;
   65         return NULL;
   66     }
   67 
   68     FoundSlot = NULL;
   69 
   70     for (unsigned int bt = 1; bt; bt *= 2) {
   71         if (n->Key == q) return n;
   72         if (q & bt)
   73             if (n->less) n = n->less;
   74             else {
   75                 FoundSlot = &n->less;
   76                 return NULL;
   77             }
   78         else
   79             if (n->more) n = n->more;
   80             else {
   81                 FoundSlot = &n->more;
   82                 return NULL;
   83             }
   84     }
   85 
   86     fprintf (stderr, "intTree FUBAR. Segmentation Fault. sorry\n");
   87     return NULL;
   88 }
   89 
   90 intNode::intNode (intTree *i)
   91 {
   92     if (i->FoundSlot) addself (i);
   93 
   94     less = more = NULL;
   95 }
   96 
   97 void intNode::addself (intTree *i)
   98 {
   99     *i->FoundSlot = this;
  100     ++i->cnt;
  101     i->FoundSlot = NULL;
  102     Key = i->Query;
  103 }
  104 
  105 void intNode::intRemove (intTree *i)
  106 {
  107     unsigned int isroot, bt = 0;
  108     intNode *n = i->root;
  109 
  110     if (!(isroot = n == this))
  111         for (bt = 1; bt; bt *= 2)
  112             if (Key & bt)   // avoid braces like hell
  113                 if (n->less != this) n = n->less;
  114                 else break;
  115             else        // yes but why?
  116                 if (n->more != this) n = n->more;
  117                 else break;
  118 
  119     if (!less && !more)
  120         if (isroot) i->root = NULL;
  121         else
  122             if (Key & bt) n->less = NULL;
  123             else n->more = NULL;
  124     else {
  125         intNode *r = this, *rp = NULL;
  126         while (r->more || r->less) {
  127             rp = r;
  128             r = (r->more) ? r->more : r->less;
  129         }
  130         if (isroot) i->root = r;
  131         else
  132             if (Key & bt) n->less = r;
  133             else n->more = r;
  134         if (rp->more == r) rp->more = NULL;
  135         else rp->less = NULL;
  136         r->more = more;
  137         r->less = less;
  138     }
  139 
  140     i->cnt--;
  141     less = more = NULL;
  142 }