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