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 (...) { */
385 int new_len = _len + array_len;
386 if (new_len >= _max) grow(new_len);
387
388 for (int j = _len - 1; j >= idx; j--) {
389 _data[j + array_len] = _data[j];
390 }
391
392 for (int j = 0; j < array_len; j++) {
393 _data[idx + j] = array->_data[j];
394 }
395
396 _len += array_len;
397 }
398
399 void appendAll(const GrowableArray<E>* l) {
400 for (int i = 0; i < l->_len; i++) {
401 raw_at_put_grow(_len, l->_data[i], E());
402 }
403 }
404
405 void sort(int f(E*,E*)) {
406 qsort(_data, length(), sizeof(E), (_sort_Fn)f);
407 }
408 // sort by fixed-stride sub arrays:
409 void sort(int f(E*,E*), int stride) {
410 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
411 }
412
413 // Binary search and insertion utility. Search array for element
414 // matching key according to the static compare function. Insert
415 // that element is not already in the list. Assumes the list is
416 // already sorted according to compare function.
417 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
418 bool found;
419 int location = find_sorted<E, compare>(key, found);
420 if (!found) {
421 insert_before(location, key);
422 }
423 return at(location);
424 }
523 assert(_array == rhs._array, "iterator belongs to different array");
524 return _position == rhs._position;
525 }
526
527 bool operator!=(const GrowableArrayIterator<E>& rhs) {
528 assert(_array == rhs._array, "iterator belongs to different array");
529 return _position != rhs._position;
530 }
531 };
532
533 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
534 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator : public StackObj {
535 friend class GrowableArray<E>;
536
537 private:
538 const GrowableArray<E>* _array; // GrowableArray we iterate over
539 int _position; // Current position in the GrowableArray
540 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
541
542 public:
543 GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate)
544 : _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
545 // Advance to first element satisfying the predicate
546 while(_position != _array->length() && !_predicate(_array->at(_position))) {
547 ++_position;
548 }
549 }
550
551 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
552 do {
553 // Advance to next element satisfying the predicate
554 ++_position;
555 } while(_position != _array->length() && !_predicate(_array->at(_position)));
556 return *this;
557 }
558
559 E operator*() { return _array->at(_position); }
560
561 bool operator==(const GrowableArrayIterator<E>& rhs) {
562 assert(_array == rhs._array, "iterator belongs to different array");
563 return _position == rhs._position;
564 }
565
566 bool operator!=(const GrowableArrayIterator<E>& rhs) {
567 assert(_array == rhs._array, "iterator belongs to different array");
568 return _position != rhs._position;
569 }
570
571 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
572 assert(_array == rhs._array, "iterator belongs to different array");
573 return _position == rhs._position;
574 }
575
576 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
577 assert(_array == rhs._array, "iterator belongs to different array");
578 return _position != rhs._position;
579 }
580 };
581
582 // Arrays for basic types
583 typedef GrowableArray<int> intArray;
584 typedef GrowableArray<int> intStack;
585 typedef GrowableArray<bool> boolArray;
586
587 #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 (...) { */
386 int new_len = _len + array_len;
387 if (new_len >= _max) grow(new_len);
388
389 for (int j = _len - 1; j >= idx; j--) {
390 _data[j + array_len] = _data[j];
391 }
392
393 for (int j = 0; j < array_len; j++) {
394 _data[idx + j] = array->_data[j];
395 }
396
397 _len += array_len;
398 }
399
400 void appendAll(const GrowableArray<E>* l) {
401 for (int i = 0; i < l->_len; i++) {
402 raw_at_put_grow(_len, l->_data[i], E());
403 }
404 }
405
406 void appendAll(const Array<E>* l) {
407 for (int i = 0; i < l->length(); i++) {
408 raw_at_put_grow(_len, l->at(i), E());
409 }
410 }
411
412 void sort(int f(E*,E*)) {
413 qsort(_data, length(), sizeof(E), (_sort_Fn)f);
414 }
415 // sort by fixed-stride sub arrays:
416 void sort(int f(E*,E*), int stride) {
417 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
418 }
419
420 // Binary search and insertion utility. Search array for element
421 // matching key according to the static compare function. Insert
422 // that element is not already in the list. Assumes the list is
423 // already sorted according to compare function.
424 template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
425 bool found;
426 int location = find_sorted<E, compare>(key, found);
427 if (!found) {
428 insert_before(location, key);
429 }
430 return at(location);
431 }
530 assert(_array == rhs._array, "iterator belongs to different array");
531 return _position == rhs._position;
532 }
533
534 bool operator!=(const GrowableArrayIterator<E>& rhs) {
535 assert(_array == rhs._array, "iterator belongs to different array");
536 return _position != rhs._position;
537 }
538 };
539
540 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
541 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator : public StackObj {
542 friend class GrowableArray<E>;
543
544 private:
545 const GrowableArray<E>* _array; // GrowableArray we iterate over
546 int _position; // Current position in the GrowableArray
547 UnaryPredicate _predicate; // Unary predicate the elements of the GrowableArray should satisfy
548
549 public:
550 GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate)
551 : _array(array), _position(0), _predicate(filter_predicate) {
552 // Advance to first element satisfying the predicate
553 while(!at_end() && !_predicate(_array->at(_position))) {
554 ++_position;
555 }
556 }
557
558 GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
559 do {
560 // Advance to next element satisfying the predicate
561 ++_position;
562 } while(!at_end() && !_predicate(_array->at(_position)));
563 return *this;
564 }
565
566 E operator*() { return _array->at(_position); }
567
568 bool operator==(const GrowableArrayIterator<E>& rhs) {
569 assert(_array == rhs._array, "iterator belongs to different array");
570 return _position == rhs._position;
571 }
572
573 bool operator!=(const GrowableArrayIterator<E>& rhs) {
574 assert(_array == rhs._array, "iterator belongs to different array");
575 return _position != rhs._position;
576 }
577
578 bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
579 assert(_array == rhs._array, "iterator belongs to different array");
580 return _position == rhs._position;
581 }
582
583 bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs) {
584 assert(_array == rhs._array, "iterator belongs to different array");
585 return _position != rhs._position;
586 }
587
588 bool at_end() const {
589 return _array == NULL || _position == _array->end()._position;
590 }
591 };
592
593 // Arrays for basic types
594 typedef GrowableArray<int> intArray;
595 typedef GrowableArray<int> intStack;
596 typedef GrowableArray<bool> boolArray;
597
598 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
|