OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 308 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
319 ASSERT(length == 0 || (length > 0 && data != NULL)); | 319 ASSERT(length == 0 || (length > 0 && data != NULL)); |
320 } | 320 } |
321 | 321 |
322 static Vector<T> New(int length) { | 322 static Vector<T> New(int length) { |
323 return Vector<T>(NewArray<T>(length), length); | 323 return Vector<T>(NewArray<T>(length), length); |
324 } | 324 } |
325 | 325 |
326 // Returns a vector using the same backing storage as this one, | 326 // Returns a vector using the same backing storage as this one, |
327 // spanning from and including 'from', to but not including 'to'. | 327 // spanning from and including 'from', to but not including 'to'. |
328 Vector<T> SubVector(int from, int to) { | 328 Vector<T> SubVector(int from, int to) { |
329 ASSERT(from < length_); | |
330 ASSERT(to <= length_); | 329 ASSERT(to <= length_); |
331 ASSERT(from < to); | 330 ASSERT(from < to); |
| 331 ASSERT(0 <= from); |
332 return Vector<T>(start() + from, to - from); | 332 return Vector<T>(start() + from, to - from); |
333 } | 333 } |
334 | 334 |
335 // Returns the length of the vector. | 335 // Returns the length of the vector. |
336 int length() const { return length_; } | 336 int length() const { return length_; } |
337 | 337 |
338 // Returns whether or not the vector is empty. | 338 // Returns whether or not the vector is empty. |
339 bool is_empty() const { return length_ == 0; } | 339 bool is_empty() const { return length_ == 0; } |
340 | 340 |
341 // Returns the pointer to the start of the data in the vector. | 341 // Returns the pointer to the start of the data in the vector. |
(...skipping 136 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
478 | 478 |
479 /* | 479 /* |
480 * A class that collects values into a backing store. | 480 * A class that collects values into a backing store. |
481 * Specialized versions of the class can allow access to the backing store | 481 * Specialized versions of the class can allow access to the backing store |
482 * in different ways. | 482 * in different ways. |
483 * There is no guarantee that the backing store is contiguous (and, as a | 483 * There is no guarantee that the backing store is contiguous (and, as a |
484 * consequence, no guarantees that consecutively added elements are adjacent | 484 * consequence, no guarantees that consecutively added elements are adjacent |
485 * in memory). The collector may move elements unless it has guaranteed not | 485 * in memory). The collector may move elements unless it has guaranteed not |
486 * to. | 486 * to. |
487 */ | 487 */ |
488 template <typename T> | 488 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> |
489 class Collector { | 489 class Collector { |
490 public: | 490 public: |
491 Collector(int initial_capacity = kMinCapacity, | 491 explicit Collector(int initial_capacity = kMinCapacity) |
492 int growth_factor = 2, | 492 : index_(0), size_(0) { |
493 int max_growth = 1 * MB) | |
494 : growth_factor_(growth_factor), max_growth_(max_growth) { | |
495 if (initial_capacity < kMinCapacity) { | 493 if (initial_capacity < kMinCapacity) { |
496 initial_capacity = kMinCapacity; | 494 initial_capacity = kMinCapacity; |
497 } | 495 } |
498 current_chunk_ = NewArray<T>(initial_capacity); | 496 current_chunk_ = Vector<T>::New(initial_capacity); |
499 current_capacity_ = initial_capacity; | |
500 index_ = 0; | |
501 } | 497 } |
502 | 498 |
503 virtual ~Collector() { | 499 virtual ~Collector() { |
504 // Free backing store (in reverse allocation order). | 500 // Free backing store (in reverse allocation order). |
505 DeleteArray(current_chunk_); | 501 current_chunk_.Dispose(); |
506 for (int i = chunks_.length() - 1; i >= 0; i--) { | 502 for (int i = chunks_.length() - 1; i >= 0; i--) { |
507 chunks_.at(i).Dispose(); | 503 chunks_.at(i).Dispose(); |
508 } | 504 } |
509 } | 505 } |
510 | 506 |
511 // Add a single element. | 507 // Add a single element. |
512 inline void Add(T value) { | 508 inline void Add(T value) { |
513 if (index_ >= current_capacity_) { | 509 if (index_ >= current_chunk_.length()) { |
514 Grow(1); | 510 Grow(1); |
515 } | 511 } |
516 current_chunk_[index_] = value; | 512 current_chunk_[index_] = value; |
517 index_++; | 513 index_++; |
| 514 size_++; |
518 } | 515 } |
519 | 516 |
520 // Add a block of contiguous elements and return a Vector backed by the | 517 // Add a block of contiguous elements and return a Vector backed by the |
521 // memory area. | 518 // memory area. |
522 // A basic Collector will keep this vector valid as long as the Collector | 519 // A basic Collector will keep this vector valid as long as the Collector |
523 // is alive. | 520 // is alive. |
524 inline Vector<T> AddBlock(int size, T initial_value) { | 521 inline Vector<T> AddBlock(int size, T initial_value) { |
525 if (index_ + size > current_capacity_) { | 522 ASSERT(size > 0); |
| 523 if (size > current_chunk_.length() - index_) { |
526 Grow(size); | 524 Grow(size); |
527 } | 525 } |
528 T* position = current_chunk_ + index_; | 526 T* position = current_chunk_.start() + index_; |
529 index_ += size; | 527 index_ += size; |
| 528 size_ += size; |
530 for (int i = 0; i < size; i++) { | 529 for (int i = 0; i < size; i++) { |
531 position[i] = initial_value; | 530 position[i] = initial_value; |
532 } | 531 } |
533 return Vector<T>(position, size); | 532 return Vector<T>(position, size); |
534 } | 533 } |
535 | 534 |
536 | 535 |
| 536 // Write the contents of the collector into the provided vector. |
| 537 void WriteTo(Vector<T> destination) { |
| 538 ASSERT(size_ <= destination.length()); |
| 539 int position = 0; |
| 540 for (int i = 0; i < chunks_.length(); i++) { |
| 541 Vector<T> chunk = chunks_.at(i); |
| 542 for (int j = 0; j < chunk.length(); j++) { |
| 543 destination[position] = chunk[j]; |
| 544 position++; |
| 545 } |
| 546 } |
| 547 for (int i = 0; i < index_; i++) { |
| 548 destination[position] = current_chunk_[i]; |
| 549 position++; |
| 550 } |
| 551 } |
| 552 |
537 // Allocate a single contiguous vector, copy all the collected | 553 // Allocate a single contiguous vector, copy all the collected |
538 // elements to the vector, and return it. | 554 // elements to the vector, and return it. |
539 // The caller is responsible for freeing the memory of the returned | 555 // The caller is responsible for freeing the memory of the returned |
540 // vector (e.g., using Vector::Dispose). | 556 // vector (e.g., using Vector::Dispose). |
541 Vector<T> ToVector() { | 557 Vector<T> ToVector() { |
542 // Find the total length. | 558 Vector<T> new_store = Vector<T>::New(size_); |
543 int total_length = index_; | 559 WriteTo(new_store); |
544 for (int i = 0; i < chunks_.length(); i++) { | 560 return new_store; |
545 total_length += chunks_.at(i).length(); | |
546 } | |
547 T* new_store = NewArray<T>(total_length); | |
548 int position = 0; | |
549 for (int i = 0; i < chunks_.length(); i++) { | |
550 Vector<T> chunk = chunks_.at(i); | |
551 for (int j = 0; j < chunk.length(); j++) { | |
552 new_store[position] = chunk[j]; | |
553 position++; | |
554 } | |
555 } | |
556 for (int i = 0; i < index_; i++) { | |
557 new_store[position] = current_chunk_[i]; | |
558 position++; | |
559 } | |
560 return Vector<T>(new_store, total_length); | |
561 } | 561 } |
562 | 562 |
563 // Resets the collector to be empty. | 563 // Resets the collector to be empty. |
564 virtual void Reset() { | 564 virtual void Reset() { |
565 for (int i = chunks_.length() - 1; i >= 0; i--) { | 565 for (int i = chunks_.length() - 1; i >= 0; i--) { |
566 chunks_.at(i).Dispose(); | 566 chunks_.at(i).Dispose(); |
567 } | 567 } |
568 chunks_.Rewind(0); | 568 chunks_.Rewind(0); |
569 index_ = 0; | 569 index_ = 0; |
| 570 size_ = 0; |
570 } | 571 } |
571 | 572 |
| 573 // Total number of elements added to collector so far. |
| 574 inline int size() { return size_; } |
| 575 |
572 protected: | 576 protected: |
573 static const int kMinCapacity = 16; | 577 static const int kMinCapacity = 16; |
574 List<Vector<T> > chunks_; | 578 List<Vector<T> > chunks_; |
575 T* current_chunk_; | 579 Vector<T> current_chunk_; // Block of memory currently being written into. |
576 int growth_factor_; | 580 int index_; // Current index in current chunk. |
577 int max_growth_; | 581 int size_; // Total number of elements in collector. |
578 int current_capacity_; | |
579 int index_; | |
580 | 582 |
581 // Creates a new current chunk, and stores the old chunk in the chunks_ list. | 583 // Creates a new current chunk, and stores the old chunk in the chunks_ list. |
582 void Grow(int min_capacity) { | 584 void Grow(int min_capacity) { |
583 ASSERT(growth_factor_ > 1); | 585 ASSERT(growth_factor > 1); |
584 int growth = current_capacity_ * (growth_factor_ - 1); | 586 int growth = current_chunk_.length() * (growth_factor - 1); |
585 if (growth > max_growth_) { | 587 if (growth > max_growth) { |
586 growth = max_growth_; | 588 growth = max_growth; |
587 } | 589 } |
588 int new_capacity = current_capacity_ + growth; | 590 int new_capacity = current_chunk_.length() + growth; |
589 if (new_capacity < min_capacity) { | 591 if (new_capacity < min_capacity) { |
590 new_capacity = min_capacity; | 592 new_capacity = min_capacity + growth; |
591 } | 593 } |
592 T* new_chunk = NewArray<T>(new_capacity); | 594 Vector<T> new_chunk = Vector<T>::New(new_capacity); |
593 int new_index = PrepareGrow(Vector<T>(new_chunk, new_capacity)); | 595 int new_index = PrepareGrow(new_chunk); |
594 chunks_.Add(Vector<T>(current_chunk_, index_)); | 596 if (index_ > 0) { |
| 597 chunks_.Add(current_chunk_.SubVector(0, index_)); |
| 598 } else { |
| 599 // Can happen if the call to PrepareGrow moves everything into |
| 600 // the new chunk. |
| 601 current_chunk_.Dispose(); |
| 602 } |
595 current_chunk_ = new_chunk; | 603 current_chunk_ = new_chunk; |
596 current_capacity_ = new_capacity; | |
597 index_ = new_index; | 604 index_ = new_index; |
598 ASSERT(index_ + min_capacity <= current_capacity_); | 605 ASSERT(index_ + min_capacity <= current_chunk_.length()); |
599 } | 606 } |
600 | 607 |
601 // Before replacing the current chunk, give a subclass the option to move | 608 // Before replacing the current chunk, give a subclass the option to move |
602 // some of the current data into the new chunk. The function may update | 609 // some of the current data into the new chunk. The function may update |
603 // the current index_ value to represent data no longer in the current chunk. | 610 // the current index_ value to represent data no longer in the current chunk. |
604 // Returns the initial index of the new chunk (after copied data). | 611 // Returns the initial index of the new chunk (after copied data). |
605 virtual int PrepareGrow(Vector<T> new_chunk) { | 612 virtual int PrepareGrow(Vector<T> new_chunk) { |
606 return 0; | 613 return 0; |
607 } | 614 } |
608 }; | 615 }; |
609 | 616 |
610 | 617 |
611 /* | 618 /* |
612 * A collector that allows sequences of values to be guaranteed to | 619 * A collector that allows sequences of values to be guaranteed to |
613 * stay consecutive. | 620 * stay consecutive. |
614 * If the backing store grows while a sequence is active, the current | 621 * If the backing store grows while a sequence is active, the current |
615 * sequence might be moved, but after the sequence is ended, it will | 622 * sequence might be moved, but after the sequence is ended, it will |
616 * not move again. | 623 * not move again. |
617 * NOTICE: Blocks allocated using Collector::AddBlock(int) can move | 624 * NOTICE: Blocks allocated using Collector::AddBlock(int) can move |
618 * as well, if inside an active sequence where another element is added. | 625 * as well, if inside an active sequence where another element is added. |
619 */ | 626 */ |
620 template <typename T> | 627 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> |
621 class SequenceCollector : public Collector<T> { | 628 class SequenceCollector : public Collector<T, growth_factor, max_growth> { |
622 public: | 629 public: |
623 SequenceCollector(int initial_capacity, | 630 explicit SequenceCollector(int initial_capacity) |
624 int growth_factor = 2, | 631 : Collector<T, growth_factor, max_growth>(initial_capacity), |
625 int max_growth = 1 * MB) | |
626 : Collector<T>(initial_capacity, growth_factor, max_growth), | |
627 sequence_start_(kNoSequence) { } | 632 sequence_start_(kNoSequence) { } |
628 | 633 |
629 virtual ~SequenceCollector() {} | 634 virtual ~SequenceCollector() {} |
630 | 635 |
631 void StartSequence() { | 636 void StartSequence() { |
632 ASSERT(sequence_start_ == kNoSequence); | 637 ASSERT(sequence_start_ == kNoSequence); |
633 sequence_start_ = this->index_; | 638 sequence_start_ = this->index_; |
634 } | 639 } |
635 | 640 |
636 Vector<T> EndSequence() { | 641 Vector<T> EndSequence() { |
637 ASSERT(sequence_start_ != kNoSequence); | 642 ASSERT(sequence_start_ != kNoSequence); |
638 int sequence_start = sequence_start_; | 643 int sequence_start = sequence_start_; |
639 sequence_start_ = kNoSequence; | 644 sequence_start_ = kNoSequence; |
640 return Vector<T>(this->current_chunk_ + sequence_start, | 645 if (sequence_start == this->index_) return Vector<T>(); |
641 this->index_ - sequence_start); | 646 return this->current_chunk_.SubVector(sequence_start, this->index_); |
642 } | 647 } |
643 | 648 |
644 // Drops the currently added sequence, and all collected elements in it. | 649 // Drops the currently added sequence, and all collected elements in it. |
645 void DropSequence() { | 650 void DropSequence() { |
646 ASSERT(sequence_start_ != kNoSequence); | 651 ASSERT(sequence_start_ != kNoSequence); |
| 652 int sequence_length = this->index_ - sequence_start_; |
647 this->index_ = sequence_start_; | 653 this->index_ = sequence_start_; |
| 654 this->size_ -= sequence_length; |
648 sequence_start_ = kNoSequence; | 655 sequence_start_ = kNoSequence; |
649 } | 656 } |
650 | 657 |
651 virtual void Reset() { | 658 virtual void Reset() { |
652 sequence_start_ = kNoSequence; | 659 sequence_start_ = kNoSequence; |
653 this->Collector<T>::Reset(); | 660 this->Collector<T, growth_factor, max_growth>::Reset(); |
654 } | 661 } |
655 | 662 |
656 private: | 663 private: |
657 static const int kNoSequence = -1; | 664 static const int kNoSequence = -1; |
658 int sequence_start_; | 665 int sequence_start_; |
659 | 666 |
660 // Move the currently active sequence to the new chunk. | 667 // Move the currently active sequence to the new chunk. |
661 virtual int PrepareGrow(Vector<T> new_chunk) { | 668 virtual int PrepareGrow(Vector<T> new_chunk) { |
662 if (sequence_start_ != kNoSequence) { | 669 if (sequence_start_ != kNoSequence) { |
663 int sequence_length = this->index_ - sequence_start_; | 670 int sequence_length = this->index_ - sequence_start_; |
(...skipping 276 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
940 } | 947 } |
941 | 948 |
942 template <class Dest, class Source> | 949 template <class Dest, class Source> |
943 inline Dest BitCast(Source* source) { | 950 inline Dest BitCast(Source* source) { |
944 return BitCast<Dest>(reinterpret_cast<uintptr_t>(source)); | 951 return BitCast<Dest>(reinterpret_cast<uintptr_t>(source)); |
945 } | 952 } |
946 | 953 |
947 } } // namespace v8::internal | 954 } } // namespace v8::internal |
948 | 955 |
949 #endif // V8_UTILS_H_ | 956 #endif // V8_UTILS_H_ |
OLD | NEW |