diff options
Diffstat (limited to 'deps/v8/src/utils.h')
-rw-r--r-- | deps/v8/src/utils.h | 213 |
1 files changed, 210 insertions, 3 deletions
diff --git a/deps/v8/src/utils.h b/deps/v8/src/utils.h index 2d0a1bfbd..d605891e6 100644 --- a/deps/v8/src/utils.h +++ b/deps/v8/src/utils.h @@ -326,9 +326,9 @@ class Vector { // Returns a vector using the same backing storage as this one, // spanning from and including 'from', to but not including 'to'. Vector<T> SubVector(int from, int to) { - ASSERT(from < length_); ASSERT(to <= length_); ASSERT(from < to); + ASSERT(0 <= from); return Vector<T>(start() + from, to - from); } @@ -476,6 +476,213 @@ inline Vector< Handle<Object> > HandleVector(v8::internal::Handle<T>* elms, } +/* + * A class that collects values into a backing store. + * Specialized versions of the class can allow access to the backing store + * in different ways. + * There is no guarantee that the backing store is contiguous (and, as a + * consequence, no guarantees that consecutively added elements are adjacent + * in memory). The collector may move elements unless it has guaranteed not + * to. + */ +template <typename T, int growth_factor = 2, int max_growth = 1 * MB> +class Collector { + public: + explicit Collector(int initial_capacity = kMinCapacity) + : index_(0), size_(0) { + if (initial_capacity < kMinCapacity) { + initial_capacity = kMinCapacity; + } + current_chunk_ = Vector<T>::New(initial_capacity); + } + + virtual ~Collector() { + // Free backing store (in reverse allocation order). + current_chunk_.Dispose(); + for (int i = chunks_.length() - 1; i >= 0; i--) { + chunks_.at(i).Dispose(); + } + } + + // Add a single element. + inline void Add(T value) { + if (index_ >= current_chunk_.length()) { + Grow(1); + } + current_chunk_[index_] = value; + index_++; + size_++; + } + + // Add a block of contiguous elements and return a Vector backed by the + // memory area. + // A basic Collector will keep this vector valid as long as the Collector + // is alive. + inline Vector<T> AddBlock(int size, T initial_value) { + ASSERT(size > 0); + if (size > current_chunk_.length() - index_) { + Grow(size); + } + T* position = current_chunk_.start() + index_; + index_ += size; + size_ += size; + for (int i = 0; i < size; i++) { + position[i] = initial_value; + } + return Vector<T>(position, size); + } + + + // Write the contents of the collector into the provided vector. + void WriteTo(Vector<T> destination) { + ASSERT(size_ <= destination.length()); + int position = 0; + for (int i = 0; i < chunks_.length(); i++) { + Vector<T> chunk = chunks_.at(i); + for (int j = 0; j < chunk.length(); j++) { + destination[position] = chunk[j]; + position++; + } + } + for (int i = 0; i < index_; i++) { + destination[position] = current_chunk_[i]; + position++; + } + } + + // Allocate a single contiguous vector, copy all the collected + // elements to the vector, and return it. + // The caller is responsible for freeing the memory of the returned + // vector (e.g., using Vector::Dispose). + Vector<T> ToVector() { + Vector<T> new_store = Vector<T>::New(size_); + WriteTo(new_store); + return new_store; + } + + // Resets the collector to be empty. + virtual void Reset() { + for (int i = chunks_.length() - 1; i >= 0; i--) { + chunks_.at(i).Dispose(); + } + chunks_.Rewind(0); + index_ = 0; + size_ = 0; + } + + // Total number of elements added to collector so far. + inline int size() { return size_; } + + protected: + static const int kMinCapacity = 16; + List<Vector<T> > chunks_; + Vector<T> current_chunk_; // Block of memory currently being written into. + int index_; // Current index in current chunk. + int size_; // Total number of elements in collector. + + // Creates a new current chunk, and stores the old chunk in the chunks_ list. + void Grow(int min_capacity) { + ASSERT(growth_factor > 1); + int growth = current_chunk_.length() * (growth_factor - 1); + if (growth > max_growth) { + growth = max_growth; + } + int new_capacity = current_chunk_.length() + growth; + if (new_capacity < min_capacity) { + new_capacity = min_capacity + growth; + } + Vector<T> new_chunk = Vector<T>::New(new_capacity); + int new_index = PrepareGrow(new_chunk); + if (index_ > 0) { + chunks_.Add(current_chunk_.SubVector(0, index_)); + } else { + // Can happen if the call to PrepareGrow moves everything into + // the new chunk. + current_chunk_.Dispose(); + } + current_chunk_ = new_chunk; + index_ = new_index; + ASSERT(index_ + min_capacity <= current_chunk_.length()); + } + + // Before replacing the current chunk, give a subclass the option to move + // some of the current data into the new chunk. The function may update + // the current index_ value to represent data no longer in the current chunk. + // Returns the initial index of the new chunk (after copied data). + virtual int PrepareGrow(Vector<T> new_chunk) { + return 0; + } +}; + + +/* + * A collector that allows sequences of values to be guaranteed to + * stay consecutive. + * If the backing store grows while a sequence is active, the current + * sequence might be moved, but after the sequence is ended, it will + * not move again. + * NOTICE: Blocks allocated using Collector::AddBlock(int) can move + * as well, if inside an active sequence where another element is added. + */ +template <typename T, int growth_factor = 2, int max_growth = 1 * MB> +class SequenceCollector : public Collector<T, growth_factor, max_growth> { + public: + explicit SequenceCollector(int initial_capacity) + : Collector<T, growth_factor, max_growth>(initial_capacity), + sequence_start_(kNoSequence) { } + + virtual ~SequenceCollector() {} + + void StartSequence() { + ASSERT(sequence_start_ == kNoSequence); + sequence_start_ = this->index_; + } + + Vector<T> EndSequence() { + ASSERT(sequence_start_ != kNoSequence); + int sequence_start = sequence_start_; + sequence_start_ = kNoSequence; + if (sequence_start == this->index_) return Vector<T>(); + return this->current_chunk_.SubVector(sequence_start, this->index_); + } + + // Drops the currently added sequence, and all collected elements in it. + void DropSequence() { + ASSERT(sequence_start_ != kNoSequence); + int sequence_length = this->index_ - sequence_start_; + this->index_ = sequence_start_; + this->size_ -= sequence_length; + sequence_start_ = kNoSequence; + } + + virtual void Reset() { + sequence_start_ = kNoSequence; + this->Collector<T, growth_factor, max_growth>::Reset(); + } + + private: + static const int kNoSequence = -1; + int sequence_start_; + + // Move the currently active sequence to the new chunk. + virtual int PrepareGrow(Vector<T> new_chunk) { + if (sequence_start_ != kNoSequence) { + int sequence_length = this->index_ - sequence_start_; + // The new chunk is always larger than the current chunk, so there + // is room for the copy. + ASSERT(sequence_length < new_chunk.length()); + for (int i = 0; i < sequence_length; i++) { + new_chunk[i] = this->current_chunk_[sequence_start_ + i]; + } + this->index_ = sequence_start_; + sequence_start_ = 0; + return sequence_length; + } + return 0; + } +}; + + // Simple support to read a file into a 0-terminated C-string. // The returned buffer must be freed by the caller. // On return, *exits tells whether the file existed. @@ -740,8 +947,8 @@ inline Dest BitCast(const Source& source) { } template <class Dest, class Source> -inline Dest BitCast(Source* & source) { - return BitCast<Dest>(reinterpret_cast<uintptr_t>(source)); +inline Dest BitCast(Source* source) { + return BitCast<Dest>(reinterpret_cast<uintptr_t>(source)); } } } // namespace v8::internal |