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