X-Git-Url: https://git.donarmstrong.com/?a=blobdiff_plain;f=flower%2Finclude%2Fdictionary.hh;h=55f0e4fedd932edba9f1c4f320319860311b362f;hb=refs%2Ftags%2Frelease%2F1.0.17;hp=b25fc84b49ac106368bb0d94eb288b66a4df993c;hpb=9f88b957750d767f2230004a4bf2d4eccca7decf;p=lilypond.git

diff --git a/flower/include/dictionary.hh b/flower/include/dictionary.hh
index b25fc84b49..55f0e4fedd 100644
--- a/flower/include/dictionary.hh
+++ b/flower/include/dictionary.hh
@@ -11,28 +11,185 @@
 #define DICTIONARY_HH
 
 #include "string.hh"
-#include "assoc.hh"
+#include "array.hh"
+
+unsigned long prime_list (int idx);
+template<class V>
+struct Dict_entry
+{
+  String name_;
+  V value_;
+  bool free_b_;
+
+  Dict_entry() {
+    free_b_ = true;
+  }
+  Dict_entry (String s, V v)
+    {
+      name_ = s;
+      value_ = v;
+      free_b_ = false;
+    }
+};
+
+unsigned int hash (String);
 
 /**
-  UGH:  write a String_hash template, 
+   A hash table of prime size.
 
-  SEE:
-  
-       #include <search.h>
+   We use quadratic probing.  
+ */
+template<class V>
+class Fixed_size_dictionary
+{
+public:
+  Array<Dict_entry<V> > dict_arr_; 
+  int size_idx_;
+  Fixed_size_dictionary (int size_idx)
+    {
+      size_idx_ = size_idx;
+      int sz = prime_list(size_idx_);
+      dict_arr_.set_size (sz);
+    }
+
+  /// find #s#, or find first empty entry corresponding to #s#
+  int lookup  (String s)
+    {
+      int sz =dict_arr_.size ();
+      int i = hash (s) % sz;
+      int j = 0;
+      while (j <= sz/2) {
+	if (dict_arr_[i].free_b_)
+	  return i;
+	    
+	if (dict_arr_[i].name_ == s)
+	  return i;
 
-       ENTRY *hsearch(ENTRY item, ACTION action);
+	j++;
+	i = (i + j*j) % sz;
+      }
 
-       int     hcreate (unsigned nel);
+      return -1;
+    }
 
-       void    hdestroy (void);
+  /// remove #s# from the hash table.  
+  V remove (String s)
+    {
+      assert (false);		// Untested routine.
+      int sz =dict_arr_.size ();
+      int i = hash (s) % sz;
+      int j = 0;
+      V retval;
+      while (j <= sz/2 && dict_arr_[i].name_ != s)
+	{
+	  assert (!dict_arr_[i].free_b_);
+	    
+	
+	  j ++;
+	  i = (i + j*j) % sz;
+	}
 
-  (should be frobnified to allow multiple hashes)
+      j++;
+      int nexti = (i + j*j) % sz;
+
+      while (j <= sz/2 && !dict_arr_[i].free_b_)
+	{
+	  dict_arr_[i] = dict_arr_[nexti];
+	  j++;
+	  i = nexti;
+	  nexti = (nexti + j*j)%sz;
+	}
+      
+    finish:
+      return retval;
+    }
+};
+
+/**
+   Hash table with sliding sizes. 
  */
-template<class T>
-class Dictionary : public Assoc<String, T>
+template<class V>
+class Dictionary
 {
+  Fixed_size_dictionary<V> * fixed_p_;
+
+  /// set size to next prime, and copy contents
+  void enlarge ()
+    {
+      Fixed_size_dictionary<V> *f = new Fixed_size_dictionary<V> (fixed_p_->size_idx_ +1);
+      for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
+	{
+	  if (fixed_p_->dict_arr_[i].free_b_)
+	    continue;
+
+	  String nm (fixed_p_->dict_arr_[i].name_);
+	  int nl = f->lookup (nm);
+	  
+	  f->dict_arr_[nl] = Dict_entry<V> (nm, fixed_p_->dict_arr_[i].value_);
+	}
+      delete fixed_p_;
+      fixed_p_ = f;
+    }
 public:
-  
+  Dictionary ()
+    {
+      fixed_p_ = new Fixed_size_dictionary<V> (0);
+    }
+  ~Dictionary ()
+    {
+      delete fixed_p_;
+    }
+  void operator = (Dictionary<V> const &src)
+    {
+      if (&src == this)
+	return;
+      
+      delete fixed_p_;
+      fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
+    }
+  Dictionary (Dictionary<V> const &src)
+    {
+      fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
+    }
+  bool elem_b (String s) const
+    {
+      int l =  fixed_p_->lookup (s);
+
+      return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
+    }
+
+  /**
+     Find and return element.  If #s# is not in the table, create an entry in the table, and init
+   */
+  V& elem (String s)
+    {
+      int l;
+      while ((l= fixed_p_->lookup (s)) <0)
+	{
+	  enlarge ();
+	}
+
+      
+       fixed_p_->dict_arr_[l].free_b_ = false;
+       fixed_p_->dict_arr_[l].name_ = s;
+       return fixed_p_->dict_arr_[l].value_;
+    }
+  V& operator [] (String k)
+    {
+      return elem (k);
+    }
+
+  V operator [] (String k) const
+    {
+      return elem (k);
+    }
+
+  V remove (String s)
+    {
+      return fixed_p_->remove (s);      
+    }
+  friend class Dictionary_iter<V>;
 };
 
+
 #endif // DICTIONARY_HH