diff options
author | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
---|---|---|
committer | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
commit | 5f8de423f190bbb79a62f804151bc24824fa32d8 (patch) | |
tree | 10027f336435511475e392454359edea8e25895d /js/src/jit/BitSet.h | |
parent | 49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff) | |
download | UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip |
Add m-esr52 at 52.6.0
Diffstat (limited to 'js/src/jit/BitSet.h')
-rw-r--r-- | js/src/jit/BitSet.h | 182 |
1 files changed, 182 insertions, 0 deletions
diff --git a/js/src/jit/BitSet.h b/js/src/jit/BitSet.h new file mode 100644 index 000000000..99541edb8 --- /dev/null +++ b/js/src/jit/BitSet.h @@ -0,0 +1,182 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sts=4 et sw=4 tw=99: + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#ifndef jit_BitSet_h +#define jit_BitSet_h + +#include "mozilla/MathAlgorithms.h" + +#include "jit/JitAllocPolicy.h" + +namespace js { +namespace jit { + +// Provides constant time set insertion and removal, and fast linear +// set operations such as intersection, difference, and union. +// N.B. All set operations must be performed on sets with the same number +// of bits. +class BitSet +{ + public: + static const size_t BitsPerWord = 8 * sizeof(uint32_t); + + static size_t RawLengthForBits(size_t bits) { + return (bits + BitsPerWord - 1) / BitsPerWord; + } + + private: + uint32_t* bits_; + const unsigned int numBits_; + + static inline uint32_t bitForValue(unsigned int value) { + return 1l << uint32_t(value % BitsPerWord); + } + + static inline unsigned int wordForValue(unsigned int value) { + return value / BitsPerWord; + } + + inline unsigned int numWords() const { + return RawLengthForBits(numBits_); + } + + BitSet(const BitSet&) = delete; + void operator=(const BitSet&) = delete; + + public: + class Iterator; + + explicit BitSet(unsigned int numBits) : + bits_(nullptr), + numBits_(numBits) {} + + MOZ_MUST_USE bool init(TempAllocator& alloc); + + unsigned int getNumBits() const { + return numBits_; + } + + // O(1): Check if this set contains the given value. + bool contains(unsigned int value) const { + MOZ_ASSERT(bits_); + MOZ_ASSERT(value < numBits_); + + return !!(bits_[wordForValue(value)] & bitForValue(value)); + } + + // O(numBits): Check if this set contains any value. + bool empty() const; + + // O(1): Insert the given value into this set. + void insert(unsigned int value) { + MOZ_ASSERT(bits_); + MOZ_ASSERT(value < numBits_); + + bits_[wordForValue(value)] |= bitForValue(value); + } + + // O(numBits): Insert every element of the given set into this set. + void insertAll(const BitSet& other); + + // O(1): Remove the given value from this set. + void remove(unsigned int value) { + MOZ_ASSERT(bits_); + MOZ_ASSERT(value < numBits_); + + bits_[wordForValue(value)] &= ~bitForValue(value); + } + + // O(numBits): Remove the every element of the given set from this set. + void removeAll(const BitSet& other); + + // O(numBits): Intersect this set with the given set. + void intersect(const BitSet& other); + + // O(numBits): Intersect this set with the given set; return whether the + // intersection caused the set to change. + bool fixedPointIntersect(const BitSet& other); + + // O(numBits): Does inplace complement of the set. + void complement(); + + // O(numBits): Clear this set. + void clear(); + + uint32_t* raw() const { + return bits_; + } + size_t rawLength() const { + return numWords(); + } +}; + +class BitSet::Iterator +{ + private: + BitSet& set_; + unsigned index_; + unsigned word_; + uint32_t value_; + + void skipEmpty() { + // Skip words containing only zeros. + unsigned numWords = set_.numWords(); + const uint32_t* bits = set_.bits_; + while (value_ == 0) { + word_++; + if (word_ == numWords) + return; + + index_ = word_ * BitSet::BitsPerWord; + value_ = bits[word_]; + } + + // Be careful: the result of CountTrailingZeroes32 is undefined if the + // input is 0. + int numZeros = mozilla::CountTrailingZeroes32(value_); + index_ += numZeros; + value_ >>= numZeros; + + MOZ_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_)); + } + + public: + explicit Iterator(BitSet& set) : + set_(set), + index_(0), + word_(0), + value_(set.bits_[0]) + { + skipEmpty(); + } + + inline bool more() const { + return word_ < set_.numWords(); + } + explicit operator bool() const { + return more(); + } + + inline void operator++() { + MOZ_ASSERT(more()); + MOZ_ASSERT(index_ < set_.numBits_); + + index_++; + value_ >>= 1; + + skipEmpty(); + } + + unsigned int operator*() { + MOZ_ASSERT(index_ < set_.numBits_); + return index_; + } +}; + +} // namespace jit +} // namespace js + +#endif /* jit_BitSet_h */ |