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 |