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