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