< prev index next >

src/share/vm/utilities/growableArray.hpp

Print this page
rev 10358 : imported patch c1_LIR
rev 10368 : imported patch minor fixes
rev 10374 : imported patch Avoid eager initialization for some types


   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_VM_UTILITIES_GROWABLEARRAY_HPP
  26 #define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
  27 


  28 #include "memory/allocation.hpp"
  29 #include "memory/allocation.inline.hpp"
  30 #include "utilities/debug.hpp"
  31 #include "utilities/globalDefinitions.hpp"
  32 #include "utilities/top.hpp"

  33 
  34 // A growable array.
  35 
  36 /*************************************************************************/
  37 /*                                                                       */
  38 /*     WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING   */
  39 /*                                                                       */
  40 /* Should you use GrowableArrays to contain handles you must be certain  */
  41 /* the the GrowableArray does not outlive the HandleMark that contains   */
  42 /* the handles. Since GrowableArrays are typically resource allocated    */
  43 /* the following is an example of INCORRECT CODE,                        */
  44 /*                                                                       */
  45 /* ResourceMark rm;                                                      */
  46 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size);         */
  47 /* if (blah) {                                                           */
  48 /*    while (...) {                                                      */
  49 /*      HandleMark hm;                                                   */
  50 /*      ...                                                              */
  51 /*      Handle h(THREAD, some_oop);                                      */
  52 /*      arr->append(h);                                                  */


 128     _len = initial_len;
 129     _max = initial_size;
 130     assert(_len >= 0 && _len <= _max, "initial_len too big");
 131     _arena = arena;
 132     _memflags = mtNone;
 133 
 134     assert(on_arena(), "arena has taken on reserved value 0 or 1");
 135     // Relax next assert to allow object allocation on resource area,
 136     // on stack or embedded into an other object.
 137     assert(allocated_on_arena() || allocated_on_stack(),
 138            "growable array must be on arena or on stack if elements are on arena");
 139   }
 140 
 141   void* raw_allocate(int elementSize);
 142 
 143   // some uses pass the Thread explicitly for speed (4990299 tuning)
 144   void* raw_allocate(Thread* thread, int elementSize) {
 145     assert(on_stack(), "fast ResourceObj path only");
 146     return (void*)resource_allocate_bytes(thread, elementSize * _max);
 147   }
















 148 };
 149 
 150 template<class E> class GrowableArrayIterator;
 151 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator;
 152 
 153 template<class E> class GrowableArray : public GenericGrowableArray {
 154   friend class VMStructs;
 155 
 156  private:
 157   E*     _data;         // data array
 158 
 159   void grow(int j);
 160   void raw_at_put_grow(int i, const E& p, const E& fill);
 161   void  clear_and_deallocate();

 162  public:
 163   GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
 164     _data = (E*)raw_allocate(thread, sizeof(E));
 165     for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
 166   }
 167 
 168   GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
 169     : GenericGrowableArray(initial_size, 0, C_heap, F) {
 170     _data = (E*)raw_allocate(sizeof(E));
 171 // Needed for Visual Studio 2012 and older
 172 #ifdef _MSC_VER
 173 #pragma warning(suppress: 4345)
 174 #endif
 175     for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
 176   }
 177 
 178   GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
 179     : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
 180     _data = (E*)raw_allocate(sizeof(E));
 181     int i = 0;
 182     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 183     for (; i < _max; i++) ::new ((void*)&_data[i]) E();
 184   }
 185 
 186   GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
 187     _data = (E*)raw_allocate(sizeof(E));
 188     int i = 0;
 189     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 190     for (; i < _max; i++) ::new ((void*)&_data[i]) E();
 191   }
 192 
 193   GrowableArray() : GenericGrowableArray(2, 0, false) {
 194     _data = (E*)raw_allocate(sizeof(E));
 195     ::new ((void*)&_data[0]) E();
 196     ::new ((void*)&_data[1]) E();
 197   }
 198 
 199                                 // Does nothing for resource and arena objects
 200   ~GrowableArray()              { if (on_C_heap()) clear_and_deallocate(); }
 201 
 202   void  clear()                 { _len = 0; }
 203   int   length() const          { return _len; }
 204   int   max_length() const      { return _max; }
 205   void  trunc_to(int l)         { assert(l <= _len,"cannot increase length"); _len = l; }
 206   bool  is_empty() const        { return _len == 0; }
 207   bool  is_nonempty() const     { return _len != 0; }
 208   bool  is_full() const         { return _len == _max; }
 209   DEBUG_ONLY(E* data_addr() const      { return _data; })
 210 
 211   void print();
 212 
 213   int append(const E& elem) {
 214     check_nesting();
 215     if (_len == _max) grow(_len);
 216     int idx = _len++;


 432     }
 433     return min;
 434   }
 435 };
 436 
 437 // Global GrowableArray methods (one instance in the library per each 'E' type).
 438 
 439 template<class E> void GrowableArray<E>::grow(int j) {
 440     // grow the array by doubling its size (amortized growth)
 441     int old_max = _max;
 442     if (_max == 0) _max = 1; // prevent endless loop
 443     while (j >= _max) _max = _max*2;
 444     // j < _max
 445     E* newData = (E*)raw_allocate(sizeof(E));
 446     int i = 0;
 447     for (     ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
 448 // Needed for Visual Studio 2012 and older
 449 #ifdef _MSC_VER
 450 #pragma warning(suppress: 4345)
 451 #endif
 452     for (     ; i < _max; i++) ::new ((void*)&newData[i]) E();
 453     for (i = 0; i < old_max; i++) _data[i].~E();
 454     if (on_C_heap() && _data != NULL) {
 455       FreeHeap(_data);
 456     }
 457     _data = newData;
 458 }
 459 
 460 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
 461     if (i >= _len) {
 462       if (i >= _max) grow(i);
 463       for (int j = _len; j < i; j++)
 464         _data[j] = fill;
 465       _len = i+1;
 466     }
 467     _data[i] = p;
 468 }
 469 
 470 // This function clears and deallocate the data in the growable array that
 471 // has been allocated on the C heap.  It's not public - called by the
 472 // destructor.
 473 template<class E> void GrowableArray<E>::clear_and_deallocate() {
 474     assert(on_C_heap(),
 475            "clear_and_deallocate should only be called when on C heap");
 476     clear();
 477     if (_data != NULL) {
 478       for (int i = 0; i < _max; i++) _data[i].~E();
 479       FreeHeap(_data);
 480       _data = NULL;
 481     }
 482 }
 483 
 484 template<class E> void GrowableArray<E>::print() {
 485     tty->print("Growable Array " INTPTR_FORMAT, this);
 486     tty->print(": length %ld (_max %ld) { ", _len, _max);
 487     for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
 488     tty->print("}\n");
 489 }
 490 
 491 // Custom STL-style iterator to iterate over GrowableArrays
 492 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
 493 template<class E> class GrowableArrayIterator : public StackObj {
 494   friend class GrowableArray<E>;
 495   template<class F, class UnaryPredicate> friend class GrowableArrayFilterIterator;
 496 
 497  private:
 498   const GrowableArray<E>* _array; // GrowableArray we iterate over


 548 
 549   bool operator==(const GrowableArrayIterator<E>& rhs)  {
 550     assert(_array == rhs._array, "iterator belongs to different array");
 551     return _position == rhs._position;
 552   }
 553 
 554   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
 555     assert(_array == rhs._array, "iterator belongs to different array");
 556     return _position != rhs._position;
 557   }
 558 
 559   bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 560     assert(_array == rhs._array, "iterator belongs to different array");
 561     return _position == rhs._position;
 562   }
 563 
 564   bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 565     assert(_array == rhs._array, "iterator belongs to different array");
 566     return _position != rhs._position;
 567   }










 568 };
 569 
 570 #endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP


   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_VM_UTILITIES_GROWABLEARRAY_HPP
  26 #define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
  27 
  28 #include <limits>
  29 
  30 #include "memory/allocation.hpp"
  31 #include "memory/allocation.inline.hpp"
  32 #include "utilities/debug.hpp"
  33 #include "utilities/globalDefinitions.hpp"
  34 #include "utilities/top.hpp"
  35 #include "utilities/traits.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 /* the 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);                                                  */


 131     _len = initial_len;
 132     _max = initial_size;
 133     assert(_len >= 0 && _len <= _max, "initial_len too big");
 134     _arena = arena;
 135     _memflags = mtNone;
 136 
 137     assert(on_arena(), "arena has taken on reserved value 0 or 1");
 138     // Relax next assert to allow object allocation on resource area,
 139     // on stack or embedded into an other object.
 140     assert(allocated_on_arena() || allocated_on_stack(),
 141            "growable array must be on arena or on stack if elements are on arena");
 142   }
 143 
 144   void* raw_allocate(int elementSize);
 145 
 146   // some uses pass the Thread explicitly for speed (4990299 tuning)
 147   void* raw_allocate(Thread* thread, int elementSize) {
 148     assert(on_stack(), "fast ResourceObj path only");
 149     return (void*)resource_allocate_bytes(thread, elementSize * _max);
 150   }
 151 
 152   template<typename T1, typename T2 = T1> class Initializer {
 153     STATIC_ASSERT((same_types<T1, T2>::value));
 154   public:
 155     static void init(T1* data, int from, int to) {
 156       for (int i = from; i < to; i++) {
 157         ::new((void*) &data[i]) T1();
 158       }
 159     }
 160 
 161     static void deinit(T1* data, int from, int to) {
 162       for (int i = from; i < to; i++) {
 163         data[i].~T1();
 164       }
 165     }
 166   };
 167 };
 168 
 169 template<class E> class GrowableArrayIterator;
 170 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator;
 171 
 172 template<class E> class GrowableArray : public GenericGrowableArray {
 173   friend class VMStructs;
 174 
 175  private:
 176   E*     _data;         // data array
 177 
 178   void grow(int j);
 179   void raw_at_put_grow(int i, const E& p, const E& fill);
 180   void  clear_and_deallocate();
 181 
 182  public:
 183   GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
 184     _data = (E*)raw_allocate(thread, sizeof(E));
 185     GenericGrowableArray::Initializer<E>::init(_data, 0, _max);
 186   }
 187 
 188   GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
 189     : GenericGrowableArray(initial_size, 0, C_heap, F) {
 190     _data = (E*)raw_allocate(sizeof(E));
 191 // Needed for Visual Studio 2012 and older
 192 #ifdef _MSC_VER
 193 #pragma warning(suppress: 4345)
 194 #endif
 195     GenericGrowableArray::Initializer<E>::init(_data, 0, _max);
 196   }
 197 
 198   GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
 199     : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
 200     _data = (E*)raw_allocate(sizeof(E));
 201     int i = 0;
 202     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 203     GenericGrowableArray::Initializer<E>::init(_data, _len, _max);
 204   }
 205 
 206   GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
 207     _data = (E*)raw_allocate(sizeof(E));
 208     int i = 0;
 209     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 210     GenericGrowableArray::Initializer<E>::init(_data, _len, _max);
 211   }
 212 
 213   GrowableArray() : GenericGrowableArray(2, 0, false) {
 214     _data = (E*)raw_allocate(sizeof(E));
 215     GenericGrowableArray::Initializer<E>::init(_data, 0, 2);

 216   }
 217 
 218                                 // Does nothing for resource and arena objects
 219   ~GrowableArray()              { if (on_C_heap()) clear_and_deallocate(); }
 220 
 221   void  clear()                 { _len = 0; }
 222   int   length() const          { return _len; }
 223   int   max_length() const      { return _max; }
 224   void  trunc_to(int l)         { assert(l <= _len,"cannot increase length"); _len = l; }
 225   bool  is_empty() const        { return _len == 0; }
 226   bool  is_nonempty() const     { return _len != 0; }
 227   bool  is_full() const         { return _len == _max; }
 228   DEBUG_ONLY(E* data_addr() const      { return _data; })
 229 
 230   void print();
 231 
 232   int append(const E& elem) {
 233     check_nesting();
 234     if (_len == _max) grow(_len);
 235     int idx = _len++;


 451     }
 452     return min;
 453   }
 454 };
 455 
 456 // Global GrowableArray methods (one instance in the library per each 'E' type).
 457 
 458 template<class E> void GrowableArray<E>::grow(int j) {
 459     // grow the array by doubling its size (amortized growth)
 460     int old_max = _max;
 461     if (_max == 0) _max = 1; // prevent endless loop
 462     while (j >= _max) _max = _max*2;
 463     // j < _max
 464     E* newData = (E*)raw_allocate(sizeof(E));
 465     int i = 0;
 466     for (     ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
 467 // Needed for Visual Studio 2012 and older
 468 #ifdef _MSC_VER
 469 #pragma warning(suppress: 4345)
 470 #endif
 471     GenericGrowableArray::Initializer<E>::init(newData, i, _max);
 472     GenericGrowableArray::Initializer<E>::deinit(_data, 0, old_max);
 473     if (on_C_heap() && _data != NULL) {
 474       FreeHeap(_data);
 475     }
 476     _data = newData;
 477 }
 478 
 479 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
 480     if (i >= _len) {
 481       if (i >= _max) grow(i);
 482       for (int j = _len; j < i; j++)
 483         _data[j] = fill;
 484       _len = i+1;
 485     }
 486     _data[i] = p;
 487 }
 488 
 489 // This function clears and deallocate the data in the growable array that
 490 // has been allocated on the C heap.  It's not public - called by the
 491 // destructor.
 492 template<class E> void GrowableArray<E>::clear_and_deallocate() {
 493     assert(on_C_heap(),
 494            "clear_and_deallocate should only be called when on C heap");
 495     clear();
 496     if (_data != NULL) {
 497       GenericGrowableArray::Initializer<E>::deinit(_data, 0, _max);
 498       FreeHeap(_data);
 499       _data = NULL;
 500     }
 501 }
 502 
 503 template<class E> void GrowableArray<E>::print() {
 504     tty->print("Growable Array " INTPTR_FORMAT, this);
 505     tty->print(": length %ld (_max %ld) { ", _len, _max);
 506     for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
 507     tty->print("}\n");
 508 }
 509 
 510 // Custom STL-style iterator to iterate over GrowableArrays
 511 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
 512 template<class E> class GrowableArrayIterator : public StackObj {
 513   friend class GrowableArray<E>;
 514   template<class F, class UnaryPredicate> friend class GrowableArrayFilterIterator;
 515 
 516  private:
 517   const GrowableArray<E>* _array; // GrowableArray we iterate over


 567 
 568   bool operator==(const GrowableArrayIterator<E>& rhs)  {
 569     assert(_array == rhs._array, "iterator belongs to different array");
 570     return _position == rhs._position;
 571   }
 572 
 573   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
 574     assert(_array == rhs._array, "iterator belongs to different array");
 575     return _position != rhs._position;
 576   }
 577 
 578   bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 579     assert(_array == rhs._array, "iterator belongs to different array");
 580     return _position == rhs._position;
 581   }
 582 
 583   bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 584     assert(_array == rhs._array, "iterator belongs to different array");
 585     return _position != rhs._position;
 586   }
 587 };
 588 
 589 template <typename T1>
 590 class GenericGrowableArray::Initializer<T1,
 591   typename enable_if<std::numeric_limits<T1>::is_integer
 592                      || is_floating_point<T1>::value
 593                      || is_pointer<T1>::value, T1>::type> {
 594 public:
 595   static void init(T1* data, int from, int to) {}
 596   static void deinit(T1* data, int from, int to) {}
 597 };
 598 
 599 #endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
< prev index next >