1 files changed, 155 insertions, 0 deletions
diff --git a/gfx/angle/src/common/BitSetIterator.h b/gfx/angle/src/common/BitSetIterator.h
new file mode 100755
index 000000000..7fecd3769
--- /dev/null
+++ b/gfx/angle/src/common/BitSetIterator.h
@@ -0,0 +1,155 @@
+//
+// 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 = static_cast<unsigned long>(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);
+    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_