hotspot/src/share/vm/utilities/growableArray.hpp
author kvn
Tue, 03 Aug 2010 15:55:03 -0700
changeset 6180 53c1bf468c81
parent 5547 f4b087cbb361
child 7397 5b173b4ca846
permissions -rw-r--r--
6973963: SEGV in ciBlock::start_bci() with EA Summary: Added more checks into ResourceObj and growableArray to verify correctness of allocation type. Reviewed-by: never, coleenp, dholmes
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
     1
/*
5547
f4b087cbb361 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 4450
diff changeset
     2
 * Copyright (c) 1997, 2008, Oracle and/or its affiliates. All rights reserved.
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
489c9b5090e2 Initial load
duke
parents:
diff changeset
     4
 *
489c9b5090e2 Initial load
duke
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
489c9b5090e2 Initial load
duke
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
489c9b5090e2 Initial load
duke
parents:
diff changeset
     7
 * published by the Free Software Foundation.
489c9b5090e2 Initial load
duke
parents:
diff changeset
     8
 *
489c9b5090e2 Initial load
duke
parents:
diff changeset
     9
 * This code is distributed in the hope that it will be useful, but WITHOUT
489c9b5090e2 Initial load
duke
parents:
diff changeset
    10
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
489c9b5090e2 Initial load
duke
parents:
diff changeset
    11
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
489c9b5090e2 Initial load
duke
parents:
diff changeset
    12
 * version 2 for more details (a copy is included in the LICENSE file that
489c9b5090e2 Initial load
duke
parents:
diff changeset
    13
 * accompanied this code).
489c9b5090e2 Initial load
duke
parents:
diff changeset
    14
 *
489c9b5090e2 Initial load
duke
parents:
diff changeset
    15
 * You should have received a copy of the GNU General Public License version
489c9b5090e2 Initial load
duke
parents:
diff changeset
    16
 * 2 along with this work; if not, write to the Free Software Foundation,
489c9b5090e2 Initial load
duke
parents:
diff changeset
    17
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    18
 *
5547
f4b087cbb361 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 4450
diff changeset
    19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
f4b087cbb361 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 4450
diff changeset
    20
 * or visit www.oracle.com if you need additional information or have any
f4b087cbb361 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 4450
diff changeset
    21
 * questions.
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
    22
 *
489c9b5090e2 Initial load
duke
parents:
diff changeset
    23
 */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    24
489c9b5090e2 Initial load
duke
parents:
diff changeset
    25
// A growable array.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    26
489c9b5090e2 Initial load
duke
parents:
diff changeset
    27
/*************************************************************************/
489c9b5090e2 Initial load
duke
parents:
diff changeset
    28
/*                                                                       */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    29
/*     WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING   */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    30
/*                                                                       */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    31
/* Should you use GrowableArrays to contain handles you must be certain  */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    32
/* the the GrowableArray does not outlive the HandleMark that contains   */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    33
/* the handles. Since GrowableArrays are typically resource allocated    */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    34
/* the following is an example of INCORRECT CODE,                        */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    35
/*                                                                       */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    36
/* ResourceMark rm;                                                      */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    37
/* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size);         */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    38
/* if (blah) {                                                           */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    39
/*    while (...) {                                                      */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    40
/*      HandleMark hm;                                                   */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    41
/*      ...                                                              */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    42
/*      Handle h(THREAD, some_oop);                                      */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    43
/*      arr->append(h);                                                  */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    44
/*    }                                                                  */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    45
/* }                                                                     */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    46
/* if (arr->length() != 0 ) {                                            */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    47
/*    oop bad_oop = arr->at(0)(); // Handle is BAD HERE.                 */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    48
/*    ...                                                                */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    49
/* }                                                                     */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    50
/*                                                                       */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    51
/* If the GrowableArrays you are creating is C_Heap allocated then it    */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    52
/* hould not old handles since the handles could trivially try and       */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    53
/* outlive their HandleMark. In some situations you might need to do     */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    54
/* this and it would be legal but be very careful and see if you can do  */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    55
/* the code in some other manner.                                        */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    56
/*                                                                       */
489c9b5090e2 Initial load
duke
parents:
diff changeset
    57
/*************************************************************************/
489c9b5090e2 Initial load
duke
parents:
diff changeset
    58
489c9b5090e2 Initial load
duke
parents:
diff changeset
    59
// To call default constructor the placement operator new() is used.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    60
// It should be empty (it only returns the passed void* pointer).
489c9b5090e2 Initial load
duke
parents:
diff changeset
    61
// The definition of placement operator new(size_t, void*) in the <new>.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    62
489c9b5090e2 Initial load
duke
parents:
diff changeset
    63
#include <new>
489c9b5090e2 Initial load
duke
parents:
diff changeset
    64
489c9b5090e2 Initial load
duke
parents:
diff changeset
    65
// Need the correct linkage to call qsort without warnings
489c9b5090e2 Initial load
duke
parents:
diff changeset
    66
extern "C" {
489c9b5090e2 Initial load
duke
parents:
diff changeset
    67
  typedef int (*_sort_Fn)(const void *, const void *);
489c9b5090e2 Initial load
duke
parents:
diff changeset
    68
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
    69
489c9b5090e2 Initial load
duke
parents:
diff changeset
    70
class GenericGrowableArray : public ResourceObj {
489c9b5090e2 Initial load
duke
parents:
diff changeset
    71
 protected:
489c9b5090e2 Initial load
duke
parents:
diff changeset
    72
  int    _len;          // current length
489c9b5090e2 Initial load
duke
parents:
diff changeset
    73
  int    _max;          // maximum length
489c9b5090e2 Initial load
duke
parents:
diff changeset
    74
  Arena* _arena;        // Indicates where allocation occurs:
489c9b5090e2 Initial load
duke
parents:
diff changeset
    75
                        //   0 means default ResourceArea
489c9b5090e2 Initial load
duke
parents:
diff changeset
    76
                        //   1 means on C heap
489c9b5090e2 Initial load
duke
parents:
diff changeset
    77
                        //   otherwise, allocate in _arena
489c9b5090e2 Initial load
duke
parents:
diff changeset
    78
#ifdef ASSERT
489c9b5090e2 Initial load
duke
parents:
diff changeset
    79
  int    _nesting;      // resource area nesting at creation
489c9b5090e2 Initial load
duke
parents:
diff changeset
    80
  void   set_nesting();
489c9b5090e2 Initial load
duke
parents:
diff changeset
    81
  void   check_nesting();
489c9b5090e2 Initial load
duke
parents:
diff changeset
    82
#else
489c9b5090e2 Initial load
duke
parents:
diff changeset
    83
#define  set_nesting();
489c9b5090e2 Initial load
duke
parents:
diff changeset
    84
#define  check_nesting();
489c9b5090e2 Initial load
duke
parents:
diff changeset
    85
#endif
489c9b5090e2 Initial load
duke
parents:
diff changeset
    86
489c9b5090e2 Initial load
duke
parents:
diff changeset
    87
  // Where are we going to allocate memory?
489c9b5090e2 Initial load
duke
parents:
diff changeset
    88
  bool on_C_heap() { return _arena == (Arena*)1; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
    89
  bool on_stack () { return _arena == NULL;      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
    90
  bool on_arena () { return _arena >  (Arena*)1;  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
    91
489c9b5090e2 Initial load
duke
parents:
diff changeset
    92
  // This GA will use the resource stack for storage if c_heap==false,
489c9b5090e2 Initial load
duke
parents:
diff changeset
    93
  // Else it will use the C heap.  Use clear_and_deallocate to avoid leaks.
489c9b5090e2 Initial load
duke
parents:
diff changeset
    94
  GenericGrowableArray(int initial_size, int initial_len, bool c_heap) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
    95
    _len = initial_len;
489c9b5090e2 Initial load
duke
parents:
diff changeset
    96
    _max = initial_size;
489c9b5090e2 Initial load
duke
parents:
diff changeset
    97
    assert(_len >= 0 && _len <= _max, "initial_len too big");
489c9b5090e2 Initial load
duke
parents:
diff changeset
    98
    _arena = (c_heap ? (Arena*)1 : NULL);
489c9b5090e2 Initial load
duke
parents:
diff changeset
    99
    set_nesting();
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   100
    assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are");
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   101
    assert(!on_stack() ||
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   102
           (allocated_on_res_area() || allocated_on_stack()),
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   103
           "growable array must be on stack if elements are not on arena and not on C heap");
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   104
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   105
489c9b5090e2 Initial load
duke
parents:
diff changeset
   106
  // This GA will use the given arena for storage.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   107
  // Consider using new(arena) GrowableArray<T> to allocate the header.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   108
  GenericGrowableArray(Arena* arena, int initial_size, int initial_len) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   109
    _len = initial_len;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   110
    _max = initial_size;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   111
    assert(_len >= 0 && _len <= _max, "initial_len too big");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   112
    _arena = arena;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   113
    assert(on_arena(), "arena has taken on reserved value 0 or 1");
6180
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   114
    // Relax next assert to allow object allocation on resource area,
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   115
    // on stack or embedded into an other object.
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   116
    assert(allocated_on_arena() || allocated_on_stack(),
53c1bf468c81 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 5547
diff changeset
   117
           "growable array must be on arena or on stack if elements are on arena");
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   118
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   119
489c9b5090e2 Initial load
duke
parents:
diff changeset
   120
  void* raw_allocate(int elementSize);
1551
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   121
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   122
  // some uses pass the Thread explicitly for speed (4990299 tuning)
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   123
  void* raw_allocate(Thread* thread, int elementSize) {
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   124
    assert(on_stack(), "fast ResourceObj path only");
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   125
    return (void*)resource_allocate_bytes(thread, elementSize * _max);
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   126
  }
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   127
};
489c9b5090e2 Initial load
duke
parents:
diff changeset
   128
489c9b5090e2 Initial load
duke
parents:
diff changeset
   129
template<class E> class GrowableArray : public GenericGrowableArray {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   130
 private:
489c9b5090e2 Initial load
duke
parents:
diff changeset
   131
  E*     _data;         // data array
489c9b5090e2 Initial load
duke
parents:
diff changeset
   132
489c9b5090e2 Initial load
duke
parents:
diff changeset
   133
  void grow(int j);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   134
  void raw_at_put_grow(int i, const E& p, const E& fill);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   135
  void  clear_and_deallocate();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   136
 public:
1551
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   137
  GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   138
    _data = (E*)raw_allocate(thread, sizeof(E));
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   139
    for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   140
  }
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   141
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   142
  GrowableArray(int initial_size, bool C_heap = false) : GenericGrowableArray(initial_size, 0, C_heap) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   143
    _data = (E*)raw_allocate(sizeof(E));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   144
    for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   145
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   146
489c9b5090e2 Initial load
duke
parents:
diff changeset
   147
  GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false) : GenericGrowableArray(initial_size, initial_len, C_heap) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   148
    _data = (E*)raw_allocate(sizeof(E));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   149
    int i = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   150
    for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   151
    for (; i < _max; i++) ::new ((void*)&_data[i]) E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   152
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   153
489c9b5090e2 Initial load
duke
parents:
diff changeset
   154
  GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   155
    _data = (E*)raw_allocate(sizeof(E));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   156
    int i = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   157
    for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   158
    for (; i < _max; i++) ::new ((void*)&_data[i]) E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   159
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   160
489c9b5090e2 Initial load
duke
parents:
diff changeset
   161
  GrowableArray() : GenericGrowableArray(2, 0, false) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   162
    _data = (E*)raw_allocate(sizeof(E));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   163
    ::new ((void*)&_data[0]) E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   164
    ::new ((void*)&_data[1]) E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   165
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   166
489c9b5090e2 Initial load
duke
parents:
diff changeset
   167
                                // Does nothing for resource and arena objects
489c9b5090e2 Initial load
duke
parents:
diff changeset
   168
  ~GrowableArray()              { if (on_C_heap()) clear_and_deallocate(); }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   169
489c9b5090e2 Initial load
duke
parents:
diff changeset
   170
  void  clear()                 { _len = 0; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   171
  int   length() const          { return _len; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   172
  void  trunc_to(int l)         { assert(l <= _len,"cannot increase length"); _len = l; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   173
  bool  is_empty() const        { return _len == 0; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   174
  bool  is_nonempty() const     { return _len != 0; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   175
  bool  is_full() const         { return _len == _max; }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   176
  DEBUG_ONLY(E* data_addr() const      { return _data; })
489c9b5090e2 Initial load
duke
parents:
diff changeset
   177
489c9b5090e2 Initial load
duke
parents:
diff changeset
   178
  void print();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   179
1551
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   180
  int append(const E& elem) {
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   181
    check_nesting();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   182
    if (_len == _max) grow(_len);
1551
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   183
    int idx = _len++;
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   184
    _data[idx] = elem;
b431de37a22c 6770949: minor tweaks before 6655638
jrose
parents: 1
diff changeset
   185
    return idx;
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   186
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   187
489c9b5090e2 Initial load
duke
parents:
diff changeset
   188
  void append_if_missing(const E& elem) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   189
    if (!contains(elem)) append(elem);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   190
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   191
489c9b5090e2 Initial load
duke
parents:
diff changeset
   192
  E at(int i) const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   193
    assert(0 <= i && i < _len, "illegal index");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   194
    return _data[i];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   195
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   196
489c9b5090e2 Initial load
duke
parents:
diff changeset
   197
  E* adr_at(int i) const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   198
    assert(0 <= i && i < _len, "illegal index");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   199
    return &_data[i];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   200
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   201
489c9b5090e2 Initial load
duke
parents:
diff changeset
   202
  E first() const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   203
    assert(_len > 0, "empty list");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   204
    return _data[0];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   205
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   206
489c9b5090e2 Initial load
duke
parents:
diff changeset
   207
  E top() const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   208
    assert(_len > 0, "empty list");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   209
    return _data[_len-1];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   210
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   211
489c9b5090e2 Initial load
duke
parents:
diff changeset
   212
  void push(const E& elem) { append(elem); }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   213
489c9b5090e2 Initial load
duke
parents:
diff changeset
   214
  E pop() {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   215
    assert(_len > 0, "empty list");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   216
    return _data[--_len];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   217
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   218
489c9b5090e2 Initial load
duke
parents:
diff changeset
   219
  void at_put(int i, const E& elem) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   220
    assert(0 <= i && i < _len, "illegal index");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   221
    _data[i] = elem;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   222
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   223
489c9b5090e2 Initial load
duke
parents:
diff changeset
   224
  E at_grow(int i, const E& fill = E()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   225
    assert(0 <= i, "negative index");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   226
    check_nesting();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   227
    if (i >= _len) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   228
      if (i >= _max) grow(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   229
      for (int j = _len; j <= i; j++)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   230
        _data[j] = fill;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   231
      _len = i+1;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   232
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   233
    return _data[i];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   234
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   235
489c9b5090e2 Initial load
duke
parents:
diff changeset
   236
  void at_put_grow(int i, const E& elem, const E& fill = E()) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   237
    assert(0 <= i, "negative index");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   238
    check_nesting();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   239
    raw_at_put_grow(i, elem, fill);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   240
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   241
489c9b5090e2 Initial load
duke
parents:
diff changeset
   242
  bool contains(const E& elem) const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   243
    for (int i = 0; i < _len; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   244
      if (_data[i] == elem) return true;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   245
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   246
    return false;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   247
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   248
489c9b5090e2 Initial load
duke
parents:
diff changeset
   249
  int  find(const E& elem) const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   250
    for (int i = 0; i < _len; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   251
      if (_data[i] == elem) return i;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   252
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   253
    return -1;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   254
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   255
489c9b5090e2 Initial load
duke
parents:
diff changeset
   256
  int  find(void* token, bool f(void*, E)) const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   257
    for (int i = 0; i < _len; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   258
      if (f(token, _data[i])) return i;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   259
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   260
    return -1;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   261
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   262
489c9b5090e2 Initial load
duke
parents:
diff changeset
   263
  int  find_at_end(void* token, bool f(void*, E)) const {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   264
    // start at the end of the array
489c9b5090e2 Initial load
duke
parents:
diff changeset
   265
    for (int i = _len-1; i >= 0; i--) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   266
      if (f(token, _data[i])) return i;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   267
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   268
    return -1;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   269
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   270
489c9b5090e2 Initial load
duke
parents:
diff changeset
   271
  void remove(const E& elem) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   272
    for (int i = 0; i < _len; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   273
      if (_data[i] == elem) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   274
        for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   275
        _len--;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   276
        return;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   277
      }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   278
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   279
    ShouldNotReachHere();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   280
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   281
489c9b5090e2 Initial load
duke
parents:
diff changeset
   282
  void remove_at(int index) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   283
    assert(0 <= index && index < _len, "illegal index");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   284
    for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j];
489c9b5090e2 Initial load
duke
parents:
diff changeset
   285
    _len--;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   286
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   287
4450
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   288
  // inserts the given element before the element at index i
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   289
  void insert_before(const int idx, const E& elem) {
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   290
    check_nesting();
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   291
    if (_len == _max) grow(_len);
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   292
    for (int j = _len - 1; j >= idx; j--) {
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   293
      _data[j + 1] = _data[j];
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   294
    }
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   295
    _len++;
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   296
    _data[idx] = elem;
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   297
  }
6d700b859b3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 1623
diff changeset
   298
1
489c9b5090e2 Initial load
duke
parents:
diff changeset
   299
  void appendAll(const GrowableArray<E>* l) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   300
    for (int i = 0; i < l->_len; i++) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   301
      raw_at_put_grow(_len, l->_data[i], 0);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   302
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   303
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   304
489c9b5090e2 Initial load
duke
parents:
diff changeset
   305
  void sort(int f(E*,E*)) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   306
    qsort(_data, length(), sizeof(E), (_sort_Fn)f);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   307
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   308
  // sort by fixed-stride sub arrays:
489c9b5090e2 Initial load
duke
parents:
diff changeset
   309
  void sort(int f(E*,E*), int stride) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   310
    qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   311
  }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   312
};
489c9b5090e2 Initial load
duke
parents:
diff changeset
   313
489c9b5090e2 Initial load
duke
parents:
diff changeset
   314
// Global GrowableArray methods (one instance in the library per each 'E' type).
489c9b5090e2 Initial load
duke
parents:
diff changeset
   315
489c9b5090e2 Initial load
duke
parents:
diff changeset
   316
template<class E> void GrowableArray<E>::grow(int j) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   317
    // grow the array by doubling its size (amortized growth)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   318
    int old_max = _max;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   319
    if (_max == 0) _max = 1; // prevent endless loop
489c9b5090e2 Initial load
duke
parents:
diff changeset
   320
    while (j >= _max) _max = _max*2;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   321
    // j < _max
489c9b5090e2 Initial load
duke
parents:
diff changeset
   322
    E* newData = (E*)raw_allocate(sizeof(E));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   323
    int i = 0;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   324
    for (     ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   325
    for (     ; i < _max; i++) ::new ((void*)&newData[i]) E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   326
    for (i = 0; i < old_max; i++) _data[i].~E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   327
    if (on_C_heap() && _data != NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   328
      FreeHeap(_data);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   329
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   330
    _data = newData;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   331
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   332
489c9b5090e2 Initial load
duke
parents:
diff changeset
   333
template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   334
    if (i >= _len) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   335
      if (i >= _max) grow(i);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   336
      for (int j = _len; j < i; j++)
489c9b5090e2 Initial load
duke
parents:
diff changeset
   337
        _data[j] = fill;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   338
      _len = i+1;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   339
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   340
    _data[i] = p;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   341
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   342
489c9b5090e2 Initial load
duke
parents:
diff changeset
   343
// This function clears and deallocate the data in the growable array that
489c9b5090e2 Initial load
duke
parents:
diff changeset
   344
// has been allocated on the C heap.  It's not public - called by the
489c9b5090e2 Initial load
duke
parents:
diff changeset
   345
// destructor.
489c9b5090e2 Initial load
duke
parents:
diff changeset
   346
template<class E> void GrowableArray<E>::clear_and_deallocate() {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   347
    assert(on_C_heap(),
489c9b5090e2 Initial load
duke
parents:
diff changeset
   348
           "clear_and_deallocate should only be called when on C heap");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   349
    clear();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   350
    if (_data != NULL) {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   351
      for (int i = 0; i < _max; i++) _data[i].~E();
489c9b5090e2 Initial load
duke
parents:
diff changeset
   352
      FreeHeap(_data);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   353
      _data = NULL;
489c9b5090e2 Initial load
duke
parents:
diff changeset
   354
    }
489c9b5090e2 Initial load
duke
parents:
diff changeset
   355
}
489c9b5090e2 Initial load
duke
parents:
diff changeset
   356
489c9b5090e2 Initial load
duke
parents:
diff changeset
   357
template<class E> void GrowableArray<E>::print() {
489c9b5090e2 Initial load
duke
parents:
diff changeset
   358
    tty->print("Growable Array " INTPTR_FORMAT, this);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   359
    tty->print(": length %ld (_max %ld) { ", _len, _max);
489c9b5090e2 Initial load
duke
parents:
diff changeset
   360
    for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
489c9b5090e2 Initial load
duke
parents:
diff changeset
   361
    tty->print("}\n");
489c9b5090e2 Initial load
duke
parents:
diff changeset
   362
}