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