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

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

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

Log Message:
-----------
added some documentation; cleaned up/removed commented code (moved to the "journey" in the sandbox)

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

Modified: cpp-commons/trunk/src/commons/fast_map.h
===================================================================
--- cpp-commons/trunk/src/commons/fast_map.h	2009-03-06 07:24:20 UTC (rev 1260)
+++ cpp-commons/trunk/src/commons/fast_map.h	2009-03-06 07:27:49 UTC (rev 1261)
@@ -11,11 +11,20 @@
   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.
+   * google::dense_hash_map.  Took the overall design from
+   * google::dense_hash_map, and also a few speed-up techniques from peeking at
+   * their source.
+   *
+   * This was originally written for ydb, where the map was the bottleneck in
+   * the application, but more importantly, the interface required the ability
+   * to serialize the map, and partially.  The internals have to be exposed in
+   * order for fast serialization (i.e. memcpy) to be possible; also, the
+   * ability to serialize just a certain range of the fast_map is also
+   * important.
    */
+  // TODO someday: template <typename K, typename V>
   class fast_map
   {
     private:
@@ -35,8 +44,6 @@
         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;
@@ -95,31 +102,6 @@
           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
       }
   };
 


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