SERVER-17496 Move range_arithmetic out of mongos

6 files changed, 461 insertions, 4 deletions

diff --git a/src/mongo/db/commands/cleanup_orphaned_cmd.cpp b/src/mongo/db/commands/cleanup_orphaned_cmd.cpp
index 6245481f292..b3d4bf31c80 100644
--- a/src/mongo/db/commands/cleanup_orphaned_cmd.cpp
+++ b/src/mongo/db/commands/cleanup_orphaned_cmd.cpp
@@ -42,11 +42,11 @@
 #include "mongo/db/field_parser.h"
 #include "mongo/db/jsobj.h"
 #include "mongo/db/namespace_string.h"
+#include "mongo/db/range_arithmetic.h"
 #include "mongo/db/range_deleter_service.h"
 #include "mongo/db/repl/replication_coordinator_global.h"
 #include "mongo/s/collection_metadata.h"
 #include "mongo/s/d_state.h"
-#include "mongo/s/range_arithmetic.h"
 #include "mongo/s/type_settings.h"
 #include "mongo/util/log.h"
 
diff --git a/src/mongo/db/dbhelpers.cpp b/src/mongo/db/dbhelpers.cpp
index 4a271717406..da3adfbc961 100644
--- a/src/mongo/db/dbhelpers.cpp
+++ b/src/mongo/db/dbhelpers.cpp
@@ -34,7 +34,6 @@
 
 #include "mongo/db/dbhelpers.h"
 
-#include <boost/filesystem/convenience.hpp>
 #include <boost/filesystem/operations.hpp>
 #include <fstream>
 
@@ -53,6 +52,7 @@
 #include "mongo/db/query/get_executor.h"
 #include "mongo/db/query/internal_plans.h"
 #include "mongo/db/query/query_planner.h"
+#include "mongo/db/range_arithmetic.h"
 #include "mongo/db/repl/oplog.h"
 #include "mongo/db/repl/replication_coordinator_global.h"
 #include "mongo/db/write_concern.h"
diff --git a/src/mongo/db/dbhelpers.h b/src/mongo/db/dbhelpers.h
index 9901ea470f4..a40114ef8ab 100644
--- a/src/mongo/db/dbhelpers.h
+++ b/src/mongo/db/dbhelpers.h
@@ -29,13 +29,11 @@
 #pragma once
 
 #include <boost/filesystem/path.hpp>
-#include <boost/noncopyable.hpp>
 
 #include "mongo/db/client.h"
 #include "mongo/db/db.h"
 #include "mongo/db/record_id.h"
 #include "mongo/db/keypattern.h"
-#include "mongo/s/range_arithmetic.h"
 
 namespace mongo {
 
@@ -44,6 +42,7 @@ namespace mongo {
     class Collection;
     class Cursor;
     class OperationContext;
+    struct KeyRange;
     struct WriteConcernOptions;
 
     /**
diff --git a/src/mongo/db/range_arithmetic.cpp b/src/mongo/db/range_arithmetic.cpp
new file mode 100644
index 00000000000..fae99baf1f0
--- /dev/null
+++ b/src/mongo/db/range_arithmetic.cpp
@@ -0,0 +1,140 @@
+/**
+ *    Copyright (C) 2013 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/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects
+ *    for all of the code used other than as permitted herein. If you modify
+ *    file(s) with this exception, you may extend this exception to your
+ *    version of the file(s), but you are not obligated to do so. If you do not
+ *    wish to do so, delete this exception statement from your version. If you
+ *    delete this exception statement from all source files in the program,
+ *    then also delete it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include "mongo/db/range_arithmetic.h"
+
+namespace mongo {
+
+    using std::make_pair;
+    using std::pair;
+    using std::string;
+    using std::stringstream;
+
+    bool rangeContains( const BSONObj& inclusiveLower,
+                        const BSONObj& exclusiveUpper,
+                        const BSONObj& point )
+    {
+        return point.woCompare( inclusiveLower ) >= 0 && point.woCompare( exclusiveUpper ) < 0;
+    }
+
+    bool rangeOverlaps( const BSONObj& inclusiveLower1,
+                        const BSONObj& exclusiveUpper1,
+                        const BSONObj& inclusiveLower2,
+                        const BSONObj& exclusiveUpper2 )
+    {
+        return ( exclusiveUpper1.woCompare( inclusiveLower2 ) > 0 )
+            && ( exclusiveUpper2.woCompare( inclusiveLower1 ) > 0 );
+    }
+
+    int compareRanges( const BSONObj& rangeMin1,
+                       const BSONObj& rangeMax1,
+                       const BSONObj& rangeMin2,
+                       const BSONObj& rangeMax2 )
+    {
+        const int minCmp = rangeMin1.woCompare( rangeMin2 );
+        if ( minCmp != 0 ) return minCmp;
+        return rangeMax1.woCompare( rangeMax2 );
+    }
+
+    // Represents the start and end of an overlap of a tested range
+    typedef pair<RangeMap::const_iterator, RangeMap::const_iterator> OverlapBounds;
+
+    // Internal-only, shared functionality
+    OverlapBounds rangeMapOverlapBounds( const RangeMap& ranges,
+                                         const BSONObj& inclusiveLower,
+                                         const BSONObj& exclusiveUpper ) {
+
+        // Returns the first chunk with a min key that is >= lower bound - the previous chunk
+        // might overlap.
+        RangeMap::const_iterator low = ranges.lower_bound( inclusiveLower );
+
+        // See if the previous chunk overlaps our range, not clear from just min key
+        if ( low != ranges.begin() ) {
+
+            RangeMap::const_iterator next = low;
+            --low;
+
+            // If the previous range's max value is lte our min value
+            if ( low->second.woCompare( inclusiveLower ) < 1 ) {
+                low = next;
+            }
+        }
+
+        // Returns the first chunk with a max key that is >= upper bound - implies the
+        // chunk does not overlap upper bound
+        RangeMap::const_iterator high = ranges.lower_bound( exclusiveUpper );
+
+        return OverlapBounds( low, high );
+    }
+
+    void getRangeMapOverlap( const RangeMap& ranges,
+                             const BSONObj& inclusiveLower,
+                             const BSONObj& exclusiveUpper,
+                             RangeVector* overlap ) {
+        overlap->clear();
+        OverlapBounds bounds = rangeMapOverlapBounds( ranges, inclusiveLower, exclusiveUpper );
+        for ( RangeMap::const_iterator it = bounds.first; it != bounds.second; ++it ) {
+            overlap->push_back( make_pair( it->first, it->second ) );
+        }
+    }
+
+    bool rangeMapOverlaps( const RangeMap& ranges,
+                           const BSONObj& inclusiveLower,
+                           const BSONObj& exclusiveUpper ) {
+        OverlapBounds bounds = rangeMapOverlapBounds( ranges, inclusiveLower, exclusiveUpper );
+        return bounds.first != bounds.second;
+    }
+
+    bool rangeMapContains( const RangeMap& ranges,
+                           const BSONObj& inclusiveLower,
+                           const BSONObj& exclusiveUpper ) {
+        OverlapBounds bounds = rangeMapOverlapBounds( ranges, inclusiveLower, exclusiveUpper );
+        if ( bounds.first == ranges.end() ) return false;
+
+        return bounds.first->first.woCompare( inclusiveLower ) == 0
+            && bounds.first->second.woCompare( exclusiveUpper ) == 0;
+    }
+
+    string rangeToString( const BSONObj& inclusiveLower, const BSONObj& exclusiveUpper ) {
+        stringstream ss;
+        ss << "[" << inclusiveLower.toString() << ", " << exclusiveUpper.toString() << ")";
+        return ss.str();
+    }
+
+    string overlapToString( RangeVector overlap ) {
+        stringstream ss;
+        for ( RangeVector::const_iterator it = overlap.begin(); it != overlap.end(); ++it ) {
+            if ( it != overlap.begin() ) ss << ", ";
+            ss << rangeToString( it->first, it->second );
+        }
+        return ss.str();
+    }
+
+}
diff --git a/src/mongo/db/range_arithmetic.h b/src/mongo/db/range_arithmetic.h
new file mode 100644
index 00000000000..d13683be70b
--- /dev/null
+++ b/src/mongo/db/range_arithmetic.h
@@ -0,0 +1,157 @@
+/**
+ *    Copyright (C) 2013 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/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects
+ *    for all of the code used other than as permitted herein. If you modify
+ *    file(s) with this exception, you may extend this exception to your
+ *    version of the file(s), but you are not obligated to do so. If you do not
+ *    wish to do so, delete this exception statement from your version. If you
+ *    delete this exception statement from all source files in the program,
+ *    then also delete it in the license file.
+ */
+
+#pragma once
+
+#include <string>
+#include <map>
+#include <vector>
+
+#include "mongo/db/jsobj.h"
+
+namespace mongo {
+
+    /**
+     * A KeyRange represents a range over keys of documents in a namespace, qualified by a
+     * key pattern which defines the documents that are in the key range.
+     *
+     * There may be many different expressions to generate the same key fields from a document - the
+     * keyPattern tells us these expressions.
+     *
+     * Ex:
+     * DocA : { field : "aaaa" }
+     * DocB : { field : "bbb" }
+     * DocC : { field : "ccccc" }
+     *
+     * keyPattern : { field : 1 }
+     * minKey : { field : "aaaa" } : Id(DocA)
+     * maxKey : { field : "ccccc" } : Id(DocB)
+     *
+     * contains Id(DocB)
+     *
+     * keyPattern : { field : "numberofletters" }
+     * minKey : { field : 4 } : numberofletters(DocA)
+     * maxKey : { field : 5 } : numberofletters(DocC)
+     *
+     * does not contain numberofletters(DocB)
+     */
+    struct KeyRange {
+
+        KeyRange( const std::string& ns,
+                  const BSONObj& minKey,
+                  const BSONObj& maxKey,
+                  const BSONObj& keyPattern ) :
+                ns( ns ), minKey( minKey ), maxKey( maxKey ), keyPattern( keyPattern )
+        {
+        }
+
+        KeyRange() {}
+
+        std::string ns;
+        BSONObj minKey;
+        BSONObj maxKey;
+        BSONObj keyPattern;
+    };
+
+    /**
+     * Returns true if the point is within the range [inclusiveLower, exclusiveUpper).
+     */
+    bool rangeContains( const BSONObj& inclusiveLower,
+                        const BSONObj& exclusiveUpper,
+                        const BSONObj& point );
+
+    /**
+     * Returns true if the bounds specified by [inclusiveLower1, exclusiveUpper1)
+     * intersects with the bounds [inclusiveLower2, exclusiveUpper2).
+     */
+    bool rangeOverlaps( const BSONObj& inclusiveLower1,
+                        const BSONObj& exclusiveUpper1,
+                        const BSONObj& inclusiveLower2,
+                        const BSONObj& exclusiveUpper2 );
+
+    /**
+     * Returns -1 if first range is less than the second range, 0 if equal and 1 if
+     * greater. The ordering is based on comparing both the min first and then uses
+     * the max as the tie breaker.
+     */
+    int compareRanges( const BSONObj& rangeMin1,
+                       const BSONObj& rangeMax1,
+                       const BSONObj& rangeMin2,
+                       const BSONObj& rangeMax2 );
+
+    /**
+     * A RangeMap is a mapping of a BSON range from lower->upper (lower maps to upper), using
+     * standard BSON woCompare.  Upper bound is exclusive.
+     *
+     * NOTE: For overlap testing to work correctly, there may be no overlaps present in the map
+     * itself.
+     */
+    typedef std::map<BSONObj, BSONObj, BSONObjCmp> RangeMap;
+
+    /**
+     * A RangeVector is a list of [lower,upper) ranges.
+     */
+    typedef std::vector<std::pair<BSONObj,BSONObj> > RangeVector;
+
+    /**
+     * Returns the overlap of a range [inclusiveLower, exclusiveUpper) with the provided range map
+     * as a vector of ranges from the map.
+     */
+    void getRangeMapOverlap( const RangeMap& ranges,
+                             const BSONObj& inclusiveLower,
+                             const BSONObj& exclusiveUpper,
+                             RangeVector* vector );
+
+    /**
+     * Returns true if the provided range map has ranges which overlap the provided range
+     * [inclusiveLower, exclusiveUpper).
+     */
+    bool rangeMapOverlaps( const RangeMap& ranges,
+                           const BSONObj& inclusiveLower,
+                           const BSONObj& exclusiveUpper );
+
+    /**
+     * Returns true if the provided range map exactly contains the provided range
+     * [inclusiveLower, exclusiveUpper).
+     */
+    bool rangeMapContains( const RangeMap& ranges,
+                           const BSONObj& inclusiveLower,
+                           const BSONObj& exclusiveUpper );
+
+    /**
+     * std::string representation of [inclusiveLower, exclusiveUpper)
+     */
+    std::string rangeToString( const BSONObj& inclusiveLower,
+                               const BSONObj& exclusiveUpper );
+
+    /**
+     * std::string representation of overlapping ranges as a list "[range1),[range2),..."
+     */
+    std::string overlapToString( RangeVector overlap );
+
+}
diff --git a/src/mongo/db/range_arithmetic_test.cpp b/src/mongo/db/range_arithmetic_test.cpp
new file mode 100644
index 00000000000..79632689bb7
--- /dev/null
+++ b/src/mongo/db/range_arithmetic_test.cpp
@@ -0,0 +1,161 @@
+/**
+ *    Copyright (C) 2013 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/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects
+ *    for all of the code used other than as permitted herein. If you modify
+ *    file(s) with this exception, you may extend this exception to your
+ *    version of the file(s), but you are not obligated to do so. If you do not
+ *    wish to do so, delete this exception statement from your version. If you
+ *    delete this exception statement from all source files in the program,
+ *    then also delete it in the license file.
+ */
+
+#include "mongo/db/range_arithmetic.h"
+#include "mongo/unittest/unittest.h"
+
+namespace {
+
+    using mongo::MINKEY;
+    using mongo::MAXKEY;
+    using mongo::rangeOverlaps;
+    using mongo::rangeMapOverlaps;
+    using mongo::RangeMap;
+    using mongo::RangeVector;
+    using std::make_pair;
+
+    TEST(BSONRange, SmallerLowerRangeNonSubset) {
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 50), BSON("x" << 200)));
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 60), BSON("x" << 199)));
+
+        ASSERT_FALSE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                   BSON("x" << 70), BSON("x" << 99)));
+        ASSERT_FALSE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                   BSON("x" << 80), BSON("x" << 100)));
+    }
+
+    TEST(BSONRange, BiggerUpperRangeNonSubset) {
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 150), BSON("x" << 200)));
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 160), BSON("x" << 201)));
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 170), BSON("x" << 220)));
+
+        ASSERT_FALSE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                   BSON("x" << 200), BSON("x" << 240)));
+    }
+
+    TEST(BSONRange, RangeIsSubsetOfOther) {
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 70), BSON("x" << 300)));
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 140), BSON("x" << 180)));
+    }
+
+    TEST(BSONRange, EqualRange) {
+        ASSERT_TRUE(rangeOverlaps(BSON("x" << 100), BSON("x" << 200),
+                                  BSON("x" << 100), BSON("x" << 200)));
+    }
+
+    TEST(RangeMap, RangeMapOverlap) {
+
+        RangeMap rangeMap;
+        rangeMap.insert( make_pair( BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+        rangeMap.insert( make_pair( BSON( "x" << 200 ), BSON( "x" << 300 ) ) );
+        rangeMap.insert( make_pair( BSON( "x" << 300 ), BSON( "x" << 400 ) ) );
+
+        RangeVector overlap;
+        getRangeMapOverlap( rangeMap, BSON( "x" << 50 ), BSON( "x" << 350 ), &overlap );
+
+        ASSERT( !overlap.empty() );
+        ASSERT_EQUALS( overlap.size(), 3u );
+    }
+
+    TEST(RangeMap, RangeMapOverlapPartial) {
+
+        RangeMap rangeMap;
+        rangeMap.insert( make_pair( BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+        rangeMap.insert( make_pair( BSON( "x" << 200 ), BSON( "x" << 300 ) ) );
+
+        RangeVector overlap;
+        getRangeMapOverlap( rangeMap, BSON( "x" << 150 ), BSON( "x" << 250 ), &overlap );
+
+        ASSERT( !overlap.empty() );
+        ASSERT_EQUALS( overlap.size(), 2u );
+    }
+
+    TEST(RangeMap, RangeMapOverlapInner) {
+
+        RangeMap rangeMap;
+        rangeMap.insert( make_pair( BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+
+        RangeVector overlap;
+        getRangeMapOverlap( rangeMap, BSON( "x" << 125 ), BSON( "x" << 150 ), &overlap );
+
+        ASSERT( !overlap.empty() );
+        ASSERT_EQUALS( overlap.size(), 1u );
+    }
+
+    TEST(RangeMap, RangeMapNoOverlap) {
+
+        RangeMap rangeMap;
+        rangeMap.insert( make_pair( BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+        rangeMap.insert( make_pair( BSON( "x" << 300 ), BSON( "x" << 400 ) ) );
+
+        RangeVector overlap;
+        getRangeMapOverlap( rangeMap, BSON( "x" << 200 ), BSON( "x" << 300 ), &overlap );
+
+        ASSERT( overlap.empty() );
+    }
+
+    TEST(RangeMap, RangeMapOverlaps) {
+
+        RangeMap rangeMap;
+        rangeMap.insert( make_pair( BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+
+        ASSERT( rangeMapOverlaps( rangeMap, BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+        ASSERT( rangeMapOverlaps( rangeMap, BSON( "x" << 99 ), BSON( "x" << 200 ) ) );
+        ASSERT( rangeMapOverlaps( rangeMap, BSON( "x" << 100 ), BSON( "x" << 201 ) ) );
+        ASSERT( rangeMapOverlaps( rangeMap, BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+        ASSERT( !rangeMapOverlaps( rangeMap, BSON( "x" << 99 ), BSON( "x" << 100 ) ) );
+        ASSERT( !rangeMapOverlaps( rangeMap, BSON( "x" << 200 ), BSON( "x" << 201 ) ) );
+    }
+
+    TEST(RangeMap, RangeMapContains) {
+
+        RangeMap rangeMap;
+        rangeMap.insert( make_pair( BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+
+        ASSERT( rangeMapContains( rangeMap, BSON( "x" << 100 ), BSON( "x" << 200 ) ) );
+        ASSERT( !rangeMapContains( rangeMap, BSON( "x" << 99 ), BSON( "x" << 200 ) ) );
+        ASSERT( !rangeMapContains( rangeMap, BSON( "x" << 100 ), BSON( "x" << 201 ) ) );
+    }
+
+    TEST(RangeMap, RangeMapContainsMinMax) {
+
+        RangeMap rangeMap;
+        rangeMap.insert( make_pair( BSON( "x" << MINKEY ), BSON( "x" << MAXKEY ) ) );
+
+        ASSERT( rangeMapContains( rangeMap, BSON( "x" << MINKEY ), BSON( "x" << MAXKEY ) ) );
+        ASSERT( !rangeMapContains( rangeMap, BSON( "x" << 1 ), BSON( "x" << MAXKEY ) ) );
+        ASSERT( !rangeMapContains( rangeMap, BSON( "x" << MINKEY ), BSON( "x" << 1 ) ) );
+    }
+}