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 +----------------------------------------------------------------------+
21 #include <type_traits>
23 #include <boost/iterator/iterator_facade.hpp>
24 #include <folly/lang/Launder.h>
25 #include <folly/portability/Malloc.h>
27 #include "hphp/util/alloc.h"
28 #include "hphp/util/assertions.h"
29 #include "hphp/util/compact-tagged-ptrs.h"
33 // Replace with std::is_nothrow_swappable in c++17
34 namespace tiny_vector_detail
{
38 struct is_nothrow_swappable
{
39 static constexpr bool value
=
40 noexcept(swap(std::declval
<U
&>(), std::declval
<U
&>()));
45 //////////////////////////////////////////////////////////////////////
48 * Simple, small buffer-optimized sequence of T.
52 * - Unlike std::vector, storage is not guaranteed to be contiguous.
54 * - Insertion and removal can only happen at the end of the
55 * sequence (although you can modify elements anywhere in the
58 * - There is no non-const iterator support, and we have forward
61 * - The elements must be nothrow move constructible and nothrow swappable.
63 * Currently, does not invalidate pointers or references to elements
64 * at indexes less than InternalSize, but we don't want to depend on
65 * this without documenting it here. Iterators should be considered
66 * invalidated after any mutation.
68 * Also: if you have a T*, and the list almost always contains at most
69 * one element, PointerList is a smaller object so may be preferable
70 * in that case. (Unless you want the first element to remain
71 * accessible inline instead of moved to the heap.)
74 // Allocator interface with an additional `usable_size()` API.
76 struct TinyVectorMallocAllocator
{
77 using size_type
= std::size_t;
79 template <typename U
> struct rebind
{
80 using other
= TinyVectorMallocAllocator
<U
>;
83 T
* allocate(std::size_t size
) const {
84 return reinterpret_cast<T
*>(malloc(size
));
86 void deallocate(T
* ptr
, size_t) const { free(ptr
); }
87 std::size_t usable_size(T
* ptr
, std::size_t) const {
88 return malloc_usable_size(ptr
);
93 size_t InternalSize
= 1,
94 size_t MinHeapCapacity
= 0,
95 typename OrigAllocator
= TinyVectorMallocAllocator
<T
>>
97 static_assert(std::is_nothrow_move_constructible
<T
>::value
,
98 "TinyVector only supports elements with "
99 "non-throwing move constructors");
100 static_assert(tiny_vector_detail::is_nothrow_swappable
<T
>::value
,
101 "TinyVector only supports elements with non-throwing swaps");
102 static_assert(InternalSize
>= 1,
103 "TinyVector assumes that the internal size is at least 1");
106 * We need to see if the allocator implements a member named `usable_size`.
107 * If it does, we assume it is a method like
108 * size_type Alloc::usable_size(pointer, size_type);
110 template <typename Alloc
> struct alloc_traits
: std::allocator_traits
<Alloc
> {
111 using typename
std::allocator_traits
<Alloc
>::size_type
;
114 template <typename AT
, decltype(&AT::usable_size
)* = nullptr>
116 template <typename AT
= Alloc
>
117 static std::true_type
helper(valid_type
<AT
>*);
118 template <typename AT
= Alloc
> static std::false_type
helper(...);
119 static constexpr bool has_usable_size
=
120 std::is_same
<std::true_type
, decltype(helper(nullptr))>::value
;
122 template<typename AT
= Alloc
> static size_type
usable_size_impl(
123 typename
std::enable_if
<alloc_traits
<AT
>::has_usable_size
, AT
>::type
& a
,
124 void* ptr
, size_type size
) {
125 return a
.usable_size(ptr
, size
);
127 template<typename AT
= Alloc
> static size_type
usable_size_impl(
128 typename
std::enable_if
<!alloc_traits
<AT
>::has_usable_size
, AT
>::type
&,
129 void*, size_type size
) {
133 static size_type
usable_size(Alloc
& a
, void* ptr
, size_type size
) {
134 return usable_size_impl(a
, ptr
, size
);
138 using Allocator
= typename
OrigAllocator::template rebind
<uint8_t>::other
;
139 using AT
= alloc_traits
<Allocator
>;
140 using AllocPtr
= typename
AT::pointer
;
142 struct const_iterator
;
144 TinyVector() = default;
145 ~TinyVector() { clear(); }
147 TinyVector(const TinyVector
& o
) {
149 for (auto const& elem
: o
) push_back(elem
);
151 TinyVector(TinyVector
&& o
) noexcept
{ swap(o
); }
153 TinyVector
& operator=(const TinyVector
& o
) {
160 TinyVector
& operator=(TinyVector
&& o
) noexcept
{
161 if (this != &o
) swap(o
);
165 template <typename U
>
166 TinyVector(std::initializer_list
<U
> il
) {
168 for (auto const& elem
: il
) push_back(elem
);
171 size_t size() const { return m_impl
.m_data
.size(); }
172 bool empty() const { return !size(); }
174 void swap(TinyVector
& o
) noexcept
{
175 auto const size1
= m_impl
.m_data
.size();
176 auto const size2
= o
.m_impl
.m_data
.size();
177 auto const internal1
= std::min
<size_t>(size1
, InternalSize
);
178 auto const internal2
= std::min
<size_t>(size2
, InternalSize
);
180 // Swap the prefix of the inline storage which both have initialized.
181 auto const both
= std::min(internal1
, internal2
);
182 for (size_t i
= 0; i
< both
; ++i
) {
184 swap(*location(i
), *o
.location(i
));
187 // Move data out of the vector with more initialized inline data into the
188 // one with less. Then destroy the moved from data.
189 if (internal1
> internal2
) {
190 uninitialized_move_n(
192 internal1
- internal2
,
193 o
.location(internal2
)
195 if (!std::is_trivially_destructible
<T
>::value
) {
196 for (size_t i
= internal2
; i
< internal1
; ++i
) location(i
)->~T();
199 uninitialized_move_n(
200 o
.location(internal1
),
201 internal2
- internal1
,
204 if (!std::is_trivially_destructible
<T
>::value
) {
205 for (size_t i
= internal1
; i
< internal2
; ++i
) o
.location(i
)->~T();
209 // Move the non-inline data. This is just a simple pointer swap.
211 swap(m_impl
.m_data
, o
.m_impl
.m_data
);
214 const_iterator
begin() const { return const_iterator(this, 0); }
215 const_iterator
end() const { return const_iterator(this); }
217 T
& operator[](size_t index
) {
218 assert(index
< size());
219 return *location(index
);
222 const T
& operator[](size_t index
) const {
223 return const_cast<TinyVector
*>(this)->operator[](index
);
227 if (!std::is_trivially_destructible
<T
>::value
) {
228 auto const current
= size();
229 for (size_t i
= 0; i
< current
; ++i
) location(i
)->~T();
232 if (HeapData
* p
= m_impl
.m_data
.ptr()) {
233 alloc_traits
<Impl
>::deallocate(m_impl
, reinterpret_cast<AllocPtr
>(p
),
234 allocSize(p
->capacity
));
236 m_impl
.m_data
.set(0, 0);
239 template <typename U
>
240 T
& push_back(const U
& u
) {
241 auto const current
= size();
242 reserve(current
+ 1);
243 auto ptr
= location(current
);
245 m_impl
.m_data
.set(current
+ 1, m_impl
.m_data
.ptr());
249 template <typename U
>
250 T
& push_back(U
&& u
) {
251 auto const current
= size();
252 reserve(current
+ 1);
253 auto ptr
= location(current
);
254 ::new (ptr
) T(std::move(u
));
255 m_impl
.m_data
.set(current
+ 1, m_impl
.m_data
.ptr());
259 template <typename
... Args
>
260 T
& emplace_back(Args
&&... args
) {
261 auto const current
= size();
262 reserve(current
+ 1);
263 auto ptr
= location(current
);
264 ::new (ptr
) T(std::forward
<Args
>(args
)...);
265 m_impl
.m_data
.set(current
+ 1, m_impl
.m_data
.ptr());
269 template <typename I
>
270 void insert(I begin
, I end
) {
271 while (begin
!= end
) emplace_back(*begin
++);
276 location(size() - 1)->~T();
277 m_impl
.m_data
.set(size() - 1, m_impl
.m_data
.ptr());
282 return (*this)[size() - 1];
285 const T
& back() const {
287 return (*this)[size() - 1];
295 const T
& front() const {
300 void reserve(size_t sz
) {
301 if (sz
< InternalSize
) return;
303 const size_t currentHeap
=
304 m_impl
.m_data
.ptr() ? m_impl
.m_data
.ptr()->capacity
: 0;
305 const size_t neededHeap
= sz
- InternalSize
;
306 if (neededHeap
<= currentHeap
) {
310 const size_t newCapacity
= std::max(
311 currentHeap
? currentHeap
* 4 / 3
312 : std::max(neededHeap
, MinHeapCapacity
),
314 const size_t requested
= allocSize(newCapacity
);
315 auto newHeap
= reinterpret_cast<HeapData
*>(AT::allocate(m_impl
, requested
));
316 const size_t usableSize
= AT::usable_size(m_impl
, newHeap
, requested
);
317 newHeap
->capacity
= (usableSize
- offsetof(HeapData
, vals
)) / sizeof(T
);
319 if (auto p
= m_impl
.m_data
.ptr()) {
320 auto const current
= size();
321 uninitialized_move_n(
322 &m_impl
.m_data
.ptr()->vals
[0],
323 current
- InternalSize
,
326 if (!std::is_trivially_destructible
<T
>::value
) {
327 for (size_t i
= InternalSize
; i
< current
; ++i
) location(i
)->~T();
331 reinterpret_cast<AllocPtr
>(p
),
332 allocSize(p
->capacity
)
335 m_impl
.m_data
.set(size(), newHeap
);
338 template<size_t isize
, size_t minheap
, typename origalloc
>
339 bool operator==(const TinyVector
<T
, isize
, minheap
, origalloc
>& tv
) const {
340 if (size() != tv
.size()) return false;
341 return std::equal(begin(), end(), tv
.begin());
343 template<size_t isize
, size_t minheap
, typename origalloc
>
344 bool operator!=(const TinyVector
<T
, isize
, minheap
, origalloc
>& tv
) const {
345 return !(*this == tv
);
348 template<size_t isize
, size_t minheap
, typename origalloc
>
349 bool operator<(const TinyVector
<T
, isize
, minheap
, origalloc
>& tv
) const {
350 return std::lexicographical_compare(begin(), end(), tv
.begin(), tv
.end());
352 template<size_t isize
, size_t minheap
, typename origalloc
>
353 bool operator<=(const TinyVector
<T
, isize
, minheap
, origalloc
>& tv
) const {
354 return (*this < tv
) || (*this == tv
);
356 template<size_t isize
, size_t minheap
, typename origalloc
>
357 bool operator>(const TinyVector
<T
, isize
, minheap
, origalloc
>& tv
) const {
358 return !(*this <= tv
);
360 template<size_t isize
, size_t minheap
, typename origalloc
>
361 bool operator>=(const TinyVector
<T
, isize
, minheap
, origalloc
>& tv
) const {
362 return !(*this < tv
);
367 uint32_t capacity
; // numbers of vals---excludes this capacity field
371 static constexpr std::size_t allocSize(uint32_t capacity
) {
372 return sizeof(HeapData
) + sizeof(T
) * capacity
;
375 T
* location(size_t index
) {
376 return (index
< InternalSize
)
377 ? folly::launder(reinterpret_cast<T
*>(&m_impl
.m_vals
[index
]))
378 : &m_impl
.m_data
.ptr()->vals
[index
- InternalSize
];
381 // Replace with std::uninitialized_move_n in c++17
382 template<typename InputIt
, typename ForwardIt
>
383 static void uninitialized_move_n(InputIt first
,
386 using Value
= typename
std::iterator_traits
<ForwardIt
>::value_type
;
387 auto current
= d_first
;
389 for (; count
> 0; ++first
, ++current
, --count
) {
390 ::new (static_cast<void*>(std::addressof(*current
)))
391 Value(std::move(*first
));
394 for (; d_first
!= current
; ++d_first
) {
401 using RawBuffer
= typename
std::aligned_storage
<sizeof(T
), alignof(T
)>::type
;
402 using InternalStorage
= RawBuffer
[InternalSize
];
404 struct Impl
: Allocator
{
405 CompactSizedPtr
<HeapData
> m_data
;
406 InternalStorage m_vals
;
411 //////////////////////////////////////////////////////////////////////
415 size_t MinHeapCapacity
,
417 struct TinyVector
<T
,InternalSize
,MinHeapCapacity
,Allocator
>::const_iterator
418 : boost::iterator_facade
<const_iterator
,
420 boost::forward_traversal_tag
>
422 explicit const_iterator(const TinyVector
* p
, uint32_t idx
)
427 explicit const_iterator(const TinyVector
* p
)
433 friend class boost::iterator_core_access
;
439 bool equal(const const_iterator
& o
) const {
440 assert(m_p
== o
.m_p
);
441 return m_idx
== o
.m_idx
;
444 const T
& dereference() const {
445 return (*m_p
)[m_idx
];
449 const TinyVector
* m_p
;
453 //////////////////////////////////////////////////////////////////////
457 size_t MinHeapCapacity
,
459 void swap(TinyVector
<T
, InternalSize
, MinHeapCapacity
, Allocator
>& v1
,
460 TinyVector
<T
, InternalSize
, MinHeapCapacity
, Allocator
>& v2
)
465 //////////////////////////////////////////////////////////////////////