bug 606080 - add SplayTree::LookupOrAdd r=froydnj
authorTrevor Saunders <tbsaunde@tbsaunde.org>
Tue, 28 Apr 2015 15:55:29 -0400
changeset 272456 ed3aed8b899ffe9559226d33836886dbb7669068
parent 272455 1c6a191fead0dcecf7b80c4f339169dd0d4df02f
child 272457 28c2b07d197c96b89e2b29ca53d4d8c62b3dc32c
push id4830
push userjlund@mozilla.com
push dateMon, 29 Jun 2015 20:18:48 +0000
treeherdermozilla-beta@4c2175bb0420 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs606080
milestone40.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
bug 606080 - add SplayTree::LookupOrAdd r=froydnj
mfbt/SplayTree.h
mfbt/tests/TestSplayTree.cpp
--- a/mfbt/SplayTree.h
+++ b/mfbt/SplayTree.h
@@ -8,16 +8,17 @@
  * A sorted tree with optimal access times, where recently-accessed elements
  * are faster to access again.
  */
 
 #ifndef mozilla_SplayTree_h
 #define mozilla_SplayTree_h
 
 #include "mozilla/Assertions.h"
+#include "mozilla/Attributes.h"
 
 namespace mozilla {
 
 template<class T, class C>
 class SplayTree;
 
 template<typename T>
 class SplayTreeNode
@@ -50,17 +51,17 @@ private:
  * method must be free from side effects.
  */
 template<typename T, class Comparator>
 class SplayTree
 {
   T* mRoot;
 
 public:
-  SplayTree()
+  MOZ_CONSTEXPR SplayTree()
     : mRoot(nullptr)
   {}
 
   bool empty() const
   {
     return !mRoot;
   }
 
@@ -81,25 +82,22 @@ public:
 
     if (!mRoot) {
       mRoot = aValue;
       return true;
     }
     T* last = lookup(*aValue);
     int cmp = Comparator::compare(*aValue, *last);
 
-    T** parentPointer = (cmp < 0) ? &last->mLeft : &last->mRight;
-    MOZ_ASSERT(!*parentPointer);
-    *parentPointer = aValue;
-    aValue->mParent = last;
-
-    splay(aValue);
+    finishInsertion(last, cmp, aValue);
     return true;
   }
 
+  T* findOrInsert(const T& aValue);
+
   T* remove(const T& aValue)
   {
     T* last = lookup(aValue);
     MOZ_ASSERT(last, "This tree must contain the element being removed.");
     MOZ_ASSERT(Comparator::compare(aValue, *last) == 0);
 
     // Splay the tree so that the item to remove is the root.
     splay(last);
@@ -191,16 +189,29 @@ private:
         node = node->mLeft;
       } else {
         node = node->mRight;
       }
     } while (node);
     return parent;
   }
 
+  T* finishInsertion(T* aLast, int32_t aCmp, T* aNew)
+  {
+    MOZ_ASSERT(aCmp, "Nodes shouldn't be equal!");
+
+    T** parentPointer = (aCmp < 0) ? &aLast->mLeft : &aLast->mRight;
+    MOZ_ASSERT(!*parentPointer);
+    *parentPointer = aNew;
+    aNew->mParent = aLast;
+
+    splay(aNew);
+    return aNew;
+  }
+
   /**
    * Rotate the tree until |node| is at the root of the tree. Performing
    * the rotations in this fashion preserves the amortized balancing of
    * the tree.
    */
   void splay(T* aNode)
   {
     MOZ_ASSERT(aNode);
@@ -290,11 +301,29 @@ private:
     }
     return aNode;
   }
 
   SplayTree(const SplayTree&) = delete;
   void operator=(const SplayTree&) = delete;
 };
 
+template<typename T, class Comparator>
+T*
+SplayTree<T, Comparator>::findOrInsert(const T& aValue)
+{
+  if (!mRoot) {
+    mRoot = new T(aValue);
+    return mRoot;
+  }
+
+  T* last = lookup(aValue);
+  int cmp = Comparator::compare(aValue, *last);
+  if (!cmp) {
+    return last;
+  }
+
+  return finishInsertion(last, cmp, new T(aValue));
+}
+
 }  /* namespace mozilla */
 
 #endif /* mozilla_SplayTree_h */
--- a/mfbt/tests/TestSplayTree.cpp
+++ b/mfbt/tests/TestSplayTree.cpp
@@ -100,37 +100,81 @@ struct SplayInt : SplayTreeNode<SplayInt
       return 1;
     }
     return 0;
   }
 
   int mValue;
 };
 
+struct SplayNoCopy : SplayTreeNode<SplayNoCopy>
+{
+  SplayNoCopy(const SplayNoCopy&) = delete;
+  SplayNoCopy(SplayNoCopy&&) = delete;
+
+  static int compare(const SplayNoCopy&, const SplayNoCopy&) {}
+};
+
+static SplayTree<SplayNoCopy, SplayNoCopy> testNoCopy;
+
 int
 main()
 {
   SplayTree<SplayInt, SplayInt> tree;
 
   MOZ_RELEASE_ASSERT(tree.empty());
 
   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0)));
 
   static const int N = mozilla::ArrayLength(gValues);
 
   // Insert the values, and check each one is findable just after insertion.
   for (int i = 0; i < N; i++) {
     tree.insert(new SplayInt(gValues[i]));
-    MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])));
+    SplayInt* inserted = tree.find(SplayInt(gValues[i]));
+    MOZ_RELEASE_ASSERT(inserted);
+    MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])) == inserted);
     tree.checkCoherency();
   }
 
   // Check they're all findable after all insertions.
   for (int i = 0; i < N; i++) {
     MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])));
+    MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])));
+    tree.checkCoherency();
+  }
+
+  // Check that non-inserted values cannot be found.
+  MOZ_RELEASE_ASSERT(!tree.find(SplayInt(-1)));
+  MOZ_RELEASE_ASSERT(!tree.find(SplayInt(N)));
+  MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0x7fffffff)));
+
+  // Remove the values, and check each one is not findable just after removal.
+  for (int i = 0; i < N; i++) {
+    SplayInt* removed = tree.remove(SplayInt(gValues[i]));
+    MOZ_RELEASE_ASSERT(removed->mValue == gValues[i]);
+    MOZ_RELEASE_ASSERT(!tree.find(*removed));
+    delete removed;
+    tree.checkCoherency();
+  }
+
+  MOZ_RELEASE_ASSERT(tree.empty());
+
+  // Insert the values, and check each one is findable just after insertion.
+  for (int i = 0; i < N; i++) {
+    SplayInt* inserted = tree.findOrInsert(SplayInt(gValues[i]));
+    MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])) == inserted);
+    MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])) == inserted);
+    tree.checkCoherency();
+  }
+
+  // Check they're all findable after all insertions.
+  for (int i = 0; i < N; i++) {
+    MOZ_RELEASE_ASSERT(tree.find(SplayInt(gValues[i])));
+    MOZ_RELEASE_ASSERT(tree.findOrInsert(SplayInt(gValues[i])));
     tree.checkCoherency();
   }
 
   // Check that non-inserted values cannot be found.
   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(-1)));
   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(N)));
   MOZ_RELEASE_ASSERT(!tree.find(SplayInt(0x7fffffff)));