[Assorted-commits] SF.net SVN: assorted:[1258] cpp-commons/trunk/src/commons/fast_map.h

[<yan...@us...>]

Revision: 1258
          http://assorted.svn.sourceforge.net/assorted/?rev=1258&view=rev
Author:   yangzhang
Date:     2009-03-06 07:22:51 +0000 (Fri, 06 Mar 2009)

Log Message:
-----------
added fast_map

Added Paths:
-----------
    cpp-commons/trunk/src/commons/fast_map.h

Added: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	                        (rev 0)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-06 07:22:51 UTC (rev 1258)
@@ -0,0 +1,128 @@
+#ifndef COMMONS_DENSE_HASH_MAP_H
+#define COMMONS_DENSE_HASH_MAP_H
+
+#include <backward/hash_fun.h>
+#include <cassert>
+#include <commons/array.h>
+#include <utility>
+
+namespace commons {
+
+  using namespace std;
+  using namespace __gnu_cxx;
+
+  // TODO template <typename K, typename V>
+  /**
+   * Quadratic internal probing with triangular numbers, a la
+   * google::dense_hash_map.
+   */
+  class fast_map
+  {
+    private:
+      static const size_t initsize = 1<<20;
+      typedef pair<int, int> entry;
+      commons::array<entry> table;
+      int empty_key, deleted_key;
+      size_t count;
+      hash<int> hasher;
+      void resize(size_t size) {
+        commons::array<entry> tmp(size);
+        // TODO faster?
+        for (size_t i = 0; i < size; ++i)
+          tmp[i].first = empty_key;
+        swap(table, tmp);
+        // Rehash old values over into new table.
+        size_t mask = table.size() - 1;
+        for (size_t i = 0; i < tmp.size(); ++i) {
+          if (tmp[i].first != empty_key && tmp[i].first != deleted_key) {
+            // NOTE: second major speedup, originally:
+            // (*this)[tmp[i].first] = tmp[i].second;
+            // Don't want to simply reuse the general lookup, since we know
+            // we're starting with a blank slate.
+            size_t pos = hasher(tmp[i].first) & mask;
+            for (size_t probe = 0;
+                 table[pos].first != empty_key;
+                 ++probe, pos = (pos + probe) & mask) {
+              assert(probe < table.size());
+            }
+            table[pos] = tmp[pos];
+          }
+        }
+      }
+      void grow() { resize(table.size() << 1); }
+      void shrink() { resize(table.size() >> 1); }
+    public:
+      fast_map() : table(0), empty_key(0), deleted_key(0), count(0) {}
+      void set_empty_key(int k) { empty_key = k; resize(initsize); }
+      void set_deleted_key(int k) { deleted_key = k; resize(initsize); }
+      size_t size() const { return count; }
+      int &operator[](int k) {
+        size_t mask = table.size() - 1;
+        size_t probe, pos = hasher(k) & mask; // , unset = -1, first_deleted = unset;
+        // Lookup.  Skip over deleted entries (but remembering the first one
+        // seen as an open slot if we later decide to insert).  If we find an
+        // empty spot, try returning the earlier deleted spot first.  If we
+        // find the key, return that.
+        for (probe = 0;
+             table[pos].first != deleted_key && table[pos].first != empty_key && table[pos].first != k;
+             ++probe, pos = (pos + probe) & mask) {
+          assert(probe < table.size());
+        }
+        if (table[pos].first == deleted_key) {
+          size_t first_deleted = pos;
+          for (;
+               table[pos].first != empty_key && table[pos].first != k;
+               ++probe, pos = (pos + probe) & mask) {
+            assert(probe < table.size());
+          }
+          if (table[pos].first == empty_key) {
+            // Inserting new entry.  Grow table if necessary.
+            if (++count > table.size() * 3 / 4) {
+              --count;
+              grow();
+              return (*this)[k];
+            }
+            pos = first_deleted;
+            table[pos].first = k;
+          }
+        } else if (table[pos].first == empty_key) {
+          // Inserting new entry.  Grow table if necessary.
+          if (++count > table.size() * 3 / 4) {
+            --count;
+            grow();
+            return (*this)[k];
+          }
+          table[pos].first = k;
+        }
+        return table[pos].second;
+#if 0
+        for (probe = 0; ; ++probe) {
+          assert(probe < table.size());
+          pos = (pos + probe) & mask;
+          int &key = table[pos].first;
+          if (key == deleted_key && first_deleted == unset) {
+            first_deleted = pos;
+          } else if (key == empty_key) {
+            // Inserting new entry.  Grow table if necessary.
+            ++count;
+            if (count > table.size() * 3 / 4) grow();
+
+            // Try using an earlier-encountered deleted spot, if any.
+            if (first_deleted != unset) pos = first_deleted;
+
+            table[pos].first = k;
+            break;
+          } else if (key == k) {
+            break;
+          }
+        }
+        assert(i < table.size());
+        assert(table[pos].first == k);
+        return table[pos].second;
+#endif
+      }
+  };
+
+}
+
+#endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.