SERVER-7174 Don't reorder elements to be added in addToSet

2 files changed, 35 insertions, 5 deletions

diff --git a/src/mongo/db/ops/modifier_add_to_set.cpp b/src/mongo/db/ops/modifier_add_to_set.cpp
index 37c1a60cde8..05e4e29fe04 100644
--- a/src/mongo/db/ops/modifier_add_to_set.cpp
+++ b/src/mongo/db/ops/modifier_add_to_set.cpp
@@ -25,6 +25,38 @@ namespace mongo {
 
     namespace mb = mutablebson;
 
+    namespace {
+
+        template<typename Ordering, typename Equality>
+        void deduplicate(mb::Element parent, Ordering comp, Equality equal) {
+
+            // First, build a vector of the children.
+            std::vector<mb::Element> children;
+            mb::Element current = parent.leftChild();
+            while (current.ok()) {
+                children.push_back(current);
+                current = current.rightSibling();
+            }
+
+            // Then, sort the child vector with our comparator.
+            std::sort(children.begin(), children.end(), comp);
+
+            // Next, remove duplicates by walking the vector.
+            std::vector<mb::Element>::iterator where = children.begin();
+            const std::vector<mb::Element>::iterator end = children.end();
+
+            while( where != end ) {
+                std::vector<mb::Element>::iterator next = where; ++next;
+                while (next != end && equal(*where, *next)) {
+                    next->remove();
+                    ++next;
+                }
+                where = next;
+            }
+        }
+
+    } // namespace
+
     struct ModifierAddToSet::PreparedState {
 
         PreparedState(mb::Document& doc)
@@ -102,9 +134,7 @@ namespace mongo {
 
                 _val = _valDoc.root().leftChild();
 
-                // Sort the values to be added, and remove duplicates.
-                mb::sortChildren(_val, mb::woLess(false));
-                mb::deduplicateChildren(_val, mb::woEqual(false));
+                deduplicate(_val, mb::woLess(false), mb::woEqual(false));
             }
         }
 
diff --git a/src/mongo/db/ops/modifier_add_to_set_test.cpp b/src/mongo/db/ops/modifier_add_to_set_test.cpp
index ce3d438cb7f..a7168eea53f 100644
--- a/src/mongo/db/ops/modifier_add_to_set_test.cpp
+++ b/src/mongo/db/ops/modifier_add_to_set_test.cpp
@@ -321,11 +321,11 @@ namespace {
         ASSERT_FALSE(execInfo.inPlace);
 
         ASSERT_OK(mod.apply());
-        ASSERT_TRUE(checkDoc(doc, fromjson("{ a : [ 1, 1, 2, 1, 2, 2, 3, 4] }")));
+        ASSERT_TRUE(checkDoc(doc, fromjson("{ a : [ 1, 1, 2, 1, 2, 2, 4, 3] }")));
 
         Document logDoc;
         ASSERT_OK(mod.log(logDoc.root()));
-        ASSERT_TRUE(checkDoc(logDoc, fromjson("{ $set : { a : [ 1, 1, 2, 1, 2, 2, 3, 4] } }")));
+        ASSERT_TRUE(checkDoc(logDoc, fromjson("{ $set : { a : [ 1, 1, 2, 1, 2, 2, 4, 3] } }")));
     }
 
 } // namespace