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