1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_BIT_SET_H_
6#define RUNTIME_VM_BIT_SET_H_
7
8#include "platform/utils.h"
9#include "vm/globals.h"
10
11namespace dart {
12
13// Just like its namesake in the STL, a BitSet object contains a fixed
14// length sequence of bits.
15template <intptr_t N>
16class BitSet {
17 public:
18 BitSet() { Reset(); }
19
20 void Set(intptr_t i, bool value) {
21 ASSERT(i >= 0);
22 ASSERT(i < N);
23 uword mask = (static_cast<uword>(1) << (i & (kBitsPerWord - 1)));
24 if (value) {
25 data_[i >> kBitsPerWordLog2] |= mask;
26 } else {
27 data_[i >> kBitsPerWordLog2] &= ~mask;
28 }
29 }
30
31 bool Test(intptr_t i) const {
32 ASSERT(i >= 0);
33 ASSERT(i < N);
34 uword mask = (static_cast<uword>(1) << (i & (kBitsPerWord - 1)));
35 return (data_[i >> kBitsPerWordLog2] & mask) != 0;
36 }
37
38 intptr_t Next(intptr_t i) const {
39 ASSERT(i >= 0);
40 ASSERT(i < N);
41 intptr_t w = i >> kBitsPerWordLog2;
42 uword mask = ~static_cast<uword>(0) << (i & (kBitsPerWord - 1));
43 if ((data_[w] & mask) != 0) {
44 uword tz = Utils::CountTrailingZerosWord(data_[w] & mask);
45 return (w << kBitsPerWordLog2) + tz;
46 }
47 while (++w < kLengthInWords) {
48 if (data_[w] != 0) {
49 return (w << kBitsPerWordLog2) +
50 Utils::CountTrailingZerosWord(data_[w]);
51 }
52 }
53 return -1;
54 }
55
56 intptr_t Last() const {
57 for (int w = kLengthInWords - 1; w >= 0; --w) {
58 uword d = data_[w];
59 if (d != 0) {
60 return ((w + 1) << kBitsPerWordLog2) - Utils::CountLeadingZerosWord(d) -
61 1;
62 }
63 }
64 return -1;
65 }
66
67 intptr_t ClearLastAndFindPrevious(intptr_t current_last) {
68 ASSERT(Test(current_last));
69 ASSERT(Last() == current_last);
70 intptr_t w = current_last >> kBitsPerWordLog2;
71 uword bits = data_[w];
72 // Clear the current last.
73 bits ^= (static_cast<uword>(1) << (current_last & (kBitsPerWord - 1)));
74 data_[w] = bits;
75 // Search backwards for a non-zero word.
76 while (bits == 0 && w > 0) {
77 bits = data_[--w];
78 }
79 if (bits == 0) {
80 // None found.
81 return -1;
82 } else {
83 // Bitlength incl. w, minus leading zeroes of w, minus 1 to 0-based index.
84 return ((w + 1) << kBitsPerWordLog2) -
85 Utils::CountLeadingZerosWord(bits) - 1;
86 }
87 }
88
89 void Reset() { memset(data_, 0, sizeof(data_)); }
90
91 intptr_t Size() const { return N; }
92
93 private:
94 static const int kLengthInWords = 1 + ((N - 1) / kBitsPerWord);
95 uword data_[kLengthInWords];
96};
97
98} // namespace dart
99
100#endif // RUNTIME_VM_BIT_SET_H_
101