michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- michael@0: * vim: set ts=8 sts=4 et sw=4 tw=99: michael@0: * This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: #ifndef jit_BitSet_h michael@0: #define jit_BitSet_h michael@0: michael@0: #include "mozilla/MathAlgorithms.h" michael@0: michael@0: #include "jit/IonAllocPolicy.h" michael@0: michael@0: namespace js { michael@0: namespace jit { michael@0: michael@0: // Provides constant time set insertion and removal, and fast linear michael@0: // set operations such as intersection, difference, and union. michael@0: // N.B. All set operations must be performed on sets with the same number michael@0: // of bits. michael@0: class BitSet : private TempObject michael@0: { michael@0: public: michael@0: static const size_t BitsPerWord = 8 * sizeof(uint32_t); michael@0: michael@0: static size_t RawLengthForBits(size_t bits) { michael@0: return (bits + BitsPerWord - 1) / BitsPerWord; michael@0: } michael@0: michael@0: private: michael@0: BitSet(unsigned int numBits) : michael@0: bits_(nullptr), michael@0: numBits_(numBits) {} michael@0: michael@0: uint32_t *bits_; michael@0: const unsigned int numBits_; michael@0: michael@0: static inline uint32_t bitForValue(unsigned int value) { michael@0: return 1l << uint32_t(value % BitsPerWord); michael@0: } michael@0: michael@0: static inline unsigned int wordForValue(unsigned int value) { michael@0: return value / BitsPerWord; michael@0: } michael@0: michael@0: inline unsigned int numWords() const { michael@0: return RawLengthForBits(numBits_); michael@0: } michael@0: michael@0: bool init(TempAllocator &alloc); michael@0: michael@0: public: michael@0: class Iterator; michael@0: michael@0: static BitSet *New(TempAllocator &alloc, unsigned int numBits); michael@0: michael@0: unsigned int getNumBits() const { michael@0: return numBits_; michael@0: } michael@0: michael@0: // O(1): Check if this set contains the given value. michael@0: bool contains(unsigned int value) const { michael@0: JS_ASSERT(bits_); michael@0: JS_ASSERT(value < numBits_); michael@0: michael@0: return !!(bits_[wordForValue(value)] & bitForValue(value)); michael@0: } michael@0: michael@0: // O(numBits): Check if this set contains any value. michael@0: bool empty() const; michael@0: michael@0: // O(1): Insert the given value into this set. michael@0: void insert(unsigned int value) { michael@0: JS_ASSERT(bits_); michael@0: JS_ASSERT(value < numBits_); michael@0: michael@0: bits_[wordForValue(value)] |= bitForValue(value); michael@0: } michael@0: michael@0: // O(numBits): Insert every element of the given set into this set. michael@0: void insertAll(const BitSet *other); michael@0: michael@0: // O(1): Remove the given value from this set. michael@0: void remove(unsigned int value) { michael@0: JS_ASSERT(bits_); michael@0: JS_ASSERT(value < numBits_); michael@0: michael@0: bits_[wordForValue(value)] &= ~bitForValue(value); michael@0: } michael@0: michael@0: // O(numBits): Remove the every element of the given set from this set. michael@0: void removeAll(const BitSet *other); michael@0: michael@0: // O(numBits): Intersect this set with the given set. michael@0: void intersect(const BitSet *other); michael@0: michael@0: // O(numBits): Intersect this set with the given set; return whether the michael@0: // intersection caused the set to change. michael@0: bool fixedPointIntersect(const BitSet *other); michael@0: michael@0: // O(numBits): Does inplace complement of the set. michael@0: void complement(); michael@0: michael@0: // O(numBits): Clear this set. michael@0: void clear(); michael@0: michael@0: uint32_t *raw() const { michael@0: return bits_; michael@0: } michael@0: size_t rawLength() const { michael@0: return numWords(); michael@0: } michael@0: }; michael@0: michael@0: class BitSet::Iterator michael@0: { michael@0: private: michael@0: BitSet &set_; michael@0: unsigned index_; michael@0: unsigned word_; michael@0: uint32_t value_; michael@0: michael@0: void skipEmpty() { michael@0: // Skip words containing only zeros. michael@0: unsigned numWords = set_.numWords(); michael@0: const uint32_t *bits = set_.bits_; michael@0: while (value_ == 0) { michael@0: word_++; michael@0: if (word_ == numWords) michael@0: return; michael@0: michael@0: JS_STATIC_ASSERT(sizeof(value_) * 8 == BitSet::BitsPerWord); michael@0: index_ = word_ * sizeof(value_) * 8; michael@0: value_ = bits[word_]; michael@0: } michael@0: michael@0: // Be careful: the result of CountTrailingZeroes32 is undefined if the michael@0: // input is 0. michael@0: int numZeros = mozilla::CountTrailingZeroes32(value_); michael@0: index_ += numZeros; michael@0: value_ >>= numZeros; michael@0: michael@0: JS_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_)); michael@0: } michael@0: michael@0: public: michael@0: Iterator(BitSet &set) : michael@0: set_(set), michael@0: index_(0), michael@0: word_(0), michael@0: value_(set.bits_[0]) michael@0: { michael@0: skipEmpty(); michael@0: } michael@0: michael@0: inline bool more() const { michael@0: return word_ < set_.numWords(); michael@0: } michael@0: inline operator bool() const { michael@0: return more(); michael@0: } michael@0: michael@0: inline Iterator& operator++(int dummy) { michael@0: JS_ASSERT(more()); michael@0: JS_ASSERT(index_ < set_.numBits_); michael@0: michael@0: index_++; michael@0: value_ >>= 1; michael@0: michael@0: skipEmpty(); michael@0: return *this; michael@0: } michael@0: michael@0: unsigned int operator *() { michael@0: JS_ASSERT(index_ < set_.numBits_); michael@0: return index_; michael@0: } michael@0: }; michael@0: michael@0: } michael@0: } michael@0: michael@0: #endif /* jit_BitSet_h */