< prev index next >

src/hotspot/share/utilities/growableArray.hpp

Print this page

  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
< prev index next >