]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. |
2 | // This source code is licensed under the BSD-style license found in the | |
3 | // LICENSE file in the root directory of this source tree. An additional grant | |
4 | // of patent rights can be found in the PATENTS file in the same 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 | ||
14 | namespace rocksdb { | |
15 | ||
16 | #ifdef ROCKSDB_LITE | |
17 | template <class T, size_t kSize = 8> | |
18 | class 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. | |
42 | template <class T, size_t kSize = 8> | |
43 | class 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) { | |
100 | return self_type(vect_, index_ - len); | |
101 | } | |
102 | ||
103 | difference_type operator-(const self_type& other) { | |
104 | assert(vect_ == other.vect_); | |
105 | return index_ - other.index_; | |
106 | } | |
107 | ||
108 | self_type operator+(difference_type len) { | |
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 | pointer operator->() { | |
128 | assert(vect_->size() >= index_); | |
129 | return &(*vect_)[index_]; | |
130 | } | |
131 | ||
132 | // -- Logical Operators | |
133 | bool operator==(const self_type& other) const { | |
134 | assert(vect_ == other.vect_); | |
135 | return index_ == other.index_; | |
136 | } | |
137 | ||
138 | bool operator!=(const self_type& other) const { return !(*this == other); } | |
139 | ||
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 { | |
146 | assert(vect_ == other.vect_); | |
147 | return index_ < other.index_; | |
148 | } | |
149 | ||
150 | bool operator>=(const self_type& other) const { | |
151 | assert(vect_ == other.vect_); | |
152 | return index_ >= other.index_; | |
153 | } | |
154 | ||
155 | bool operator<=(const self_type& other) const { | |
156 | assert(vect_ == other.vect_); | |
157 | return index_ <= other.index_; | |
158 | } | |
159 | ||
160 | private: | |
161 | TAutoVector* vect_ = nullptr; | |
162 | size_t index_ = 0; | |
163 | }; | |
164 | ||
165 | typedef iterator_impl<autovector, value_type> iterator; | |
166 | typedef iterator_impl<const autovector, const value_type> const_iterator; | |
167 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
168 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
169 | ||
170 | autovector() = default; | |
171 | ||
172 | autovector(std::initializer_list<T> init_list) { | |
173 | for (const T& item : init_list) { | |
174 | push_back(item); | |
175 | } | |
176 | } | |
177 | ||
178 | ~autovector() = default; | |
179 | ||
180 | // -- Immutable operations | |
181 | // Indicate if all data resides in in-stack data structure. | |
182 | bool only_in_stack() const { | |
183 | // If no element was inserted at all, the vector's capacity will be `0`. | |
184 | return vect_.capacity() == 0; | |
185 | } | |
186 | ||
187 | size_type size() const { return num_stack_items_ + vect_.size(); } | |
188 | ||
189 | // resize does not guarantee anything about the contents of the newly | |
190 | // available elements | |
191 | void resize(size_type n) { | |
192 | if (n > kSize) { | |
193 | vect_.resize(n - kSize); | |
194 | num_stack_items_ = kSize; | |
195 | } else { | |
196 | vect_.clear(); | |
197 | num_stack_items_ = n; | |
198 | } | |
199 | } | |
200 | ||
201 | bool empty() const { return size() == 0; } | |
202 | ||
203 | const_reference operator[](size_type n) const { | |
204 | assert(n < size()); | |
205 | return n < kSize ? values_[n] : vect_[n - kSize]; | |
206 | } | |
207 | ||
208 | reference operator[](size_type n) { | |
209 | assert(n < size()); | |
210 | return n < kSize ? values_[n] : vect_[n - kSize]; | |
211 | } | |
212 | ||
213 | const_reference at(size_type n) const { | |
214 | assert(n < size()); | |
215 | return (*this)[n]; | |
216 | } | |
217 | ||
218 | reference at(size_type n) { | |
219 | assert(n < size()); | |
220 | return (*this)[n]; | |
221 | } | |
222 | ||
223 | reference front() { | |
224 | assert(!empty()); | |
225 | return *begin(); | |
226 | } | |
227 | ||
228 | const_reference front() const { | |
229 | assert(!empty()); | |
230 | return *begin(); | |
231 | } | |
232 | ||
233 | reference back() { | |
234 | assert(!empty()); | |
235 | return *(end() - 1); | |
236 | } | |
237 | ||
238 | const_reference back() const { | |
239 | assert(!empty()); | |
240 | return *(end() - 1); | |
241 | } | |
242 | ||
243 | // -- Mutable Operations | |
244 | void push_back(T&& item) { | |
245 | if (num_stack_items_ < kSize) { | |
246 | values_[num_stack_items_++] = std::move(item); | |
247 | } else { | |
248 | vect_.push_back(item); | |
249 | } | |
250 | } | |
251 | ||
252 | void push_back(const T& item) { | |
253 | if (num_stack_items_ < kSize) { | |
254 | values_[num_stack_items_++] = item; | |
255 | } else { | |
256 | vect_.push_back(item); | |
257 | } | |
258 | } | |
259 | ||
260 | template <class... Args> | |
261 | void emplace_back(Args&&... args) { | |
262 | push_back(value_type(args...)); | |
263 | } | |
264 | ||
265 | void pop_back() { | |
266 | assert(!empty()); | |
267 | if (!vect_.empty()) { | |
268 | vect_.pop_back(); | |
269 | } else { | |
270 | --num_stack_items_; | |
271 | } | |
272 | } | |
273 | ||
274 | void clear() { | |
275 | num_stack_items_ = 0; | |
276 | vect_.clear(); | |
277 | } | |
278 | ||
279 | // -- Copy and Assignment | |
280 | autovector& assign(const autovector& other); | |
281 | ||
282 | autovector(const autovector& other) { assign(other); } | |
283 | ||
284 | autovector& operator=(const autovector& other) { return assign(other); } | |
285 | ||
286 | // -- Iterator Operations | |
287 | iterator begin() { return iterator(this, 0); } | |
288 | ||
289 | const_iterator begin() const { return const_iterator(this, 0); } | |
290 | ||
291 | iterator end() { return iterator(this, this->size()); } | |
292 | ||
293 | const_iterator end() const { return const_iterator(this, this->size()); } | |
294 | ||
295 | reverse_iterator rbegin() { return reverse_iterator(end()); } | |
296 | ||
297 | const_reverse_iterator rbegin() const { | |
298 | return const_reverse_iterator(end()); | |
299 | } | |
300 | ||
301 | reverse_iterator rend() { return reverse_iterator(begin()); } | |
302 | ||
303 | const_reverse_iterator rend() const { | |
304 | return const_reverse_iterator(begin()); | |
305 | } | |
306 | ||
307 | private: | |
308 | size_type num_stack_items_ = 0; // current number of items | |
309 | value_type values_[kSize]; // the first `kSize` items | |
310 | // used only if there are more than `kSize` items. | |
311 | std::vector<T> vect_; | |
312 | }; | |
313 | ||
314 | template <class T, size_t kSize> | |
315 | autovector<T, kSize>& autovector<T, kSize>::assign(const autovector& other) { | |
316 | // copy the internal vector | |
317 | vect_.assign(other.vect_.begin(), other.vect_.end()); | |
318 | ||
319 | // copy array | |
320 | num_stack_items_ = other.num_stack_items_; | |
321 | std::copy(other.values_, other.values_ + num_stack_items_, values_); | |
322 | ||
323 | return *this; | |
324 | } | |
325 | #endif // ROCKSDB_LITE | |
326 | } // namespace rocksdb |