OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_UTILS_H_ | 5 #ifndef V8_UTILS_H_ |
6 #define V8_UTILS_H_ | 6 #define V8_UTILS_H_ |
7 | 7 |
8 #include <limits.h> | 8 #include <limits.h> |
9 #include <stdlib.h> | 9 #include <stdlib.h> |
10 #include <string.h> | 10 #include <string.h> |
(...skipping 530 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
541 Vector<T>::operator=(rhs); | 541 Vector<T>::operator=(rhs); |
542 MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize); | 542 MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize); |
543 this->set_start(buffer_); | 543 this->set_start(buffer_); |
544 return *this; | 544 return *this; |
545 } | 545 } |
546 | 546 |
547 private: | 547 private: |
548 T buffer_[kSize]; | 548 T buffer_[kSize]; |
549 }; | 549 }; |
550 | 550 |
551 | |
552 /* | |
553 * A class that collects values into a backing store. | |
554 * Specialized versions of the class can allow access to the backing store | |
555 * in different ways. | |
556 * There is no guarantee that the backing store is contiguous (and, as a | |
557 * consequence, no guarantees that consecutively added elements are adjacent | |
558 * in memory). The collector may move elements unless it has guaranteed not | |
559 * to. | |
560 */ | |
561 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> | |
562 class Collector { | |
563 public: | |
564 explicit Collector(int initial_capacity = kMinCapacity) | |
565 : index_(0), size_(0) { | |
566 current_chunk_ = Vector<T>::New(initial_capacity); | |
567 } | |
568 | |
569 virtual ~Collector() { | |
570 // Free backing store (in reverse allocation order). | |
571 current_chunk_.Dispose(); | |
572 for (int i = chunks_.length() - 1; i >= 0; i--) { | |
573 chunks_.at(i).Dispose(); | |
574 } | |
575 } | |
576 | |
577 // Add a single element. | |
578 inline void Add(T value) { | |
579 if (index_ >= current_chunk_.length()) { | |
580 Grow(1); | |
581 } | |
582 current_chunk_[index_] = value; | |
583 index_++; | |
584 size_++; | |
585 } | |
586 | |
587 // Add a block of contiguous elements and return a Vector backed by the | |
588 // memory area. | |
589 // A basic Collector will keep this vector valid as long as the Collector | |
590 // is alive. | |
591 inline Vector<T> AddBlock(int size, T initial_value) { | |
592 DCHECK(size > 0); | |
593 if (size > current_chunk_.length() - index_) { | |
594 Grow(size); | |
595 } | |
596 T* position = current_chunk_.start() + index_; | |
597 index_ += size; | |
598 size_ += size; | |
599 for (int i = 0; i < size; i++) { | |
600 position[i] = initial_value; | |
601 } | |
602 return Vector<T>(position, size); | |
603 } | |
604 | |
605 | |
606 // Add a contiguous block of elements and return a vector backed | |
607 // by the added block. | |
608 // A basic Collector will keep this vector valid as long as the Collector | |
609 // is alive. | |
610 inline Vector<T> AddBlock(Vector<const T> source) { | |
611 if (source.length() > current_chunk_.length() - index_) { | |
612 Grow(source.length()); | |
613 } | |
614 T* position = current_chunk_.start() + index_; | |
615 index_ += source.length(); | |
616 size_ += source.length(); | |
617 for (int i = 0; i < source.length(); i++) { | |
618 position[i] = source[i]; | |
619 } | |
620 return Vector<T>(position, source.length()); | |
621 } | |
622 | |
623 | |
624 // Write the contents of the collector into the provided vector. | |
625 void WriteTo(Vector<T> destination) { | |
626 DCHECK(size_ <= destination.length()); | |
627 int position = 0; | |
628 for (int i = 0; i < chunks_.length(); i++) { | |
629 Vector<T> chunk = chunks_.at(i); | |
630 for (int j = 0; j < chunk.length(); j++) { | |
631 destination[position] = chunk[j]; | |
632 position++; | |
633 } | |
634 } | |
635 for (int i = 0; i < index_; i++) { | |
636 destination[position] = current_chunk_[i]; | |
637 position++; | |
638 } | |
639 } | |
640 | |
641 // Allocate a single contiguous vector, copy all the collected | |
642 // elements to the vector, and return it. | |
643 // The caller is responsible for freeing the memory of the returned | |
644 // vector (e.g., using Vector::Dispose). | |
645 Vector<T> ToVector() { | |
646 Vector<T> new_store = Vector<T>::New(size_); | |
647 WriteTo(new_store); | |
648 return new_store; | |
649 } | |
650 | |
651 // Resets the collector to be empty. | |
652 virtual void Reset() { | |
653 for (int i = chunks_.length() - 1; i >= 0; i--) { | |
654 chunks_.at(i).Dispose(); | |
655 } | |
656 chunks_.Rewind(0); | |
657 index_ = 0; | |
658 size_ = 0; | |
659 } | |
660 | |
661 // Total number of elements added to collector so far. | |
662 inline int size() { return size_; } | |
663 | |
664 protected: | |
665 static const int kMinCapacity = 16; | |
666 List<Vector<T> > chunks_; | |
667 Vector<T> current_chunk_; // Block of memory currently being written into. | |
668 int index_; // Current index in current chunk. | |
669 int size_; // Total number of elements in collector. | |
670 | |
671 // Creates a new current chunk, and stores the old chunk in the chunks_ list. | |
672 void Grow(int min_capacity) { | |
673 DCHECK(growth_factor > 1); | |
674 int new_capacity; | |
675 int current_length = current_chunk_.length(); | |
676 if (current_length < kMinCapacity) { | |
677 // The collector started out as empty. | |
678 new_capacity = min_capacity * growth_factor; | |
679 if (new_capacity < kMinCapacity) new_capacity = kMinCapacity; | |
680 } else { | |
681 int growth = current_length * (growth_factor - 1); | |
682 if (growth > max_growth) { | |
683 growth = max_growth; | |
684 } | |
685 new_capacity = current_length + growth; | |
686 if (new_capacity < min_capacity) { | |
687 new_capacity = min_capacity + growth; | |
688 } | |
689 } | |
690 NewChunk(new_capacity); | |
691 DCHECK(index_ + min_capacity <= current_chunk_.length()); | |
692 } | |
693 | |
694 // Before replacing the current chunk, give a subclass the option to move | |
695 // some of the current data into the new chunk. The function may update | |
696 // the current index_ value to represent data no longer in the current chunk. | |
697 // Returns the initial index of the new chunk (after copied data). | |
698 virtual void NewChunk(int new_capacity) { | |
699 Vector<T> new_chunk = Vector<T>::New(new_capacity); | |
700 if (index_ > 0) { | |
701 chunks_.Add(current_chunk_.SubVector(0, index_)); | |
702 } else { | |
703 current_chunk_.Dispose(); | |
704 } | |
705 current_chunk_ = new_chunk; | |
706 index_ = 0; | |
707 } | |
708 }; | |
709 | |
710 | |
711 /* | |
712 * A collector that allows sequences of values to be guaranteed to | |
713 * stay consecutive. | |
714 * If the backing store grows while a sequence is active, the current | |
715 * sequence might be moved, but after the sequence is ended, it will | |
716 * not move again. | |
717 * NOTICE: Blocks allocated using Collector::AddBlock(int) can move | |
718 * as well, if inside an active sequence where another element is added. | |
719 */ | |
720 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> | |
721 class SequenceCollector : public Collector<T, growth_factor, max_growth> { | |
722 public: | |
723 explicit SequenceCollector(int initial_capacity) | |
724 : Collector<T, growth_factor, max_growth>(initial_capacity), | |
725 sequence_start_(kNoSequence) { } | |
726 | |
727 virtual ~SequenceCollector() {} | |
728 | |
729 void StartSequence() { | |
730 DCHECK(sequence_start_ == kNoSequence); | |
731 sequence_start_ = this->index_; | |
732 } | |
733 | |
734 Vector<T> EndSequence() { | |
735 DCHECK(sequence_start_ != kNoSequence); | |
736 int sequence_start = sequence_start_; | |
737 sequence_start_ = kNoSequence; | |
738 if (sequence_start == this->index_) return Vector<T>(); | |
739 return this->current_chunk_.SubVector(sequence_start, this->index_); | |
740 } | |
741 | |
742 // Drops the currently added sequence, and all collected elements in it. | |
743 void DropSequence() { | |
744 DCHECK(sequence_start_ != kNoSequence); | |
745 int sequence_length = this->index_ - sequence_start_; | |
746 this->index_ = sequence_start_; | |
747 this->size_ -= sequence_length; | |
748 sequence_start_ = kNoSequence; | |
749 } | |
750 | |
751 virtual void Reset() { | |
752 sequence_start_ = kNoSequence; | |
753 this->Collector<T, growth_factor, max_growth>::Reset(); | |
754 } | |
755 | |
756 private: | |
757 static const int kNoSequence = -1; | |
758 int sequence_start_; | |
759 | |
760 // Move the currently active sequence to the new chunk. | |
761 virtual void NewChunk(int new_capacity) { | |
762 if (sequence_start_ == kNoSequence) { | |
763 // Fall back on default behavior if no sequence has been started. | |
764 this->Collector<T, growth_factor, max_growth>::NewChunk(new_capacity); | |
765 return; | |
766 } | |
767 int sequence_length = this->index_ - sequence_start_; | |
768 Vector<T> new_chunk = Vector<T>::New(sequence_length + new_capacity); | |
769 DCHECK(sequence_length < new_chunk.length()); | |
770 for (int i = 0; i < sequence_length; i++) { | |
771 new_chunk[i] = this->current_chunk_[sequence_start_ + i]; | |
772 } | |
773 if (sequence_start_ > 0) { | |
774 this->chunks_.Add(this->current_chunk_.SubVector(0, sequence_start_)); | |
775 } else { | |
776 this->current_chunk_.Dispose(); | |
777 } | |
778 this->current_chunk_ = new_chunk; | |
779 this->index_ = sequence_length; | |
780 sequence_start_ = 0; | |
781 } | |
782 }; | |
783 | |
784 | |
785 // Compare 8bit/16bit chars to 8bit/16bit chars. | 551 // Compare 8bit/16bit chars to 8bit/16bit chars. |
786 template <typename lchar, typename rchar> | 552 template <typename lchar, typename rchar> |
787 inline int CompareCharsUnsigned(const lchar* lhs, const rchar* rhs, | 553 inline int CompareCharsUnsigned(const lchar* lhs, const rchar* rhs, |
788 size_t chars) { | 554 size_t chars) { |
789 const lchar* limit = lhs + chars; | 555 const lchar* limit = lhs + chars; |
790 if (sizeof(*lhs) == sizeof(char) && sizeof(*rhs) == sizeof(char)) { | 556 if (sizeof(*lhs) == sizeof(char) && sizeof(*rhs) == sizeof(char)) { |
791 // memcmp compares byte-by-byte, yielding wrong results for two-byte | 557 // memcmp compares byte-by-byte, yielding wrong results for two-byte |
792 // strings on little-endian systems. | 558 // strings on little-endian systems. |
793 return memcmp(lhs, rhs, chars); | 559 return memcmp(lhs, rhs, chars); |
794 } | 560 } |
(...skipping 974 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1769 } | 1535 } |
1770 | 1536 |
1771 static inline void WriteUnalignedUInt32(void* p, uint32_t value) { | 1537 static inline void WriteUnalignedUInt32(void* p, uint32_t value) { |
1772 WriteUnalignedValue(p, value); | 1538 WriteUnalignedValue(p, value); |
1773 } | 1539 } |
1774 | 1540 |
1775 } // namespace internal | 1541 } // namespace internal |
1776 } // namespace v8 | 1542 } // namespace v8 |
1777 | 1543 |
1778 #endif // V8_UTILS_H_ | 1544 #endif // V8_UTILS_H_ |
OLD | NEW |