lib-src/tries/hashtrie.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <string.h>
  26 #include <AD/tries/hashtrie.h>
  27
  28 HashTrie::HashTrie() : slots(0), symbol(0), back(0) {}
  29
  30 inline int log2(register long n)
  31 {  register int m;
  32    for (m = 0, n--; n > 0; m++) n >>= 1;
  33    return m;
  34 }
  35
  36 void HashTrie::clear()
  37 {   memset(back,-1,slots * sizeof(Node));
  38     back[0] = 0;  // the root is always occupied
  39     count = 0;
  40 }
  41
  42 void HashTrie::init(long n)
  43 {   n = 1 << log2(n);
  44     slots  = n;
  45     mask   = n - 1;
  46     symbol = new Symbol [n];
  47     back   = new Node [n];
  48 }
  49
  50 HashTrie::HashTrie(long n)
  51 {  init(n);
  52    clear();
  53 };
  54
  55 HashTrie::HashTrie(const HashTrie& trie)
  56    : symbol(0), back(0)
  57 {  *this = trie; }
  58
  59 HashTrie::~HashTrie()
  60 {   delete [] symbol;
  61     delete [] back;
  62 }
  63
  64 HashTrie& HashTrie :: operator = (const HashTrie& trie)
  65 {   if (this != &trie) {
  66        delete [] symbol;
  67        delete [] back;
  68        init(trie.slots);
  69        count = trie.count;
  70        memcpy(symbol,trie.symbol,trie.slots * sizeof(Symbol));
  71        memcpy(back,trie.back,trie.slots * sizeof(Node));
  72     }
  73     return *this;
  74 }