Bug 1449094 - Implement constexpr mozilla::AllOf. r=froydnj
☠☠ backed out by 2539ded2a075 ☠ ☠
authorMasatoshi Kimura <VYV03354@nifty.ne.jp>
Wed, 28 Mar 2018 00:01:08 +0900
changeset 775159 577c204175529bf4f23c7736bd67552b393dcc27
parent 775158 89678976aa895c43739b2abc9e3fff0940eb4cde
child 775160 2539ded2a075507d76408feb079ddbf5472195f3
push id104638
push userbmo:jlorenzo@mozilla.com
push dateFri, 30 Mar 2018 13:27:33 +0000
reviewersfroydnj
bugs1449094
milestone61.0a1
Bug 1449094 - Implement constexpr mozilla::AllOf. r=froydnj MozReview-Commit-ID: KvKY9CMqfww
mfbt/Algorithm.h
mfbt/moz.build
mfbt/tests/TestAlgorithm.cpp
mfbt/tests/moz.build
new file mode 100644
--- /dev/null
+++ b/mfbt/Algorithm.h
@@ -0,0 +1,43 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/* A polyfill for `<algorithm>`. */
+
+#ifndef mozilla_Algorithm_h
+#define mozilla_Algorithm_h
+
+namespace mozilla {
+
+// Returns true if all elements in the range [aFirst, aLast)
+// satisfy the predicate aPred.
+template <class Iter, class Pred>
+bool AllOf(Iter aFirst, Iter aLast, Pred aPred)
+{
+  for (; aFirst != aLast; ++aFirst) {
+    if (!aPred(*aFirst)) {
+      return false;
+    }
+  }
+  return true;
+}
+
+// This is a `constexpr` alternative to AllOf. It should
+// only be used for compile-time computation because it uses recursion.
+// XXX: once support for GCC 4.9 is dropped, this function should be removed
+// and AllOf should be made `constexpr`.
+// XXX: This implementation requires RandomAccessIterator.
+template <class Iter, class Pred>
+constexpr bool ConstExprAllOf(Iter aFirst, Iter aLast, Pred aPred)
+{
+  return aFirst == aLast ? true :
+    aLast - aFirst == 1 ? aPred(*aFirst) :
+    ConstExprAllOf(aFirst, aFirst + (aLast - aFirst) / 2, aPred) &&
+    ConstExprAllOf(aFirst + (aLast - aFirst) / 2, aLast, aPred);
+}
+
+} // namespace mozilla
+
+#endif // mozilla_Algorithm_h
--- a/mfbt/moz.build
+++ b/mfbt/moz.build
@@ -7,16 +7,17 @@
 with Files("**"):
     BUG_COMPONENT = ("Core", "MFBT")
 
 TEST_DIRS += ['tests']
 
 Library('mfbt')
 
 EXPORTS.mozilla = [
+    'Algorithm.h',
     'Alignment.h',
     'AllocPolicy.h',
     'AlreadyAddRefed.h',
     'Array.h',
     'ArrayUtils.h',
     'Assertions.h',
     'Atomics.h',
     'Attributes.h',
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestAlgorithm.cpp
@@ -0,0 +1,56 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this file,
+ * You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/Algorithm.h"
+#include "mozilla/Assertions.h"
+#include <algorithm>
+
+static constexpr bool even(int32_t n) { return !(n & 1); }
+static constexpr bool odd(int32_t n) { return (n & 1); }
+
+void TestAllOf()
+{
+  using namespace mozilla;
+  using namespace std;
+
+  int32_t arr1[3] = {1, 2, 3};
+  MOZ_RELEASE_ASSERT(!AllOf(begin(arr1), end(arr1), even));
+  MOZ_RELEASE_ASSERT(!AllOf(begin(arr1), end(arr1), odd));
+
+  int32_t arr2[3] = {1, 3, 5};
+  MOZ_RELEASE_ASSERT(!AllOf(begin(arr2), end(arr2), even));
+  MOZ_RELEASE_ASSERT(AllOf(begin(arr2), end(arr2), odd));
+
+  int32_t arr3[3] = {2, 4, 6};
+  MOZ_RELEASE_ASSERT(AllOf(begin(arr3), end(arr3), even));
+  MOZ_RELEASE_ASSERT(!AllOf(begin(arr3), end(arr3), odd));
+}
+
+void TestConstExprAllOf()
+{
+  using namespace mozilla;
+  using namespace std;
+
+  constexpr int32_t arr1[3] = {1, 2, 3};
+  static_assert(!ConstExprAllOf(begin(arr1), end(arr1), even), "1-1");
+  static_assert(!ConstExprAllOf(begin(arr1), end(arr1), odd), "1-2");
+
+  constexpr int32_t arr2[3] = {1, 3, 5};
+  static_assert(!ConstExprAllOf(begin(arr2), end(arr2), even), "2-1");
+  static_assert(ConstExprAllOf(begin(arr2), end(arr2), odd), "2-2");
+
+  constexpr int32_t arr3[3] = {2, 4, 6};
+  static_assert(ConstExprAllOf(begin(arr3), end(arr3), even), "3-1");
+  static_assert(!ConstExprAllOf(begin(arr3), end(arr3), odd), "3-2");
+}
+
+int
+main()
+{
+  TestAllOf();
+  TestConstExprAllOf();
+  return 0;
+}
\ No newline at end of file
--- a/mfbt/tests/moz.build
+++ b/mfbt/tests/moz.build
@@ -5,16 +5,17 @@
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 if CONFIG['MOZ_WIDGET_TOOLKIT']:
     TEST_DIRS += [
         'gtest',
     ]
 
 CppUnitTests([
+    'TestAlgorithm',
     'TestArray',
     'TestArrayUtils',
     'TestAtomics',
     'TestBinarySearch',
     'TestBloomFilter',
     'TestBufferList',
     'TestCasting',
     'TestCeilingFloor',