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/oop.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include "utilities/ostream.hpp"
33
34 // A growable array.
35
36 /*************************************************************************/
37 /* */
38 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */
39 /* */
40 /* Should you use GrowableArrays to contain handles you must be certain */
41 /* the the GrowableArray does not outlive the HandleMark that contains */
42 /* the handles. Since GrowableArrays are typically resource allocated */
43 /* the following is an example of INCORRECT CODE, */
44 /* */
45 /* ResourceMark rm; */
46 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */
47 /* if (blah) { */
48 /* while (...) { */
391 int new_len = _len + array_len;
392 if (new_len >= _max) grow(new_len);
393
394 for (int j = _len - 1; j >= idx; j--) {
395 _data[j + array_len] = _data[j];
396 }
397
398 for (int j = 0; j < array_len; j++) {
399 _data[idx + j] = array->_data[j];
400 }
401
402 _len += array_len;
403 }
404
405 void appendAll(const GrowableArray<E>* l) {
406 for (int i = 0; i < l->_len; i++) {
407 raw_at_put_grow(_len, l->_data[i], E());
408 }
409 }
410
411 void sort(int f(E*,E*)) {
412 qsort(_data, length(), sizeof(E), (_sort_Fn)f);
413 }
414 // sort by fixed-stride sub arrays:
415 void sort(int f(E*,E*), int stride) {
416 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
417 }
418
419 // Binary search and insertion utility. Search array for element
420 // matching key according to the static compare function. Insert
421 // that element is not already in the list. Assumes the list is
422 // already sorted according to compare function.
423 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
424 bool found;
425 int location = find_sorted<E, compare>(key, found);
426 if (!found) {
427 insert_before(location, key);
428 }
429 return at(location);
430 }
560 assert(_array == rhs._array, "iterator belongs to different array");
561 return _position == rhs._position;
562 }
563
564 bool operator!=(const GrowableArrayIterator<E>& rhs) {
565 assert(_array == rhs._array, "iterator belongs to different array");
566 return _position != rhs._position;
567 }
568 };
569
570 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
571 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator : public StackObj {
572 friend class GrowableArray<E>;
573
574 private:
575 const GrowableArray<E>* _array; // GrowableArray we iterate over
576 int _position; // Current position in the GrowableArray
577 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
578
579 public:
580 GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate)
581 : _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
582 // Advance to first element satisfying the predicate
583 while(_position != _array->length() && !_predicate(_array->at(_position))) {
584 ++_position;
585 }
586 }
587
588 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
589 do {
590 // Advance to next element satisfying the predicate
591 ++_position;
592 } while(_position != _array->length() && !_predicate(_array->at(_position)));
593 return *this;
594 }
595
596 E operator*() { return _array->at(_position); }
597
598 bool operator==(const GrowableArrayIterator<E>& rhs) {
599 assert(_array == rhs._array, "iterator belongs to different array");
600 return _position == rhs._position;
601 }
602
603 bool operator!=(const GrowableArrayIterator<E>& rhs) {
604 assert(_array == rhs._array, "iterator belongs to different array");
605 return _position != rhs._position;
606 }
607
608 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
609 assert(_array == rhs._array, "iterator belongs to different array");
610 return _position == rhs._position;
611 }
612
613 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
614 assert(_array == rhs._array, "iterator belongs to different array");
615 return _position != rhs._position;
616 }
617 };
618
619 // Arrays for basic types
620 typedef GrowableArray<int> intArray;
621 typedef GrowableArray<int> intStack;
622 typedef GrowableArray<bool> boolArray;
623
624 #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 "utilities/debug.hpp"
32 #include "utilities/globalDefinitions.hpp"
33 #include "utilities/ostream.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 /* the 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) { */
49 /* while (...) { */
392 int new_len = _len + array_len;
393 if (new_len >= _max) grow(new_len);
394
395 for (int j = _len - 1; j >= idx; j--) {
396 _data[j + array_len] = _data[j];
397 }
398
399 for (int j = 0; j < array_len; j++) {
400 _data[idx + j] = array->_data[j];
401 }
402
403 _len += array_len;
404 }
405
406 void appendAll(const GrowableArray<E>* l) {
407 for (int i = 0; i < l->_len; i++) {
408 raw_at_put_grow(_len, l->_data[i], E());
409 }
410 }
411
412 void appendAll(const Array<E>* l) {
413 for (int i = 0; i < l->length(); i++) {
414 raw_at_put_grow(_len, l->at(i), E());
415 }
416 }
417
418 void sort(int f(E*,E*)) {
419 qsort(_data, length(), sizeof(E), (_sort_Fn)f);
420 }
421 // sort by fixed-stride sub arrays:
422 void sort(int f(E*,E*), int stride) {
423 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
424 }
425
426 // Binary search and insertion utility. Search array for element
427 // matching key according to the static compare function. Insert
428 // that element is not already in the list. Assumes the list is
429 // already sorted according to compare function.
430 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
431 bool found;
432 int location = find_sorted<E, compare>(key, found);
433 if (!found) {
434 insert_before(location, key);
435 }
436 return at(location);
437 }
567 assert(_array == rhs._array, "iterator belongs to different array");
568 return _position == rhs._position;
569 }
570
571 bool operator!=(const GrowableArrayIterator<E>& rhs) {
572 assert(_array == rhs._array, "iterator belongs to different array");
573 return _position != rhs._position;
574 }
575 };
576
577 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
578 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator : public StackObj {
579 friend class GrowableArray<E>;
580
581 private:
582 const GrowableArray<E>* _array; // GrowableArray we iterate over
583 int _position; // Current position in the GrowableArray
584 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
585
586 public:
587 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate)
588 : _array(array), _position(0), _predicate(filter_predicate) {
589 // Advance to first element satisfying the predicate
590 while(!at_end() && !_predicate(_array->at(_position))) {
591 ++_position;
592 }
593 }
594
595 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
596 do {
597 // Advance to next element satisfying the predicate
598 ++_position;
599 } while(!at_end() && !_predicate(_array->at(_position)));
600 return *this;
601 }
602
603 E operator*() { return _array->at(_position); }
604
605 bool operator==(const GrowableArrayIterator<E>& rhs) {
606 assert(_array == rhs._array, "iterator belongs to different array");
607 return _position == rhs._position;
608 }
609
610 bool operator!=(const GrowableArrayIterator<E>& rhs) {
611 assert(_array == rhs._array, "iterator belongs to different array");
612 return _position != rhs._position;
613 }
614
615 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
616 assert(_array == rhs._array, "iterator belongs to different array");
617 return _position == rhs._position;
618 }
619
620 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
621 assert(_array == rhs._array, "iterator belongs to different array");
622 return _position != rhs._position;
623 }
624
625 bool at_end() const {
626 return _array == NULL || _position == _array->end()._position;
627 }
628 };
629
630 // Arrays for basic types
631 typedef GrowableArray<int> intArray;
632 typedef GrowableArray<int> intStack;
633 typedef GrowableArray<bool> boolArray;
634
635 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|