OLD | NEW |
(Empty) | |
| 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_ |
OLD | NEW |