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