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