ceph/src/rocksdb/util/autovector.h

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