home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 7 / FreshFishVol7.bin / bbs / gnu / libg++-2.6-fsf.lha / libg++-2.6 / libg++ / etc / ADT-examples / Patricia.cc < prev    next >
C/C++ Source or Header  |  1993-01-15  |  7KB  |  202 lines
  1. /* Implements the PATRICIA trie abstraction. */
  2.  
  3. #include <std.h>
  4. #include "Patricia.h"
  5.  
  6. const int HI_WORD = 7;         /* Hi-order bit, starting count from 0 */
  7. const int BIT_MASK = 07;       /* WORD_SHIFT low-order bits enabled */
  8. const int WORD_BITS = 8;       /* Number of Bits in a Block */
  9. const int WORD_SHIFT = 3;      /* i.e. lg (WORD_BITS) */
  10.  
  11. /* Normalizes the ith Bit representation */
  12. inline int get_bit (int i) { return HI_WORD - i; }
  13.  
  14. Trie_Node::Trie_Node (char *k, int len, CONTENTS new_contents, int b): 
  15.      branch_bit (b)
  16. {
  17.   trie_rec.set_contents (new_contents);
  18.  
  19.   /* Dynamically compute the length, if it's not given */
  20.   if (!len)             
  21.     len = strlen (k) + 1;
  22.   trie_rec.set_key (strcpy (new char[len], k));
  23. }
  24.  
  25. /* Recursively free tree memory via modified post-order traversal */
  26. void 
  27. Patricia_Trie::dispose_trie (Trie_Node *root)
  28. {
  29.   if (root->left->branch_bit <= root->branch_bit &&
  30.       root->right->branch_bit <= root->branch_bit)
  31.     ;                           /* do nothing! */
  32.   else if (root->left->branch_bit <= root->branch_bit) 
  33.     dispose_trie (root->right);
  34.   else if (root->right->branch_bit <= root->branch_bit) 
  35.     dispose_trie (root->left);
  36.   else
  37.     {
  38.       dispose_trie (root->left);
  39.       dispose_trie (root->right);
  40.     }
  41.   delete root;
  42. }
  43.  
  44. /* Initializes Patricia_Trie, using dummy header. */
  45.  
  46. Patricia_Trie::Patricia_Trie (void)
  47. {                           
  48.   root        = new Trie_Node;
  49.   root->left  = root;
  50.   root->right = root;
  51. }
  52.  
  53. /* Frees all dynamic memory in Patricia Trie */
  54. Patricia_Trie::~Patricia_Trie (void)
  55. {                           
  56.   dispose_trie (root->left);
  57.   delete root;
  58. }
  59.  
  60. /* Attempts to locate the record associated with Key.  The basic
  61.    algorithm is abstractly similar to Sedgewick's description in his
  62.    Algorithm's book.  However, I've modified things to speed up the Bit
  63.    comparisons greatly, as well as to run the Branch_Bit index from
  64.    0..whatever, since this allows arbitrarily large keys (For some
  65.    strange reason Sedgewick goes from some predefined limit,
  66.    Max_Branch_Bit, *downto* 0!!).
  67.  
  68.    Most of the contortions below help manage a Bit cache, which
  69.    reduces the total amount of work required to test the next Branch_Bit.
  70.    Empirical tests revealed that this was main bottleneck in the Find
  71.    routine.  To make the algorithm work I needed to have the first Bit in
  72.    the first word always be 0.  Therefore, I've ordered the bits from
  73.    high-order Bit to low-order Bit (e.g., 8 .. 1), running from word 0
  74.    to word K.  This fits intuitively with how you might draw the bits onn
  75.    paper, but *not* with how it would work if you programmed it in the
  76.    normal way (i.e., running from bit 1 to 8, from word 0 to K).  At
  77.    any rate, that's what the BIT macro is for, it normalizes my abstract
  78.    concept of bit-order with the actual bit-order. */
  79.      
  80. Trie_Record *
  81. Patricia_Trie::find (char *key)
  82. {
  83.   
  84.   Trie_Node *parent;
  85.   Trie_Node *cur   = root->left; /* Root is *always* a dummy node, skip it */
  86.   char      *block = key;        /* Pointer to Current Block of Bits */
  87.   int        lower = 0;
  88.   
  89.   do
  90.     {
  91.       parent  = cur;   
  92.       int bit = cur->branch_bit - lower;
  93.       
  94.       /* Oh well, time to refill the Bit cache! 
  95.          This loop gets executed infrequently, in general */
  96.       if (bit >= WORD_BITS)
  97.         
  98.         while (lower + WORD_BITS <= cur->branch_bit)
  99.           {
  100.             lower += WORD_BITS;
  101.             ++block;
  102.             bit -= WORD_BITS;
  103.           }                 
  104.       
  105.       cur = (is_bit_set (*block, get_bit (bit)) ? cur->right : cur->left);
  106.     }
  107.   while (parent->branch_bit < cur->branch_bit);
  108.   
  109.   return &cur->trie_rec;                   /* Let calling routine worry whether Keys matched! */
  110. }
  111.  
  112. /* Inserts a new KEY and its associated CONTENTS into the trie. */
  113.  
  114. void 
  115. Patricia_Trie::insert (char *key, CONTENTS contents, int key_len)
  116. {
  117.   Trie_Node *parent;
  118.   Trie_Node *cur   = root;
  119.   char      *block = key;
  120.   int        lower = 0;
  121.   
  122.   /* This loop is essentially the same as in the Find routine. */
  123.  
  124.   do
  125.     {                           
  126.       parent  = cur;   
  127.       int bit = cur->branch_bit - lower;
  128.       if (bit >= WORD_BITS)
  129.         while (lower + WORD_BITS <= cur->branch_bit)
  130.           {
  131.             lower += WORD_BITS;
  132.             ++block;
  133.             bit -= WORD_BITS;
  134.           }
  135.       cur = (is_bit_set (*block, get_bit (bit)) ? cur->right : cur->left);
  136.     } 
  137.   while (parent->branch_bit < cur->branch_bit);
  138.   
  139.   /* Exclude duplicates */
  140.   if (strcmp (key, cur->trie_rec.get_key ()))
  141.     {                           
  142.       char *key_block = key;
  143.       char *cur_block = cur->trie_rec.get_key ();
  144.       
  145.       /* Find the first word where Bits differ, skip common prefixes. */
  146.  
  147.       for (int first_bit_diff = 0;  
  148.            *cur_block == *key_block;         
  149.            first_bit_diff += WORD_BITS)
  150.         cur_block++, key_block++;
  151.  
  152.       /* Now, find location of that Bit, xor does us a favor here. */
  153.  
  154.       for (int bit = *cur_block ^ *key_block; 
  155.            !(bit & POW2 (HI_WORD));     
  156.            bit <<= 1)
  157.         first_bit_diff++;
  158.       
  159.       /* *Not* adding at a leaf node */
  160.       if (parent->branch_bit > first_bit_diff)
  161.         {                       
  162.           
  163.           /* This is almost identical to the original Find above, however, we are */
  164.           /* guaranteed to end up at an internal node, rather than a leaf. */
  165.           
  166.           for (cur = root, lower = 0, cur_block = key; ;)
  167.             {
  168.               parent  = cur;   
  169.               int bit = cur->branch_bit - lower;
  170.  
  171.               if (bit >= WORD_BITS)
  172.  
  173.                 while (lower + WORD_BITS <= cur->branch_bit)
  174.                   {
  175.                     lower += WORD_BITS;
  176.                     ++cur_block;
  177.                     bit -= WORD_BITS;
  178.                   }
  179.               
  180.               cur = (is_bit_set (*cur_block, get_bit (bit)) ? cur->right : cur->left);
  181.               if (cur->branch_bit >= first_bit_diff) 
  182.                 break;
  183.             }
  184.         }
  185.       
  186.       Trie_Node *t = new Trie_Node (key, key_len, contents, first_bit_diff);
  187.       
  188.       /* Key_Block was saved from above, this avoids some costly recomputation. */
  189.       if (is_bit_set (*key_block, get_bit (first_bit_diff & BIT_MASK)))
  190.         t->left = cur, t->right = t;
  191.       else
  192.         t->left = t, t->right = cur;
  193.       
  194.       /* Determine whether the new node goes to the left or right of its parent */
  195.       block = key + (parent->branch_bit >> WORD_SHIFT);
  196.  
  197.       (is_bit_set (*block, get_bit (parent->branch_bit & BIT_MASK))
  198.        ? parent->right : parent->left) = t;
  199.     }
  200. }
  201.  
  202.