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 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) const {
 100       return self_type(vect_, index_ - len);
 101     }
 102
 103     difference_type operator-(const self_type& other) const {
 104       assert(vect_ == other.vect_);
 105       return index_ - other.index_;
 106     }
 107
 108     self_type operator+(difference_type len) const {
 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
 128     const_reference operator*() const {
 129       assert(vect_->size() >= index_);
 130       return (*vect_)[index_];
 131     }
 132
 133     pointer operator->() {
 134       assert(vect_->size() >= index_);
 135       return &(*vect_)[index_];
 136     }
 137
 138     const_pointer operator->() const {
 139       assert(vect_->size() >= index_);
 140       return &(*vect_)[index_];
 141     }
 142
 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   typedef iterator_impl<autovector, value_type> iterator;
 178   typedef iterator_impl<const autovector, const value_type> const_iterator;
 179   typedef std::reverse_iterator<iterator> reverse_iterator;
 180   typedef std::reverse_iterator<const_iterator> const_reverse_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   const_reference operator[](size_type n) const {
 225     assert(n < size());
 226     if (n < kSize) {
 227       return values_[n];
 228     }
 229     return vect_[n - kSize];
 230   }
 231
 232   reference operator[](size_type n) {
 233     assert(n < size());
 234     if (n < kSize) {
 235       return values_[n];
 236     }
 237     return vect_[n - kSize];
 238   }
 239
 240   const_reference at(size_type n) const {
 241     assert(n < size());
 242     return (*this)[n];
 243   }
 244
 245   reference at(size_type n) {
 246     assert(n < size());
 247     return (*this)[n];
 248   }
 249
 250   reference front() {
 251     assert(!empty());
 252     return *begin();
 253   }
 254
 255   const_reference front() const {
 256     assert(!empty());
 257     return *begin();
 258   }
 259
 260   reference back() {
 261     assert(!empty());
 262     return *(end() - 1);
 263   }
 264
 265   const_reference back() const {
 266     assert(!empty());
 267     return *(end() - 1);
 268   }
 269
 270   // -- Mutable Operations
 271   void push_back(T&& item) {
 272     if (num_stack_items_ < kSize) {
 273       new ((void*)(&values_[num_stack_items_])) value_type();
 274       values_[num_stack_items_++] = std::move(item);
 275     } else {
 276       vect_.push_back(item);
 277     }
 278   }
 279
 280   void push_back(const T& item) {
 281     if (num_stack_items_ < kSize) {
 282       new ((void*)(&values_[num_stack_items_])) value_type();
 283       values_[num_stack_items_++] = item;
 284     } else {
 285       vect_.push_back(item);
 286     }
 287   }
 288
 289   template <class... Args>
 290   void emplace_back(Args&&... args) {
 291     if (num_stack_items_ < kSize) {
 292       new ((void*)(&values_[num_stack_items_++]))
 293           value_type(std::forward<Args>(args)...);
 294     } else {
 295       vect_.emplace_back(std::forward<Args>(args)...);
 296     }
 297   }
 298
 299   void pop_back() {
 300     assert(!empty());
 301     if (!vect_.empty()) {
 302       vect_.pop_back();
 303     } else {
 304       values_[--num_stack_items_].~value_type();
 305     }
 306   }
 307
 308   void clear() {
 309     while (num_stack_items_ > 0) {
 310       values_[--num_stack_items_].~value_type();
 311     }
 312     vect_.clear();
 313   }
 314
 315   // -- Copy and Assignment
 316   autovector& assign(const autovector& other);
 317
 318   autovector(const autovector& other) { assign(other); }
 319
 320   autovector& operator=(const autovector& other) { return assign(other); }
 321
 322   // -- Iterator Operations
 323   iterator begin() { return iterator(this, 0); }
 324
 325   const_iterator begin() const { return const_iterator(this, 0); }
 326
 327   iterator end() { return iterator(this, this->size()); }
 328
 329   const_iterator end() const { return const_iterator(this, this->size()); }
 330
 331   reverse_iterator rbegin() { return reverse_iterator(end()); }
 332
 333   const_reverse_iterator rbegin() const {
 334     return const_reverse_iterator(end());
 335   }
 336
 337   reverse_iterator rend() { return reverse_iterator(begin()); }
 338
 339   const_reverse_iterator rend() const {
 340     return const_reverse_iterator(begin());
 341   }
 342
 343  private:
 344   size_type num_stack_items_ = 0;  // current number of items
 345   alignas(alignof(
 346       value_type)) char buf_[kSize *
 347                              sizeof(value_type)];  // the first `kSize` items
 348   pointer values_;
 349   // used only if there are more than `kSize` items.
 350   std::vector<T> vect_;
 351 };
 352
 353 template <class T, size_t kSize>
 354 autovector<T, kSize>& autovector<T, kSize>::assign(const autovector& other) {
 355   values_ = reinterpret_cast<pointer>(buf_);
 356   // copy the internal vector
 357   vect_.assign(other.vect_.begin(), other.vect_.end());
 358
 359   // copy array
 360   num_stack_items_ = other.num_stack_items_;
 361   std::copy(other.values_, other.values_ + num_stack_items_, values_);
 362
 363   return *this;
 364 }
 365 #endif  // ROCKSDB_LITE
 366 }  // namespace rocksdb