OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 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 479 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
490 * There is no guarantee that the backing store is contiguous (and, as a | 490 * There is no guarantee that the backing store is contiguous (and, as a |
491 * consequence, no guarantees that consecutively added elements are adjacent | 491 * consequence, no guarantees that consecutively added elements are adjacent |
492 * in memory). The collector may move elements unless it has guaranteed not | 492 * in memory). The collector may move elements unless it has guaranteed not |
493 * to. | 493 * to. |
494 */ | 494 */ |
495 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> | 495 template <typename T, int growth_factor = 2, int max_growth = 1 * MB> |
496 class Collector { | 496 class Collector { |
497 public: | 497 public: |
498 explicit Collector(int initial_capacity = kMinCapacity) | 498 explicit Collector(int initial_capacity = kMinCapacity) |
499 : index_(0), size_(0) { | 499 : index_(0), size_(0) { |
500 if (initial_capacity < kMinCapacity) { | |
501 initial_capacity = kMinCapacity; | |
502 } | |
503 current_chunk_ = Vector<T>::New(initial_capacity); | 500 current_chunk_ = Vector<T>::New(initial_capacity); |
504 } | 501 } |
505 | 502 |
506 virtual ~Collector() { | 503 virtual ~Collector() { |
507 // Free backing store (in reverse allocation order). | 504 // Free backing store (in reverse allocation order). |
508 current_chunk_.Dispose(); | 505 current_chunk_.Dispose(); |
509 for (int i = chunks_.length() - 1; i >= 0; i--) { | 506 for (int i = chunks_.length() - 1; i >= 0; i--) { |
510 chunks_.at(i).Dispose(); | 507 chunks_.at(i).Dispose(); |
511 } | 508 } |
512 } | 509 } |
(...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
594 protected: | 591 protected: |
595 static const int kMinCapacity = 16; | 592 static const int kMinCapacity = 16; |
596 List<Vector<T> > chunks_; | 593 List<Vector<T> > chunks_; |
597 Vector<T> current_chunk_; // Block of memory currently being written into. | 594 Vector<T> current_chunk_; // Block of memory currently being written into. |
598 int index_; // Current index in current chunk. | 595 int index_; // Current index in current chunk. |
599 int size_; // Total number of elements in collector. | 596 int size_; // Total number of elements in collector. |
600 | 597 |
601 // Creates a new current chunk, and stores the old chunk in the chunks_ list. | 598 // Creates a new current chunk, and stores the old chunk in the chunks_ list. |
602 void Grow(int min_capacity) { | 599 void Grow(int min_capacity) { |
603 ASSERT(growth_factor > 1); | 600 ASSERT(growth_factor > 1); |
604 int growth = current_chunk_.length() * (growth_factor - 1); | 601 int new_capacity; |
605 if (growth > max_growth) { | 602 int current_length = current_chunk_.length(); |
606 growth = max_growth; | 603 if (current_length < kMinCapacity) { |
607 } | 604 // The collector started out as empty. |
608 int new_capacity = current_chunk_.length() + growth; | 605 new_capacity = min_capacity * growth_factor; |
609 if (new_capacity < min_capacity) { | 606 if (new_capacity < kMinCapacity) new_capacity = kMinCapacity; |
610 new_capacity = min_capacity + growth; | 607 } else { |
| 608 int growth = current_length * (growth_factor - 1); |
| 609 if (growth > max_growth) { |
| 610 growth = max_growth; |
| 611 } |
| 612 new_capacity = current_length + growth; |
| 613 if (new_capacity < min_capacity) { |
| 614 new_capacity = min_capacity + growth; |
| 615 } |
611 } | 616 } |
612 Vector<T> new_chunk = Vector<T>::New(new_capacity); | 617 Vector<T> new_chunk = Vector<T>::New(new_capacity); |
613 int new_index = PrepareGrow(new_chunk); | 618 int new_index = PrepareGrow(new_chunk); |
614 if (index_ > 0) { | 619 if (index_ > 0) { |
615 chunks_.Add(current_chunk_.SubVector(0, index_)); | 620 chunks_.Add(current_chunk_.SubVector(0, index_)); |
616 } else { | 621 } else { |
617 // Can happen if the call to PrepareGrow moves everything into | 622 // Can happen if the call to PrepareGrow moves everything into |
618 // the new chunk. | 623 // the new chunk. |
619 current_chunk_.Dispose(); | 624 current_chunk_.Dispose(); |
620 } | 625 } |
(...skipping 285 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
906 ASSERT(element < static_cast<int>(sizeof(T) * CHAR_BIT)); | 911 ASSERT(element < static_cast<int>(sizeof(T) * CHAR_BIT)); |
907 return 1 << element; | 912 return 1 << element; |
908 } | 913 } |
909 | 914 |
910 T bits_; | 915 T bits_; |
911 }; | 916 }; |
912 | 917 |
913 } } // namespace v8::internal | 918 } } // namespace v8::internal |
914 | 919 |
915 #endif // V8_UTILS_H_ | 920 #endif // V8_UTILS_H_ |
OLD | NEW |