2 files changed, 161 insertions, 0 deletions
diff --git a/utils/SkBitSet.cpp b/utils/SkBitSet.cpp
new file mode 100755
index 00000000..664c8cd8
--- /dev/null
+++ b/utils/SkBitSet.cpp
@@ -0,0 +1,83 @@
+
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+
+#include "SkBitSet.h"
+
+SkBitSet::SkBitSet(int numberOfBits)
+    : fBitData(NULL), fDwordCount(0), fBitCount(numberOfBits) {
+    SkASSERT(numberOfBits > 0);
+    // Round up size to 32-bit boundary.
+    fDwordCount = (numberOfBits + 31) / 32;
+    fBitData.set(malloc(fDwordCount * sizeof(uint32_t)));
+    clearAll();
+}
+
+SkBitSet::SkBitSet(const SkBitSet& source)
+    : fBitData(NULL), fDwordCount(0), fBitCount(0) {
+    *this = source;
+}
+
+const SkBitSet& SkBitSet::operator=(const SkBitSet& rhs) {
+    if (this == &rhs) {
+        return *this;
+    }
+    fBitCount = rhs.fBitCount;
+    fBitData.free();
+    fDwordCount = rhs.fDwordCount;
+    fBitData.set(malloc(fDwordCount * sizeof(uint32_t)));
+    memcpy(fBitData.get(), rhs.fBitData.get(), fDwordCount * sizeof(uint32_t));
+    return *this;
+}
+
+bool SkBitSet::operator==(const SkBitSet& rhs) {
+    if (fBitCount == rhs.fBitCount) {
+        if (fBitData.get() != NULL) {
+            return (memcmp(fBitData.get(), rhs.fBitData.get(),
+                           fDwordCount * sizeof(uint32_t)) == 0);
+        }
+        return true;
+    }
+    return false;
+}
+
+bool SkBitSet::operator!=(const SkBitSet& rhs) {
+    return !(*this == rhs);
+}
+
+void SkBitSet::clearAll() {
+    if (fBitData.get() != NULL) {
+        sk_bzero(fBitData.get(), fDwordCount * sizeof(uint32_t));
+    }
+}
+
+void SkBitSet::setBit(int index, bool value) {
+    uint32_t mask = 1 << (index % 32);
+    if (value) {
+        *(internalGet(index)) |= mask;
+    } else {
+        *(internalGet(index)) &= ~mask;
+    }
+}
+
+bool SkBitSet::isBitSet(int index) const {
+    uint32_t mask = 1 << (index % 32);
+    return 0 != (*internalGet(index) & mask);
+}
+
+bool SkBitSet::orBits(const SkBitSet& source) {
+    if (fBitCount != source.fBitCount) {
+        return false;
+    }
+    uint32_t* targetBitmap = internalGet(0);
+    uint32_t* sourceBitmap = source.internalGet(0);
+    for (size_t i = 0; i < fDwordCount; ++i) {
+        targetBitmap[i] |= sourceBitmap[i];
+    }
+    return true;
+}
diff --git a/utils/SkBitSet.h b/utils/SkBitSet.h
new file mode 100755
index 00000000..484fc2ae
--- /dev/null
+++ b/utils/SkBitSet.h
@@ -0,0 +1,78 @@
+
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+
+#ifndef SkBitSet_DEFINED
+#define SkBitSet_DEFINED
+
+#include "SkTypes.h"
+#include "SkTDArray.h"
+
+class SkBitSet {
+public:
+    /** NumberOfBits must be greater than zero.
+     */
+    explicit SkBitSet(int numberOfBits);
+    explicit SkBitSet(const SkBitSet& source);
+
+    const SkBitSet& operator=(const SkBitSet& rhs);
+    bool operator==(const SkBitSet& rhs);
+    bool operator!=(const SkBitSet& rhs);
+
+    /** Clear all data.
+     */
+    void clearAll();
+
+    /** Set the value of the index-th bit.
+     */
+    void setBit(int index, bool value);
+
+    /** Test if bit index is set.
+     */
+    bool isBitSet(int index) const;
+
+    /** Or bits from source.  false is returned if this doesn't have the same
+     *  bit count as source.
+     */
+    bool orBits(const SkBitSet& source);
+
+    /** Export indices of set bits to T array.
+     */
+    template<typename T>
+    void exportTo(SkTDArray<T>* array) const {
+        SkASSERT(array);
+        uint32_t* data = reinterpret_cast<uint32_t*>(fBitData.get());
+        for (unsigned int i = 0; i < fDwordCount; ++i) {
+            uint32_t value = data[i];
+            if (value) {  // There are set bits
+                unsigned int index = i * 32;
+                for (unsigned int j = 0; j < 32; ++j) {
+                    if (0x1 & (value >> j)) {
+                        array->push(index + j);
+                    }
+                }
+            }
+        }
+    }
+
+private:
+    SkAutoFree fBitData;
+    // Dword (32-bit) count of the bitset.
+    size_t fDwordCount;
+    size_t fBitCount;
+
+    uint32_t* internalGet(int index) const {
+        SkASSERT((size_t)index < fBitCount);
+        size_t internalIndex = index / 32;
+        SkASSERT(internalIndex < fDwordCount);
+        return reinterpret_cast<uint32_t*>(fBitData.get()) + internalIndex;
+    }
+};
+
+
+#endif