1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
|
#pragma once
#include <util/system/defaults.h>
#include <cstdint>
#include <iterator>
#include <limits>
namespace NYT {
////////////////////////////////////////////////////////////////////////////////
template <class T>
struct TCompactVectorOnHeapStorage;
//! A vector-like structure optimized for storing elements inline
//! and with little memory overhead.
/*!
* Stores up to #N (<= 254) elements inline.
*
* When capacity starts exceeding #N, moves all elements to heap;
* \see #TCompactVectorOnHeapStorage.
*
* When linked with YTAlloc, employs its API to adjust the on-heap capacity in accordance
* to the actual size of the allocated region.
*
* Assuming the entropy and the alignment constraints, yields a seemingly optimal memory overhead.
* E.g. TCompactVector<uint8_t, 7> takes 8 bytes and TCompactVector<uint32_t, 3> takes 16 bytes.
* \see #ByteSize.
*
* Assumes (and asserts) the following:
* 1) the platform is 64 bit;
* 2) the highest 8 bits of pointers returned by |malloc| are zeroes;
* 3) the platform is little-endian.
*/
template <class T, size_t N>
class TCompactVector
{
public:
static_assert(N < std::numeric_limits<uint8_t>::max());
using size_type = size_t;
using difference_type = ptrdiff_t;
using value_type = T;
using iterator = T*;
using const_iterator = const T*;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
using reverse_iterator = std::reverse_iterator<iterator>;
using reference = T&;
using const_reference = const T&;
using pointer = T*;
using const_pointer = const T*;
TCompactVector() noexcept;
TCompactVector(const TCompactVector& other);
template <size_t OtherN>
TCompactVector(const TCompactVector<T, OtherN>& other);
TCompactVector(TCompactVector&& other) noexcept(std::is_nothrow_move_constructible_v<T>);
template <size_t OtherN>
TCompactVector(TCompactVector<T, OtherN>&& other);
explicit TCompactVector(size_type count);
TCompactVector(size_type count, const T& value);
template <class TIterator>
TCompactVector(TIterator first, TIterator last);
TCompactVector(std::initializer_list<T> list);
~TCompactVector();
[[nodiscard]] bool empty() const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
size_type size() const;
size_type capacity() const;
size_type max_size() const;
pointer data();
const_pointer data() const;
reference operator[](size_type index);
const_reference operator[](size_type index) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
void push_back(const T& value);
void push_back(T&& value);
template <class... TArgs>
iterator emplace(const_iterator pos, TArgs&&... args);
template <class... TArgs>
reference emplace_back(TArgs&&... args);
void pop_back();
iterator erase(const_iterator pos);
iterator erase(const_iterator first, const_iterator last);
void clear();
void resize(size_type newSize);
void resize(size_type newSize, const T& value);
void reserve(size_type newCapacity);
void swap(TCompactVector& other);
void assign(size_type count, const T& value);
template <class TIterator>
void assign(TIterator first, TIterator last);
void assign(std::initializer_list<T> list);
template <size_t OtherN>
void assign(const TCompactVector<T, OtherN>& other);
template <size_t OtherN>
void assign(TCompactVector<T, OtherN>&& other);
TCompactVector& operator=(const TCompactVector& other);
template <size_t OtherN>
TCompactVector& operator=(const TCompactVector<T, OtherN>& other);
TCompactVector& operator=(TCompactVector&& other);
template <size_t OtherN>
TCompactVector& operator=(TCompactVector<T, OtherN>&& other);
TCompactVector& operator=(std::initializer_list<T> list);
iterator insert(const_iterator pos, const T& value);
iterator insert(const_iterator pos, T&& value);
iterator insert(const_iterator pos, size_type count, const T& value);
template <class TIterator>
iterator insert(const_iterator pos, TIterator first, TIterator last);
iterator insert(const_iterator pos, std::initializer_list<T> list);
void shrink_to_small();
private:
template <class OtherT, size_t OtherN>
friend class TCompactVector;
using TOnHeapStorage = TCompactVectorOnHeapStorage<T>;
static constexpr size_t ByteSize =
(sizeof(T) * N + alignof(T) + sizeof(uintptr_t) - 1) &
~(sizeof(uintptr_t) - 1);
struct TInlineMeta
{
char Padding[ByteSize - sizeof(uint8_t)];
// > 0 indicates inline storage
// == 0 indicates on-heap storage
uint8_t SizePlusOne;
} alias_hack;
// TODO(aleexfi): Use [[no_unique_address]] when clang will support it on windows.
template <class = void>
struct TOnHeapMeta
{
char Padding[ByteSize - sizeof(uintptr_t)];
TOnHeapStorage* Storage;
} alias_hack;
template <class _>
requires (ByteSize == sizeof(uintptr_t))
struct TOnHeapMeta<_>
{
TOnHeapStorage* Storage;
} alias_hack;
static_assert(sizeof(TOnHeapMeta<>) == ByteSize);
union
{
T InlineElements_[N];
TInlineMeta InlineMeta_;
TOnHeapMeta<> OnHeapMeta_;
};
bool IsInline() const;
void SetSize(size_t newSize);
void EnsureOnHeapCapacity(size_t newCapacity, bool incremental);
template <class TPtr, class F>
reference PushBackImpl(TPtr valuePtr, F&& func);
template <class F>
void ResizeImpl(size_t newSize, F&& func);
template <class TPtr, class UninitializedF, class InitializedF>
iterator InsertOneImpl(const_iterator pos, TPtr valuePtr, UninitializedF&& uninitializedFunc, InitializedF&& initializedFunc);
template <class UninitializedF, class InitializedF>
iterator InsertManyImpl(const_iterator pos, size_t insertCount, UninitializedF&& uninitializedFunc, InitializedF&& initializedFunc);
static void Destroy(T* first, T* last);
template <class T1, class T2>
static void Copy(const T1* srcFirst, const T1* srcLast, T2* dst);
template <class T1, class T2>
static void UninitializedCopy(const T1* srcFirst, const T1* srcLast, T2* dst);
static void Move(T* srcFirst, T* srcLast, T* dst);
static void MoveBackward(T* srcFirst, T* srcLast, T* dst);
static void UninitializedMove(T* srcFirst, T* srcLast, T* dst);
};
////////////////////////////////////////////////////////////////////////////////
template <class T, size_t LhsN, size_t RhsN>
bool operator==(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs);
template <class T, size_t LhsN, size_t RhsN>
bool operator!=(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs);
template <class T, size_t LhsN, size_t RhsN>
bool operator<(const TCompactVector<T, LhsN>& lhs, const TCompactVector<T, RhsN>& rhs);
////////////////////////////////////////////////////////////////////////////////
} // namespace NYT
#define COMPACT_VECTOR_INL_H_
#include "compact_vector-inl.h"
#undef COMPACT_VECTOR_INL_H_
|
