1// Copyright (c) 2017, the Dart project authors. Please see the AUTHORS file
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.
4// Defines growable array classes, that differ where they are allocated:
5// - GrowableArray: allocated on stack.
6// - ZoneGrowableArray: allocated in the zone.
7// - MallocGrowableArray: allocates using malloc/realloc; free is only called
8// at destruction.
9
10#ifndef RUNTIME_PLATFORM_GROWABLE_ARRAY_H_
11#define RUNTIME_PLATFORM_GROWABLE_ARRAY_H_
12
13#include "platform/allocation.h"
14#include "platform/utils.h"
15
16namespace dart {
17
18template <typename T, typename B, typename Allocator>
19class BaseGrowableArray : public B {
20 public:
21 explicit BaseGrowableArray(Allocator* allocator)
22 : length_(0), capacity_(0), data_(nullptr), allocator_(allocator) {}
23
24 BaseGrowableArray(intptr_t initial_capacity, Allocator* allocator)
25 : length_(0), capacity_(0), data_(nullptr), allocator_(allocator) {
26 if (initial_capacity > 0) {
27 capacity_ = Utils::RoundUpToPowerOfTwo(x: initial_capacity);
28 data_ = allocator_->template Alloc<T>(capacity_);
29 }
30 }
31
32 BaseGrowableArray(BaseGrowableArray&& other)
33 : length_(other.length_),
34 capacity_(other.capacity_),
35 data_(other.data_),
36 allocator_(other.allocator_) {
37 other.length_ = 0;
38 other.capacity_ = 0;
39 other.data_ = nullptr;
40 }
41
42 ~BaseGrowableArray() { allocator_->template Free<T>(data_, capacity_); }
43
44 BaseGrowableArray& operator=(BaseGrowableArray&& other) {
45 intptr_t temp = other.length_;
46 other.length_ = length_;
47 length_ = temp;
48 temp = other.capacity_;
49 other.capacity_ = capacity_;
50 capacity_ = temp;
51 T* temp_data = other.data_;
52 other.data_ = data_;
53 data_ = temp_data;
54 Allocator* temp_allocator = other.allocator_;
55 other.allocator_ = allocator_;
56 allocator_ = temp_allocator;
57 return *this;
58 }
59
60 intptr_t length() const { return length_; }
61 T* data() const { return data_; }
62 bool is_empty() const { return length_ == 0; }
63
64 void TruncateTo(intptr_t length) {
65 ASSERT(length_ >= length);
66 length_ = length;
67 }
68
69 inline bool Contains(const T& other,
70 bool isEqual(const T&, const T&) = nullptr) const {
71 for (const auto& value : *this) {
72 if (value == other) {
73 // Value identity should imply isEqual.
74 ASSERT(isEqual == nullptr || isEqual(value, other));
75 return true;
76 }
77 if (isEqual != nullptr && isEqual(value, other)) {
78 return true;
79 }
80 }
81 return false;
82 }
83
84 void Add(const T& value) {
85 Resize(new_length: length() + 1);
86 Last() = value;
87 }
88
89 T& RemoveLast() {
90 ASSERT(length_ > 0);
91 T& result = operator[](index: length_ - 1);
92 length_--;
93 return result;
94 }
95
96 T& operator[](intptr_t index) const {
97 ASSERT(0 <= index);
98 ASSERT(index < length_);
99 ASSERT(length_ <= capacity_);
100 return data_[index];
101 }
102
103 void FillWith(const T& value, intptr_t start, intptr_t length) {
104 ASSERT(start >= 0);
105 ASSERT(length >= 0);
106 ASSERT(start <= length_);
107
108 Resize(new_length: start + length);
109 for (intptr_t i = 0; i < length; ++i) {
110 data_[start + i] = value;
111 }
112 }
113
114 void EnsureLength(intptr_t new_length, const T& default_value) {
115 const intptr_t old_length = length_;
116 if (old_length < new_length) {
117 Resize(new_length);
118 for (intptr_t i = old_length; i < new_length; ++i) {
119 (*this)[i] = default_value;
120 }
121 }
122 }
123
124 const T& At(intptr_t index) const { return operator[](index); }
125
126 T& Last() const {
127 ASSERT(length_ > 0);
128 return operator[](index: length_ - 1);
129 }
130
131 void AddArray(const BaseGrowableArray<T, B, Allocator>& src) {
132 for (intptr_t i = 0; i < src.length(); i++) {
133 Add(value: src[i]);
134 }
135 }
136
137 void Clear() { length_ = 0; }
138
139 void InsertAt(intptr_t idx, const T& value) {
140 Resize(new_length: length() + 1);
141 for (intptr_t i = length_ - 2; i >= idx; i--) {
142 data_[i + 1] = data_[i];
143 }
144 data_[idx] = value;
145 }
146
147 void Reverse() {
148 for (intptr_t i = 0; i < length_ / 2; i++) {
149 const intptr_t j = length_ - 1 - i;
150 T temp = data_[i];
151 data_[i] = data_[j];
152 data_[j] = temp;
153 }
154 }
155
156 // Swap entries |i| and |j|.
157 void Swap(intptr_t i, intptr_t j) {
158 ASSERT(i >= 0);
159 ASSERT(j >= 0);
160 ASSERT(i < length_);
161 ASSERT(j < length_);
162 T temp = data_[i];
163 data_[i] = data_[j];
164 data_[j] = temp;
165 }
166
167 // NOTE: Does not preserve array order.
168 void RemoveAt(intptr_t i) {
169 ASSERT(i >= 0);
170 ASSERT(i < length_);
171 intptr_t last = length_ - 1;
172 if (i < last) {
173 Swap(i, j: last);
174 }
175 RemoveLast();
176 }
177
178 // Preserves array order.
179 void EraseAt(intptr_t idx) {
180 ASSERT(idx >= 0);
181 ASSERT(idx < length_);
182 for (intptr_t i = idx; i < length_ - 1; i++) {
183 data_[i] = data_[i + 1];
184 }
185 RemoveLast();
186 }
187
188 // The content is uninitialized after calling it.
189 void SetLength(intptr_t new_length);
190
191 // The content (if expanded) is uninitialized after calling it.
192 // The backing store (if expanded) will grow with by a power-of-2.
193 void Resize(intptr_t new_length);
194
195 // Sort the array in place.
196 inline void Sort(int compare(const T*, const T*));
197
198 void StealBuffer(T** buffer, intptr_t* length) {
199 *buffer = data_;
200 *length = length_;
201 data_ = nullptr;
202 length_ = 0;
203 capacity_ = 0;
204 }
205
206 T* begin() { return &data_[0]; }
207 const T* begin() const { return &data_[0]; }
208
209 T* end() { return &data_[length_]; }
210 const T* end() const { return &data_[length_]; }
211
212 private:
213 intptr_t length_;
214 intptr_t capacity_;
215 T* data_;
216 Allocator* allocator_; // Used to (re)allocate the array.
217
218 DISALLOW_COPY_AND_ASSIGN(BaseGrowableArray);
219};
220
221template <typename T, typename B, typename Allocator>
222inline void BaseGrowableArray<T, B, Allocator>::Sort(int compare(const T*,
223 const T*)) {
224 // Avoid calling qsort with a null array.
225 if (length_ == 0) return;
226
227 typedef int (*CompareFunction)(const void*, const void*);
228 qsort(data_, length_, sizeof(T), reinterpret_cast<CompareFunction>(compare));
229}
230
231template <typename T, typename B, typename Allocator>
232void BaseGrowableArray<T, B, Allocator>::Resize(intptr_t new_length) {
233 if (new_length > capacity_) {
234 intptr_t new_capacity = Utils::RoundUpToPowerOfTwo(x: new_length);
235 T* new_data =
236 allocator_->template Realloc<T>(data_, capacity_, new_capacity);
237 ASSERT(new_data != nullptr);
238 data_ = new_data;
239 capacity_ = new_capacity;
240 }
241 length_ = new_length;
242}
243
244template <typename T, typename B, typename Allocator>
245void BaseGrowableArray<T, B, Allocator>::SetLength(intptr_t new_length) {
246 if (new_length > capacity_) {
247 T* new_data = allocator_->template Alloc<T>(new_length);
248 ASSERT(new_data != nullptr);
249 data_ = new_data;
250 capacity_ = new_length;
251 }
252 length_ = new_length;
253}
254
255class Malloc : public AllStatic {
256 public:
257 template <class T>
258 static inline T* Alloc(intptr_t len) {
259 return reinterpret_cast<T*>(dart::malloc(size: len * sizeof(T)));
260 }
261
262 template <class T>
263 static inline T* Realloc(T* old_array, intptr_t old_len, intptr_t new_len) {
264 return reinterpret_cast<T*>(dart::realloc(ptr: old_array, size: new_len * sizeof(T)));
265 }
266
267 template <class T>
268 static inline void Free(T* old_array, intptr_t old_len) {
269 free(old_array);
270 }
271};
272
273template <typename T>
274class MallocGrowableArray
275 : public BaseGrowableArray<T, MallocAllocated, Malloc> {
276 public:
277 explicit MallocGrowableArray(intptr_t initial_capacity)
278 : BaseGrowableArray<T, MallocAllocated, Malloc>(initial_capacity,
279 nullptr) {}
280 MallocGrowableArray()
281 : BaseGrowableArray<T, MallocAllocated, Malloc>(nullptr) {}
282};
283
284} // namespace dart
285
286#endif // RUNTIME_PLATFORM_GROWABLE_ARRAY_H_
287

source code of flutter_engine/third_party/dart/runtime/platform/growable_array.h