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) { */
396 int new_len = this->_len + array_len;
397 if (new_len >= this->_max) grow(new_len);
398
399 for (int j = this->_len - 1; j >= idx; j--) {
400 this->_data[j + array_len] = this->_data[j];
401 }
402
403 for (int j = 0; j < array_len; j++) {
404 this->_data[idx + j] = array->at(j);
405 }
406
407 this->_len += array_len;
408 }
409
410 void appendAll(const GrowableArrayView<E>* l) {
411 for (int i = 0; i < l->length(); i++) {
412 this->at_put_grow(this->_len, l->at(i), E());
413 }
414 }
415
416 // Binary search and insertion utility. Search array for element
417 // matching key according to the static compare function. Insert
418 // that element is not already in the list. Assumes the list is
419 // already sorted according to compare function.
420 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
421 bool found;
422 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
423 if (!found) {
424 insert_before(location, key);
425 }
426 return this->at(location);
427 }
428
429 E insert_sorted(CompareClosure<E>* cc, const E& key) {
430 bool found;
431 int location = find_sorted(cc, key, found);
432 if (!found) {
433 insert_before(location, key);
434 }
435 return this->at(location);
736 return _position == rhs._position;
737 }
738
739 bool operator!=(const GrowableArrayIterator<E>& rhs) {
740 assert(_array == rhs._array, "iterator belongs to different array");
741 return _position != rhs._position;
742 }
743 };
744
745 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
746 template <typename E, class UnaryPredicate>
747 class GrowableArrayFilterIterator : public StackObj {
748 friend class GrowableArrayView<E>;
749
750 private:
751 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
752 int _position; // Current position in the GrowableArray
753 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
754
755 public:
756 GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate) :
757 _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
758 // Advance to first element satisfying the predicate
759 while(_position != _array->length() && !_predicate(_array->at(_position))) {
760 ++_position;
761 }
762 }
763
764 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
765 do {
766 // Advance to next element satisfying the predicate
767 ++_position;
768 } while(_position != _array->length() && !_predicate(_array->at(_position)));
769 return *this;
770 }
771
772 E operator*() { return _array->at(_position); }
773
774 bool operator==(const GrowableArrayIterator<E>& rhs) {
775 assert(_array == rhs._array, "iterator belongs to different array");
776 return _position == rhs._position;
777 }
778
779 bool operator!=(const GrowableArrayIterator<E>& rhs) {
780 assert(_array == rhs._array, "iterator belongs to different array");
781 return _position != rhs._position;
782 }
783
784 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
785 assert(_array == rhs._array, "iterator belongs to different array");
786 return _position == rhs._position;
787 }
788
789 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
790 assert(_array == rhs._array, "iterator belongs to different array");
791 return _position != rhs._position;
792 }
793 };
794
795 // Arrays for basic types
796 typedef GrowableArray<int> intArray;
797 typedef GrowableArray<int> intStack;
798 typedef GrowableArray<bool> boolArray;
799
800 #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) { */
398 int new_len = this->_len + array_len;
399 if (new_len >= this->_max) grow(new_len);
400
401 for (int j = this->_len - 1; j >= idx; j--) {
402 this->_data[j + array_len] = this->_data[j];
403 }
404
405 for (int j = 0; j < array_len; j++) {
406 this->_data[idx + j] = array->at(j);
407 }
408
409 this->_len += array_len;
410 }
411
412 void appendAll(const GrowableArrayView<E>* l) {
413 for (int i = 0; i < l->length(); i++) {
414 this->at_put_grow(this->_len, l->at(i), E());
415 }
416 }
417
418 void appendAll(const Array<E>* l) {
419 for (int i = 0; i < l->length(); i++) {
420 this->at_put_grow(this->_len, l->at(i), E());
421 }
422 }
423
424 // Binary search and insertion utility. Search array for element
425 // matching key according to the static compare function. Insert
426 // that element is not already in the list. Assumes the list is
427 // already sorted according to compare function.
428 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
429 bool found;
430 int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
431 if (!found) {
432 insert_before(location, key);
433 }
434 return this->at(location);
435 }
436
437 E insert_sorted(CompareClosure<E>* cc, const E& key) {
438 bool found;
439 int location = find_sorted(cc, key, found);
440 if (!found) {
441 insert_before(location, key);
442 }
443 return this->at(location);
744 return _position == rhs._position;
745 }
746
747 bool operator!=(const GrowableArrayIterator<E>& rhs) {
748 assert(_array == rhs._array, "iterator belongs to different array");
749 return _position != rhs._position;
750 }
751 };
752
753 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
754 template <typename E, class UnaryPredicate>
755 class GrowableArrayFilterIterator : public StackObj {
756 friend class GrowableArrayView<E>;
757
758 private:
759 const GrowableArrayView<E>* _array; // GrowableArray we iterate over
760 int _position; // Current position in the GrowableArray
761 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
762
763 public:
764 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate) :
765 _array(array), _position(0), _predicate(filter_predicate) {
766 // Advance to first element satisfying the predicate
767 while(!at_end() && !_predicate(_array->at(_position))) {
768 ++_position;
769 }
770 }
771
772 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
773 do {
774 // Advance to next element satisfying the predicate
775 ++_position;
776 } while(!at_end() && !_predicate(_array->at(_position)));
777 return *this;
778 }
779
780 E operator*() { return _array->at(_position); }
781
782 bool operator==(const GrowableArrayIterator<E>& rhs) {
783 assert(_array == rhs._array, "iterator belongs to different array");
784 return _position == rhs._position;
785 }
786
787 bool operator!=(const GrowableArrayIterator<E>& rhs) {
788 assert(_array == rhs._array, "iterator belongs to different array");
789 return _position != rhs._position;
790 }
791
792 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
793 assert(_array == rhs._array, "iterator belongs to different array");
794 return _position == rhs._position;
795 }
796
797 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
798 assert(_array == rhs._array, "iterator belongs to different array");
799 return _position != rhs._position;
800 }
801
802 bool at_end() const {
803 return _array == NULL || _position == _array->end()._position;
804 }
805 };
806
807 // Arrays for basic types
808 typedef GrowableArray<int> intArray;
809 typedef GrowableArray<int> intStack;
810 typedef GrowableArray<bool> boolArray;
811
812 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|