diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 17:32:43 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 17:32:43 +0000 |
commit | 6bf0a5cb5034a7e684dcc3500e841785237ce2dd (patch) | |
tree | a68f146d7fa01f0134297619fbe7e33db084e0aa /js/src/jit/BitSet.h | |
parent | Initial commit. (diff) | |
download | thunderbird-6bf0a5cb5034a7e684dcc3500e841785237ce2dd.tar.xz thunderbird-6bf0a5cb5034a7e684dcc3500e841785237ce2dd.zip |
Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | js/src/jit/BitSet.h | 167 |
1 files changed, 167 insertions, 0 deletions
diff --git a/js/src/jit/BitSet.h b/js/src/jit/BitSet.h new file mode 100644 index 0000000000..4e34b1ecb1 --- /dev/null +++ b/js/src/jit/BitSet.h @@ -0,0 +1,167 @@ +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- + * vim: set ts=8 sts=2 et sw=2 tw=80: + * 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/Assertions.h" +#include "mozilla/MathAlgorithms.h" + +#include <stddef.h> +#include <stdint.h> + +namespace js { +namespace jit { + +class TempAllocator; + +// 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) {} + + [[nodiscard]] 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 */ |