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_GROWABLEARRAY_HPP
26 #define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/allocation.inline.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include "utilities/top.hpp"
33
34 // A growable array.
35
36 /*************************************************************************/
37 /* */
38 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
39 /* */
40 /* Should you use GrowableArrays to contain handles you must be certain */
41 /* the the GrowableArray does not outlive the HandleMark that contains */
42 /* the handles. Since GrowableArrays are typically resource allocated */
43 /* the following is an example of INCORRECT CODE, */
44 /* */
45 /* ResourceMark rm; */
46 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
47 /* if (blah) { */
48 /* while (...) { */
49 /* HandleMark hm; */
50 /* ... */
51 /* Handle h(THREAD, some_oop); */
52 /* arr->append(h); */
128 _len = initial_len;
129 _max = initial_size;
130 assert(_len >= 0 && _len <= _max, "initial_len too big");
131 _arena = arena;
132 _memflags = mtNone;
133
134 assert(on_arena(), "arena has taken on reserved value 0 or 1");
135 // Relax next assert to allow object allocation on resource area,
136 // on stack or embedded into an other object.
137 assert(allocated_on_arena() || allocated_on_stack(),
138 "growable array must be on arena or on stack if elements are on arena");
139 }
140
141 void* raw_allocate(int elementSize);
142
143 // some uses pass the Thread explicitly for speed (4990299 tuning)
144 void* raw_allocate(Thread* thread, int elementSize) {
145 assert(on_stack(), "fast ResourceObj path only");
146 return (void*)resource_allocate_bytes(thread, elementSize * _max);
147 }
148 };
149
150 template<class E> class GrowableArrayIterator;
151 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator;
152
153 template<class E> class GrowableArray : public GenericGrowableArray {
154 friend class VMStructs;
155
156 private:
157 E* _data; // data array
158
159 void grow(int j);
160 void raw_at_put_grow(int i, const E& p, const E& fill);
161 void clear_and_deallocate();
162 public:
163 GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
164 _data = (E*)raw_allocate(thread, sizeof(E));
165 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
166 }
167
168 GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
169 : GenericGrowableArray(initial_size, 0, C_heap, F) {
170 _data = (E*)raw_allocate(sizeof(E));
171 // Needed for Visual Studio 2012 and older
172 #ifdef _MSC_VER
173 #pragma warning(suppress: 4345)
174 #endif
175 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
176 }
177
178 GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
179 : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
180 _data = (E*)raw_allocate(sizeof(E));
181 int i = 0;
182 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
183 for (; i < _max; i++) ::new ((void*)&_data[i]) E();
184 }
185
186 GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
187 _data = (E*)raw_allocate(sizeof(E));
188 int i = 0;
189 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
190 for (; i < _max; i++) ::new ((void*)&_data[i]) E();
191 }
192
193 GrowableArray() : GenericGrowableArray(2, 0, false) {
194 _data = (E*)raw_allocate(sizeof(E));
195 ::new ((void*)&_data[0]) E();
196 ::new ((void*)&_data[1]) E();
197 }
198
199 // Does nothing for resource and arena objects
200 ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); }
201
202 void clear() { _len = 0; }
203 int length() const { return _len; }
204 int max_length() const { return _max; }
205 void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; }
206 bool is_empty() const { return _len == 0; }
207 bool is_nonempty() const { return _len != 0; }
208 bool is_full() const { return _len == _max; }
209 DEBUG_ONLY(E* data_addr() const { return _data; })
210
211 void print();
212
213 int append(const E& elem) {
214 check_nesting();
215 if (_len == _max) grow(_len);
216 int idx = _len++;
432 }
433 return min;
434 }
435 };
436
437 // Global GrowableArray methods (one instance in the library per each 'E' type).
438
439 template<class E> void GrowableArray<E>::grow(int j) {
440 // grow the array by doubling its size (amortized growth)
441 int old_max = _max;
442 if (_max == 0) _max = 1; // prevent endless loop
443 while (j >= _max) _max = _max*2;
444 // j < _max
445 E* newData = (E*)raw_allocate(sizeof(E));
446 int i = 0;
447 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
448 // Needed for Visual Studio 2012 and older
449 #ifdef _MSC_VER
450 #pragma warning(suppress: 4345)
451 #endif
452 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E();
453 for (i = 0; i < old_max; i++) _data[i].~E();
454 if (on_C_heap() && _data != NULL) {
455 FreeHeap(_data);
456 }
457 _data = newData;
458 }
459
460 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
461 if (i >= _len) {
462 if (i >= _max) grow(i);
463 for (int j = _len; j < i; j++)
464 _data[j] = fill;
465 _len = i+1;
466 }
467 _data[i] = p;
468 }
469
470 // This function clears and deallocate the data in the growable array that
471 // has been allocated on the C heap. It's not public - called by the
472 // destructor.
473 template<class E> void GrowableArray<E>::clear_and_deallocate() {
474 assert(on_C_heap(),
475 "clear_and_deallocate should only be called when on C heap");
476 clear();
477 if (_data != NULL) {
478 for (int i = 0; i < _max; i++) _data[i].~E();
479 FreeHeap(_data);
480 _data = NULL;
481 }
482 }
483
484 template<class E> void GrowableArray<E>::print() {
485 tty->print("Growable Array " INTPTR_FORMAT, this);
486 tty->print(": length %ld (_max %ld) { ", _len, _max);
487 for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
488 tty->print("}\n");
489 }
490
491 // Custom STL-style iterator to iterate over GrowableArrays
492 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
493 template<class E> class GrowableArrayIterator : public StackObj {
494 friend class GrowableArray<E>;
495 template<class F, class UnaryPredicate> friend class GrowableArrayFilterIterator;
496
497 private:
498 const GrowableArray<E>* _array; // GrowableArray we iterate over
548
549 bool operator==(const GrowableArrayIterator<E>& rhs) {
550 assert(_array == rhs._array, "iterator belongs to different array");
551 return _position == rhs._position;
552 }
553
554 bool operator!=(const GrowableArrayIterator<E>& rhs) {
555 assert(_array == rhs._array, "iterator belongs to different array");
556 return _position != rhs._position;
557 }
558
559 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
560 assert(_array == rhs._array, "iterator belongs to different array");
561 return _position == rhs._position;
562 }
563
564 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
565 assert(_array == rhs._array, "iterator belongs to different array");
566 return _position != rhs._position;
567 }
568 };
569
570 #endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
|
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_GROWABLEARRAY_HPP
26 #define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
27
28 #include <limits>
29
30 #include "memory/allocation.hpp"
31 #include "memory/allocation.inline.hpp"
32 #include "utilities/debug.hpp"
33 #include "utilities/globalDefinitions.hpp"
34 #include "utilities/top.hpp"
35 #include "utilities/traits.hpp"
36
37 // A growable array.
38
39 /*************************************************************************/
40 /* */
41 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
42 /* */
43 /* Should you use GrowableArrays to contain handles you must be certain */
44 /* the the GrowableArray does not outlive the HandleMark that contains */
45 /* the handles. Since GrowableArrays are typically resource allocated */
46 /* the following is an example of INCORRECT CODE, */
47 /* */
48 /* ResourceMark rm; */
49 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
50 /* if (blah) { */
51 /* while (...) { */
52 /* HandleMark hm; */
53 /* ... */
54 /* Handle h(THREAD, some_oop); */
55 /* arr->append(h); */
131 _len = initial_len;
132 _max = initial_size;
133 assert(_len >= 0 && _len <= _max, "initial_len too big");
134 _arena = arena;
135 _memflags = mtNone;
136
137 assert(on_arena(), "arena has taken on reserved value 0 or 1");
138 // Relax next assert to allow object allocation on resource area,
139 // on stack or embedded into an other object.
140 assert(allocated_on_arena() || allocated_on_stack(),
141 "growable array must be on arena or on stack if elements are on arena");
142 }
143
144 void* raw_allocate(int elementSize);
145
146 // some uses pass the Thread explicitly for speed (4990299 tuning)
147 void* raw_allocate(Thread* thread, int elementSize) {
148 assert(on_stack(), "fast ResourceObj path only");
149 return (void*)resource_allocate_bytes(thread, elementSize * _max);
150 }
151
152 template<typename T1, typename T2 = T1> class Initializer {
153 STATIC_ASSERT((same_types<T1, T2>::value));
154 public:
155 static void init(T1* data, int from, int to) {
156 for (int i = from; i < to; i++) {
157 ::new((void*) &data[i]) T1();
158 }
159 }
160
161 static void deinit(T1* data, int from, int to) {
162 for (int i = from; i < to; i++) {
163 data[i].~T1();
164 }
165 }
166 };
167 };
168
169 template<class E> class GrowableArrayIterator;
170 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator;
171
172 template<class E> class GrowableArray : public GenericGrowableArray {
173 friend class VMStructs;
174
175 private:
176 E* _data; // data array
177
178 void grow(int j);
179 void raw_at_put_grow(int i, const E& p, const E& fill);
180 void clear_and_deallocate();
181
182 public:
183 GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
184 _data = (E*)raw_allocate(thread, sizeof(E));
185 GenericGrowableArray::Initializer<E>::init(_data, 0, _max);
186 }
187
188 GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
189 : GenericGrowableArray(initial_size, 0, C_heap, F) {
190 _data = (E*)raw_allocate(sizeof(E));
191 // Needed for Visual Studio 2012 and older
192 #ifdef _MSC_VER
193 #pragma warning(suppress: 4345)
194 #endif
195 GenericGrowableArray::Initializer<E>::init(_data, 0, _max);
196 }
197
198 GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
199 : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
200 _data = (E*)raw_allocate(sizeof(E));
201 int i = 0;
202 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
203 GenericGrowableArray::Initializer<E>::init(_data, _len, _max);
204 }
205
206 GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
207 _data = (E*)raw_allocate(sizeof(E));
208 int i = 0;
209 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
210 GenericGrowableArray::Initializer<E>::init(_data, _len, _max);
211 }
212
213 GrowableArray() : GenericGrowableArray(2, 0, false) {
214 _data = (E*)raw_allocate(sizeof(E));
215 GenericGrowableArray::Initializer<E>::init(_data, 0, 2);
216 }
217
218 // Does nothing for resource and arena objects
219 ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); }
220
221 void clear() { _len = 0; }
222 int length() const { return _len; }
223 int max_length() const { return _max; }
224 void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; }
225 bool is_empty() const { return _len == 0; }
226 bool is_nonempty() const { return _len != 0; }
227 bool is_full() const { return _len == _max; }
228 DEBUG_ONLY(E* data_addr() const { return _data; })
229
230 void print();
231
232 int append(const E& elem) {
233 check_nesting();
234 if (_len == _max) grow(_len);
235 int idx = _len++;
451 }
452 return min;
453 }
454 };
455
456 // Global GrowableArray methods (one instance in the library per each 'E' type).
457
458 template<class E> void GrowableArray<E>::grow(int j) {
459 // grow the array by doubling its size (amortized growth)
460 int old_max = _max;
461 if (_max == 0) _max = 1; // prevent endless loop
462 while (j >= _max) _max = _max*2;
463 // j < _max
464 E* newData = (E*)raw_allocate(sizeof(E));
465 int i = 0;
466 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
467 // Needed for Visual Studio 2012 and older
468 #ifdef _MSC_VER
469 #pragma warning(suppress: 4345)
470 #endif
471 GenericGrowableArray::Initializer<E>::init(newData, i, _max);
472 GenericGrowableArray::Initializer<E>::deinit(_data, 0, old_max);
473 if (on_C_heap() && _data != NULL) {
474 FreeHeap(_data);
475 }
476 _data = newData;
477 }
478
479 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
480 if (i >= _len) {
481 if (i >= _max) grow(i);
482 for (int j = _len; j < i; j++)
483 _data[j] = fill;
484 _len = i+1;
485 }
486 _data[i] = p;
487 }
488
489 // This function clears and deallocate the data in the growable array that
490 // has been allocated on the C heap. It's not public - called by the
491 // destructor.
492 template<class E> void GrowableArray<E>::clear_and_deallocate() {
493 assert(on_C_heap(),
494 "clear_and_deallocate should only be called when on C heap");
495 clear();
496 if (_data != NULL) {
497 GenericGrowableArray::Initializer<E>::deinit(_data, 0, _max);
498 FreeHeap(_data);
499 _data = NULL;
500 }
501 }
502
503 template<class E> void GrowableArray<E>::print() {
504 tty->print("Growable Array " INTPTR_FORMAT, this);
505 tty->print(": length %ld (_max %ld) { ", _len, _max);
506 for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
507 tty->print("}\n");
508 }
509
510 // Custom STL-style iterator to iterate over GrowableArrays
511 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
512 template<class E> class GrowableArrayIterator : public StackObj {
513 friend class GrowableArray<E>;
514 template<class F, class UnaryPredicate> friend class GrowableArrayFilterIterator;
515
516 private:
517 const GrowableArray<E>* _array; // GrowableArray we iterate over
567
568 bool operator==(const GrowableArrayIterator<E>& rhs) {
569 assert(_array == rhs._array, "iterator belongs to different array");
570 return _position == rhs._position;
571 }
572
573 bool operator!=(const GrowableArrayIterator<E>& rhs) {
574 assert(_array == rhs._array, "iterator belongs to different array");
575 return _position != rhs._position;
576 }
577
578 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
579 assert(_array == rhs._array, "iterator belongs to different array");
580 return _position == rhs._position;
581 }
582
583 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
584 assert(_array == rhs._array, "iterator belongs to different array");
585 return _position != rhs._position;
586 }
587 };
588
589 template <typename T1>
590 class GenericGrowableArray::Initializer<T1,
591 typename enable_if<std::numeric_limits<T1>::is_integer
592 || is_floating_point<T1>::value
593 || is_pointer<T1>::value, T1>::type> {
594 public:
595 static void init(T1* data, int from, int to) {}
596 static void deinit(T1* data, int from, int to) {}
597 };
598
599 #endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP
|