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