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