1 /*
2 * Copyright (c) 1997, 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_GROWABLEARRAY_HPP
26 #define SHARE_UTILITIES_GROWABLEARRAY_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/iterator.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include "utilities/ostream.hpp"
33 #include "utilities/powerOfTwo.hpp"
34
35 // A growable array.
36
37 /*************************************************************************/
38 /* */
39 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
40 /* */
41 /* Should you use GrowableArrays to contain handles you must be certain */
42 /* that the GrowableArray does not outlive the HandleMark that contains */
43 /* the handles. Since GrowableArrays are typically resource allocated */
44 /* the following is an example of INCORRECT CODE, */
45 /* */
46 /* ResourceMark rm; */
47 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
48 /* if (blah) { */
49 /* while (...) { */
50 /* HandleMark hm; */
51 /* ... */
52 /* Handle h(THREAD, some_oop); */
53 /* arr->append(h); */
54 /* } */
55 /* } */
56 /* if (arr->length() != 0 ) { */
57 /* oop bad_oop = arr->at(0)(); // Handle is BAD HERE. */
58 /* ... */
59 /* } */
60 /* */
61 /* If the GrowableArrays you are creating is C_Heap allocated then it */
62 /* should not hold handles since the handles could trivially try and */
63 /* outlive their HandleMark. In some situations you might need to do */
64 /* this and it would be legal but be very careful and see if you can do */
65 /* the code in some other manner. */
66 /* */
67 /*************************************************************************/
68
69 // Non-template base class responsible for handling the length and max.
70
71
72 class GrowableArrayBase : public AnyObj {
73 friend class VMStructs;
74
75 protected:
76 // Current number of accessible elements
77 int _len;
78 // Current number of allocated elements
79 int _capacity;
80
81 GrowableArrayBase(int capacity, int initial_len) :
82 _len(initial_len),
83 _capacity(capacity) {
84 assert(_len >= 0 && _len <= _capacity, "initial_len too big");
85 }
86
87 ~GrowableArrayBase() {}
88
89 public:
90 int length() const { return _len; }
91 int capacity() const { return _capacity; }
92
93 bool is_empty() const { return _len == 0; }
94 bool is_nonempty() const { return _len != 0; }
95 bool is_full() const { return _len == _capacity; }
96
97 void clear() { _len = 0; }
98 void trunc_to(int length) {
99 assert(length <= _len,"cannot increase length");
100 _len = length;
101 }
102 };
103
104 template <typename E> class GrowableArrayIterator;
105
106 // Extends GrowableArrayBase with a typed data array.
107 //
108 // E: Element type
109 //
110 // The "view" adds function that don't grow or deallocate
111 // the _data array, so there's no need for an allocator.
112 //
113 // The "view" can be used to type erase the allocator classes
114 // of GrowableArrayWithAllocator.
115 template <typename E>
116 class GrowableArrayView : public GrowableArrayBase {
117 protected:
118 E* _data; // data array
119
120 GrowableArrayView(E* data, int capacity, int initial_len) :
121 GrowableArrayBase(capacity, initial_len), _data(data) {}
122
123 ~GrowableArrayView() {}
124
125 public:
126 bool operator==(const GrowableArrayView& rhs) const {
127 if (_len != rhs._len)
128 return false;
129 for (int i = 0; i < _len; i++) {
130 if (at(i) != rhs.at(i)) {
131 return false;
132 }
133 }
134 return true;
135 }
136
137 bool operator!=(const GrowableArrayView& rhs) const {
138 return !(*this == rhs);
139 }
140
141 E& at(int i) {
142 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len);
143 return _data[i];
144 }
145
146 E const& at(int i) const {
147 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len);
148 return _data[i];
149 }
150
151 E* adr_at(int i) const {
152 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len);
153 return &_data[i];
154 }
155
156 E& first() {
157 assert(_len > 0, "empty");
158 return _data[0];
159 }
160
161 E const& first() const {
162 assert(_len > 0, "empty");
163 return _data[0];
164 }
165
166 E& top() {
167 assert(_len > 0, "empty");
168 return _data[_len - 1];
169 }
170
171 E const& top() const {
172 assert(_len > 0, "empty");
173 return _data[_len - 1];
174 }
175
176 E& last() {
177 return top();
178 }
179
180 E const& last() const {
181 return top();
182 }
183
184 GrowableArrayIterator<E> begin() const {
185 return GrowableArrayIterator<E>(this, 0);
186 }
187
188 GrowableArrayIterator<E> end() const {
189 return GrowableArrayIterator<E>(this, length());
190 }
191
192 E pop() {
193 assert(_len > 0, "empty list");
194 return _data[--_len];
195 }
196
197 void at_put(int i, const E& elem) {
198 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len);
199 _data[i] = elem;
200 }
201
202 bool contains(const E& elem) const {
203 for (int i = 0; i < _len; i++) {
204 if (_data[i] == elem) return true;
205 }
206 return false;
207 }
208
209 int find(const E& elem) const {
210 for (int i = 0; i < _len; i++) {
211 if (_data[i] == elem) return i;
212 }
213 return -1;
214 }
215
216 int find_from_end(const E& elem) const {
217 for (int i = _len-1; i >= 0; i--) {
218 if (_data[i] == elem) return i;
219 }
220 return -1;
221 }
222
223 // Find first element that matches the given predicate.
224 //
225 // Predicate: bool predicate(const E& elem)
226 //
227 // Returns the index of the element or -1 if no element matches the predicate
228 template<typename Predicate>
229 int find_if(Predicate predicate) const {
230 for (int i = 0; i < _len; i++) {
231 if (predicate(_data[i])) return i;
232 }
233 return -1;
234 }
235
236 // Find last element that matches the given predicate.
237 //
238 // Predicate: bool predicate(const E& elem)
239 //
240 // Returns the index of the element or -1 if no element matches the predicate
241 template<typename Predicate>
242 int find_from_end_if(Predicate predicate) const {
243 // start at the end of the array
244 for (int i = _len-1; i >= 0; i--) {
245 if (predicate(_data[i])) return i;
246 }
247 return -1;
248 }
249
250 // Order preserving remove operations.
251
252 void remove(const E& elem) {
253 // Assuming that element does exist.
254 bool removed = remove_if_existing(elem);
255 if (removed) return;
256 ShouldNotReachHere();
257 }
258
259 bool remove_if_existing(const E& elem) {
260 // Returns TRUE if elem is removed.
261 for (int i = 0; i < _len; i++) {
262 if (_data[i] == elem) {
263 remove_at(i);
264 return true;
265 }
266 }
267 return false;
268 }
269
270 void remove_at(int index) {
271 assert(0 <= index && index < _len, "illegal index %d for length %d", index, _len);
272 for (int j = index + 1; j < _len; j++) {
273 _data[j-1] = _data[j];
274 }
275 _len--;
276 }
277
278 // Remove all elements up to the index (exclusive). The order is preserved.
279 void remove_till(int idx) {
280 remove_range(0, idx);
281 }
282
283 // Remove all elements in the range [start - end). The order is preserved.
284 void remove_range(int start, int end) {
285 assert(0 <= start, "illegal start index %d", start);
286 assert(start < end && end <= _len, "erase called with invalid range (%d, %d) for length %d", start, end, _len);
287
288 for (int i = start, j = end; j < length(); i++, j++) {
289 at_put(i, at(j));
290 }
291 trunc_to(length() - (end - start));
292 }
293
294 // The order is changed.
295 void delete_at(int index) {
296 assert(0 <= index && index < _len, "illegal index %d for length %d", index, _len);
297 if (index < --_len) {
298 // Replace removed element with last one.
299 _data[index] = _data[_len];
300 }
301 }
302
303 void sort(int f(E*, E*)) {
304 if (_data == nullptr) return;
305 qsort(_data, length(), sizeof(E), (_sort_Fn)f);
306 }
307 // sort by fixed-stride sub arrays:
308 void sort(int f(E*, E*), int stride) {
309 if (_data == nullptr) return;
310 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
311 }
312
313 template <typename K, int compare(const K&, const E&)> int find_sorted(const K& key, bool& found) const {
314 found = false;
315 int min = 0;
316 int max = length() - 1;
317
318 while (max >= min) {
319 int mid = (int)(((uint)max + min) / 2);
320 E value = at(mid);
321 int diff = compare(key, value);
322 if (diff > 0) {
323 min = mid + 1;
324 } else if (diff < 0) {
325 max = mid - 1;
326 } else {
327 found = true;
328 return mid;
329 }
330 }
331 return min;
332 }
333
334 template <typename K>
335 int find_sorted(CompareClosure<E>* cc, const K& key, bool& found) {
336 found = false;
337 int min = 0;
338 int max = length() - 1;
339
340 while (max >= min) {
341 int mid = (int)(((uint)max + min) / 2);
342 E value = at(mid);
343 int diff = cc->do_compare(key, value);
344 if (diff > 0) {
345 min = mid + 1;
346 } else if (diff < 0) {
347 max = mid - 1;
348 } else {
349 found = true;
350 return mid;
351 }
352 }
353 return min;
354 }
355
356 void print() const {
357 tty->print("Growable Array " PTR_FORMAT, p2i(this));
358 tty->print(": length %d (capacity %d) { ", _len, _capacity);
359 for (int i = 0; i < _len; i++) {
360 tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
361 }
362 tty->print("}\n");
363 }
364 };
365
366 template <typename E>
367 class GrowableArrayFromArray : public GrowableArrayView<E> {
368 public:
369
370 GrowableArrayFromArray(E* data, int len) :
371 GrowableArrayView<E>(data, len, len) {}
372 };
373
374 // GrowableArrayWithAllocator extends the "view" with
375 // the capability to grow and deallocate the data array.
376 //
377 // The allocator responsibility is delegated to the sub-class.
378 //
379 // Derived: The sub-class responsible for allocation / deallocation
380 // - E* Derived::allocate() - member function responsible for allocation
381 // - void Derived::deallocate(E*) - member function responsible for deallocation
382 template <typename E, typename Derived>
383 class GrowableArrayWithAllocator : public GrowableArrayView<E> {
384 friend class VMStructs;
385
386 void expand_to(int j);
387 void grow(int j);
388
389 protected:
390 GrowableArrayWithAllocator(E* data, int capacity) :
391 GrowableArrayView<E>(data, capacity, 0) {
392 for (int i = 0; i < capacity; i++) {
393 ::new ((void*)&data[i]) E();
394 }
395 }
396
397 GrowableArrayWithAllocator(E* data, int capacity, int initial_len, const E& filler) :
398 GrowableArrayView<E>(data, capacity, initial_len) {
399 int i = 0;
400 for (; i < initial_len; i++) {
401 ::new ((void*)&data[i]) E(filler);
402 }
403 for (; i < capacity; i++) {
404 ::new ((void*)&data[i]) E();
405 }
406 }
407
408 ~GrowableArrayWithAllocator() {}
409
410 public:
411 int append(const E& elem) {
412 if (this->_len == this->_capacity) grow(this->_len);
413 int idx = this->_len++;
414 this->_data[idx] = elem;
415 return idx;
416 }
417
418 bool append_if_missing(const E& elem) {
419 // Returns TRUE if elem is added.
420 bool missed = !this->contains(elem);
421 if (missed) append(elem);
422 return missed;
423 }
424
425 void push(const E& elem) { append(elem); }
426
427 E& at_grow(int i, const E& fill = E()) {
428 assert(0 <= i, "negative index %d", i);
429 if (i >= this->_len) {
430 if (i >= this->_capacity) grow(i);
431 for (int j = this->_len; j <= i; j++)
432 this->_data[j] = fill;
433 this->_len = i+1;
434 }
435 return this->_data[i];
436 }
437
438 void at_put_grow(int i, const E& elem, const E& fill = E()) {
439 assert(0 <= i, "negative index %d", i);
440 if (i >= this->_len) {
441 if (i >= this->_capacity) grow(i);
442 for (int j = this->_len; j < i; j++)
443 this->_data[j] = fill;
444 this->_len = i+1;
445 }
446 this->_data[i] = elem;
447 }
448
449 // inserts the given element before the element at index i
450 void insert_before(const int idx, const E& elem) {
451 assert(0 <= idx && idx <= this->_len, "illegal index %d for length %d", idx, this->_len);
452 if (this->_len == this->_capacity) grow(this->_len);
453 for (int j = this->_len - 1; j >= idx; j--) {
454 this->_data[j + 1] = this->_data[j];
455 }
456 this->_len++;
457 this->_data[idx] = elem;
458 }
459
460 void insert_before(const int idx, const GrowableArrayView<E>* array) {
461 assert(0 <= idx && idx <= this->_len, "illegal index %d for length %d", idx, this->_len);
462 int array_len = array->length();
463 int new_len = this->_len + array_len;
464 if (new_len >= this->_capacity) grow(new_len);
465
466 for (int j = this->_len - 1; j >= idx; j--) {
467 this->_data[j + array_len] = this->_data[j];
468 }
469
470 for (int j = 0; j < array_len; j++) {
471 this->_data[idx + j] = array->at(j);
472 }
473
474 this->_len += array_len;
475 }
476
477 void appendAll(const GrowableArrayView<E>* l) {
478 for (int i = 0; i < l->length(); i++) {
479 this->at_put_grow(this->_len, l->at(i), E());
480 }
481 }
482
483 // Binary search and insertion utility. Search array for element
484 // matching key according to the static compare function. Insert
485 // that element if not already in the list. Assumes the list is
486 // already sorted according to compare function.
487 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
488 bool found;
489 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
490 if (!found) {
491 insert_before(location, key);
492 }
493 return this->at(location);
494 }
495
496 E insert_sorted(CompareClosure<E>* cc, const E& key) {
497 bool found;
498 int location = find_sorted(cc, key, found);
499 if (!found) {
500 insert_before(location, key);
501 }
502 return this->at(location);
503 }
504
505 void swap(GrowableArrayWithAllocator* other) {
506 ::swap(this->_data, other->_data);
507 ::swap(this->_len, other->_len);
508 ::swap(this->_capacity, other->_capacity);
509 }
510
511 // Ensure capacity is at least new_capacity.
512 void reserve(int new_capacity);
513
514 // Reduce capacity to length.
515 void shrink_to_fit();
516
517 void clear_and_deallocate();
518 };
519
520 template <typename E, typename Derived>
521 void GrowableArrayWithAllocator<E, Derived>::expand_to(int new_capacity) {
522 int old_capacity = this->_capacity;
523 assert(new_capacity > old_capacity,
524 "expected growth but %d <= %d", new_capacity, old_capacity);
525 this->_capacity = new_capacity;
526 E* newData = static_cast<Derived*>(this)->allocate();
527 int i = 0;
528 for ( ; i < this->_len; i++) ::new ((void*)&newData[i]) E(this->_data[i]);
529 for ( ; i < this->_capacity; i++) ::new ((void*)&newData[i]) E();
530 for (i = 0; i < old_capacity; i++) this->_data[i].~E();
531 if (this->_data != nullptr) {
532 static_cast<Derived*>(this)->deallocate(this->_data);
533 }
534 this->_data = newData;
535 }
536
537 template <typename E, typename Derived>
538 void GrowableArrayWithAllocator<E, Derived>::grow(int j) {
539 // grow the array by increasing _capacity to the first power of two larger than the size we need
540 expand_to(next_power_of_2(j));
541 }
542
543 template <typename E, typename Derived>
544 void GrowableArrayWithAllocator<E, Derived>::reserve(int new_capacity) {
545 if (new_capacity > this->_capacity) {
546 expand_to(new_capacity);
547 }
548 }
549
550 template <typename E, typename Derived>
551 void GrowableArrayWithAllocator<E, Derived>::shrink_to_fit() {
552 int old_capacity = this->_capacity;
553 int len = this->_len;
554 assert(len <= old_capacity, "invariant");
555
556 // If already at full capacity, nothing to do.
557 if (len == old_capacity) {
558 return;
559 }
560
561 // If not empty, allocate new, smaller, data, and copy old data to it.
562 E* old_data = this->_data;
563 E* new_data = nullptr;
564 this->_capacity = len; // Must preceed allocate().
565 if (len > 0) {
566 new_data = static_cast<Derived*>(this)->allocate();
567 for (int i = 0; i < len; ++i) ::new (&new_data[i]) E(old_data[i]);
568 }
569 // Destroy contents of old data, and deallocate it.
570 for (int i = 0; i < old_capacity; ++i) old_data[i].~E();
571 if (old_data != nullptr) {
572 static_cast<Derived*>(this)->deallocate(old_data);
573 }
574 // Install new data, which might be nullptr.
575 this->_data = new_data;
576 }
577
578 template <typename E, typename Derived>
579 void GrowableArrayWithAllocator<E, Derived>::clear_and_deallocate() {
580 this->clear();
581 this->shrink_to_fit();
582 }
583
584 class GrowableArrayResourceAllocator {
585 public:
586 static void* allocate(int max, int element_size);
587 };
588
589 // Arena allocator
590 class GrowableArrayArenaAllocator {
591 public:
592 static void* allocate(int max, int element_size, Arena* arena);
593 };
594
595 // CHeap allocator
596 class GrowableArrayCHeapAllocator {
597 public:
598 static void* allocate(int max, int element_size, MemTag mem_tag);
599 static void deallocate(void* mem);
600 };
601
602 #ifdef ASSERT
603
604 // Checks resource allocation nesting
605 class GrowableArrayNestingCheck {
606 // resource area nesting at creation
607 int _nesting;
608
609 public:
610 GrowableArrayNestingCheck(bool on_resource_area);
611
612 void on_resource_area_alloc() const;
613 };
614
615 #endif // ASSERT
616
617 // Encodes where the backing array is allocated
618 // and performs necessary checks.
619 class GrowableArrayMetadata {
620 uintptr_t _bits;
621
622 // resource area nesting at creation
623 debug_only(GrowableArrayNestingCheck _nesting_check;)
624
625 // Resource allocation
626 static uintptr_t bits() {
627 return 0;
628 }
629
630 // CHeap allocation
631 static uintptr_t bits(MemTag mem_tag) {
632 assert(mem_tag != mtNone, "Must provide a proper MemTag");
633 return (uintptr_t(mem_tag) << 1) | 1;
634 }
635
636 // Arena allocation
637 static uintptr_t bits(Arena* arena) {
638 assert((uintptr_t(arena) & 1) == 0, "Required for on_C_heap() to work");
639 return uintptr_t(arena);
640 }
641
642 public:
643 // Resource allocation
644 GrowableArrayMetadata() :
645 _bits(bits())
646 debug_only(COMMA _nesting_check(true)) {
647 }
648
649 // Arena allocation
650 GrowableArrayMetadata(Arena* arena) :
651 _bits(bits(arena))
652 debug_only(COMMA _nesting_check(false)) {
653 }
654
655 // CHeap allocation
656 GrowableArrayMetadata(MemTag mem_tag) :
657 _bits(bits(mem_tag))
658 debug_only(COMMA _nesting_check(false)) {
659 }
660
661 #ifdef ASSERT
662 GrowableArrayMetadata(const GrowableArrayMetadata& other) :
663 _bits(other._bits),
664 _nesting_check(other._nesting_check) {
665 assert(!on_C_heap(), "Copying of CHeap arrays not supported");
666 assert(!other.on_C_heap(), "Copying of CHeap arrays not supported");
667 }
668
669 GrowableArrayMetadata& operator=(const GrowableArrayMetadata& other) {
670 _bits = other._bits;
671 _nesting_check = other._nesting_check;
672 assert(!on_C_heap(), "Assignment of CHeap arrays not supported");
673 assert(!other.on_C_heap(), "Assignment of CHeap arrays not supported");
674 return *this;
675 }
676
677 void init_checks(const GrowableArrayBase* array) const;
678 void on_resource_area_alloc_check() const;
679 #endif // ASSERT
680
681 bool on_C_heap() const { return (_bits & 1) == 1; }
682 bool on_resource_area() const { return _bits == 0; }
683 bool on_arena() const { return (_bits & 1) == 0 && _bits != 0; }
684
685 Arena* arena() const { return (Arena*)_bits; }
686 MemTag mem_tag() const { return MemTag(_bits >> 1); }
687 };
688
689 // THE GrowableArray.
690 //
691 // Supports multiple allocation strategies:
692 // - Resource stack allocation: if no extra argument is provided
693 // - CHeap allocation: if mem_tag is provided
694 // - Arena allocation: if an arena is provided
695 //
696 // There are some drawbacks of using GrowableArray, that are removed in some
697 // of the other implementations of GrowableArrayWithAllocator sub-classes:
698 //
699 // Memory overhead: The multiple allocation strategies uses extra metadata
700 // embedded in the instance.
701 //
702 // Strict allocation locations: There are rules about where the GrowableArray
703 // instance is allocated, that depends on where the data array is allocated.
704 // See: init_checks.
705
706 template <typename E>
707 class GrowableArray : public GrowableArrayWithAllocator<E, GrowableArray<E>> {
708 friend class GrowableArrayWithAllocator<E, GrowableArray>;
709 friend class GrowableArrayTest;
710
711 static E* allocate(int max) {
712 return (E*)GrowableArrayResourceAllocator::allocate(max, sizeof(E));
713 }
714
715 static E* allocate(int max, MemTag mem_tag) {
716 return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), mem_tag);
717 }
718
719 static E* allocate(int max, Arena* arena) {
720 return (E*)GrowableArrayArenaAllocator::allocate(max, sizeof(E), arena);
721 }
722
723 GrowableArrayMetadata _metadata;
724
725 void init_checks() const { debug_only(_metadata.init_checks(this);) }
726
727 // Where are we going to allocate memory?
728 bool on_C_heap() const { return _metadata.on_C_heap(); }
729 bool on_resource_area() const { return _metadata.on_resource_area(); }
730 bool on_arena() const { return _metadata.on_arena(); }
731
732 E* allocate() {
733 if (on_resource_area()) {
734 debug_only(_metadata.on_resource_area_alloc_check());
735 return allocate(this->_capacity);
736 }
737
738 if (on_C_heap()) {
739 return allocate(this->_capacity, _metadata.mem_tag());
740 }
741
742 assert(on_arena(), "Sanity");
743 return allocate(this->_capacity, _metadata.arena());
744 }
745
746 void deallocate(E* mem) {
747 if (on_C_heap()) {
748 GrowableArrayCHeapAllocator::deallocate(mem);
749 }
750 }
751
752 public:
753 GrowableArray() : GrowableArray(2 /* initial_capacity */) {}
754
755 explicit GrowableArray(int initial_capacity) :
756 GrowableArrayWithAllocator<E, GrowableArray>(
757 allocate(initial_capacity),
758 initial_capacity),
759 _metadata() {
760 init_checks();
761 }
762
763 GrowableArray(int initial_capacity, MemTag mem_tag) :
764 GrowableArrayWithAllocator<E, GrowableArray>(
765 allocate(initial_capacity, mem_tag),
766 initial_capacity),
767 _metadata(mem_tag) {
768 init_checks();
769 }
770
771 GrowableArray(int initial_capacity, int initial_len, const E& filler) :
772 GrowableArrayWithAllocator<E, GrowableArray>(
773 allocate(initial_capacity),
774 initial_capacity, initial_len, filler),
775 _metadata() {
776 init_checks();
777 }
778
779 GrowableArray(int initial_capacity, int initial_len, const E& filler, MemTag mem_tag) :
780 GrowableArrayWithAllocator<E, GrowableArray>(
781 allocate(initial_capacity, mem_tag),
782 initial_capacity, initial_len, filler),
783 _metadata(mem_tag) {
784 init_checks();
785 }
786
787 GrowableArray(Arena* arena, int initial_capacity, int initial_len, const E& filler) :
788 GrowableArrayWithAllocator<E, GrowableArray>(
789 allocate(initial_capacity, arena),
790 initial_capacity, initial_len, filler),
791 _metadata(arena) {
792 init_checks();
793 }
794
795 ~GrowableArray() {
796 if (on_C_heap()) {
797 this->clear_and_deallocate();
798 }
799 }
800 };
801
802 // Leaner GrowableArray for CHeap backed data arrays, with compile-time decided MemTag.
803 template <typename E, MemTag MT>
804 class GrowableArrayCHeap : public GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> > {
805 friend class GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >;
806
807 STATIC_ASSERT(MT != mtNone);
808
809 static E* allocate(int max, MemTag mem_tag) {
810 if (max == 0) {
811 return nullptr;
812 }
813
814 return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), mem_tag);
815 }
816
817 NONCOPYABLE(GrowableArrayCHeap);
818
819 E* allocate() {
820 return allocate(this->_capacity, MT);
821 }
822
823 void deallocate(E* mem) {
824 GrowableArrayCHeapAllocator::deallocate(mem);
825 }
826
827 public:
828 GrowableArrayCHeap(int initial_capacity = 0) :
829 GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >(
830 allocate(initial_capacity, MT),
831 initial_capacity) {}
832
833 GrowableArrayCHeap(int initial_capacity, int initial_len, const E& filler) :
834 GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >(
835 allocate(initial_capacity, MT),
836 initial_capacity, initial_len, filler) {}
837
838 ~GrowableArrayCHeap() {
839 this->clear_and_deallocate();
840 }
841
842 void* operator new(size_t size) {
843 return AnyObj::operator new(size, MT);
844 }
845
846 void* operator new(size_t size, const std::nothrow_t& nothrow_constant) throw() {
847 return AnyObj::operator new(size, nothrow_constant, MT);
848 }
849 void operator delete(void *p) {
850 AnyObj::operator delete(p);
851 }
852 };
853
854 // Custom STL-style iterator to iterate over GrowableArrays
855 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
856 template <typename E>
857 class GrowableArrayIterator : public StackObj {
858 friend class GrowableArrayView<E>;
859
860 private:
861 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
862 int _position; // The current position in the GrowableArray
863
864 // Private constructor used in GrowableArray::begin() and GrowableArray::end()
865 GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
866 assert(0 <= position && position <= _array->length(), "illegal position");
867 }
868
869 public:
870 GrowableArrayIterator() : _array(nullptr), _position(0) { }
871 GrowableArrayIterator& operator++() { ++_position; return *this; }
872 E operator*() { return _array->at(_position); }
873
874 bool operator==(const GrowableArrayIterator& rhs) {
875 assert(_array == rhs._array, "iterator belongs to different array");
876 return _position == rhs._position;
877 }
878
879 bool operator!=(const GrowableArrayIterator& rhs) {
880 assert(_array == rhs._array, "iterator belongs to different array");
881 return _position != rhs._position;
882 }
883 };
884
885 // Arrays for basic types
886 typedef GrowableArray<int> intArray;
887 typedef GrowableArray<int> intStack;
888 typedef GrowableArray<bool> boolArray;
889
890 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP