< prev index next >

src/share/vm/utilities/growableArray.hpp

Print this page




 151 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator;
 152 
 153 template<class E> class GrowableArray : public GenericGrowableArray {
 154   friend class VMStructs;
 155 
 156  private:
 157   E*     _data;         // data array
 158 
 159   void grow(int j);
 160   void raw_at_put_grow(int i, const E& p, const E& fill);
 161   void  clear_and_deallocate();
 162  public:
 163   GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
 164     _data = (E*)raw_allocate(thread, sizeof(E));
 165     for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
 166   }
 167 
 168   GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
 169     : GenericGrowableArray(initial_size, 0, C_heap, F) {
 170     _data = (E*)raw_allocate(sizeof(E));




 171     for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
 172   }
 173 
 174   GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
 175     : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
 176     _data = (E*)raw_allocate(sizeof(E));
 177     int i = 0;
 178     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 179     for (; i < _max; i++) ::new ((void*)&_data[i]) E();
 180   }
 181 
 182   GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
 183     _data = (E*)raw_allocate(sizeof(E));
 184     int i = 0;
 185     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 186     for (; i < _max; i++) ::new ((void*)&_data[i]) E();
 187   }
 188 
 189   GrowableArray() : GenericGrowableArray(2, 0, false) {
 190     _data = (E*)raw_allocate(sizeof(E));


 355     for (int j = _len - 1; j >= idx; j--) {
 356       _data[j + 1] = _data[j];
 357     }
 358     _len++;
 359     _data[idx] = elem;
 360   }
 361 
 362   void appendAll(const GrowableArray<E>* l) {
 363     for (int i = 0; i < l->_len; i++) {
 364       raw_at_put_grow(_len, l->_data[i], E());
 365     }
 366   }
 367 
 368   void sort(int f(E*,E*)) {
 369     qsort(_data, length(), sizeof(E), (_sort_Fn)f);
 370   }
 371   // sort by fixed-stride sub arrays:
 372   void sort(int f(E*,E*), int stride) {
 373     qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
 374   }


































 375 };
 376 
 377 // Global GrowableArray methods (one instance in the library per each 'E' type).
 378 
 379 template<class E> void GrowableArray<E>::grow(int j) {
 380     // grow the array by doubling its size (amortized growth)
 381     int old_max = _max;
 382     if (_max == 0) _max = 1; // prevent endless loop
 383     while (j >= _max) _max = _max*2;
 384     // j < _max
 385     E* newData = (E*)raw_allocate(sizeof(E));
 386     int i = 0;
 387     for (     ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);




 388     for (     ; i < _max; i++) ::new ((void*)&newData[i]) E();
 389     for (i = 0; i < old_max; i++) _data[i].~E();
 390     if (on_C_heap() && _data != NULL) {
 391       FreeHeap(_data);
 392     }
 393     _data = newData;
 394 }
 395 
 396 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
 397     if (i >= _len) {
 398       if (i >= _max) grow(i);
 399       for (int j = _len; j < i; j++)
 400         _data[j] = fill;
 401       _len = i+1;
 402     }
 403     _data[i] = p;
 404 }
 405 
 406 // This function clears and deallocate the data in the growable array that
 407 // has been allocated on the C heap.  It's not public - called by the




 151 template<class E, class UnaryPredicate> class GrowableArrayFilterIterator;
 152 
 153 template<class E> class GrowableArray : public GenericGrowableArray {
 154   friend class VMStructs;
 155 
 156  private:
 157   E*     _data;         // data array
 158 
 159   void grow(int j);
 160   void raw_at_put_grow(int i, const E& p, const E& fill);
 161   void  clear_and_deallocate();
 162  public:
 163   GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) {
 164     _data = (E*)raw_allocate(thread, sizeof(E));
 165     for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
 166   }
 167 
 168   GrowableArray(int initial_size, bool C_heap = false, MEMFLAGS F = mtInternal)
 169     : GenericGrowableArray(initial_size, 0, C_heap, F) {
 170     _data = (E*)raw_allocate(sizeof(E));
 171 // Needed for Visual Studio 2012 and older
 172 #ifdef _MSC_VER
 173 #pragma warning(suppress: 4345)
 174 #endif
 175     for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E();
 176   }
 177 
 178   GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false, MEMFLAGS memflags = mtInternal)
 179     : GenericGrowableArray(initial_size, initial_len, C_heap, memflags) {
 180     _data = (E*)raw_allocate(sizeof(E));
 181     int i = 0;
 182     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 183     for (; i < _max; i++) ::new ((void*)&_data[i]) E();
 184   }
 185 
 186   GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) {
 187     _data = (E*)raw_allocate(sizeof(E));
 188     int i = 0;
 189     for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler);
 190     for (; i < _max; i++) ::new ((void*)&_data[i]) E();
 191   }
 192 
 193   GrowableArray() : GenericGrowableArray(2, 0, false) {
 194     _data = (E*)raw_allocate(sizeof(E));


 359     for (int j = _len - 1; j >= idx; j--) {
 360       _data[j + 1] = _data[j];
 361     }
 362     _len++;
 363     _data[idx] = elem;
 364   }
 365 
 366   void appendAll(const GrowableArray<E>* l) {
 367     for (int i = 0; i < l->_len; i++) {
 368       raw_at_put_grow(_len, l->_data[i], E());
 369     }
 370   }
 371 
 372   void sort(int f(E*,E*)) {
 373     qsort(_data, length(), sizeof(E), (_sort_Fn)f);
 374   }
 375   // sort by fixed-stride sub arrays:
 376   void sort(int f(E*,E*), int stride) {
 377     qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f);
 378   }
 379 
 380   // Binary search and insertion utility.  Search array for element
 381   // matching key according to the static compare function.  Insert
 382   // that element is not already in the list.  Assumes the list is
 383   // already sorted according to compare function.
 384   template <int compare(const E&, const E&)> E insert_sorted(const E& key) {
 385     bool found;
 386     int location = find_sorted<E, compare>(key, found);
 387     if (!found) {
 388       insert_before(location, key);
 389     }
 390     return at(location);
 391   }
 392 
 393   template <typename K, int compare(const K&, const E&)> int find_sorted(const K& key, bool& found) {
 394     found = false;
 395     int min = 0;
 396     int max = length() - 1;
 397 
 398     while (max >= min) {
 399       int mid = (int)(((uint)max + min) / 2);
 400       E value = at(mid);
 401       int diff = compare(key, value);
 402       if (diff > 0) {
 403         min = mid + 1;
 404       } else if (diff < 0) {
 405         max = mid - 1;
 406       } else {
 407         found = true;
 408         return mid;
 409       }
 410     }
 411     return min;
 412   }
 413 };
 414 
 415 // Global GrowableArray methods (one instance in the library per each 'E' type).
 416 
 417 template<class E> void GrowableArray<E>::grow(int j) {
 418     // grow the array by doubling its size (amortized growth)
 419     int old_max = _max;
 420     if (_max == 0) _max = 1; // prevent endless loop
 421     while (j >= _max) _max = _max*2;
 422     // j < _max
 423     E* newData = (E*)raw_allocate(sizeof(E));
 424     int i = 0;
 425     for (     ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]);
 426 // Needed for Visual Studio 2012 and older
 427 #ifdef _MSC_VER
 428 #pragma warning(suppress: 4345)
 429 #endif
 430     for (     ; i < _max; i++) ::new ((void*)&newData[i]) E();
 431     for (i = 0; i < old_max; i++) _data[i].~E();
 432     if (on_C_heap() && _data != NULL) {
 433       FreeHeap(_data);
 434     }
 435     _data = newData;
 436 }
 437 
 438 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) {
 439     if (i >= _len) {
 440       if (i >= _max) grow(i);
 441       for (int j = _len; j < i; j++)
 442         _data[j] = fill;
 443       _len = i+1;
 444     }
 445     _data[i] = p;
 446 }
 447 
 448 // This function clears and deallocate the data in the growable array that
 449 // has been allocated on the C heap.  It's not public - called by the


< prev index next >