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/runtime/base/memory-manager.h"
20 #include "hphp/runtime/vm/jit/ir-unit.h"
24 //////////////////////////////////////////////////////////////////////
27 * IdSet implements a bitset over the range of Key's ids, optimized for
28 * a relatively low number of bits. If we only need one word of storage,
29 * this doesn't allocate any extra memory. Otherwise allocate an array
34 IdSet() : m_bits
{0}, m_cap
{0}, m_base
{0} {}
36 explicit IdSet(const Key
* k
) : IdSet() { add(k
); }
37 explicit IdSet(const Key
& k
) : IdSet() { add(k
); }
39 IdSet(const IdSet
& o
) {
47 // "Trim" the other set by finding the first and last block index
48 // with bits set. These are the only blocks we actually need to
49 // copy. This avoids expanding the current set by more than
53 auto foundBegin
= false;
54 for (size_t i
= 0; i
< o
.m_cap
; ++i
) {
55 if (!o
.m_bitsptr
[i
]) continue;
64 // Other set is empty, so we are as well.
68 } else if (begin
+ 1 == end
) {
69 // Other set has just a single block, so we can avoid allocating
72 m_base
= begin
* kBlockSize
+ o
.m_base
;
73 m_bits
= o
.m_bitsptr
[begin
];
75 // Otherwise we need to allocate and copy.
77 m_base
= begin
* kBlockSize
+ o
.m_base
;
78 m_bitsptr
= (uint64_t*)malloc(m_cap
* sizeof(uint64_t));
79 for (size_t i
= begin
; i
< end
; ++i
) {
80 m_bitsptr
[i
- begin
] = o
.m_bitsptr
[i
];
85 IdSet(IdSet
&& o
) noexcept
95 IdSet
& operator=(const IdSet
& o
) {
96 if (this == &o
) return *this;
100 // "Trim" the other set by finding the first and last block index
101 // with bits set. These are the only blocks we actually need to
102 // copy. This avoids expanding the current set by more than
106 auto foundBegin
= false;
107 for (size_t i
= 0; i
< o
.m_cap
; ++i
) {
108 if (!b2
[i
]) continue;
117 // Other set is actually empty. Just clear our bits.
122 // Ensure we have enough space.
124 resize(begin
* kBlockSize
+ o
.m_base
, end
* kBlockSize
+ o
.m_base
);
126 assertx(m_base
<= (begin
* kBlockSize
+ o
.m_base
));
127 assertx((m_cap
* kBlockSize
+ m_base
) >= (end
* kBlockSize
+ o
.m_base
));
129 auto const prefix
= (o
.m_base
/ kBlockSize
+ begin
) - m_base
/ kBlockSize
;
130 for (size_t i
= 0; i
< prefix
; ++i
) b1
[i
] = 0;
131 for (size_t i
= begin
; i
< end
; ++i
) b1
[i
- begin
+ prefix
] = b2
[i
];
132 for (size_t i
= end
- begin
+ prefix
; i
< m_cap
; ++i
) b1
[i
] = 0;
137 IdSet
& operator=(IdSet
&& other
) noexcept
{
143 if (m_cap
> 1) free(m_bitsptr
);
147 void add(uint32_t id
) {
148 auto ptr
= resize(id
, id
+ 1);
149 assertx(id
>= m_base
&&
150 id
< ((m_cap
* kBlockSize
) + m_base
));
151 bitvec_set(ptr
, id
- m_base
);
153 void add(const Key
* k
) { add(k
->id()); }
154 void add(const Key
& k
) { add(k
.id()); }
157 void erase(uint32_t id
) {
158 if (id
< m_base
|| id
>= ((m_cap
* kBlockSize
) + m_base
)) return;
159 bitvec_clear(bits(), id
- m_base
);
161 void erase(const Key
* k
) { erase(k
->id()); }
162 void erase(const Key
& k
) { erase(k
.id()); }
167 for (size_t i
= 0; i
< m_cap
; ++i
) b
[i
] = 0;
170 // Union another IdSet with this
171 void operator|=(const IdSet
& o
) {
172 if (this == &o
) return;
176 // "Trim" the other set by finding the first and last block index
177 // with bits set. These are the only blocks we actually need to
178 // copy. This avoids expanding the current set by more than
182 auto foundBegin
= false;
183 for (size_t i
= 0; i
< o
.m_cap
; ++i
) {
184 if (!b2
[i
]) continue;
192 // Other set is actually empty
193 if (begin
== end
) return;
195 // Resize and do actual union
197 resize(begin
* kBlockSize
+ o
.m_base
, end
* kBlockSize
+ o
.m_base
);
199 assertx(m_base
<= (begin
* kBlockSize
+ o
.m_base
));
200 assertx((m_cap
* kBlockSize
+ m_base
) >= (end
* kBlockSize
+ o
.m_base
));
202 auto const prefix
= (o
.m_base
/ kBlockSize
+ begin
) - m_base
/ kBlockSize
;
203 for (size_t i
= begin
; i
< end
; ++i
) b1
[i
- begin
+ prefix
] |= b2
[i
];
206 void swap(IdSet
& o
) noexcept
{
208 swap(m_bits
, o
.m_bits
);
209 swap(m_cap
, o
.m_cap
);
210 swap(m_base
, o
.m_base
);
213 // Check if a specific id is present.
214 bool operator[](uint32_t id
) const {
217 id
< ((m_cap
* kBlockSize
) + m_base
) &&
218 bitvec_test(bits(), id
- m_base
);
220 bool operator[](const Key
& k
) const { return (*this)[k
.id()]; }
221 bool operator[](const Key
* k
) const { return (*this)[k
->id()]; }
223 // Check if no ids are present.
225 if (LIKELY(m_cap
<= 1)) return !m_bits
;
226 for (size_t i
= 0; i
< m_cap
; ++i
) {
227 if (m_bitsptr
[i
] != 0) return false;
232 // Invoke f(id) for each id present
233 template <class Fun
> void forEach(Fun f
) const {
235 for (size_t i
= 0, n
= m_cap
; i
< n
; ++i
) {
236 uint64_t word
= b
[i
];
238 while (ffs64(word
, out
)) {
239 assertx(0 <= out
&& out
< 64);
240 word
&= ~(uint64_t{1} << out
);
241 f(i
* kBlockSize
+ out
+ m_base
);
246 static const constexpr size_t kBlockSize
= 64;
249 uint64_t* bits() { return m_cap
> 1 ? m_bitsptr
: &m_bits
; }
250 const uint64_t* bits() const { return m_cap
> 1 ? m_bitsptr
: &m_bits
; }
252 // Ensure that this bitset has enough storage to represent all bits
253 // between [min and max), returning the proper storage. The new bits
254 // will be initialized to zero.
255 uint64_t* resize(uint32_t min
, uint32_t max
) {
259 // Common case: everything already fits
260 if (min
>= m_base
&& max
<= (m_cap
* kBlockSize
+ m_base
)) return bits();
262 // Calculate the new base and capacity
263 auto const roundedMin
= min
- (min
% kBlockSize
);
265 (m_cap
> 0) ? std::min
<uint32_t>(roundedMin
, m_base
) : roundedMin
;
266 auto const newMax
= std::max
<uint32_t>(max
, m_cap
* kBlockSize
+ m_base
);
268 ((newMax
+ kBlockSize
- 1) / kBlockSize
) - (base
/ kBlockSize
);
270 // The common case check should have already caught the case where
271 // we don't need to expand.
272 assertx(cap
> m_cap
);
274 // We've gone from empty to a single block. Just initialize the
278 // Otherwise we need to allocate memory off the heap.
279 auto const prefix
= (m_cap
> 0)
280 ? (m_base
/ kBlockSize
- base
/ kBlockSize
)
283 if (m_cap
<= 1 || prefix
> 0) {
284 // Allocate new memory, and copy the existing bits over to
285 // it. Initialize the new prefix and new suffix to zero.
286 auto ptr
= (uint64_t*)malloc(cap
* sizeof(uint64_t));
288 auto oldbits
= bits();
289 auto const copy
= prefix
+ m_cap
;
290 for (size_t i
= 0; i
< prefix
; ++i
) ptr
[i
] = 0;
291 for (size_t i
= prefix
; i
< copy
; ++i
) ptr
[i
] = oldbits
[i
- prefix
];
292 for (size_t i
= copy
; i
< cap
; ++i
) ptr
[i
] = 0;
294 if (m_cap
> 1) free(m_bitsptr
);
297 // If we already have heap allocated storage, and we're not
298 // expanding the front, we can use realloc.
299 m_bitsptr
= (uint64_t*)realloc(m_bitsptr
, cap
* sizeof(uint64_t));
300 for (size_t i
= m_cap
; i
< cap
; ++i
) m_bitsptr
[i
] = 0;
304 assertx(base
% kBlockSize
== 0);
311 // Storage. If the bits fit in a single word, we use m_bits,
312 // m_bitsptr pointing to malloced memory otherwise.
317 // Number of allocated blocks. If <= 1, then m_bits is active,
318 // m_bitsptr otherwise.
320 // Logical start index of the bits. This lets us avoid allocating
321 // memory if the ids are clustered but not near zero. Must be a
322 // multiple of kBlockSize.
326 //////////////////////////////////////////////////////////////////////
329 void swap(IdSet
<K
>& a
, IdSet
<K
>& b
) noexcept
{
333 //////////////////////////////////////////////////////////////////////