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