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     finish:
 104       return retval;
 105     }
 106 };
 107
 108 /**
 109    Hash table with sliding sizes.
 110  */
 111 template<class V>
 112 class Dictionary
 113 {
 114   Fixed_size_dictionary<V> * fixed_p_;
 115
 116   /// set size to next prime, and copy contents
 117   void enlarge ()
 118     {
 119       Fixed_size_dictionary<V> *f = new Fixed_size_dictionary<V> (fixed_p_->size_idx_ +1);
 120       for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
 121         {
 122           if (fixed_p_->dict_arr_[i].free_b_)
 123             continue;
 124
 125           String nm (fixed_p_->dict_arr_[i].name_);
 126           int nl = f->lookup (nm);
 127
 128           f->dict_arr_[nl] = Dict_entry<V> (nm, fixed_p_->dict_arr_[i].value_);
 129         }
 130       delete fixed_p_;
 131       fixed_p_ = f;
 132     }
 133 public:
 134   Dictionary ()
 135     {
 136       fixed_p_ = new Fixed_size_dictionary<V> (0);
 137     }
 138   ~Dictionary ()
 139     {
 140       delete fixed_p_;
 141     }
 142   void operator = (Dictionary<V> const &src)
 143     {
 144       if (&src == this)
 145         return;
 146
 147       delete fixed_p_;
 148       fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
 149     }
 150   Dictionary (Dictionary<V> const &src)
 151     {
 152       fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
 153     }
 154   bool elem_b (String s) const
 155     {
 156       int l =  fixed_p_->lookup (s);
 157
 158       return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
 159     }
 160
 161   /**
 162      Find and return element.  If #s# is not in the table, create an entry in the table, and init
 163    */
 164   V& elem (String s)
 165     {
 166       int l;
 167       while ((l= fixed_p_->lookup (s)) <0)
 168         {
 169           enlarge ();
 170         }
 171
 172
 173        fixed_p_->dict_arr_[l].free_b_ = false;
 174        fixed_p_->dict_arr_[l].name_ = s;
 175        return fixed_p_->dict_arr_[l].value_;
 176     }
 177   V& operator [] (String k)
 178     {
 179       return elem (k);
 180     }
 181
 182   V operator [] (String k) const
 183     {
 184       return elem (k);
 185     }
 186
 187   V remove (String s)
 188     {
 189       return fixed_p_->remove (s);
 190     }
 191   friend class Dictionary_iter<V>;
 192 };
 193
 194
 195 #endif // DICTIONARY_HH