patch::: 1.4.6.po1

[lilypond.git] / flower / include / hash-table.hh

diff --git a/flower/include/hash-table.hh b/flower/include/hash-table.hh
index ef497f1c757185607eefb6d23d395572e99fdaa4..8cc51f2e1b403f490d1b69300423f12bc28463d2 100644 (file)
--- a/flower/include/hash-table.hh
+++ b/flower/include/hash-table.hh
@@ -12,6 +12,15 @@
 
 unsigned int int_hash (int);
 unsigned long prime_list (int idx);
+template<class K, class V> struct Hash_table_iter;
+
+template<class K>
+unsigned int
+pointer_hash (K *p)
+{
+  return int_hash ((unsigned int) p);
+}
+
 template<class K, class V>
 struct Hash_table_entry
 {
@@ -19,7 +28,7 @@ struct Hash_table_entry
   V value_;
   bool free_b_;
 
-  Hash_table_entry() {
+  Hash_table_entry () {
     free_b_ = true;
   }
   Hash_table_entry (K s, V v)
@@ -34,7 +43,9 @@ struct Hash_table_entry
    A hash table of prime size.
 
    We use quadratic probing.  
- */
+
+  DEPRECATED. Use either SCM (preferred) or STL 
+*/
 template<class K, class V>
 class Fixed_size_hash_table
 {
@@ -44,59 +55,38 @@ public:
   Fixed_size_hash_table (int size_idx)
     {
       size_idx_ = size_idx;
-      int sz = prime_list(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  (K s, unsigned int initial_hash)
+  int lookup (K s, unsigned int initial_hash)
     {
       int sz =dict_arr_.size ();
-      int i = initial_hash % sz;
+      initial_hash = initial_hash % sz; 
+      int i;
       int j = 0;
       while (j <= sz/2) {
+       i = (initial_hash + j*j) % sz;
+       
        if (dict_arr_[i].free_b_)
          return i;
-           
+
        if (dict_arr_[i].key_ == s)
          return i;
 
        j++;
-       i = (i + j*j) % sz;
       }
 
+      
       return -1;
     }
 
   /// remove #s# from the hash table.  
   V remove (K s, unsigned int initial_hash)
     {
-      assert (false);          // Untested routine.
-      int sz =dict_arr_.size ();
-      int i = initial_hash % sz;
-      int j = 0;
-      V retval;
-      while (j <= sz/2 && dict_arr_[i].key_ != s)
-       {
-         assert (!dict_arr_[i].free_b_);
-           
-       
-         j ++;
-         i = (i + j*j) % sz;
-       }
-
-      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;
-       }
-      
-      return retval;
+      // TODO
+      assert (false);
     }
 };
 
@@ -112,13 +102,13 @@ class Hash_table
     {
       Fixed_size_hash_table<K,V> *f = new Fixed_size_hash_table<K,V> (fixed_p_->size_idx_ +1);
       
-      for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
+      for (int i=0; i < fixed_p_->dict_arr_.size (); i++)
        {
          if (fixed_p_->dict_arr_[i].free_b_)
            continue;
 
          K nm (fixed_p_->dict_arr_[i].key_);
-         unsigned int h = (*hash_func_)(nm);
+         unsigned int h = (*hash_func_) (nm);
          int nl = f->lookup (nm, h);
          
          f->dict_arr_[nl] = Hash_table_entry<K,V> (nm, fixed_p_->dict_arr_[i].value_);
@@ -159,18 +149,18 @@ public:
     }
   bool elem_b (K s) const
     {
-      int l =  fixed_p_->lookup (s, (*hash_func_)(s));
+      int l =  fixed_p_->lookup (s, (*hash_func_) (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
-   */
+     Find and return element.  If #s# is not in the table, create an
+     entry in the table, and init */
   V& elem (K s)
     {
       int l;
-      unsigned int h = (*hash_func_)(s);
+      unsigned int h = (*hash_func_) (s);
       while ((l= fixed_p_->lookup (s,h)) <0)
        {
          enlarge ();
@@ -180,6 +170,17 @@ public:
        fixed_p_->dict_arr_[l].key_ = s;
        return fixed_p_->dict_arr_[l].value_;
     }
+  bool try_retrieve (K k, V *v)
+  {
+    int l =  fixed_p_->lookup (k, (*hash_func_) (k));
+    if (l < 0 || fixed_p_->dict_arr_[l].free_b_)
+      return false;
+    else
+      {
+       *v = fixed_p_->dict_arr_[l].value_;
+       return true;
+      }
+  }
   V elem (K s) const
     {
       return const_elem (s);
@@ -187,8 +188,8 @@ public:
   V const_elem (K k) const
   {
       V retval;
-      if (elem_b (k))
-       retval = ((Hash_table<K,V>*)this)->elem (k);
+      assert (elem_b (k));
+      retval = ((Hash_table<K,V>*)this)->elem (k);
       return retval;
   }
   V& operator [] (K k)
@@ -203,11 +204,11 @@ public:
 
   V remove (K s)
     {
-      return fixed_p_->remove (s, (*hash_func_)(s));
+      return fixed_p_->remove (s, (*hash_func_) (s));
     }
   friend class Hash_table_iter<K,V>;
 public:
-  unsigned int (*hash_func_)(K);
+  unsigned int (*hash_func_) (K);
 };