/* -*- 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 */
