< 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) {                                                           */

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