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) { */
428 int new_len = this->_len + array_len;
429 if (new_len >= this->_max) grow(new_len);
430
431 for (int j = this->_len - 1; j >= idx; j--) {
432 this->_data[j + array_len] = this->_data[j];
433 }
434
435 for (int j = 0; j < array_len; j++) {
436 this->_data[idx + j] = array->at(j);
437 }
438
439 this->_len += array_len;
440 }
441
442 void appendAll(const GrowableArrayView<E>* l) {
443 for (int i = 0; i < l->length(); i++) {
444 this->at_put_grow(this->_len, l->at(i), E());
445 }
446 }
447
448 // Binary search and insertion utility. Search array for element
449 // matching key according to the static compare function. Insert
450 // that element if not already in the list. Assumes the list is
451 // already sorted according to compare function.
452 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
453 bool found;
454 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
455 if (!found) {
456 insert_before(location, key);
457 }
458 return this->at(location);
459 }
460
461 E insert_sorted(CompareClosure<E>* cc, const E& key) {
462 bool found;
463 int location = find_sorted(cc, key, found);
464 if (!found) {
465 insert_before(location, key);
466 }
467 return this->at(location);
774 return _position == rhs._position;
775 }
776
777 bool operator!=(const GrowableArrayIterator<E>& rhs) {
778 assert(_array == rhs._array, "iterator belongs to different array");
779 return _position != rhs._position;
780 }
781 };
782
783 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
784 template <typename E, class UnaryPredicate>
785 class GrowableArrayFilterIterator : public StackObj {
786 friend class GrowableArrayView<E>;
787
788 private:
789 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
790 int _position; // Current position in the GrowableArray
791 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
792
793 public:
794 GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate) :
795 _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
796 // Advance to first element satisfying the predicate
797 while(_position != _array->length() && !_predicate(_array->at(_position))) {
798 ++_position;
799 }
800 }
801
802 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
803 do {
804 // Advance to next element satisfying the predicate
805 ++_position;
806 } while(_position != _array->length() && !_predicate(_array->at(_position)));
807 return *this;
808 }
809
810 E operator*() { return _array->at(_position); }
811
812 bool operator==(const GrowableArrayIterator<E>& rhs) {
813 assert(_array == rhs._array, "iterator belongs to different array");
814 return _position == rhs._position;
815 }
816
817 bool operator!=(const GrowableArrayIterator<E>& rhs) {
818 assert(_array == rhs._array, "iterator belongs to different array");
819 return _position != rhs._position;
820 }
821
822 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
823 assert(_array == rhs._array, "iterator belongs to different array");
824 return _position == rhs._position;
825 }
826
827 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
828 assert(_array == rhs._array, "iterator belongs to different array");
829 return _position != rhs._position;
830 }
831 };
832
833 // Arrays for basic types
834 typedef GrowableArray<int> intArray;
835 typedef GrowableArray<int> intStack;
836 typedef GrowableArray<bool> boolArray;
837
838 #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) { */
430 int new_len = this->_len + array_len;
431 if (new_len >= this->_max) grow(new_len);
432
433 for (int j = this->_len - 1; j >= idx; j--) {
434 this->_data[j + array_len] = this->_data[j];
435 }
436
437 for (int j = 0; j < array_len; j++) {
438 this->_data[idx + j] = array->at(j);
439 }
440
441 this->_len += array_len;
442 }
443
444 void appendAll(const GrowableArrayView<E>* l) {
445 for (int i = 0; i < l->length(); i++) {
446 this->at_put_grow(this->_len, l->at(i), E());
447 }
448 }
449
450 void appendAll(const Array<E>* l) {
451 for (int i = 0; i < l->length(); i++) {
452 this->at_put_grow(this->_len, l->at(i), E());
453 }
454 }
455
456 // Binary search and insertion utility. Search array for element
457 // matching key according to the static compare function. Insert
458 // that element if not already in the list. Assumes the list is
459 // already sorted according to compare function.
460 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
461 bool found;
462 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
463 if (!found) {
464 insert_before(location, key);
465 }
466 return this->at(location);
467 }
468
469 E insert_sorted(CompareClosure<E>* cc, const E& key) {
470 bool found;
471 int location = find_sorted(cc, key, found);
472 if (!found) {
473 insert_before(location, key);
474 }
475 return this->at(location);
782 return _position == rhs._position;
783 }
784
785 bool operator!=(const GrowableArrayIterator<E>& rhs) {
786 assert(_array == rhs._array, "iterator belongs to different array");
787 return _position != rhs._position;
788 }
789 };
790
791 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
792 template <typename E, class UnaryPredicate>
793 class GrowableArrayFilterIterator : public StackObj {
794 friend class GrowableArrayView<E>;
795
796 private:
797 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
798 int _position; // Current position in the GrowableArray
799 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
800
801 public:
802 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate) :
803 _array(array), _position(0), _predicate(filter_predicate) {
804 // Advance to first element satisfying the predicate
805 while(!at_end() && !_predicate(_array->at(_position))) {
806 ++_position;
807 }
808 }
809
810 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
811 do {
812 // Advance to next element satisfying the predicate
813 ++_position;
814 } while(!at_end() && !_predicate(_array->at(_position)));
815 return *this;
816 }
817
818 E operator*() { return _array->at(_position); }
819
820 bool operator==(const GrowableArrayIterator<E>& rhs) {
821 assert(_array == rhs._array, "iterator belongs to different array");
822 return _position == rhs._position;
823 }
824
825 bool operator!=(const GrowableArrayIterator<E>& rhs) {
826 assert(_array == rhs._array, "iterator belongs to different array");
827 return _position != rhs._position;
828 }
829
830 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
831 assert(_array == rhs._array, "iterator belongs to different array");
832 return _position == rhs._position;
833 }
834
835 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
836 assert(_array == rhs._array, "iterator belongs to different array");
837 return _position != rhs._position;
838 }
839
840 bool at_end() const {
841 return _array == NULL || _position == _array->end()._position;
842 }
843 };
844
845 // Arrays for basic types
846 typedef GrowableArray<int> intArray;
847 typedef GrowableArray<int> intStack;
848 typedef GrowableArray<bool> boolArray;
849
850 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|