Mercurial > hg > graal-compiler
annotate src/share/vm/utilities/growableArray.hpp @ 1941:79d04223b8a5
Added caching for resolved types and resolved fields.
This is crucial, because the local load elimination will lead to wrong results, if field equality (of two RiField objects with the same object and the same RiType) is not given. The caching makes sure that the default equals implementation is sufficient.
| author | Thomas Wuerthinger <wuerthinger@ssw.jku.at> |
|---|---|
| date | Tue, 28 Dec 2010 18:33:26 +0100 |
| parents | 0e35fa8ebccd |
| children | f95d63e2154a |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1080
diff
changeset
|
2 * Copyright (c) 1997, 2008, 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 | |
| 25 // A growable array. | |
| 26 | |
| 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 /*************************************************************************/ | |
| 58 | |
| 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>. | |
| 62 | |
| 63 #include <new> | |
| 64 | |
| 65 // Need the correct linkage to call qsort without warnings | |
| 66 extern "C" { | |
| 67 typedef int (*_sort_Fn)(const void *, const void *); | |
| 68 } | |
| 69 | |
| 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 | |
| 86 | |
| 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; } | |
| 91 | |
| 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(); | |
| 1685 | 100 assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are"); |
| 101 assert(!on_stack() || | |
| 102 (allocated_on_res_area() || allocated_on_stack()), | |
| 103 "growable array must be on stack if elements are not on arena and not on C heap"); | |
| 0 | 104 } |
| 105 | |
| 106 // This GA will use the given arena for storage. | |
| 107 // Consider using new(arena) GrowableArray<T> to allocate the header. | |
| 108 GenericGrowableArray(Arena* arena, int initial_size, int initial_len) { | |
| 109 _len = initial_len; | |
| 110 _max = initial_size; | |
| 111 assert(_len >= 0 && _len <= _max, "initial_len too big"); | |
| 112 _arena = arena; | |
| 113 assert(on_arena(), "arena has taken on reserved value 0 or 1"); | |
| 1685 | 114 // Relax next assert to allow object allocation on resource area, |
| 115 // on stack or embedded into an other object. | |
| 116 assert(allocated_on_arena() || allocated_on_stack(), | |
| 117 "growable array must be on arena or on stack if elements are on arena"); | |
| 0 | 118 } |
| 119 | |
| 120 void* raw_allocate(int elementSize); | |
| 432 | 121 |
| 122 // some uses pass the Thread explicitly for speed (4990299 tuning) | |
| 123 void* raw_allocate(Thread* thread, int elementSize) { | |
| 124 assert(on_stack(), "fast ResourceObj path only"); | |
| 125 return (void*)resource_allocate_bytes(thread, elementSize * _max); | |
| 126 } | |
| 0 | 127 }; |
| 128 | |
| 129 template<class E> class GrowableArray : public GenericGrowableArray { | |
| 130 private: | |
| 131 E* _data; // data array | |
| 132 | |
| 133 void grow(int j); | |
| 134 void raw_at_put_grow(int i, const E& p, const E& fill); | |
| 135 void clear_and_deallocate(); | |
| 136 public: | |
| 432 | 137 GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) { |
| 138 _data = (E*)raw_allocate(thread, sizeof(E)); | |
| 139 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
| 140 } | |
| 141 | |
| 0 | 142 GrowableArray(int initial_size, bool C_heap = false) : GenericGrowableArray(initial_size, 0, C_heap) { |
| 143 _data = (E*)raw_allocate(sizeof(E)); | |
| 144 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
| 145 } | |
| 146 | |
| 147 GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false) : GenericGrowableArray(initial_size, initial_len, C_heap) { | |
| 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 } | |
| 153 | |
| 154 GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) { | |
| 155 _data = (E*)raw_allocate(sizeof(E)); | |
| 156 int i = 0; | |
| 157 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler); | |
| 158 for (; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
| 159 } | |
| 160 | |
| 161 GrowableArray() : GenericGrowableArray(2, 0, false) { | |
| 162 _data = (E*)raw_allocate(sizeof(E)); | |
| 163 ::new ((void*)&_data[0]) E(); | |
| 164 ::new ((void*)&_data[1]) E(); | |
| 165 } | |
| 166 | |
| 167 // Does nothing for resource and arena objects | |
| 168 ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); } | |
| 169 | |
| 170 void clear() { _len = 0; } | |
| 171 int length() const { return _len; } | |
| 172 void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; } | |
| 173 bool is_empty() const { return _len == 0; } | |
| 174 bool is_nonempty() const { return _len != 0; } | |
| 175 bool is_full() const { return _len == _max; } | |
| 176 DEBUG_ONLY(E* data_addr() const { return _data; }) | |
| 177 | |
| 178 void print(); | |
| 179 | |
| 432 | 180 int append(const E& elem) { |
| 0 | 181 check_nesting(); |
| 182 if (_len == _max) grow(_len); | |
| 432 | 183 int idx = _len++; |
| 184 _data[idx] = elem; | |
| 185 return idx; | |
| 0 | 186 } |
| 187 | |
| 188 void append_if_missing(const E& elem) { | |
| 189 if (!contains(elem)) append(elem); | |
| 190 } | |
| 191 | |
| 192 E at(int i) const { | |
| 193 assert(0 <= i && i < _len, "illegal index"); | |
| 194 return _data[i]; | |
| 195 } | |
| 196 | |
| 197 E* adr_at(int i) const { | |
| 198 assert(0 <= i && i < _len, "illegal index"); | |
| 199 return &_data[i]; | |
| 200 } | |
| 201 | |
| 202 E first() const { | |
| 203 assert(_len > 0, "empty list"); | |
| 204 return _data[0]; | |
| 205 } | |
| 206 | |
| 207 E top() const { | |
| 208 assert(_len > 0, "empty list"); | |
| 209 return _data[_len-1]; | |
| 210 } | |
| 211 | |
| 212 void push(const E& elem) { append(elem); } | |
| 213 | |
| 214 E pop() { | |
| 215 assert(_len > 0, "empty list"); | |
| 216 return _data[--_len]; | |
| 217 } | |
| 218 | |
| 219 void at_put(int i, const E& elem) { | |
| 220 assert(0 <= i && i < _len, "illegal index"); | |
| 221 _data[i] = elem; | |
| 222 } | |
| 223 | |
| 224 E at_grow(int i, const E& fill = E()) { | |
| 225 assert(0 <= i, "negative index"); | |
| 226 check_nesting(); | |
| 227 if (i >= _len) { | |
| 228 if (i >= _max) grow(i); | |
| 229 for (int j = _len; j <= i; j++) | |
| 230 _data[j] = fill; | |
| 231 _len = i+1; | |
| 232 } | |
| 233 return _data[i]; | |
| 234 } | |
| 235 | |
| 236 void at_put_grow(int i, const E& elem, const E& fill = E()) { | |
| 237 assert(0 <= i, "negative index"); | |
| 238 check_nesting(); | |
| 239 raw_at_put_grow(i, elem, fill); | |
| 240 } | |
| 241 | |
| 242 bool contains(const E& elem) const { | |
| 243 for (int i = 0; i < _len; i++) { | |
| 244 if (_data[i] == elem) return true; | |
| 245 } | |
| 246 return false; | |
| 247 } | |
| 248 | |
| 249 int find(const E& elem) const { | |
| 250 for (int i = 0; i < _len; i++) { | |
| 251 if (_data[i] == elem) return i; | |
| 252 } | |
| 253 return -1; | |
| 254 } | |
| 255 | |
| 256 int find(void* token, bool f(void*, E)) const { | |
| 257 for (int i = 0; i < _len; i++) { | |
| 258 if (f(token, _data[i])) return i; | |
| 259 } | |
| 260 return -1; | |
| 261 } | |
| 262 | |
| 263 int find_at_end(void* token, bool f(void*, E)) const { | |
| 264 // start at the end of the array | |
| 265 for (int i = _len-1; i >= 0; i--) { | |
| 266 if (f(token, _data[i])) return i; | |
| 267 } | |
| 268 return -1; | |
| 269 } | |
| 270 | |
| 271 void remove(const E& elem) { | |
| 272 for (int i = 0; i < _len; i++) { | |
| 273 if (_data[i] == elem) { | |
| 274 for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j]; | |
| 275 _len--; | |
| 276 return; | |
| 277 } | |
| 278 } | |
| 279 ShouldNotReachHere(); | |
| 280 } | |
| 281 | |
| 282 void remove_at(int index) { | |
| 283 assert(0 <= index && index < _len, "illegal index"); | |
| 284 for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j]; | |
| 285 _len--; | |
| 286 } | |
| 287 | |
|
1080
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
288 // inserts the given element before the element at index i |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
289 void insert_before(const int idx, const E& elem) { |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
290 check_nesting(); |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
291 if (_len == _max) grow(_len); |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
292 for (int j = _len - 1; j >= idx; j--) { |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
293 _data[j + 1] = _data[j]; |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
294 } |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
295 _len++; |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
296 _data[idx] = elem; |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
297 } |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
298 |
| 0 | 299 void appendAll(const GrowableArray<E>* l) { |
| 300 for (int i = 0; i < l->_len; i++) { | |
| 301 raw_at_put_grow(_len, l->_data[i], 0); | |
| 302 } | |
| 303 } | |
| 304 | |
| 305 void sort(int f(E*,E*)) { | |
| 306 qsort(_data, length(), sizeof(E), (_sort_Fn)f); | |
| 307 } | |
| 308 // sort by fixed-stride sub arrays: | |
| 309 void sort(int f(E*,E*), int stride) { | |
| 310 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); | |
| 311 } | |
| 312 }; | |
| 313 | |
| 314 // Global GrowableArray methods (one instance in the library per each 'E' type). | |
| 315 | |
| 316 template<class E> void GrowableArray<E>::grow(int j) { | |
| 317 // grow the array by doubling its size (amortized growth) | |
| 318 int old_max = _max; | |
| 319 if (_max == 0) _max = 1; // prevent endless loop | |
| 320 while (j >= _max) _max = _max*2; | |
| 321 // j < _max | |
| 322 E* newData = (E*)raw_allocate(sizeof(E)); | |
| 323 int i = 0; | |
| 324 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]); | |
| 325 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E(); | |
| 326 for (i = 0; i < old_max; i++) _data[i].~E(); | |
| 327 if (on_C_heap() && _data != NULL) { | |
| 328 FreeHeap(_data); | |
| 329 } | |
| 330 _data = newData; | |
| 331 } | |
| 332 | |
| 333 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) { | |
| 334 if (i >= _len) { | |
| 335 if (i >= _max) grow(i); | |
| 336 for (int j = _len; j < i; j++) | |
| 337 _data[j] = fill; | |
| 338 _len = i+1; | |
| 339 } | |
| 340 _data[i] = p; | |
| 341 } | |
| 342 | |
| 343 // This function clears and deallocate the data in the growable array that | |
| 344 // has been allocated on the C heap. It's not public - called by the | |
| 345 // destructor. | |
| 346 template<class E> void GrowableArray<E>::clear_and_deallocate() { | |
| 347 assert(on_C_heap(), | |
| 348 "clear_and_deallocate should only be called when on C heap"); | |
| 349 clear(); | |
| 350 if (_data != NULL) { | |
| 351 for (int i = 0; i < _max; i++) _data[i].~E(); | |
| 352 FreeHeap(_data); | |
| 353 _data = NULL; | |
| 354 } | |
| 355 } | |
| 356 | |
| 357 template<class E> void GrowableArray<E>::print() { | |
| 358 tty->print("Growable Array " INTPTR_FORMAT, this); | |
| 359 tty->print(": length %ld (_max %ld) { ", _len, _max); | |
| 360 for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i])); | |
| 361 tty->print("}\n"); | |
| 362 } |