Mercurial > hg > truffle
annotate src/share/vm/utilities/growableArray.hpp @ 6862:8a5ea0a9ccc4
7127708: G1: change task num types from int to uint in concurrent mark
Summary: Change the type of various task num fields, parameters etc to unsigned and rename them to be more consistent with the other collectors. Code changes were also reviewed by Vitaly Davidovich.
Reviewed-by: johnc
Contributed-by: Kaushik Srenevasan <kaushik@twitter.com>
author | johnc |
---|---|
date | Sat, 06 Oct 2012 01:17:44 -0700 |
parents | da91efe96a93 |
children | 4735d2c84362 |
rev | line source |
---|---|
0 | 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 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
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 | 22 * |
23 */ | |
24 | |
1972 | 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 | |
0 | 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); */ | |
53 /* } */ | |
54 /* } */ | |
55 /* if (arr->length() != 0 ) { */ | |
56 /* oop bad_oop = arr->at(0)(); // Handle is BAD HERE. */ | |
57 /* ... */ | |
58 /* } */ | |
59 /* */ | |
60 /* If the GrowableArrays you are creating is C_Heap allocated then it */ | |
61 /* hould not old handles since the handles could trivially try and */ | |
62 /* outlive their HandleMark. In some situations you might need to do */ | |
63 /* this and it would be legal but be very careful and see if you can do */ | |
64 /* the code in some other manner. */ | |
65 /* */ | |
66 /*************************************************************************/ | |
67 | |
68 // To call default constructor the placement operator new() is used. | |
69 // It should be empty (it only returns the passed void* pointer). | |
70 // The definition of placement operator new(size_t, void*) in the <new>. | |
71 | |
72 #include <new> | |
73 | |
74 // Need the correct linkage to call qsort without warnings | |
75 extern "C" { | |
76 typedef int (*_sort_Fn)(const void *, const void *); | |
77 } | |
78 | |
79 class GenericGrowableArray : public ResourceObj { | |
3939 | 80 friend class VMStructs; |
81 | |
0 | 82 protected: |
83 int _len; // current length | |
84 int _max; // maximum length | |
85 Arena* _arena; // Indicates where allocation occurs: | |
86 // 0 means default ResourceArea | |
87 // 1 means on C heap | |
88 // otherwise, allocate in _arena | |
6197 | 89 |
90 MEMFLAGS _memflags; // memory type if allocation in C heap | |
91 | |
0 | 92 #ifdef ASSERT |
93 int _nesting; // resource area nesting at creation | |
94 void set_nesting(); | |
95 void check_nesting(); | |
96 #else | |
97 #define set_nesting(); | |
98 #define check_nesting(); | |
99 #endif | |
100 | |
101 // Where are we going to allocate memory? | |
102 bool on_C_heap() { return _arena == (Arena*)1; } | |
103 bool on_stack () { return _arena == NULL; } | |
104 bool on_arena () { return _arena > (Arena*)1; } | |
105 | |
106 // This GA will use the resource stack for storage if c_heap==false, | |
107 // Else it will use the C heap. Use clear_and_deallocate to avoid leaks. | |
6197 | 108 GenericGrowableArray(int initial_size, int initial_len, bool c_heap, MEMFLAGS flags = mtNone) { |
0 | 109 _len = initial_len; |
110 _max = initial_size; | |
6197 | 111 _memflags = flags; |
112 | |
113 // memory type has to be specified for C heap allocation | |
114 assert(!(c_heap && flags == mtNone), "memory type not specified for C heap object"); | |
115 | |
0 | 116 assert(_len >= 0 && _len <= _max, "initial_len too big"); |
117 _arena = (c_heap ? (Arena*)1 : NULL); | |
118 set_nesting(); | |
1685 | 119 assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are"); |
120 assert(!on_stack() || | |
121 (allocated_on_res_area() || allocated_on_stack()), | |
122 "growable array must be on stack if elements are not on arena and not on C heap"); | |
0 | 123 } |
124 | |
125 // This GA will use the given arena for storage. | |
126 // Consider using new(arena) GrowableArray<T> to allocate the header. | |
127 GenericGrowableArray(Arena* arena, int initial_size, int initial_len) { | |
128 _len = initial_len; | |
129 _max = initial_size; | |
130 assert(_len >= 0 && _len <= _max, "initial_len too big"); | |
131 _arena = arena; | |
6197 | 132 _memflags = mtNone; |
133 | |
0 | 134 assert(on_arena(), "arena has taken on reserved value 0 or 1"); |
1685 | 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"); | |
0 | 139 } |
140 | |
141 void* raw_allocate(int elementSize); | |
432 | 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 } | |
0 | 148 }; |
149 | |
150 template<class E> class GrowableArray : public GenericGrowableArray { | |
3939 | 151 friend class VMStructs; |
152 | |
0 | 153 private: |
154 E* _data; // data array | |
155 | |
156 void grow(int j); | |
157 void raw_at_put_grow(int i, const E& p, const E& fill); | |
158 void clear_and_deallocate(); | |
159 public: | |
432 | 160 GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) { |
161 _data = (E*)raw_allocate(thread, sizeof(E)); | |
162 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
163 } | |
164 | |
6197 | 165 GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal) |
166 : GenericGrowableArray(initial_size, 0, C_heap, F) { | |
0 | 167 _data = (E*)raw_allocate(sizeof(E)); |
168 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
169 } | |
170 | |
6197 | 171 GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal) |
172 : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) { | |
0 | 173 _data = (E*)raw_allocate(sizeof(E)); |
174 int i = 0; | |
175 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler); | |
176 for (; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
177 } | |
178 | |
179 GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) { | |
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() : GenericGrowableArray(2, 0, false) { | |
187 _data = (E*)raw_allocate(sizeof(E)); | |
188 ::new ((void*)&_data[0]) E(); | |
189 ::new ((void*)&_data[1]) E(); | |
190 } | |
191 | |
192 // Does nothing for resource and arena objects | |
193 ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); } | |
194 | |
195 void clear() { _len = 0; } | |
196 int length() const { return _len; } | |
197 void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; } | |
198 bool is_empty() const { return _len == 0; } | |
199 bool is_nonempty() const { return _len != 0; } | |
200 bool is_full() const { return _len == _max; } | |
201 DEBUG_ONLY(E* data_addr() const { return _data; }) | |
202 | |
203 void print(); | |
204 | |
432 | 205 int append(const E& elem) { |
0 | 206 check_nesting(); |
207 if (_len == _max) grow(_len); | |
432 | 208 int idx = _len++; |
209 _data[idx] = elem; | |
210 return idx; | |
0 | 211 } |
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 | 218 } |
219 | |
220 E at(int i) const { | |
221 assert(0 <= i && i < _len, "illegal index"); | |
222 return _data[i]; | |
223 } | |
224 | |
225 E* adr_at(int i) const { | |
226 assert(0 <= i && i < _len, "illegal index"); | |
227 return &_data[i]; | |
228 } | |
229 | |
230 E first() const { | |
231 assert(_len > 0, "empty list"); | |
232 return _data[0]; | |
233 } | |
234 | |
235 E top() const { | |
236 assert(_len > 0, "empty list"); | |
237 return _data[_len-1]; | |
238 } | |
239 | |
240 void push(const E& elem) { append(elem); } | |
241 | |
242 E pop() { | |
243 assert(_len > 0, "empty list"); | |
244 return _data[--_len]; | |
245 } | |
246 | |
247 void at_put(int i, const E& elem) { | |
248 assert(0 <= i && i < _len, "illegal index"); | |
249 _data[i] = elem; | |
250 } | |
251 | |
252 E at_grow(int i, const E& fill = E()) { | |
253 assert(0 <= i, "negative index"); | |
254 check_nesting(); | |
255 if (i >= _len) { | |
256 if (i >= _max) grow(i); | |
257 for (int j = _len; j <= i; j++) | |
258 _data[j] = fill; | |
259 _len = i+1; | |
260 } | |
261 return _data[i]; | |
262 } | |
263 | |
264 void at_put_grow(int i, const E& elem, const E& fill = E()) { | |
265 assert(0 <= i, "negative index"); | |
266 check_nesting(); | |
267 raw_at_put_grow(i, elem, fill); | |
268 } | |
269 | |
270 bool contains(const E& elem) const { | |
271 for (int i = 0; i < _len; i++) { | |
272 if (_data[i] == elem) return true; | |
273 } | |
274 return false; | |
275 } | |
276 | |
277 int find(const E& elem) const { | |
278 for (int i = 0; i < _len; i++) { | |
279 if (_data[i] == elem) return i; | |
280 } | |
281 return -1; | |
282 } | |
283 | |
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
284 int find_from_end(const E& elem) const { |
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
285 for (int i = _len-1; i >= 0; i--) { |
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
286 if (_data[i] == elem) return i; |
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
287 } |
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
288 return -1; |
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
289 } |
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
290 |
0 | 291 int find(void* token, bool f(void*, E)) const { |
292 for (int i = 0; i < _len; i++) { | |
293 if (f(token, _data[i])) return i; | |
294 } | |
295 return -1; | |
296 } | |
297 | |
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6197
diff
changeset
|
298 int find_from_end(void* token, bool f(void*, E)) const { |
0 | 299 // start at the end of the array |
300 for (int i = _len-1; i >= 0; i--) { | |
301 if (f(token, _data[i])) return i; | |
302 } | |
303 return -1; | |
304 } | |
305 | |
306 void remove(const E& elem) { | |
307 for (int i = 0; i < _len; i++) { | |
308 if (_data[i] == elem) { | |
309 for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j]; | |
310 _len--; | |
311 return; | |
312 } | |
313 } | |
314 ShouldNotReachHere(); | |
315 } | |
316 | |
5948
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
317 // The order is preserved. |
0 | 318 void remove_at(int index) { |
319 assert(0 <= index && index < _len, "illegal index"); | |
320 for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j]; | |
321 _len--; | |
322 } | |
323 | |
5948
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
324 // The order is changed. |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
325 void delete_at(int index) { |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
326 assert(0 <= index && index < _len, "illegal index"); |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
327 if (index < --_len) { |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
328 // Replace removed element with last one. |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
329 _data[index] = _data[_len]; |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
330 } |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
331 } |
ee138854b3a6
7147744: CTW: assert(false) failed: infinite EA connection graph build
kvn
parents:
3939
diff
changeset
|
332 |
1080
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
333 // inserts the given element before the element at index i |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
334 void insert_before(const int idx, const E& elem) { |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
335 check_nesting(); |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
336 if (_len == _max) grow(_len); |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
337 for (int j = _len - 1; j >= idx; j--) { |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
338 _data[j + 1] = _data[j]; |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
339 } |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
340 _len++; |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
341 _data[idx] = elem; |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
342 } |
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
343 |
0 | 344 void appendAll(const GrowableArray<E>* l) { |
345 for (int i = 0; i < l->_len; i++) { | |
346 raw_at_put_grow(_len, l->_data[i], 0); | |
347 } | |
348 } | |
349 | |
350 void sort(int f(E*,E*)) { | |
351 qsort(_data, length(), sizeof(E), (_sort_Fn)f); | |
352 } | |
353 // sort by fixed-stride sub arrays: | |
354 void sort(int f(E*,E*), int stride) { | |
355 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); | |
356 } | |
357 }; | |
358 | |
359 // Global GrowableArray methods (one instance in the library per each 'E' type). | |
360 | |
361 template<class E> void GrowableArray<E>::grow(int j) { | |
362 // grow the array by doubling its size (amortized growth) | |
363 int old_max = _max; | |
364 if (_max == 0) _max = 1; // prevent endless loop | |
365 while (j >= _max) _max = _max*2; | |
366 // j < _max | |
367 E* newData = (E*)raw_allocate(sizeof(E)); | |
368 int i = 0; | |
369 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]); | |
370 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E(); | |
371 for (i = 0; i < old_max; i++) _data[i].~E(); | |
372 if (on_C_heap() && _data != NULL) { | |
373 FreeHeap(_data); | |
374 } | |
375 _data = newData; | |
376 } | |
377 | |
378 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) { | |
379 if (i >= _len) { | |
380 if (i >= _max) grow(i); | |
381 for (int j = _len; j < i; j++) | |
382 _data[j] = fill; | |
383 _len = i+1; | |
384 } | |
385 _data[i] = p; | |
386 } | |
387 | |
388 // This function clears and deallocate the data in the growable array that | |
389 // has been allocated on the C heap. It's not public - called by the | |
390 // destructor. | |
391 template<class E> void GrowableArray<E>::clear_and_deallocate() { | |
392 assert(on_C_heap(), | |
393 "clear_and_deallocate should only be called when on C heap"); | |
394 clear(); | |
395 if (_data != NULL) { | |
396 for (int i = 0; i < _max; i++) _data[i].~E(); | |
397 FreeHeap(_data); | |
398 _data = NULL; | |
399 } | |
400 } | |
401 | |
402 template<class E> void GrowableArray<E>::print() { | |
403 tty->print("Growable Array " INTPTR_FORMAT, this); | |
404 tty->print(": length %ld (_max %ld) { ", _len, _max); | |
405 for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i])); | |
406 tty->print("}\n"); | |
407 } | |
1972 | 408 |
409 #endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP |