8247755: Leaner and more versatile GrowableArray classes
Reviewed-by: kbarrett, coleenp
diff --git a/src/hotspot/share/memory/iterator.hpp b/src/hotspot/share/memory/iterator.hpp
index 520acf3..df351f1 100644
--- a/src/hotspot/share/memory/iterator.hpp
+++ b/src/hotspot/share/memory/iterator.hpp
@@ -347,6 +347,12 @@
}
};
+template <typename E>
+class CompareClosure : public Closure {
+public:
+ virtual int do_compare(const E&, const E&) = 0;
+};
+
// Dispatches to the non-virtual functions if OopClosureType has
// a concrete implementation, otherwise a virtual call is taken.
class Devirtualizer {
diff --git a/src/hotspot/share/memory/metaspaceShared.cpp b/src/hotspot/share/memory/metaspaceShared.cpp
index 135979d..ab948f6 100644
--- a/src/hotspot/share/memory/metaspaceShared.cpp
+++ b/src/hotspot/share/memory/metaspaceShared.cpp
@@ -456,10 +456,10 @@
}
}
-static GrowableArray<Handle>* _extra_interned_strings = NULL;
+static GrowableArrayCHeap<Handle, mtClassShared>* _extra_interned_strings = NULL;
void MetaspaceShared::read_extra_data(const char* filename, TRAPS) {
- _extra_interned_strings = new (ResourceObj::C_HEAP, mtClassShared) GrowableArray<Handle>(10000, mtClassShared);
+ _extra_interned_strings = new GrowableArrayCHeap<Handle, mtClassShared>(10000);
HashtableTextDump reader(filename);
reader.check_version("VERSION: 1.0");
diff --git a/src/hotspot/share/runtime/arguments.cpp b/src/hotspot/share/runtime/arguments.cpp
index dd0797a..c075d88 100644
--- a/src/hotspot/share/runtime/arguments.cpp
+++ b/src/hotspot/share/runtime/arguments.cpp
@@ -3307,7 +3307,7 @@
// allocated memory is deleted by the destructor. If this method
// returns anything other than JNI_OK, then this object is in a
// partially constructed state, and should be abandoned.
- jint set_args(GrowableArray<JavaVMOption>* options) {
+ jint set_args(const GrowableArrayView<JavaVMOption>* options) {
_is_set = true;
JavaVMOption* options_arr = NEW_C_HEAP_ARRAY_RETURN_NULL(
JavaVMOption, options->length(), mtArguments);
@@ -3365,23 +3365,21 @@
assert(vm_options_file_pos != -1, "vm_options_file_pos should be set");
int length = args->nOptions + args_to_insert->nOptions - 1;
- GrowableArray<JavaVMOption> *options = new (ResourceObj::C_HEAP, mtArguments)
- GrowableArray<JavaVMOption>(length, mtArguments); // Construct new option array
+ // Construct new option array
+ GrowableArrayCHeap<JavaVMOption, mtArguments> options(length);
for (int i = 0; i < args->nOptions; i++) {
if (i == vm_options_file_pos) {
// insert the new options starting at the same place as the
// -XX:VMOptionsFile option
for (int j = 0; j < args_to_insert->nOptions; j++) {
- options->push(args_to_insert->options[j]);
+ options.push(args_to_insert->options[j]);
}
} else {
- options->push(args->options[i]);
+ options.push(args->options[i]);
}
}
// make into options array
- jint result = set_args(options);
- delete options;
- return result;
+ return set_args(&options);
}
};
@@ -3478,7 +3476,8 @@
}
jint Arguments::parse_options_buffer(const char* name, char* buffer, const size_t buf_len, ScopedVMInitArgs* vm_args) {
- GrowableArray<JavaVMOption> *options = new (ResourceObj::C_HEAP, mtArguments) GrowableArray<JavaVMOption>(2, mtArguments); // Construct option array
+ // Construct option array
+ GrowableArrayCHeap<JavaVMOption, mtArguments> options(2);
// some pointers to help with parsing
char *buffer_end = buffer + buf_len;
@@ -3518,7 +3517,6 @@
// did not see closing quote
jio_fprintf(defaultStream::error_stream(),
"Unmatched quote in %s\n", name);
- delete options;
return JNI_ERR;
}
} else {
@@ -3534,16 +3532,13 @@
option.optionString = opt_hd;
option.extraInfo = NULL;
- options->append(option); // Fill in option
+ options.append(option); // Fill in option
rd++; // Advance to next character
}
// Fill out JavaVMInitArgs structure.
- jint status = vm_args->set_args(options);
-
- delete options;
- return status;
+ return vm_args->set_args(&options);
}
jint Arguments::set_shared_spaces_flags_and_archive_paths() {
diff --git a/src/hotspot/share/runtime/vmStructs.cpp b/src/hotspot/share/runtime/vmStructs.cpp
index b3ae355..2037696 100644
--- a/src/hotspot/share/runtime/vmStructs.cpp
+++ b/src/hotspot/share/runtime/vmStructs.cpp
@@ -532,9 +532,8 @@
/* GrowableArrays */ \
/*******************/ \
\
- nonstatic_field(GenericGrowableArray, _len, int) \
- nonstatic_field(GenericGrowableArray, _max, int) \
- nonstatic_field(GenericGrowableArray, _arena, Arena*) \
+ nonstatic_field(GrowableArrayBase, _len, int) \
+ nonstatic_field(GrowableArrayBase, _max, int) \
nonstatic_field(GrowableArray<int>, _data, int*) \
\
/********************************/ \
@@ -1339,7 +1338,7 @@
declare_toplevel_type(SystemDictionary) \
declare_toplevel_type(vmSymbols) \
\
- declare_toplevel_type(GenericGrowableArray) \
+ declare_toplevel_type(GrowableArrayBase) \
declare_toplevel_type(GrowableArray<int>) \
declare_toplevel_type(Arena) \
declare_type(ResourceArea, Arena) \
diff --git a/src/hotspot/share/utilities/globalDefinitions.hpp b/src/hotspot/share/utilities/globalDefinitions.hpp
index 279b0e2..4f86c97 100644
--- a/src/hotspot/share/utilities/globalDefinitions.hpp
+++ b/src/hotspot/share/utilities/globalDefinitions.hpp
@@ -432,6 +432,11 @@
#define CAST_TO_FN_PTR(func_type, value) (reinterpret_cast<func_type>(value))
#define CAST_FROM_FN_PTR(new_type, func_ptr) ((new_type)((address_word)(func_ptr)))
+// Need the correct linkage to call qsort without warnings
+extern "C" {
+ typedef int (*_sort_Fn)(const void *, const void *);
+}
+
// Unsigned byte types for os and stream.hpp
// Unsigned one, two, four and eigth byte quantities used for describing
diff --git a/src/hotspot/share/utilities/growableArray.cpp b/src/hotspot/share/utilities/growableArray.cpp
index 0765298..fc0ab6e 100644
--- a/src/hotspot/share/utilities/growableArray.cpp
+++ b/src/hotspot/share/utilities/growableArray.cpp
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2020, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -28,36 +28,65 @@
#include "runtime/thread.inline.hpp"
#include "utilities/growableArray.hpp"
-#ifdef ASSERT
-void GenericGrowableArray::set_nesting() {
- if (on_stack()) {
- _nesting = Thread::current()->resource_area()->nesting();
- }
+void* GrowableArrayResourceAllocator::allocate(int max, int elementSize) {
+ assert(max >= 0, "integer overflow");
+ size_t byte_size = elementSize * (size_t) max;
+
+ return (void*)resource_allocate_bytes(byte_size);
}
-void GenericGrowableArray::check_nesting() {
+void* GrowableArrayArenaAllocator::allocate(int max, int element_size, Arena* arena) {
+ assert(max >= 0, "integer overflow");
+ size_t byte_size = element_size * (size_t) max;
+
+ return arena->Amalloc(byte_size);
+}
+
+void* GrowableArrayCHeapAllocator::allocate(int max, int element_size, MEMFLAGS memflags) {
+ assert(max >= 0, "integer overflow");
+ size_t byte_size = element_size * (size_t) max;
+
+ // memory type has to be specified for C heap allocation
+ assert(memflags != mtNone, "memory type not specified for C heap object");
+ return (void*)AllocateHeap(byte_size, memflags);
+}
+
+void GrowableArrayCHeapAllocator::deallocate(void* elements) {
+ FreeHeap(elements);
+}
+
+#ifdef ASSERT
+
+GrowableArrayNestingCheck::GrowableArrayNestingCheck(bool on_stack) :
+ _nesting(on_stack ? Thread::current()->resource_area()->nesting() : 0) {
+}
+
+void GrowableArrayNestingCheck::on_stack_alloc() const {
// Check for insidious allocation bug: if a GrowableArray overflows, the
// grown array must be allocated under the same ResourceMark as the original.
// Otherwise, the _data array will be deallocated too early.
- if (on_stack() &&
- _nesting != Thread::current()->resource_area()->nesting()) {
+ if (_nesting != Thread::current()->resource_area()->nesting()) {
fatal("allocation bug: GrowableArray could grow within nested ResourceMark");
}
}
-#endif
-void* GenericGrowableArray::raw_allocate(int elementSize) {
- assert(_max >= 0, "integer overflow");
- size_t byte_size = elementSize * (size_t) _max;
- if (on_stack()) {
- return (void*)resource_allocate_bytes(byte_size);
- } else if (on_C_heap()) {
- return (void*)AllocateHeap(byte_size, _memflags);
- } else {
- return _arena->Amalloc(byte_size);
+void GrowableArrayMetadata::init_checks(const GrowableArrayBase* array) const {
+ // Stack allocated arrays support all three element allocation locations
+ if (array->allocated_on_stack()) {
+ return;
}
+
+ // Otherwise there's a strict one-to-one mapping
+ assert(on_C_heap() == array->allocated_on_C_heap(),
+ "growable array must be C heap allocated if elements are");
+ assert(on_stack() == array->allocated_on_res_area(),
+ "growable array must be resource allocated if elements are");
+ assert(on_arena() == array->allocated_on_arena(),
+ "growable array must be arena allocated if elements are");
}
-void GenericGrowableArray::free_C_heap(void* elements) {
- FreeHeap(elements);
+void GrowableArrayMetadata::on_stack_alloc_check() const {
+ _nesting_check.on_stack_alloc();
}
+
+#endif // ASSERT
diff --git a/src/hotspot/share/utilities/growableArray.hpp b/src/hotspot/share/utilities/growableArray.hpp
index b54a8d8..479e6ec 100644
--- a/src/hotspot/share/utilities/growableArray.hpp
+++ b/src/hotspot/share/utilities/growableArray.hpp
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 2020, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -26,7 +26,7 @@
#define SHARE_UTILITIES_GROWABLEARRAY_HPP
#include "memory/allocation.hpp"
-#include "oops/oop.hpp"
+#include "memory/iterator.hpp"
#include "utilities/debug.hpp"
#include "utilities/globalDefinitions.hpp"
#include "utilities/ostream.hpp"
@@ -39,7 +39,7 @@
/* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
/* */
/* Should you use GrowableArrays to contain handles you must be certain */
-/* the the GrowableArray does not outlive the HandleMark that contains */
+/* that the GrowableArray does not outlive the HandleMark that contains */
/* the handles. Since GrowableArrays are typically resource allocated */
/* the following is an example of INCORRECT CODE, */
/* */
@@ -59,174 +59,71 @@
/* } */
/* */
/* If the GrowableArrays you are creating is C_Heap allocated then it */
-/* hould not old handles since the handles could trivially try and */
+/* should not hold handles since the handles could trivially try and */
/* outlive their HandleMark. In some situations you might need to do */
/* this and it would be legal but be very careful and see if you can do */
/* the code in some other manner. */
/* */
/*************************************************************************/
-// To call default constructor the placement operator new() is used.
-// It should be empty (it only returns the passed void* pointer).
-// The definition of placement operator new(size_t, void*) in the <new>.
+// Non-template base class responsible for handling the length and max.
-#include <new>
-// Need the correct linkage to call qsort without warnings
-extern "C" {
- typedef int (*_sort_Fn)(const void *, const void *);
-}
-
-class GenericGrowableArray : public ResourceObj {
+class GrowableArrayBase : public ResourceObj {
friend class VMStructs;
- protected:
- int _len; // current length
- int _max; // maximum length
- Arena* _arena; // Indicates where allocation occurs:
- // 0 means default ResourceArea
- // 1 means on C heap
- // otherwise, allocate in _arena
+protected:
+ // Current number of accessible elements
+ int _len;
+ // Current number of allocated elements
+ int _max;
- MEMFLAGS _memflags; // memory type if allocation in C heap
-
-#ifdef ASSERT
- int _nesting; // resource area nesting at creation
- void set_nesting();
- void check_nesting();
-#else
-#define set_nesting();
-#define check_nesting();
-#endif
-
- // Where are we going to allocate memory?
- bool on_C_heap() { return _arena == (Arena*)1; }
- bool on_stack () { return _arena == NULL; }
- bool on_arena () { return _arena > (Arena*)1; }
-
- // This GA will use the resource stack for storage if c_heap==false,
- // Else it will use the C heap. Use clear_and_deallocate to avoid leaks.
- GenericGrowableArray(int initial_size, int initial_len, MEMFLAGS flags) {
- _len = initial_len;
- _max = initial_size;
- _memflags = flags;
-
+ GrowableArrayBase(int initial_max, int initial_len) :
+ _len(initial_len),
+ _max(initial_max) {
assert(_len >= 0 && _len <= _max, "initial_len too big");
-
- const bool c_heap = flags != mtNone;
- _arena = (c_heap ? (Arena*)1 : NULL);
- set_nesting();
- assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are");
- assert(!on_stack() ||
- (allocated_on_res_area() || allocated_on_stack()),
- "growable array must be on stack if elements are not on arena and not on C heap");
}
- // This GA will use the given arena for storage.
- // Consider using new(arena) GrowableArray<T> to allocate the header.
- GenericGrowableArray(Arena* arena, int initial_size, int initial_len) {
- _len = initial_len;
- _max = initial_size;
- assert(_len >= 0 && _len <= _max, "initial_len too big");
- _arena = arena;
- _memflags = mtNone;
-
- assert(on_arena(), "arena has taken on reserved value 0 or 1");
- // Relax next assert to allow object allocation on resource area,
- // on stack or embedded into an other object.
- assert(allocated_on_arena() || allocated_on_stack(),
- "growable array must be on arena or on stack if elements are on arena");
- }
-
- void* raw_allocate(int elementSize);
-
- void free_C_heap(void* elements);
-};
-
-template<class E> class GrowableArrayIterator;
-template<class E, class UnaryPredicate> class GrowableArrayFilterIterator;
-
-template<class E>
-class CompareClosure : public Closure {
-public:
- virtual int do_compare(const E&, const E&) = 0;
-};
-
-template<class E> class GrowableArray : public GenericGrowableArray {
- friend class VMStructs;
-
- private:
- E* _data; // data array
-
- void grow(int j);
- void raw_at_put_grow(int i, const E& p, const E& fill);
- void clear_and_deallocate();
+ ~GrowableArrayBase() {}
public:
- GrowableArray(int initial_size, MEMFLAGS F = mtNone)
- : GenericGrowableArray(initial_size, 0, F) {
- _data = (E*)raw_allocate(sizeof(E));
-// Needed for Visual Studio 2012 and older
-#ifdef _MSC_VER
-#pragma warning(suppress: 4345)
-#endif
- for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
- }
-
- GrowableArray(int initial_size, int initial_len, const E& filler, MEMFLAGS memflags = mtNone)
- : GenericGrowableArray(initial_size, initial_len, memflags) {
- _data = (E*)raw_allocate(sizeof(E));
- int i = 0;
- for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
- for (; i < _max; i++) ::new ((void*)&_data[i]) E();
- }
-
- // Watch out, if filler was generated by a constructor, the destuctor might
- // be called on the original object invalidating all the copies made here.
- // Carefully design the copy constructor.
- GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) :
- GenericGrowableArray(arena, initial_size, initial_len) {
- _data = (E*)raw_allocate(sizeof(E));
- int i = 0;
- for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
- for (; i < _max; i++) ::new ((void*)&_data[i]) E();
- }
-
- GrowableArray() : GenericGrowableArray(2, 0, mtNone) {
- _data = (E*)raw_allocate(sizeof(E));
- ::new ((void*)&_data[0]) E();
- ::new ((void*)&_data[1]) E();
- }
-
- // Does nothing for resource and arena objects
- ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); }
-
- void clear() { _len = 0; }
int length() const { return _len; }
int max_length() const { return _max; }
- void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; }
+
bool is_empty() const { return _len == 0; }
bool is_nonempty() const { return _len != 0; }
bool is_full() const { return _len == _max; }
- DEBUG_ONLY(E* data_addr() const { return _data; })
- void print();
-
- int append(const E& elem) {
- check_nesting();
- if (_len == _max) grow(_len);
- int idx = _len++;
- _data[idx] = elem;
- return idx;
+ void clear() { _len = 0; }
+ void trunc_to(int length) {
+ assert(length <= _len,"cannot increase length");
+ _len = length;
}
+};
- bool append_if_missing(const E& elem) {
- // Returns TRUE if elem is added.
- bool missed = !contains(elem);
- if (missed) append(elem);
- return missed;
- }
+template <typename E> class GrowableArrayIterator;
+template <typename E, typename UnaryPredicate> class GrowableArrayFilterIterator;
+// Extends GrowableArrayBase with a typed data array.
+//
+// E: Element type
+//
+// The "view" adds function that don't grow or deallocate
+// the _data array, so there's no need for an allocator.
+//
+// The "view" can be used to type erase the allocator classes
+// of GrowableArrayWithAllocator.
+template <typename E>
+class GrowableArrayView : public GrowableArrayBase {
+protected:
+ E* _data; // data array
+
+ GrowableArrayView<E>(E* data, int initial_max, int initial_len) :
+ GrowableArrayBase(initial_max, initial_len), _data(data) {}
+
+ ~GrowableArrayView() {}
+
+public:
E& at(int i) {
assert(0 <= i && i < _len, "illegal index");
return _data[i];
@@ -264,8 +161,6 @@
return GrowableArrayIterator<E>(this, length());
}
- void push(const E& elem) { append(elem); }
-
E pop() {
assert(_len > 0, "empty list");
return _data[--_len];
@@ -276,24 +171,6 @@
_data[i] = elem;
}
- E at_grow(int i, const E& fill = E()) {
- assert(0 <= i, "negative index");
- check_nesting();
- if (i >= _len) {
- if (i >= _max) grow(i);
- for (int j = _len; j <= i; j++)
- _data[j] = fill;
- _len = i+1;
- }
- return _data[i];
- }
-
- void at_put_grow(int i, const E& elem, const E& fill = E()) {
- assert(0 <= i, "negative index");
- check_nesting();
- raw_at_put_grow(i, elem, fill);
- }
-
bool contains(const E& elem) const {
for (int i = 0; i < _len; i++) {
if (_data[i] == elem) return true;
@@ -357,63 +234,14 @@
}
}
- // inserts the given element before the element at index i
- void insert_before(const int idx, const E& elem) {
- assert(0 <= idx && idx <= _len, "illegal index");
- check_nesting();
- if (_len == _max) grow(_len);
- for (int j = _len - 1; j >= idx; j--) {
- _data[j + 1] = _data[j];
- }
- _len++;
- _data[idx] = elem;
- }
-
- void insert_before(const int idx, const GrowableArray<E>* array) {
- assert(0 <= idx && idx <= _len, "illegal index");
- check_nesting();
- int array_len = array->length();
- int new_len = _len + array_len;
- if (new_len >= _max) grow(new_len);
-
- for (int j = _len - 1; j >= idx; j--) {
- _data[j + array_len] = _data[j];
- }
-
- for (int j = 0; j < array_len; j++) {
- _data[idx + j] = array->_data[j];
- }
-
- _len += array_len;
- }
-
- void appendAll(const GrowableArray<E>* l) {
- for (int i = 0; i < l->_len; i++) {
- raw_at_put_grow(_len, l->_data[i], E());
- }
- }
-
- void sort(int f(E*,E*)) {
+ void sort(int f(E*, E*)) {
qsort(_data, length(), sizeof(E), (_sort_Fn)f);
}
// sort by fixed-stride sub arrays:
- void sort(int f(E*,E*), int stride) {
+ void sort(int f(E*, E*), int stride) {
qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
}
- // Binary search and insertion utility. Search array for element
- // matching key according to the static compare function. Insert
- // that element is not already in the list. Assumes the list is
- // already sorted according to compare function.
- template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
- bool found;
- int location = find_sorted<E, compare>(key, found);
- if (!found) {
- insert_before(location, key);
- }
- return at(location);
- }
-
template <typename K, int compare(const K&, const E&)> int find_sorted(const K& key, bool& found) {
found = false;
int min = 0;
@@ -435,16 +263,7 @@
return min;
}
- E insert_sorted(CompareClosure<E>* cc, const E& key) {
- bool found;
- int location = find_sorted(cc, key, found);
- if (!found) {
- insert_before(location, key);
- }
- return at(location);
- }
-
- template<typename K>
+ template <typename K>
int find_sorted(CompareClosure<E>* cc, const K& key, bool& found) {
found = false;
int min = 0;
@@ -465,80 +284,442 @@
}
return min;
}
-};
-// Global GrowableArray methods (one instance in the library per each 'E' type).
-
-template<class E> void GrowableArray<E>::grow(int j) {
- int old_max = _max;
- // grow the array by increasing _max to the first power of two larger than the size we need
- _max = next_power_of_2((uint32_t)j);
- // j < _max
- E* newData = (E*)raw_allocate(sizeof(E));
- int i = 0;
- for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
-// Needed for Visual Studio 2012 and older
-#ifdef _MSC_VER
-#pragma warning(suppress: 4345)
-#endif
- for ( ; i < _max; i++) ::new ((void*)&newData[i]) E();
- for (i = 0; i < old_max; i++) _data[i].~E();
- if (on_C_heap() && _data != NULL) {
- free_C_heap(_data);
- }
- _data = newData;
-}
-
-template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
- if (i >= _len) {
- if (i >= _max) grow(i);
- for (int j = _len; j < i; j++)
- _data[j] = fill;
- _len = i+1;
- }
- _data[i] = p;
-}
-
-// This function clears and deallocate the data in the growable array that
-// has been allocated on the C heap. It's not public - called by the
-// destructor.
-template<class E> void GrowableArray<E>::clear_and_deallocate() {
- assert(on_C_heap(),
- "clear_and_deallocate should only be called when on C heap");
- clear();
- if (_data != NULL) {
- for (int i = 0; i < _max; i++) _data[i].~E();
- free_C_heap(_data);
- _data = NULL;
- }
-}
-
-template<class E> void GrowableArray<E>::print() {
+ void print() {
tty->print("Growable Array " INTPTR_FORMAT, this);
tty->print(": length %ld (_max %ld) { ", _len, _max);
- for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
+ for (int i = 0; i < _len; i++) {
+ tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i]));
+ }
tty->print("}\n");
+ }
+};
+
+// GrowableArrayWithAllocator extends the "view" with
+// the capability to grow and deallocate the data array.
+//
+// The allocator responsibility is delegated to the sub-class.
+//
+// Derived: The sub-class responsible for allocation / deallocation
+// - E* Derived::allocate() - member function responsible for allocation
+// - void Derived::deallocate(E*) - member function responsible for deallocation
+template <typename E, typename Derived>
+class GrowableArrayWithAllocator : public GrowableArrayView<E> {
+ friend class VMStructs;
+
+ void grow(int j);
+
+protected:
+ GrowableArrayWithAllocator(E* data, int initial_max) :
+ GrowableArrayView<E>(data, initial_max, 0) {
+ for (int i = 0; i < initial_max; i++) {
+ ::new ((void*)&data[i]) E();
+ }
+ }
+
+ GrowableArrayWithAllocator(E* data, int initial_max, int initial_len, const E& filler) :
+ GrowableArrayView<E>(data, initial_max, initial_len) {
+ int i = 0;
+ for (; i < initial_len; i++) {
+ ::new ((void*)&data[i]) E(filler);
+ }
+ for (; i < initial_max; i++) {
+ ::new ((void*)&data[i]) E();
+ }
+ }
+
+ ~GrowableArrayWithAllocator() {}
+
+public:
+ int append(const E& elem) {
+ if (this->_len == this->_max) grow(this->_len);
+ int idx = this->_len++;
+ this->_data[idx] = elem;
+ return idx;
+ }
+
+ bool append_if_missing(const E& elem) {
+ // Returns TRUE if elem is added.
+ bool missed = !this->contains(elem);
+ if (missed) append(elem);
+ return missed;
+ }
+
+ void push(const E& elem) { append(elem); }
+
+ E at_grow(int i, const E& fill = E()) {
+ assert(0 <= i, "negative index");
+ if (i >= this->_len) {
+ if (i >= this->_max) grow(i);
+ for (int j = this->_len; j <= i; j++)
+ this->_data[j] = fill;
+ this->_len = i+1;
+ }
+ return this->_data[i];
+ }
+
+ void at_put_grow(int i, const E& elem, const E& fill = E()) {
+ assert(0 <= i, "negative index");
+ if (i >= this->_len) {
+ if (i >= this->_max) grow(i);
+ for (int j = this->_len; j < i; j++)
+ this->_data[j] = fill;
+ this->_len = i+1;
+ }
+ this->_data[i] = elem;
+ }
+
+ // inserts the given element before the element at index i
+ void insert_before(const int idx, const E& elem) {
+ assert(0 <= idx && idx <= this->_len, "illegal index");
+ if (this->_len == this->_max) grow(this->_len);
+ for (int j = this->_len - 1; j >= idx; j--) {
+ this->_data[j + 1] = this->_data[j];
+ }
+ this->_len++;
+ this->_data[idx] = elem;
+ }
+
+ void insert_before(const int idx, const GrowableArrayView<E>* array) {
+ assert(0 <= idx && idx <= this->_len, "illegal index");
+ int array_len = array->length();
+ int new_len = this->_len + array_len;
+ if (new_len >= this->_max) grow(new_len);
+
+ for (int j = this->_len - 1; j >= idx; j--) {
+ this->_data[j + array_len] = this->_data[j];
+ }
+
+ for (int j = 0; j < array_len; j++) {
+ this->_data[idx + j] = array->at(j);
+ }
+
+ this->_len += array_len;
+ }
+
+ void appendAll(const GrowableArrayView<E>* l) {
+ for (int i = 0; i < l->length(); i++) {
+ this->at_put_grow(this->_len, l->at(i), E());
+ }
+ }
+
+ // Binary search and insertion utility. Search array for element
+ // matching key according to the static compare function. Insert
+ // that element is not already in the list. Assumes the list is
+ // already sorted according to compare function.
+ template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
+ bool found;
+ int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
+ if (!found) {
+ insert_before(location, key);
+ }
+ return this->at(location);
+ }
+
+ E insert_sorted(CompareClosure<E>* cc, const E& key) {
+ bool found;
+ int location = find_sorted(cc, key, found);
+ if (!found) {
+ insert_before(location, key);
+ }
+ return this->at(location);
+ }
+
+ void clear_and_deallocate();
+};
+
+template <typename E, typename Derived>
+void GrowableArrayWithAllocator<E, Derived>::grow(int j) {
+ int old_max = this->_max;
+ // grow the array by increasing _max to the first power of two larger than the size we need
+ this->_max = next_power_of_2((uint32_t)j);
+ // j < _max
+ E* newData = static_cast<Derived*>(this)->allocate();
+ int i = 0;
+ for ( ; i < this->_len; i++) ::new ((void*)&newData[i]) E(this->_data[i]);
+ for ( ; i < this->_max; i++) ::new ((void*)&newData[i]) E();
+ for (i = 0; i < old_max; i++) this->_data[i].~E();
+ if (this->_data != NULL) {
+ static_cast<Derived*>(this)->deallocate(this->_data);
+ }
+ this->_data = newData;
}
+template <typename E, typename Derived>
+void GrowableArrayWithAllocator<E, Derived>::clear_and_deallocate() {
+ if (this->_data != NULL) {
+ for (int i = 0; i < this->_max; i++) {
+ this->_data[i].~E();
+ }
+ static_cast<Derived*>(this)->deallocate(this->_data);
+ this->_data = NULL;
+ }
+ this->_len = 0;
+ this->_max = 0;
+}
+
+class GrowableArrayResourceAllocator {
+public:
+ static void* allocate(int max, int element_size);
+};
+
+// Arena allocator
+class GrowableArrayArenaAllocator {
+public:
+ static void* allocate(int max, int element_size, Arena* arena);
+};
+
+// CHeap allocator
+class GrowableArrayCHeapAllocator {
+public:
+ static void* allocate(int max, int element_size, MEMFLAGS memflags);
+ static void deallocate(void* mem);
+};
+
+#ifdef ASSERT
+
+// Checks resource allocation nesting
+class GrowableArrayNestingCheck {
+ // resource area nesting at creation
+ int _nesting;
+
+public:
+ GrowableArrayNestingCheck(bool on_stack);
+
+ void on_stack_alloc() const;
+};
+
+#endif // ASSERT
+
+// Encodes where the backing array is allocated
+// and performs necessary checks.
+class GrowableArrayMetadata {
+ uintptr_t _bits;
+
+ // resource area nesting at creation
+ debug_only(GrowableArrayNestingCheck _nesting_check;)
+
+ uintptr_t bits(MEMFLAGS memflags) const {
+ if (memflags == mtNone) {
+ // Stack allocation
+ return 0;
+ }
+
+ // CHeap allocation
+ return (uintptr_t(memflags) << 1) | 1;
+ }
+
+ uintptr_t bits(Arena* arena) const {
+ return uintptr_t(arena);
+ }
+
+public:
+ GrowableArrayMetadata(Arena* arena) :
+ _bits(bits(arena))
+ debug_only(COMMA _nesting_check(on_stack())) {
+ }
+
+ GrowableArrayMetadata(MEMFLAGS memflags) :
+ _bits(bits(memflags))
+ debug_only(COMMA _nesting_check(on_stack())) {
+ }
+
+#ifdef ASSERT
+ GrowableArrayMetadata(const GrowableArrayMetadata& other) :
+ _bits(other._bits),
+ _nesting_check(other._nesting_check) {
+ assert(!on_C_heap(), "Copying of CHeap arrays not supported");
+ assert(!other.on_C_heap(), "Copying of CHeap arrays not supported");
+ }
+
+ GrowableArrayMetadata& operator=(const GrowableArrayMetadata& other) {
+ _bits = other._bits;
+ _nesting_check = other._nesting_check;
+ assert(!on_C_heap(), "Assignment of CHeap arrays not supported");
+ assert(!other.on_C_heap(), "Assignment of CHeap arrays not supported");
+ return *this;
+ }
+
+ void init_checks(const GrowableArrayBase* array) const;
+ void on_stack_alloc_check() const;
+#endif // ASSERT
+
+ bool on_C_heap() const { return (_bits & 1) == 1; }
+ bool on_stack () const { return _bits == 0; }
+ bool on_arena () const { return (_bits & 1) == 0 && _bits != 0; }
+
+ Arena* arena() const { return (Arena*)_bits; }
+ MEMFLAGS memflags() const { return MEMFLAGS(_bits >> 1); }
+};
+
+// THE GrowableArray.
+//
+// Supports multiple allocation strategies:
+// - Resource stack allocation: if memflags == mtNone
+// - CHeap allocation: if memflags != mtNone
+// - Arena allocation: if an arena is provided
+//
+// There are some drawbacks of using GrowableArray, that are removed in some
+// of the other implementations of GrowableArrayWithAllocator sub-classes:
+//
+// Memory overhead: The multiple allocation strategies uses extra metadata
+// embedded in the instance.
+//
+// Strict allocation locations: There are rules about where the GrowableArray
+// instance is allocated, that depends on where the data array is allocated.
+// See: init_checks.
+
+template <typename E>
+class GrowableArray : public GrowableArrayWithAllocator<E, GrowableArray<E> > {
+ friend class GrowableArrayWithAllocator<E, GrowableArray<E> >;
+ friend class GrowableArrayTest;
+
+ static E* allocate(int max) {
+ return (E*)GrowableArrayResourceAllocator::allocate(max, sizeof(E));
+ }
+
+ static E* allocate(int max, MEMFLAGS memflags) {
+ if (memflags != mtNone) {
+ return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), memflags);
+ }
+
+ return (E*)GrowableArrayResourceAllocator::allocate(max, sizeof(E));
+ }
+
+ static E* allocate(int max, Arena* arena) {
+ return (E*)GrowableArrayArenaAllocator::allocate(max, sizeof(E), arena);
+ }
+
+ GrowableArrayMetadata _metadata;
+
+ void init_checks() const { debug_only(_metadata.init_checks(this);) }
+
+ // Where are we going to allocate memory?
+ bool on_C_heap() const { return _metadata.on_C_heap(); }
+ bool on_stack () const { return _metadata.on_stack(); }
+ bool on_arena () const { return _metadata.on_arena(); }
+
+ E* allocate() {
+ if (on_stack()) {
+ debug_only(_metadata.on_stack_alloc_check());
+ return allocate(this->_max);
+ }
+
+ if (on_C_heap()) {
+ return allocate(this->_max, _metadata.memflags());
+ }
+
+ assert(on_arena(), "Sanity");
+ return allocate(this->_max, _metadata.arena());
+ }
+
+ void deallocate(E* mem) {
+ if (on_C_heap()) {
+ GrowableArrayCHeapAllocator::deallocate(mem);
+ }
+ }
+
+public:
+ GrowableArray(int initial_max = 2, MEMFLAGS memflags = mtNone) :
+ GrowableArrayWithAllocator<E, GrowableArray<E> >(
+ allocate(initial_max, memflags),
+ initial_max),
+ _metadata(memflags) {
+ init_checks();
+ }
+
+ GrowableArray(int initial_max, int initial_len, const E& filler, MEMFLAGS memflags = mtNone) :
+ GrowableArrayWithAllocator<E, GrowableArray<E> >(
+ allocate(initial_max, memflags),
+ initial_max, initial_len, filler),
+ _metadata(memflags) {
+ init_checks();
+ }
+
+ GrowableArray(Arena* arena, int initial_max, int initial_len, const E& filler) :
+ GrowableArrayWithAllocator<E, GrowableArray<E> >(
+ allocate(initial_max, arena),
+ initial_max, initial_len, filler),
+ _metadata(arena) {
+ init_checks();
+ }
+
+ ~GrowableArray() {
+ if (on_C_heap()) {
+ this->clear_and_deallocate();
+ }
+ }
+};
+
+// Leaner GrowableArray for CHeap backed data arrays, with compile-time decided MEMFLAGS.
+template <typename E, MEMFLAGS F>
+class GrowableArrayCHeap : public GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> > {
+ friend class GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> >;
+
+ STATIC_ASSERT(F != mtNone);
+
+ static E* allocate(int max, MEMFLAGS flags) {
+ if (max == 0) {
+ return NULL;
+ }
+
+ return (E*)GrowableArrayCHeapAllocator::allocate(max, sizeof(E), flags);
+ }
+
+ NONCOPYABLE(GrowableArrayCHeap);
+
+ E* allocate() {
+ return allocate(this->_max, F);
+ }
+
+ void deallocate(E* mem) {
+ GrowableArrayCHeapAllocator::deallocate(mem);
+ }
+
+public:
+ GrowableArrayCHeap(int initial_max) :
+ GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> >(
+ allocate(initial_max, F),
+ initial_max) {}
+
+ GrowableArrayCHeap(int initial_max, int initial_len, const E& filler) :
+ GrowableArrayWithAllocator<E, GrowableArrayCHeap<E, F> >(
+ allocate(initial_max, F),
+ initial_max, initial_len, filler) {}
+
+ ~GrowableArrayCHeap() {
+ this->clear_and_deallocate();
+ }
+
+ void* operator new(size_t size) throw() {
+ return ResourceObj::operator new(size, ResourceObj::C_HEAP, F);
+ }
+
+ void* operator new(size_t size, const std::nothrow_t& nothrow_constant) throw() {
+ return ResourceObj::operator new(size, nothrow_constant, ResourceObj::C_HEAP, F);
+ }
+};
+
// Custom STL-style iterator to iterate over GrowableArrays
// It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
-template<class E> class GrowableArrayIterator : public StackObj {
- friend class GrowableArray<E>;
- template<class F, class UnaryPredicate> friend class GrowableArrayFilterIterator;
+template <typename E>
+class GrowableArrayIterator : public StackObj {
+ friend class GrowableArrayView<E>;
+ template <typename F, typename UnaryPredicate> friend class GrowableArrayFilterIterator;
private:
- const GrowableArray<E>* _array; // GrowableArray we iterate over
- int _position; // The current position in the GrowableArray
+ const GrowableArrayView<E>* _array; // GrowableArray we iterate over
+ int _position; // The current position in the GrowableArray
// Private constructor used in GrowableArray::begin() and GrowableArray::end()
- GrowableArrayIterator(const GrowableArray<E>* array, int position) : _array(array), _position(position) {
+ GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
assert(0 <= position && position <= _array->length(), "illegal position");
}
public:
GrowableArrayIterator() : _array(NULL), _position(0) { }
- GrowableArrayIterator<E>& operator++() { ++_position; return *this; }
- E operator*() { return _array->at(_position); }
+ GrowableArrayIterator<E>& operator++() { ++_position; return *this; }
+ E operator*() { return _array->at(_position); }
bool operator==(const GrowableArrayIterator<E>& rhs) {
assert(_array == rhs._array, "iterator belongs to different array");
@@ -552,17 +733,18 @@
};
// Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
-template<class E, class UnaryPredicate> class GrowableArrayFilterIterator : public StackObj {
- friend class GrowableArray<E>;
+template <typename E, class UnaryPredicate>
+class GrowableArrayFilterIterator : public StackObj {
+ friend class GrowableArrayView<E>;
private:
- const GrowableArray<E>* _array; // GrowableArray we iterate over
- int _position; // Current position in the GrowableArray
- UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
+ const GrowableArrayView<E>* _array; // GrowableArray we iterate over
+ int _position; // Current position in the GrowableArray
+ UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
public:
- GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate)
- : _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
+ GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate) :
+ _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
// Advance to first element satisfying the predicate
while(_position != _array->length() && !_predicate(_array->at(_position))) {
++_position;
@@ -577,7 +759,7 @@
return *this;
}
- E operator*() { return _array->at(_position); }
+ E operator*() { return _array->at(_position); }
bool operator==(const GrowableArrayIterator<E>& rhs) {
assert(_array == rhs._array, "iterator belongs to different array");
diff --git a/src/hotspot/share/utilities/hashtable.cpp b/src/hotspot/share/utilities/hashtable.cpp
index be8a87f..4ce5b30 100644
--- a/src/hotspot/share/utilities/hashtable.cpp
+++ b/src/hotspot/share/utilities/hashtable.cpp
@@ -67,7 +67,7 @@
len = 1 << log2_int(len); // round down to power of 2
assert(len >= _entry_size, "");
_first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
- _entry_blocks->append(_first_free_entry);
+ _entry_blocks.append(_first_free_entry);
_end_block = _first_free_entry + len;
}
entry = (BasicHashtableEntry<F>*)_first_free_entry;
diff --git a/src/hotspot/share/utilities/hashtable.hpp b/src/hotspot/share/utilities/hashtable.hpp
index fa4b8d6..a9b7ddb 100644
--- a/src/hotspot/share/utilities/hashtable.hpp
+++ b/src/hotspot/share/utilities/hashtable.hpp
@@ -158,14 +158,14 @@
private:
// Instance variables
- int _table_size;
- HashtableBucket<F>* _buckets;
+ int _table_size;
+ HashtableBucket<F>* _buckets;
BasicHashtableEntry<F>* volatile _free_list;
- char* _first_free_entry;
- char* _end_block;
- int _entry_size;
- volatile int _number_of_entries;
- GrowableArray<char*>* _entry_blocks;
+ char* _first_free_entry;
+ char* _end_block;
+ int _entry_size;
+ volatile int _number_of_entries;
+ GrowableArrayCHeap<char*, F> _entry_blocks;
protected:
diff --git a/src/hotspot/share/utilities/hashtable.inline.hpp b/src/hotspot/share/utilities/hashtable.inline.hpp
index 11c5d33..a106f31 100644
--- a/src/hotspot/share/utilities/hashtable.inline.hpp
+++ b/src/hotspot/share/utilities/hashtable.inline.hpp
@@ -36,7 +36,8 @@
// Initialize a table.
-template <MEMFLAGS F> inline BasicHashtable<F>::BasicHashtable(int table_size, int entry_size) {
+template <MEMFLAGS F> inline BasicHashtable<F>::BasicHashtable(int table_size, int entry_size) :
+ _entry_blocks(4) {
// Called on startup, no locking needed
initialize(table_size, entry_size, 0);
_buckets = NEW_C_HEAP_ARRAY2(HashtableBucket<F>, table_size, F, CURRENT_PC);
@@ -49,7 +50,8 @@
template <MEMFLAGS F> inline BasicHashtable<F>::BasicHashtable(int table_size, int entry_size,
HashtableBucket<F>* buckets,
- int number_of_entries) {
+ int number_of_entries) :
+ _entry_blocks(4) {
// Called on startup, no locking needed
initialize(table_size, entry_size, number_of_entries);
_buckets = buckets;
@@ -57,10 +59,9 @@
}
template <MEMFLAGS F> inline BasicHashtable<F>::~BasicHashtable() {
- for (int i = 0; i < _entry_blocks->length(); i++) {
- FREE_C_HEAP_ARRAY(char, _entry_blocks->at(i));
+ for (int i = 0; i < _entry_blocks.length(); i++) {
+ FREE_C_HEAP_ARRAY(char, _entry_blocks.at(i));
}
- delete _entry_blocks;
free_buckets();
}
@@ -73,7 +74,6 @@
_first_free_entry = NULL;
_end_block = NULL;
_number_of_entries = number_of_entries;
- _entry_blocks = new(ResourceObj::C_HEAP, F) GrowableArray<char*>(4, F);
}
diff --git a/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/HotSpotTypeDataBase.java b/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/HotSpotTypeDataBase.java
index c54f5e8..c4c5f43 100644
--- a/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/HotSpotTypeDataBase.java
+++ b/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/HotSpotTypeDataBase.java
@@ -116,8 +116,8 @@
BasicType basicTargetType = createBasicType(cTypeName, false, false, false);
- // transfer fields from GenericGrowableArray to template instance
- BasicType generic = lookupOrFail("GenericGrowableArray");
+ // transfer fields from GrowableArrayBase to template instance
+ BasicType generic = lookupOrFail("GrowableArrayBase");
BasicType specific = lookupOrFail("GrowableArray<int>");
basicTargetType.setSize(specific.getSize());
Iterator fields = generic.getFields();
diff --git a/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/utilities/GenericGrowableArray.java b/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/utilities/GenericGrowableArray.java
index a738e75..4f98367 100644
--- a/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/utilities/GenericGrowableArray.java
+++ b/src/jdk.hotspot.agent/share/classes/sun/jvm/hotspot/utilities/GenericGrowableArray.java
@@ -42,13 +42,11 @@
}
private static synchronized void initialize(TypeDataBase db) throws WrongTypeException {
- Type type = db.lookupType("GenericGrowableArray");
- _arena_field = type.getAddressField("_arena");
+ Type type = db.lookupType("GrowableArrayBase");
_max_field = new CIntField(type.getCIntegerField("_max"), 0);
_len_field = new CIntField(type.getCIntegerField("_len"), 0);
}
- private static AddressField _arena_field;
private static CIntField _max_field;
private static CIntField _len_field;
diff --git a/test/hotspot/gtest/utilities/test_growableArray.cpp b/test/hotspot/gtest/utilities/test_growableArray.cpp
new file mode 100644
index 0000000..2ead040
--- /dev/null
+++ b/test/hotspot/gtest/utilities/test_growableArray.cpp
@@ -0,0 +1,557 @@
+/*
+ * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+#include "precompiled.hpp"
+#include "memory/resourceArea.hpp"
+#include "utilities/growableArray.hpp"
+#include "unittest.hpp"
+
+struct WithEmbeddedArray {
+ // Array embedded in another class
+ GrowableArray<int> _a;
+
+ // Resource allocated data array
+ WithEmbeddedArray(int initial_max) : _a(initial_max) {}
+ // Arena allocated data array
+ WithEmbeddedArray(Arena* arena, int initial_max) : _a(arena, initial_max, 0, 0) {}
+ // CHeap allocated data array
+ WithEmbeddedArray(int initial_max, MEMFLAGS memflags) : _a(initial_max, memflags) {
+ assert(memflags != mtNone, "test requirement");
+ }
+ WithEmbeddedArray(const GrowableArray<int>& other) : _a(other) {}
+};
+
+// Test fixture to work with TEST_VM_F
+class GrowableArrayTest : public ::testing::Test {
+protected:
+ // friend -> private accessors
+ template <typename E>
+ static bool elements_on_C_heap(const GrowableArray<E>* array) {
+ return array->on_C_heap();
+ }
+ template <typename E>
+ static bool elements_on_stack(const GrowableArray<E>* array) {
+ return array->on_stack();
+ }
+ template <typename E>
+ static bool elements_on_arena(const GrowableArray<E>* array) {
+ return array->on_arena();
+ }
+
+ template <typename ArrayClass>
+ static void test_append(ArrayClass* a) {
+ // Add elements
+ for (int i = 0; i < 10; i++) {
+ a->append(i);
+ }
+
+ // Check size
+ ASSERT_EQ(a->length(), 10);
+
+ // Check elements
+ for (int i = 0; i < 10; i++) {
+ EXPECT_EQ(a->at(i), i);
+ }
+ }
+
+ template <typename ArrayClass>
+ static void test_clear(ArrayClass* a) {
+ // Add elements
+ for (int i = 0; i < 10; i++) {
+ a->append(i);
+ }
+
+ // Check size
+ ASSERT_EQ(a->length(), 10);
+ ASSERT_EQ(a->is_empty(), false);
+
+ // Clear elements
+ a->clear();
+
+ // Check size
+ ASSERT_EQ(a->length(), 0);
+ ASSERT_EQ(a->is_empty(), true);
+
+ // Add element
+ a->append(11);
+
+ // Check size
+ ASSERT_EQ(a->length(), 1);
+ ASSERT_EQ(a->is_empty(), false);
+
+ // Clear elements
+ a->clear();
+
+ // Check size
+ ASSERT_EQ(a->length(), 0);
+ ASSERT_EQ(a->is_empty(), true);
+ }
+
+ template <typename ArrayClass>
+ static void test_iterator(ArrayClass* a) {
+ // Add elements
+ for (int i = 0; i < 10; i++) {
+ a->append(i);
+ }
+
+ // Iterate
+ int counter = 0;
+ for (GrowableArrayIterator<int> i = a->begin(); i != a->end(); ++i) {
+ ASSERT_EQ(*i, counter++);
+ }
+
+ // Check count
+ ASSERT_EQ(counter, 10);
+ }
+
+ template <typename ArrayClass>
+ static void test_copy1(ArrayClass* a) {
+ ASSERT_EQ(a->length(), 1);
+ ASSERT_EQ(a->at(0), 1);
+
+ // Only allowed to copy to stack and embedded ResourceObjs
+
+ // Copy to stack
+ {
+ GrowableArray<int> c(*a);
+
+ ASSERT_EQ(c.length(), 1);
+ ASSERT_EQ(c.at(0), 1);
+ }
+
+ // Copy to embedded
+ {
+ WithEmbeddedArray c(*a);
+
+ ASSERT_EQ(c._a.length(), 1);
+ ASSERT_EQ(c._a.at(0), 1);
+ }
+ }
+
+ template <typename ArrayClass>
+ static void test_assignment1(ArrayClass* a) {
+ ASSERT_EQ(a->length(), 1);
+ ASSERT_EQ(a->at(0), 1);
+
+ // Only allowed to assign to stack and embedded ResourceObjs
+
+ // Copy to embedded/resource
+ {
+ ResourceMark rm;
+ GrowableArray<int> c(1);
+ c = *a;
+
+ ASSERT_EQ(c.length(), 1);
+ ASSERT_EQ(c.at(0), 1);
+ }
+
+ // Copy to embedded/arena
+ {
+ Arena arena(mtTest);
+ GrowableArray<int> c(&arena, 1, 0, 0);
+ c = *a;
+
+ ASSERT_EQ(c.length(), 1);
+ ASSERT_EQ(c.at(0), 1);
+ }
+
+ // Copy to embedded/resource
+ {
+ ResourceMark rm;
+ WithEmbeddedArray c(1);
+ c._a = *a;
+
+ ASSERT_EQ(c._a.length(), 1);
+ ASSERT_EQ(c._a.at(0), 1);
+ }
+
+ // Copy to embedded/arena
+ {
+ Arena arena(mtTest);
+ WithEmbeddedArray c(&arena, 1);
+ c._a = *a;
+
+ ASSERT_EQ(c._a.length(), 1);
+ ASSERT_EQ(c._a.at(0), 1);
+ }
+ }
+
+ // Supported by all GrowableArrays
+ enum TestEnum {
+ Append,
+ Clear,
+ Iterator,
+ };
+
+ template <typename ArrayClass>
+ static void do_test(ArrayClass* a, TestEnum test) {
+ switch (test) {
+ case Append:
+ test_append(a);
+ break;
+
+ case Clear:
+ test_clear(a);
+ break;
+
+ case Iterator:
+ test_iterator(a);
+ break;
+
+ default:
+ fatal("Missing dispatch");
+ break;
+ }
+ }
+
+ // Only supported by GrowableArrays without CHeap data arrays
+ enum TestNoCHeapEnum {
+ Copy1,
+ Assignment1,
+ };
+
+ template <typename ArrayClass>
+ static void do_test(ArrayClass* a, TestNoCHeapEnum test) {
+ switch (test) {
+ case Copy1:
+ test_copy1(a);
+ break;
+
+ case Assignment1:
+ test_assignment1(a);
+ break;
+
+ default:
+ fatal("Missing dispatch");
+ break;
+ }
+ }
+
+ enum ModifyEnum {
+ Append1,
+ Append1Clear,
+ Append1ClearAndDeallocate,
+ NoModify
+ };
+
+ template <typename ArrayClass>
+ static void do_modify(ArrayClass* a, ModifyEnum modify) {
+ switch (modify) {
+ case Append1:
+ a->append(1);
+ break;
+
+ case Append1Clear:
+ a->append(1);
+ a->clear();
+ break;
+
+ case Append1ClearAndDeallocate:
+ a->append(1);
+ a->clear_and_deallocate();
+ break;
+
+ case NoModify:
+ // Nothing to do
+ break;
+
+ default:
+ fatal("Missing dispatch");
+ break;
+ }
+ }
+
+ static const int Max0 = 0;
+ static const int Max1 = 1;
+
+ template <typename ArrayClass, typename T>
+ static void modify_and_test(ArrayClass* array, ModifyEnum modify, T test) {
+ do_modify(array, modify);
+ do_test(array, test);
+ }
+
+ template <typename T>
+ static void with_no_cheap_array(int max, ModifyEnum modify, T test) {
+ // Resource/Resource allocated
+ {
+ ResourceMark rm;
+ GrowableArray<int>* a = new GrowableArray<int>(max);
+ modify_and_test(a, modify, test);
+ }
+
+ // Resource/Arena allocated
+ // Combination not supported
+
+ // CHeap/Resource allocated
+ // Combination not supported
+
+ // CHeap/Arena allocated
+ // Combination not supported
+
+ // Stack/Resource allocated
+ {
+ ResourceMark rm;
+ GrowableArray<int> a(max);
+ modify_and_test(&a, modify, test);
+ }
+
+ // Stack/Arena allocated
+ {
+ Arena arena(mtTest);
+ GrowableArray<int> a(&arena, max, 0, 0);
+ modify_and_test(&a, modify, test);
+ }
+
+ // Embedded/Resource allocated
+ {
+ ResourceMark rm;
+ WithEmbeddedArray w(max);
+ modify_and_test(&w._a, modify, test);
+ }
+
+ // Embedded/Arena allocated
+ {
+ Arena arena(mtTest);
+ WithEmbeddedArray w(&arena, max);
+ modify_and_test(&w._a, modify, test);
+ }
+ }
+
+ static void with_cheap_array(int max, ModifyEnum modify, TestEnum test) {
+ // Resource/CHeap allocated
+ // Combination not supported
+
+ // CHeap/CHeap allocated
+ {
+ GrowableArray<int>* a = new (ResourceObj::C_HEAP, mtTest) GrowableArray<int>(max, mtTest);
+ modify_and_test(a, modify, test);
+ delete a;
+ }
+
+ // Stack/CHeap allocated
+ {
+ GrowableArray<int> a(max, mtTest);
+ modify_and_test(&a, modify, test);
+ }
+
+ // Embedded/CHeap allocated
+ {
+ WithEmbeddedArray w(max, mtTest);
+ modify_and_test(&w._a, modify, test);
+ }
+ }
+
+ static void with_all_types(int max, ModifyEnum modify, TestEnum test) {
+ with_no_cheap_array(max, modify, test);
+ with_cheap_array(max, modify, test);
+ }
+
+ static void with_all_types_empty(TestEnum test) {
+ with_all_types(Max0, NoModify, test);
+ }
+
+ static void with_all_types_max_set(TestEnum test) {
+ with_all_types(Max1, NoModify, test);
+ }
+
+ static void with_all_types_cleared(TestEnum test) {
+ with_all_types(Max1, Append1Clear, test);
+ }
+
+ static void with_all_types_clear_and_deallocated(TestEnum test) {
+ with_all_types(Max1, Append1ClearAndDeallocate, test);
+ }
+
+ static void with_all_types_all_0(TestEnum test) {
+ with_all_types_empty(test);
+ with_all_types_max_set(test);
+ with_all_types_cleared(test);
+ with_all_types_clear_and_deallocated(test);
+ }
+
+ static void with_no_cheap_array_append1(TestNoCHeapEnum test) {
+ with_no_cheap_array(Max0, Append1, test);
+ }
+};
+
+TEST_VM_F(GrowableArrayTest, append) {
+ with_all_types_all_0(Append);
+}
+
+TEST_VM_F(GrowableArrayTest, clear) {
+ with_all_types_all_0(Clear);
+}
+
+TEST_VM_F(GrowableArrayTest, iterator) {
+ with_all_types_all_0(Iterator);
+}
+
+TEST_VM_F(GrowableArrayTest, copy) {
+ with_no_cheap_array_append1(Copy1);
+}
+
+TEST_VM_F(GrowableArrayTest, assignment) {
+ with_no_cheap_array_append1(Assignment1);
+}
+
+#ifdef ASSERT
+TEST_VM_F(GrowableArrayTest, where) {
+ WithEmbeddedArray s(1, mtTest);
+ ASSERT_FALSE(s._a.allocated_on_C_heap());
+ ASSERT_TRUE(elements_on_C_heap(&s._a));
+
+ // Resource/Resource allocated
+ {
+ ResourceMark rm;
+ GrowableArray<int>* a = new GrowableArray<int>();
+ ASSERT_TRUE(a->allocated_on_res_area());
+ ASSERT_TRUE(elements_on_stack(a));
+ }
+
+ // Resource/CHeap allocated
+ // Combination not supported
+
+ // Resource/Arena allocated
+ // Combination not supported
+
+ // CHeap/Resource allocated
+ // Combination not supported
+
+ // CHeap/CHeap allocated
+ {
+ GrowableArray<int>* a = new (ResourceObj::C_HEAP, mtTest) GrowableArray<int>(0, mtTest);
+ ASSERT_TRUE(a->allocated_on_C_heap());
+ ASSERT_TRUE(elements_on_C_heap(a));
+ delete a;
+ }
+
+ // CHeap/Arena allocated
+ // Combination not supported
+
+ // Stack/Resource allocated
+ {
+ ResourceMark rm;
+ GrowableArray<int> a(0);
+ ASSERT_TRUE(a.allocated_on_stack());
+ ASSERT_TRUE(elements_on_stack(&a));
+ }
+
+ // Stack/CHeap allocated
+ {
+ GrowableArray<int> a(0, mtTest);
+ ASSERT_TRUE(a.allocated_on_stack());
+ ASSERT_TRUE(elements_on_C_heap(&a));
+ }
+
+ // Stack/Arena allocated
+ {
+ Arena arena(mtTest);
+ GrowableArray<int> a(&arena, 0, 0, 0);
+ ASSERT_TRUE(a.allocated_on_stack());
+ ASSERT_TRUE(elements_on_arena(&a));
+ }
+
+ // Embedded/Resource allocated
+ {
+ ResourceMark rm;
+ WithEmbeddedArray w(0);
+ ASSERT_TRUE(w._a.allocated_on_stack());
+ ASSERT_TRUE(elements_on_stack(&w._a));
+ }
+
+ // Embedded/CHeap allocated
+ {
+ WithEmbeddedArray w(0, mtTest);
+ ASSERT_TRUE(w._a.allocated_on_stack());
+ ASSERT_TRUE(elements_on_C_heap(&w._a));
+ }
+
+ // Embedded/Arena allocated
+ {
+ Arena arena(mtTest);
+ WithEmbeddedArray w(&arena, 0);
+ ASSERT_TRUE(w._a.allocated_on_stack());
+ ASSERT_TRUE(elements_on_arena(&w._a));
+ }
+}
+
+TEST_VM_ASSERT_MSG(GrowableArrayAssertingTest, copy_with_embedded_cheap,
+ "Copying of CHeap arrays not supported") {
+ WithEmbeddedArray s(1, mtTest);
+ // Intentionally asserts that copy of CHeap arrays are not allowed
+ WithEmbeddedArray c(s);
+}
+
+TEST_VM_ASSERT_MSG(GrowableArrayAssertingTest, assignment_with_embedded_cheap,
+ "Assignment of CHeap arrays not supported") {
+ WithEmbeddedArray s(1, mtTest);
+ WithEmbeddedArray c(1, mtTest);
+
+ // Intentionally asserts that assignment of CHeap arrays are not allowed
+ c = s;
+}
+
+#endif
+
+TEST(GrowableArrayCHeap, sanity) {
+ // Stack/CHeap
+ {
+ GrowableArrayCHeap<int, mtTest> a(0);
+#ifdef ASSERT
+ ASSERT_TRUE(a.allocated_on_stack());
+#endif
+ ASSERT_TRUE(a.is_empty());
+
+ a.append(1);
+ ASSERT_FALSE(a.is_empty());
+ ASSERT_EQ(a.at(0), 1);
+ }
+
+ // CHeap/CHeap
+ {
+ GrowableArrayCHeap<int, mtTest>* a = new GrowableArrayCHeap<int, mtTest>(0);
+#ifdef ASSERT
+ ASSERT_TRUE(a->allocated_on_C_heap());
+#endif
+ ASSERT_TRUE(a->is_empty());
+
+ a->append(1);
+ ASSERT_FALSE(a->is_empty());
+ ASSERT_EQ(a->at(0), 1);
+ delete a;
+ }
+
+ // CHeap/CHeap - nothrow new operator
+ {
+ GrowableArrayCHeap<int, mtTest>* a = new (std::nothrow) GrowableArrayCHeap<int, mtTest>(0);
+#ifdef ASSERT
+ ASSERT_TRUE(a->allocated_on_C_heap());
+#endif
+ ASSERT_TRUE(a->is_empty());
+
+ a->append(1);
+ ASSERT_FALSE(a->is_empty());
+ ASSERT_EQ(a->at(0), 1);
+ delete a;
+ }
+}
