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_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) { */
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 void clear() { _len = 0; }
98 void trunc_to(int length) {
99 assert(length <= _len,"cannot increase length");
100 _len = length;
101 }
102 };
103
104 template <typename E> class GrowableArrayIterator;
105
106 // Extends GrowableArrayBase with a typed data array.
107 //
108 // E: Element type
109 //
110 // The "view" adds function that don't grow or deallocate
111 // the _data array, so there's no need for an allocator.
112 //
113 // The "view" can be used to type erase the allocator classes
114 // of GrowableArrayWithAllocator.
115 template <typename E>
116 class GrowableArrayView : public GrowableArrayBase {
117 protected:
118 E* _data; // data array
119
120 GrowableArrayView(E* data, int capacity, int initial_len) :
121 GrowableArrayBase(capacity, initial_len), _data(data) {}
122
123 ~GrowableArrayView() {}
124
466 int new_len = this->_len + array_len;
467 if (new_len >= this->_capacity) grow(new_len);
468
469 for (int j = this->_len - 1; j >= idx; j--) {
470 this->_data[j + array_len] = this->_data[j];
471 }
472
473 for (int j = 0; j < array_len; j++) {
474 this->_data[idx + j] = array->at(j);
475 }
476
477 this->_len += array_len;
478 }
479
480 void appendAll(const GrowableArrayView<E>* l) {
481 for (int i = 0; i < l->length(); i++) {
482 this->at_put_grow(this->_len, l->at(i), E());
483 }
484 }
485
486 // Binary search and insertion utility. Search array for element
487 // matching key according to the static compare function. Insert
488 // that element if not already in the list. Assumes the list is
489 // already sorted according to compare function.
490 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
491 bool found;
492 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
493 if (!found) {
494 insert_before(location, key);
495 }
496 return this->at(location);
497 }
498
499 E insert_sorted(CompareClosure<E>* cc, const E& key) {
500 bool found;
501 int location = find_sorted(cc, key, found);
502 if (!found) {
503 insert_before(location, key);
504 }
505 return this->at(location);
851 this->clear_and_deallocate();
852 }
853
854 void* operator new(size_t size) {
855 return AnyObj::operator new(size, MT);
856 }
857
858 void* operator new(size_t size, const std::nothrow_t& nothrow_constant) throw() {
859 return AnyObj::operator new(size, nothrow_constant, MT);
860 }
861 void operator delete(void *p) {
862 AnyObj::operator delete(p);
863 }
864 };
865
866 // Custom STL-style iterator to iterate over GrowableArrays
867 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
868 template <typename E>
869 class GrowableArrayIterator : public StackObj {
870 friend class GrowableArrayView<E>;
871
872 private:
873 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
874 int _position; // The current position in the GrowableArray
875
876 // Private constructor used in GrowableArray::begin() and GrowableArray::end()
877 GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
878 assert(0 <= position && position <= _array->length(), "illegal position");
879 }
880
881 public:
882 GrowableArrayIterator() : _array(nullptr), _position(0) { }
883 GrowableArrayIterator& operator++() { ++_position; return *this; }
884 E operator*() { return _array->at(_position); }
885
886 bool operator==(const GrowableArrayIterator& rhs) {
887 assert(_array == rhs._array, "iterator belongs to different array");
888 return _position == rhs._position;
889 }
890
891 bool operator!=(const GrowableArrayIterator& rhs) {
892 assert(_array == rhs._array, "iterator belongs to different array");
893 return _position != rhs._position;
894 }
895 };
896
897 // Arrays for basic types
898 typedef GrowableArray<int> intArray;
899 typedef GrowableArray<int> intStack;
900 typedef GrowableArray<bool> boolArray;
901
902 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|
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_UTILITIES_GROWABLEARRAY_HPP
26 #define SHARE_UTILITIES_GROWABLEARRAY_HPP
27
28 #include "memory/allocation.hpp"
29 #include "oops/array.hpp"
30 #include "oops/oop.hpp"
31 #include "memory/iterator.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) { */
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 void clear() { _len = 0; }
100 void trunc_to(int length) {
101 assert(length <= _len,"cannot increase length");
102 _len = length;
103 }
104 };
105
106 template <typename E> class GrowableArrayIterator;
107 template <typename E, typename UnaryPredicate> class GrowableArrayFilterIterator;
108
109 // Extends GrowableArrayBase with a typed data array.
110 //
111 // E: Element type
112 //
113 // The "view" adds function that don't grow or deallocate
114 // the _data array, so there's no need for an allocator.
115 //
116 // The "view" can be used to type erase the allocator classes
117 // of GrowableArrayWithAllocator.
118 template <typename E>
119 class GrowableArrayView : public GrowableArrayBase {
120 protected:
121 E* _data; // data array
122
123 GrowableArrayView(E* data, int capacity, int initial_len) :
124 GrowableArrayBase(capacity, initial_len), _data(data) {}
125
126 ~GrowableArrayView() {}
127
469 int new_len = this->_len + array_len;
470 if (new_len >= this->_capacity) grow(new_len);
471
472 for (int j = this->_len - 1; j >= idx; j--) {
473 this->_data[j + array_len] = this->_data[j];
474 }
475
476 for (int j = 0; j < array_len; j++) {
477 this->_data[idx + j] = array->at(j);
478 }
479
480 this->_len += array_len;
481 }
482
483 void appendAll(const GrowableArrayView<E>* l) {
484 for (int i = 0; i < l->length(); i++) {
485 this->at_put_grow(this->_len, l->at(i), E());
486 }
487 }
488
489 void appendAll(const Array<E>* l) {
490 for (int i = 0; i < l->length(); i++) {
491 this->at_put_grow(this->_len, l->at(i), E());
492 }
493 }
494
495 // Binary search and insertion utility. Search array for element
496 // matching key according to the static compare function. Insert
497 // that element if not already in the list. Assumes the list is
498 // already sorted according to compare function.
499 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
500 bool found;
501 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
502 if (!found) {
503 insert_before(location, key);
504 }
505 return this->at(location);
506 }
507
508 E insert_sorted(CompareClosure<E>* cc, const E& key) {
509 bool found;
510 int location = find_sorted(cc, key, found);
511 if (!found) {
512 insert_before(location, key);
513 }
514 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 template <typename F, typename UnaryPredicate> friend class GrowableArrayFilterIterator;
881
882 private:
883 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
884 int _position; // The current position in the GrowableArray
885
886 // Private constructor used in GrowableArray::begin() and GrowableArray::end()
887 GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
888 assert(0 <= position && position <= _array->length(), "illegal position");
889 }
890
891 public:
892 GrowableArrayIterator() : _array(nullptr), _position(0) { }
893 GrowableArrayIterator& operator++() { ++_position; return *this; }
894 E operator*() { return _array->at(_position); }
895
896 bool operator==(const GrowableArrayIterator& rhs) {
897 assert(_array == rhs._array, "iterator belongs to different array");
898 return _position == rhs._position;
899 }
900
901 bool operator!=(const GrowableArrayIterator& rhs) {
902 assert(_array == rhs._array, "iterator belongs to different array");
903 return _position != rhs._position;
904 }
905 };
906
907 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
908 template <typename E, class UnaryPredicate>
909 class GrowableArrayFilterIterator : public StackObj {
910 friend class GrowableArrayView<E>;
911
912 private:
913 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
914 int _position; // Current position in the GrowableArray
915 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
916
917 public:
918 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate) :
919 _array(array), _position(0), _predicate(filter_predicate) {
920 // Advance to first element satisfying the predicate
921 while(!at_end() && !_predicate(_array->at(_position))) {
922 ++_position;
923 }
924 }
925
926 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
927 do {
928 // Advance to next element satisfying the predicate
929 ++_position;
930 } while(!at_end() && !_predicate(_array->at(_position)));
931 return *this;
932 }
933
934 E operator*() { return _array->at(_position); }
935
936 bool operator==(const GrowableArrayIterator<E>& rhs) {
937 assert(_array == rhs._array, "iterator belongs to different array");
938 return _position == rhs._position;
939 }
940
941 bool operator!=(const GrowableArrayIterator<E>& rhs) {
942 assert(_array == rhs._array, "iterator belongs to different array");
943 return _position != rhs._position;
944 }
945
946 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
947 assert(_array == rhs._array, "iterator belongs to different array");
948 return _position == rhs._position;
949 }
950
951 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
952 assert(_array == rhs._array, "iterator belongs to different array");
953 return _position != rhs._position;
954 }
955
956 bool at_end() const {
957 return _array == nullptr || _position == _array->end()._position;
958 }
959 };
960
961 // Arrays for basic types
962 typedef GrowableArray<int> intArray;
963 typedef GrowableArray<int> intStack;
964 typedef GrowableArray<bool> boolArray;
965
966 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|