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