1 /*
2 * Copyright (c) 2000, 2014, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_UTILITIES_ARRAY_HPP
26 #define SHARE_VM_UTILITIES_ARRAY_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/allocation.inline.hpp"
30 #include "memory/metaspace.hpp"
31 #include "runtime/orderAccess.hpp"
32
33 // correct linkage required to compile w/o warnings
34 // (must be on file level - cannot be local)
35 extern "C" { typedef int (*ftype)(const void*, const void*); }
36
37
38 class ResourceArray: public ResourceObj {
39 protected:
40 int _length; // the number of array elements
41 void* _data; // the array memory
42 #ifdef ASSERT
43 int _nesting; // the resource area nesting level
44 #endif
45
46 // creation
47 ResourceArray() {
48 _length = 0;
49 _data = NULL;
50 DEBUG_ONLY(init_nesting();)
51 // client may call initialize, at most once
52 }
53
54
55 ResourceArray(size_t esize, int length) {
56 DEBUG_ONLY(_data = NULL);
57 initialize(esize, length);
58 }
59
60 void initialize(size_t esize, int length) {
61 assert(length >= 0, "illegal length");
62 assert(StressRewriter || _data == NULL, "must be new object");
63 _length = length;
64 _data = resource_allocate_bytes(esize * length);
65 DEBUG_ONLY(init_nesting();)
66 }
67
68 #ifdef ASSERT
69 void init_nesting();
70 #endif
71
72 // helper functions
73 void sort (size_t esize, ftype f); // sort the array
74 void expand (size_t esize, int i, int& size);// expand the array to include slot i
75 void remove_at(size_t esize, int i); // remove the element in slot i
76
77 public:
78 // standard operations
79 int length() const { return _length; }
80 bool is_empty() const { return length() == 0; }
81 };
82
83
84 template <MEMFLAGS F>class CHeapArray: public CHeapObj<F> {
85 protected:
86 int _length; // the number of array elements
87 void* _data; // the array memory
88
89 // creation
90 CHeapArray() {
91 _length = 0;
92 _data = NULL;
93 }
94
95
96 CHeapArray(size_t esize, int length) {
97 assert(length >= 0, "illegal length");
98 _length = length;
99 _data = (void*) NEW_C_HEAP_ARRAY(char *, esize * length, F);
100 }
101
102 void initialize(size_t esize, int length) {
103 // In debug set array to 0?
104 }
105
106 #ifdef ASSERT
107 void init_nesting();
108 #endif
109
110 // helper functions
111 void sort (size_t esize, ftype f); // sort the array
112 void expand (size_t esize, int i, int& size);// expand the array to include slot i
113 void remove_at(size_t esize, int i); // remove the element in slot i
114
115 public:
116 // standard operations
117 int length() const { return _length; }
118 bool is_empty() const { return length() == 0; }
119 };
120
121 #define define_generic_array(array_name,element_type, base_class) \
122 class array_name: public base_class { \
123 protected: \
124 typedef element_type etype; \
125 enum { esize = sizeof(etype) }; \
126 \
127 void base_remove_at(size_t size, int i) { base_class::remove_at(size, i); } \
128 \
129 public: \
130 /* creation */ \
131 array_name() : base_class() {} \
132 explicit array_name(const int length) : base_class(esize, length) {} \
133 array_name(const int length, const etype fx) { initialize(length, fx); } \
134 void initialize(const int length) { base_class::initialize(esize, length); } \
135 void initialize(const int length, const etype fx) { \
136 initialize(length); \
137 for (int i = 0; i < length; i++) ((etype*)_data)[i] = fx; \
138 } \
139 \
140 /* standard operations */ \
141 etype& operator [] (const int i) const { \
142 assert(0 <= i && i < length(), "index out of bounds"); \
143 return ((etype*)_data)[i]; \
144 } \
145 \
146 int index_of(const etype x) const { \
147 int i = length(); \
148 while (i-- > 0 && ((etype*)_data)[i] != x) ; \
149 /* i < 0 || ((etype*)_data)_data[i] == x */ \
150 return i; \
151 } \
152 \
153 void sort(int f(etype*, etype*)) { base_class::sort(esize, (ftype)f); } \
154 bool contains(const etype x) const { return index_of(x) >= 0; } \
155 \
156 /* deprecated operations - for compatibility with GrowableArray only */ \
157 etype at(const int i) const { return (*this)[i]; } \
158 void at_put(const int i, const etype x) { (*this)[i] = x; } \
159 etype* adr_at(const int i) { return &(*this)[i]; } \
160 int find(const etype x) { return index_of(x); } \
161 }; \
162
163
164 #define define_array(array_name,element_type) \
165 define_generic_array(array_name, element_type, ResourceArray)
166
167
168 #define define_stack(stack_name,array_name) \
169 class stack_name: public array_name { \
170 protected: \
171 int _size; \
172 \
173 void grow(const int i, const etype fx) { \
174 assert(i >= length(), "index too small"); \
175 if (i >= size()) expand(esize, i, _size); \
176 for (int j = length(); j <= i; j++) ((etype*)_data)[j] = fx; \
177 _length = i+1; \
178 } \
179 \
180 public: \
181 /* creation */ \
182 stack_name() : array_name() { _size = 0; } \
183 stack_name(const int size) { initialize(size); } \
184 stack_name(const int size, const etype fx) { initialize(size, fx); } \
185 void initialize(const int size, const etype fx) { \
186 _size = size; \
187 array_name::initialize(size, fx); \
188 /* _length == size, allocation and size are the same */ \
189 } \
190 void initialize(const int size) { \
191 _size = size; \
192 array_name::initialize(size); \
193 _length = 0; /* reset length to zero; _size records the allocation */ \
194 } \
195 \
196 /* standard operations */ \
197 int size() const { return _size; } \
198 \
199 int push(const etype x) { \
200 int len = length(); \
201 if (len >= size()) expand(esize, len, _size); \
202 ((etype*)_data)[len] = x; \
203 _length = len+1; \
204 return len; \
205 } \
206 \
207 etype pop() { \
208 assert(!is_empty(), "stack is empty"); \
209 return ((etype*)_data)[--_length]; \
210 } \
211 \
212 etype top() const { \
213 assert(!is_empty(), "stack is empty"); \
214 return ((etype*)_data)[length() - 1]; \
215 } \
216 \
217 void push_all(const stack_name* stack) { \
218 const int l = stack->length(); \
219 for (int i = 0; i < l; i++) push(((etype*)(stack->_data))[i]); \
220 } \
221 \
222 etype at_grow(const int i, const etype fx) { \
223 if (i >= length()) grow(i, fx); \
224 return ((etype*)_data)[i]; \
225 } \
226 \
227 void at_put_grow(const int i, const etype x, const etype fx) { \
228 if (i >= length()) grow(i, fx); \
229 ((etype*)_data)[i] = x; \
230 } \
231 \
232 void truncate(const int length) { \
233 assert(0 <= length && length <= this->length(), "illegal length"); \
234 _length = length; \
235 } \
236 \
237 void remove_at(int i) { base_remove_at(esize, i); } \
238 void remove(etype x) { remove_at(index_of(x)); } \
239 \
240 /* inserts the given element before the element at index i */ \
241 void insert_before(const int i, const etype el) { \
242 int len = length(); \
243 int new_length = len + 1; \
244 if (new_length >= size()) expand(esize, new_length, _size); \
245 for (int j = len - 1; j >= i; j--) { \
246 ((etype*)_data)[j + 1] = ((etype*)_data)[j]; \
247 } \
248 _length = new_length; \
249 at_put(i, el); \
250 } \
251 \
252 /* inserts contents of the given stack before the element at index i */ \
253 void insert_before(const int i, const stack_name *st) { \
254 if (st->length() == 0) return; \
255 int len = length(); \
256 int st_len = st->length(); \
257 int new_length = len + st_len; \
258 if (new_length >= size()) expand(esize, new_length, _size); \
259 int j; \
260 for (j = len - 1; j >= i; j--) { \
261 ((etype*)_data)[j + st_len] = ((etype*)_data)[j]; \
262 } \
263 for (j = 0; j < st_len; j++) { \
264 ((etype*)_data)[i + j] = ((etype*)st->_data)[j]; \
265 } \
266 _length = new_length; \
267 } \
268 \
269 /* deprecated operations - for compatibility with GrowableArray only */ \
270 int capacity() const { return size(); } \
271 void clear() { truncate(0); } \
272 void trunc_to(const int length) { truncate(length); } \
273 int append(const etype x) { return push(x); } \
274 void appendAll(const stack_name* stack) { push_all(stack); } \
275 etype last() const { return top(); } \
276 }; \
277
278
279 #define define_resource_list(element_type) \
280 define_generic_array(element_type##Array, element_type, ResourceArray) \
281 define_stack(element_type##List, element_type##Array)
282
283 #define define_resource_pointer_list(element_type) \
284 define_generic_array(element_type##Array, element_type *, ResourceArray) \
285 define_stack(element_type##List, element_type##Array)
286
287 #define define_c_heap_list(element_type) \
288 define_generic_array(element_type##Array, element_type, CHeapArray) \
289 define_stack(element_type##List, element_type##Array)
290
291 #define define_c_heap_pointer_list(element_type) \
292 define_generic_array(element_type##Array, element_type *, CHeapArray) \
293 define_stack(element_type##List, element_type##Array)
294
295
296 // Arrays for basic types
297
298 define_array(boolArray, bool) define_stack(boolStack, boolArray)
299 define_array(intArray , int ) define_stack(intStack , intArray )
300
301 // Array for metadata allocation
302
303 template <typename T>
304 class Array: public MetaspaceObj {
305 friend class MetadataFactory;
306 friend class VMStructs;
307 friend class MethodHandleCompiler; // special case
308 friend class WhiteBox;
309 protected:
310 int _length; // the number of array elements
311 T _data[1]; // the array memory
312
313 void initialize(int length) {
314 _length = length;
315 }
316
317 private:
318 // Turn off copy constructor and assignment operator.
319 Array(const Array<T>&);
320 void operator=(const Array<T>&);
321
322 void* operator new(size_t size, ClassLoaderData* loader_data, int length, bool read_only, TRAPS) throw() {
323 size_t word_size = Array::size(length);
324 return (void*) Metaspace::allocate(loader_data, word_size, read_only,
325 MetaspaceObj::array_type(sizeof(T)), THREAD);
326 }
327
328 static size_t byte_sizeof(int length) { return sizeof(Array<T>) + MAX2(length - 1, 0) * sizeof(T); }
329
330 // WhiteBox API helper.
331 // Can't distinguish between array of length 0 and length 1,
332 // will always return 0 in those cases.
333 static int bytes_to_length(size_t bytes) {
334 assert(is_size_aligned(bytes, BytesPerWord), "Must be, for now");
335
336 if (sizeof(Array<T>) >= bytes) {
337 return 0;
338 }
339
340 size_t left = bytes - sizeof(Array<T>);
341 assert(is_size_aligned(left, sizeof(T)), "Must be");
342
343 size_t elements = left / sizeof(T);
344 assert(elements <= (size_t)INT_MAX, "number of elements " SIZE_FORMAT "doesn't fit into an int.", elements);
345
346 int length = (int)elements;
347
348 assert((size_t)size(length) * BytesPerWord == bytes,
349 "Expected: " SIZE_FORMAT " got: " SIZE_FORMAT,
350 bytes, (size_t)size(length) * BytesPerWord);
351
352 return length;
353 }
354
355 explicit Array(int length) : _length(length) {
356 assert(length >= 0, "illegal length");
357 }
358
359 Array(int length, T init) : _length(length) {
360 assert(length >= 0, "illegal length");
361 for (int i = 0; i < length; i++) {
362 _data[i] = init;
363 }
364 }
365
366 public:
367
368 // standard operations
369 int length() const { return _length; }
370 T* data() { return _data; }
371 bool is_empty() const { return length() == 0; }
372
373 int index_of(const T& x) const {
374 int i = length();
375 while (i-- > 0 && _data[i] != x) ;
376
377 return i;
378 }
379
380 // sort the array.
381 bool contains(const T& x) const { return index_of(x) >= 0; }
382
383 T at(int i) const { assert(i >= 0 && i< _length, "oob: 0 <= %d < %d", i, _length); return _data[i]; }
384 void at_put(const int i, const T& x) { assert(i >= 0 && i< _length, "oob: 0 <= %d < %d", i, _length); _data[i] = x; }
385 T* adr_at(const int i) { assert(i >= 0 && i< _length, "oob: 0 <= %d < %d", i, _length); return &_data[i]; }
386 int find(const T& x) { return index_of(x); }
387
388 T at_acquire(const int which) { return OrderAccess::load_acquire(adr_at(which)); }
389 void release_at_put(int which, T contents) { OrderAccess::release_store(adr_at(which), contents); }
390
391 static int size(int length) {
392 return align_size_up(byte_sizeof(length), BytesPerWord) / BytesPerWord;
393 }
394
395 int size() {
396 return size(_length);
397 }
398
399 static int length_offset_in_bytes() { return (int) (offset_of(Array<T>, _length)); }
400 // Note, this offset don't have to be wordSize aligned.
401 static int base_offset_in_bytes() { return (int) (offset_of(Array<T>, _data)); };
402
403 // FIXME: How to handle this?
404 void print_value_on(outputStream* st) const {
405 st->print("Array<T>(" INTPTR_FORMAT ")", p2i(this));
406 }
407
408 #ifndef PRODUCT
409 void print(outputStream* st) {
410 for (int i = 0; i< _length; i++) {
411 st->print_cr("%d: " INTPTR_FORMAT, i, (intptr_t)at(i));
412 }
413 }
414 void print() { print(tty); }
415 #endif // PRODUCT
416 };
417
418
419 #endif // SHARE_VM_UTILITIES_ARRAY_HPP