Ben Murdoch | da12d29 | 2016-06-02 14:46:10 +0100 | [diff] [blame] | 1 | // Copyright 2016 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_COLLECTOR_H_ |
| 6 | #define V8_COLLECTOR_H_ |
| 7 | |
| 8 | #include "src/checks.h" |
| 9 | #include "src/list.h" |
| 10 | #include "src/vector.h" |
| 11 | |
| 12 | namespace v8 { |
| 13 | namespace internal { |
| 14 | |
| 15 | /* |
| 16 | * A class that collects values into a backing store. |
| 17 | * Specialized versions of the class can allow access to the backing store |
| 18 | * in different ways. |
| 19 | * There is no guarantee that the backing store is contiguous (and, as a |
| 20 | * consequence, no guarantees that consecutively added elements are adjacent |
| 21 | * in memory). The collector may move elements unless it has guaranteed not |
| 22 | * to. |
| 23 | */ |
| 24 | template <typename T, int growth_factor = 2, int max_growth = 1 * MB> |
| 25 | class Collector { |
| 26 | public: |
| 27 | explicit Collector(int initial_capacity = kMinCapacity) |
| 28 | : index_(0), size_(0) { |
| 29 | current_chunk_ = Vector<T>::New(initial_capacity); |
| 30 | } |
| 31 | |
| 32 | virtual ~Collector() { |
| 33 | // Free backing store (in reverse allocation order). |
| 34 | current_chunk_.Dispose(); |
| 35 | for (int i = chunks_.length() - 1; i >= 0; i--) { |
| 36 | chunks_.at(i).Dispose(); |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | // Add a single element. |
| 41 | inline void Add(T value) { |
| 42 | if (index_ >= current_chunk_.length()) { |
| 43 | Grow(1); |
| 44 | } |
| 45 | current_chunk_[index_] = value; |
| 46 | index_++; |
| 47 | size_++; |
| 48 | } |
| 49 | |
| 50 | // Add a block of contiguous elements and return a Vector backed by the |
| 51 | // memory area. |
| 52 | // A basic Collector will keep this vector valid as long as the Collector |
| 53 | // is alive. |
| 54 | inline Vector<T> AddBlock(int size, T initial_value) { |
| 55 | DCHECK(size > 0); |
| 56 | if (size > current_chunk_.length() - index_) { |
| 57 | Grow(size); |
| 58 | } |
| 59 | T* position = current_chunk_.start() + index_; |
| 60 | index_ += size; |
| 61 | size_ += size; |
| 62 | for (int i = 0; i < size; i++) { |
| 63 | position[i] = initial_value; |
| 64 | } |
| 65 | return Vector<T>(position, size); |
| 66 | } |
| 67 | |
| 68 | // Add a contiguous block of elements and return a vector backed |
| 69 | // by the added block. |
| 70 | // A basic Collector will keep this vector valid as long as the Collector |
| 71 | // is alive. |
| 72 | inline Vector<T> AddBlock(Vector<const T> source) { |
| 73 | if (source.length() > current_chunk_.length() - index_) { |
| 74 | Grow(source.length()); |
| 75 | } |
| 76 | T* position = current_chunk_.start() + index_; |
| 77 | index_ += source.length(); |
| 78 | size_ += source.length(); |
| 79 | for (int i = 0; i < source.length(); i++) { |
| 80 | position[i] = source[i]; |
| 81 | } |
| 82 | return Vector<T>(position, source.length()); |
| 83 | } |
| 84 | |
| 85 | // Write the contents of the collector into the provided vector. |
| 86 | void WriteTo(Vector<T> destination) { |
| 87 | DCHECK(size_ <= destination.length()); |
| 88 | int position = 0; |
| 89 | for (int i = 0; i < chunks_.length(); i++) { |
| 90 | Vector<T> chunk = chunks_.at(i); |
| 91 | for (int j = 0; j < chunk.length(); j++) { |
| 92 | destination[position] = chunk[j]; |
| 93 | position++; |
| 94 | } |
| 95 | } |
| 96 | for (int i = 0; i < index_; i++) { |
| 97 | destination[position] = current_chunk_[i]; |
| 98 | position++; |
| 99 | } |
| 100 | } |
| 101 | |
| 102 | // Allocate a single contiguous vector, copy all the collected |
| 103 | // elements to the vector, and return it. |
| 104 | // The caller is responsible for freeing the memory of the returned |
| 105 | // vector (e.g., using Vector::Dispose). |
| 106 | Vector<T> ToVector() { |
| 107 | Vector<T> new_store = Vector<T>::New(size_); |
| 108 | WriteTo(new_store); |
| 109 | return new_store; |
| 110 | } |
| 111 | |
| 112 | // Resets the collector to be empty. |
| 113 | virtual void Reset() { |
| 114 | for (int i = chunks_.length() - 1; i >= 0; i--) { |
| 115 | chunks_.at(i).Dispose(); |
| 116 | } |
| 117 | chunks_.Rewind(0); |
| 118 | index_ = 0; |
| 119 | size_ = 0; |
| 120 | } |
| 121 | |
| 122 | // Total number of elements added to collector so far. |
| 123 | inline int size() { return size_; } |
| 124 | |
| 125 | protected: |
| 126 | static const int kMinCapacity = 16; |
| 127 | List<Vector<T> > chunks_; |
| 128 | Vector<T> current_chunk_; // Block of memory currently being written into. |
| 129 | int index_; // Current index in current chunk. |
| 130 | int size_; // Total number of elements in collector. |
| 131 | |
| 132 | // Creates a new current chunk, and stores the old chunk in the chunks_ list. |
| 133 | void Grow(int min_capacity) { |
| 134 | DCHECK(growth_factor > 1); |
| 135 | int new_capacity; |
| 136 | int current_length = current_chunk_.length(); |
| 137 | if (current_length < kMinCapacity) { |
| 138 | // The collector started out as empty. |
| 139 | new_capacity = min_capacity * growth_factor; |
| 140 | if (new_capacity < kMinCapacity) new_capacity = kMinCapacity; |
| 141 | } else { |
| 142 | int growth = current_length * (growth_factor - 1); |
| 143 | if (growth > max_growth) { |
| 144 | growth = max_growth; |
| 145 | } |
| 146 | new_capacity = current_length + growth; |
| 147 | if (new_capacity < min_capacity) { |
| 148 | new_capacity = min_capacity + growth; |
| 149 | } |
| 150 | } |
| 151 | NewChunk(new_capacity); |
| 152 | DCHECK(index_ + min_capacity <= current_chunk_.length()); |
| 153 | } |
| 154 | |
| 155 | // Before replacing the current chunk, give a subclass the option to move |
| 156 | // some of the current data into the new chunk. The function may update |
| 157 | // the current index_ value to represent data no longer in the current chunk. |
| 158 | // Returns the initial index of the new chunk (after copied data). |
| 159 | virtual void NewChunk(int new_capacity) { |
| 160 | Vector<T> new_chunk = Vector<T>::New(new_capacity); |
| 161 | if (index_ > 0) { |
| 162 | chunks_.Add(current_chunk_.SubVector(0, index_)); |
| 163 | } else { |
| 164 | current_chunk_.Dispose(); |
| 165 | } |
| 166 | current_chunk_ = new_chunk; |
| 167 | index_ = 0; |
| 168 | } |
| 169 | }; |
| 170 | |
| 171 | /* |
| 172 | * A collector that allows sequences of values to be guaranteed to |
| 173 | * stay consecutive. |
| 174 | * If the backing store grows while a sequence is active, the current |
| 175 | * sequence might be moved, but after the sequence is ended, it will |
| 176 | * not move again. |
| 177 | * NOTICE: Blocks allocated using Collector::AddBlock(int) can move |
| 178 | * as well, if inside an active sequence where another element is added. |
| 179 | */ |
| 180 | template <typename T, int growth_factor = 2, int max_growth = 1 * MB> |
| 181 | class SequenceCollector : public Collector<T, growth_factor, max_growth> { |
| 182 | public: |
| 183 | explicit SequenceCollector(int initial_capacity) |
| 184 | : Collector<T, growth_factor, max_growth>(initial_capacity), |
| 185 | sequence_start_(kNoSequence) {} |
| 186 | |
| 187 | virtual ~SequenceCollector() {} |
| 188 | |
| 189 | void StartSequence() { |
| 190 | DCHECK(sequence_start_ == kNoSequence); |
| 191 | sequence_start_ = this->index_; |
| 192 | } |
| 193 | |
| 194 | Vector<T> EndSequence() { |
| 195 | DCHECK(sequence_start_ != kNoSequence); |
| 196 | int sequence_start = sequence_start_; |
| 197 | sequence_start_ = kNoSequence; |
| 198 | if (sequence_start == this->index_) return Vector<T>(); |
| 199 | return this->current_chunk_.SubVector(sequence_start, this->index_); |
| 200 | } |
| 201 | |
| 202 | // Drops the currently added sequence, and all collected elements in it. |
| 203 | void DropSequence() { |
| 204 | DCHECK(sequence_start_ != kNoSequence); |
| 205 | int sequence_length = this->index_ - sequence_start_; |
| 206 | this->index_ = sequence_start_; |
| 207 | this->size_ -= sequence_length; |
| 208 | sequence_start_ = kNoSequence; |
| 209 | } |
| 210 | |
| 211 | virtual void Reset() { |
| 212 | sequence_start_ = kNoSequence; |
| 213 | this->Collector<T, growth_factor, max_growth>::Reset(); |
| 214 | } |
| 215 | |
| 216 | private: |
| 217 | static const int kNoSequence = -1; |
| 218 | int sequence_start_; |
| 219 | |
| 220 | // Move the currently active sequence to the new chunk. |
| 221 | virtual void NewChunk(int new_capacity) { |
| 222 | if (sequence_start_ == kNoSequence) { |
| 223 | // Fall back on default behavior if no sequence has been started. |
| 224 | this->Collector<T, growth_factor, max_growth>::NewChunk(new_capacity); |
| 225 | return; |
| 226 | } |
| 227 | int sequence_length = this->index_ - sequence_start_; |
| 228 | Vector<T> new_chunk = Vector<T>::New(sequence_length + new_capacity); |
| 229 | DCHECK(sequence_length < new_chunk.length()); |
| 230 | for (int i = 0; i < sequence_length; i++) { |
| 231 | new_chunk[i] = this->current_chunk_[sequence_start_ + i]; |
| 232 | } |
| 233 | if (sequence_start_ > 0) { |
| 234 | this->chunks_.Add(this->current_chunk_.SubVector(0, sequence_start_)); |
| 235 | } else { |
| 236 | this->current_chunk_.Dispose(); |
| 237 | } |
| 238 | this->current_chunk_ = new_chunk; |
| 239 | this->index_ = sequence_length; |
| 240 | sequence_start_ = 0; |
| 241 | } |
| 242 | }; |
| 243 | |
| 244 | } // namespace internal |
| 245 | } // namespace v8 |
| 246 | |
| 247 | #endif // V8_COLLECTOR_H_ |