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