1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jit/BitSet.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,183 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef jit_BitSet_h
1.11 +#define jit_BitSet_h
1.12 +
1.13 +#include "mozilla/MathAlgorithms.h"
1.14 +
1.15 +#include "jit/IonAllocPolicy.h"
1.16 +
1.17 +namespace js {
1.18 +namespace jit {
1.19 +
1.20 +// Provides constant time set insertion and removal, and fast linear
1.21 +// set operations such as intersection, difference, and union.
1.22 +// N.B. All set operations must be performed on sets with the same number
1.23 +// of bits.
1.24 +class BitSet : private TempObject
1.25 +{
1.26 + public:
1.27 + static const size_t BitsPerWord = 8 * sizeof(uint32_t);
1.28 +
1.29 + static size_t RawLengthForBits(size_t bits) {
1.30 + return (bits + BitsPerWord - 1) / BitsPerWord;
1.31 + }
1.32 +
1.33 + private:
1.34 + BitSet(unsigned int numBits) :
1.35 + bits_(nullptr),
1.36 + numBits_(numBits) {}
1.37 +
1.38 + uint32_t *bits_;
1.39 + const unsigned int numBits_;
1.40 +
1.41 + static inline uint32_t bitForValue(unsigned int value) {
1.42 + return 1l << uint32_t(value % BitsPerWord);
1.43 + }
1.44 +
1.45 + static inline unsigned int wordForValue(unsigned int value) {
1.46 + return value / BitsPerWord;
1.47 + }
1.48 +
1.49 + inline unsigned int numWords() const {
1.50 + return RawLengthForBits(numBits_);
1.51 + }
1.52 +
1.53 + bool init(TempAllocator &alloc);
1.54 +
1.55 + public:
1.56 + class Iterator;
1.57 +
1.58 + static BitSet *New(TempAllocator &alloc, unsigned int numBits);
1.59 +
1.60 + unsigned int getNumBits() const {
1.61 + return numBits_;
1.62 + }
1.63 +
1.64 + // O(1): Check if this set contains the given value.
1.65 + bool contains(unsigned int value) const {
1.66 + JS_ASSERT(bits_);
1.67 + JS_ASSERT(value < numBits_);
1.68 +
1.69 + return !!(bits_[wordForValue(value)] & bitForValue(value));
1.70 + }
1.71 +
1.72 + // O(numBits): Check if this set contains any value.
1.73 + bool empty() const;
1.74 +
1.75 + // O(1): Insert the given value into this set.
1.76 + void insert(unsigned int value) {
1.77 + JS_ASSERT(bits_);
1.78 + JS_ASSERT(value < numBits_);
1.79 +
1.80 + bits_[wordForValue(value)] |= bitForValue(value);
1.81 + }
1.82 +
1.83 + // O(numBits): Insert every element of the given set into this set.
1.84 + void insertAll(const BitSet *other);
1.85 +
1.86 + // O(1): Remove the given value from this set.
1.87 + void remove(unsigned int value) {
1.88 + JS_ASSERT(bits_);
1.89 + JS_ASSERT(value < numBits_);
1.90 +
1.91 + bits_[wordForValue(value)] &= ~bitForValue(value);
1.92 + }
1.93 +
1.94 + // O(numBits): Remove the every element of the given set from this set.
1.95 + void removeAll(const BitSet *other);
1.96 +
1.97 + // O(numBits): Intersect this set with the given set.
1.98 + void intersect(const BitSet *other);
1.99 +
1.100 + // O(numBits): Intersect this set with the given set; return whether the
1.101 + // intersection caused the set to change.
1.102 + bool fixedPointIntersect(const BitSet *other);
1.103 +
1.104 + // O(numBits): Does inplace complement of the set.
1.105 + void complement();
1.106 +
1.107 + // O(numBits): Clear this set.
1.108 + void clear();
1.109 +
1.110 + uint32_t *raw() const {
1.111 + return bits_;
1.112 + }
1.113 + size_t rawLength() const {
1.114 + return numWords();
1.115 + }
1.116 +};
1.117 +
1.118 +class BitSet::Iterator
1.119 +{
1.120 + private:
1.121 + BitSet &set_;
1.122 + unsigned index_;
1.123 + unsigned word_;
1.124 + uint32_t value_;
1.125 +
1.126 + void skipEmpty() {
1.127 + // Skip words containing only zeros.
1.128 + unsigned numWords = set_.numWords();
1.129 + const uint32_t *bits = set_.bits_;
1.130 + while (value_ == 0) {
1.131 + word_++;
1.132 + if (word_ == numWords)
1.133 + return;
1.134 +
1.135 + JS_STATIC_ASSERT(sizeof(value_) * 8 == BitSet::BitsPerWord);
1.136 + index_ = word_ * sizeof(value_) * 8;
1.137 + value_ = bits[word_];
1.138 + }
1.139 +
1.140 + // Be careful: the result of CountTrailingZeroes32 is undefined if the
1.141 + // input is 0.
1.142 + int numZeros = mozilla::CountTrailingZeroes32(value_);
1.143 + index_ += numZeros;
1.144 + value_ >>= numZeros;
1.145 +
1.146 + JS_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_));
1.147 + }
1.148 +
1.149 + public:
1.150 + Iterator(BitSet &set) :
1.151 + set_(set),
1.152 + index_(0),
1.153 + word_(0),
1.154 + value_(set.bits_[0])
1.155 + {
1.156 + skipEmpty();
1.157 + }
1.158 +
1.159 + inline bool more() const {
1.160 + return word_ < set_.numWords();
1.161 + }
1.162 + inline operator bool() const {
1.163 + return more();
1.164 + }
1.165 +
1.166 + inline Iterator& operator++(int dummy) {
1.167 + JS_ASSERT(more());
1.168 + JS_ASSERT(index_ < set_.numBits_);
1.169 +
1.170 + index_++;
1.171 + value_ >>= 1;
1.172 +
1.173 + skipEmpty();
1.174 + return *this;
1.175 + }
1.176 +
1.177 + unsigned int operator *() {
1.178 + JS_ASSERT(index_ < set_.numBits_);
1.179 + return index_;
1.180 + }
1.181 +};
1.182 +
1.183 +}
1.184 +}
1.185 +
1.186 +#endif /* jit_BitSet_h */
