| 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 |
|
| 26 |
namespace spvtools { |
| 27 |
namespace 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. |
| 41 |
template <class T, size_t small_size> |
| 42 |
class 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_ |