Mercurial > jdk8-mips64-public > hotspot / file revision
src/share/vm/utilities/growableArray.hpp@c96030fff130
src/share/vm/utilities/growableArray.hpp
Thu, 20 Nov 2008 16:56:09 -0800
- author
- ysr
- date
- Thu, 20 Nov 2008 16:56:09 -0800
- changeset 888
- c96030fff130
- parent 867
- 275a3b7ff0d6
- child 905
- ad8c8ca4ab0f
- permissions
- -rw-r--r--
6684579: SoftReference processing can be made more efficient
Summary: For current soft-ref clearing policies, we can decide at marking time if a soft-reference will definitely not be cleared, postponing the decision of whether it will definitely be cleared to the final reference processing phase. This can be especially beneficial in the case of concurrent collectors where the marking is usually concurrent but reference processing is usually not.
Reviewed-by: jmasa
1 /*
2 * Copyright 1997-2005 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
25 // A growable array.
27 /*************************************************************************/
28 /* */
29 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
30 /* */
31 /* Should you use GrowableArrays to contain handles you must be certain */
32 /* the the GrowableArray does not outlive the HandleMark that contains */
33 /* the handles. Since GrowableArrays are typically resource allocated */
34 /* the following is an example of INCORRECT CODE, */
35 /* */
36 /* ResourceMark rm; */
37 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
38 /* if (blah) { */
39 /* while (...) { */
40 /* HandleMark hm; */
41 /* ... */
42 /* Handle h(THREAD, some_oop); */
43 /* arr->append(h); */
44 /* } */
45 /* } */
46 /* if (arr->length() != 0 ) { */
47 /* oop bad_oop = arr->at(0)(); // Handle is BAD HERE. */
48 /* ... */
49 /* } */
50 /* */
51 /* If the GrowableArrays you are creating is C_Heap allocated then it */
52 /* hould not old handles since the handles could trivially try and */
53 /* outlive their HandleMark. In some situations you might need to do */
54 /* this and it would be legal but be very careful and see if you can do */
55 /* the code in some other manner. */
56 /* */
57 /*************************************************************************/
59 // To call default constructor the placement operator new() is used.
60 // It should be empty (it only returns the passed void* pointer).
61 // The definition of placement operator new(size_t, void*) in the <new>.
63 #include <new>
65 // Need the correct linkage to call qsort without warnings
66 extern "C" {
67 typedef int (*_sort_Fn)(const void *, const void *);
68 }
70 class GenericGrowableArray : public ResourceObj {
71 protected:
72 int _len; // current length
73 int _max; // maximum length
74 Arena* _arena; // Indicates where allocation occurs:
75 // 0 means default ResourceArea
76 // 1 means on C heap
77 // otherwise, allocate in _arena
78 #ifdef ASSERT
79 int _nesting; // resource area nesting at creation
80 void set_nesting();
81 void check_nesting();
82 #else
83 #define set_nesting();
84 #define check_nesting();
85 #endif
87 // Where are we going to allocate memory?
88 bool on_C_heap() { return _arena == (Arena*)1; }
89 bool on_stack () { return _arena == NULL; }
90 bool on_arena () { return _arena > (Arena*)1; }
92 // This GA will use the resource stack for storage if c_heap==false,
93 // Else it will use the C heap. Use clear_and_deallocate to avoid leaks.
94 GenericGrowableArray(int initial_size, int initial_len, bool c_heap) {
95 _len = initial_len;
96 _max = initial_size;
97 assert(_len >= 0 && _len <= _max, "initial_len too big");
98 _arena = (c_heap ? (Arena*)1 : NULL);
99 set_nesting();
100 assert(!c_heap || allocated_on_C_heap(), "growable array must be on C heap if elements are");
101 }
103 // This GA will use the given arena for storage.
104 // Consider using new(arena) GrowableArray<T> to allocate the header.
105 GenericGrowableArray(Arena* arena, int initial_size, int initial_len) {
106 _len = initial_len;
107 _max = initial_size;
108 assert(_len >= 0 && _len <= _max, "initial_len too big");
109 _arena = arena;
110 assert(on_arena(), "arena has taken on reserved value 0 or 1");
111 }
113 void* raw_allocate(int elementSize);
115 // some uses pass the Thread explicitly for speed (4990299 tuning)
116 void* raw_allocate(Thread* thread, int elementSize) {
117 assert(on_stack(), "fast ResourceObj path only");
118 return (void*)resource_allocate_bytes(thread, elementSize * _max);
119 }
120 };
122 template<class E> class GrowableArray : public GenericGrowableArray {
123 private:
124 E* _data; // data array
126 void grow(int j);
127 void raw_at_put_grow(int i, const E& p, const E& fill);
128 void clear_and_deallocate();
129 public:
130 GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
131 _data = (E*)raw_allocate(thread, sizeof(E));
132 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
133 }
135 GrowableArray(int initial_size, bool C_heap = false) : GenericGrowableArray(initial_size, 0, C_heap) {
136 _data = (E*)raw_allocate(sizeof(E));
137 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
138 }
140 GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false) : GenericGrowableArray(initial_size, initial_len, C_heap) {
141 _data = (E*)raw_allocate(sizeof(E));
142 int i = 0;
143 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
144 for (; i < _max; i++) ::new ((void*)&_data[i]) E();
145 }
147 GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
148 _data = (E*)raw_allocate(sizeof(E));
149 int i = 0;
150 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
151 for (; i < _max; i++) ::new ((void*)&_data[i]) E();
152 }
154 GrowableArray() : GenericGrowableArray(2, 0, false) {
155 _data = (E*)raw_allocate(sizeof(E));
156 ::new ((void*)&_data[0]) E();
157 ::new ((void*)&_data[1]) E();
158 }
160 // Does nothing for resource and arena objects
161 ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); }
163 void clear() { _len = 0; }
164 int length() const { return _len; }
165 void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; }
166 bool is_empty() const { return _len == 0; }
167 bool is_nonempty() const { return _len != 0; }
168 bool is_full() const { return _len == _max; }
169 DEBUG_ONLY(E* data_addr() const { return _data; })
171 void print();
173 int append(const E& elem) {
174 check_nesting();
175 if (_len == _max) grow(_len);
176 int idx = _len++;
177 _data[idx] = elem;
178 return idx;
179 }
181 void append_if_missing(const E& elem) {
182 if (!contains(elem)) append(elem);
183 }
185 E at(int i) const {
186 assert(0 <= i && i < _len, "illegal index");
187 return _data[i];
188 }
190 E* adr_at(int i) const {
191 assert(0 <= i && i < _len, "illegal index");
192 return &_data[i];
193 }
195 E first() const {
196 assert(_len > 0, "empty list");
197 return _data[0];
198 }
200 E top() const {
201 assert(_len > 0, "empty list");
202 return _data[_len-1];
203 }
205 void push(const E& elem) { append(elem); }
207 E pop() {
208 assert(_len > 0, "empty list");
209 return _data[--_len];
210 }
212 void at_put(int i, const E& elem) {
213 assert(0 <= i && i < _len, "illegal index");
214 _data[i] = elem;
215 }
217 E at_grow(int i, const E& fill = E()) {
218 assert(0 <= i, "negative index");
219 check_nesting();
220 if (i >= _len) {
221 if (i >= _max) grow(i);
222 for (int j = _len; j <= i; j++)
223 _data[j] = fill;
224 _len = i+1;
225 }
226 return _data[i];
227 }
229 void at_put_grow(int i, const E& elem, const E& fill = E()) {
230 assert(0 <= i, "negative index");
231 check_nesting();
232 raw_at_put_grow(i, elem, fill);
233 }
235 bool contains(const E& elem) const {
236 for (int i = 0; i < _len; i++) {
237 if (_data[i] == elem) return true;
238 }
239 return false;
240 }
242 int find(const E& elem) const {
243 for (int i = 0; i < _len; i++) {
244 if (_data[i] == elem) return i;
245 }
246 return -1;
247 }
249 int find(void* token, bool f(void*, E)) const {
250 for (int i = 0; i < _len; i++) {
251 if (f(token, _data[i])) return i;
252 }
253 return -1;
254 }
256 int find_at_end(void* token, bool f(void*, E)) const {
257 // start at the end of the array
258 for (int i = _len-1; i >= 0; i--) {
259 if (f(token, _data[i])) return i;
260 }
261 return -1;
262 }
264 void remove(const E& elem) {
265 for (int i = 0; i < _len; i++) {
266 if (_data[i] == elem) {
267 for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j];
268 _len--;
269 return;
270 }
271 }
272 ShouldNotReachHere();
273 }
275 void remove_at(int index) {
276 assert(0 <= index && index < _len, "illegal index");
277 for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j];
278 _len--;
279 }
281 void appendAll(const GrowableArray<E>* l) {
282 for (int i = 0; i < l->_len; i++) {
283 raw_at_put_grow(_len, l->_data[i], 0);
284 }
285 }
287 void sort(int f(E*,E*)) {
288 qsort(_data, length(), sizeof(E), (_sort_Fn)f);
289 }
290 // sort by fixed-stride sub arrays:
291 void sort(int f(E*,E*), int stride) {
292 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
293 }
294 };
296 // Global GrowableArray methods (one instance in the library per each 'E' type).
298 template<class E> void GrowableArray<E>::grow(int j) {
299 // grow the array by doubling its size (amortized growth)
300 int old_max = _max;
301 if (_max == 0) _max = 1; // prevent endless loop
302 while (j >= _max) _max = _max*2;
303 // j < _max
304 E* newData = (E*)raw_allocate(sizeof(E));
305 int i = 0;
306 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
307 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E();
308 for (i = 0; i < old_max; i++) _data[i].~E();
309 if (on_C_heap() && _data != NULL) {
310 FreeHeap(_data);
311 }
312 _data = newData;
313 }
315 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
316 if (i >= _len) {
317 if (i >= _max) grow(i);
318 for (int j = _len; j < i; j++)
319 _data[j] = fill;
320 _len = i+1;
321 }
322 _data[i] = p;
323 }
325 // This function clears and deallocate the data in the growable array that
326 // has been allocated on the C heap. It's not public - called by the
327 // destructor.
328 template<class E> void GrowableArray<E>::clear_and_deallocate() {
329 assert(on_C_heap(),
330 "clear_and_deallocate should only be called when on C heap");
331 clear();
332 if (_data != NULL) {
333 for (int i = 0; i < _max; i++) _data[i].~E();
334 FreeHeap(_data);
335 _data = NULL;
336 }
337 }
339 template<class E> void GrowableArray<E>::print() {
340 tty->print("Growable Array " INTPTR_FORMAT, this);
341 tty->print(": length %ld (_max %ld) { ", _len, _max);
342 for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
343 tty->print("}\n");
344 }
