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