Line data    Source code

       1             : // Copyright 2018 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #ifndef V8_BASE_SMALL_VECTOR_H_
       6             : #define V8_BASE_SMALL_VECTOR_H_
       7             : 
       8             : #include <type_traits>
       9             : 
      10             : #include "src/base/bits.h"
      11             : #include "src/base/macros.h"
      12             : 
      13             : namespace v8 {
      14             : namespace base {
      15             : 
      16             : // Minimal SmallVector implementation. Uses inline storage first, switches to
      17             : // malloc when it overflows.
      18             : template <typename T, size_t kSize>
      19             : class SmallVector {
      20             :   // Currently only support trivially copyable and trivially destructible data
      21             :   // types, as it uses memcpy to copy elements and never calls destructors.
      22             :   ASSERT_TRIVIALLY_COPYABLE(T);
      23             :   STATIC_ASSERT(std::is_trivially_destructible<T>::value);
      24             : 
      25             :  public:
      26             :   static constexpr size_t kInlineSize = kSize;
      27             : 
      28     2275591 :   SmallVector() = default;
      29       13108 :   explicit SmallVector(size_t size) { resize_no_init(size); }
      30             :   SmallVector(const SmallVector& other) V8_NOEXCEPT { *this = other; }
      31      151380 :   SmallVector(SmallVector&& other) V8_NOEXCEPT { *this = std::move(other); }
      32             : 
      33             :   ~SmallVector() {
      34     1329966 :     if (is_big()) free(begin_);
      35     1329966 :   }
      36             : 
      37       56314 :   SmallVector& operator=(const SmallVector& other) V8_NOEXCEPT {
      38       56314 :     if (this == &other) return *this;
      39             :     size_t other_size = other.size();
      40       56316 :     if (capacity() < other_size) {
      41             :       // Create large-enough heap-allocated storage.
      42          12 :       if (is_big()) free(begin_);
      43          12 :       begin_ = reinterpret_cast<T*>(malloc(sizeof(T) * other_size));
      44          12 :       end_of_storage_ = begin_ + other_size;
      45             :     }
      46       56316 :     memcpy(begin_, other.begin_, sizeof(T) * other_size);
      47       56316 :     end_ = begin_ + other_size;
      48       56316 :     return *this;
      49             :   }
      50             : 
      51       75689 :   SmallVector& operator=(SmallVector&& other) V8_NOEXCEPT {
      52       75689 :     if (this == &other) return *this;
      53       75689 :     if (other.is_big()) {
      54           0 :       if (is_big()) free(begin_);
      55           0 :       begin_ = other.begin_;
      56           0 :       end_ = other.end_;
      57           0 :       end_of_storage_ = other.end_of_storage_;
      58             :       other.reset();
      59             :     } else {
      60             :       DCHECK_GE(capacity(), other.size());  // Sanity check.
      61             :       size_t other_size = other.size();
      62       75689 :       memcpy(begin_, other.begin_, sizeof(T) * other_size);
      63       75689 :       end_ = begin_ + other_size;
      64             :     }
      65             :     return *this;
      66             :   }
      67             : 
      68             :   T* data() { return begin_; }
      69             :   const T* data() const { return begin_; }
      70             : 
      71             :   T* begin() { return begin_; }
      72             :   const T* begin() const { return begin_; }
      73             : 
      74             :   T* end() { return end_; }
      75             :   const T* end() const { return end_; }
      76             : 
      77     1505257 :   size_t size() const { return end_ - begin_; }
      78             :   bool empty() const { return end_ == begin_; }
      79      243057 :   size_t capacity() const { return end_of_storage_ - begin_; }
      80             : 
      81             :   T& back() {
      82             :     DCHECK_NE(0, size());
      83      404657 :     return end_[-1];
      84             :   }
      85             : 
      86             :   T& operator[](size_t index) {
      87             :     DCHECK_GT(size(), index);
      88     2586441 :     return begin_[index];
      89             :   }
      90             : 
      91             :   const T& operator[](size_t index) const {
      92             :     DCHECK_GT(size(), index);
      93       19739 :     return begin_[index];
      94             :   }
      95             : 
      96             :   template <typename... Args>
      97     2211592 :   void emplace_back(Args&&... args) {
      98     2211592 :     if (V8_UNLIKELY(end_ == end_of_storage_)) Grow();
      99     2211690 :     new (end_) T(std::forward<Args>(args)...);
     100     2211690 :     ++end_;
     101     2211690 :   }
     102             : 
     103             :   void pop_back(size_t count = 1) {
     104             :     DCHECK_GE(size(), count);
     105     1529738 :     end_ -= count;
     106             :   }
     107             : 
     108       66332 :   void resize_no_init(size_t new_size) {
     109             :     // Resizing without initialization is safe if T is trivially copyable.
     110             :     ASSERT_TRIVIALLY_COPYABLE(T);
     111      280721 :     if (new_size > capacity()) Grow(new_size);
     112      280721 :     end_ = begin_ + new_size;
     113       66332 :   }
     114             : 
     115             :   // Clear without freeing any storage.
     116             :   void clear() { end_ = begin_; }
     117             : 
     118             :   // Clear and go back to inline storage.
     119             :   void reset() {
     120           0 :     begin_ = inline_storage_begin();
     121           0 :     end_ = begin_;
     122           0 :     end_of_storage_ = begin_ + kInlineSize;
     123             :   }
     124             : 
     125             :  private:
     126             :   T* begin_ = inline_storage_begin();
     127             :   T* end_ = begin_;
     128     1109780 :   T* end_of_storage_ = begin_ + kInlineSize;
     129             :   typename std::aligned_storage<sizeof(T) * kInlineSize, alignof(T)>::type
     130             :       inline_storage_;
     131             : 
     132       13147 :   void Grow(size_t min_capacity = 0) {
     133       13147 :     size_t in_use = end_ - begin_;
     134             :     size_t new_capacity =
     135       39441 :         base::bits::RoundUpToPowerOfTwo(std::max(min_capacity, 2 * capacity()));
     136       13147 :     T* new_storage = reinterpret_cast<T*>(malloc(sizeof(T) * new_capacity));
     137       13147 :     memcpy(new_storage, begin_, sizeof(T) * in_use);
     138       13147 :     if (is_big()) free(begin_);
     139       13147 :     begin_ = new_storage;
     140       13147 :     end_ = new_storage + in_use;
     141       13147 :     end_of_storage_ = new_storage + new_capacity;
     142       13147 :   }
     143             : 
     144     1405655 :   bool is_big() const { return begin_ != inline_storage_begin(); }
     145             : 
     146     1109780 :   T* inline_storage_begin() { return reinterpret_cast<T*>(&inline_storage_); }
     147             :   const T* inline_storage_begin() const {
     148     1144669 :     return reinterpret_cast<const T*>(&inline_storage_);
     149             :   }
     150             : };
     151             : 
     152             : }  // namespace base
     153             : }  // namespace v8
     154             : 
     155             : #endif  // V8_BASE_SMALL_VECTOR_H_