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


 391     int new_len = _len + array_len;
 392     if (new_len >= _max) grow(new_len);
 393 
 394     for (int j = _len - 1; j >= idx; j--) {
 395       _data[j + array_len] = _data[j];
 396     }
 397 
 398     for (int j = 0; j < array_len; j++) {
 399       _data[idx + j] = array->_data[j];
 400     }
 401 
 402     _len += array_len;
 403   }
 404 
 405   void appendAll(const GrowableArray<E>* l) {
 406     for (int i = 0; i < l->_len; i++) {
 407       raw_at_put_grow(_len, l->_data[i], E());
 408     }
 409   }
 410 






 411   void sort(int f(E*,E*)) {
 412     qsort(_data, length(), sizeof(E), (_sort_Fn)f);
 413   }
 414   // sort by fixed-stride sub arrays:
 415   void sort(int f(E*,E*), int stride) {
 416     qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
 417   }
 418 
 419   // Binary search and insertion utility.  Search array for element
 420   // matching key according to the static compare function.  Insert
 421   // that element is not already in the list.  Assumes the list is
 422   // already sorted according to compare function.
 423   template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
 424     bool found;
 425     int location = find_sorted<E, compare>(key, found);
 426     if (!found) {
 427       insert_before(location, key);
 428     }
 429     return at(location);
 430   }


 560     assert(_array == rhs._array, "iterator belongs to different array");
 561     return _position == rhs._position;
 562   }
 563 
 564   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
 565     assert(_array == rhs._array, "iterator belongs to different array");
 566     return _position != rhs._position;
 567   }
 568 };
 569 
 570 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
 571 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator : public StackObj {
 572   friend class GrowableArray<E>;
 573 
 574  private:
 575   const GrowableArray<E>* _array;   // GrowableArray we iterate over
 576   int _position;                    // Current position in the GrowableArray
 577   UnaryPredicate _predicate;        // Unary predicate the elements of the GrowableArray should satisfy
 578 
 579  public:
 580   GrowableArrayFilterIterator(const GrowableArrayIterator<E>& begin, UnaryPredicate filter_predicate)
 581    : _array(begin._array), _position(begin._position), _predicate(filter_predicate) {
 582     // Advance to first element satisfying the predicate
 583     while(_position != _array->length() && !_predicate(_array->at(_position))) {
 584       ++_position;
 585     }
 586   }
 587 
 588   GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
 589     do {
 590       // Advance to next element satisfying the predicate
 591       ++_position;
 592     } while(_position != _array->length() && !_predicate(_array->at(_position)));
 593     return *this;
 594   }
 595 
 596   E operator*()   { return _array->at(_position); }
 597 
 598   bool operator==(const GrowableArrayIterator<E>& rhs)  {
 599     assert(_array == rhs._array, "iterator belongs to different array");
 600     return _position == rhs._position;
 601   }
 602 
 603   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
 604     assert(_array == rhs._array, "iterator belongs to different array");
 605     return _position != rhs._position;
 606   }
 607 
 608   bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 609     assert(_array == rhs._array, "iterator belongs to different array");
 610     return _position == rhs._position;
 611   }
 612 
 613   bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 614     assert(_array == rhs._array, "iterator belongs to different array");
 615     return _position != rhs._position;




 616   }
 617 };
 618 
 619 // Arrays for basic types
 620 typedef GrowableArray<int> intArray;
 621 typedef GrowableArray<int> intStack;
 622 typedef GrowableArray<bool> boolArray;
 623 
 624 #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 (...) {                                                      */


 392     int new_len = _len + array_len;
 393     if (new_len >= _max) grow(new_len);
 394 
 395     for (int j = _len - 1; j >= idx; j--) {
 396       _data[j + array_len] = _data[j];
 397     }
 398 
 399     for (int j = 0; j < array_len; j++) {
 400       _data[idx + j] = array->_data[j];
 401     }
 402 
 403     _len += array_len;
 404   }
 405 
 406   void appendAll(const GrowableArray<E>* l) {
 407     for (int i = 0; i < l->_len; i++) {
 408       raw_at_put_grow(_len, l->_data[i], E());
 409     }
 410   }
 411 
 412   void appendAll(const Array<E>* l) {
 413     for (int i = 0; i < l->length(); i++) {
 414       raw_at_put_grow(_len, l->at(i), E());
 415     }
 416   }
 417 
 418   void sort(int f(E*,E*)) {
 419     qsort(_data, length(), sizeof(E), (_sort_Fn)f);
 420   }
 421   // sort by fixed-stride sub arrays:
 422   void sort(int f(E*,E*), int stride) {
 423     qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
 424   }
 425 
 426   // Binary search and insertion utility.  Search array for element
 427   // matching key according to the static compare function.  Insert
 428   // that element is not already in the list.  Assumes the list is
 429   // already sorted according to compare function.
 430   template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
 431     bool found;
 432     int location = find_sorted<E, compare>(key, found);
 433     if (!found) {
 434       insert_before(location, key);
 435     }
 436     return at(location);
 437   }


 567     assert(_array == rhs._array, "iterator belongs to different array");
 568     return _position == rhs._position;
 569   }
 570 
 571   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
 572     assert(_array == rhs._array, "iterator belongs to different array");
 573     return _position != rhs._position;
 574   }
 575 };
 576 
 577 // Custom STL-style iterator to iterate over elements of a GrowableArray that satisfy a given predicate
 578 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator : public StackObj {
 579   friend class GrowableArray<E>;
 580 
 581  private:
 582   const GrowableArray<E>* _array;   // GrowableArray we iterate over
 583   int _position;                    // Current position in the GrowableArray
 584   UnaryPredicate _predicate;        // Unary predicate the elements of the GrowableArray should satisfy
 585 
 586  public:
 587   GrowableArrayFilterIterator(const GrowableArray<E>* array, UnaryPredicate filter_predicate)
 588    : _array(array), _position(0), _predicate(filter_predicate) {
 589     // Advance to first element satisfying the predicate
 590     while(!at_end() && !_predicate(_array->at(_position))) {
 591       ++_position;
 592     }
 593   }
 594 
 595   GrowableArrayFilterIterator<E, UnaryPredicate>& operator++() {
 596     do {
 597       // Advance to next element satisfying the predicate
 598       ++_position;
 599     } while(!at_end() && !_predicate(_array->at(_position)));
 600     return *this;
 601   }
 602 
 603   E operator*()   { return _array->at(_position); }
 604 
 605   bool operator==(const GrowableArrayIterator<E>& rhs)  {
 606     assert(_array == rhs._array, "iterator belongs to different array");
 607     return _position == rhs._position;
 608   }
 609 
 610   bool operator!=(const GrowableArrayIterator<E>& rhs)  {
 611     assert(_array == rhs._array, "iterator belongs to different array");
 612     return _position != rhs._position;
 613   }
 614 
 615   bool operator==(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 616     assert(_array == rhs._array, "iterator belongs to different array");
 617     return _position == rhs._position;
 618   }
 619 
 620   bool operator!=(const GrowableArrayFilterIterator<E, UnaryPredicate>& rhs)  {
 621     assert(_array == rhs._array, "iterator belongs to different array");
 622     return _position != rhs._position;
 623   }
 624 
 625   bool at_end() const {
 626     return _array == NULL || _position == _array->end()._position;
 627   }
 628 };
 629 
 630 // Arrays for basic types
 631 typedef GrowableArray<int> intArray;
 632 typedef GrowableArray<int> intStack;
 633 typedef GrowableArray<bool> boolArray;
 634 
 635 #endif // SHARE_UTILITIES_GROWABLEARRAY_HPP
< prev index next >