Bug 1287706 part 5 - Add RemoveElementsBy method to nsTArray and nsTObserverArray to allow filtering elements by predicate function. r=froydnj
authorXidorn Quan <me@upsuper.org>
Thu, 28 Jul 2016 12:00:06 +1000
changeset 332044 a53cb28a89a1649ff60a59b45c2029fc342e70f0
parent 332043 f26a98e3e7b082a0cbf9bc365f2c265fdbedf8d5
child 332045 2439dff9e9c4bf85c8a9e066597a2ae7a78fa795
push id9858
push userjlund@mozilla.com
push dateMon, 01 Aug 2016 14:37:10 +0000
treeherdermozilla-aurora@203106ef6cb6 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1287706
milestone50.0a1
Bug 1287706 part 5 - Add RemoveElementsBy method to nsTArray and nsTObserverArray to allow filtering elements by predicate function. r=froydnj MozReview-Commit-ID: LjUXYsIuaFL
xpcom/glue/nsTArray.h
xpcom/glue/nsTObserverArray.h
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -8,16 +8,17 @@
 #define nsTArray_h__
 
 #include "nsTArrayForwardDeclare.h"
 #include "mozilla/Alignment.h"
 #include "mozilla/Assertions.h"
 #include "mozilla/Attributes.h"
 #include "mozilla/BinarySearch.h"
 #include "mozilla/fallible.h"
+#include "mozilla/Function.h"
 #include "mozilla/InitializerList.h"
 #include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 #include "mozilla/ReverseIterator.h"
 #include "mozilla/TypeTraits.h"
 
 #include <string.h>
@@ -1584,16 +1585,23 @@ public:
   void RemoveElementsAt(index_type aStart, size_type aCount);
 
   // A variation on the RemoveElementsAt method defined above.
   void RemoveElementAt(index_type aIndex) { RemoveElementsAt(aIndex, 1); }
 
   // A variation on the RemoveElementsAt method defined above.
   void Clear() { RemoveElementsAt(0, Length()); }
 
+  // This method removes elements based on the return value of the
+  // callback function aPredicate. If the function returns true for
+  // an element, the element is removed. aPredicate will be called
+  // for each element in order. It is not safe to access the array
+  // inside aPredicate.
+  void RemoveElementsBy(mozilla::function<bool(const elem_type&)> aPredicate);
+
   // This helper function combines IndexOf with RemoveElementAt to "search
   // and destroy" the first element that is equal to the given element.
   // @param aItem The item to search for.
   // @param aComp The Comparator used to determine element equality.
   // @return true if the element was found
   template<class Item, class Comparator>
   bool RemoveElement(const Item& aItem, const Comparator& aComp)
   {
@@ -1889,16 +1897,40 @@ nsTArray_Impl<E, Alloc>::RemoveElementsA
   MOZ_ASSERT(aStart <= aStart + aCount, "Start index plus length overflows");
   DestructRange(aStart, aCount);
   this->template ShiftData<InfallibleAlloc>(aStart, aCount, 0,
                                             sizeof(elem_type),
                                             MOZ_ALIGNOF(elem_type));
 }
 
 template<typename E, class Alloc>
+void
+nsTArray_Impl<E, Alloc>::RemoveElementsBy(mozilla::function<bool(const elem_type&)> aPredicate)
+{
+  if (base_type::mHdr == EmptyHdr()) {
+    return;
+  }
+
+  index_type j = 0;
+  index_type len = Length();
+  for (index_type i = 0; i < len; ++i) {
+    if (aPredicate(Elements()[i])) {
+      elem_traits::Destruct(Elements() + i);
+    } else {
+      if (j < i) {
+        copy_type::MoveNonOverlappingRegion(Elements() + j, Elements() + i,
+                                            1, sizeof(elem_type));
+      }
+      ++j;
+    }
+  }
+  base_type::mHdr->mLength = j;
+}
+
+template<typename E, class Alloc>
 template<class Item, typename ActualAlloc>
 auto
 nsTArray_Impl<E, Alloc>::InsertElementsAt(index_type aIndex, size_type aCount,
                                           const Item& aItem) -> elem_type*
 {
   if (!base_type::template InsertSlotsAt<ActualAlloc>(aIndex, aCount,
                                                       sizeof(elem_type),
                                                       MOZ_ALIGNOF(elem_type))) {
--- a/xpcom/glue/nsTObserverArray.h
+++ b/xpcom/glue/nsTObserverArray.h
@@ -243,16 +243,31 @@ public:
       return false;
     }
 
     mArray.RemoveElementAt(index);
     AdjustIterators(index, -1);
     return true;
   }
 
+  // See nsTArray::RemoveElementsBy.
+  void RemoveElementsBy(mozilla::function<bool(const elem_type&)> aPredicate)
+  {
+    index_type i = 0;
+    mArray.RemoveElementsBy([&](const elem_type& aItem) {
+      if (aPredicate(aItem)) {
+        // This element is going to be removed.
+        AdjustIterators(i, -1);
+        return true;
+      }
+      ++i;
+      return false;
+    });
+  }
+
   // Removes all observers and collapses all iterators to the beginning of
   // the array. The result is that forward iterators will see all elements
   // in the array.
   void Clear()
   {
     mArray.Clear();
     ClearIterators();
   }