SERVER-1752 Dedup DiskLocs in IntervalBtreeCursor using an unordered_set.

4 files changed, 71 insertions, 3 deletions

diff --git a/src/mongo/db/diskloc.h b/src/mongo/db/diskloc.h
index a6adb204a58..70acc975d95 100644
--- a/src/mongo/db/diskloc.h
+++ b/src/mongo/db/diskloc.h
@@ -24,6 +24,7 @@
 
 #include "mongo/db/jsobj.h"
 #include "mongo/platform/cstdint.h"
+#include "mongo/platform/unordered_set.h"
 
 namespace mongo {
 
@@ -131,7 +132,13 @@ namespace mongo {
             return compare(b) < 0;
         }
 
-        uint64_t asUint64() const { return *reinterpret_cast<const uint64_t*>( this ); }
+        /**
+         * Hash value for this disk location.  The hash implementation may be modified, and its
+         * behavior may differ across platforms.  Hash values should not be persisted.
+         */
+        struct Hasher {
+            size_t operator()( DiskLoc loc ) const;
+        };
 
         /**
          * Marks this disk loc for writing
@@ -161,6 +168,14 @@ namespace mongo {
     };
 #pragma pack()
 
+    inline size_t DiskLoc::Hasher::operator()( DiskLoc loc ) const {
+        // Older tr1 implementations do not support hashing 64 bit integers.  This implementation
+        // delegates to hashing 32 bit integers.
+        return
+            unordered_set<uint32_t>::hasher()( loc.a() ) ^
+            unordered_set<uint32_t>::hasher()( loc.getOfs() );
+    }
+
     inline std::ostream& operator<<( std::ostream &stream, const DiskLoc &loc ) {
         return stream << loc.toString();
     }
diff --git a/src/mongo/db/diskloc_test.cpp b/src/mongo/db/diskloc_test.cpp
new file mode 100644
index 00000000000..db3e0c8a65b
--- /dev/null
+++ b/src/mongo/db/diskloc_test.cpp
@@ -0,0 +1,53 @@
+/**
+ *    Copyright (C) 2012 10gen Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/** Unit tests for DiskLoc. */
+
+#include "mongo/db/diskloc.h"
+
+#include "mongo/unittest/unittest.h"
+
+namespace mongo {
+namespace {
+
+    TEST( DiskLoc, HashEqual ) {
+        DiskLoc locA( 1, 2 );
+        DiskLoc locB;
+        locB.set( 1, 2 );
+        ASSERT_EQUALS( locA, locB );
+        DiskLoc::Hasher hasher;
+        ASSERT_EQUALS( hasher( locA ), hasher( locB ) );
+    }
+
+    TEST( DiskLoc, HashNotEqual ) {
+        DiskLoc original( 1, 2 );
+        DiskLoc diffFile( 10, 2 );
+        DiskLoc diffOfs( 1, 20 );
+        DiskLoc diffBoth( 10, 20 );
+        ASSERT_NOT_EQUALS( original, diffFile );
+        ASSERT_NOT_EQUALS( original, diffOfs );
+        ASSERT_NOT_EQUALS( original, diffBoth );
+        
+        // Unequal DiskLocs need not produce unequal hashes.  But unequal hashes are likely, and
+        // assumed here for sanity checking of the custom hash implementation.
+        DiskLoc::Hasher hasher;
+        ASSERT_NOT_EQUALS( hasher( original ), hasher( diffFile ) );
+        ASSERT_NOT_EQUALS( hasher( original ), hasher( diffOfs ) );
+        ASSERT_NOT_EQUALS( hasher( original ), hasher( diffBoth ) );
+    }
+    
+} // namespace
+} // namespace mongo
diff --git a/src/mongo/db/intervalbtreecursor.cpp b/src/mongo/db/intervalbtreecursor.cpp
index b995e1ad3a3..58190a08280 100644
--- a/src/mongo/db/intervalbtreecursor.cpp
+++ b/src/mongo/db/intervalbtreecursor.cpp
@@ -150,7 +150,7 @@ namespace mongo {
         // TODO _multikeyFlag may be set part way through an iteration by checkLocation().  In this
         // case results returned earlier, when _multikeyFlag was false, will not be deduped.  This
         // is an old issue with all mongo btree cursor implementations.
-        return _multikeyFlag && !_dups.insert( loc.asUint64() ).second;
+        return _multikeyFlag && !_dups.insert( loc ).second;
     }
 
     BSONObj IntervalBtreeCursor::prettyIndexBounds() const {
diff --git a/src/mongo/db/intervalbtreecursor.h b/src/mongo/db/intervalbtreecursor.h
index 49328f40945..01c1d26e919 100644
--- a/src/mongo/db/intervalbtreecursor.h
+++ b/src/mongo/db/intervalbtreecursor.h
@@ -139,7 +139,7 @@ namespace mongo {
 
         shared_ptr<CoveredIndexMatcher> _matcher;
         bool _multikeyFlag;
-        set<uint64_t> _dups;
+        unordered_set<DiskLoc,DiskLoc::Hasher> _dups;
     };
 
 } // namespace mongo