]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | #pragma once |
6 | ||
7 | #include <algorithm> | |
8 | #include <cassert> | |
9 | #include <initializer_list> | |
10 | #include <iterator> | |
11 | #include <stdexcept> | |
12 | #include <vector> | |
13 | ||
f67539c2 TL |
14 | #include "rocksdb/rocksdb_namespace.h" |
15 | ||
16 | namespace ROCKSDB_NAMESPACE { | |
7c673cae FG |
17 | |
18 | #ifdef ROCKSDB_LITE | |
19 | template <class T, size_t kSize = 8> | |
20 | class autovector : public std::vector<T> { | |
21 | using std::vector<T>::vector; | |
20effc67 TL |
22 | |
23 | public: | |
24 | autovector() { | |
25 | // Make sure the initial vector has space for kSize elements | |
26 | std::vector<T>::reserve(kSize); | |
27 | } | |
7c673cae FG |
28 | }; |
29 | #else | |
30 | // A vector that leverages pre-allocated stack-based array to achieve better | |
31 | // performance for array with small amount of items. | |
32 | // | |
33 | // The interface resembles that of vector, but with less features since we aim | |
34 | // to solve the problem that we have in hand, rather than implementing a | |
35 | // full-fledged generic container. | |
36 | // | |
37 | // Currently we don't support: | |
38 | // * reserve()/shrink_to_fit() | |
39 | // If used correctly, in most cases, people should not touch the | |
40 | // underlying vector at all. | |
41 | // * random insert()/erase(), please only use push_back()/pop_back(). | |
42 | // * No move/swap operations. Each autovector instance has a | |
43 | // stack-allocated array and if we want support move/swap operations, we | |
44 | // need to copy the arrays other than just swapping the pointers. In this | |
45 | // case we'll just explicitly forbid these operations since they may | |
46 | // lead users to make false assumption by thinking they are inexpensive | |
47 | // operations. | |
48 | // | |
49 | // Naming style of public methods almost follows that of the STL's. | |
50 | template <class T, size_t kSize = 8> | |
51 | class autovector { | |
52 | public: | |
53 | // General STL-style container member types. | |
54 | typedef T value_type; | |
55 | typedef typename std::vector<T>::difference_type difference_type; | |
56 | typedef typename std::vector<T>::size_type size_type; | |
57 | typedef value_type& reference; | |
58 | typedef const value_type& const_reference; | |
59 | typedef value_type* pointer; | |
60 | typedef const value_type* const_pointer; | |
61 | ||
62 | // This class is the base for regular/const iterator | |
63 | template <class TAutoVector, class TValueType> | |
64 | class iterator_impl { | |
65 | public: | |
66 | // -- iterator traits | |
67 | typedef iterator_impl<TAutoVector, TValueType> self_type; | |
68 | typedef TValueType value_type; | |
69 | typedef TValueType& reference; | |
70 | typedef TValueType* pointer; | |
71 | typedef typename TAutoVector::difference_type difference_type; | |
72 | typedef std::random_access_iterator_tag iterator_category; | |
73 | ||
74 | iterator_impl(TAutoVector* vect, size_t index) | |
75 | : vect_(vect), index_(index) {}; | |
76 | iterator_impl(const iterator_impl&) = default; | |
77 | ~iterator_impl() {} | |
78 | iterator_impl& operator=(const iterator_impl&) = default; | |
79 | ||
80 | // -- Advancement | |
81 | // ++iterator | |
82 | self_type& operator++() { | |
83 | ++index_; | |
84 | return *this; | |
85 | } | |
86 | ||
87 | // iterator++ | |
88 | self_type operator++(int) { | |
89 | auto old = *this; | |
90 | ++index_; | |
91 | return old; | |
92 | } | |
93 | ||
94 | // --iterator | |
95 | self_type& operator--() { | |
96 | --index_; | |
97 | return *this; | |
98 | } | |
99 | ||
100 | // iterator-- | |
101 | self_type operator--(int) { | |
102 | auto old = *this; | |
103 | --index_; | |
104 | return old; | |
105 | } | |
106 | ||
11fdf7f2 | 107 | self_type operator-(difference_type len) const { |
7c673cae FG |
108 | return self_type(vect_, index_ - len); |
109 | } | |
110 | ||
11fdf7f2 | 111 | difference_type operator-(const self_type& other) const { |
7c673cae FG |
112 | assert(vect_ == other.vect_); |
113 | return index_ - other.index_; | |
114 | } | |
115 | ||
11fdf7f2 | 116 | self_type operator+(difference_type len) const { |
7c673cae FG |
117 | return self_type(vect_, index_ + len); |
118 | } | |
119 | ||
120 | self_type& operator+=(difference_type len) { | |
121 | index_ += len; | |
122 | return *this; | |
123 | } | |
124 | ||
125 | self_type& operator-=(difference_type len) { | |
126 | index_ -= len; | |
127 | return *this; | |
128 | } | |
129 | ||
130 | // -- Reference | |
f67539c2 | 131 | reference operator*() const { |
11fdf7f2 TL |
132 | assert(vect_->size() >= index_); |
133 | return (*vect_)[index_]; | |
134 | } | |
135 | ||
f67539c2 | 136 | pointer operator->() const { |
7c673cae FG |
137 | assert(vect_->size() >= index_); |
138 | return &(*vect_)[index_]; | |
139 | } | |
140 | ||
f67539c2 TL |
141 | reference operator[](difference_type len) const { |
142 | return *(*this + len); | |
11fdf7f2 TL |
143 | } |
144 | ||
7c673cae FG |
145 | // -- Logical Operators |
146 | bool operator==(const self_type& other) const { | |
147 | assert(vect_ == other.vect_); | |
148 | return index_ == other.index_; | |
149 | } | |
150 | ||
151 | bool operator!=(const self_type& other) const { return !(*this == other); } | |
152 | ||
153 | bool operator>(const self_type& other) const { | |
154 | assert(vect_ == other.vect_); | |
155 | return index_ > other.index_; | |
156 | } | |
157 | ||
158 | bool operator<(const self_type& other) const { | |
159 | assert(vect_ == other.vect_); | |
160 | return index_ < other.index_; | |
161 | } | |
162 | ||
163 | bool operator>=(const self_type& other) const { | |
164 | assert(vect_ == other.vect_); | |
165 | return index_ >= other.index_; | |
166 | } | |
167 | ||
168 | bool operator<=(const self_type& other) const { | |
169 | assert(vect_ == other.vect_); | |
170 | return index_ <= other.index_; | |
171 | } | |
172 | ||
173 | private: | |
174 | TAutoVector* vect_ = nullptr; | |
175 | size_t index_ = 0; | |
176 | }; | |
177 | ||
178 | typedef iterator_impl<autovector, value_type> iterator; | |
179 | typedef iterator_impl<const autovector, const value_type> const_iterator; | |
180 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
181 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
182 | ||
494da23a | 183 | autovector() : values_(reinterpret_cast<pointer>(buf_)) {} |
7c673cae | 184 | |
494da23a TL |
185 | autovector(std::initializer_list<T> init_list) |
186 | : values_(reinterpret_cast<pointer>(buf_)) { | |
7c673cae FG |
187 | for (const T& item : init_list) { |
188 | push_back(item); | |
189 | } | |
190 | } | |
191 | ||
494da23a | 192 | ~autovector() { clear(); } |
7c673cae FG |
193 | |
194 | // -- Immutable operations | |
195 | // Indicate if all data resides in in-stack data structure. | |
196 | bool only_in_stack() const { | |
197 | // If no element was inserted at all, the vector's capacity will be `0`. | |
198 | return vect_.capacity() == 0; | |
199 | } | |
200 | ||
201 | size_type size() const { return num_stack_items_ + vect_.size(); } | |
202 | ||
203 | // resize does not guarantee anything about the contents of the newly | |
204 | // available elements | |
205 | void resize(size_type n) { | |
206 | if (n > kSize) { | |
207 | vect_.resize(n - kSize); | |
494da23a TL |
208 | while (num_stack_items_ < kSize) { |
209 | new ((void*)(&values_[num_stack_items_++])) value_type(); | |
210 | } | |
7c673cae FG |
211 | num_stack_items_ = kSize; |
212 | } else { | |
213 | vect_.clear(); | |
494da23a TL |
214 | while (num_stack_items_ < n) { |
215 | new ((void*)(&values_[num_stack_items_++])) value_type(); | |
216 | } | |
217 | while (num_stack_items_ > n) { | |
218 | values_[--num_stack_items_].~value_type(); | |
219 | } | |
7c673cae FG |
220 | } |
221 | } | |
222 | ||
223 | bool empty() const { return size() == 0; } | |
224 | ||
225 | const_reference operator[](size_type n) const { | |
226 | assert(n < size()); | |
494da23a TL |
227 | if (n < kSize) { |
228 | return values_[n]; | |
229 | } | |
230 | return vect_[n - kSize]; | |
7c673cae FG |
231 | } |
232 | ||
233 | reference operator[](size_type n) { | |
234 | assert(n < size()); | |
494da23a TL |
235 | if (n < kSize) { |
236 | return values_[n]; | |
237 | } | |
238 | return vect_[n - kSize]; | |
7c673cae FG |
239 | } |
240 | ||
241 | const_reference at(size_type n) const { | |
242 | assert(n < size()); | |
243 | return (*this)[n]; | |
244 | } | |
245 | ||
246 | reference at(size_type n) { | |
247 | assert(n < size()); | |
248 | return (*this)[n]; | |
249 | } | |
250 | ||
251 | reference front() { | |
252 | assert(!empty()); | |
253 | return *begin(); | |
254 | } | |
255 | ||
256 | const_reference front() const { | |
257 | assert(!empty()); | |
258 | return *begin(); | |
259 | } | |
260 | ||
261 | reference back() { | |
262 | assert(!empty()); | |
263 | return *(end() - 1); | |
264 | } | |
265 | ||
266 | const_reference back() const { | |
267 | assert(!empty()); | |
268 | return *(end() - 1); | |
269 | } | |
270 | ||
271 | // -- Mutable Operations | |
272 | void push_back(T&& item) { | |
273 | if (num_stack_items_ < kSize) { | |
494da23a | 274 | new ((void*)(&values_[num_stack_items_])) value_type(); |
7c673cae FG |
275 | values_[num_stack_items_++] = std::move(item); |
276 | } else { | |
277 | vect_.push_back(item); | |
278 | } | |
279 | } | |
280 | ||
281 | void push_back(const T& item) { | |
282 | if (num_stack_items_ < kSize) { | |
494da23a | 283 | new ((void*)(&values_[num_stack_items_])) value_type(); |
7c673cae FG |
284 | values_[num_stack_items_++] = item; |
285 | } else { | |
286 | vect_.push_back(item); | |
287 | } | |
288 | } | |
289 | ||
290 | template <class... Args> | |
291 | void emplace_back(Args&&... args) { | |
494da23a TL |
292 | if (num_stack_items_ < kSize) { |
293 | new ((void*)(&values_[num_stack_items_++])) | |
294 | value_type(std::forward<Args>(args)...); | |
295 | } else { | |
296 | vect_.emplace_back(std::forward<Args>(args)...); | |
297 | } | |
7c673cae FG |
298 | } |
299 | ||
300 | void pop_back() { | |
301 | assert(!empty()); | |
302 | if (!vect_.empty()) { | |
303 | vect_.pop_back(); | |
304 | } else { | |
494da23a | 305 | values_[--num_stack_items_].~value_type(); |
7c673cae FG |
306 | } |
307 | } | |
308 | ||
309 | void clear() { | |
494da23a TL |
310 | while (num_stack_items_ > 0) { |
311 | values_[--num_stack_items_].~value_type(); | |
312 | } | |
7c673cae FG |
313 | vect_.clear(); |
314 | } | |
315 | ||
316 | // -- Copy and Assignment | |
317 | autovector& assign(const autovector& other); | |
318 | ||
319 | autovector(const autovector& other) { assign(other); } | |
320 | ||
321 | autovector& operator=(const autovector& other) { return assign(other); } | |
322 | ||
323 | // -- Iterator Operations | |
324 | iterator begin() { return iterator(this, 0); } | |
325 | ||
326 | const_iterator begin() const { return const_iterator(this, 0); } | |
327 | ||
328 | iterator end() { return iterator(this, this->size()); } | |
329 | ||
330 | const_iterator end() const { return const_iterator(this, this->size()); } | |
331 | ||
332 | reverse_iterator rbegin() { return reverse_iterator(end()); } | |
333 | ||
334 | const_reverse_iterator rbegin() const { | |
335 | return const_reverse_iterator(end()); | |
336 | } | |
337 | ||
338 | reverse_iterator rend() { return reverse_iterator(begin()); } | |
339 | ||
340 | const_reverse_iterator rend() const { | |
341 | return const_reverse_iterator(begin()); | |
342 | } | |
343 | ||
344 | private: | |
345 | size_type num_stack_items_ = 0; // current number of items | |
494da23a TL |
346 | alignas(alignof( |
347 | value_type)) char buf_[kSize * | |
348 | sizeof(value_type)]; // the first `kSize` items | |
349 | pointer values_; | |
7c673cae FG |
350 | // used only if there are more than `kSize` items. |
351 | std::vector<T> vect_; | |
352 | }; | |
353 | ||
354 | template <class T, size_t kSize> | |
355 | autovector<T, kSize>& autovector<T, kSize>::assign(const autovector& other) { | |
494da23a | 356 | values_ = reinterpret_cast<pointer>(buf_); |
7c673cae FG |
357 | // copy the internal vector |
358 | vect_.assign(other.vect_.begin(), other.vect_.end()); | |
359 | ||
360 | // copy array | |
361 | num_stack_items_ = other.num_stack_items_; | |
362 | std::copy(other.values_, other.values_ + num_stack_items_, values_); | |
363 | ||
364 | return *this; | |
365 | } | |
366 | #endif // ROCKSDB_LITE | |
f67539c2 | 367 | } // namespace ROCKSDB_NAMESPACE |