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_(NULL), allocator_(allocator) {}
23
24 BaseGrowableArray(intptr_t initial_capacity, Allocator* allocator)
25 : length_(0), capacity_(0), data_(NULL), allocator_(allocator) {
26 if (initial_capacity > 0) {
27 capacity_ = Utils::RoundUpToPowerOfTwo(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_ = NULL;
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 void Add(const T& value) {
70 Resize(length() + 1);
71 Last() = value;
72 }
73
74 T& RemoveLast() {
75 ASSERT(length_ > 0);
76 T& result = operator[](length_ - 1);
77 length_--;
78 return result;
79 }
80
81 T& operator[](intptr_t index) const {
82 ASSERT(0 <= index);
83 ASSERT(index < length_);
84 ASSERT(length_ <= capacity_);
85 return data_[index];
86 }
87
88 void FillWith(const T& value, intptr_t start, intptr_t length) {
89 ASSERT(start >= 0);
90 ASSERT(length >= 0);
91 ASSERT(start <= length_);
92
93 Resize(start + length);
94 for (intptr_t i = 0; i < length; ++i) {
95 data_[start + i] = value;
96 }
97 }
98
99 void EnsureLength(intptr_t new_length, const T& default_value) {
100 const intptr_t old_length = length_;
101 if (old_length < new_length) {
102 Resize(new_length);
103 for (intptr_t i = old_length; i < new_length; ++i) {
104 (*this)[i] = default_value;
105 }
106 }
107 }
108
109 const T& At(intptr_t index) const { return operator[](index); }
110
111 T& Last() const {
112 ASSERT(length_ > 0);
113 return operator[](length_ - 1);
114 }
115
116 void AddArray(const BaseGrowableArray<T, B, Allocator>& src) {
117 for (intptr_t i = 0; i < src.length(); i++) {
118 Add(src[i]);
119 }
120 }
121
122 void Clear() { length_ = 0; }
123
124 void InsertAt(intptr_t idx, const T& value) {
125 Resize(length() + 1);
126 for (intptr_t i = length_ - 2; i >= idx; i--) {
127 data_[i + 1] = data_[i];
128 }
129 data_[idx] = value;
130 }
131
132 void Reverse() {
133 for (intptr_t i = 0; i < length_ / 2; i++) {
134 const intptr_t j = length_ - 1 - i;
135 T temp = data_[i];
136 data_[i] = data_[j];
137 data_[j] = temp;
138 }
139 }
140
141 // Swap entries |i| and |j|.
142 void Swap(intptr_t i, intptr_t j) {
143 ASSERT(i >= 0);
144 ASSERT(j >= 0);
145 ASSERT(i < length_);
146 ASSERT(j < length_);
147 T temp = data_[i];
148 data_[i] = data_[j];
149 data_[j] = temp;
150 }
151
152 // NOTE: Does not preserve array order.
153 void RemoveAt(intptr_t i) {
154 ASSERT(i >= 0);
155 ASSERT(i < length_);
156 intptr_t last = length_ - 1;
157 if (i < last) {
158 Swap(i, last);
159 }
160 RemoveLast();
161 }
162
163 // Preserves array order.
164 void EraseAt(intptr_t idx) {
165 ASSERT(idx >= 0);
166 ASSERT(idx < length_);
167 for (intptr_t i = idx; i < length_ - 1; i++) {
168 data_[i] = data_[i + 1];
169 }
170 RemoveLast();
171 }
172
173 // The content is uninitialized after calling it.
174 void SetLength(intptr_t new_length);
175
176 // Sort the array in place.
177 inline void Sort(int compare(const T*, const T*));
178
179 void StealBuffer(T** buffer, intptr_t* length) {
180 *buffer = data_;
181 *length = length_;
182 data_ = NULL;
183 length_ = 0;
184 capacity_ = 0;
185 }
186
187 T* begin() { return &data_[0]; }
188 const T* begin() const { return &data_[0]; }
189
190 T* end() { return &data_[length_]; }
191 const T* end() const { return &data_[length_]; }
192
193 private:
194 intptr_t length_;
195 intptr_t capacity_;
196 T* data_;
197 Allocator* allocator_; // Used to (re)allocate the array.
198
199 // Used for growing the array.
200 void Resize(intptr_t new_length);
201
202 DISALLOW_COPY_AND_ASSIGN(BaseGrowableArray);
203};
204
205template <typename T, typename B, typename Allocator>
206inline void BaseGrowableArray<T, B, Allocator>::Sort(int compare(const T*,
207 const T*)) {
208 // Avoid calling qsort with a null array.
209 if (length_ == 0) return;
210
211 typedef int (*CompareFunction)(const void*, const void*);
212 qsort(data_, length_, sizeof(T), reinterpret_cast<CompareFunction>(compare));
213}
214
215template <typename T, typename B, typename Allocator>
216void BaseGrowableArray<T, B, Allocator>::Resize(intptr_t new_length) {
217 if (new_length > capacity_) {
218 intptr_t new_capacity = Utils::RoundUpToPowerOfTwo(new_length);
219 T* new_data =
220 allocator_->template Realloc<T>(data_, capacity_, new_capacity);
221 ASSERT(new_data != NULL);
222 data_ = new_data;
223 capacity_ = new_capacity;
224 }
225 length_ = new_length;
226}
227
228template <typename T, typename B, typename Allocator>
229void BaseGrowableArray<T, B, Allocator>::SetLength(intptr_t new_length) {
230 if (new_length > capacity_) {
231 T* new_data = allocator_->template Alloc<T>(new_length);
232 ASSERT(new_data != NULL);
233 data_ = new_data;
234 capacity_ = new_length;
235 }
236 length_ = new_length;
237}
238
239class Malloc : public AllStatic {
240 public:
241 template <class T>
242 static inline T* Alloc(intptr_t len) {
243 return reinterpret_cast<T*>(malloc(len * sizeof(T)));
244 }
245
246 template <class T>
247 static inline T* Realloc(T* old_array, intptr_t old_len, intptr_t new_len) {
248 return reinterpret_cast<T*>(realloc(old_array, new_len * sizeof(T)));
249 }
250
251 template <class T>
252 static inline void Free(T* old_array, intptr_t old_len) {
253 free(old_array);
254 }
255};
256
257class EmptyBase {};
258
259template <typename T>
260class MallocGrowableArray : public BaseGrowableArray<T, EmptyBase, Malloc> {
261 public:
262 explicit MallocGrowableArray(intptr_t initial_capacity)
263 : BaseGrowableArray<T, EmptyBase, Malloc>(initial_capacity, NULL) {}
264 MallocGrowableArray() : BaseGrowableArray<T, EmptyBase, Malloc>(NULL) {}
265};
266
267} // namespace dart
268
269#endif // RUNTIME_PLATFORM_GROWABLE_ARRAY_H_
270