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

 85   }
 86 
 87   ~GrowableArrayBase() {}
 88 
 89 public:
 90   int   length() const          { return _len; }
 91   int   capacity() const        { return _capacity; }
 92 
 93   bool  is_empty() const        { return _len == 0; }
 94   bool  is_nonempty() const     { return _len != 0; }
 95   bool  is_full() const         { return _len == _capacity; }
 96 
 97   void  clear()                 { _len = 0; }
 98   void  trunc_to(int length)    {
 99     assert(length <= _len,"cannot increase length");
100     _len = length;
101   }
102 };
103 
104 template <typename E> class GrowableArrayIterator;

105 
106 // Extends GrowableArrayBase with a typed data array.
107 //
108 // E: Element type
109 //
110 // The "view" adds function that don't grow or deallocate
111 // the _data array, so there's no need for an allocator.
112 //
113 // The "view" can be used to type erase the allocator classes
114 // of GrowableArrayWithAllocator.
115 template <typename E>
116 class GrowableArrayView : public GrowableArrayBase {
117 protected:
118   E* _data; // data array
119 
120   GrowableArrayView(E* data, int capacity, int initial_len) :
121       GrowableArrayBase(capacity, initial_len), _data(data) {}
122 
123   ~GrowableArrayView() {}
124 

463     int new_len = this->_len + array_len;
464     if (new_len >= this->_capacity) grow(new_len);
465 
466     for (int j = this->_len - 1; j >= idx; j--) {
467       this->_data[j + array_len] = this->_data[j];
468     }
469 
470     for (int j = 0; j < array_len; j++) {
471       this->_data[idx + j] = array->at(j);
472     }
473 
474     this->_len += array_len;
475   }
476 
477   void appendAll(const GrowableArrayView<E>* l) {
478     for (int i = 0; i < l->length(); i++) {
479       this->at_put_grow(this->_len, l->at(i), E());
480     }
481   }
482 






483   // Binary search and insertion utility.  Search array for element
484   // matching key according to the static compare function.  Insert
485   // that element if not already in the list.  Assumes the list is
486   // already sorted according to compare function.
487   template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
488     bool found;
489     int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
490     if (!found) {
491       insert_before(location, key);
492     }
493     return this->at(location);
494   }
495 
496   E insert_sorted(CompareClosure<E>* cc, const E& key) {
497     bool found;
498     int location = find_sorted(cc, key, found);
499     if (!found) {
500       insert_before(location, key);
501     }
502     return this->at(location);

843     this->clear_and_deallocate();
844   }
845 
846   void* operator new(size_t size) {
847     return AnyObj::operator new(size, MT);
848   }
849 
850   void* operator new(size_t size, const std::nothrow_t&  nothrow_constant) throw() {
851     return AnyObj::operator new(size, nothrow_constant, MT);
852   }
853   void operator delete(void *p) {
854     AnyObj::operator delete(p);
855   }
856 };
857 
858 // Custom STL-style iterator to iterate over GrowableArrays
859 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
860 template <typename E>
861 class GrowableArrayIterator : public StackObj {
862   friend class GrowableArrayView<E>;

863 
864  private:
865   const GrowableArrayView<E>* _array; // GrowableArray we iterate over
866   int _position;                      // The current position in the GrowableArray
867 
868   // Private constructor used in GrowableArray::begin() and GrowableArray::end()
869   GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
870     assert(0 <= position && position <= _array->length(), "illegal position");
871   }
872 
873  public:
874   GrowableArrayIterator() : _array(nullptr), _position(0) { }
875   GrowableArrayIterator& operator++() { ++_position; return *this; }
876   E operator*()                       { return _array->at(_position); }
877 
878   bool operator==(const GrowableArrayIterator& rhs)  {
879     assert(_array == rhs._array, "iterator belongs to different array");
880     return _position == rhs._position;
881   }
882 
883   bool operator!=(const GrowableArrayIterator& rhs)  {
884     assert(_array == rhs._array, "iterator belongs to different array");
885     return _position != rhs._position;
886   }
887 };
888 






















































889 // Arrays for basic types
890 typedef GrowableArray<int> intArray;
891 typedef GrowableArray<int> intStack;
892 typedef GrowableArray<bool> boolArray;
893 
894 #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) {                                                           */

 87   }
 88 
 89   ~GrowableArrayBase() {}
 90 
 91 public:
 92   int   length() const          { return _len; }
 93   int   capacity() const        { return _capacity; }
 94 
 95   bool  is_empty() const        { return _len == 0; }
 96   bool  is_nonempty() const     { return _len != 0; }
 97   bool  is_full() const         { return _len == _capacity; }
 98 
 99   void  clear()                 { _len = 0; }
100   void  trunc_to(int length)    {
101     assert(length <= _len,"cannot increase length");
102     _len = length;
103   }
104 };
105 
106 template <typename E> class GrowableArrayIterator;
107 template <typename E, typename UnaryPredicate> class GrowableArrayFilterIterator;
108 
109 // Extends GrowableArrayBase with a typed data array.
110 //
111 // E: Element type
112 //
113 // The "view" adds function that don't grow or deallocate
114 // the _data array, so there's no need for an allocator.
115 //
116 // The "view" can be used to type erase the allocator classes
117 // of GrowableArrayWithAllocator.
118 template <typename E>
119 class GrowableArrayView : public GrowableArrayBase {
120 protected:
121   E* _data; // data array
122 
123   GrowableArrayView(E* data, int capacity, int initial_len) :
124       GrowableArrayBase(capacity, initial_len), _data(data) {}
125 
126   ~GrowableArrayView() {}
127 

466     int new_len = this->_len + array_len;
467     if (new_len >= this->_capacity) grow(new_len);
468 
469     for (int j = this->_len - 1; j >= idx; j--) {
470       this->_data[j + array_len] = this->_data[j];
471     }
472 
473     for (int j = 0; j < array_len; j++) {
474       this->_data[idx + j] = array->at(j);
475     }
476 
477     this->_len += array_len;
478   }
479 
480   void appendAll(const GrowableArrayView<E>* l) {
481     for (int i = 0; i < l->length(); i++) {
482       this->at_put_grow(this->_len, l->at(i), E());
483     }
484   }
485 
486   void appendAll(const Array<E>* l) {
487     for (int i = 0; i < l->length(); i++) {
488       this->at_put_grow(this->_len, l->at(i), E());
489     }
490   }
491 
492   // Binary search and insertion utility.  Search array for element
493   // matching key according to the static compare function.  Insert
494   // that element if not already in the list.  Assumes the list is
495   // already sorted according to compare function.
496   template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
497     bool found;
498     int location = GrowableArrayView<E>::template find_sorted<E, compare>(key, found);
499     if (!found) {
500       insert_before(location, key);
501     }
502     return this->at(location);
503   }
504 
505   E insert_sorted(CompareClosure<E>* cc, const E& key) {
506     bool found;
507     int location = find_sorted(cc, key, found);
508     if (!found) {
509       insert_before(location, key);
510     }
511     return this->at(location);

852     this->clear_and_deallocate();
853   }
854 
855   void* operator new(size_t size) {
856     return AnyObj::operator new(size, MT);
857   }
858 
859   void* operator new(size_t size, const std::nothrow_t&  nothrow_constant) throw() {
860     return AnyObj::operator new(size, nothrow_constant, MT);
861   }
862   void operator delete(void *p) {
863     AnyObj::operator delete(p);
864   }
865 };
866 
867 // Custom STL-style iterator to iterate over GrowableArrays
868 // It is constructed by invoking GrowableArray::begin() and GrowableArray::end()
869 template <typename E>
870 class GrowableArrayIterator : public StackObj {
871   friend class GrowableArrayView<E>;
872   template <typename F, typename UnaryPredicate> friend class GrowableArrayFilterIterator;
873 
874  private:
875   const GrowableArrayView<E>* _array; // GrowableArray we iterate over
876   int _position;                      // The current position in the GrowableArray
877 
878   // Private constructor used in GrowableArray::begin() and GrowableArray::end()
879   GrowableArrayIterator(const GrowableArrayView<E>* array, int position) : _array(array), _position(position) {
880     assert(0 <= position && position <= _array->length(), "illegal position");
881   }
882 
883  public:
884   GrowableArrayIterator() : _array(nullptr), _position(0) { }
885   GrowableArrayIterator& operator++() { ++_position; return *this; }
886   E operator*()                       { return _array->at(_position); }
887 
888   bool operator==(const GrowableArrayIterator& rhs)  {
889     assert(_array == rhs._array, "iterator belongs to different array");
890     return _position == rhs._position;
891   }
892 
893   bool operator!=(const GrowableArrayIterator& rhs)  {
894     assert(_array == rhs._array, "iterator belongs to different array");
895     return _position != rhs._position;
896   }
897 };
898 
899 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
900 template <typename E, class UnaryPredicate>
901 class GrowableArrayFilterIterator : public StackObj {
902   friend class GrowableArrayView<E>;
903 
904  private:
905   const GrowableArrayView<E>* _array; // GrowableArray we iterate over
906   int _position;                      // Current position in the GrowableArray
907   UnaryPredicate _predicate;          // Unary predicate the elements of the GrowableArray should satisfy
908 
909  public:
910   GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate) :
911       _array(array), _position(0), _predicate(filter_predicate) {
912     // Advance to first element satisfying the predicate
913     while(!at_end() && !_predicate(_array->at(_position))) {
914       ++_position;
915     }
916   }
917 
918   GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
919     do {
920       // Advance to next element satisfying the predicate
921       ++_position;
922     } while(!at_end() && !_predicate(_array->at(_position)));
923     return *this;
924   }
925 
926   E operator*() { return _array->at(_position); }
927 
928   bool operator==(const GrowableArrayIterator<E>& rhs)  {
929     assert(_array == rhs._array, "iterator belongs to different array");
930     return _position == rhs._position;
931   }
932 
933   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
934     assert(_array == rhs._array, "iterator belongs to different array");
935     return _position != rhs._position;
936   }
937 
938   bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
939     assert(_array == rhs._array, "iterator belongs to different array");
940     return _position == rhs._position;
941   }
942 
943   bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
944     assert(_array == rhs._array, "iterator belongs to different array");
945     return _position != rhs._position;
946   }
947 
948   bool at_end() const {
949     return _array == nullptr || _position == _array->end()._position;
950   }
951 };
952 
953 // Arrays for basic types
954 typedef GrowableArray<int> intArray;
955 typedef GrowableArray<int> intStack;
956 typedef GrowableArray<bool> boolArray;
957 
958 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
< prev index next >