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