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