2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
19 #include <hphp/util/assertions.h>
27 friend struct BitsetArray
;
28 friend struct BitsetWrapper
;
30 const BitsetRef
& operator=(const BitsetRef
&) = delete;
32 size_t size() const { return (e
- s
) * bits_per_word
; }
34 friend bool operator==(const BitsetRef
& o1
, const BitsetRef
& o2
) {
38 if (*p1
!= *p2
) return false;
46 friend bool operator!=(const BitsetRef
& o1
, const BitsetRef
& o2
) {
50 friend BitsetWrapper
operator|(const BitsetRef
& o1
, const BitsetRef
& o2
);
51 friend BitsetWrapper
operator&(const BitsetRef
& o1
, const BitsetRef
& o2
);
52 friend BitsetWrapper
operator-(const BitsetRef
& o1
, const BitsetRef
& o2
);
54 BitsetRef
& operator|=(const BitsetRef
& o
) {
56 [](uint64_t* dst
, const uint64_t *src
) {
61 BitsetRef
& operator&=(const BitsetRef
& o
) {
63 [](uint64_t* dst
, const uint64_t *src
) {
68 BitsetRef
& operator-=(const BitsetRef
& o
) {
70 [](uint64_t* dst
, const uint64_t *src
) {
76 void assign(const BitsetRef
& o
) {
78 [](uint64_t* dst
, const uint64_t *src
) {
83 void assign_add(const BitsetRef
& o1
, const BitsetRef
& o2
) {
85 [](uint64_t* dst
, const uint64_t *src1
, const uint64_t *src2
) {
90 void assign_sub(const BitsetRef
& o1
, const BitsetRef
& o2
) {
92 [](uint64_t* dst
, const uint64_t *src1
, const uint64_t *src2
) {
93 *dst
= *src1
& ~*src2
;
97 void assign_and(const BitsetRef
& o1
, const BitsetRef
& o2
) {
99 [](uint64_t* dst
, const uint64_t *src1
, const uint64_t *src2
) {
100 *dst
= *src1
& *src2
;
104 BitsetRef
next(int n
= 1) const {
105 return BitsetRef
{ s
+ (e
- s
) * n
, e
+ (e
- s
) * n
};
108 BitsetRef
prev(int n
= 1) const {
109 return BitsetRef
{ s
- (e
- s
) * n
, e
- (e
- s
) * n
};
112 bool operator[](size_t bit
) const { return test(bit
); }
113 bool test(size_t bit
) const {
114 auto idx
= bit
/ bits_per_word
;
115 auto pos
= bit
- (idx
* bits_per_word
);
117 assert(idx
< (e
- s
));
118 return (s
[idx
] >> pos
) & 1;
121 void reset(size_t bit
) {
122 auto idx
= bit
/ bits_per_word
;
123 auto pos
= bit
- (idx
* bits_per_word
);
125 assert(idx
< (e
- s
));
126 s
[idx
] &= ~(ElemType
{1} << pos
);
130 for (auto p
= s
; p
!= e
; ++p
) *p
= 0;
133 void set(size_t bit
) {
134 auto idx
= bit
/ bits_per_word
;
135 auto pos
= bit
- (idx
* bits_per_word
);
137 assert(idx
< (e
- s
));
138 s
[idx
] |= ElemType
{1} << pos
;
142 for (auto p
= s
; p
!= e
; ++p
) *p
= ~ElemType
{};
146 for (auto p
= s
; p
!= e
; ++p
) if (*p
) return true;
150 bool none() const { return !any(); }
152 using ElemType
= uint64_t;
153 static constexpr auto bits_per_word
= std::numeric_limits
<ElemType
>::digits
;
155 BitsetRef(ElemType
* s
, ElemType
* e
) : s
{s
}, e
{e
} {}
156 size_t words() const { return e
- s
; }
158 template <typename F
>
159 void perform(const BitsetRef
& o
, F
&& f
) {
170 template <typename F
>
171 void perform(const BitsetRef
& o1
, const BitsetRef
& o2
, F
&& f
) {
181 assert(src1
== o1
.e
);
182 assert(src2
== o2
.e
);
189 struct BitsetWrapper
: BitsetRef
{
190 BitsetWrapper(BitsetWrapper
&& o
) : BitsetRef
{o
.s
, o
.e
} {
193 ~BitsetWrapper() { delete [] s
; }
195 friend BitsetWrapper
operator|(const BitsetRef
& o1
, const BitsetRef
& o2
) {
196 BitsetWrapper r
{o1
.words()};
197 r
.assign_add(o1
, o2
);
201 friend BitsetWrapper
operator&(const BitsetRef
& o1
, const BitsetRef
& o2
) {
202 BitsetWrapper r
{o1
.words()};
203 r
.assign_and(o1
, o2
);
207 friend BitsetWrapper
operator-(const BitsetRef
& o1
, const BitsetRef
& o2
) {
208 BitsetWrapper r
{o1
.words()};
209 r
.assign_sub(o1
, o2
);
215 BitsetWrapper(size_t words
) : BitsetRef
{nullptr, nullptr} {
216 s
= new uint64_t[words
];
222 BitsetArray(size_t rows
, size_t bits
) : m_rows
{rows
}, m_rowData
{nullptr} {
224 (bits
+ BitsetRef::bits_per_word
- 1) / BitsetRef::bits_per_word
;
225 auto const words
= m_rowElems
* rows
;
226 m_rowData
= new uint64_t[words
];
227 memset(m_rowData
, 0, words
* sizeof(*m_rowData
));
230 BitsetRef
row(size_t r
) {
232 auto const s
= m_rowData
+ r
* m_rowElems
;
233 return BitsetRef
{ s
, s
+ m_rowElems
};
236 const BitsetRef
row(size_t r
) const {
238 auto const s
= m_rowData
+ r
* m_rowElems
;
239 return BitsetRef
{ s
, s
+ m_rowElems
};
242 ~BitsetArray() { delete [] m_rowData
; }
246 BitsetRef::ElemType
* m_rowData
;