annotate src/share/vm/utilities/growableArray.hpp @ 9126:bc26f978b0ce

HotSpotResolvedObjectType: implement hasFinalizeSubclass() correctly don't use the (wrong) cached value, but ask the runtime on each request. Fixes regression on xml.* benchmarks @ specjvm2008. The problem was: After the constructor of Object was deoptimized due to an assumption violation, it was recompiled again after some time. However, on recompilation, the value of hasFinalizeSubclass for the class was not updated and it was compiled again with a, now wrong, assumption, which then triggers deoptimization again. This was repeated until it hit the recompilation limit (defined by PerMethodRecompilationCutoff), and therefore only executed by the interpreter from now on, causing the performance regression.
author Bernhard Urban <bernhard.urban@jku.at>
date Mon, 15 Apr 2013 19:54:58 +0200
parents 4735d2c84362
children 5888334c9c24
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
a61af66fc99e Initial load
duke
parents:
diff changeset
1 /*
5948
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
2 * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
0
a61af66fc99e Initial load
duke
parents:
diff changeset
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
a61af66fc99e Initial load
duke
parents:
diff changeset
4 *
a61af66fc99e Initial load
duke
parents:
diff changeset
5 * This code is free software; you can redistribute it and/or modify it
a61af66fc99e Initial load
duke
parents:
diff changeset
6 * under the terms of the GNU General Public License version 2 only, as
a61af66fc99e Initial load
duke
parents:
diff changeset
7 * published by the Free Software Foundation.
a61af66fc99e Initial load
duke
parents:
diff changeset
8 *
a61af66fc99e Initial load
duke
parents:
diff changeset
9 * This code is distributed in the hope that it will be useful, but WITHOUT
a61af66fc99e Initial load
duke
parents:
diff changeset
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
a61af66fc99e Initial load
duke
parents:
diff changeset
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
a61af66fc99e Initial load
duke
parents:
diff changeset
12 * version 2 for more details (a copy is included in the LICENSE file that
a61af66fc99e Initial load
duke
parents:
diff changeset
13 * accompanied this code).
a61af66fc99e Initial load
duke
parents:
diff changeset
14 *
a61af66fc99e Initial load
duke
parents:
diff changeset
15 * You should have received a copy of the GNU General Public License version
a61af66fc99e Initial load
duke
parents:
diff changeset
16 * 2 along with this work; if not, write to the Free Software Foundation,
a61af66fc99e Initial load
duke
parents:
diff changeset
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
a61af66fc99e Initial load
duke
parents:
diff changeset
18 *
1552
c18cbe5936b8 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 1080
diff changeset
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
c18cbe5936b8 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 1080
diff changeset
20 * or visit www.oracle.com if you need additional information or have any
c18cbe5936b8 6941466: Oracle rebranding changes for Hotspot repositories
trims
parents: 1080
diff changeset
21 * questions.
0
a61af66fc99e Initial load
duke
parents:
diff changeset
22 *
a61af66fc99e Initial load
duke
parents:
diff changeset
23 */
a61af66fc99e Initial load
duke
parents:
diff changeset
24
1972
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
25 #ifndef SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
26 #define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
27
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
28 #include "memory/allocation.hpp"
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
29 #include "memory/allocation.inline.hpp"
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
30 #include "utilities/debug.hpp"
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
31 #include "utilities/globalDefinitions.hpp"
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
32 #include "utilities/top.hpp"
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
33
0
a61af66fc99e Initial load
duke
parents:
diff changeset
34 // A growable array.
a61af66fc99e Initial load
duke
parents:
diff changeset
35
a61af66fc99e Initial load
duke
parents:
diff changeset
36 /*************************************************************************/
a61af66fc99e Initial load
duke
parents:
diff changeset
37 /* */
a61af66fc99e Initial load
duke
parents:
diff changeset
38 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
a61af66fc99e Initial load
duke
parents:
diff changeset
39 /* */
a61af66fc99e Initial load
duke
parents:
diff changeset
40 /* Should you use GrowableArrays to contain handles you must be certain */
a61af66fc99e Initial load
duke
parents:
diff changeset
41 /* the the GrowableArray does not outlive the HandleMark that contains */
a61af66fc99e Initial load
duke
parents:
diff changeset
42 /* the handles. Since GrowableArrays are typically resource allocated */
a61af66fc99e Initial load
duke
parents:
diff changeset
43 /* the following is an example of INCORRECT CODE, */
a61af66fc99e Initial load
duke
parents:
diff changeset
44 /* */
a61af66fc99e Initial load
duke
parents:
diff changeset
45 /* ResourceMark rm; */
a61af66fc99e Initial load
duke
parents:
diff changeset
46 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
a61af66fc99e Initial load
duke
parents:
diff changeset
47 /* if (blah) { */
a61af66fc99e Initial load
duke
parents:
diff changeset
48 /* while (...) { */
a61af66fc99e Initial load
duke
parents:
diff changeset
49 /* HandleMark hm; */
a61af66fc99e Initial load
duke
parents:
diff changeset
50 /* ... */
a61af66fc99e Initial load
duke
parents:
diff changeset
51 /* Handle h(THREAD, some_oop); */
a61af66fc99e Initial load
duke
parents:
diff changeset
52 /* arr->append(h); */
a61af66fc99e Initial load
duke
parents:
diff changeset
53 /* } */
a61af66fc99e Initial load
duke
parents:
diff changeset
54 /* } */
a61af66fc99e Initial load
duke
parents:
diff changeset
55 /* if (arr->length() != 0 ) { */
a61af66fc99e Initial load
duke
parents:
diff changeset
56 /* oop bad_oop = arr->at(0)(); // Handle is BAD HERE. */
a61af66fc99e Initial load
duke
parents:
diff changeset
57 /* ... */
a61af66fc99e Initial load
duke
parents:
diff changeset
58 /* } */
a61af66fc99e Initial load
duke
parents:
diff changeset
59 /* */
a61af66fc99e Initial load
duke
parents:
diff changeset
60 /* If the GrowableArrays you are creating is C_Heap allocated then it */
a61af66fc99e Initial load
duke
parents:
diff changeset
61 /* hould not old handles since the handles could trivially try and */
a61af66fc99e Initial load
duke
parents:
diff changeset
62 /* outlive their HandleMark. In some situations you might need to do */
a61af66fc99e Initial load
duke
parents:
diff changeset
63 /* this and it would be legal but be very careful and see if you can do */
a61af66fc99e Initial load
duke
parents:
diff changeset
64 /* the code in some other manner. */
a61af66fc99e Initial load
duke
parents:
diff changeset
65 /* */
a61af66fc99e Initial load
duke
parents:
diff changeset
66 /*************************************************************************/
a61af66fc99e Initial load
duke
parents:
diff changeset
67
a61af66fc99e Initial load
duke
parents:
diff changeset
68 // To call default constructor the placement operator new() is used.
a61af66fc99e Initial load
duke
parents:
diff changeset
69 // It should be empty (it only returns the passed void* pointer).
a61af66fc99e Initial load
duke
parents:
diff changeset
70 // The definition of placement operator new(size_t, void*) in the <new>.
a61af66fc99e Initial load
duke
parents:
diff changeset
71
a61af66fc99e Initial load
duke
parents:
diff changeset
72 #include <new>
a61af66fc99e Initial load
duke
parents:
diff changeset
73
a61af66fc99e Initial load
duke
parents:
diff changeset
74 // Need the correct linkage to call qsort without warnings
a61af66fc99e Initial load
duke
parents:
diff changeset
75 extern "C" {
a61af66fc99e Initial load
duke
parents:
diff changeset
76 typedef int (*_sort_Fn)(const void *, const void *);
a61af66fc99e Initial load
duke
parents:
diff changeset
77 }
a61af66fc99e Initial load
duke
parents:
diff changeset
78
a61af66fc99e Initial load
duke
parents:
diff changeset
79 class GenericGrowableArray : public ResourceObj {
3939
f6f3bb0ee072 7088955: add C2 IR support to the SA
never
parents: 1972
diff changeset
80 friend class VMStructs;
f6f3bb0ee072 7088955: add C2 IR support to the SA
never
parents: 1972
diff changeset
81
0
a61af66fc99e Initial load
duke
parents:
diff changeset
82 protected:
a61af66fc99e Initial load
duke
parents:
diff changeset
83 int _len; // current length
a61af66fc99e Initial load
duke
parents:
diff changeset
84 int _max; // maximum length
a61af66fc99e Initial load
duke
parents:
diff changeset
85 Arena* _arena; // Indicates where allocation occurs:
a61af66fc99e Initial load
duke
parents:
diff changeset
86 // 0 means default ResourceArea
a61af66fc99e Initial load
duke
parents:
diff changeset
87 // 1 means on C heap
a61af66fc99e Initial load
duke
parents:
diff changeset
88 // otherwise, allocate in _arena
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
89
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
90 MEMFLAGS _memflags; // memory type if allocation in C heap
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
91
0
a61af66fc99e Initial load
duke
parents:
diff changeset
92 #ifdef ASSERT
a61af66fc99e Initial load
duke
parents:
diff changeset
93 int _nesting; // resource area nesting at creation
a61af66fc99e Initial load
duke
parents:
diff changeset
94 void set_nesting();
a61af66fc99e Initial load
duke
parents:
diff changeset
95 void check_nesting();
a61af66fc99e Initial load
duke
parents:
diff changeset
96 #else
a61af66fc99e Initial load
duke
parents:
diff changeset
97 #define set_nesting();
a61af66fc99e Initial load
duke
parents:
diff changeset
98 #define check_nesting();
a61af66fc99e Initial load
duke
parents:
diff changeset
99 #endif
a61af66fc99e Initial load
duke
parents:
diff changeset
100
a61af66fc99e Initial load
duke
parents:
diff changeset
101 // Where are we going to allocate memory?
a61af66fc99e Initial load
duke
parents:
diff changeset
102 bool on_C_heap() { return _arena == (Arena*)1; }
a61af66fc99e Initial load
duke
parents:
diff changeset
103 bool on_stack () { return _arena == NULL; }
a61af66fc99e Initial load
duke
parents:
diff changeset
104 bool on_arena () { return _arena > (Arena*)1; }
a61af66fc99e Initial load
duke
parents:
diff changeset
105
a61af66fc99e Initial load
duke
parents:
diff changeset
106 // This GA will use the resource stack for storage if c_heap==false,
a61af66fc99e Initial load
duke
parents:
diff changeset
107 // Else it will use the C heap. Use clear_and_deallocate to avoid leaks.
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
108 GenericGrowableArray(int initial_size, int initial_len, bool c_heap, MEMFLAGS flags = mtNone) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
109 _len = initial_len;
a61af66fc99e Initial load
duke
parents:
diff changeset
110 _max = initial_size;
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
111 _memflags = flags;
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
112
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
113 // memory type has to be specified for C heap allocation
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
114 assert(!(c_heap && flags == mtNone), "memory type not specified for C heap object");
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
115
0
a61af66fc99e Initial load
duke
parents:
diff changeset
116 assert(_len >= 0 && _len <= _max, "initial_len too big");
a61af66fc99e Initial load
duke
parents:
diff changeset
117 _arena = (c_heap ? (Arena*)1 : NULL);
a61af66fc99e Initial load
duke
parents:
diff changeset
118 set_nesting();
1685
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
119 assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are");
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
120 assert(!on_stack() ||
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
121 (allocated_on_res_area() || allocated_on_stack()),
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
122 "growable array must be on stack if elements are not on arena and not on C heap");
0
a61af66fc99e Initial load
duke
parents:
diff changeset
123 }
a61af66fc99e Initial load
duke
parents:
diff changeset
124
a61af66fc99e Initial load
duke
parents:
diff changeset
125 // This GA will use the given arena for storage.
a61af66fc99e Initial load
duke
parents:
diff changeset
126 // Consider using new(arena) GrowableArray<T> to allocate the header.
a61af66fc99e Initial load
duke
parents:
diff changeset
127 GenericGrowableArray(Arena* arena, int initial_size, int initial_len) {
a61af66fc99e Initial load
duke
parents:
diff changeset
128 _len = initial_len;
a61af66fc99e Initial load
duke
parents:
diff changeset
129 _max = initial_size;
a61af66fc99e Initial load
duke
parents:
diff changeset
130 assert(_len >= 0 && _len <= _max, "initial_len too big");
a61af66fc99e Initial load
duke
parents:
diff changeset
131 _arena = arena;
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
132 _memflags = mtNone;
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
133
0
a61af66fc99e Initial load
duke
parents:
diff changeset
134 assert(on_arena(), "arena has taken on reserved value 0 or 1");
1685
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
135 // Relax next assert to allow object allocation on resource area,
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
136 // on stack or embedded into an other object.
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
137 assert(allocated_on_arena() || allocated_on_stack(),
0e35fa8ebccd 6973963: SEGV in ciBlock::start_bci() with EA
kvn
parents: 1552
diff changeset
138 "growable array must be on arena or on stack if elements are on arena");
0
a61af66fc99e Initial load
duke
parents:
diff changeset
139 }
a61af66fc99e Initial load
duke
parents:
diff changeset
140
a61af66fc99e Initial load
duke
parents:
diff changeset
141 void* raw_allocate(int elementSize);
432
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
142
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
143 // some uses pass the Thread explicitly for speed (4990299 tuning)
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
144 void* raw_allocate(Thread* thread, int elementSize) {
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
145 assert(on_stack(), "fast ResourceObj path only");
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
146 return (void*)resource_allocate_bytes(thread, elementSize * _max);
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
147 }
0
a61af66fc99e Initial load
duke
parents:
diff changeset
148 };
a61af66fc99e Initial load
duke
parents:
diff changeset
149
a61af66fc99e Initial load
duke
parents:
diff changeset
150 template<class E> class GrowableArray : public GenericGrowableArray {
3939
f6f3bb0ee072 7088955: add C2 IR support to the SA
never
parents: 1972
diff changeset
151 friend class VMStructs;
f6f3bb0ee072 7088955: add C2 IR support to the SA
never
parents: 1972
diff changeset
152
0
a61af66fc99e Initial load
duke
parents:
diff changeset
153 private:
a61af66fc99e Initial load
duke
parents:
diff changeset
154 E* _data; // data array
a61af66fc99e Initial load
duke
parents:
diff changeset
155
a61af66fc99e Initial load
duke
parents:
diff changeset
156 void grow(int j);
a61af66fc99e Initial load
duke
parents:
diff changeset
157 void raw_at_put_grow(int i, const E& p, const E& fill);
a61af66fc99e Initial load
duke
parents:
diff changeset
158 void clear_and_deallocate();
a61af66fc99e Initial load
duke
parents:
diff changeset
159 public:
432
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
160 GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
161 _data = (E*)raw_allocate(thread, sizeof(E));
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
162 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
163 }
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
164
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
165 GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
166 : GenericGrowableArray(initial_size, 0, C_heap, F) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
167 _data = (E*)raw_allocate(sizeof(E));
a61af66fc99e Initial load
duke
parents:
diff changeset
168 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
a61af66fc99e Initial load
duke
parents:
diff changeset
169 }
a61af66fc99e Initial load
duke
parents:
diff changeset
170
6197
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
171 GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
d2a62e0f25eb 6995781: Native Memory Tracking (Phase 1)
zgu
parents: 5948
diff changeset
172 : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
173 _data = (E*)raw_allocate(sizeof(E));
a61af66fc99e Initial load
duke
parents:
diff changeset
174 int i = 0;
a61af66fc99e Initial load
duke
parents:
diff changeset
175 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
a61af66fc99e Initial load
duke
parents:
diff changeset
176 for (; i < _max; i++) ::new ((void*)&_data[i]) E();
a61af66fc99e Initial load
duke
parents:
diff changeset
177 }
a61af66fc99e Initial load
duke
parents:
diff changeset
178
a61af66fc99e Initial load
duke
parents:
diff changeset
179 GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
a61af66fc99e Initial load
duke
parents:
diff changeset
180 _data = (E*)raw_allocate(sizeof(E));
a61af66fc99e Initial load
duke
parents:
diff changeset
181 int i = 0;
a61af66fc99e Initial load
duke
parents:
diff changeset
182 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
a61af66fc99e Initial load
duke
parents:
diff changeset
183 for (; i < _max; i++) ::new ((void*)&_data[i]) E();
a61af66fc99e Initial load
duke
parents:
diff changeset
184 }
a61af66fc99e Initial load
duke
parents:
diff changeset
185
a61af66fc99e Initial load
duke
parents:
diff changeset
186 GrowableArray() : GenericGrowableArray(2, 0, false) {
a61af66fc99e Initial load
duke
parents:
diff changeset
187 _data = (E*)raw_allocate(sizeof(E));
a61af66fc99e Initial load
duke
parents:
diff changeset
188 ::new ((void*)&_data[0]) E();
a61af66fc99e Initial load
duke
parents:
diff changeset
189 ::new ((void*)&_data[1]) E();
a61af66fc99e Initial load
duke
parents:
diff changeset
190 }
a61af66fc99e Initial load
duke
parents:
diff changeset
191
a61af66fc99e Initial load
duke
parents:
diff changeset
192 // Does nothing for resource and arena objects
a61af66fc99e Initial load
duke
parents:
diff changeset
193 ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); }
a61af66fc99e Initial load
duke
parents:
diff changeset
194
a61af66fc99e Initial load
duke
parents:
diff changeset
195 void clear() { _len = 0; }
a61af66fc99e Initial load
duke
parents:
diff changeset
196 int length() const { return _len; }
a61af66fc99e Initial load
duke
parents:
diff changeset
197 void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; }
a61af66fc99e Initial load
duke
parents:
diff changeset
198 bool is_empty() const { return _len == 0; }
a61af66fc99e Initial load
duke
parents:
diff changeset
199 bool is_nonempty() const { return _len != 0; }
a61af66fc99e Initial load
duke
parents:
diff changeset
200 bool is_full() const { return _len == _max; }
a61af66fc99e Initial load
duke
parents:
diff changeset
201 DEBUG_ONLY(E* data_addr() const { return _data; })
a61af66fc99e Initial load
duke
parents:
diff changeset
202
a61af66fc99e Initial load
duke
parents:
diff changeset
203 void print();
a61af66fc99e Initial load
duke
parents:
diff changeset
204
432
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
205 int append(const E& elem) {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
206 check_nesting();
a61af66fc99e Initial load
duke
parents:
diff changeset
207 if (_len == _max) grow(_len);
432
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
208 int idx = _len++;
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
209 _data[idx] = elem;
275a3b7ff0d6 6770949: minor tweaks before 6655638
jrose
parents: 0
diff changeset
210 return idx;
0
a61af66fc99e Initial load
duke
parents:
diff changeset
211 }
a61af66fc99e Initial load
duke
parents:
diff changeset
212
5948
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
213 bool append_if_missing(const E& elem) {
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
214 // Returns TRUE if elem is added.
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
215 bool missed = !contains(elem);
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
216 if (missed) append(elem);
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
217 return missed;
0
a61af66fc99e Initial load
duke
parents:
diff changeset
218 }
a61af66fc99e Initial load
duke
parents:
diff changeset
219
6934
4735d2c84362 7200776: Implement default methods in interfaces
kamg
parents: 6725
diff changeset
220 E& at(int i) {
4735d2c84362 7200776: Implement default methods in interfaces
kamg
parents: 6725
diff changeset
221 assert(0 <= i && i < _len, "illegal index");
4735d2c84362 7200776: Implement default methods in interfaces
kamg
parents: 6725
diff changeset
222 return _data[i];
4735d2c84362 7200776: Implement default methods in interfaces
kamg
parents: 6725
diff changeset
223 }
4735d2c84362 7200776: Implement default methods in interfaces
kamg
parents: 6725
diff changeset
224
4735d2c84362 7200776: Implement default methods in interfaces
kamg
parents: 6725
diff changeset
225 E const& at(int i) const {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
226 assert(0 <= i && i < _len, "illegal index");
a61af66fc99e Initial load
duke
parents:
diff changeset
227 return _data[i];
a61af66fc99e Initial load
duke
parents:
diff changeset
228 }
a61af66fc99e Initial load
duke
parents:
diff changeset
229
a61af66fc99e Initial load
duke
parents:
diff changeset
230 E* adr_at(int i) const {
a61af66fc99e Initial load
duke
parents:
diff changeset
231 assert(0 <= i && i < _len, "illegal index");
a61af66fc99e Initial load
duke
parents:
diff changeset
232 return &_data[i];
a61af66fc99e Initial load
duke
parents:
diff changeset
233 }
a61af66fc99e Initial load
duke
parents:
diff changeset
234
a61af66fc99e Initial load
duke
parents:
diff changeset
235 E first() const {
a61af66fc99e Initial load
duke
parents:
diff changeset
236 assert(_len > 0, "empty list");
a61af66fc99e Initial load
duke
parents:
diff changeset
237 return _data[0];
a61af66fc99e Initial load
duke
parents:
diff changeset
238 }
a61af66fc99e Initial load
duke
parents:
diff changeset
239
a61af66fc99e Initial load
duke
parents:
diff changeset
240 E top() const {
a61af66fc99e Initial load
duke
parents:
diff changeset
241 assert(_len > 0, "empty list");
a61af66fc99e Initial load
duke
parents:
diff changeset
242 return _data[_len-1];
a61af66fc99e Initial load
duke
parents:
diff changeset
243 }
a61af66fc99e Initial load
duke
parents:
diff changeset
244
a61af66fc99e Initial load
duke
parents:
diff changeset
245 void push(const E& elem) { append(elem); }
a61af66fc99e Initial load
duke
parents:
diff changeset
246
a61af66fc99e Initial load
duke
parents:
diff changeset
247 E pop() {
a61af66fc99e Initial load
duke
parents:
diff changeset
248 assert(_len > 0, "empty list");
a61af66fc99e Initial load
duke
parents:
diff changeset
249 return _data[--_len];
a61af66fc99e Initial load
duke
parents:
diff changeset
250 }
a61af66fc99e Initial load
duke
parents:
diff changeset
251
a61af66fc99e Initial load
duke
parents:
diff changeset
252 void at_put(int i, const E& elem) {
a61af66fc99e Initial load
duke
parents:
diff changeset
253 assert(0 <= i && i < _len, "illegal index");
a61af66fc99e Initial load
duke
parents:
diff changeset
254 _data[i] = elem;
a61af66fc99e Initial load
duke
parents:
diff changeset
255 }
a61af66fc99e Initial load
duke
parents:
diff changeset
256
a61af66fc99e Initial load
duke
parents:
diff changeset
257 E at_grow(int i, const E& fill = E()) {
a61af66fc99e Initial load
duke
parents:
diff changeset
258 assert(0 <= i, "negative index");
a61af66fc99e Initial load
duke
parents:
diff changeset
259 check_nesting();
a61af66fc99e Initial load
duke
parents:
diff changeset
260 if (i >= _len) {
a61af66fc99e Initial load
duke
parents:
diff changeset
261 if (i >= _max) grow(i);
a61af66fc99e Initial load
duke
parents:
diff changeset
262 for (int j = _len; j <= i; j++)
a61af66fc99e Initial load
duke
parents:
diff changeset
263 _data[j] = fill;
a61af66fc99e Initial load
duke
parents:
diff changeset
264 _len = i+1;
a61af66fc99e Initial load
duke
parents:
diff changeset
265 }
a61af66fc99e Initial load
duke
parents:
diff changeset
266 return _data[i];
a61af66fc99e Initial load
duke
parents:
diff changeset
267 }
a61af66fc99e Initial load
duke
parents:
diff changeset
268
a61af66fc99e Initial load
duke
parents:
diff changeset
269 void at_put_grow(int i, const E& elem, const E& fill = E()) {
a61af66fc99e Initial load
duke
parents:
diff changeset
270 assert(0 <= i, "negative index");
a61af66fc99e Initial load
duke
parents:
diff changeset
271 check_nesting();
a61af66fc99e Initial load
duke
parents:
diff changeset
272 raw_at_put_grow(i, elem, fill);
a61af66fc99e Initial load
duke
parents:
diff changeset
273 }
a61af66fc99e Initial load
duke
parents:
diff changeset
274
a61af66fc99e Initial load
duke
parents:
diff changeset
275 bool contains(const E& elem) const {
a61af66fc99e Initial load
duke
parents:
diff changeset
276 for (int i = 0; i < _len; i++) {
a61af66fc99e Initial load
duke
parents:
diff changeset
277 if (_data[i] == elem) return true;
a61af66fc99e Initial load
duke
parents:
diff changeset
278 }
a61af66fc99e Initial load
duke
parents:
diff changeset
279 return false;
a61af66fc99e Initial load
duke
parents:
diff changeset
280 }
a61af66fc99e Initial load
duke
parents:
diff changeset
281
a61af66fc99e Initial load
duke
parents:
diff changeset
282 int find(const E& elem) const {
a61af66fc99e Initial load
duke
parents:
diff changeset
283 for (int i = 0; i < _len; i++) {
a61af66fc99e Initial load
duke
parents:
diff changeset
284 if (_data[i] == elem) return i;
a61af66fc99e Initial load
duke
parents:
diff changeset
285 }
a61af66fc99e Initial load
duke
parents:
diff changeset
286 return -1;
a61af66fc99e Initial load
duke
parents:
diff changeset
287 }
a61af66fc99e Initial load
duke
parents:
diff changeset
288
6725
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
289 int find_from_end(const E& elem) const {
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
290 for (int i = _len-1; i >= 0; i--) {
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
291 if (_data[i] == elem) return i;
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
292 }
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
293 return -1;
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
294 }
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
295
0
a61af66fc99e Initial load
duke
parents:
diff changeset
296 int find(void* token, bool f(void*, E)) const {
a61af66fc99e Initial load
duke
parents:
diff changeset
297 for (int i = 0; i < _len; i++) {
a61af66fc99e Initial load
duke
parents:
diff changeset
298 if (f(token, _data[i])) return i;
a61af66fc99e Initial load
duke
parents:
diff changeset
299 }
a61af66fc99e Initial load
duke
parents:
diff changeset
300 return -1;
a61af66fc99e Initial load
duke
parents:
diff changeset
301 }
a61af66fc99e Initial load
duke
parents:
diff changeset
302
6725
da91efe96a93 6964458: Reimplement class meta-data storage to use native memory
coleenp
parents: 6197
diff changeset
303 int find_from_end(void* token, bool f(void*, E)) const {
0
a61af66fc99e Initial load
duke
parents:
diff changeset
304 // start at the end of the array
a61af66fc99e Initial load
duke
parents:
diff changeset
305 for (int i = _len-1; i >= 0; i--) {
a61af66fc99e Initial load
duke
parents:
diff changeset
306 if (f(token, _data[i])) return i;
a61af66fc99e Initial load
duke
parents:
diff changeset
307 }
a61af66fc99e Initial load
duke
parents:
diff changeset
308 return -1;
a61af66fc99e Initial load
duke
parents:
diff changeset
309 }
a61af66fc99e Initial load
duke
parents:
diff changeset
310
a61af66fc99e Initial load
duke
parents:
diff changeset
311 void remove(const E& elem) {
a61af66fc99e Initial load
duke
parents:
diff changeset
312 for (int i = 0; i < _len; i++) {
a61af66fc99e Initial load
duke
parents:
diff changeset
313 if (_data[i] == elem) {
a61af66fc99e Initial load
duke
parents:
diff changeset
314 for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j];
a61af66fc99e Initial load
duke
parents:
diff changeset
315 _len--;
a61af66fc99e Initial load
duke
parents:
diff changeset
316 return;
a61af66fc99e Initial load
duke
parents:
diff changeset
317 }
a61af66fc99e Initial load
duke
parents:
diff changeset
318 }
a61af66fc99e Initial load
duke
parents:
diff changeset
319 ShouldNotReachHere();
a61af66fc99e Initial load
duke
parents:
diff changeset
320 }
a61af66fc99e Initial load
duke
parents:
diff changeset
321
5948
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
322 // The order is preserved.
0
a61af66fc99e Initial load
duke
parents:
diff changeset
323 void remove_at(int index) {
a61af66fc99e Initial load
duke
parents:
diff changeset
324 assert(0 <= index && index < _len, "illegal index");
a61af66fc99e Initial load
duke
parents:
diff changeset
325 for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j];
a61af66fc99e Initial load
duke
parents:
diff changeset
326 _len--;
a61af66fc99e Initial load
duke
parents:
diff changeset
327 }
a61af66fc99e Initial load
duke
parents:
diff changeset
328
5948
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
329 // The order is changed.
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
330 void delete_at(int index) {
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
331 assert(0 <= index && index < _len, "illegal index");
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
332 if (index < --_len) {
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
333 // Replace removed element with last one.
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
334 _data[index] = _data[_len];
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
335 }
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
336 }
ee138854b3a6 7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents: 3939
diff changeset
337
1080
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
338 // inserts the given element before the element at index i
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
339 void insert_before(const int idx, const E& elem) {
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
340 check_nesting();
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
341 if (_len == _max) grow(_len);
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
342 for (int j = _len - 1; j >= idx; j--) {
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
343 _data[j + 1] = _data[j];
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
344 }
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
345 _len++;
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
346 _data[idx] = elem;
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
347 }
7c57aead6d3e 6892658: C2 should optimize some stringbuilder patterns
never
parents: 470
diff changeset
348
0
a61af66fc99e Initial load
duke
parents:
diff changeset
349 void appendAll(const GrowableArray<E>* l) {
a61af66fc99e Initial load
duke
parents:
diff changeset
350 for (int i = 0; i < l->_len; i++) {
a61af66fc99e Initial load
duke
parents:
diff changeset
351 raw_at_put_grow(_len, l->_data[i], 0);
a61af66fc99e Initial load
duke
parents:
diff changeset
352 }
a61af66fc99e Initial load
duke
parents:
diff changeset
353 }
a61af66fc99e Initial load
duke
parents:
diff changeset
354
a61af66fc99e Initial load
duke
parents:
diff changeset
355 void sort(int f(E*,E*)) {
a61af66fc99e Initial load
duke
parents:
diff changeset
356 qsort(_data, length(), sizeof(E), (_sort_Fn)f);
a61af66fc99e Initial load
duke
parents:
diff changeset
357 }
a61af66fc99e Initial load
duke
parents:
diff changeset
358 // sort by fixed-stride sub arrays:
a61af66fc99e Initial load
duke
parents:
diff changeset
359 void sort(int f(E*,E*), int stride) {
a61af66fc99e Initial load
duke
parents:
diff changeset
360 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
a61af66fc99e Initial load
duke
parents:
diff changeset
361 }
a61af66fc99e Initial load
duke
parents:
diff changeset
362 };
a61af66fc99e Initial load
duke
parents:
diff changeset
363
a61af66fc99e Initial load
duke
parents:
diff changeset
364 // Global GrowableArray methods (one instance in the library per each 'E' type).
a61af66fc99e Initial load
duke
parents:
diff changeset
365
a61af66fc99e Initial load
duke
parents:
diff changeset
366 template<class E> void GrowableArray<E>::grow(int j) {
a61af66fc99e Initial load
duke
parents:
diff changeset
367 // grow the array by doubling its size (amortized growth)
a61af66fc99e Initial load
duke
parents:
diff changeset
368 int old_max = _max;
a61af66fc99e Initial load
duke
parents:
diff changeset
369 if (_max == 0) _max = 1; // prevent endless loop
a61af66fc99e Initial load
duke
parents:
diff changeset
370 while (j >= _max) _max = _max*2;
a61af66fc99e Initial load
duke
parents:
diff changeset
371 // j < _max
a61af66fc99e Initial load
duke
parents:
diff changeset
372 E* newData = (E*)raw_allocate(sizeof(E));
a61af66fc99e Initial load
duke
parents:
diff changeset
373 int i = 0;
a61af66fc99e Initial load
duke
parents:
diff changeset
374 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
a61af66fc99e Initial load
duke
parents:
diff changeset
375 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E();
a61af66fc99e Initial load
duke
parents:
diff changeset
376 for (i = 0; i < old_max; i++) _data[i].~E();
a61af66fc99e Initial load
duke
parents:
diff changeset
377 if (on_C_heap() && _data != NULL) {
a61af66fc99e Initial load
duke
parents:
diff changeset
378 FreeHeap(_data);
a61af66fc99e Initial load
duke
parents:
diff changeset
379 }
a61af66fc99e Initial load
duke
parents:
diff changeset
380 _data = newData;
a61af66fc99e Initial load
duke
parents:
diff changeset
381 }
a61af66fc99e Initial load
duke
parents:
diff changeset
382
a61af66fc99e Initial load
duke
parents:
diff changeset
383 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
a61af66fc99e Initial load
duke
parents:
diff changeset
384 if (i >= _len) {
a61af66fc99e Initial load
duke
parents:
diff changeset
385 if (i >= _max) grow(i);
a61af66fc99e Initial load
duke
parents:
diff changeset
386 for (int j = _len; j < i; j++)
a61af66fc99e Initial load
duke
parents:
diff changeset
387 _data[j] = fill;
a61af66fc99e Initial load
duke
parents:
diff changeset
388 _len = i+1;
a61af66fc99e Initial load
duke
parents:
diff changeset
389 }
a61af66fc99e Initial load
duke
parents:
diff changeset
390 _data[i] = p;
a61af66fc99e Initial load
duke
parents:
diff changeset
391 }
a61af66fc99e Initial load
duke
parents:
diff changeset
392
a61af66fc99e Initial load
duke
parents:
diff changeset
393 // This function clears and deallocate the data in the growable array that
a61af66fc99e Initial load
duke
parents:
diff changeset
394 // has been allocated on the C heap. It's not public - called by the
a61af66fc99e Initial load
duke
parents:
diff changeset
395 // destructor.
a61af66fc99e Initial load
duke
parents:
diff changeset
396 template<class E> void GrowableArray<E>::clear_and_deallocate() {
a61af66fc99e Initial load
duke
parents:
diff changeset
397 assert(on_C_heap(),
a61af66fc99e Initial load
duke
parents:
diff changeset
398 "clear_and_deallocate should only be called when on C heap");
a61af66fc99e Initial load
duke
parents:
diff changeset
399 clear();
a61af66fc99e Initial load
duke
parents:
diff changeset
400 if (_data != NULL) {
a61af66fc99e Initial load
duke
parents:
diff changeset
401 for (int i = 0; i < _max; i++) _data[i].~E();
a61af66fc99e Initial load
duke
parents:
diff changeset
402 FreeHeap(_data);
a61af66fc99e Initial load
duke
parents:
diff changeset
403 _data = NULL;
a61af66fc99e Initial load
duke
parents:
diff changeset
404 }
a61af66fc99e Initial load
duke
parents:
diff changeset
405 }
a61af66fc99e Initial load
duke
parents:
diff changeset
406
a61af66fc99e Initial load
duke
parents:
diff changeset
407 template<class E> void GrowableArray<E>::print() {
a61af66fc99e Initial load
duke
parents:
diff changeset
408 tty->print("Growable Array " INTPTR_FORMAT, this);
a61af66fc99e Initial load
duke
parents:
diff changeset
409 tty->print(": length %ld (_max %ld) { ", _len, _max);
a61af66fc99e Initial load
duke
parents:
diff changeset
410 for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
a61af66fc99e Initial load
duke
parents:
diff changeset
411 tty->print("}\n");
a61af66fc99e Initial load
duke
parents:
diff changeset
412 }
1972
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
413
f95d63e2154a 6989984: Use standard include model for Hospot
stefank
parents: 1685
diff changeset
414 #endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP