testing new non-autotools build system

[chaz/yoink] / src / stlplus / containers / hash.tpp

diff --git a/src/moof/stlplus/hash.tpp b/src/stlplus/containers/hash.tpp
old mode 100755 (executable)
new mode 100644 (file)
similarity index 82%
rename from src/moof/stlplus/hash.tpp
rename to src/stlplus/containers/hash.tpp
index bcb5bc5..9a1e4e9
--- a/src/moof/stlplus/hash.tpp
+++ b/src/stlplus/containers/hash.tpp
@@ -6,6 +6,7 @@
 //   License:   BSD License, see ../docs/license.html\r
 \r
 ////////////////////////////////////////////////////////////////////////////////\r
+#include <iomanip>\r
 \r
 namespace stlplus\r
 {\r
@@ -22,13 +23,13 @@ namespace stlplus
     hash_element<K,T,H,E>* m_next;\r
     unsigned m_hash;\r
 \r
-    hash_element(const hash<K,T,H,E>* owner, const K& key, const T& data, unsigned hash) : \r
-      m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash) \r
+    hash_element(const hash<K,T,H,E>* owner, const K& key, const T& data, unsigned hash) :\r
+      m_master(owner,this), m_value(key,data), m_next(0), m_hash(hash)\r
       {\r
       }\r
 \r
-    hash_element(const hash<K,T,H,E>* owner, const std::pair<const K,T>& value, unsigned hash) : \r
-      m_master(owner,this), m_value(value), m_next(0), m_hash(hash) \r
+    hash_element(const hash<K,T,H,E>* owner, const std::pair<const K,T>& value, unsigned hash) :\r
+      m_master(owner,this), m_value(value), m_next(0), m_hash(hash)\r
       {\r
       }\r
 \r
@@ -441,7 +442,7 @@ namespace stlplus
   // remove a key from the table - return true if the key was found and removed, false if it wasn't present\r
 \r
   template<typename K, typename T, class H, class E>\r
-  bool hash<K,T,H,E>::erase(const K& key)\r
+  unsigned hash<K,T,H,E>::erase(const K& key)\r
   {\r
     unsigned hash_value_full = H()(key);\r
     unsigned bin = hash_value_full % m_bins;\r
@@ -465,9 +466,43 @@ namespace stlplus
       delete current;\r
       // remember to maintain the size count\r
       m_size--;\r
-      return true;\r
+      return 1;\r
     }\r
-    return false;\r
+    return 0;\r
+  }\r
+\r
+  // remove an element from the hash table using an iterator (std::map equivalent)\r
+  template<typename K, typename T, class H, class E>\r
+  TYPENAME hash<K,T,H,E>::iterator hash<K,T,H,E>::erase(TYPENAME hash<K,T,H,E>::iterator it)\r
+  {\r
+    // work out what the next iterator is in order to return it later\r
+    TYPENAME hash<K,T,H,E>::iterator next(it);\r
+    ++next;\r
+    // we now need to find where this item is - made difficult by the use of\r
+    // single-linked lists which means I have to search through the bin from\r
+    // the top in order to unlink from the list.\r
+    unsigned hash_value_full = it.node()->m_hash;\r
+    unsigned bin = hash_value_full % m_bins;\r
+    // scan the list for this element\r
+    // need to keep a previous pointer because the lists are single-linked\r
+    hash_element<K,T,H,E>* previous = 0;\r
+    for (hash_element<K,T,H,E>* current = m_values[bin]; current; previous = current, current = current->m_next)\r
+    {\r
+      // direct test on the address of the element\r
+      if (current != it.node()) continue;\r
+      // found this iterator, so unhook the element from the list\r
+      if (previous)\r
+        previous->m_next = current->m_next;\r
+      else\r
+        m_values[bin] = current->m_next;\r
+      // destroy it\r
+      delete current;\r
+      current = 0;\r
+      // remember to maintain the size count\r
+      m_size--;\r
+      break;\r
+    }\r
+    return next;\r
   }\r
 \r
   template<typename K, typename T, class H, class E>\r
@@ -569,6 +604,54 @@ namespace stlplus
     return hash_iterator<K,T,H,E,std::pair<const K,T> >(this);\r
   }\r
 \r
+  template<typename K, typename T, class H, class E>\r
+  void hash<K,T,H,E>::debug_report(std::ostream& str) const\r
+  {\r
+    // calculate some stats first\r
+    unsigned occupied = 0;\r
+    unsigned min_in_bin = m_size;\r
+    unsigned max_in_bin = 0;\r
+    for (unsigned i = 0; i < m_bins; i++)\r
+    {\r
+      if (m_values[i]) occupied++;\r
+      unsigned count = 0;\r
+      for (hash_element<K,T,H,E>* item = m_values[i]; item; item = item->m_next) count++;\r
+      if (count > max_in_bin) max_in_bin = count;\r
+      if (count < min_in_bin) min_in_bin = count;\r
+    }\r
+    // now print the table\r
+    str << "------------------------------------------------------------------------" << std::endl;\r
+    str << "| size:     " << m_size << std::endl;\r
+    str << "| bins:     " << m_bins << std::endl;\r
+    str << "| loading:  " << loading() << " ";\r
+    if (m_rehash)\r
+      str << "auto-rehash at " << m_rehash << std::endl;\r
+    else\r
+      str << "manual rehash" << std::endl;\r
+    str << "| occupied: " << occupied \r
+        << std::fixed << " (" << (100.0*(float)occupied/(float)m_bins) << "%)" << std::scientific\r
+        << ", min = " << min_in_bin << ", max = " << max_in_bin << std::endl;\r
+    str << "|-----------------------------------------------------------------------" << std::endl;\r
+    str << "|  bin         0     1     2     3     4     5     6     7     8     9" << std::endl;\r
+    str << "|        ---------------------------------------------------------------";\r
+    for (unsigned j = 0; j < m_bins; j++)\r
+    {\r
+      if (j % 10 == 0)\r
+      {\r
+        str << std::endl;\r
+        str << "| " << std::setw(6) << std::right << (j/10*10) << std::left << " |";\r
+      }\r
+      unsigned count = 0;\r
+      for (hash_element<K,T,H,E>* item = m_values[j]; item; item = item->m_next) count++;\r
+      if (!count)\r
+        str << "     .";\r
+      else\r
+        str << std::setw(6) << std::right << count << std::left;\r
+    }\r
+    str << std::endl;\r
+    str << "------------------------------------------------------------------------" << std::endl;\r
+  }\r
+\r
   ////////////////////////////////////////////////////////////////////////////////\r
 \r
 } // end namespace stlplus\r