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