blob: a60f668264d3d4d39cfcf390d372c75043e17b4c [file] [log] [blame]
// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#ifndef VM_BIT_SET_H_
#define VM_BIT_SET_H_
#include "platform/utils.h"
#include "vm/globals.h"
namespace dart {
// Just like its namesake in the STL, a BitSet object contains a fixed
// length sequence of bits.
template<intptr_t N>
class BitSet {
public:
BitSet() {
Reset();
}
void Set(intptr_t i, bool value) {
ASSERT(i >= 0);
ASSERT(i < N);
uword mask = (static_cast<uword>(1) << (i & (kBitsPerWord - 1)));
if (value) {
data_[i >> kBitsPerWordLog2] |= mask;
} else {
data_[i >> kBitsPerWordLog2] &= ~mask;
}
}
bool Test(intptr_t i) const {
ASSERT(i >= 0);
ASSERT(i < N);
uword mask = (static_cast<uword>(1) << (i & (kBitsPerWord - 1)));
return (data_[i >> kBitsPerWordLog2] & mask) != 0;
}
intptr_t Next(intptr_t i) const {
ASSERT(i >= 0);
ASSERT(i < N);
intptr_t w = i >> kBitsPerWordLog2;
uword mask = ~static_cast<uword>(0) << (i & (kBitsPerWord - 1));
if ((data_[w] & mask) != 0) {
uword tz = Utils::CountTrailingZeros(data_[w] & mask);
return (w << kBitsPerWordLog2) + tz;
}
while (++w < kLengthInWords) {
if (data_[w] != 0) {
return (w << kBitsPerWordLog2) + Utils::CountTrailingZeros(data_[w]);
}
}
return -1;
}
intptr_t Last() const {
for (int w = kLengthInWords - 1; w >= 0; --w) {
uword d = data_[w];
if (d != 0) {
return ((w + 1) << kBitsPerWordLog2) - Utils::CountLeadingZeros(d) - 1;
}
}
return -1;
}
intptr_t ClearLastAndFindPrevious(intptr_t current_last) {
ASSERT(Test(current_last));
ASSERT(Last() == current_last);
intptr_t w = current_last >> kBitsPerWordLog2;
uword bits = data_[w];
// Clear the current last.
bits ^= (static_cast<uword>(1) << (current_last & (kBitsPerWord - 1)));
data_[w] = bits;
// Search backwards for a non-zero word.
while (bits == 0 && w > 0) {
bits = data_[--w];
}
if (bits == 0) {
// None found.
return -1;
} else {
// Bitlength incl. w, minus leading zeroes of w, minus 1 to 0-based index.
return ((w + 1) << kBitsPerWordLog2) - Utils::CountLeadingZeros(bits) - 1;
}
}
void Reset() {
memset(data_, 0, sizeof(data_));
}
intptr_t Size() const {
return N;
}
private:
static const int kLengthInWords = 1 + ((N - 1) / kBitsPerWord);
uword data_[kLengthInWords];
};
} // namespace dart
#endif // VM_BIT_SET_H_