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   size_t data_size_in_bytes() const {
324     return _len * sizeof(E);
325   }
326 
327   void print() const {
328     tty->print("Growable Array " INTPTR_FORMAT, p2i(this));
329     tty->print(": length %d (_max %d) { ", _len, _max);
330     for (int i = 0; i < _len; i++) {
331       tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
332     }
333     tty->print("}\n");
334   }
335 };
336 
337 template<typename E>
338 const GrowableArrayView<E> GrowableArrayView<E>::EMPTY(nullptr, 0, 0);
339 
340 // GrowableArrayWithAllocator extends the "view" with
341 // the capability to grow and deallocate the data array.
342 //
343 // The allocator responsibility is delegated to the sub-class.
344 //
345 // Derived: The sub-class responsible for allocation / deallocation
346 //  - E* Derived::allocate()       - member function responsible for allocation
347 //  - void Derived::deallocate(E*) - member function responsible for deallocation
348 template <typename E, typename Derived>
349 class GrowableArrayWithAllocator : public GrowableArrayView<E> {
350   friend class VMStructs;
351 
352   void grow(int j);
353 
354 protected:
355   GrowableArrayWithAllocator(E* data, int initial_max) :
356       GrowableArrayView<E>(data, initial_max, 0) {
357     for (int i = 0; i < initial_max; i++) {
358       ::new ((void*)&data[i]) E();
359     }
360   }
361 
362   GrowableArrayWithAllocator(E* data, int initial_max, int initial_len, const E& filler) :
363       GrowableArrayView<E>(data, initial_max, initial_len) {
364     int i = 0;
365     for (; i < initial_len; i++) {
366       ::new ((void*)&data[i]) E(filler);
367     }
368     for (; i < initial_max; i++) {
369       ::new ((void*)&data[i]) E();
370     }
371   }
372 
373   ~GrowableArrayWithAllocator() {}
374 
375 public:
376   int append(const E& elem) {
377     if (this->_len == this->_max) grow(this->_len);
378     int idx = this->_len++;
379     this->_data[idx] = elem;
380     return idx;
381   }
382 
383   bool append_if_missing(const E& elem) {
384     // Returns TRUE if elem is added.
385     bool missed = !this->contains(elem);
386     if (missed) append(elem);
387     return missed;
388   }
389 
390   void push(const E& elem) { append(elem); }
391 
392   E at_grow(int i, const E& fill = E()) {
393     assert(0 <= i, "negative index");
394     if (i >= this->_len) {
395       if (i >= this->_max) grow(i);
396       for (int j = this->_len; j <= i; j++)
397         this->_data[j] = fill;
398       this->_len = i+1;
399     }
400     return this->_data[i];
401   }
402 
403   void at_put_grow(int i, const E& elem, 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     this->_data[i] = elem;
412   }
413 
414   // inserts the given element before the element at index i
415   void insert_before(const int idx, const E& elem) {
416     assert(0 <= idx && idx <= this->_len, "illegal index");
417     if (this->_len == this->_max) grow(this->_len);
418     for (int j = this->_len - 1; j >= idx; j--) {
419       this->_data[j + 1] = this->_data[j];
420     }
421     this->_len++;
422     this->_data[idx] = elem;
423   }
424 
425   void insert_before(const int idx, const GrowableArrayView<E>* array) {
426     assert(0 <= idx && idx <= this->_len, "illegal index");
427     int array_len = array->length();
428     int new_len = this->_len + array_len;
429     if (new_len >= this->_max) grow(new_len);
430 
431     for (int j = this->_len - 1; j >= idx; j--) {
432       this->_data[j + array_len] = this->_data[j];
433     }
434 
435     for (int j = 0; j < array_len; j++) {
436       this->_data[idx + j] = array->at(j);
437     }
438 
439     this->_len += array_len;
440   }
441 
442   void appendAll(const GrowableArrayView<E>* l) {
443     for (int i = 0; i < l->length(); i++) {
444       this->at_put_grow(this->_len, l->at(i), E());
445     }
446   }
447 
448   // Binary search and insertion utility.  Search array for element
449   // matching key according to the static compare function.  Insert
450   // that element if not already in the list.  Assumes the list is
451   // already sorted according to compare function.
452   template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
453     bool found;
454     int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
455     if (!found) {
456       insert_before(location, key);
457     }
458     return this->at(location);
459   }
460 
461   E insert_sorted(CompareClosure<E>* cc, const E& key) {
462     bool found;
463     int location = find_sorted(cc, key, found);
464     if (!found) {
465       insert_before(location, key);
466     }
467     return this->at(location);
468   }
469 
470   void swap(GrowableArrayWithAllocator<E, Derived>* other) {
471     ::swap(this->_data, other->_data);
472     ::swap(this->_len, other->_len);
473     ::swap(this->_max, other->_max);
474   }
475 
476   void clear_and_deallocate();
477 };
478 
479 template <typename E, typename Derived>
480 void GrowableArrayWithAllocator<E, Derived>::grow(int j) {
481   int old_max = this->_max;
482   // grow the array by increasing _max to the first power of two larger than the size we need
483   this->_max = next_power_of_2((uint32_t)j);
484   // j < _max
485   E* newData = static_cast<Derived*>(this)->allocate();
486   int i = 0;
487   for (     ; i < this->_len; i++) ::new ((void*)&newData[i]) E(this->_data[i]);
488   for (     ; i < this->_max; i++) ::new ((void*)&newData[i]) E();
489   for (i = 0; i < old_max; i++) this->_data[i].~E();
490   if (this->_data != NULL) {
491     static_cast<Derived*>(this)->deallocate(this->_data);
492   }
493   this->_data = newData;
494 }
495 
496 template <typename E, typename Derived>
497 void GrowableArrayWithAllocator<E, Derived>::clear_and_deallocate() {
498   if (this->_data != NULL) {
499     for (int i = 0; i < this->_max; i++) {
500       this->_data[i].~E();
501     }
502     static_cast<Derived*>(this)->deallocate(this->_data);
503     this->_data = NULL;
504   }
505   this->_len = 0;
506   this->_max = 0;
507 }
508 
509 class GrowableArrayResourceAllocator {
510 public:
511   static void* allocate(int max, int element_size);
512 };
513 
514 // Arena allocator
515 class GrowableArrayArenaAllocator {
516 public:
517   static void* allocate(int max, int element_size, Arena* arena);
518 };
519 
520 // CHeap allocator
521 class GrowableArrayCHeapAllocator {
522 public:
523   static void* allocate(int max, int element_size, MEMFLAGS memflags);
524   static void deallocate(void* mem);
525 };
526 
527 #ifdef ASSERT
528 
529 // Checks resource allocation nesting
530 class GrowableArrayNestingCheck {
531   // resource area nesting at creation
532   int _nesting;
533 
534 public:
535   GrowableArrayNestingCheck(bool on_stack);
536 
537   void on_stack_alloc() const;
538 };
539 
540 #endif // ASSERT
541 
542 // Encodes where the backing array is allocated
543 // and performs necessary checks.
544 class GrowableArrayMetadata {
545   uintptr_t _bits;
546 
547   // resource area nesting at creation
548   debug_only(GrowableArrayNestingCheck _nesting_check;)
549 
550   uintptr_t bits(MEMFLAGS memflags) const {
551     if (memflags == mtNone) {
552       // Stack allocation
553       return 0;
554     }
555 
556     // CHeap allocation
557     return (uintptr_t(memflags) << 1) | 1;
558   }
559 
560   uintptr_t bits(Arena* arena) const {
561     return uintptr_t(arena);
562   }
563 
564 public:
565   GrowableArrayMetadata(Arena* arena) :
566       _bits(bits(arena))
567       debug_only(COMMA _nesting_check(on_stack())) {
568   }
569 
570   GrowableArrayMetadata(MEMFLAGS memflags) :
571       _bits(bits(memflags))
572       debug_only(COMMA _nesting_check(on_stack())) {
573   }
574 
575 #ifdef ASSERT
576   GrowableArrayMetadata(const GrowableArrayMetadata& other) :
577       _bits(other._bits),
578       _nesting_check(other._nesting_check) {
579     assert(!on_C_heap(), "Copying of CHeap arrays not supported");
580     assert(!other.on_C_heap(), "Copying of CHeap arrays not supported");
581   }
582 
583   GrowableArrayMetadata& operator=(const GrowableArrayMetadata& other) {
584     _bits = other._bits;
585     _nesting_check = other._nesting_check;
586     assert(!on_C_heap(), "Assignment of CHeap arrays not supported");
587     assert(!other.on_C_heap(), "Assignment of CHeap arrays not supported");
588     return *this;
589   }
590 
591   void init_checks(const GrowableArrayBase* array) const;
592   void on_stack_alloc_check() const;
593 #endif // ASSERT
594 
595   bool on_C_heap() const { return (_bits & 1) == 1; }
596   bool on_stack () const { return _bits == 0;      }
597   bool on_arena () const { return (_bits & 1) == 0 && _bits != 0; }
598 
599   Arena* arena() const      { return (Arena*)_bits; }
600   MEMFLAGS memflags() const { return MEMFLAGS(_bits >> 1); }
601 };
602 
603 // THE GrowableArray.
604 //
605 // Supports multiple allocation strategies:
606 //  - Resource stack allocation: if memflags == mtNone
607 //  - CHeap allocation: if memflags != mtNone
608 //  - Arena allocation: if an arena is provided
609 //
610 // There are some drawbacks of using GrowableArray, that are removed in some
611 // of the other implementations of GrowableArrayWithAllocator sub-classes:
612 //
613 // Memory overhead: The multiple allocation strategies uses extra metadata
614 //  embedded in the instance.
615 //
616 // Strict allocation locations: There are rules about where the GrowableArray
617 //  instance is allocated, that depends on where the data array is allocated.
618 //  See: init_checks.
619 
620 template <typename E>
621 class GrowableArray : public GrowableArrayWithAllocator<E, GrowableArray<E> > {
622   friend class GrowableArrayWithAllocator<E, GrowableArray<E> >;
623   friend class GrowableArrayTest;
624 
625   static E* allocate(int max) {
626     return (E*)GrowableArrayResourceAllocator::allocate(max, sizeof(E));
627   }
628 
629   static E* allocate(int max, MEMFLAGS memflags) {
630     if (memflags != mtNone) {
631       return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), memflags);
632     }
633 
634     return (E*)GrowableArrayResourceAllocator::allocate(max, sizeof(E));
635   }
636 
637   static E* allocate(int max, Arena* arena) {
638     return (E*)GrowableArrayArenaAllocator::allocate(max, sizeof(E), arena);
639   }
640 
641   GrowableArrayMetadata _metadata;
642 
643   void init_checks() const { debug_only(_metadata.init_checks(this);) }
644 
645   // Where are we going to allocate memory?
646   bool on_C_heap() const { return _metadata.on_C_heap(); }
647   bool on_stack () const { return _metadata.on_stack(); }
648   bool on_arena () const { return _metadata.on_arena(); }
649 
650   E* allocate() {
651     if (on_stack()) {
652       debug_only(_metadata.on_stack_alloc_check());
653       return allocate(this->_max);
654     }
655 
656     if (on_C_heap()) {
657       return allocate(this->_max, _metadata.memflags());
658     }
659 
660     assert(on_arena(), "Sanity");
661     return allocate(this->_max, _metadata.arena());
662   }
663 
664   void deallocate(E* mem) {
665     if (on_C_heap()) {
666       GrowableArrayCHeapAllocator::deallocate(mem);
667     }
668   }
669 
670 public:
671   GrowableArray(int initial_max = 2, MEMFLAGS memflags = mtNone) :
672       GrowableArrayWithAllocator<E, GrowableArray<E> >(
673           allocate(initial_max, memflags),
674           initial_max),
675       _metadata(memflags) {
676     init_checks();
677   }
678 
679   GrowableArray(int initial_max, int initial_len, const E& filler, MEMFLAGS memflags = mtNone) :
680       GrowableArrayWithAllocator<E, GrowableArray<E> >(
681           allocate(initial_max, memflags),
682           initial_max, initial_len, filler),
683       _metadata(memflags) {
684     init_checks();
685   }
686 
687   GrowableArray(Arena* arena, int initial_max, int initial_len, const E& filler) :
688       GrowableArrayWithAllocator<E, GrowableArray<E> >(
689           allocate(initial_max, arena),
690           initial_max, initial_len, filler),
691       _metadata(arena) {
692     init_checks();
693   }
694 
695   ~GrowableArray() {
696     if (on_C_heap()) {
697       this->clear_and_deallocate();
698     }
699   }
700 };
701 
702 // Leaner GrowableArray for CHeap backed data arrays, with compile-time decided MEMFLAGS.
703 template <typename E, MEMFLAGS F>
704 class GrowableArrayCHeap : public GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> > {
705   friend class GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> >;
706 
707   STATIC_ASSERT(F != mtNone);
708 
709   static E* allocate(int max, MEMFLAGS flags) {
710     if (max == 0) {
711       return NULL;
712     }
713 
714     return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), flags);
715   }
716 
717   NONCOPYABLE(GrowableArrayCHeap);
718 
719   E* allocate() {
720     return allocate(this->_max, F);
721   }
722 
723   void deallocate(E* mem) {
724     GrowableArrayCHeapAllocator::deallocate(mem);
725   }
726 
727 public:
728   GrowableArrayCHeap(int initial_max = 0) :
729       GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> >(
730           allocate(initial_max, F),
731           initial_max) {}
732 
733   GrowableArrayCHeap(int initial_max, int initial_len, const E& filler) :
734       GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> >(
735           allocate(initial_max, F),
736           initial_max, initial_len, filler) {}
737 
738   ~GrowableArrayCHeap() {
739     this->clear_and_deallocate();
740   }
741 
742   void* operator new(size_t size) throw() {
743     return ResourceObj::operator new(size, ResourceObj::C_HEAP, F);
744   }
745 
746   void* operator new(size_t size, const std::nothrow_t&  nothrow_constant) throw() {
747     return ResourceObj::operator new(size, nothrow_constant, ResourceObj::C_HEAP, F);
748   }
749 };
750 
751 // Custom STL-style iterator to iterate over GrowableArrays
752 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
753 template <typename E>
754 class GrowableArrayIterator : public StackObj {
755   friend class GrowableArrayView<E>;
756   template <typename F, typename UnaryPredicate> friend class GrowableArrayFilterIterator;
757 
758  private:
759   const GrowableArrayView<E>* _array; // GrowableArray we iterate over
760   int _position;                      // The current position in the GrowableArray
761 
762   // Private constructor used in GrowableArray::begin() and GrowableArray::end()
763   GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
764     assert(0 <= position && position <= _array->length(), "illegal position");
765   }
766 
767  public:
768   GrowableArrayIterator() : _array(NULL), _position(0) { }
769   GrowableArrayIterator<E>& operator++() { ++_position; return *this; }
770   E operator*()                          { return _array->at(_position); }
771 
772   bool operator==(const GrowableArrayIterator<E>& rhs)  {
773     assert(_array == rhs._array, "iterator belongs to different array");
774     return _position == rhs._position;
775   }
776 
777   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
778     assert(_array == rhs._array, "iterator belongs to different array");
779     return _position != rhs._position;
780   }
781 };
782 
783 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
784 template <typename E, class UnaryPredicate>
785 class GrowableArrayFilterIterator : public StackObj {
786   friend class GrowableArrayView<E>;
787 
788  private:
789   const GrowableArrayView<E>* _array; // GrowableArray we iterate over
790   int _position;                      // Current position in the GrowableArray
791   UnaryPredicate _predicate;          // Unary predicate the elements of the GrowableArray should satisfy
792 
793  public:
794   GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate) :
795       _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
796     // Advance to first element satisfying the predicate
797     while(_position != _array->length() && !_predicate(_array->at(_position))) {
798       ++_position;
799     }
800   }
801 
802   GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
803     do {
804       // Advance to next element satisfying the predicate
805       ++_position;
806     } while(_position != _array->length() && !_predicate(_array->at(_position)));
807     return *this;
808   }
809 
810   E operator*() { return _array->at(_position); }
811 
812   bool operator==(const GrowableArrayIterator<E>& rhs)  {
813     assert(_array == rhs._array, "iterator belongs to different array");
814     return _position == rhs._position;
815   }
816 
817   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
818     assert(_array == rhs._array, "iterator belongs to different array");
819     return _position != rhs._position;
820   }
821 
822   bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
823     assert(_array == rhs._array, "iterator belongs to different array");
824     return _position == rhs._position;
825   }
826 
827   bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
828     assert(_array == rhs._array, "iterator belongs to different array");
829     return _position != rhs._position;
830   }
831 };
832 
833 // Arrays for basic types
834 typedef GrowableArray<int> intArray;
835 typedef GrowableArray<int> intStack;
836 typedef GrowableArray<bool> boolArray;
837 
838 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP