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