- Revision
- 199354
- Author
- carlo...@webkit.org
- Date
- 2016-04-12 08:46:05 -0700 (Tue, 12 Apr 2016)
Log Message
Merge r197788 - Support iterating over an OptionSet and checking if it is empty
https://bugs.webkit.org/show_bug.cgi?id=154941
<rdar://problem/24964187>
Reviewed by Darin Adler.
Source/WTF:
Implements support for iterating over the enumerators in an OptionSet as well as
determining if the set is empty.
Iterating over an OptionSet is in Big Theta(N) where N is the number of items in
the set. More precisely, it is in Big Theta(log M) where M is the bitmask represented
by the bitwise OR-ing of all enumerators in the set.
* wtf/OptionSet.h: Added comment to describe the purpose of this class and its invariant -
the enumerators must be positive powers of two.
(WTF::OptionSet::Iterator::operator*): Returns the enumerator pointed to by the iterator.
(WTF::OptionSet::Iterator::operator++): Advance to the next smallest enumerator in the set.
(WTF::OptionSet::Iterator::operator==): Returns whether the iterator is equal to the specified iterator.
(WTF::OptionSet::Iterator::operator!=): Returns whether the iterator is not equal to the specified iterator.
(WTF::OptionSet::Iterator::Iterator): Added.
(WTF::OptionSet::fromRaw): Instantiate using specialized private constructor to allow
instantiation with a raw value of 0.
(WTF::OptionSet::OptionSet): Specialized constructor that asserts that the specified value
is a positive power of two. This variant is only compiled when assertions are enabled (i.e. !ASSERT_DISABLED).
(WTF::OptionSet::isEmpty): Returns whether the set is empty.
(WTF::OptionSet::begin): Returns an iterator to the enumerator with the smallest value in the set.
(WTF::OptionSet::end): Returns an iterator that represents the end sentinel of the set.
Tools:
Add tests to ensure that we do not regression both iteration of an OptionSet and
determining whether an OptionSet is empty.
* TestWebKitAPI/Test.h:
(TestWebKitAPI::Util::assertStrongEnum): Helper function to assert two strong enum type for equality.
* TestWebKitAPI/Tests/WTF/OptionSet.cpp:
(TestWebKitAPI::TEST):
Modified Paths
Diff
Modified: releases/WebKitGTK/webkit-2.12/Source/WTF/ChangeLog (199353 => 199354)
--- releases/WebKitGTK/webkit-2.12/Source/WTF/ChangeLog 2016-04-12 15:45:42 UTC (rev 199353)
+++ releases/WebKitGTK/webkit-2.12/Source/WTF/ChangeLog 2016-04-12 15:46:05 UTC (rev 199354)
@@ -1,3 +1,33 @@
+2016-03-08 Daniel Bates <daba...@apple.com>
+
+ Support iterating over an OptionSet and checking if it is empty
+ https://bugs.webkit.org/show_bug.cgi?id=154941
+ <rdar://problem/24964187>
+
+ Reviewed by Darin Adler.
+
+ Implements support for iterating over the enumerators in an OptionSet as well as
+ determining if the set is empty.
+
+ Iterating over an OptionSet is in Big Theta(N) where N is the number of items in
+ the set. More precisely, it is in Big Theta(log M) where M is the bitmask represented
+ by the bitwise OR-ing of all enumerators in the set.
+
+ * wtf/OptionSet.h: Added comment to describe the purpose of this class and its invariant -
+ the enumerators must be positive powers of two.
+ (WTF::OptionSet::Iterator::operator*): Returns the enumerator pointed to by the iterator.
+ (WTF::OptionSet::Iterator::operator++): Advance to the next smallest enumerator in the set.
+ (WTF::OptionSet::Iterator::operator==): Returns whether the iterator is equal to the specified iterator.
+ (WTF::OptionSet::Iterator::operator!=): Returns whether the iterator is not equal to the specified iterator.
+ (WTF::OptionSet::Iterator::Iterator): Added.
+ (WTF::OptionSet::fromRaw): Instantiate using specialized private constructor to allow
+ instantiation with a raw value of 0.
+ (WTF::OptionSet::OptionSet): Specialized constructor that asserts that the specified value
+ is a positive power of two. This variant is only compiled when assertions are enabled (i.e. !ASSERT_DISABLED).
+ (WTF::OptionSet::isEmpty): Returns whether the set is empty.
+ (WTF::OptionSet::begin): Returns an iterator to the enumerator with the smallest value in the set.
+ (WTF::OptionSet::end): Returns an iterator that represents the end sentinel of the set.
+
2016-03-03 Daniel Bates <daba...@apple.com>
Add unit tests for WTF::OptionSet
Modified: releases/WebKitGTK/webkit-2.12/Source/WTF/wtf/OptionSet.h (199353 => 199354)
--- releases/WebKitGTK/webkit-2.12/Source/WTF/wtf/OptionSet.h 2016-04-12 15:45:42 UTC (rev 199353)
+++ releases/WebKitGTK/webkit-2.12/Source/WTF/wtf/OptionSet.h 2016-04-12 15:46:05 UTC (rev 199354)
@@ -27,37 +27,83 @@
#define OptionSet_h
#include <initializer_list>
+#include <iterator>
#include <type_traits>
+#include <wtf/Assertions.h>
+#include <wtf/MathExtras.h>
namespace WTF {
+// OptionSet is a class that represents a set of enumerators in a space-efficient manner. The enumerators
+// must be powers of two greater than 0. This class is useful as a replacement for passing a bitmask of
+// enumerators around.
template<typename T> class OptionSet {
static_assert(std::is_enum<T>::value, "T is not an enum type");
typedef typename std::make_unsigned<typename std::underlying_type<T>::type>::type StorageType;
public:
+ template<typename StorageType> class Iterator {
+ public:
+ // Isolate the rightmost set bit.
+ T operator*() const { return static_cast<T>(m_value & -m_value); }
+
+ // Iterates from smallest to largest enum value by turning off the rightmost set bit.
+ Iterator& operator++()
+ {
+ m_value &= m_value - 1;
+ return *this;
+ }
+
+ Iterator& operator++(int) = delete;
+
+ bool operator==(const Iterator& other) const { return m_value == other.m_value; }
+ bool operator!=(const Iterator& other) const { return m_value != other.m_value; }
+
+ private:
+ Iterator(StorageType value) : m_value(value) { }
+ friend OptionSet;
+
+ StorageType m_value;
+ };
+ using iterator = Iterator<StorageType>;
+
static OptionSet fromRaw(StorageType storageType)
{
- return static_cast<T>(storageType);
+ return OptionSet(static_cast<T>(storageType), FromRawValue);
}
constexpr OptionSet() = default;
+#if ASSERT_DISABLED
constexpr OptionSet(T t)
: m_storage(static_cast<StorageType>(t))
{
}
+#else
+ OptionSet(T t)
+ : m_storage(static_cast<StorageType>(t))
+ {
+ ASSERT_WITH_MESSAGE(hasOneBitSet(static_cast<StorageType>(t)), "Enumerator is not a positive power of two.");
+ }
+#endif
// FIXME: Make this constexpr once we adopt C++14 as C++11 does not support for-loops
// in a constexpr function.
OptionSet(std::initializer_list<T> initializerList)
{
- for (auto& option : initializerList)
+ for (auto& option : initializerList) {
+ ASSERT_WITH_MESSAGE(hasOneBitSet(static_cast<StorageType>(option)), "Enumerator is not a positive power of two.");
m_storage |= static_cast<StorageType>(option);
+ }
}
constexpr StorageType toRaw() const { return m_storage; }
+ constexpr bool isEmpty() const { return !m_storage; }
+
+ constexpr iterator begin() const { return m_storage; }
+ constexpr iterator end() const { return 0; }
+
constexpr bool contains(OptionSet optionSet) const
{
return m_storage & optionSet.m_storage;
@@ -71,6 +117,11 @@
}
private:
+ enum InitializationTag { FromRawValue };
+ constexpr OptionSet(T t, InitializationTag)
+ : m_storage(static_cast<StorageType>(t))
+ {
+ }
StorageType m_storage { 0 };
};
Modified: releases/WebKitGTK/webkit-2.12/Tools/ChangeLog (199353 => 199354)
--- releases/WebKitGTK/webkit-2.12/Tools/ChangeLog 2016-04-12 15:45:42 UTC (rev 199353)
+++ releases/WebKitGTK/webkit-2.12/Tools/ChangeLog 2016-04-12 15:46:05 UTC (rev 199354)
@@ -1,3 +1,19 @@
+2016-03-08 Daniel Bates <daba...@apple.com>
+
+ Support iterating over an OptionSet and checking if it is empty
+ https://bugs.webkit.org/show_bug.cgi?id=154941
+ <rdar://problem/24964187>
+
+ Reviewed by Darin Adler.
+
+ Add tests to ensure that we do not regression both iteration of an OptionSet and
+ determining whether an OptionSet is empty.
+
+ * TestWebKitAPI/Test.h:
+ (TestWebKitAPI::Util::assertStrongEnum): Helper function to assert two strong enum type for equality.
+ * TestWebKitAPI/Tests/WTF/OptionSet.cpp:
+ (TestWebKitAPI::TEST):
+
2016-03-03 Daniel Bates <daba...@apple.com>
Add unit tests for WTF::OptionSet
Modified: releases/WebKitGTK/webkit-2.12/Tools/TestWebKitAPI/Test.h (199353 => 199354)
--- releases/WebKitGTK/webkit-2.12/Tools/TestWebKitAPI/Test.h 2016-04-12 15:45:42 UTC (rev 199353)
+++ releases/WebKitGTK/webkit-2.12/Tools/TestWebKitAPI/Test.h 2016-04-12 15:46:05 UTC (rev 199354)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2010 Apple Inc. All rights reserved.
+ * Copyright (C) 2010, 2016 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -26,6 +26,8 @@
#ifndef Test_h
#define Test_h
+#include <type_traits>
+
namespace TestWebKitAPI {
#define EXPECT_NOT_NULL(_expression_) \
@@ -40,6 +42,18 @@
#define ASSERT_NULL(_expression_) \
ASSERT_TRUE(!(_expression_))
+template<typename T>
+static inline ::testing::AssertionResult assertStrongEnum(const char* expected_expression, const char* actual_expression, T expected, T actual)
+{
+ static_assert(std::is_enum<T>::value, "T is not an enum type");
+ typedef typename std::underlying_type<T>::type UnderlyingStorageType;
+ return ::testing::internal::CmpHelperEQ(expected_expression, actual_expression, static_cast<UnderlyingStorageType>(expected), static_cast<UnderlyingStorageType>(actual));
+}
+
+#define EXPECT_STRONG_ENUM_EQ(expected, actual) \
+ EXPECT_PRED_FORMAT2(TestWebKitAPI::assertStrongEnum, expected, actual)
+
+
} // namespace TestWebKitAPI
#endif // Test_h
Modified: releases/WebKitGTK/webkit-2.12/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp (199353 => 199354)
--- releases/WebKitGTK/webkit-2.12/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp 2016-04-12 15:45:42 UTC (rev 199353)
+++ releases/WebKitGTK/webkit-2.12/Tools/TestWebKitAPI/Tests/WTF/OptionSet.cpp 2016-04-12 15:46:05 UTC (rev 199354)
@@ -25,40 +25,74 @@
#include "config.h"
+#include "Test.h"
#include <wtf/OptionSet.h>
namespace TestWebKitAPI {
-enum class ExampleFlags {
+enum class ExampleFlags : uint64_t {
A = 1 << 0,
B = 1 << 1,
C = 1 << 2,
+ D = 1ULL << 31,
+ E = 1ULL << 63,
};
TEST(WTF_OptionSet, EmptySet)
{
OptionSet<ExampleFlags> set;
+ EXPECT_TRUE(set.isEmpty());
EXPECT_FALSE(set.contains(ExampleFlags::A));
EXPECT_FALSE(set.contains(ExampleFlags::B));
EXPECT_FALSE(set.contains(ExampleFlags::C));
+ EXPECT_FALSE(set.contains(ExampleFlags::D));
+ EXPECT_FALSE(set.contains(ExampleFlags::E));
}
TEST(WTF_OptionSet, ContainsOneFlag)
{
OptionSet<ExampleFlags> set = ExampleFlags::A;
+ EXPECT_FALSE(set.isEmpty());
EXPECT_TRUE(set.contains(ExampleFlags::A));
EXPECT_FALSE(set.contains(ExampleFlags::B));
EXPECT_FALSE(set.contains(ExampleFlags::C));
+ EXPECT_FALSE(set.contains(ExampleFlags::D));
+ EXPECT_FALSE(set.contains(ExampleFlags::E));
}
TEST(WTF_OptionSet, ContainsTwoFlags)
{
OptionSet<ExampleFlags> set { ExampleFlags::A, ExampleFlags::B };
+ EXPECT_FALSE(set.isEmpty());
EXPECT_TRUE(set.contains(ExampleFlags::A));
EXPECT_TRUE(set.contains(ExampleFlags::B));
EXPECT_FALSE(set.contains(ExampleFlags::C));
+ EXPECT_FALSE(set.contains(ExampleFlags::D));
+ EXPECT_FALSE(set.contains(ExampleFlags::E));
}
+TEST(WTF_OptionSet, ContainsTwoFlags2)
+{
+ OptionSet<ExampleFlags> set { ExampleFlags::A, ExampleFlags::D };
+ EXPECT_FALSE(set.isEmpty());
+ EXPECT_TRUE(set.contains(ExampleFlags::A));
+ EXPECT_TRUE(set.contains(ExampleFlags::D));
+ EXPECT_FALSE(set.contains(ExampleFlags::B));
+ EXPECT_FALSE(set.contains(ExampleFlags::C));
+ EXPECT_FALSE(set.contains(ExampleFlags::E));
+}
+
+TEST(WTF_OptionSet, ContainsTwoFlags3)
+{
+ OptionSet<ExampleFlags> set { ExampleFlags::D, ExampleFlags::E };
+ EXPECT_FALSE(set.isEmpty());
+ EXPECT_TRUE(set.contains(ExampleFlags::D));
+ EXPECT_TRUE(set.contains(ExampleFlags::E));
+ EXPECT_FALSE(set.contains(ExampleFlags::A));
+ EXPECT_FALSE(set.contains(ExampleFlags::B));
+ EXPECT_FALSE(set.contains(ExampleFlags::C));
+}
+
TEST(WTF_OptionSet, OperatorBitwiseOr)
{
OptionSet<ExampleFlags> set = ExampleFlags::A;
@@ -71,11 +105,13 @@
TEST(WTF_OptionSet, EmptyOptionSetToRawValueToOptionSet)
{
OptionSet<ExampleFlags> set;
+ EXPECT_TRUE(set.isEmpty());
EXPECT_FALSE(set.contains(ExampleFlags::A));
EXPECT_FALSE(set.contains(ExampleFlags::B));
EXPECT_FALSE(set.contains(ExampleFlags::C));
auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
+ EXPECT_TRUE(set2.isEmpty());
EXPECT_FALSE(set2.contains(ExampleFlags::A));
EXPECT_FALSE(set2.contains(ExampleFlags::B));
EXPECT_FALSE(set2.contains(ExampleFlags::C));
@@ -84,27 +120,152 @@
TEST(WTF_OptionSet, OptionSetThatContainsOneFlagToRawValueToOptionSet)
{
OptionSet<ExampleFlags> set = ExampleFlags::A;
+ EXPECT_FALSE(set.isEmpty());
EXPECT_TRUE(set.contains(ExampleFlags::A));
EXPECT_FALSE(set.contains(ExampleFlags::B));
EXPECT_FALSE(set.contains(ExampleFlags::C));
+ EXPECT_FALSE(set.contains(ExampleFlags::D));
+ EXPECT_FALSE(set.contains(ExampleFlags::E));
auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
+ EXPECT_FALSE(set2.isEmpty());
EXPECT_TRUE(set2.contains(ExampleFlags::A));
EXPECT_FALSE(set2.contains(ExampleFlags::B));
EXPECT_FALSE(set2.contains(ExampleFlags::C));
+ EXPECT_FALSE(set2.contains(ExampleFlags::D));
+ EXPECT_FALSE(set2.contains(ExampleFlags::E));
}
+TEST(WTF_OptionSet, OptionSetThatContainsOneFlagToRawValueToOptionSet2)
+{
+ OptionSet<ExampleFlags> set = ExampleFlags::E;
+ EXPECT_FALSE(set.isEmpty());
+ EXPECT_TRUE(set.contains(ExampleFlags::E));
+ EXPECT_FALSE(set.contains(ExampleFlags::A));
+ EXPECT_FALSE(set.contains(ExampleFlags::B));
+ EXPECT_FALSE(set.contains(ExampleFlags::C));
+ EXPECT_FALSE(set.contains(ExampleFlags::D));
+
+ auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
+ EXPECT_FALSE(set2.isEmpty());
+ EXPECT_TRUE(set2.contains(ExampleFlags::E));
+ EXPECT_FALSE(set2.contains(ExampleFlags::A));
+ EXPECT_FALSE(set2.contains(ExampleFlags::B));
+ EXPECT_FALSE(set2.contains(ExampleFlags::C));
+ EXPECT_FALSE(set2.contains(ExampleFlags::D));
+}
+
TEST(WTF_OptionSet, OptionSetThatContainsTwoFlagsToRawValueToOptionSet)
{
OptionSet<ExampleFlags> set { ExampleFlags::A, ExampleFlags::C };
+ EXPECT_FALSE(set.isEmpty());
EXPECT_TRUE(set.contains(ExampleFlags::A));
EXPECT_TRUE(set.contains(ExampleFlags::C));
EXPECT_FALSE(set.contains(ExampleFlags::B));
auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
+ EXPECT_FALSE(set2.isEmpty());
EXPECT_TRUE(set2.contains(ExampleFlags::A));
EXPECT_TRUE(set2.contains(ExampleFlags::C));
EXPECT_FALSE(set2.contains(ExampleFlags::B));
}
+TEST(WTF_OptionSet, OptionSetThatContainsTwoFlagsToRawValueToOptionSet2)
+{
+ OptionSet<ExampleFlags> set { ExampleFlags::D, ExampleFlags::E };
+ EXPECT_FALSE(set.isEmpty());
+ EXPECT_TRUE(set.contains(ExampleFlags::D));
+ EXPECT_TRUE(set.contains(ExampleFlags::E));
+ EXPECT_FALSE(set.contains(ExampleFlags::A));
+ EXPECT_FALSE(set.contains(ExampleFlags::B));
+ EXPECT_FALSE(set.contains(ExampleFlags::C));
+
+ auto set2 = OptionSet<ExampleFlags>::fromRaw(set.toRaw());
+ EXPECT_FALSE(set2.isEmpty());
+ EXPECT_TRUE(set2.contains(ExampleFlags::D));
+ EXPECT_TRUE(set2.contains(ExampleFlags::E));
+ EXPECT_FALSE(set2.contains(ExampleFlags::A));
+ EXPECT_FALSE(set2.contains(ExampleFlags::B));
+ EXPECT_FALSE(set2.contains(ExampleFlags::C));
+}
+
+TEST(WTF_OptionSet, TwoIteratorsIntoSameOptionSet)
+{
+ OptionSet<ExampleFlags> set { ExampleFlags::C, ExampleFlags::B };
+ OptionSet<ExampleFlags>::iterator it1 = set.begin();
+ OptionSet<ExampleFlags>::iterator it2 = it1;
+ ++it1;
+ EXPECT_STRONG_ENUM_EQ(ExampleFlags::C, *it1);
+ EXPECT_STRONG_ENUM_EQ(ExampleFlags::B, *it2);
+}
+
+TEST(WTF_OptionSet, IterateOverOptionSetThatContainsTwoFlags)
+{
+ OptionSet<ExampleFlags> set { ExampleFlags::A, ExampleFlags::C };
+ OptionSet<ExampleFlags>::iterator it = set.begin();
+ OptionSet<ExampleFlags>::iterator end = set.end();
+ EXPECT_TRUE(it != end);
+ EXPECT_STRONG_ENUM_EQ(ExampleFlags::A, *it);
+ ++it;
+ EXPECT_STRONG_ENUM_EQ(ExampleFlags::C, *it);
+ ++it;
+ EXPECT_TRUE(it == end);
+}
+
+TEST(WTF_OptionSet, IterateOverOptionSetThatContainsFlags2)
+{
+ OptionSet<ExampleFlags> set { ExampleFlags::D, ExampleFlags::E };
+ OptionSet<ExampleFlags>::iterator it = set.begin();
+ OptionSet<ExampleFlags>::iterator end = set.end();
+ EXPECT_TRUE(it != end);
+ EXPECT_STRONG_ENUM_EQ(ExampleFlags::D, *it);
+ ++it;
+ EXPECT_STRONG_ENUM_EQ(ExampleFlags::E, *it);
+ ++it;
+ EXPECT_TRUE(it == end);
+}
+
+TEST(WTF_OptionSet, NextItemAfterLargestIn32BitFlagSet)
+{
+ enum class ThirtyTwoBitFlags : uint32_t {
+ A = 1UL << 31,
+ };
+ OptionSet<ThirtyTwoBitFlags> set { ThirtyTwoBitFlags::A };
+ OptionSet<ThirtyTwoBitFlags>::iterator it = set.begin();
+ OptionSet<ThirtyTwoBitFlags>::iterator end = set.end();
+ EXPECT_TRUE(it != end);
+ ++it;
+ EXPECT_TRUE(it == end);
+}
+
+TEST(WTF_OptionSet, NextItemAfterLargestIn64BitFlagSet)
+{
+ enum class SixtyFourBitFlags : uint64_t {
+ A = 1ULL << 63,
+ };
+ OptionSet<SixtyFourBitFlags> set { SixtyFourBitFlags::A };
+ OptionSet<SixtyFourBitFlags>::iterator it = set.begin();
+ OptionSet<SixtyFourBitFlags>::iterator end = set.end();
+ EXPECT_TRUE(it != end);
+ ++it;
+ EXPECT_TRUE(it == end);
+}
+
+TEST(WTF_OptionSet, IterationOrderTheSameRegardlessOfInsertionOrder)
+{
+ OptionSet<ExampleFlags> set1 = ExampleFlags::C;
+ set1 |= ExampleFlags::A;
+
+ OptionSet<ExampleFlags> set2 = ExampleFlags::A;
+ set2 |= ExampleFlags::C;
+
+ OptionSet<ExampleFlags>::iterator it1 = set1.begin();
+ OptionSet<ExampleFlags>::iterator it2 = set2.begin();
+
+ EXPECT_TRUE(*it1 == *it2);
+ ++it1;
+ ++it2;
+ EXPECT_TRUE(*it1 == *it2);
+}
+
} // namespace TestWebKitAPI
