1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/utilities/growableArray.hpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,331 @@
1.4 +/*
1.5 + * Copyright 1997-2005 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// A growable array.
1.29 +
1.30 +/*************************************************************************/
1.31 +/* */
1.32 +/* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
1.33 +/* */
1.34 +/* Should you use GrowableArrays to contain handles you must be certain */
1.35 +/* the the GrowableArray does not outlive the HandleMark that contains */
1.36 +/* the handles. Since GrowableArrays are typically resource allocated */
1.37 +/* the following is an example of INCORRECT CODE, */
1.38 +/* */
1.39 +/* ResourceMark rm; */
1.40 +/* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
1.41 +/* if (blah) { */
1.42 +/* while (...) { */
1.43 +/* HandleMark hm; */
1.44 +/* ... */
1.45 +/* Handle h(THREAD, some_oop); */
1.46 +/* arr->append(h); */
1.47 +/* } */
1.48 +/* } */
1.49 +/* if (arr->length() != 0 ) { */
1.50 +/* oop bad_oop = arr->at(0)(); // Handle is BAD HERE. */
1.51 +/* ... */
1.52 +/* } */
1.53 +/* */
1.54 +/* If the GrowableArrays you are creating is C_Heap allocated then it */
1.55 +/* hould not old handles since the handles could trivially try and */
1.56 +/* outlive their HandleMark. In some situations you might need to do */
1.57 +/* this and it would be legal but be very careful and see if you can do */
1.58 +/* the code in some other manner. */
1.59 +/* */
1.60 +/*************************************************************************/
1.61 +
1.62 +// To call default constructor the placement operator new() is used.
1.63 +// It should be empty (it only returns the passed void* pointer).
1.64 +// The definition of placement operator new(size_t, void*) in the <new>.
1.65 +
1.66 +#include <new>
1.67 +
1.68 +// Need the correct linkage to call qsort without warnings
1.69 +extern "C" {
1.70 + typedef int (*_sort_Fn)(const void *, const void *);
1.71 +}
1.72 +
1.73 +class GenericGrowableArray : public ResourceObj {
1.74 + protected:
1.75 + int _len; // current length
1.76 + int _max; // maximum length
1.77 + Arena* _arena; // Indicates where allocation occurs:
1.78 + // 0 means default ResourceArea
1.79 + // 1 means on C heap
1.80 + // otherwise, allocate in _arena
1.81 +#ifdef ASSERT
1.82 + int _nesting; // resource area nesting at creation
1.83 + void set_nesting();
1.84 + void check_nesting();
1.85 +#else
1.86 +#define set_nesting();
1.87 +#define check_nesting();
1.88 +#endif
1.89 +
1.90 + // Where are we going to allocate memory?
1.91 + bool on_C_heap() { return _arena == (Arena*)1; }
1.92 + bool on_stack () { return _arena == NULL; }
1.93 + bool on_arena () { return _arena > (Arena*)1; }
1.94 +
1.95 + // This GA will use the resource stack for storage if c_heap==false,
1.96 + // Else it will use the C heap. Use clear_and_deallocate to avoid leaks.
1.97 + GenericGrowableArray(int initial_size, int initial_len, bool c_heap) {
1.98 + _len = initial_len;
1.99 + _max = initial_size;
1.100 + assert(_len >= 0 && _len <= _max, "initial_len too big");
1.101 + _arena = (c_heap ? (Arena*)1 : NULL);
1.102 + set_nesting();
1.103 + assert(!c_heap || allocated_on_C_heap(), "growable array must be on C heap if elements are");
1.104 + }
1.105 +
1.106 + // This GA will use the given arena for storage.
1.107 + // Consider using new(arena) GrowableArray<T> to allocate the header.
1.108 + GenericGrowableArray(Arena* arena, int initial_size, int initial_len) {
1.109 + _len = initial_len;
1.110 + _max = initial_size;
1.111 + assert(_len >= 0 && _len <= _max, "initial_len too big");
1.112 + _arena = arena;
1.113 + assert(on_arena(), "arena has taken on reserved value 0 or 1");
1.114 + }
1.115 +
1.116 + void* raw_allocate(int elementSize);
1.117 +};
1.118 +
1.119 +template<class E> class GrowableArray : public GenericGrowableArray {
1.120 + private:
1.121 + E* _data; // data array
1.122 +
1.123 + void grow(int j);
1.124 + void raw_at_put_grow(int i, const E& p, const E& fill);
1.125 + void clear_and_deallocate();
1.126 + public:
1.127 + GrowableArray(int initial_size, bool C_heap = false) : GenericGrowableArray(initial_size, 0, C_heap) {
1.128 + _data = (E*)raw_allocate(sizeof(E));
1.129 + for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
1.130 + }
1.131 +
1.132 + GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false) : GenericGrowableArray(initial_size, initial_len, C_heap) {
1.133 + _data = (E*)raw_allocate(sizeof(E));
1.134 + int i = 0;
1.135 + for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
1.136 + for (; i < _max; i++) ::new ((void*)&_data[i]) E();
1.137 + }
1.138 +
1.139 + GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
1.140 + _data = (E*)raw_allocate(sizeof(E));
1.141 + int i = 0;
1.142 + for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
1.143 + for (; i < _max; i++) ::new ((void*)&_data[i]) E();
1.144 + }
1.145 +
1.146 + GrowableArray() : GenericGrowableArray(2, 0, false) {
1.147 + _data = (E*)raw_allocate(sizeof(E));
1.148 + ::new ((void*)&_data[0]) E();
1.149 + ::new ((void*)&_data[1]) E();
1.150 + }
1.151 +
1.152 + // Does nothing for resource and arena objects
1.153 + ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); }
1.154 +
1.155 + void clear() { _len = 0; }
1.156 + int length() const { return _len; }
1.157 + void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; }
1.158 + bool is_empty() const { return _len == 0; }
1.159 + bool is_nonempty() const { return _len != 0; }
1.160 + bool is_full() const { return _len == _max; }
1.161 + DEBUG_ONLY(E* data_addr() const { return _data; })
1.162 +
1.163 + void print();
1.164 +
1.165 + void append(const E& elem) {
1.166 + check_nesting();
1.167 + if (_len == _max) grow(_len);
1.168 + _data[_len++] = elem;
1.169 + }
1.170 +
1.171 + void append_if_missing(const E& elem) {
1.172 + if (!contains(elem)) append(elem);
1.173 + }
1.174 +
1.175 + E at(int i) const {
1.176 + assert(0 <= i && i < _len, "illegal index");
1.177 + return _data[i];
1.178 + }
1.179 +
1.180 + E* adr_at(int i) const {
1.181 + assert(0 <= i && i < _len, "illegal index");
1.182 + return &_data[i];
1.183 + }
1.184 +
1.185 + E first() const {
1.186 + assert(_len > 0, "empty list");
1.187 + return _data[0];
1.188 + }
1.189 +
1.190 + E top() const {
1.191 + assert(_len > 0, "empty list");
1.192 + return _data[_len-1];
1.193 + }
1.194 +
1.195 + void push(const E& elem) { append(elem); }
1.196 +
1.197 + E pop() {
1.198 + assert(_len > 0, "empty list");
1.199 + return _data[--_len];
1.200 + }
1.201 +
1.202 + void at_put(int i, const E& elem) {
1.203 + assert(0 <= i && i < _len, "illegal index");
1.204 + _data[i] = elem;
1.205 + }
1.206 +
1.207 + E at_grow(int i, const E& fill = E()) {
1.208 + assert(0 <= i, "negative index");
1.209 + check_nesting();
1.210 + if (i >= _len) {
1.211 + if (i >= _max) grow(i);
1.212 + for (int j = _len; j <= i; j++)
1.213 + _data[j] = fill;
1.214 + _len = i+1;
1.215 + }
1.216 + return _data[i];
1.217 + }
1.218 +
1.219 + void at_put_grow(int i, const E& elem, const E& fill = E()) {
1.220 + assert(0 <= i, "negative index");
1.221 + check_nesting();
1.222 + raw_at_put_grow(i, elem, fill);
1.223 + }
1.224 +
1.225 + bool contains(const E& elem) const {
1.226 + for (int i = 0; i < _len; i++) {
1.227 + if (_data[i] == elem) return true;
1.228 + }
1.229 + return false;
1.230 + }
1.231 +
1.232 + int find(const E& elem) const {
1.233 + for (int i = 0; i < _len; i++) {
1.234 + if (_data[i] == elem) return i;
1.235 + }
1.236 + return -1;
1.237 + }
1.238 +
1.239 + int find(void* token, bool f(void*, E)) const {
1.240 + for (int i = 0; i < _len; i++) {
1.241 + if (f(token, _data[i])) return i;
1.242 + }
1.243 + return -1;
1.244 + }
1.245 +
1.246 + int find_at_end(void* token, bool f(void*, E)) const {
1.247 + // start at the end of the array
1.248 + for (int i = _len-1; i >= 0; i--) {
1.249 + if (f(token, _data[i])) return i;
1.250 + }
1.251 + return -1;
1.252 + }
1.253 +
1.254 + void remove(const E& elem) {
1.255 + for (int i = 0; i < _len; i++) {
1.256 + if (_data[i] == elem) {
1.257 + for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j];
1.258 + _len--;
1.259 + return;
1.260 + }
1.261 + }
1.262 + ShouldNotReachHere();
1.263 + }
1.264 +
1.265 + void remove_at(int index) {
1.266 + assert(0 <= index && index < _len, "illegal index");
1.267 + for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j];
1.268 + _len--;
1.269 + }
1.270 +
1.271 + void appendAll(const GrowableArray<E>* l) {
1.272 + for (int i = 0; i < l->_len; i++) {
1.273 + raw_at_put_grow(_len, l->_data[i], 0);
1.274 + }
1.275 + }
1.276 +
1.277 + void sort(int f(E*,E*)) {
1.278 + qsort(_data, length(), sizeof(E), (_sort_Fn)f);
1.279 + }
1.280 + // sort by fixed-stride sub arrays:
1.281 + void sort(int f(E*,E*), int stride) {
1.282 + qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
1.283 + }
1.284 +};
1.285 +
1.286 +// Global GrowableArray methods (one instance in the library per each 'E' type).
1.287 +
1.288 +template<class E> void GrowableArray<E>::grow(int j) {
1.289 + // grow the array by doubling its size (amortized growth)
1.290 + int old_max = _max;
1.291 + if (_max == 0) _max = 1; // prevent endless loop
1.292 + while (j >= _max) _max = _max*2;
1.293 + // j < _max
1.294 + E* newData = (E*)raw_allocate(sizeof(E));
1.295 + int i = 0;
1.296 + for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
1.297 + for ( ; i < _max; i++) ::new ((void*)&newData[i]) E();
1.298 + for (i = 0; i < old_max; i++) _data[i].~E();
1.299 + if (on_C_heap() && _data != NULL) {
1.300 + FreeHeap(_data);
1.301 + }
1.302 + _data = newData;
1.303 +}
1.304 +
1.305 +template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
1.306 + if (i >= _len) {
1.307 + if (i >= _max) grow(i);
1.308 + for (int j = _len; j < i; j++)
1.309 + _data[j] = fill;
1.310 + _len = i+1;
1.311 + }
1.312 + _data[i] = p;
1.313 +}
1.314 +
1.315 +// This function clears and deallocate the data in the growable array that
1.316 +// has been allocated on the C heap. It's not public - called by the
1.317 +// destructor.
1.318 +template<class E> void GrowableArray<E>::clear_and_deallocate() {
1.319 + assert(on_C_heap(),
1.320 + "clear_and_deallocate should only be called when on C heap");
1.321 + clear();
1.322 + if (_data != NULL) {
1.323 + for (int i = 0; i < _max; i++) _data[i].~E();
1.324 + FreeHeap(_data);
1.325 + _data = NULL;
1.326 + }
1.327 +}
1.328 +
1.329 +template<class E> void GrowableArray<E>::print() {
1.330 + tty->print("Growable Array " INTPTR_FORMAT, this);
1.331 + tty->print(": length %ld (_max %ld) { ", _len, _max);
1.332 + for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
1.333 + tty->print("}\n");
1.334 +}
