< 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);

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

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






















































885 // Arrays for basic types
886 typedef GrowableArray<int> intArray;
887 typedef GrowableArray<int> intStack;
888 typedef GrowableArray<bool> boolArray;
889 
890 #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);

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