1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
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 *
229 E const& at(int i) const {
230 assert(0 <= i && i < _len, "illegal index");
231 return _data[i];
232 }
233
234 E* adr_at(int i) const {
235 assert(0 <= i && i < _len, "illegal index");
236 return &_data[i];
237 }
238
239 E first() const {
240 assert(_len > 0, "empty list");
241 return _data[0];
242 }
243
244 E top() const {
245 assert(_len > 0, "empty list");
246 return _data[_len-1];
247 }
248
249 GrowableArrayIterator<E> begin() const {
250 return GrowableArrayIterator<E>(this, 0);
251 }
252
253 GrowableArrayIterator<E> end() const {
254 return GrowableArrayIterator<E>(this, length());
255 }
256
257 void push(const E& elem) { append(elem); }
258
259 E pop() {
260 assert(_len > 0, "empty list");
261 return _data[--_len];
262 }
263
264 void at_put(int i, const E& elem) {
265 assert(0 <= i && i < _len, "illegal index");
266 _data[i] = elem;
267 }
268
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 }
|
1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
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 *
229 E const& at(int i) const {
230 assert(0 <= i && i < _len, "illegal index");
231 return _data[i];
232 }
233
234 E* adr_at(int i) const {
235 assert(0 <= i && i < _len, "illegal index");
236 return &_data[i];
237 }
238
239 E first() const {
240 assert(_len > 0, "empty list");
241 return _data[0];
242 }
243
244 E top() const {
245 assert(_len > 0, "empty list");
246 return _data[_len-1];
247 }
248
249 E last() const {
250 return top();
251 }
252
253 GrowableArrayIterator<E> begin() const {
254 return GrowableArrayIterator<E>(this, 0);
255 }
256
257 GrowableArrayIterator<E> end() const {
258 return GrowableArrayIterator<E>(this, length());
259 }
260
261 void push(const E& elem) { append(elem); }
262
263 E pop() {
264 assert(_len > 0, "empty list");
265 return _data[--_len];
266 }
267
268 void at_put(int i, const E& elem) {
269 assert(0 <= i && i < _len, "illegal index");
270 _data[i] = elem;
271 }
272
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 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E();
427 for (i = 0; i < old_max; i++) _data[i].~E();
428 if (on_C_heap() && _data != NULL) {
429 FreeHeap(_data);
430 }
431 _data = newData;
432 }
|