1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/growableArray.hpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,415 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#ifndef SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
1.29 +#define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
1.30 +
1.31 +#include "memory/allocation.hpp"
1.32 +#include "memory/allocation.inline.hpp"
1.33 +#include "utilities/debug.hpp"
1.34 +#include "utilities/globalDefinitions.hpp"
1.35 +#include "utilities/top.hpp"
1.36 +
1.37 +// A growable array.
1.38 +
1.39 +/*************************************************************************/
1.40 +/* */
1.41 +/* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
1.42 +/* */
1.43 +/* Should you use GrowableArrays to contain handles you must be certain */
1.44 +/* the the GrowableArray does not outlive the HandleMark that contains */
1.45 +/* the handles. Since GrowableArrays are typically resource allocated */
1.46 +/* the following is an example of INCORRECT CODE, */
1.47 +/* */
1.48 +/* ResourceMark rm; */
1.49 +/* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
1.50 +/* if (blah) { */
1.51 +/* while (...) { */
1.52 +/* HandleMark hm; */
1.53 +/* ... */
1.54 +/* Handle h(THREAD, some_oop); */
1.55 +/* arr->append(h); */
1.56 +/* } */
1.57 +/* } */
1.58 +/* if (arr->length() != 0 ) { */
1.59 +/* oop bad_oop = arr->at(0)(); // Handle is BAD HERE. */
1.60 +/* ... */
1.61 +/* } */
1.62 +/* */
1.63 +/* If the GrowableArrays you are creating is C_Heap allocated then it */
1.64 +/* hould not old handles since the handles could trivially try and */
1.65 +/* outlive their HandleMark. In some situations you might need to do */
1.66 +/* this and it would be legal but be very careful and see if you can do */
1.67 +/* the code in some other manner. */
1.68 +/* */
1.69 +/*************************************************************************/
1.70 +
1.71 +// To call default constructor the placement operator new() is used.
1.72 +// It should be empty (it only returns the passed void* pointer).
1.73 +// The definition of placement operator new(size_t, void*) in the <new>.
1.74 +
1.75 +#include <new>
1.76 +
1.77 +// Need the correct linkage to call qsort without warnings
1.78 +extern "C" {
1.79 + typedef int (*_sort_Fn)(const void *, const void *);
1.80 +}
1.81 +
1.82 +class GenericGrowableArray : public ResourceObj {
1.83 + friend class VMStructs;
1.84 +
1.85 + protected:
1.86 + int _len; // current length
1.87 + int _max; // maximum length
1.88 + Arena* _arena; // Indicates where allocation occurs:
1.89 + // 0 means default ResourceArea
1.90 + // 1 means on C heap
1.91 + // otherwise, allocate in _arena
1.92 +
1.93 + MEMFLAGS _memflags; // memory type if allocation in C heap
1.94 +
1.95 +#ifdef ASSERT
1.96 + int _nesting; // resource area nesting at creation
1.97 + void set_nesting();
1.98 + void check_nesting();
1.99 +#else
1.100 +#define set_nesting();
1.101 +#define check_nesting();
1.102 +#endif
1.103 +
1.104 + // Where are we going to allocate memory?
1.105 + bool on_C_heap() { return _arena == (Arena*)1; }
1.106 + bool on_stack () { return _arena == NULL; }
1.107 + bool on_arena () { return _arena > (Arena*)1; }
1.108 +
1.109 + // This GA will use the resource stack for storage if c_heap==false,
1.110 + // Else it will use the C heap. Use clear_and_deallocate to avoid leaks.
1.111 + GenericGrowableArray(int initial_size, int initial_len, bool c_heap, MEMFLAGS flags = mtNone) {
1.112 + _len = initial_len;
1.113 + _max = initial_size;
1.114 + _memflags = flags;
1.115 +
1.116 + // memory type has to be specified for C heap allocation
1.117 + assert(!(c_heap && flags == mtNone), "memory type not specified for C heap object");
1.118 +
1.119 + assert(_len >= 0 && _len <= _max, "initial_len too big");
1.120 + _arena = (c_heap ? (Arena*)1 : NULL);
1.121 + set_nesting();
1.122 + assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are");
1.123 + assert(!on_stack() ||
1.124 + (allocated_on_res_area() || allocated_on_stack()),
1.125 + "growable array must be on stack if elements are not on arena and not on C heap");
1.126 + }
1.127 +
1.128 + // This GA will use the given arena for storage.
1.129 + // Consider using new(arena) GrowableArray<T> to allocate the header.
1.130 + GenericGrowableArray(Arena* arena, int initial_size, int initial_len) {
1.131 + _len = initial_len;
1.132 + _max = initial_size;
1.133 + assert(_len >= 0 && _len <= _max, "initial_len too big");
1.134 + _arena = arena;
1.135 + _memflags = mtNone;
1.136 +
1.137 + assert(on_arena(), "arena has taken on reserved value 0 or 1");
1.138 + // Relax next assert to allow object allocation on resource area,
1.139 + // on stack or embedded into an other object.
1.140 + assert(allocated_on_arena() || allocated_on_stack(),
1.141 + "growable array must be on arena or on stack if elements are on arena");
1.142 + }
1.143 +
1.144 + void* raw_allocate(int elementSize);
1.145 +
1.146 + // some uses pass the Thread explicitly for speed (4990299 tuning)
1.147 + void* raw_allocate(Thread* thread, int elementSize) {
1.148 + assert(on_stack(), "fast ResourceObj path only");
1.149 + return (void*)resource_allocate_bytes(thread, elementSize * _max);
1.150 + }
1.151 +};
1.152 +
1.153 +template<class E> class GrowableArray : public GenericGrowableArray {
1.154 + friend class VMStructs;
1.155 +
1.156 + private:
1.157 + E* _data; // data array
1.158 +
1.159 + void grow(int j);
1.160 + void raw_at_put_grow(int i, const E& p, const E& fill);
1.161 + void clear_and_deallocate();
1.162 + public:
1.163 + GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
1.164 + _data = (E*)raw_allocate(thread, sizeof(E));
1.165 + for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
1.166 + }
1.167 +
1.168 + GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
1.169 + : GenericGrowableArray(initial_size, 0, C_heap, F) {
1.170 + _data = (E*)raw_allocate(sizeof(E));
1.171 + for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
1.172 + }
1.173 +
1.174 + GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
1.175 + : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
1.176 + _data = (E*)raw_allocate(sizeof(E));
1.177 + int i = 0;
1.178 + for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
1.179 + for (; i < _max; i++) ::new ((void*)&_data[i]) E();
1.180 + }
1.181 +
1.182 + GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
1.183 + _data = (E*)raw_allocate(sizeof(E));
1.184 + int i = 0;
1.185 + for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
1.186 + for (; i < _max; i++) ::new ((void*)&_data[i]) E();
1.187 + }
1.188 +
1.189 + GrowableArray() : GenericGrowableArray(2, 0, false) {
1.190 + _data = (E*)raw_allocate(sizeof(E));
1.191 + ::new ((void*)&_data[0]) E();
1.192 + ::new ((void*)&_data[1]) E();
1.193 + }
1.194 +
1.195 + // Does nothing for resource and arena objects
1.196 + ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); }
1.197 +
1.198 + void clear() { _len = 0; }
1.199 + int length() const { return _len; }
1.200 + int max_length() const { return _max; }
1.201 + void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; }
1.202 + bool is_empty() const { return _len == 0; }
1.203 + bool is_nonempty() const { return _len != 0; }
1.204 + bool is_full() const { return _len == _max; }
1.205 + DEBUG_ONLY(E* data_addr() const { return _data; })
1.206 +
1.207 + void print();
1.208 +
1.209 + int append(const E& elem) {
1.210 + check_nesting();
1.211 + if (_len == _max) grow(_len);
1.212 + int idx = _len++;
1.213 + _data[idx] = elem;
1.214 + return idx;
1.215 + }
1.216 +
1.217 + bool append_if_missing(const E& elem) {
1.218 + // Returns TRUE if elem is added.
1.219 + bool missed = !contains(elem);
1.220 + if (missed) append(elem);
1.221 + return missed;
1.222 + }
1.223 +
1.224 + E& at(int i) {
1.225 + assert(0 <= i && i < _len, "illegal index");
1.226 + return _data[i];
1.227 + }
1.228 +
1.229 + E const& at(int i) const {
1.230 + assert(0 <= i && i < _len, "illegal index");
1.231 + return _data[i];
1.232 + }
1.233 +
1.234 + E* adr_at(int i) const {
1.235 + assert(0 <= i && i < _len, "illegal index");
1.236 + return &_data[i];
1.237 + }
1.238 +
1.239 + E first() const {
1.240 + assert(_len > 0, "empty list");
1.241 + return _data[0];
1.242 + }
1.243 +
1.244 + E top() const {
1.245 + assert(_len > 0, "empty list");
1.246 + return _data[_len-1];
1.247 + }
1.248 +
1.249 + void push(const E& elem) { append(elem); }
1.250 +
1.251 + E pop() {
1.252 + assert(_len > 0, "empty list");
1.253 + return _data[--_len];
1.254 + }
1.255 +
1.256 + void at_put(int i, const E& elem) {
1.257 + assert(0 <= i && i < _len, "illegal index");
1.258 + _data[i] = elem;
1.259 + }
1.260 +
1.261 + E at_grow(int i, const E& fill = E()) {
1.262 + assert(0 <= i, "negative index");
1.263 + check_nesting();
1.264 + if (i >= _len) {
1.265 + if (i >= _max) grow(i);
1.266 + for (int j = _len; j <= i; j++)
1.267 + _data[j] = fill;
1.268 + _len = i+1;
1.269 + }
1.270 + return _data[i];
1.271 + }
1.272 +
1.273 + void at_put_grow(int i, const E& elem, const E& fill = E()) {
1.274 + assert(0 <= i, "negative index");
1.275 + check_nesting();
1.276 + raw_at_put_grow(i, elem, fill);
1.277 + }
1.278 +
1.279 + bool contains(const E& elem) const {
1.280 + for (int i = 0; i < _len; i++) {
1.281 + if (_data[i] == elem) return true;
1.282 + }
1.283 + return false;
1.284 + }
1.285 +
1.286 + int find(const E& elem) const {
1.287 + for (int i = 0; i < _len; i++) {
1.288 + if (_data[i] == elem) return i;
1.289 + }
1.290 + return -1;
1.291 + }
1.292 +
1.293 + int find_from_end(const E& elem) const {
1.294 + for (int i = _len-1; i >= 0; i--) {
1.295 + if (_data[i] == elem) return i;
1.296 + }
1.297 + return -1;
1.298 + }
1.299 +
1.300 + int find(void* token, bool f(void*, E)) const {
1.301 + for (int i = 0; i < _len; i++) {
1.302 + if (f(token, _data[i])) return i;
1.303 + }
1.304 + return -1;
1.305 + }
1.306 +
1.307 + int find_from_end(void* token, bool f(void*, E)) const {
1.308 + // start at the end of the array
1.309 + for (int i = _len-1; i >= 0; i--) {
1.310 + if (f(token, _data[i])) return i;
1.311 + }
1.312 + return -1;
1.313 + }
1.314 +
1.315 + void remove(const E& elem) {
1.316 + for (int i = 0; i < _len; i++) {
1.317 + if (_data[i] == elem) {
1.318 + for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j];
1.319 + _len--;
1.320 + return;
1.321 + }
1.322 + }
1.323 + ShouldNotReachHere();
1.324 + }
1.325 +
1.326 + // The order is preserved.
1.327 + void remove_at(int index) {
1.328 + assert(0 <= index && index < _len, "illegal index");
1.329 + for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j];
1.330 + _len--;
1.331 + }
1.332 +
1.333 + // The order is changed.
1.334 + void delete_at(int index) {
1.335 + assert(0 <= index && index < _len, "illegal index");
1.336 + if (index < --_len) {
1.337 + // Replace removed element with last one.
1.338 + _data[index] = _data[_len];
1.339 + }
1.340 + }
1.341 +
1.342 + // inserts the given element before the element at index i
1.343 + void insert_before(const int idx, const E& elem) {
1.344 + check_nesting();
1.345 + if (_len == _max) grow(_len);
1.346 + for (int j = _len - 1; j >= idx; j--) {
1.347 + _data[j + 1] = _data[j];
1.348 + }
1.349 + _len++;
1.350 + _data[idx] = elem;
1.351 + }
1.352 +
1.353 + void appendAll(const GrowableArray<E>* l) {
1.354 + for (int i = 0; i < l->_len; i++) {
1.355 + raw_at_put_grow(_len, l->_data[i], 0);
1.356 + }
1.357 + }
1.358 +
1.359 + void sort(int f(E*,E*)) {
1.360 + qsort(_data, length(), sizeof(E), (_sort_Fn)f);
1.361 + }
1.362 + // sort by fixed-stride sub arrays:
1.363 + void sort(int f(E*,E*), int stride) {
1.364 + qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
1.365 + }
1.366 +};
1.367 +
1.368 +// Global GrowableArray methods (one instance in the library per each 'E' type).
1.369 +
1.370 +template<class E> void GrowableArray<E>::grow(int j) {
1.371 + // grow the array by doubling its size (amortized growth)
1.372 + int old_max = _max;
1.373 + if (_max == 0) _max = 1; // prevent endless loop
1.374 + while (j >= _max) _max = _max*2;
1.375 + // j < _max
1.376 + E* newData = (E*)raw_allocate(sizeof(E));
1.377 + int i = 0;
1.378 + for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
1.379 + for ( ; i < _max; i++) ::new ((void*)&newData[i]) E();
1.380 + for (i = 0; i < old_max; i++) _data[i].~E();
1.381 + if (on_C_heap() && _data != NULL) {
1.382 + FreeHeap(_data);
1.383 + }
1.384 + _data = newData;
1.385 +}
1.386 +
1.387 +template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
1.388 + if (i >= _len) {
1.389 + if (i >= _max) grow(i);
1.390 + for (int j = _len; j < i; j++)
1.391 + _data[j] = fill;
1.392 + _len = i+1;
1.393 + }
1.394 + _data[i] = p;
1.395 +}
1.396 +
1.397 +// This function clears and deallocate the data in the growable array that
1.398 +// has been allocated on the C heap. It's not public - called by the
1.399 +// destructor.
1.400 +template<class E> void GrowableArray<E>::clear_and_deallocate() {
1.401 + assert(on_C_heap(),
1.402 + "clear_and_deallocate should only be called when on C heap");
1.403 + clear();
1.404 + if (_data != NULL) {
1.405 + for (int i = 0; i < _max; i++) _data[i].~E();
1.406 + FreeHeap(_data);
1.407 + _data = NULL;
1.408 + }
1.409 +}
1.410 +
1.411 +template<class E> void GrowableArray<E>::print() {
1.412 + tty->print("Growable Array " INTPTR_FORMAT, this);
1.413 + tty->print(": length %ld (_max %ld) { ", _len, _max);
1.414 + for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
1.415 + tty->print("}\n");
1.416 +}
1.417 +
1.418 +#endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
