1 /*
2 * Copyright (c) 1997, 2025, 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(E* data, int capacity, int initial_len) :
409 GrowableArrayView<E>(data, capacity, initial_len) {}
410
411 ~GrowableArrayWithAllocator() {}
412
413 public:
414 int append(const E& elem) {
415 if (this->_len == this->_capacity) grow(this->_len);
416 int idx = this->_len++;
417 this->_data[idx] = elem;
418 return idx;
419 }
420
421 bool append_if_missing(const E& elem) {
422 // Returns TRUE if elem is added.
423 bool missed = !this->contains(elem);
424 if (missed) append(elem);
425 return missed;
426 }
427
428 void push(const E& elem) { append(elem); }
429
430 E& at_grow(int i, const E& fill = E()) {
431 assert(0 <= i, "negative index %d", i);
432 if (i >= this->_len) {
433 if (i >= this->_capacity) grow(i);
434 for (int j = this->_len; j <= i; j++)
435 this->_data[j] = fill;
436 this->_len = i+1;
437 }
438 return this->_data[i];
439 }
440
441 void at_put_grow(int i, const E& elem, const E& fill = E()) {
442 assert(0 <= i, "negative index %d", i);
443 if (i >= this->_len) {
444 if (i >= this->_capacity) grow(i);
445 for (int j = this->_len; j < i; j++)
446 this->_data[j] = fill;
447 this->_len = i+1;
448 }
449 this->_data[i] = elem;
450 }
451
452 // inserts the given element before the element at index i
453 void insert_before(const int idx, const E& elem) {
454 assert(0 <= idx && idx <= this->_len, "illegal index %d for length %d", idx, this->_len);
455 if (this->_len == this->_capacity) grow(this->_len);
456 for (int j = this->_len - 1; j >= idx; j--) {
457 this->_data[j + 1] = this->_data[j];
458 }
459 this->_len++;
460 this->_data[idx] = elem;
461 }
462
463 void insert_before(const int idx, const GrowableArrayView<E>* array) {
464 assert(0 <= idx && idx <= this->_len, "illegal index %d for length %d", idx, this->_len);
465 int array_len = array->length();
466 int new_len = this->_len + array_len;
467 if (new_len >= this->_capacity) grow(new_len);
468
469 for (int j = this->_len - 1; j >= idx; j--) {
470 this->_data[j + array_len] = this->_data[j];
471 }
472
473 for (int j = 0; j < array_len; j++) {
474 this->_data[idx + j] = array->at(j);
475 }
476
477 this->_len += array_len;
478 }
479
480 void appendAll(const GrowableArrayView<E>* l) {
481 for (int i = 0; i < l->length(); i++) {
482 this->at_put_grow(this->_len, l->at(i), E());
483 }
484 }
485
486 // Binary search and insertion utility. Search array for element
487 // matching key according to the static compare function. Insert
488 // that element if not already in the list. Assumes the list is
489 // already sorted according to compare function.
490 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
491 bool found;
492 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
493 if (!found) {
494 insert_before(location, key);
495 }
496 return this->at(location);
497 }
498
499 E insert_sorted(CompareClosure<E>* cc, const E& key) {
500 bool found;
501 int location = find_sorted(cc, key, found);
502 if (!found) {
503 insert_before(location, key);
504 }
505 return this->at(location);
506 }
507
508 void swap(GrowableArrayWithAllocator* other) {
509 ::swap(this->_data, other->_data);
510 ::swap(this->_len, other->_len);
511 ::swap(this->_capacity, other->_capacity);
512 }
513
514 // Ensure capacity is at least new_capacity.
515 void reserve(int new_capacity);
516
517 // Reduce capacity to length.
518 void shrink_to_fit();
519
520 void clear_and_deallocate();
521 };
522
523 template <typename E, typename Derived>
524 void GrowableArrayWithAllocator<E, Derived>::expand_to(int new_capacity) {
525 int old_capacity = this->_capacity;
526 assert(new_capacity > old_capacity,
527 "expected growth but %d <= %d", new_capacity, old_capacity);
528 this->_capacity = new_capacity;
529 E* newData = static_cast<Derived*>(this)->allocate();
530 int i = 0;
531 for ( ; i < this->_len; i++) ::new ((void*)&newData[i]) E(this->_data[i]);
532 for ( ; i < this->_capacity; i++) ::new ((void*)&newData[i]) E();
533 for (i = 0; i < old_capacity; i++) this->_data[i].~E();
534 if (this->_data != nullptr) {
535 static_cast<Derived*>(this)->deallocate(this->_data);
536 }
537 this->_data = newData;
538 }
539
540 template <typename E, typename Derived>
541 void GrowableArrayWithAllocator<E, Derived>::grow(int j) {
542 // grow the array by increasing _capacity to the first power of two larger than the size we need
543 expand_to(next_power_of_2(j));
544 }
545
546 template <typename E, typename Derived>
547 void GrowableArrayWithAllocator<E, Derived>::reserve(int new_capacity) {
548 if (new_capacity > this->_capacity) {
549 expand_to(new_capacity);
550 }
551 }
552
553 template <typename E, typename Derived>
554 void GrowableArrayWithAllocator<E, Derived>::shrink_to_fit() {
555 int old_capacity = this->_capacity;
556 int len = this->_len;
557 assert(len <= old_capacity, "invariant");
558
559 // If already at full capacity, nothing to do.
560 if (len == old_capacity) {
561 return;
562 }
563
564 // If not empty, allocate new, smaller, data, and copy old data to it.
565 E* old_data = this->_data;
566 E* new_data = nullptr;
567 this->_capacity = len; // Must preceed allocate().
568 if (len > 0) {
569 new_data = static_cast<Derived*>(this)->allocate();
570 for (int i = 0; i < len; ++i) ::new (&new_data[i]) E(old_data[i]);
571 }
572 // Destroy contents of old data, and deallocate it.
573 for (int i = 0; i < old_capacity; ++i) old_data[i].~E();
574 if (old_data != nullptr) {
575 static_cast<Derived*>(this)->deallocate(old_data);
576 }
577 // Install new data, which might be nullptr.
578 this->_data = new_data;
579 }
580
581 template <typename E, typename Derived>
582 void GrowableArrayWithAllocator<E, Derived>::clear_and_deallocate() {
583 this->clear();
584 this->shrink_to_fit();
585 }
586
587 class GrowableArrayResourceAllocator {
588 public:
589 static void* allocate(int max, int element_size);
590 };
591
592 // Arena allocator
593 class GrowableArrayArenaAllocator {
594 public:
595 static void* allocate(int max, int element_size, Arena* arena);
596 };
597
598 // CHeap allocator
599 class GrowableArrayCHeapAllocator {
600 public:
601 static void* allocate(int max, int element_size, MemTag mem_tag);
602 static void deallocate(void* mem);
603 };
604
605 #ifdef ASSERT
606
607 // Checks resource allocation nesting
608 class GrowableArrayNestingCheck {
609 // resource area nesting at creation
610 int _nesting;
611
612 public:
613 GrowableArrayNestingCheck(bool on_resource_area);
614 GrowableArrayNestingCheck(Arena* arena);
615
616 void on_resource_area_alloc() const;
617 void on_arena_alloc(Arena* arena) const;
618 };
619
620 #endif // ASSERT
621
622 // Encodes where the backing array is allocated
623 // and performs necessary checks.
624 class GrowableArrayMetadata {
625 uintptr_t _bits;
626
627 // resource area nesting at creation
628 DEBUG_ONLY(GrowableArrayNestingCheck _nesting_check;)
629
630 // Resource allocation
631 static uintptr_t bits() {
632 return 0;
633 }
634
635 // CHeap allocation
636 static uintptr_t bits(MemTag mem_tag) {
637 assert(mem_tag != mtNone, "Must provide a proper MemTag");
638 return (uintptr_t(mem_tag) << 1) | 1;
639 }
640
641 // Arena allocation
642 static uintptr_t bits(Arena* arena) {
643 assert((uintptr_t(arena) & 1) == 0, "Required for on_C_heap() to work");
644 return uintptr_t(arena);
645 }
646
647 public:
648 // Resource allocation
649 GrowableArrayMetadata() :
650 _bits(bits())
651 DEBUG_ONLY(COMMA _nesting_check(true)) {
652 }
653
654 // Arena allocation
655 GrowableArrayMetadata(Arena* arena) :
656 _bits(bits(arena))
657 DEBUG_ONLY(COMMA _nesting_check(arena)) {
658 }
659
660 // CHeap allocation
661 GrowableArrayMetadata(MemTag mem_tag) :
662 _bits(bits(mem_tag))
663 DEBUG_ONLY(COMMA _nesting_check(false)) {
664 }
665
666 #ifdef ASSERT
667 GrowableArrayMetadata(const GrowableArrayMetadata& other) :
668 _bits(other._bits),
669 _nesting_check(other._nesting_check) {
670 assert(!on_C_heap(), "Copying of CHeap arrays not supported");
671 assert(!other.on_C_heap(), "Copying of CHeap arrays not supported");
672 }
673
674 GrowableArrayMetadata& operator=(const GrowableArrayMetadata& other) {
675 _bits = other._bits;
676 _nesting_check = other._nesting_check;
677 assert(!on_C_heap(), "Assignment of CHeap arrays not supported");
678 assert(!other.on_C_heap(), "Assignment of CHeap arrays not supported");
679 return *this;
680 }
681
682 void init_checks(const GrowableArrayBase* array) const;
683 void on_resource_area_alloc_check() const;
684 void on_arena_alloc_check() const;
685 #endif // ASSERT
686
687 bool on_C_heap() const { return (_bits & 1) == 1; }
688 bool on_resource_area() const { return _bits == 0; }
689 bool on_arena() const { return (_bits & 1) == 0 && _bits != 0; }
690
691 Arena* arena() const { return (Arena*)_bits; }
692 MemTag mem_tag() const { return MemTag(_bits >> 1); }
693 };
694
695 // THE GrowableArray.
696 //
697 // Supports multiple allocation strategies:
698 // - Resource stack allocation: if no extra argument is provided
699 // - CHeap allocation: if mem_tag is provided
700 // - Arena allocation: if an arena is provided
701 //
702 // There are some drawbacks of using GrowableArray, that are removed in some
703 // of the other implementations of GrowableArrayWithAllocator sub-classes:
704 //
705 // Memory overhead: The multiple allocation strategies uses extra metadata
706 // embedded in the instance.
707 //
708 // Strict allocation locations: There are rules about where the GrowableArray
709 // instance is allocated, that depends on where the data array is allocated.
710 // See: init_checks.
711
712 template <typename E>
713 class GrowableArray : public GrowableArrayWithAllocator<E, GrowableArray<E>> {
714 friend class GrowableArrayWithAllocator<E, GrowableArray>;
715 friend class GrowableArrayTest;
716
717 static E* allocate(int max) {
718 return (E*)GrowableArrayResourceAllocator::allocate(max, sizeof(E));
719 }
720
721 static E* allocate(int max, MemTag mem_tag) {
722 return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), mem_tag);
723 }
724
725 static E* allocate(int max, Arena* arena) {
726 return (E*)GrowableArrayArenaAllocator::allocate(max, sizeof(E), arena);
727 }
728
729 GrowableArrayMetadata _metadata;
730
731 void init_checks() const { DEBUG_ONLY(_metadata.init_checks(this);) }
732
733 // Where are we going to allocate memory?
734 bool on_C_heap() const { return _metadata.on_C_heap(); }
735 bool on_resource_area() const { return _metadata.on_resource_area(); }
736 bool on_arena() const { return _metadata.on_arena(); }
737
738 E* allocate() {
739 if (on_resource_area()) {
740 DEBUG_ONLY(_metadata.on_resource_area_alloc_check());
741 return allocate(this->_capacity);
742 }
743
744 if (on_C_heap()) {
745 return allocate(this->_capacity, _metadata.mem_tag());
746 }
747
748 assert(on_arena(), "Sanity");
749 DEBUG_ONLY(_metadata.on_arena_alloc_check());
750 return allocate(this->_capacity, _metadata.arena());
751 }
752
753 void deallocate(E* mem) {
754 if (on_C_heap()) {
755 GrowableArrayCHeapAllocator::deallocate(mem);
756 }
757 }
758
759 public:
760 GrowableArray() : GrowableArray(2 /* initial_capacity */) {}
761
762 explicit GrowableArray(int initial_capacity) :
763 GrowableArrayWithAllocator<E, GrowableArray>(
764 allocate(initial_capacity),
765 initial_capacity),
766 _metadata() {
767 init_checks();
768 }
769
770 GrowableArray(int initial_capacity, MemTag mem_tag) :
771 GrowableArrayWithAllocator<E, GrowableArray>(
772 allocate(initial_capacity, mem_tag),
773 initial_capacity),
774 _metadata(mem_tag) {
775 init_checks();
776 }
777
778 GrowableArray(int initial_capacity, int initial_len, const E& filler) :
779 GrowableArrayWithAllocator<E, GrowableArray>(
780 allocate(initial_capacity),
781 initial_capacity, initial_len, filler),
782 _metadata() {
783 init_checks();
784 }
785
786 // This constructor performs no default initialization, so be careful.
787 GrowableArray(int initial_capacity, int initial_len, MemTag mem_tag) :
788 GrowableArrayWithAllocator<E, GrowableArray>(
789 allocate(initial_capacity, mem_tag),
790 initial_capacity, initial_len),
791 _metadata(mem_tag) {
792 init_checks();
793 }
794
795 GrowableArray(int initial_capacity, int initial_len, const E& filler, MemTag mem_tag) :
796 GrowableArrayWithAllocator<E, GrowableArray>(
797 allocate(initial_capacity, mem_tag),
798 initial_capacity, initial_len, filler),
799 _metadata(mem_tag) {
800 init_checks();
801 }
802
803 GrowableArray(Arena* arena, int initial_capacity, int initial_len, const E& filler) :
804 GrowableArrayWithAllocator<E, GrowableArray>(
805 allocate(initial_capacity, arena),
806 initial_capacity, initial_len, filler),
807 _metadata(arena) {
808 init_checks();
809 }
810
811 ~GrowableArray() {
812 if (on_C_heap()) {
813 this->clear_and_deallocate();
814 }
815 }
816 };
817
818 // Leaner GrowableArray for CHeap backed data arrays, with compile-time decided MemTag.
819 template <typename E, MemTag MT>
820 class GrowableArrayCHeap : public GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> > {
821 friend class GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >;
822
823 STATIC_ASSERT(MT != mtNone);
824
825 static E* allocate(int max, MemTag mem_tag) {
826 return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), mem_tag);
827 }
828
829 NONCOPYABLE(GrowableArrayCHeap);
830
831 E* allocate() {
832 return allocate(this->_capacity, MT);
833 }
834
835 void deallocate(E* mem) {
836 GrowableArrayCHeapAllocator::deallocate(mem);
837 }
838
839 public:
840 GrowableArrayCHeap(int initial_capacity = 0) :
841 GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >(
842 allocate(initial_capacity, MT),
843 initial_capacity) {}
844
845 GrowableArrayCHeap(int initial_capacity, int initial_len, const E& filler) :
846 GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >(
847 allocate(initial_capacity, MT),
848 initial_capacity, initial_len, filler) {}
849
850 ~GrowableArrayCHeap() {
851 this->clear_and_deallocate();
852 }
853
854 void* operator new(size_t size) {
855 return AnyObj::operator new(size, MT);
856 }
857
858 void* operator new(size_t size, const std::nothrow_t& nothrow_constant) throw() {
859 return AnyObj::operator new(size, nothrow_constant, MT);
860 }
861 void operator delete(void *p) {
862 AnyObj::operator delete(p);
863 }
864 };
865
866 // Custom STL-style iterator to iterate over GrowableArrays
867 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
868 template <typename E>
869 class GrowableArrayIterator : public StackObj {
870 friend class GrowableArrayView<E>;
871
872 private:
873 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
874 int _position; // The current position in the GrowableArray
875
876 // Private constructor used in GrowableArray::begin() and GrowableArray::end()
877 GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
878 assert(0 <= position && position <= _array->length(), "illegal position");
879 }
880
881 public:
882 GrowableArrayIterator() : _array(nullptr), _position(0) { }
883 GrowableArrayIterator& operator++() { ++_position; return *this; }
884 E operator*() { return _array->at(_position); }
885
886 bool operator==(const GrowableArrayIterator& rhs) {
887 assert(_array == rhs._array, "iterator belongs to different array");
888 return _position == rhs._position;
889 }
890
891 bool operator!=(const GrowableArrayIterator& rhs) {
892 assert(_array == rhs._array, "iterator belongs to different array");
893 return _position != rhs._position;
894 }
895 };
896
897 // Arrays for basic types
898 typedef GrowableArray<int> intArray;
899 typedef GrowableArray<int> intStack;
900 typedef GrowableArray<bool> boolArray;
901
902 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP