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