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) { */
453 int new_len = this->_len + array_len;
454 if (new_len >= this->_capacity) grow(new_len);
455
456 for (int j = this->_len - 1; j >= idx; j--) {
457 this->_data[j + array_len] = this->_data[j];
458 }
459
460 for (int j = 0; j < array_len; j++) {
461 this->_data[idx + j] = array->at(j);
462 }
463
464 this->_len += array_len;
465 }
466
467 void appendAll(const GrowableArrayView<E>* l) {
468 for (int i = 0; i < l->length(); i++) {
469 this->at_put_grow(this->_len, l->at(i), E());
470 }
471 }
472
473 // Binary search and insertion utility. Search array for element
474 // matching key according to the static compare function. Insert
475 // that element if not already in the list. Assumes the list is
476 // already sorted according to compare function.
477 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
478 bool found;
479 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
480 if (!found) {
481 insert_before(location, key);
482 }
483 return this->at(location);
484 }
485
486 E insert_sorted(CompareClosure<E>* cc, const E& key) {
487 bool found;
488 int location = find_sorted(cc, key, found);
489 if (!found) {
490 insert_before(location, key);
491 }
492 return this->at(location);
867 return _position == rhs._position;
868 }
869
870 bool operator!=(const GrowableArrayIterator<E>& rhs) {
871 assert(_array == rhs._array, "iterator belongs to different array");
872 return _position != rhs._position;
873 }
874 };
875
876 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
877 template <typename E, class UnaryPredicate>
878 class GrowableArrayFilterIterator : public StackObj {
879 friend class GrowableArrayView<E>;
880
881 private:
882 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
883 int _position; // Current position in the GrowableArray
884 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
885
886 public:
887 GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate) :
888 _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
889 // Advance to first element satisfying the predicate
890 while(_position != _array->length() && !_predicate(_array->at(_position))) {
891 ++_position;
892 }
893 }
894
895 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
896 do {
897 // Advance to next element satisfying the predicate
898 ++_position;
899 } while(_position != _array->length() && !_predicate(_array->at(_position)));
900 return *this;
901 }
902
903 E operator*() { return _array->at(_position); }
904
905 bool operator==(const GrowableArrayIterator<E>& rhs) {
906 assert(_array == rhs._array, "iterator belongs to different array");
907 return _position == rhs._position;
908 }
909
910 bool operator!=(const GrowableArrayIterator<E>& rhs) {
911 assert(_array == rhs._array, "iterator belongs to different array");
912 return _position != rhs._position;
913 }
914
915 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
916 assert(_array == rhs._array, "iterator belongs to different array");
917 return _position == rhs._position;
918 }
919
920 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
921 assert(_array == rhs._array, "iterator belongs to different array");
922 return _position != rhs._position;
923 }
924 };
925
926 // Arrays for basic types
927 typedef GrowableArray<int> intArray;
928 typedef GrowableArray<int> intStack;
929 typedef GrowableArray<bool> boolArray;
930
931 #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) { */
455 int new_len = this->_len + array_len;
456 if (new_len >= this->_capacity) grow(new_len);
457
458 for (int j = this->_len - 1; j >= idx; j--) {
459 this->_data[j + array_len] = this->_data[j];
460 }
461
462 for (int j = 0; j < array_len; j++) {
463 this->_data[idx + j] = array->at(j);
464 }
465
466 this->_len += array_len;
467 }
468
469 void appendAll(const GrowableArrayView<E>* l) {
470 for (int i = 0; i < l->length(); i++) {
471 this->at_put_grow(this->_len, l->at(i), E());
472 }
473 }
474
475 void appendAll(const Array<E>* l) {
476 for (int i = 0; i < l->length(); i++) {
477 this->at_put_grow(this->_len, l->at(i), E());
478 }
479 }
480
481 // Binary search and insertion utility. Search array for element
482 // matching key according to the static compare function. Insert
483 // that element if not already in the list. Assumes the list is
484 // already sorted according to compare function.
485 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
486 bool found;
487 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
488 if (!found) {
489 insert_before(location, key);
490 }
491 return this->at(location);
492 }
493
494 E insert_sorted(CompareClosure<E>* cc, const E& key) {
495 bool found;
496 int location = find_sorted(cc, key, found);
497 if (!found) {
498 insert_before(location, key);
499 }
500 return this->at(location);
875 return _position == rhs._position;
876 }
877
878 bool operator!=(const GrowableArrayIterator<E>& rhs) {
879 assert(_array == rhs._array, "iterator belongs to different array");
880 return _position != rhs._position;
881 }
882 };
883
884 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
885 template <typename E, class UnaryPredicate>
886 class GrowableArrayFilterIterator : public StackObj {
887 friend class GrowableArrayView<E>;
888
889 private:
890 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
891 int _position; // Current position in the GrowableArray
892 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
893
894 public:
895 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate) :
896 _array(array), _position(0), _predicate(filter_predicate) {
897 // Advance to first element satisfying the predicate
898 while(!at_end() && !_predicate(_array->at(_position))) {
899 ++_position;
900 }
901 }
902
903 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
904 do {
905 // Advance to next element satisfying the predicate
906 ++_position;
907 } while(!at_end() && !_predicate(_array->at(_position)));
908 return *this;
909 }
910
911 E operator*() { return _array->at(_position); }
912
913 bool operator==(const GrowableArrayIterator<E>& rhs) {
914 assert(_array == rhs._array, "iterator belongs to different array");
915 return _position == rhs._position;
916 }
917
918 bool operator!=(const GrowableArrayIterator<E>& rhs) {
919 assert(_array == rhs._array, "iterator belongs to different array");
920 return _position != rhs._position;
921 }
922
923 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
924 assert(_array == rhs._array, "iterator belongs to different array");
925 return _position == rhs._position;
926 }
927
928 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
929 assert(_array == rhs._array, "iterator belongs to different array");
930 return _position != rhs._position;
931 }
932
933 bool at_end() const {
934 return _array == nullptr || _position == _array->end()._position;
935 }
936 };
937
938 // Arrays for basic types
939 typedef GrowableArray<int> intArray;
940 typedef GrowableArray<int> intStack;
941 typedef GrowableArray<bool> boolArray;
942
943 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|