commit f96f199161e50e2d92032721389435bd0975b70d
parent fb53dd7a34e2025a015949c9c8ffa76a8ab93a95
Author: Andreas Pehrson <apehrson@mozilla.com>
Date: Thu, 23 Oct 2025 14:11:20 +0000
Bug 1771789 - In nsTArray, allow Comparators to compare elements to a type defined by the caller. r=xpcom-reviewers,nika
This allows more flexibility with methods explicitly taking an arbitrary item, e.g.:
```c++
struct State {
int mId;
bool mSuccess;
};
nsTArray<State> states;
int id{};
(...)
size_t idx = states.IndexOf(
/*aItem=*/id, /*aStart=*/0,
[](const State& aState, const int& aItem) { return aState.mId - aItem; });
```
Differential Revision: https://phabricator.services.mozilla.com/D266403
Diffstat:
2 files changed, 36 insertions(+), 21 deletions(-)
diff --git a/xpcom/ds/nsTArray.h b/xpcom/ds/nsTArray.h
@@ -768,17 +768,17 @@ namespace detail {
// called as a function with two instances of our element type, returns an int,
// we treat it as a tri-state comparator.
//
-// T is the type of the comparator object we want to check. U is the array
-// element type that we'll be comparing.
+// T is the type of the comparator object we want to check. L and R are the
+// types that we'll be comparing.
//
// V is never passed, and is only used to allow us to specialize on the return
// value of the comparator function.
-template <typename T, typename U, typename V = int>
+template <typename T, typename L, typename R, typename V = int>
struct IsCompareMethod : std::false_type {};
-template <typename T, typename U>
+template <typename T, typename L, typename R>
struct IsCompareMethod<
- T, U, decltype(std::declval<T>()(std::declval<U>(), std::declval<U>()))>
+ T, L, R, decltype(std::declval<T>()(std::declval<L>(), std::declval<R>()))>
: std::true_type {};
// These two wrappers allow us to use either a tri-state comparator, or an
@@ -793,7 +793,8 @@ struct IsCompareMethod<
// purpose.
// Comparator wrapper for a tri-state comparator function
-template <typename T, typename U, bool IsCompare = IsCompareMethod<T, U>::value>
+template <typename T, typename L, typename R,
+ bool IsCompare = IsCompareMethod<T, L, R>::value>
struct CompareWrapper {
#ifdef _MSC_VER
# pragma warning(push)
@@ -825,8 +826,8 @@ struct CompareWrapper {
};
// Comparator wrapper for a class with Equals() and LessThan() methods.
-template <typename T, typename U>
-struct CompareWrapper<T, U, false> {
+template <typename T, typename L, typename R>
+struct CompareWrapper<T, L, R, false> {
MOZ_IMPLICIT CompareWrapper(const T& aComparator)
: mComparator(aComparator) {}
@@ -1222,7 +1223,7 @@ class nsTArray_Impl
template <class Item, class Comparator>
[[nodiscard]] index_type IndexOf(const Item& aItem, index_type aStart,
const Comparator& aComp) const {
- ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+ ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);
const value_type* iter = Elements() + aStart;
const value_type* iend = Elements() + Length();
@@ -1256,7 +1257,7 @@ class nsTArray_Impl
template <class Item, class Comparator>
[[nodiscard]] index_type LastIndexOf(const Item& aItem, index_type aStart,
const Comparator& aComp) const {
- ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+ ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);
size_type endOffset = aStart >= Length() ? Length() : aStart + 1;
const value_type* iend = Elements() - 1;
@@ -1293,7 +1294,7 @@ class nsTArray_Impl
[[nodiscard]] index_type BinaryIndexOf(const Item& aItem,
const Comparator& aComp) const {
using mozilla::BinarySearchIf;
- ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+ ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);
size_t index;
bool found = BinarySearchIf(
@@ -1538,7 +1539,7 @@ class nsTArray_Impl
[[nodiscard]] index_type IndexOfFirstElementGt(
const Item& aItem, const Comparator& aComp) const {
using mozilla::BinarySearchIf;
- ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+ ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);
size_t index;
BinarySearchIf(
@@ -2015,7 +2016,7 @@ class nsTArray_Impl
typename mozilla::FunctionTypeTraits<FunctionElse>::ReturnType>,
"ApplyIf's `Function` and `FunctionElse` must return the same type.");
- ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+ ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);
const value_type* const elements = Elements();
const value_type* const iend = elements + Length();
@@ -2036,7 +2037,7 @@ class nsTArray_Impl
typename mozilla::FunctionTypeTraits<FunctionElse>::ReturnType>,
"ApplyIf's `Function` and `FunctionElse` must return the same type.");
- ::detail::CompareWrapper<Comparator, Item> comp(aComp);
+ ::detail::CompareWrapper<Comparator, value_type, Item> comp(aComp);
value_type* const elements = Elements();
value_type* const iend = elements + Length();
@@ -2246,7 +2247,7 @@ class nsTArray_Impl
static_assert(std::is_move_assignable_v<value_type>);
static_assert(std::is_move_constructible_v<value_type>);
- ::detail::CompareWrapper<Comparator, value_type> comp(aComp);
+ ::detail::CompareWrapper<Comparator, value_type, value_type> comp(aComp);
auto compFn = [&comp](const auto& left, const auto& right) {
return comp.LessThan(left, right);
};
@@ -2272,7 +2273,8 @@ class nsTArray_Impl
static_assert(std::is_move_assignable_v<value_type>);
static_assert(std::is_move_constructible_v<value_type>);
- const ::detail::CompareWrapper<Comparator, value_type> comp(aComp);
+ const ::detail::CompareWrapper<Comparator, value_type, value_type> comp(
+ aComp);
auto compFn = [&comp](const auto& lhs, const auto& rhs) {
return comp.LessThan(lhs, rhs);
};
diff --git a/xpcom/tests/gtest/TestTArray2.cpp b/xpcom/tests/gtest/TestTArray2.cpp
@@ -1448,8 +1448,9 @@ TEST(TArray, test_SetLengthAndRetainStorage_no_ctor)
#undef RPAREN
}
-template <typename Comparator>
-bool TestCompareMethods(const Comparator& aComp) {
+template <typename F, typename Comparator, typename ItemComparator>
+bool TestCompareMethodsImpl(F aItemCreator, const Comparator& aComp,
+ const ItemComparator& aItemComp) {
nsTArray<int> ary({57, 4, 16, 17, 3, 5, 96, 12});
ary.Sort(aComp);
@@ -1461,31 +1462,43 @@ bool TestCompareMethods(const Comparator& aComp) {
}
}
- if (!ary.ContainsSorted(5, aComp)) {
+ if (!ary.ContainsSorted(aItemCreator(5), aItemComp)) {
return false;
}
- if (ary.ContainsSorted(42, aComp)) {
+ if (ary.ContainsSorted(aItemCreator(42), aItemComp)) {
return false;
}
- if (ary.BinaryIndexOf(16, aComp) != 4) {
+ if (ary.BinaryIndexOf(aItemCreator(16), aItemComp) != 4) {
return false;
}
return true;
}
+template <typename Comparator>
+bool TestCompareMethods(const Comparator& aComp) {
+ return TestCompareMethodsImpl([](int aI) { return aI; }, aComp, aComp);
+}
+
struct IntComparator {
bool Equals(int aLeft, int aRight) const { return aLeft == aRight; }
bool LessThan(int aLeft, int aRight) const { return aLeft < aRight; }
};
+struct IntWrapper {
+ int mI;
+};
+
TEST(TArray, test_comparator_objects)
{
ASSERT_TRUE(TestCompareMethods(IntComparator()));
ASSERT_TRUE(
TestCompareMethods([](int aLeft, int aRight) { return aLeft - aRight; }));
+ ASSERT_TRUE(TestCompareMethodsImpl(
+ [](int aI) { return IntWrapper{.mI = aI}; }, IntComparator(),
+ [](int aElem, const IntWrapper& aItem) { return aElem - aItem.mI; }));
}
struct Big {
