| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 // Defines growable array classes, that differ where they are allocated: | 4 // Defines growable array classes, that differ where they are allocated: |
| 5 // - GrowableArray: allocate on stack. | 5 // - GrowableArray: allocate on stack. |
| 6 // - ZoneGrowableArray: allocated in the zone. | 6 // - ZoneGrowableArray: allocated in the zone. |
| 7 | 7 |
| 8 #ifndef VM_GROWABLE_ARRAY_H_ | 8 #ifndef VM_GROWABLE_ARRAY_H_ |
| 9 #define VM_GROWABLE_ARRAY_H_ | 9 #define VM_GROWABLE_ARRAY_H_ |
| 10 | 10 |
| 11 #include "platform/utils.h" | 11 #include "platform/utils.h" |
| 12 #include "vm/allocation.h" | 12 #include "vm/allocation.h" |
| 13 #include "vm/isolate.h" | 13 #include "vm/isolate.h" |
| 14 #include "vm/zone.h" | 14 #include "vm/zone.h" |
| 15 | 15 |
| 16 namespace dart { | 16 namespace dart { |
| 17 | 17 |
| 18 template<typename T, typename B> | 18 template<typename T, typename B> |
| 19 class BaseGrowableArray : public B { | 19 class BaseGrowableArray : public B { |
| 20 public: | 20 public: |
| 21 explicit BaseGrowableArray(Zone* zone) | 21 explicit BaseGrowableArray(Zone* zone) |
| 22 : length_(0), capacity_(0), data_(NULL), zone_(zone) { | 22 : length_(0), capacity_(0), data_(NULL), zone_(zone) { |
| 23 ASSERT(zone_ != NULL); | 23 ASSERT(zone_ != NULL); |
| 24 } | 24 } |
| 25 | 25 |
| 26 BaseGrowableArray(int initial_capacity, Zone* zone) | 26 BaseGrowableArray(intptr_t initial_capacity, Zone* zone) |
| 27 : length_(0), capacity_(0), data_(NULL), zone_(zone) { | 27 : length_(0), capacity_(0), data_(NULL), zone_(zone) { |
| 28 ASSERT(zone_ != NULL); | 28 ASSERT(zone_ != NULL); |
| 29 if (initial_capacity > 0) { | 29 if (initial_capacity > 0) { |
| 30 capacity_ = Utils::RoundUpToPowerOfTwo(initial_capacity); | 30 capacity_ = Utils::RoundUpToPowerOfTwo(initial_capacity); |
| 31 data_ = zone_->Alloc<T>(capacity_); | 31 data_ = zone_->Alloc<T>(capacity_); |
| 32 } | 32 } |
| 33 } | 33 } |
| 34 | 34 |
| 35 int length() const { return length_; } | 35 intptr_t length() const { return length_; } |
| 36 T* data() const { return data_; } | 36 T* data() const { return data_; } |
| 37 bool is_empty() const { return length_ == 0; } | 37 bool is_empty() const { return length_ == 0; } |
| 38 | 38 |
| 39 void TruncateTo(intptr_t length) { | 39 void TruncateTo(intptr_t length) { |
| 40 ASSERT(length_ >= length); | 40 ASSERT(length_ >= length); |
| 41 length_ = length; | 41 length_ = length; |
| 42 } | 42 } |
| 43 | 43 |
| 44 void Add(const T& value) { | 44 void Add(const T& value) { |
| 45 Resize(length() + 1); | 45 Resize(length() + 1); |
| 46 Last() = value; | 46 Last() = value; |
| 47 } | 47 } |
| 48 | 48 |
| 49 T& RemoveLast() { | 49 T& RemoveLast() { |
| 50 ASSERT(length_ > 0); | 50 ASSERT(length_ > 0); |
| 51 T& result = operator[](length_ - 1); | 51 T& result = operator[](length_ - 1); |
| 52 length_--; | 52 length_--; |
| 53 return result; | 53 return result; |
| 54 } | 54 } |
| 55 | 55 |
| 56 T& operator[](int index) const { | 56 T& operator[](intptr_t index) const { |
| 57 ASSERT(0 <= index); | 57 ASSERT(0 <= index); |
| 58 ASSERT(index < length_); | 58 ASSERT(index < length_); |
| 59 ASSERT(length_ <= capacity_); | 59 ASSERT(length_ <= capacity_); |
| 60 return data_[index]; | 60 return data_[index]; |
| 61 } | 61 } |
| 62 | 62 |
| 63 T& Last() const { | 63 T& Last() const { |
| 64 ASSERT(length_ > 0); | 64 ASSERT(length_ > 0); |
| 65 return operator[](length_ - 1); | 65 return operator[](length_ - 1); |
| 66 } | 66 } |
| (...skipping 13 matching lines...) Expand all Loading... |
| 80 for (intptr_t i = length_ - 2; i >= idx; i--) { | 80 for (intptr_t i = length_ - 2; i >= idx; i--) { |
| 81 data_[i + 1] = data_[i]; | 81 data_[i + 1] = data_[i]; |
| 82 } | 82 } |
| 83 data_[idx] = value; | 83 data_[idx] = value; |
| 84 } | 84 } |
| 85 | 85 |
| 86 // Sort the array in place. | 86 // Sort the array in place. |
| 87 inline void Sort(int compare(const T*, const T*)); | 87 inline void Sort(int compare(const T*, const T*)); |
| 88 | 88 |
| 89 private: | 89 private: |
| 90 int length_; | 90 intptr_t length_; |
| 91 int capacity_; | 91 intptr_t capacity_; |
| 92 T* data_; | 92 T* data_; |
| 93 Zone* zone_; // Zone in which we are allocating the array. | 93 Zone* zone_; // Zone in which we are allocating the array. |
| 94 | 94 |
| 95 void Resize(int new_length); | 95 void Resize(intptr_t new_length); |
| 96 | 96 |
| 97 DISALLOW_COPY_AND_ASSIGN(BaseGrowableArray); | 97 DISALLOW_COPY_AND_ASSIGN(BaseGrowableArray); |
| 98 }; | 98 }; |
| 99 | 99 |
| 100 | 100 |
| 101 template<typename T, typename B> | 101 template<typename T, typename B> |
| 102 inline void BaseGrowableArray<T, B>::Sort( | 102 inline void BaseGrowableArray<T, B>::Sort( |
| 103 int compare(const T*, const T*)) { | 103 int compare(const T*, const T*)) { |
| 104 typedef int (*CompareFunction)(const void*, const void*); | 104 typedef int (*CompareFunction)(const void*, const void*); |
| 105 qsort(data_, length_, sizeof(T), reinterpret_cast<CompareFunction>(compare)); | 105 qsort(data_, length_, sizeof(T), reinterpret_cast<CompareFunction>(compare)); |
| 106 } | 106 } |
| 107 | 107 |
| 108 | 108 |
| 109 template<typename T, typename B> | 109 template<typename T, typename B> |
| 110 void BaseGrowableArray<T, B>::Resize(int new_length) { | 110 void BaseGrowableArray<T, B>::Resize(intptr_t new_length) { |
| 111 if (new_length > capacity_) { | 111 if (new_length > capacity_) { |
| 112 int new_capacity = Utils::RoundUpToPowerOfTwo(new_length); | 112 intptr_t new_capacity = Utils::RoundUpToPowerOfTwo(new_length); |
| 113 T* new_data = zone_->Realloc<T>(data_, capacity_, new_capacity); | 113 T* new_data = zone_->Realloc<T>(data_, capacity_, new_capacity); |
| 114 ASSERT(new_data != NULL); | 114 ASSERT(new_data != NULL); |
| 115 data_ = new_data; | 115 data_ = new_data; |
| 116 capacity_ = new_capacity; | 116 capacity_ = new_capacity; |
| 117 } | 117 } |
| 118 length_ = new_length; | 118 length_ = new_length; |
| 119 } | 119 } |
| 120 | 120 |
| 121 | 121 |
| 122 template<typename T> | 122 template<typename T> |
| 123 class GrowableArray : public BaseGrowableArray<T, ValueObject> { | 123 class GrowableArray : public BaseGrowableArray<T, ValueObject> { |
| 124 public: | 124 public: |
| 125 explicit GrowableArray(int initial_capacity) | 125 explicit GrowableArray(intptr_t initial_capacity) |
| 126 : BaseGrowableArray<T, ValueObject>( | 126 : BaseGrowableArray<T, ValueObject>( |
| 127 initial_capacity, | 127 initial_capacity, |
| 128 Isolate::Current()->current_zone()) {} | 128 Isolate::Current()->current_zone()) {} |
| 129 GrowableArray() | 129 GrowableArray() |
| 130 : BaseGrowableArray<T, ValueObject>( | 130 : BaseGrowableArray<T, ValueObject>( |
| 131 Isolate::Current()->current_zone()) {} | 131 Isolate::Current()->current_zone()) {} |
| 132 }; | 132 }; |
| 133 | 133 |
| 134 | 134 |
| 135 template<typename T> | 135 template<typename T> |
| 136 class ZoneGrowableArray : public BaseGrowableArray<T, ZoneAllocated> { | 136 class ZoneGrowableArray : public BaseGrowableArray<T, ZoneAllocated> { |
| 137 public: | 137 public: |
| 138 explicit ZoneGrowableArray(int initial_capacity) | 138 explicit ZoneGrowableArray(intptr_t initial_capacity) |
| 139 : BaseGrowableArray<T, ZoneAllocated>( | 139 : BaseGrowableArray<T, ZoneAllocated>( |
| 140 initial_capacity, | 140 initial_capacity, |
| 141 Isolate::Current()->current_zone()) {} | 141 Isolate::Current()->current_zone()) {} |
| 142 ZoneGrowableArray() : | 142 ZoneGrowableArray() : |
| 143 BaseGrowableArray<T, ZoneAllocated>( | 143 BaseGrowableArray<T, ZoneAllocated>( |
| 144 Isolate::Current()->current_zone()) {} | 144 Isolate::Current()->current_zone()) {} |
| 145 }; | 145 }; |
| 146 | 146 |
| 147 } // namespace dart | 147 } // namespace dart |
| 148 | 148 |
| 149 #endif // VM_GROWABLE_ARRAY_H_ | 149 #endif // VM_GROWABLE_ARRAY_H_ |
| OLD | NEW |