1// Copyright (c) 2018 Google LLC
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_UTIL_SMALL_VECTOR_H_
16#define SOURCE_UTIL_SMALL_VECTOR_H_
17
18#include <cassert>
19#include <iostream>
20#include <memory>
21#include <utility>
22#include <vector>
23
24#include "source/util/make_unique.h"
25
26namespace spvtools {
27namespace utils {
28
29// The |SmallVector| class is intended to be a drop-in replacement for
30// |std::vector|. The difference is in the implementation. A |SmallVector| is
31// optimized for when the number of elements in the vector are small. Small is
32// defined by the template parameter |small_size|.
33//
34// Note that |SmallVector| is not always faster than an |std::vector|, so you
35// should experiment with different values for |small_size| and compare to
36// using and |std::vector|.
37//
38// TODO: I have implemented the public member functions from |std::vector| that
39// I needed. If others are needed they should be implemented. Do not implement
40// public member functions that are not defined by std::vector.
41template <class T, size_t small_size>
42class SmallVector {
43 public:
44 using iterator = T*;
45 using const_iterator = const T*;
46
47 SmallVector()
48 : size_(0),
49 small_data_(reinterpret_cast<T*>(buffer)),
50 large_data_(nullptr) {}
51
52 SmallVector(const SmallVector& that) : SmallVector() { *this = that; }
53
54 SmallVector(SmallVector&& that) : SmallVector() { *this = std::move(that); }
55
56 SmallVector(const std::vector<T>& vec) : SmallVector() {
57 if (vec.size() > small_size) {
58 large_data_ = MakeUnique<std::vector<T>>(vec);
59 } else {
60 size_ = vec.size();
61 for (uint32_t i = 0; i < size_; i++) {
62 new (small_data_ + i) T(vec[i]);
63 }
64 }
65 }
66
67 SmallVector(std::vector<T>&& vec) : SmallVector() {
68 if (vec.size() > small_size) {
69 large_data_ = MakeUnique<std::vector<T>>(std::move(vec));
70 } else {
71 size_ = vec.size();
72 for (uint32_t i = 0; i < size_; i++) {
73 new (small_data_ + i) T(std::move(vec[i]));
74 }
75 }
76 vec.clear();
77 }
78
79 SmallVector(std::initializer_list<T> init_list) : SmallVector() {
80 if (init_list.size() < small_size) {
81 for (auto it = init_list.begin(); it != init_list.end(); ++it) {
82 new (small_data_ + (size_++)) T(std::move(*it));
83 }
84 } else {
85 large_data_ = MakeUnique<std::vector<T>>(std::move(init_list));
86 }
87 }
88
89 SmallVector(size_t s, const T& v) : SmallVector() { resize(s, v); }
90
91 virtual ~SmallVector() {
92 for (T* p = small_data_; p < small_data_ + size_; ++p) {
93 p->~T();
94 }
95 }
96
97 SmallVector& operator=(const SmallVector& that) {
98 assert(small_data_);
99 if (that.large_data_) {
100 if (large_data_) {
101 *large_data_ = *that.large_data_;
102 } else {
103 large_data_ = MakeUnique<std::vector<T>>(*that.large_data_);
104 }
105 } else {
106 large_data_.reset(nullptr);
107 size_t i = 0;
108 // Do a copy for any element in |this| that is already constructed.
109 for (; i < size_ && i < that.size_; ++i) {
110 small_data_[i] = that.small_data_[i];
111 }
112
113 if (i >= that.size_) {
114 // If the size of |this| becomes smaller after the assignment, then
115 // destroy any extra elements.
116 for (; i < size_; ++i) {
117 small_data_[i].~T();
118 }
119 } else {
120 // If the size of |this| becomes larger after the assignement, copy
121 // construct the new elements that are needed.
122 for (; i < that.size_; ++i) {
123 new (small_data_ + i) T(that.small_data_[i]);
124 }
125 }
126 size_ = that.size_;
127 }
128 return *this;
129 }
130
131 SmallVector& operator=(SmallVector&& that) {
132 if (that.large_data_) {
133 large_data_.reset(that.large_data_.release());
134 } else {
135 large_data_.reset(nullptr);
136 size_t i = 0;
137 // Do a move for any element in |this| that is already constructed.
138 for (; i < size_ && i < that.size_; ++i) {
139 small_data_[i] = std::move(that.small_data_[i]);
140 }
141
142 if (i >= that.size_) {
143 // If the size of |this| becomes smaller after the assignment, then
144 // destroy any extra elements.
145 for (; i < size_; ++i) {
146 small_data_[i].~T();
147 }
148 } else {
149 // If the size of |this| becomes larger after the assignement, move
150 // construct the new elements that are needed.
151 for (; i < that.size_; ++i) {
152 new (small_data_ + i) T(std::move(that.small_data_[i]));
153 }
154 }
155 size_ = that.size_;
156 }
157
158 // Reset |that| because all of the data has been moved to |this|.
159 that.DestructSmallData();
160 return *this;
161 }
162
163 template <class OtherVector>
164 friend bool operator==(const SmallVector& lhs, const OtherVector& rhs) {
165 if (lhs.size() != rhs.size()) {
166 return false;
167 }
168
169 auto rit = rhs.begin();
170 for (auto lit = lhs.begin(); lit != lhs.end(); ++lit, ++rit) {
171 if (*lit != *rit) {
172 return false;
173 }
174 }
175 return true;
176 }
177
178 friend bool operator==(const std::vector<T>& lhs, const SmallVector& rhs) {
179 return rhs == lhs;
180 }
181
182 friend bool operator!=(const SmallVector& lhs, const std::vector<T>& rhs) {
183 return !(lhs == rhs);
184 }
185
186 friend bool operator!=(const std::vector<T>& lhs, const SmallVector& rhs) {
187 return rhs != lhs;
188 }
189
190 T& operator[](size_t i) {
191 if (!large_data_) {
192 return small_data_[i];
193 } else {
194 return (*large_data_)[i];
195 }
196 }
197
198 const T& operator[](size_t i) const {
199 if (!large_data_) {
200 return small_data_[i];
201 } else {
202 return (*large_data_)[i];
203 }
204 }
205
206 size_t size() const {
207 if (!large_data_) {
208 return size_;
209 } else {
210 return large_data_->size();
211 }
212 }
213
214 iterator begin() {
215 if (large_data_) {
216 return large_data_->data();
217 } else {
218 return small_data_;
219 }
220 }
221
222 const_iterator begin() const {
223 if (large_data_) {
224 return large_data_->data();
225 } else {
226 return small_data_;
227 }
228 }
229
230 const_iterator cbegin() const { return begin(); }
231
232 iterator end() {
233 if (large_data_) {
234 return large_data_->data() + large_data_->size();
235 } else {
236 return small_data_ + size_;
237 }
238 }
239
240 const_iterator end() const {
241 if (large_data_) {
242 return large_data_->data() + large_data_->size();
243 } else {
244 return small_data_ + size_;
245 }
246 }
247
248 const_iterator cend() const { return end(); }
249
250 T* data() { return begin(); }
251
252 const T* data() const { return cbegin(); }
253
254 T& front() { return (*this)[0]; }
255
256 const T& front() const { return (*this)[0]; }
257
258 iterator erase(const_iterator pos) { return erase(pos, pos + 1); }
259
260 iterator erase(const_iterator first, const_iterator last) {
261 if (large_data_) {
262 size_t start_index = first - large_data_->data();
263 size_t end_index = last - large_data_->data();
264 auto r = large_data_->erase(large_data_->begin() + start_index,
265 large_data_->begin() + end_index);
266 return large_data_->data() + (r - large_data_->begin());
267 }
268
269 // Since C++11, std::vector has |const_iterator| for the parameters, so I
270 // follow that. However, I need iterators to modify the current container,
271 // which is not const. This is why I cast away the const.
272 iterator f = const_cast<iterator>(first);
273 iterator l = const_cast<iterator>(last);
274 iterator e = end();
275
276 size_t num_of_del_elements = last - first;
277 iterator ret = f;
278 if (first == last) {
279 return ret;
280 }
281
282 // Move |last| and any elements after it their earlier position.
283 while (l != e) {
284 *f = std::move(*l);
285 ++f;
286 ++l;
287 }
288
289 // Destroy the elements that were supposed to be deleted.
290 while (f != l) {
291 f->~T();
292 ++f;
293 }
294
295 // Update the size.
296 size_ -= num_of_del_elements;
297 return ret;
298 }
299
300 void push_back(const T& value) {
301 if (!large_data_ && size_ == small_size) {
302 MoveToLargeData();
303 }
304
305 if (large_data_) {
306 large_data_->push_back(value);
307 return;
308 }
309
310 new (small_data_ + size_) T(value);
311 ++size_;
312 }
313
314 void push_back(T&& value) {
315 if (!large_data_ && size_ == small_size) {
316 MoveToLargeData();
317 }
318
319 if (large_data_) {
320 large_data_->push_back(std::move(value));
321 return;
322 }
323
324 new (small_data_ + size_) T(std::move(value));
325 ++size_;
326 }
327
328 template <class InputIt>
329 iterator insert(iterator pos, InputIt first, InputIt last) {
330 size_t element_idx = (pos - begin());
331 size_t num_of_new_elements = std::distance(first, last);
332 size_t new_size = size_ + num_of_new_elements;
333 if (!large_data_ && new_size > small_size) {
334 MoveToLargeData();
335 }
336
337 if (large_data_) {
338 typename std::vector<T>::iterator new_pos =
339 large_data_->begin() + element_idx;
340 large_data_->insert(new_pos, first, last);
341 return begin() + element_idx;
342 }
343
344 // Move |pos| and all of the elements after it over |num_of_new_elements|
345 // places. We start at the end and work backwards, to make sure we do not
346 // overwrite data that we have not moved yet.
347 for (iterator i = begin() + new_size - 1, j = end() - 1; j >= pos;
348 --i, --j) {
349 if (i >= begin() + size_) {
350 new (i) T(std::move(*j));
351 } else {
352 *i = std::move(*j);
353 }
354 }
355
356 // Copy the new elements into position.
357 iterator p = pos;
358 for (; first != last; ++p, ++first) {
359 if (p >= small_data_ + size_) {
360 new (p) T(*first);
361 } else {
362 *p = *first;
363 }
364 }
365
366 // Upate the size.
367 size_ += num_of_new_elements;
368 return pos;
369 }
370
371 bool empty() const {
372 if (large_data_) {
373 return large_data_->empty();
374 }
375 return size_ == 0;
376 }
377
378 void clear() {
379 if (large_data_) {
380 large_data_->clear();
381 } else {
382 DestructSmallData();
383 }
384 }
385
386 template <class... Args>
387 void emplace_back(Args&&... args) {
388 if (!large_data_ && size_ == small_size) {
389 MoveToLargeData();
390 }
391
392 if (large_data_) {
393 large_data_->emplace_back(std::forward<Args>(args)...);
394 } else {
395 new (small_data_ + size_) T(std::forward<Args>(args)...);
396 ++size_;
397 }
398 }
399
400 void resize(size_t new_size, const T& v) {
401 if (!large_data_ && new_size > small_size) {
402 MoveToLargeData();
403 }
404
405 if (large_data_) {
406 large_data_->resize(new_size, v);
407 return;
408 }
409
410 // If |new_size| < |size_|, then destroy the extra elements.
411 for (size_t i = new_size; i < size_; ++i) {
412 small_data_[i].~T();
413 }
414
415 // If |new_size| > |size_|, the copy construct the new elements.
416 for (size_t i = size_; i < new_size; ++i) {
417 new (small_data_ + i) T(v);
418 }
419
420 // Update the size.
421 size_ = new_size;
422 }
423
424 private:
425 // Moves all of the element from |small_data_| into a new std::vector that can
426 // be access through |large_data|.
427 void MoveToLargeData() {
428 assert(!large_data_);
429 large_data_ = MakeUnique<std::vector<T>>();
430 for (size_t i = 0; i < size_; ++i) {
431 large_data_->emplace_back(std::move(small_data_[i]));
432 }
433 DestructSmallData();
434 }
435
436 // Destroys all of the elements in |small_data_| that have been constructed.
437 void DestructSmallData() {
438 for (size_t i = 0; i < size_; ++i) {
439 small_data_[i].~T();
440 }
441 size_ = 0;
442 }
443
444 // The number of elements in |small_data_| that have been constructed.
445 size_t size_;
446
447 // The pointed used to access the array of elements when the number of
448 // elements is small.
449 T* small_data_;
450
451 // The actual data used to store the array elements. It must never be used
452 // directly, but must only be accesed through |small_data_|.
453 typename std::aligned_storage<sizeof(T), std::alignment_of<T>::value>::type
454 buffer[small_size];
455
456 // A pointer to a vector that is used to store the elements of the vector when
457 // this size exceeds |small_size|. If |large_data_| is nullptr, then the data
458 // is stored in |small_data_|. Otherwise, the data is stored in
459 // |large_data_|.
460 std::unique_ptr<std::vector<T>> large_data_;
461}; // namespace utils
462
463} // namespace utils
464} // namespace spvtools
465
466#endif // SOURCE_UTIL_SMALL_VECTOR_H_
467