1 /* 2 * Copyright (c) 1997, 2025, 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 "oops/array.hpp" 31 #include "oops/oop.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 100 template <typename E> class GrowableArrayIterator; 101 template <typename E, typename UnaryPredicate> class GrowableArrayFilterIterator; 102 103 // Extends GrowableArrayBase with a typed data array. 104 // 105 // E: Element type 106 // 107 // The "view" adds function that don't grow or deallocate 108 // the _data array, so there's no need for an allocator. 109 // 110 // The "view" can be used to type erase the allocator classes 111 // of GrowableArrayWithAllocator. 112 template <typename E> 113 class GrowableArrayView : public GrowableArrayBase { 114 protected: 115 E* _data; // data array 116 117 GrowableArrayView(E* data, int capacity, int initial_len) : 118 GrowableArrayBase(capacity, initial_len), _data(data) {} 119 120 ~GrowableArrayView() {} 121 122 public: 123 bool operator==(const GrowableArrayView& rhs) const { 124 if (_len != rhs._len) 125 return false; 126 for (int i = 0; i < _len; i++) { 127 if (at(i) != rhs.at(i)) { 128 return false; 129 } 130 } 131 return true; 132 } 133 134 bool operator!=(const GrowableArrayView& rhs) const { 135 return !(*this == rhs); 136 } 137 138 E& at(int i) { 139 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len); 140 return _data[i]; 141 } 142 143 E const& at(int i) const { 144 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len); 145 return _data[i]; 146 } 147 148 E* adr_at(int i) const { 149 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len); 150 return &_data[i]; 151 } 152 153 E& first() { 154 assert(_len > 0, "empty"); 155 return _data[0]; 156 } 157 158 E const& first() const { 159 assert(_len > 0, "empty"); 160 return _data[0]; 161 } 162 163 E& top() { 164 assert(_len > 0, "empty"); 165 return _data[_len - 1]; 166 } 167 168 E const& top() const { 169 assert(_len > 0, "empty"); 170 return _data[_len - 1]; 171 } 172 173 E& last() { 174 return top(); 175 } 176 177 E const& last() const { 178 return top(); 179 } 180 181 GrowableArrayIterator<E> begin() const { 182 return GrowableArrayIterator<E>(this, 0); 183 } 184 185 GrowableArrayIterator<E> end() const { 186 return GrowableArrayIterator<E>(this, length()); 187 } 188 189 void at_put(int i, const E& elem) { 190 assert(0 <= i && i < _len, "illegal index %d for length %d", i, _len); 191 _data[i] = elem; 192 } 193 194 bool contains(const E& elem) const { 195 for (int i = 0; i < _len; i++) { 196 if (_data[i] == elem) return true; 197 } 198 return false; 199 } 200 201 int find(const E& elem) const { 202 for (int i = 0; i < _len; i++) { 203 if (_data[i] == elem) return i; 204 } 205 return -1; 206 } 207 208 int find_from_end(const E& elem) const { 209 for (int i = _len-1; i >= 0; i--) { 210 if (_data[i] == elem) return i; 211 } 212 return -1; 213 } 214 215 // Find first element that matches the given predicate. 216 // 217 // Predicate: bool predicate(const E& elem) 218 // 219 // Returns the index of the element or -1 if no element matches the predicate 220 template<typename Predicate> 221 int find_if(Predicate predicate) const { 222 for (int i = 0; i < _len; i++) { 223 if (predicate(_data[i])) return i; 224 } 225 return -1; 226 } 227 228 // Find last element that matches the given predicate. 229 // 230 // Predicate: bool predicate(const E& elem) 231 // 232 // Returns the index of the element or -1 if no element matches the predicate 233 template<typename Predicate> 234 int find_from_end_if(Predicate predicate) const { 235 // start at the end of the array 236 for (int i = _len-1; i >= 0; i--) { 237 if (predicate(_data[i])) return i; 238 } 239 return -1; 240 } 241 242 void sort(int f(E*, E*)) { 243 if (_data == nullptr) return; 244 qsort(_data, length(), sizeof(E), (_sort_Fn)f); 245 } 246 // sort by fixed-stride sub arrays: 247 void sort(int f(E*, E*), int stride) { 248 if (_data == nullptr) return; 249 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); 250 } 251 252 template <typename K, int compare(const K&, const E&)> int find_sorted(const K& key, bool& found) const { 253 found = false; 254 int min = 0; 255 int max = length() - 1; 256 257 while (max >= min) { 258 int mid = (int)(((uint)max + min) / 2); 259 E value = at(mid); 260 int diff = compare(key, value); 261 if (diff > 0) { 262 min = mid + 1; 263 } else if (diff < 0) { 264 max = mid - 1; 265 } else { 266 found = true; 267 return mid; 268 } 269 } 270 return min; 271 } 272 273 template <typename K> 274 int find_sorted(CompareClosure<E>* cc, const K& key, bool& found) { 275 found = false; 276 int min = 0; 277 int max = length() - 1; 278 279 while (max >= min) { 280 int mid = (int)(((uint)max + min) / 2); 281 E value = at(mid); 282 int diff = cc->do_compare(key, value); 283 if (diff > 0) { 284 min = mid + 1; 285 } else if (diff < 0) { 286 max = mid - 1; 287 } else { 288 found = true; 289 return mid; 290 } 291 } 292 return min; 293 } 294 295 void print() const { 296 tty->print("Growable Array " PTR_FORMAT, p2i(this)); 297 tty->print(": length %d (capacity %d) { ", _len, _capacity); 298 for (int i = 0; i < _len; i++) { 299 tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i])); 300 } 301 tty->print("}\n"); 302 } 303 }; 304 305 template <typename E> 306 class GrowableArrayFromArray : public GrowableArrayView<E> { 307 public: 308 309 GrowableArrayFromArray(E* data, int len) : 310 GrowableArrayView<E>(data, len, len) {} 311 }; 312 313 // GrowableArrayWithAllocator extends the "view" with 314 // the capability to grow and deallocate the data array. 315 // 316 // The allocator responsibility is delegated to the sub-class. 317 // 318 // Derived: The sub-class responsible for allocation / deallocation 319 // - E* Derived::allocate() - member function responsible for allocation 320 // - void Derived::deallocate(E*) - member function responsible for deallocation 321 template <typename E, typename Derived> 322 class GrowableArrayWithAllocator : public GrowableArrayView<E> { 323 friend class VMStructs; 324 325 void expand_to(int j); 326 void grow(int j); 327 328 protected: 329 GrowableArrayWithAllocator(E* data, int capacity) : 330 GrowableArrayView<E>(data, capacity, 0) { 331 for (int i = 0; i < capacity; i++) { 332 ::new ((void*)&data[i]) E(); 333 } 334 } 335 336 GrowableArrayWithAllocator(E* data, int capacity, int initial_len, const E& filler) : 337 GrowableArrayView<E>(data, capacity, initial_len) { 338 int i = 0; 339 for (; i < initial_len; i++) { 340 ::new ((void*)&data[i]) E(filler); 341 } 342 for (; i < capacity; i++) { 343 ::new ((void*)&data[i]) E(); 344 } 345 } 346 347 GrowableArrayWithAllocator(E* data, int capacity, int initial_len) : 348 GrowableArrayView<E>(data, capacity, initial_len) {} 349 350 ~GrowableArrayWithAllocator() {} 351 352 public: 353 int append(const E& elem) { 354 if (this->_len == this->_capacity) grow(this->_len); 355 int idx = this->_len++; 356 this->_data[idx] = elem; 357 return idx; 358 } 359 360 bool append_if_missing(const E& elem) { 361 // Returns TRUE if elem is added. 362 bool missed = !this->contains(elem); 363 if (missed) append(elem); 364 return missed; 365 } 366 367 void push(const E& elem) { append(elem); } 368 369 E pop() { 370 assert(this->_len > 0, "empty list"); 371 return this->_data[--this->_len]; 372 } 373 374 E& at_grow(int i, const E& fill = E()) { 375 assert(0 <= i, "negative index %d", i); 376 if (i >= this->_len) { 377 if (i >= this->_capacity) grow(i); 378 for (int j = this->_len; j <= i; j++) 379 this->_data[j] = fill; 380 this->_len = i+1; 381 } 382 return this->_data[i]; 383 } 384 385 void at_put_grow(int i, const E& elem, const E& fill = E()) { 386 assert(0 <= i, "negative index %d", i); 387 if (i >= this->_len) { 388 if (i >= this->_capacity) grow(i); 389 for (int j = this->_len; j < i; j++) 390 this->_data[j] = fill; 391 this->_len = i+1; 392 } 393 this->_data[i] = elem; 394 } 395 396 // inserts the given element before the element at index i 397 void insert_before(const int idx, const E& elem) { 398 assert(0 <= idx && idx <= this->_len, "illegal index %d for length %d", idx, this->_len); 399 if (this->_len == this->_capacity) grow(this->_len); 400 for (int j = this->_len - 1; j >= idx; j--) { 401 this->_data[j + 1] = this->_data[j]; 402 } 403 this->_len++; 404 this->_data[idx] = elem; 405 } 406 407 void insert_before(const int idx, const GrowableArrayView<E>* array) { 408 assert(0 <= idx && idx <= this->_len, "illegal index %d for length %d", idx, this->_len); 409 int array_len = array->length(); 410 int new_len = this->_len + array_len; 411 if (new_len >= this->_capacity) grow(new_len); 412 413 for (int j = this->_len - 1; j >= idx; j--) { 414 this->_data[j + array_len] = this->_data[j]; 415 } 416 417 for (int j = 0; j < array_len; j++) { 418 this->_data[idx + j] = array->at(j); 419 } 420 421 this->_len += array_len; 422 } 423 424 void appendAll(const GrowableArrayView<E>* l) { 425 for (int i = 0; i < l->length(); i++) { 426 this->at_put_grow(this->_len, l->at(i), E()); 427 } 428 } 429 430 void appendAll(const Array<E>* l) { 431 for (int i = 0; i < l->length(); i++) { 432 this->at_put_grow(this->_len, l->at(i), E()); 433 } 434 } 435 436 // Binary search and insertion utility. Search array for element 437 // matching key according to the static compare function. Insert 438 // that element if not already in the list. Assumes the list is 439 // already sorted according to compare function. 440 template <int compare(const E&, const E&)> E insert_sorted(const E& key) { 441 bool found; 442 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found); 443 if (!found) { 444 insert_before(location, key); 445 } 446 return this->at(location); 447 } 448 449 E insert_sorted(CompareClosure<E>* cc, const E& key) { 450 bool found; 451 int location = find_sorted(cc, key, found); 452 if (!found) { 453 insert_before(location, key); 454 } 455 return this->at(location); 456 } 457 458 void swap(GrowableArrayWithAllocator* other) { 459 ::swap(this->_data, other->_data); 460 ::swap(this->_len, other->_len); 461 ::swap(this->_capacity, other->_capacity); 462 } 463 464 // Ensure capacity is at least new_capacity. 465 void reserve(int new_capacity); 466 467 void trunc_to(int length) { 468 assert(length <= this->_len,"cannot increase length"); 469 this->_len = length; 470 } 471 472 // Order preserving remove operations. 473 474 void remove_at(int index) { 475 assert(0 <= index && index < this->_len, 476 "illegal index %d for length %d", index, this->_len); 477 for (int j = index + 1; j < this->_len; j++) { 478 this->_data[j-1] = this->_data[j]; 479 } 480 this->_len--; 481 } 482 483 void remove(const E& elem) { 484 // Assuming that element does exist. 485 bool removed = this->remove_if_existing(elem); 486 if (removed) return; 487 ShouldNotReachHere(); 488 } 489 490 bool remove_if_existing(const E& elem) { 491 // Returns TRUE if elem is removed. 492 for (int i = 0; i < this->_len; i++) { 493 if (this->_data[i] == elem) { 494 this->remove_at(i); 495 return true; 496 } 497 } 498 return false; 499 } 500 501 // Remove all elements up to the index (exclusive). The order is preserved. 502 void remove_till(int idx) { 503 remove_range(0, idx); 504 } 505 506 // Remove all elements in the range [start - end). The order is preserved. 507 void remove_range(int start, int end) { 508 assert(0 <= start, "illegal start index %d", start); 509 assert(start < end && end <= this->_len, 510 "erase called with invalid range (%d, %d) for length %d", 511 start, end, this->_len); 512 513 for (int i = start, j = end; j < this->length(); i++, j++) { 514 this->at_put(i, this->at(j)); 515 } 516 this->_len -= (end - start); 517 } 518 519 // Replaces the designated element with the last element and shrinks by 1. 520 void delete_at(int index) { 521 assert(0 <= index && index < this->_len, "illegal index %d for length %d", index, this->_len); 522 if (index < --this->_len) { 523 // Replace removed element with last one. 524 this->_data[index] = this->_data[this->_len]; 525 } 526 } 527 528 // Reduce capacity to length. 529 void shrink_to_fit(); 530 531 void clear() { this->_len = 0; } 532 void clear_and_deallocate(); 533 }; 534 535 template <typename E, typename Derived> 536 void GrowableArrayWithAllocator<E, Derived>::expand_to(int new_capacity) { 537 int old_capacity = this->_capacity; 538 assert(new_capacity > old_capacity, 539 "expected growth but %d <= %d", new_capacity, old_capacity); 540 this->_capacity = new_capacity; 541 E* newData = static_cast<Derived*>(this)->allocate(); 542 int i = 0; 543 for ( ; i < this->_len; i++) ::new ((void*)&newData[i]) E(this->_data[i]); 544 for ( ; i < this->_capacity; i++) ::new ((void*)&newData[i]) E(); 545 for (i = 0; i < old_capacity; i++) this->_data[i].~E(); 546 if (this->_data != nullptr) { 547 static_cast<Derived*>(this)->deallocate(this->_data); 548 } 549 this->_data = newData; 550 } 551 552 template <typename E, typename Derived> 553 void GrowableArrayWithAllocator<E, Derived>::grow(int j) { 554 // grow the array by increasing _capacity to the first power of two larger than the size we need 555 expand_to(next_power_of_2(j)); 556 } 557 558 template <typename E, typename Derived> 559 void GrowableArrayWithAllocator<E, Derived>::reserve(int new_capacity) { 560 if (new_capacity > this->_capacity) { 561 expand_to(new_capacity); 562 } 563 } 564 565 template <typename E, typename Derived> 566 void GrowableArrayWithAllocator<E, Derived>::shrink_to_fit() { 567 int old_capacity = this->_capacity; 568 int len = this->_len; 569 assert(len <= old_capacity, "invariant"); 570 571 // If already at full capacity, nothing to do. 572 if (len == old_capacity) { 573 return; 574 } 575 576 // If not empty, allocate new, smaller, data, and copy old data to it. 577 E* old_data = this->_data; 578 E* new_data = nullptr; 579 this->_capacity = len; // Must preceed allocate(). 580 if (len > 0) { 581 new_data = static_cast<Derived*>(this)->allocate(); 582 for (int i = 0; i < len; ++i) ::new (&new_data[i]) E(old_data[i]); 583 } 584 // Destroy contents of old data, and deallocate it. 585 for (int i = 0; i < old_capacity; ++i) old_data[i].~E(); 586 if (old_data != nullptr) { 587 static_cast<Derived*>(this)->deallocate(old_data); 588 } 589 // Install new data, which might be nullptr. 590 this->_data = new_data; 591 } 592 593 template <typename E, typename Derived> 594 void GrowableArrayWithAllocator<E, Derived>::clear_and_deallocate() { 595 this->clear(); 596 this->shrink_to_fit(); 597 } 598 599 class GrowableArrayResourceAllocator { 600 public: 601 static void* allocate(int max, int element_size); 602 }; 603 604 // Arena allocator 605 class GrowableArrayArenaAllocator { 606 public: 607 static void* allocate(int max, int element_size, Arena* arena); 608 }; 609 610 // CHeap allocator 611 class GrowableArrayCHeapAllocator { 612 public: 613 static void* allocate(int max, int element_size, MemTag mem_tag); 614 static void deallocate(void* mem); 615 }; 616 617 #ifdef ASSERT 618 619 // Checks resource allocation nesting 620 class GrowableArrayNestingCheck { 621 // resource area nesting at creation 622 int _nesting; 623 624 public: 625 GrowableArrayNestingCheck(bool on_resource_area); 626 GrowableArrayNestingCheck(Arena* arena); 627 628 void on_resource_area_alloc() const; 629 void on_arena_alloc(Arena* arena) const; 630 }; 631 632 #endif // ASSERT 633 634 // Encodes where the backing array is allocated 635 // and performs necessary checks. 636 class GrowableArrayMetadata { 637 uintptr_t _bits; 638 639 // resource area nesting at creation 640 DEBUG_ONLY(GrowableArrayNestingCheck _nesting_check;) 641 642 // Resource allocation 643 static uintptr_t bits() { 644 return 0; 645 } 646 647 // CHeap allocation 648 static uintptr_t bits(MemTag mem_tag) { 649 assert(mem_tag != mtNone, "Must provide a proper MemTag"); 650 return (uintptr_t(mem_tag) << 1) | 1; 651 } 652 653 // Arena allocation 654 static uintptr_t bits(Arena* arena) { 655 assert((uintptr_t(arena) & 1) == 0, "Required for on_C_heap() to work"); 656 return uintptr_t(arena); 657 } 658 659 public: 660 // Resource allocation 661 GrowableArrayMetadata() : 662 _bits(bits()) 663 DEBUG_ONLY(COMMA _nesting_check(true)) { 664 } 665 666 // Arena allocation 667 GrowableArrayMetadata(Arena* arena) : 668 _bits(bits(arena)) 669 DEBUG_ONLY(COMMA _nesting_check(arena)) { 670 } 671 672 // CHeap allocation 673 GrowableArrayMetadata(MemTag mem_tag) : 674 _bits(bits(mem_tag)) 675 DEBUG_ONLY(COMMA _nesting_check(false)) { 676 } 677 678 #ifdef ASSERT 679 GrowableArrayMetadata(const GrowableArrayMetadata& other) : 680 _bits(other._bits), 681 _nesting_check(other._nesting_check) { 682 assert(!on_C_heap(), "Copying of CHeap arrays not supported"); 683 assert(!other.on_C_heap(), "Copying of CHeap arrays not supported"); 684 } 685 686 GrowableArrayMetadata& operator=(const GrowableArrayMetadata& other) { 687 _bits = other._bits; 688 _nesting_check = other._nesting_check; 689 assert(!on_C_heap(), "Assignment of CHeap arrays not supported"); 690 assert(!other.on_C_heap(), "Assignment of CHeap arrays not supported"); 691 return *this; 692 } 693 694 void init_checks(const GrowableArrayBase* array) const; 695 void on_resource_area_alloc_check() const; 696 void on_arena_alloc_check() const; 697 #endif // ASSERT 698 699 bool on_C_heap() const { return (_bits & 1) == 1; } 700 bool on_resource_area() const { return _bits == 0; } 701 bool on_arena() const { return (_bits & 1) == 0 && _bits != 0; } 702 703 Arena* arena() const { return (Arena*)_bits; } 704 MemTag mem_tag() const { return MemTag(_bits >> 1); } 705 }; 706 707 // THE GrowableArray. 708 // 709 // Supports multiple allocation strategies: 710 // - Resource stack allocation: if no extra argument is provided 711 // - CHeap allocation: if mem_tag is provided 712 // - Arena allocation: if an arena is provided 713 // 714 // There are some drawbacks of using GrowableArray, that are removed in some 715 // of the other implementations of GrowableArrayWithAllocator sub-classes: 716 // 717 // Memory overhead: The multiple allocation strategies uses extra metadata 718 // embedded in the instance. 719 // 720 // Strict allocation locations: There are rules about where the GrowableArray 721 // instance is allocated, that depends on where the data array is allocated. 722 // See: init_checks. 723 724 template <typename E> 725 class GrowableArray : public GrowableArrayWithAllocator<E, GrowableArray<E>> { 726 friend class GrowableArrayWithAllocator<E, GrowableArray>; 727 friend class GrowableArrayTest; 728 729 static E* allocate(int max) { 730 return (E*)GrowableArrayResourceAllocator::allocate(max, sizeof(E)); 731 } 732 733 static E* allocate(int max, MemTag mem_tag) { 734 return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), mem_tag); 735 } 736 737 static E* allocate(int max, Arena* arena) { 738 return (E*)GrowableArrayArenaAllocator::allocate(max, sizeof(E), arena); 739 } 740 741 GrowableArrayMetadata _metadata; 742 743 void init_checks() const { DEBUG_ONLY(_metadata.init_checks(this);) } 744 745 // Where are we going to allocate memory? 746 bool on_C_heap() const { return _metadata.on_C_heap(); } 747 bool on_resource_area() const { return _metadata.on_resource_area(); } 748 bool on_arena() const { return _metadata.on_arena(); } 749 750 E* allocate() { 751 if (on_resource_area()) { 752 DEBUG_ONLY(_metadata.on_resource_area_alloc_check()); 753 return allocate(this->_capacity); 754 } 755 756 if (on_C_heap()) { 757 return allocate(this->_capacity, _metadata.mem_tag()); 758 } 759 760 assert(on_arena(), "Sanity"); 761 DEBUG_ONLY(_metadata.on_arena_alloc_check()); 762 return allocate(this->_capacity, _metadata.arena()); 763 } 764 765 void deallocate(E* mem) { 766 if (on_C_heap()) { 767 GrowableArrayCHeapAllocator::deallocate(mem); 768 } 769 } 770 771 public: 772 GrowableArray() : GrowableArray(2 /* initial_capacity */) {} 773 774 explicit GrowableArray(int initial_capacity) : 775 GrowableArrayWithAllocator<E, GrowableArray>( 776 allocate(initial_capacity), 777 initial_capacity), 778 _metadata() { 779 init_checks(); 780 } 781 782 GrowableArray(int initial_capacity, MemTag mem_tag) : 783 GrowableArrayWithAllocator<E, GrowableArray>( 784 allocate(initial_capacity, mem_tag), 785 initial_capacity), 786 _metadata(mem_tag) { 787 init_checks(); 788 } 789 790 GrowableArray(int initial_capacity, int initial_len, const E& filler) : 791 GrowableArrayWithAllocator<E, GrowableArray>( 792 allocate(initial_capacity), 793 initial_capacity, initial_len, filler), 794 _metadata() { 795 init_checks(); 796 } 797 798 // This constructor performs no default initialization, so be careful. 799 GrowableArray(int initial_capacity, int initial_len, MemTag mem_tag) : 800 GrowableArrayWithAllocator<E, GrowableArray>( 801 allocate(initial_capacity, mem_tag), 802 initial_capacity, initial_len), 803 _metadata(mem_tag) { 804 init_checks(); 805 } 806 807 GrowableArray(int initial_capacity, int initial_len, const E& filler, MemTag mem_tag) : 808 GrowableArrayWithAllocator<E, GrowableArray>( 809 allocate(initial_capacity, mem_tag), 810 initial_capacity, initial_len, filler), 811 _metadata(mem_tag) { 812 init_checks(); 813 } 814 815 GrowableArray(Arena* arena, int initial_capacity, int initial_len, const E& filler) : 816 GrowableArrayWithAllocator<E, GrowableArray>( 817 allocate(initial_capacity, arena), 818 initial_capacity, initial_len, filler), 819 _metadata(arena) { 820 init_checks(); 821 } 822 823 ~GrowableArray() { 824 if (on_C_heap()) { 825 this->clear_and_deallocate(); 826 } 827 } 828 }; 829 830 // Leaner GrowableArray for CHeap backed data arrays, with compile-time decided MemTag. 831 template <typename E, MemTag MT> 832 class GrowableArrayCHeap : public GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> > { 833 friend class GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >; 834 835 STATIC_ASSERT(MT != mtNone); 836 837 static E* allocate(int max, MemTag mem_tag) { 838 return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), mem_tag); 839 } 840 841 NONCOPYABLE(GrowableArrayCHeap); 842 843 E* allocate() { 844 return allocate(this->_capacity, MT); 845 } 846 847 void deallocate(E* mem) { 848 GrowableArrayCHeapAllocator::deallocate(mem); 849 } 850 851 public: 852 GrowableArrayCHeap(int initial_capacity = 0) : 853 GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >( 854 allocate(initial_capacity, MT), 855 initial_capacity) {} 856 857 GrowableArrayCHeap(int initial_capacity, int initial_len, const E& filler) : 858 GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, MT> >( 859 allocate(initial_capacity, MT), 860 initial_capacity, initial_len, filler) {} 861 862 ~GrowableArrayCHeap() { 863 this->clear_and_deallocate(); 864 } 865 866 void* operator new(size_t size) { 867 return AnyObj::operator new(size, MT); 868 } 869 870 void* operator new(size_t size, const std::nothrow_t& nothrow_constant) throw() { 871 return AnyObj::operator new(size, nothrow_constant, MT); 872 } 873 void operator delete(void *p) { 874 AnyObj::operator delete(p); 875 } 876 }; 877 878 // Custom STL-style iterator to iterate over GrowableArrays 879 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end() 880 template <typename E> 881 class GrowableArrayIterator : public StackObj { 882 friend class GrowableArrayView<E>; 883 template <typename F, typename UnaryPredicate> friend class GrowableArrayFilterIterator; 884 885 private: 886 const GrowableArrayView<E>* _array; // GrowableArray we iterate over 887 int _position; // The current position in the GrowableArray 888 889 // Private constructor used in GrowableArray::begin() and GrowableArray::end() 890 GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) { 891 assert(0 <= position && position <= _array->length(), "illegal position"); 892 } 893 894 public: 895 GrowableArrayIterator() : _array(nullptr), _position(0) { } 896 GrowableArrayIterator& operator++() { ++_position; return *this; } 897 E operator*() { return _array->at(_position); } 898 899 bool operator==(const GrowableArrayIterator& rhs) { 900 assert(_array == rhs._array, "iterator belongs to different array"); 901 return _position == rhs._position; 902 } 903 904 bool operator!=(const GrowableArrayIterator& rhs) { 905 assert(_array == rhs._array, "iterator belongs to different array"); 906 return _position != rhs._position; 907 } 908 }; 909 910 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate 911 template <typename E, class UnaryPredicate> 912 class GrowableArrayFilterIterator : public StackObj { 913 friend class GrowableArrayView<E>; 914 915 private: 916 const GrowableArrayView<E>* _array; // GrowableArray we iterate over 917 int _position; // Current position in the GrowableArray 918 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy 919 920 public: 921 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate) : 922 _array(array), _position(0), _predicate(filter_predicate) { 923 // Advance to first element satisfying the predicate 924 while(!at_end() && !_predicate(_array->at(_position))) { 925 ++_position; 926 } 927 } 928 929 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() { 930 do { 931 // Advance to next element satisfying the predicate 932 ++_position; 933 } while(!at_end() && !_predicate(_array->at(_position))); 934 return *this; 935 } 936 937 E operator*() { return _array->at(_position); } 938 939 bool operator==(const GrowableArrayIterator<E>& rhs) { 940 assert(_array == rhs._array, "iterator belongs to different array"); 941 return _position == rhs._position; 942 } 943 944 bool operator!=(const GrowableArrayIterator<E>& rhs) { 945 assert(_array == rhs._array, "iterator belongs to different array"); 946 return _position != rhs._position; 947 } 948 949 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) { 950 assert(_array == rhs._array, "iterator belongs to different array"); 951 return _position == rhs._position; 952 } 953 954 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) { 955 assert(_array == rhs._array, "iterator belongs to different array"); 956 return _position != rhs._position; 957 } 958 959 bool at_end() const { 960 return _array == nullptr || _position == _array->end()._position; 961 } 962 }; 963 964 // Arrays for basic types 965 typedef GrowableArray<int> intArray; 966 typedef GrowableArray<int> intStack; 967 typedef GrowableArray<bool> boolArray; 968 969 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP