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_UTILITIES_GROWABLEARRAY_HPP
26 #define SHARE_UTILITIES_GROWABLEARRAY_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/iterator.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include "utilities/ostream.hpp"
33 #include "utilities/powerOfTwo.hpp"
34
35 // A growable array.
36
37 /*************************************************************************/
38 /* */
39 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
40 /* */
41 /* Should you use GrowableArrays to contain handles you must be certain */
42 /* that the GrowableArray does not outlive the HandleMark that contains */
43 /* the handles. Since GrowableArrays are typically resource allocated */
44 /* the following is an example of INCORRECT CODE, */
45 /* */
46 /* ResourceMark rm; */
47 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
48 /* if (blah) { */
49 /* while (...) { */
79 int _capacity;
80
81 GrowableArrayBase(int capacity, int initial_len) :
82 _len(initial_len),
83 _capacity(capacity) {
84 assert(_len >= 0 && _len <= _capacity, "initial_len too big");
85 }
86
87 ~GrowableArrayBase() {}
88
89 public:
90 int length() const { return _len; }
91 int capacity() const { return _capacity; }
92
93 bool is_empty() const { return _len == 0; }
94 bool is_nonempty() const { return _len != 0; }
95 bool is_full() const { return _len == _capacity; }
96 };
97
98 template <typename E> class GrowableArrayIterator;
99
100 // Extends GrowableArrayBase with a typed data array.
101 //
102 // E: Element type
103 //
104 // The "view" adds function that don't grow or deallocate
105 // the _data array, so there's no need for an allocator.
106 //
107 // The "view" can be used to type erase the allocator classes
108 // of GrowableArrayWithAllocator.
109 template <typename E>
110 class GrowableArrayView : public GrowableArrayBase {
111 protected:
112 E* _data; // data array
113
114 GrowableArrayView(E* data, int capacity, int initial_len) :
115 GrowableArrayBase(capacity, initial_len), _data(data) {}
116
117 ~GrowableArrayView() {}
118
410 int new_len = this->_len + array_len;
411 if (new_len >= this->_capacity) grow(new_len);
412
413 for (int j = this->_len - 1; j >= idx; j--) {
414 this->_data[j + array_len] = this->_data[j];
415 }
416
417 for (int j = 0; j < array_len; j++) {
418 this->_data[idx + j] = array->at(j);
419 }
420
421 this->_len += array_len;
422 }
423
424 void appendAll(const GrowableArrayView<E>* l) {
425 for (int i = 0; i < l->length(); i++) {
426 this->at_put_grow(this->_len, l->at(i), E());
427 }
428 }
429
430 // Binary search and insertion utility. Search array for element
431 // matching key according to the static compare function. Insert
432 // that element if not already in the list. Assumes the list is
433 // already sorted according to compare function.
434 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
435 bool found;
436 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
437 if (!found) {
438 insert_before(location, key);
439 }
440 return this->at(location);
441 }
442
443 E insert_sorted(CompareClosure<E>* cc, const E& key) {
444 bool found;
445 int location = find_sorted(cc, key, found);
446 if (!found) {
447 insert_before(location, key);
448 }
449 return this->at(location);
860 this->clear_and_deallocate();
861 }
862
863 void* operator new(size_t size) {
864 return AnyObj::operator new(size, MT);
865 }
866
867 void* operator new(size_t size, const std::nothrow_t& nothrow_constant) throw() {
868 return AnyObj::operator new(size, nothrow_constant, MT);
869 }
870 void operator delete(void *p) {
871 AnyObj::operator delete(p);
872 }
873 };
874
875 // Custom STL-style iterator to iterate over GrowableArrays
876 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
877 template <typename E>
878 class GrowableArrayIterator : public StackObj {
879 friend class GrowableArrayView<E>;
880
881 private:
882 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
883 int _position; // The current position in the GrowableArray
884
885 // Private constructor used in GrowableArray::begin() and GrowableArray::end()
886 GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
887 assert(0 <= position && position <= _array->length(), "illegal position");
888 }
889
890 public:
891 GrowableArrayIterator() : _array(nullptr), _position(0) { }
892 GrowableArrayIterator& operator++() { ++_position; return *this; }
893 E operator*() { return _array->at(_position); }
894
895 bool operator==(const GrowableArrayIterator& rhs) {
896 assert(_array == rhs._array, "iterator belongs to different array");
897 return _position == rhs._position;
898 }
899
900 bool operator!=(const GrowableArrayIterator& rhs) {
901 assert(_array == rhs._array, "iterator belongs to different array");
902 return _position != rhs._position;
903 }
904 };
905
906 // Arrays for basic types
907 typedef GrowableArray<int> intArray;
908 typedef GrowableArray<int> intStack;
909 typedef GrowableArray<bool> boolArray;
910
911 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|
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_UTILITIES_GROWABLEARRAY_HPP
26 #define SHARE_UTILITIES_GROWABLEARRAY_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/iterator.hpp"
30 #include "oops/array.hpp"
31 #include "utilities/debug.hpp"
32 #include "utilities/globalDefinitions.hpp"
33 #include "utilities/ostream.hpp"
34 #include "utilities/powerOfTwo.hpp"
35
36 // A growable array.
37
38 /*************************************************************************/
39 /* */
40 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
41 /* */
42 /* Should you use GrowableArrays to contain handles you must be certain */
43 /* that the GrowableArray does not outlive the HandleMark that contains */
44 /* the handles. Since GrowableArrays are typically resource allocated */
45 /* the following is an example of INCORRECT CODE, */
46 /* */
47 /* ResourceMark rm; */
48 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
49 /* if (blah) { */
50 /* while (...) { */
80 int _capacity;
81
82 GrowableArrayBase(int capacity, int initial_len) :
83 _len(initial_len),
84 _capacity(capacity) {
85 assert(_len >= 0 && _len <= _capacity, "initial_len too big");
86 }
87
88 ~GrowableArrayBase() {}
89
90 public:
91 int length() const { return _len; }
92 int capacity() const { return _capacity; }
93
94 bool is_empty() const { return _len == 0; }
95 bool is_nonempty() const { return _len != 0; }
96 bool is_full() const { return _len == _capacity; }
97 };
98
99 template <typename E> class GrowableArrayIterator;
100 template <typename E, typename UnaryPredicate> class GrowableArrayFilterIterator;
101
102 // Extends GrowableArrayBase with a typed data array.
103 //
104 // E: Element type
105 //
106 // The "view" adds function that don't grow or deallocate
107 // the _data array, so there's no need for an allocator.
108 //
109 // The "view" can be used to type erase the allocator classes
110 // of GrowableArrayWithAllocator.
111 template <typename E>
112 class GrowableArrayView : public GrowableArrayBase {
113 protected:
114 E* _data; // data array
115
116 GrowableArrayView(E* data, int capacity, int initial_len) :
117 GrowableArrayBase(capacity, initial_len), _data(data) {}
118
119 ~GrowableArrayView() {}
120
412 int new_len = this->_len + array_len;
413 if (new_len >= this->_capacity) grow(new_len);
414
415 for (int j = this->_len - 1; j >= idx; j--) {
416 this->_data[j + array_len] = this->_data[j];
417 }
418
419 for (int j = 0; j < array_len; j++) {
420 this->_data[idx + j] = array->at(j);
421 }
422
423 this->_len += array_len;
424 }
425
426 void appendAll(const GrowableArrayView<E>* l) {
427 for (int i = 0; i < l->length(); i++) {
428 this->at_put_grow(this->_len, l->at(i), E());
429 }
430 }
431
432 void appendAll(const Array<E>* l) {
433 for (int i = 0; i < l->length(); i++) {
434 this->at_put_grow(this->_len, l->at(i), E());
435 }
436 }
437
438 // Binary search and insertion utility. Search array for element
439 // matching key according to the static compare function. Insert
440 // that element if not already in the list. Assumes the list is
441 // already sorted according to compare function.
442 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
443 bool found;
444 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
445 if (!found) {
446 insert_before(location, key);
447 }
448 return this->at(location);
449 }
450
451 E insert_sorted(CompareClosure<E>* cc, const E& key) {
452 bool found;
453 int location = find_sorted(cc, key, found);
454 if (!found) {
455 insert_before(location, key);
456 }
457 return this->at(location);
868 this->clear_and_deallocate();
869 }
870
871 void* operator new(size_t size) {
872 return AnyObj::operator new(size, MT);
873 }
874
875 void* operator new(size_t size, const std::nothrow_t& nothrow_constant) throw() {
876 return AnyObj::operator new(size, nothrow_constant, MT);
877 }
878 void operator delete(void *p) {
879 AnyObj::operator delete(p);
880 }
881 };
882
883 // Custom STL-style iterator to iterate over GrowableArrays
884 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
885 template <typename E>
886 class GrowableArrayIterator : public StackObj {
887 friend class GrowableArrayView<E>;
888 template <typename F, typename UnaryPredicate> friend class GrowableArrayFilterIterator;
889
890 private:
891 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
892 int _position; // The current position in the GrowableArray
893
894 // Private constructor used in GrowableArray::begin() and GrowableArray::end()
895 GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
896 assert(0 <= position && position <= _array->length(), "illegal position");
897 }
898
899 public:
900 GrowableArrayIterator() : _array(nullptr), _position(0) { }
901 GrowableArrayIterator& operator++() { ++_position; return *this; }
902 E operator*() { return _array->at(_position); }
903
904 bool operator==(const GrowableArrayIterator& rhs) {
905 assert(_array == rhs._array, "iterator belongs to different array");
906 return _position == rhs._position;
907 }
908
909 bool operator!=(const GrowableArrayIterator& rhs) {
910 assert(_array == rhs._array, "iterator belongs to different array");
911 return _position != rhs._position;
912 }
913 };
914
915 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
916 template <typename E, class UnaryPredicate>
917 class GrowableArrayFilterIterator : public StackObj {
918 friend class GrowableArrayView<E>;
919
920 private:
921 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
922 int _position; // Current position in the GrowableArray
923 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
924
925 public:
926 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate) :
927 _array(array), _position(0), _predicate(filter_predicate) {
928 // Advance to first element satisfying the predicate
929 while(!at_end() && !_predicate(_array->at(_position))) {
930 ++_position;
931 }
932 }
933
934 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
935 do {
936 // Advance to next element satisfying the predicate
937 ++_position;
938 } while(!at_end() && !_predicate(_array->at(_position)));
939 return *this;
940 }
941
942 E operator*() { return _array->at(_position); }
943
944 bool operator==(const GrowableArrayIterator<E>& rhs) {
945 assert(_array == rhs._array, "iterator belongs to different array");
946 return _position == rhs._position;
947 }
948
949 bool operator!=(const GrowableArrayIterator<E>& rhs) {
950 assert(_array == rhs._array, "iterator belongs to different array");
951 return _position != rhs._position;
952 }
953
954 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
955 assert(_array == rhs._array, "iterator belongs to different array");
956 return _position == rhs._position;
957 }
958
959 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
960 assert(_array == rhs._array, "iterator belongs to different array");
961 return _position != rhs._position;
962 }
963
964 bool at_end() const {
965 return _array == nullptr || _position == _array->end()._position;
966 }
967 };
968
969 // Arrays for basic types
970 typedef GrowableArray<int> intArray;
971 typedef GrowableArray<int> intStack;
972 typedef GrowableArray<bool> boolArray;
973
974 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|