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 +----------------------------------------------------------------------+
17 #ifndef incl_HPHP_COMPACT_VECTOR_H_
18 #define incl_HPHP_COMPACT_VECTOR_H_
22 #include <type_traits>
23 #include <initializer_list>
25 #include "hphp/util/assertions.h"
26 #include "hphp/util/safe-cast.h"
29 ///////////////////////////////////////////////////////////////////////////////
32 * During its lifetime, an instance of CompactVector can transition
35 * This is the initial state for a newly constructed CompactVector.
36 * There are no elements and no allocated block of memory.
38 * In this state, m_data points to a malloced block of memory. The
39 * number of elements, the capacity of the block, and the values of
40 * all the elements reside in the allocated block of memory.
42 template <typename T
, typename Alloc
= std::allocator
<char>>
43 struct CompactVector
: private Alloc::template rebind
<char>::other
{
44 using size_type
= std::size_t;
47 using const_iterator
= const T
*;
48 using Allocator
= typename
Alloc::template rebind
<char>::other
;
50 friend iterator
begin(CompactVector
& v
) { return v
.begin(); }
51 friend iterator
end(CompactVector
& v
) { return v
.end(); }
52 friend const_iterator
begin(const CompactVector
& v
) { return v
.begin(); }
53 friend const_iterator
end(const CompactVector
& v
) { return v
.end(); }
56 explicit CompactVector(size_type n
);
57 CompactVector(size_type n
, const T
&);
58 CompactVector(CompactVector
&& other
) noexcept
;
59 CompactVector(const CompactVector
& other
);
60 CompactVector(std::initializer_list
<T
> init
);
61 CompactVector
& operator=(CompactVector
&&);
62 CompactVector
& operator=(const CompactVector
&);
65 void swap(CompactVector
& other
) noexcept
;
67 bool operator==(const CompactVector
& other
) const;
69 bool operator!=(const CompactVector
& other
) const {
70 return !(*this == other
);
73 iterator
begin() { return m_data
? elems() : nullptr; }
74 iterator
end() { return m_data
? elems() + size() : nullptr; }
75 const_iterator
begin() const { return m_data
? elems() : nullptr; }
76 const_iterator
end() const { return m_data
? elems() + size() : nullptr; }
77 T
* data() { return m_data
? elems() : nullptr; }
78 const T
* data() const { return m_data
? elems() : nullptr; }
81 size_type
size() const;
84 void push_back(const T
& val
);
85 void push_back(T
&& val
);
86 template <class... Args
>
87 void emplace_back(Args
&&... args
);
90 void erase(iterator
, iterator
);
91 iterator
insert(iterator p
, const T
& v
) { return insert_impl(p
, 1, v
); }
92 iterator
insert(iterator p
, T
&& v
) { return insert_impl(p
, 1, std::move(v
)); };
93 iterator
insert(iterator p
, size_t num
, const T
& v
) {
94 return insert_impl(p
, num
, v
);
97 iterator
insert(iterator p
, U i1
, U i2
);
98 void resize(size_type sz
);
99 void resize(size_type sz
, const value_type
& value
);
100 void shrink_to_fit();
102 T
& operator[](size_type index
) { return *get(index
); }
103 const T
& operator[](size_type index
) const { return *get(index
); }
104 T
& front() { return *get(0); }
105 const T
& front() const { return *get(0); }
106 T
& back() { return *get(m_data
->m_len
- 1); }
107 const T
& back() const { return *get(m_data
->m_len
- 1); }
109 void reserve(size_type sz
);
111 using Allocator::allocate
;
112 using Allocator::deallocate
;
114 struct CompactVectorData
{
119 iterator
insert_elems(iterator
, size_t num
);
121 iterator
insert_impl(iterator
, size_t num
, U
&&);
122 void assign(const CompactVector
& other
);
124 T
* get(size_type index
) const;
126 static size_t required_mem(size_type n
);
127 void reserve_impl(size_type sz
);
128 bool resize_helper(size_type sz
);
130 CompactVectorData
* m_data
;
132 static constexpr size_type initial_capacity
= 4;
133 /* We mainly want this so pretty.py can figure out the alignment */
134 static constexpr size_type elems_offset
=
135 alignof(T
) >= sizeof(CompactVectorData
) ?
136 alignof(T
) : sizeof(CompactVectorData
);
137 /* And we need this to prevent gcc from throwing away elems_offset */
138 using elems_offset_type
= char[elems_offset
];
141 template <typename T
, typename A
>
142 CompactVector
<T
, A
>::CompactVector() {
146 template <typename T
, typename A
>
147 CompactVector
<T
, A
>::CompactVector(size_type n
) {
152 template <typename T
, typename A
>
153 CompactVector
<T
, A
>::CompactVector(size_type n
, const T
& val
) {
158 template <typename T
, typename A
>
159 CompactVector
<T
, A
>::CompactVector(CompactVector
&& other
) noexcept
160 : m_data(other
.m_data
) {
161 other
.m_data
= nullptr;
164 template <typename T
, typename A
>
165 CompactVector
<T
, A
>::CompactVector(const CompactVector
& other
)
170 template <typename T
, typename A
>
172 CompactVector
<T
, A
>::operator=(const CompactVector
& other
) {
173 if (this == &other
) return *this;
179 template <typename T
, typename A
>
180 CompactVector
<T
, A
>::CompactVector(std::initializer_list
<T
> init
) :
182 reserve_impl(init
.size());
183 for (auto const& e
: init
) {
188 template <typename T
, typename A
>
189 void CompactVector
<T
, A
>::assign(const CompactVector
& other
) {
191 if (!other
.size()) return;
192 reserve_impl(other
.m_data
->m_len
);
193 auto const sz
= other
.m_data
->m_len
;
194 for (size_type i
= 0; i
< sz
; ++i
) {
199 template <typename T
, typename A
>
200 CompactVector
<T
, A
>& CompactVector
<T
, A
>::operator=(CompactVector
&& other
) {
201 std::swap(m_data
, other
.m_data
);
205 template <typename T
, typename A
>
206 void CompactVector
<T
, A
>::swap(CompactVector
& other
) noexcept
{
207 std::swap(m_data
, other
.m_data
);
210 template <typename T
, typename A
>
211 bool CompactVector
<T
, A
>::operator==(const CompactVector
& other
) const {
212 auto const sz
= size();
213 if (sz
!= other
.size()) return false;
214 for (size_type i
= 0; i
< sz
; ++i
) {
215 if (!(*get(i
) == other
[i
])) return false;
220 template <typename T
, typename A
>
221 CompactVector
<T
, A
>::~CompactVector() {
225 template <typename T
, typename A
>
226 T
* CompactVector
<T
, A
>::elems() const {
228 return (T
*)((char*)m_data
+ elems_offset
);
231 template <typename T
, typename A
>
232 size_t CompactVector
<T
, A
>::required_mem(size_type n
) {
233 return elems_offset
+ sizeof(T
) * n
;
236 template <typename T
, typename A
>
237 T
* CompactVector
<T
, A
>::get(size_type index
) const {
238 // Index into the allocated block of memory
240 assert(index
< m_data
->m_len
);
244 template <typename T
, typename A
>
245 bool CompactVector
<T
, A
>::empty() const {
249 template <typename T
, typename A
>
250 typename CompactVector
<T
, A
>::size_type CompactVector
<T
, A
>::size() const {
251 return m_data
? m_data
->m_len
: 0;
254 template <typename T
, typename A
>
255 typename CompactVector
<T
, A
>::size_type CompactVector
<T
, A
>::capacity() {
256 return m_data
? m_data
->m_capacity
: 0;
259 template <typename T
, typename A
>
260 void CompactVector
<T
, A
>::erase(iterator elm
) {
261 assert(elm
- elems() < size());
262 auto const e
= end();
264 elm
[-1] = std::move(*elm
);
270 template <typename T
, typename A
>
271 void CompactVector
<T
, A
>::erase(iterator elm1
, iterator elm2
) {
272 if (elm1
== elm2
) return;
273 assert(elems() <= elm1
&& elm1
<= elm2
&& elm2
<= end());
274 auto const e
= end();
276 *elm1
++ = std::move(*elm2
++);
278 m_data
->m_len
-= elm2
- elm1
;
284 template <typename T
, typename A
>
285 bool CompactVector
<T
, A
>::resize_helper(size_type sz
) {
286 auto const old_size
= size();
287 if (sz
== old_size
) return true;
296 } while (++sz
< old_size
);
300 template <typename T
, typename A
>
301 void CompactVector
<T
, A
>::resize(size_type sz
, const value_type
& v
) {
302 if (resize_helper(sz
)) return;
303 while (m_data
->m_len
< sz
) {
308 template <typename T
, typename A
>
309 void CompactVector
<T
, A
>::resize(size_type sz
) {
310 if (resize_helper(sz
)) return;
311 while (m_data
->m_len
< sz
) {
316 template <typename T
, typename A
>
317 void CompactVector
<T
, A
>::shrink_to_fit() {
318 if (!m_data
|| m_data
->m_capacity
== m_data
->m_len
) return;
319 if (!m_data
->m_len
) {
323 reserve_impl(m_data
->m_len
);
326 template <typename T
, typename A
>
327 void copy(CompactVector
<T
, A
>& dest
, const std::vector
<T
>& src
) {
329 dest
.reserve(src
.size());
330 for (auto const& v
: src
) dest
.push_back(v
);
333 template <typename T
, typename A
>
334 void CompactVector
<T
, A
>::clear() {
336 if (!std::is_trivially_destructible
<T
>::value
) {
337 if (auto sz
= size()) {
339 do { elm
++->~T(); } while (--sz
);
342 deallocate(reinterpret_cast<char*>(m_data
),
343 required_mem(m_data
->m_capacity
));
347 template <typename T
, typename A
>
348 void CompactVector
<T
, A
>::grow() {
349 reserve_impl(m_data
? m_data
->m_capacity
* 2LL : initial_capacity
);
352 template <typename T
, typename A
>
353 void CompactVector
<T
, A
>::reserve_impl(size_type new_capacity
) {
354 auto new_data
= (CompactVectorData
*)allocate(required_mem(new_capacity
));
355 if (!new_data
) throw std::bad_alloc
{};
358 auto len
= m_data
->m_len
;
359 auto old_data
= m_data
;
360 auto const old_capacity
= old_data
->m_capacity
;
361 auto old_elems
= elems();
363 auto new_elems
= elems();
365 m_data
->m_capacity
= safe_cast
<uint32_t>(new_capacity
);
367 new (new_elems
++) T(std::move(*old_elems
));
370 deallocate(reinterpret_cast<char*>(old_data
), required_mem(old_capacity
));
372 // If there are currently no elements, all we have to do is allocate a
373 // block of memory and initialize m_len and m_capacity.
376 m_data
->m_capacity
= new_capacity
;
380 template <typename T
, typename A
>
381 void CompactVector
<T
, A
>::reserve(size_type new_capacity
) {
382 if (new_capacity
> capacity()) reserve_impl(new_capacity
);
385 template <typename T
, typename A
>
386 typename CompactVector
<T
, A
>::iterator
387 CompactVector
<T
, A
>::insert_elems(iterator before
, size_t num
) {
388 if (!num
) return before
;
389 auto const sz
= size();
390 assert(sz
<= capacity());
391 auto cap
= capacity();
392 if (sz
+ num
> cap
) {
393 auto const pos
= sz
? before
- elems() : 0;
396 if (sz
+ num
> cap
) {
398 if (cap
< initial_capacity
) cap
= initial_capacity
;
401 before
= elems() + pos
;
405 m_data
->m_len
+= num
;
406 while (e
!= before
) {
408 new (e
+ num
) T(std::move(*e
));
415 template <typename T
, typename A
>
416 template <typename U
>
417 typename CompactVector
<T
, A
>::iterator
418 CompactVector
<T
, A
>::insert_impl(iterator before
, size_t num
, U
&& val
) {
419 auto e
= insert_elems(before
, num
);
421 new (e
+ num
) T(std::forward
<U
>(val
));
426 template <typename T
, typename A
>
427 template <typename U
>
428 typename CompactVector
<T
, A
>::iterator
429 CompactVector
<T
, A
>::insert(iterator before
, U i1
, U i2
) {
430 auto e
= insert_elems(before
, i2
- i1
);
438 template <typename T
, typename A
>
439 void CompactVector
<T
, A
>::push_back(const T
& val
) {
440 auto const sz
= size();
441 assert(sz
<= capacity());
442 if (sz
== capacity()) grow();
444 new (get(sz
)) T(val
);
447 template <typename T
, typename A
>
448 void CompactVector
<T
, A
>::push_back(T
&& val
) {
449 auto const sz
= size();
450 assert(sz
<= capacity());
451 if (sz
== capacity()) grow();
453 new (get(sz
)) T(std::move(val
));
456 template <typename T
, typename A
>
457 template <class... Args
>
458 void CompactVector
<T
, A
>::emplace_back(Args
&&... args
) {
459 auto const sz
= size();
460 assert(sz
<= capacity());
461 if (sz
== capacity()) grow();
463 new (get(sz
)) T(std::forward
<Args
>(args
)...);
466 template <typename T
, typename A
>
467 void CompactVector
<T
, A
>::pop_back() {
468 if (m_data
&& m_data
->m_len
> 0) {
469 // Otherwise, we just decrement the length
474 ///////////////////////////////////////////////////////////////////////////////