flower/include/dictionary.hh

   1 /*
   2   dictionary.hh -- declare Dictionary
   3
   4   source file of the Flower Library
   5
   6   (c)  1997--1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7 */
   8
   9
  10 #ifndef DICTIONARY_HH
  11 #define DICTIONARY_HH
  12
  13 #include "string.hh"
  14 #include "array.hh"
  15
  16 unsigned long prime_list (int idx);
  17 template<class V>
  18 struct Dict_entry
  19 {
  20   String name_;
  21   V value_;
  22   bool free_b_;
  23
  24   Dict_entry() {
  25     free_b_ = true;
  26   }
  27   Dict_entry (String s, V v)
  28     {
  29       name_ = s;
  30       value_ = v;
  31       free_b_ = false;
  32     }
  33 };
  34
  35 unsigned int hash (String);
  36
  37 /**
  38    A hash table of prime size.
  39
  40    We use quadratic probing.
  41  */
  42 template<class V>
  43 class Fixed_size_dictionary
  44 {
  45 public:
  46   Array<Dict_entry<V> > dict_arr_;
  47   int size_idx_;
  48   Fixed_size_dictionary (int size_idx)
  49     {
  50       size_idx_ = size_idx;
  51       int sz = prime_list(size_idx_);
  52       dict_arr_.set_size (sz);
  53     }
  54
  55   /// find #s#, or find first empty entry corresponding to #s#
  56   int lookup  (String s)
  57     {
  58       int sz =dict_arr_.size ();
  59       int i = hash (s) % sz;
  60       int j = 0;
  61       while (j <= sz/2) {
  62         if (dict_arr_[i].free_b_)
  63           return i;
  64
  65         if (dict_arr_[i].name_ == s)
  66           return i;
  67
  68         j++;
  69         i = (i + j*j) % sz;
  70       }
  71
  72       return -1;
  73     }
  74
  75   /// remove #s# from the hash table.
  76   V remove (String s)
  77     {
  78       assert (false);           // Untested routine.
  79       int sz =dict_arr_.size ();
  80       int i = hash (s) % sz;
  81       int j = 0;
  82       V retval;
  83       while (j <= sz/2 && dict_arr_[i].name_ != s)
  84         {
  85           assert (!dict_arr_[i].free_b_);
  86
  87
  88           j ++;
  89           i = (i + j*j) % sz;
  90         }
  91
  92       j++;
  93       int nexti = (i + j*j) % sz;
  94
  95       while (j <= sz/2 && !dict_arr_[i].free_b_)
  96         {
  97           dict_arr_[i] = dict_arr_[nexti];
  98           j++;
  99           i = nexti;
 100           nexti = (nexti + j*j)%sz;
 101         }
 102
 103       return retval;
 104     }
 105 };
 106
 107 /**
 108    Hash table with sliding sizes.
 109  */
 110 template<class V>
 111 class Dictionary
 112 {
 113   Fixed_size_dictionary<V> * fixed_p_;
 114
 115   /// set size to next prime, and copy contents
 116   void enlarge ()
 117     {
 118       Fixed_size_dictionary<V> *f = new Fixed_size_dictionary<V> (fixed_p_->size_idx_ +1);
 119       for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
 120         {
 121           if (fixed_p_->dict_arr_[i].free_b_)
 122             continue;
 123
 124           String nm (fixed_p_->dict_arr_[i].name_);
 125           int nl = f->lookup (nm);
 126
 127           f->dict_arr_[nl] = Dict_entry<V> (nm, fixed_p_->dict_arr_[i].value_);
 128         }
 129       delete fixed_p_;
 130       fixed_p_ = f;
 131     }
 132 public:
 133   Dictionary ()
 134     {
 135       fixed_p_ = new Fixed_size_dictionary<V> (0);
 136     }
 137   ~Dictionary ()
 138     {
 139       delete fixed_p_;
 140     }
 141   void operator = (Dictionary<V> const &src)
 142     {
 143       if (&src == this)
 144         return;
 145
 146       delete fixed_p_;
 147       fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
 148     }
 149   Dictionary (Dictionary<V> const &src)
 150     {
 151       fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
 152     }
 153   bool elem_b (String s) const
 154     {
 155       int l =  fixed_p_->lookup (s);
 156
 157       return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
 158     }
 159
 160   /**
 161      Find and return element.  If #s# is not in the table, create an entry in the table, and init
 162    */
 163   V& elem (String s)
 164     {
 165       int l;
 166       while ((l= fixed_p_->lookup (s)) <0)
 167         {
 168           enlarge ();
 169         }
 170
 171
 172        fixed_p_->dict_arr_[l].free_b_ = false;
 173        fixed_p_->dict_arr_[l].name_ = s;
 174        return fixed_p_->dict_arr_[l].value_;
 175     }
 176   V& operator [] (String k)
 177     {
 178       return elem (k);
 179     }
 180
 181   V operator [] (String k) const
 182     {
 183       V retval;
 184       if (!elem_b (k))
 185         return retval ;
 186       return ((Dictionary<V> *) this)->elem (k);
 187     }
 188
 189   V remove (String s)
 190     {
 191       return fixed_p_->remove (s);
 192     }
 193   friend class Dictionary_iter<V>;
 194 };
 195
 196
 197 #endif // DICTIONARY_HH