Reland of "Add Iterable bitset class."
This helper allows us to quickly iterate state bits from the
Impl/Renderer layers.
Re-land with no C++11 usage.
BUG=angleproject:1040
TEST=angle_unittests (Mac/Win/Linux)
Change-Id: I3b6d5beb2bcff7fa3d45c9220d7c026c64c45d2e
Reviewed-on: https://chromium-review.googlesource.com/290153
Tested-by: Jamie Madill <jmadill@chromium.org>
Reviewed-by: Geoff Lang <geofflang@chromium.org>
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
diff --git a/src/common/BitSetIterator.h b/src/common/BitSetIterator.h
new file mode 100644
index 0000000..d1d2a50
--- /dev/null
+++ b/src/common/BitSetIterator.h
@@ -0,0 +1,156 @@
+//
+// Copyright 2015 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// BitSetIterator:
+// A helper class to quickly bitscan bitsets for set bits.
+//
+
+#ifndef COMMON_BITSETITERATOR_H_
+#define COMMON_BITSETITERATOR_H_
+
+#include <stdint.h>
+
+#include <bitset>
+
+#include "common/angleutils.h"
+#include "common/debug.h"
+#include "common/mathutil.h"
+#include "common/platform.h"
+
+namespace angle
+{
+template <size_t N>
+class BitSetIterator final
+{
+ public:
+ BitSetIterator(const std::bitset<N> &bitset);
+ BitSetIterator(const BitSetIterator &other);
+ BitSetIterator &operator=(const BitSetIterator &other);
+
+ class Iterator final
+ {
+ public:
+ Iterator(const std::bitset<N> &bits);
+ Iterator &operator++();
+
+ bool operator==(const Iterator &other) const;
+ bool operator!=(const Iterator &other) const;
+ unsigned long operator*() const { return mCurrentBit; }
+
+ private:
+ unsigned long getNextBit();
+
+ static const size_t BitsPerWord = sizeof(unsigned long) * 8;
+ std::bitset<N> mBits;
+ unsigned long mCurrentBit;
+ unsigned long mOffset;
+ };
+
+ Iterator begin() const { return Iterator(mBits); }
+ Iterator end() const { return Iterator(std::bitset<N>(0)); }
+
+ private:
+ const std::bitset<N> &mBits;
+};
+
+template <size_t N>
+BitSetIterator<N>::BitSetIterator(const std::bitset<N> &bitset)
+ : mBits(bitset)
+{
+}
+
+template <size_t N>
+BitSetIterator<N>::BitSetIterator(const BitSetIterator &other)
+ : mBits(other.mBits)
+{
+}
+
+template <size_t N>
+BitSetIterator<N> &BitSetIterator<N>::operator=(const BitSetIterator &other)
+{
+ mBits = other.mBits;
+ return *this;
+}
+
+template <size_t N>
+BitSetIterator<N>::Iterator::Iterator(const std::bitset<N> &bits)
+ : mBits(bits), mCurrentBit(0), mOffset(0)
+{
+ if (bits.any())
+ {
+ mCurrentBit = getNextBit();
+ }
+ else
+ {
+ mOffset = rx::roundUp(N, BitsPerWord);
+ }
+}
+
+template <size_t N>
+typename BitSetIterator<N>::Iterator &BitSetIterator<N>::Iterator::operator++()
+{
+ ASSERT(mBits.any());
+ mBits.set(mCurrentBit - mOffset, 0);
+ mCurrentBit = getNextBit();
+ return *this;
+}
+
+inline unsigned long ScanForward(unsigned long bits)
+{
+ ASSERT(bits != 0);
+#if defined(ANGLE_PLATFORM_WINDOWS)
+ unsigned long firstBitIndex = 0ul;
+ unsigned char ret = _BitScanForward(&firstBitIndex, bits);
+ ASSERT(ret != 0);
+ UNUSED_ASSERTION_VARIABLE(ret);
+ return firstBitIndex;
+#elif defined(ANGLE_PLATFORM_POSIX)
+ return static_cast<unsigned long>(__builtin_ctzl(bits));
+#else
+#error Please implement bit-scan-forward for your platform!
+#endif
+}
+
+template <size_t N>
+bool BitSetIterator<N>::Iterator::operator==(const Iterator &other) const
+{
+ return mOffset == other.mOffset && mBits == other.mBits;
+}
+
+template <size_t N>
+bool BitSetIterator<N>::Iterator::operator!=(const Iterator &other) const
+{
+ return !(*this == other);
+}
+
+template <size_t N>
+unsigned long BitSetIterator<N>::Iterator::getNextBit()
+{
+ static std::bitset<N> wordMask(std::numeric_limits<unsigned long>::max());
+
+ while (mOffset < N)
+ {
+ unsigned long wordBits = (mBits & wordMask).to_ulong();
+ if (wordBits != 0ul)
+ {
+ return ScanForward(wordBits) + mOffset;
+ }
+
+ mBits >>= BitsPerWord;
+ mOffset += BitsPerWord;
+ }
+ return 0;
+}
+
+// Helper to avoid needing to specify the template parameter size
+template <size_t N>
+BitSetIterator<N> IterateBitSet(const std::bitset<N> &bitset)
+{
+ return BitSetIterator<N>(bitset);
+}
+
+} // angle
+
+#endif // COMMON_BITSETITERATOR_H_
diff --git a/src/common/BitSetIterator_unittest.cpp b/src/common/BitSetIterator_unittest.cpp
new file mode 100644
index 0000000..b1411d9
--- /dev/null
+++ b/src/common/BitSetIterator_unittest.cpp
@@ -0,0 +1,48 @@
+//
+// Copyright 2015 The ANGLE Project Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+//
+// BitSetIteratorTest:
+// Test the IterableBitSet class.
+//
+
+#include <gtest/gtest.h>
+
+#include "common/BitSetIterator.h"
+
+using namespace angle;
+
+namespace
+{
+class BitSetIteratorTest : public testing::Test
+{
+ protected:
+ std::bitset<40> mStateBits;
+};
+
+TEST_F(BitSetIteratorTest, Iterator)
+{
+ std::set<unsigned long> originalValues;
+ originalValues.insert(2);
+ originalValues.insert(6);
+ originalValues.insert(8);
+ originalValues.insert(35);
+
+ for (unsigned long value : originalValues)
+ {
+ mStateBits.set(value);
+ }
+
+ std::set<unsigned long> readValues;
+ for (unsigned long bit : IterateBitSet(mStateBits))
+ {
+ EXPECT_EQ(1u, originalValues.count(bit));
+ EXPECT_EQ(0u, readValues.count(bit));
+ readValues.insert(bit);
+ }
+
+ EXPECT_EQ(originalValues.size(), readValues.size());
+}
+
+} // anonymous namespace
diff --git a/src/libGLESv2.gypi b/src/libGLESv2.gypi
index b1681d5..2af46fc 100644
--- a/src/libGLESv2.gypi
+++ b/src/libGLESv2.gypi
@@ -8,6 +8,7 @@
# These file lists are shared with the GN build.
'libangle_common_sources':
[
+ 'common/BitSetIterator.h',
'common/Float16ToFloat32.cpp',
'common/MemoryBuffer.cpp',
'common/MemoryBuffer.h',
diff --git a/src/tests/angle_unittests.gypi b/src/tests/angle_unittests.gypi
index 1081575..aae9d81 100644
--- a/src/tests/angle_unittests.gypi
+++ b/src/tests/angle_unittests.gypi
@@ -15,6 +15,7 @@
# This file list will be shared with the GN build.
'angle_unittests_sources':
[
+ '<(angle_path)/src/common/BitSetIterator_unittest.cpp',
'<(angle_path)/src/common/Optional_unittest.cpp',
'<(angle_path)/src/common/mathutil_unittest.cpp',
'<(angle_path)/src/common/matrix_utils_unittest.cpp',