Bug 1216001 part 1 - Optimize nsRange::IsNodeSelected. r=bz
authorMats Palmgren <mats@mozilla.com>
Sat, 13 Feb 2016 18:40:23 +0100
changeset 284192 2e047065c2912e930e294eaccef64e4012794e4c
parent 284191 61588bf601551fcb1d959b0b45be296f64cac4f2
child 284193 4bf7966153a0a116c49c30693c755609b8282973
push id29998
push userphilringnalda@gmail.com
push dateSun, 14 Feb 2016 03:19:08 +0000
treeherderautoland@e355cacefc88 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbz
bugs1216001
milestone47.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 1216001 part 1 - Optimize nsRange::IsNodeSelected. r=bz
dom/base/nsRange.cpp
dom/base/nsRange.h
mfbt/BinarySearch.h
--- a/dom/base/nsRange.cpp
+++ b/dom/base/nsRange.cpp
@@ -146,43 +146,92 @@ GetNextRangeCommonAncestor(nsINode* aNod
     if (!aNode->IsDescendantOfCommonAncestorForRangeInSelection()) {
       return nullptr;
     }
     aNode = aNode->GetParentNode();
   }
   return aNode;
 }
 
+/**
+ * A Comparator suitable for mozilla::BinarySearchIf for searching a collection
+ * of nsRange* for an overlap of (mNode, mStartOffset) .. (mNode, mEndOffset).
+ */
+struct IsItemInRangeComparator
+{
+  nsINode* mNode;
+  uint32_t mStartOffset;
+  uint32_t mEndOffset;
+
+  int operator()(const nsRange* const aRange) const
+  {
+    int32_t cmp = nsContentUtils::ComparePoints(mNode, mEndOffset,
+                                                aRange->GetStartParent(),
+                                                aRange->StartOffset());
+    if (cmp == 1) {
+      cmp = nsContentUtils::ComparePoints(mNode, mStartOffset,
+                                          aRange->GetEndParent(),
+                                          aRange->EndOffset());
+      if (cmp == -1) {
+        return 0;
+      }
+      return 1;
+    }
+    return -1;
+  }
+};
+
 /* static */ bool
 nsRange::IsNodeSelected(nsINode* aNode, uint32_t aStartOffset,
                         uint32_t aEndOffset)
 {
   NS_PRECONDITION(aNode, "bad arg");
 
   nsINode* n = GetNextRangeCommonAncestor(aNode);
   NS_ASSERTION(n || !aNode->IsSelectionDescendant(),
                "orphan selection descendant");
+
+  // Collect the potential ranges and their selection objects.
+  RangeHashTable ancestorSelectionRanges;
+  nsTHashtable<nsPtrHashKey<Selection>> ancestorSelections;
+  uint32_t maxRangeCount = 0;
   for (; n; n = GetNextRangeCommonAncestor(n->GetParentNode())) {
     RangeHashTable* ranges =
       static_cast<RangeHashTable*>(n->GetProperty(nsGkAtoms::range));
     for (auto iter = ranges->ConstIter(); !iter.Done(); iter.Next()) {
       nsRange* range = iter.Get()->GetKey();
       if (range->IsInSelection() && !range->Collapsed()) {
-        int32_t cmp = nsContentUtils::ComparePoints(aNode, aEndOffset,
-                                                    range->GetStartParent(),
-                                                    range->StartOffset());
-        if (cmp == 1) {
-          cmp = nsContentUtils::ComparePoints(aNode, aStartOffset,
-                                              range->GetEndParent(),
-                                              range->EndOffset());
-          if (cmp == -1) {
-            return true;
-          }
+        ancestorSelectionRanges.PutEntry(range);
+        Selection* selection = range->mSelection;
+        ancestorSelections.PutEntry(selection);
+        maxRangeCount = std::max(maxRangeCount, selection->RangeCount());
+      }
+    }
+  }
+
+  if (!ancestorSelectionRanges.IsEmpty()) {
+    nsTArray<const nsRange*> sortedRanges(maxRangeCount);
+    for (auto iter = ancestorSelections.ConstIter(); !iter.Done(); iter.Next()) {
+      Selection* selection = iter.Get()->GetKey();
+      // Sort the found ranges for |selection| in document order
+      // (Selection::GetRangeAt returns its ranges ordered).
+      for (uint32_t i = 0, len = selection->RangeCount(); i < len; ++i) {
+        nsRange* range = selection->GetRangeAt(i);
+        if (ancestorSelectionRanges.Contains(range)) {
+          sortedRanges.AppendElement(range);
         }
       }
+      MOZ_ASSERT(!sortedRanges.IsEmpty());
+      // Binary search the now sorted ranges.
+      IsItemInRangeComparator comparator = { aNode, aStartOffset, aEndOffset };
+      size_t unused;
+      if (mozilla::BinarySearchIf(sortedRanges, 0, sortedRanges.Length(), comparator, &unused)) {
+        return true;
+      }
+      sortedRanges.ClearAndRetainStorage();
     }
   }
   return false;
 }
 
 /******************************************************
  * constructor/destructor
  ******************************************************/
--- a/dom/base/nsRange.h
+++ b/dom/base/nsRange.h
@@ -247,16 +247,24 @@ public:
  *
  *  XXX - callers responsibility to ensure node in same doc as range!
  *
  *****************************************************************************/
   static nsresult CompareNodeToRange(nsINode* aNode, nsRange* aRange,
                                      bool *outNodeBefore,
                                      bool *outNodeAfter);
 
+  /**
+   * Return true if any part of (aNode, aStartOffset) .. (aNode, aEndOffset)
+   * overlaps any nsRange in aNode's GetNextRangeCommonAncestor ranges (i.e.
+   * where aNode is a descendant of a range's common ancestor node).
+   * If a nsRange starts in (aNode, aEndOffset) or if it ends in
+   * (aNode, aStartOffset) then it is non-overlapping and the result is false
+   * for that nsRange.  Collapsed ranges always counts as non-overlapping.
+   */
   static bool IsNodeSelected(nsINode* aNode, uint32_t aStartOffset,
                              uint32_t aEndOffset);
 
   static void CollectClientRects(nsLayoutUtils::RectCallback* aCollector,
                                  nsRange* aRange,
                                  nsINode* aStartParent, int32_t aStartOffset,
                                  nsINode* aEndParent, int32_t aEndOffset,
                                  bool aClampToEdge, bool aFlushLayout);
@@ -293,16 +301,24 @@ protected:
    * ancestor for the range.  This method uses the selection bits and
    * nsGkAtoms::range property on the nodes to quickly find the ancestor.
    * That is, it's a faster version of GetCommonAncestor that only works
    * for ranges in a Selection.  The method will assert and the behavior
    * is undefined if called on a range where IsInSelection() is false.
    */
   nsINode* GetRegisteredCommonAncestor();
 
+  // Helper to IsNodeSelected.
+  static bool IsNodeInSortedRanges(nsINode* aNode,
+                                   uint32_t aStartOffset,
+                                   uint32_t aEndOffset,
+                                   const nsTArray<const nsRange*>& aRanges,
+                                   size_t aRangeStart,
+                                   size_t aRangeEnd);
+
   struct MOZ_STACK_CLASS AutoInvalidateSelection
   {
     explicit AutoInvalidateSelection(nsRange* aRange) : mRange(aRange)
     {
 #ifdef DEBUG
       mWasInSelection = mRange->IsInSelection();
 #endif
       if (!mRange->IsInSelection() || mIsNested) {
--- a/mfbt/BinarySearch.h
+++ b/mfbt/BinarySearch.h
@@ -42,17 +42,17 @@ namespace mozilla {
  *
  * the value.
  *
  * Example:
  *
  *   struct Comparator {
  *     int operator()(int val) const {
  *       if (mTarget < val) return -1;
- *       if (mValue > val) return 1;
+ *       if (mTarget > val) return 1;
  *       return 0;
  *     }
  *     Comparator(int target) : mTarget(target) {}
        const int mTarget;
  *   };
  *
  *   Vector<int> sortedInts = ...
  *