1 /*
2 * Copyright (c) 1997, 2024, 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. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package org.openjdk.bench.valhalla.sandbox.corelibs;
27
28 import java.util.Arrays;
29 import java.util.ConcurrentModificationException;
30 import java.util.Objects;
31 import java.util.NoSuchElementException;
32 import java.util.function.Consumer;
33 import java.util.function.IntConsumer;
34 import java.util.function.Predicate;
35 import java.util.function.UnaryOperator;
36
37 /**
38 * Resizable-array implementation like {@code ArrayList<PrimitiveInt>}.
39 */
40 public class ArrayListPrimitiveInt
41 // extends AbstractList<E>
42 // implements List<int>, RandomAccess, Cloneable, java.io.Serializable
43 {
44 @java.io.Serial
45 private static final long serialVersionUID = 8683452581122892189L;
46
47 /**
48 * Default initial capacity.
49 */
50 private static final int DEFAULT_CAPACITY = 10;
51
52 /**
53 * Shared empty array instance used for empty instances.
54 */
55 private static final PrimitiveInt[] EMPTY_ELEMENTDATA = {};
56
57 /**
58 * Shared empty array instance used for default sized empty instances. We
59 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
60 * first element is added.
61 */
62 private static final PrimitiveInt[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new PrimitiveInt[0];
63
64 /**
65 * The array buffer into which the elements of the ArrayList are stored.
66 * The capacity of the ArrayList is the length of this array buffer. Any
67 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
68 * will be expanded to DEFAULT_CAPACITY when the first element is added.
69 */
70 transient PrimitiveInt[] elementData; // non-private to simplify nested class access
71
72 protected transient int modCount = 0;
73
74 /**
75 * The size of the ArrayList (the number of elements it contains).
76 *
77 * @serial
78 */
79 private int size;
80
81 /**
82 * Constructs an empty list with the specified initial capacity.
83 *
84 * @param initialCapacity the initial capacity of the list
85 * @throws IllegalArgumentException if the specified initial capacity
86 * is negative
87 */
88 public ArrayListPrimitiveInt(int initialCapacity) {
89 if (initialCapacity > 0) {
90 this.elementData = new PrimitiveInt[initialCapacity];
91 } else if (initialCapacity == 0) {
92 this.elementData = EMPTY_ELEMENTDATA;
93 } else {
94 throw new IllegalArgumentException("Illegal Capacity: "+
95 initialCapacity);
96 }
97 }
98
99 /**
100 * Constructs an empty list with an initial capacity of ten.
101 */
102 public ArrayListPrimitiveInt() {
103 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
104 }
105
106 /**
107 * Trims the capacity of this {@code ArrayList} instance to be the
108 * list's current size. An application can use this operation to minimize
109 * the storage of an {@code ArrayList} instance.
110 */
111 public void trimToSize() {
112 modCount++;
113 if (size < elementData.length) {
114 elementData = (size == 0)
115 ? EMPTY_ELEMENTDATA
116 : (PrimitiveInt[])Arrays.copyOf(elementData, size);
117 }
118 }
119
120 /**
121 * Increases the capacity of this {@code ArrayList} instance, if
122 * necessary, to ensure that it can hold at least the number of elements
123 * specified by the minimum capacity argument.
124 *
125 * @param minCapacity the desired minimum capacity
126 */
127 public void ensureCapacity(int minCapacity) {
128 if (minCapacity > elementData.length
129 && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
130 && minCapacity <= DEFAULT_CAPACITY)) {
131 modCount++;
132 grow(minCapacity);
133 }
134 }
135
136 /**
137 * Increases the capacity to ensure that it can hold at least the
138 * number of elements specified by the minimum capacity argument.
139 *
140 * @param minCapacity the desired minimum capacity
141 * @throws OutOfMemoryError if minCapacity is less than zero
142 */
143 private PrimitiveInt[] grow(int minCapacity) {
144 int oldCapacity = elementData.length;
145 if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
146 int newCapacity = newLength(oldCapacity,
147 minCapacity - oldCapacity, /* minimum growth */
148 oldCapacity >> 1 /* preferred growth */);
149 return elementData = (PrimitiveInt[])Arrays.copyOf(elementData, newCapacity);
150 } else {
151 return elementData = new PrimitiveInt[Math.max(DEFAULT_CAPACITY, minCapacity)];
152 }
153 }
154
155 private PrimitiveInt[] grow() {
156 return grow(size + 1);
157 }
158
159 /**
160 * Returns the number of elements in this list.
161 *
162 * @return the number of elements in this list
163 */
164 public int size() {
165 return size;
166 }
167
168 /**
169 * Returns {@code true} if this list contains no elements.
170 *
171 * @return {@code true} if this list contains no elements
172 */
173 public boolean isEmpty() {
174 return size == 0;
175 }
176
177 /**
178 * Returns {@code true} if this list contains the specified element.
179 * More formally, returns {@code true} if and only if this list contains
180 * at least one element {@code e} such that
181 * {@code Objects.equals(o, e)}.
182 *
183 * @param o element whose presence in this list is to be tested
184 * @return {@code true} if this list contains the specified element
185 */
186 public boolean contains(PrimitiveInt o) {
187 return indexOf(o) >= 0;
188 }
189
190 /**
191 * Returns the index of the first occurrence of the specified element
192 * in this list, or -1 if this list does not contain the element.
193 * More formally, returns the lowest index {@code i} such that
194 * {@code Objects.equals(o, get(i))},
195 * or -1 if there is no such index.
196 */
197 public int indexOf(PrimitiveInt o) {
198 return indexOfRange(o, 0, size);
199 }
200
201 int indexOfRange(PrimitiveInt o, int start, int end) {
202 PrimitiveInt[] es = elementData;
203 {
204 for (int i = start; i < end; i++) {
205 if (o == es[i]) {
206 return i;
207 }
208 }
209 }
210 return -1;
211 }
212
213 /**
214 * Returns the index of the last occurrence of the specified element
215 * in this list, or -1 if this list does not contain the element.
216 * More formally, returns the highest index {@code i} such that
217 * {@code Objects.equals(o, get(i))},
218 * or -1 if there is no such index.
219 */
220 public int lastIndexOf(PrimitiveInt o) {
221 return lastIndexOfRange(o, 0, size);
222 }
223
224 int lastIndexOfRange(PrimitiveInt o, int start, int end) {
225 PrimitiveInt[] es = elementData;
226 {
227 for (int i = end - 1; i >= start; i--) {
228 if (o == es[i]) {
229 return i;
230 }
231 }
232 }
233 return -1;
234 }
235
236 /**
237 * Returns an array containing all of the elements in this list
238 * in proper sequence (from first to last element).
239 *
240 * <p>The returned array will be "safe" in that no references to it are
241 * maintained by this list. (In other words, this method must allocate
242 * a new array). The caller is thus free to modify the returned array.
243 *
244 * <p>This method acts as bridge between array-based and collection-based
245 * APIs.
246 *
247 * @return an array containing all of the elements in this list in
248 * proper sequence
249 */
250 public PrimitiveInt[] toArray() {
251 return (PrimitiveInt[])Arrays.copyOf(elementData, size);
252 }
253
254 /**
255 * Returns an array containing all of the elements in this list in proper
256 * sequence (from first to last element); the runtime type of the returned
257 * array is that of the specified array. If the list fits in the
258 * specified array, it is returned therein. Otherwise, a new array is
259 * allocated with the runtime type of the specified array and the size of
260 * this list.
261 *
262 * <p>If the list fits in the specified array with room to spare
263 * (i.e., the array has more elements than the list), the element in
264 * the array immediately following the end of the collection is set to
265 * {@code null}. (This is useful in determining the length of the
266 * list <i>only</i> if the caller knows that the list does not contain
267 * any null elements.)
268 *
269 * @param a the array into which the elements of the list are to
270 * be stored, if it is big enough; otherwise, a new array of the
271 * same runtime type is allocated for this purpose.
272 * @return an array containing the elements of the list
273 * @throws ArrayStoreException if the runtime type of the specified array
274 * is not a supertype of the runtime type of every element in
275 * this list
276 * @throws NullPointerException if the specified array is null
277 */
278 // @SuppressWarnings("unchecked")
279 // public <T> T[] toArray(T[] a) {
280 // if (a.length < size)
281 // // Make a new array of a's runtime type, but my contents:
282 // return (T[]) Arrays.copyOf(elementData, size, a.getClass());
283 // System.arraycopy(elementData, 0, a, 0, size);
284 // if (a.length > size)
285 // a[size] = null;
286 // return a;
287 // }
288
289 // Positional Access Operations
290
291 @SuppressWarnings("unchecked")
292 PrimitiveInt elementData(int index) {
293 return (PrimitiveInt) elementData[index];
294 }
295
296 @SuppressWarnings("unchecked")
297 static PrimitiveInt elementAt(PrimitiveInt[] es, int index) {
298 return es[index];
299 }
300
301 /**
302 * Returns the element at the specified position in this list.
303 *
304 * @param index index of the element to return
305 * @return the element at the specified position in this list
306 * @throws IndexOutOfBoundsException {@inheritDoc}
307 */
308 public PrimitiveInt get(int index) {
309 Objects.checkIndex(index, size);
310 return elementData(index);
311 }
312
313 /**
314 * Replaces the element at the specified position in this list with
315 * the specified element.
316 *
317 * @param index index of the element to replace
318 * @param element element to be stored at the specified position
319 * @return the element previously at the specified position
320 * @throws IndexOutOfBoundsException {@inheritDoc}
321 */
322 public PrimitiveInt set(int index, PrimitiveInt element) {
323 Objects.checkIndex(index, size);
324 PrimitiveInt oldValue = elementData(index);
325 elementData[index] = element;
326 return oldValue;
327 }
328
329 /**
330 * This helper method split out from add(int) to keep method
331 * bytecode size under 35 (the -XX:MaxInlineSize default value),
332 * which helps when add(int) is called in a C1-compiled loop.
333 */
334 private void add(PrimitiveInt e, PrimitiveInt[] elementData, int s) {
335 if (s == elementData.length)
336 elementData = grow();
337 elementData[s] = e;
338 size = s + 1;
339 }
340
341 /**
342 * Appends the specified element to the end of this list.
343 *
344 * @param e element to be appended to this list
345 * @return {@code true} (as specified by {@link Collection#add})
346 */
347 public boolean add(PrimitiveInt e) {
348 modCount++;
349 add(e, elementData, size);
350 return true;
351 }
352
353 /**
354 * Inserts the specified element at the specified position in this
355 * list. Shifts the element currently at that position (if any) and
356 * any subsequent elements to the right (adds one to their indices).
357 *
358 * @param index index at which the specified element is to be inserted
359 * @param element element to be inserted
360 * @throws IndexOutOfBoundsException {@inheritDoc}
361 */
362 public void add(int index, PrimitiveInt element) {
363 rangeCheckForAdd(index);
364 modCount++;
365 final int s;
366 PrimitiveInt[] elementData;
367 if ((s = size) == (elementData = this.elementData).length)
368 elementData = grow();
369 System.arraycopy(elementData, index,
370 elementData, index + 1,
371 s - index);
372 elementData[index] = element;
373 size = s + 1;
374 }
375
376 /**
377 * Removes the element at the specified position in this list.
378 * Shifts any subsequent elements to the left (subtracts one from their
379 * indices).
380 *
381 * @param index the index of the element to be removed
382 * @return the element that was removed from the list
383 * @throws IndexOutOfBoundsException {@inheritDoc}
384 */
385 public PrimitiveInt remove(int index) {
386 Objects.checkIndex(index, size);
387 final PrimitiveInt[] es = elementData;
388
389 PrimitiveInt oldValue = (PrimitiveInt) es[index];
390 fastRemove(es, index);
391
392 return oldValue;
393 }
394
395 /**
396 * {@inheritDoc}
397 */
398 public boolean equals(Object o) {
399 if (o == this) {
400 return true;
401 }
402
403 if (!(o instanceof ArrayListPrimitiveInt)) {
404 return false;
405 }
406
407 final int expectedModCount = modCount;
408 // ArrayList can be subclassed and given arbitrary behavior, but we can
409 // still deal with the common case where o is ArrayList precisely
410 boolean equal = equalsArrayList((ArrayListPrimitiveInt) o);
411
412 checkForComodification(expectedModCount);
413 return equal;
414 }
415
416 private boolean equalsArrayList(ArrayListPrimitiveInt other) {
417 final int otherModCount = other.modCount;
418 final int s = size;
419 boolean equal;
420 if (equal = (s == other.size)) {
421 final PrimitiveInt[] otherEs = other.elementData;
422 final PrimitiveInt[] es = elementData;
423 if (s > es.length || s > otherEs.length) {
424 throw new ConcurrentModificationException();
425 }
426 for (int i = 0; i < s; i++) {
427 if (es[i] != otherEs[i]) {
428 equal = false;
429 break;
430 }
431 }
432 }
433 other.checkForComodification(otherModCount);
434 return equal;
435 }
436
437 private void checkForComodification(final int expectedModCount) {
438 if (modCount != expectedModCount) {
439 throw new ConcurrentModificationException();
440 }
441 }
442
443 /**
444 * {@inheritDoc}
445 */
446 public int hashCode() {
447 int expectedModCount = modCount;
448 int hash = hashCodeRange(0, size);
449 checkForComodification(expectedModCount);
450 return hash;
451 }
452
453 int hashCodeRange(int from, int to) {
454 final PrimitiveInt[] es = elementData;
455 if (to > es.length) {
456 throw new ConcurrentModificationException();
457 }
458 int hashCode = 1;
459 for (int i = from; i < to; i++) {
460 PrimitiveInt e = es[i];
461 hashCode = 31 * hashCode + e.hashCode();
462 }
463 return hashCode;
464 }
465
466 /**
467 * Removes the first occurrence of the specified element from this list,
468 * if it is present. If the list does not contain the element, it is
469 * unchanged. More formally, removes the element with the lowest index
470 * {@code i} such that
471 * {@code Objects.equals(o, get(i))}
472 * (if such an element exists). Returns {@code true} if this list
473 * contained the specified element (or equivalently, if this list
474 * changed as a result of the call).
475 *
476 * @param o element to be removed from this list, if present
477 * @return {@code true} if this list contained the specified element
478 */
479 public boolean removeC(PrimitiveInt o) {
480 final PrimitiveInt[] es = elementData;
481 final int size = this.size;
482 int i = 0;
483 found:
484 {
485 // if (o == null) {
486 // for (; i < size; i++)
487 // if (es[i] == null)
488 // break found;
489 // } else
490 {
491 for (; i < size; i++)
492 if (o == es[i])
493 break found;
494 }
495 return false;
496 }
497 fastRemove(es, i);
498 return true;
499 }
500
501 /**
502 * Private remove method that skips bounds checking and does not
503 * return the value removed.
504 */
505 private void fastRemove(PrimitiveInt[] es, int i) {
506 modCount++;
507 final int newSize;
508 if ((newSize = size - 1) > i)
509 System.arraycopy(es, i + 1, es, i, newSize - i);
510 es[size = newSize] = new PrimitiveInt();
511 }
512
513 /**
514 * Removes all of the elements from this list. The list will
515 * be empty after this call returns.
516 */
517 public void clear() {
518 modCount++;
519 final PrimitiveInt[] es = elementData;
520 for (int to = size, i = size = 0; i < to; i++)
521 es[i] = new PrimitiveInt();
522 }
523
524 /**
525 * Removes from this list all of the elements whose index is between
526 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
527 * Shifts any succeeding elements to the left (reduces their index).
528 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
529 * (If {@code toIndex==fromIndex}, this operation has no effect.)
530 *
531 * @throws IndexOutOfBoundsException if {@code fromIndex} or
532 * {@code toIndex} is out of range
533 * ({@code fromIndex < 0 ||
534 * toIndex > size() ||
535 * toIndex < fromIndex})
536 */
537 protected void removeRange(int fromIndex, int toIndex) {
538 if (fromIndex > toIndex) {
539 throw new IndexOutOfBoundsException(
540 outOfBoundsMsg(fromIndex, toIndex));
541 }
542 modCount++;
543 shiftTailOverGap(elementData, fromIndex, toIndex);
544 }
545
546 /** Erases the gap from lo to hi, by sliding down following elements. */
547 private void shiftTailOverGap(PrimitiveInt[] es, int lo, int hi) {
548 System.arraycopy(es, hi, es, lo, size - hi);
549 for (int to = size, i = (size -= hi - lo); i < to; i++)
550 es[i] = new PrimitiveInt();
551 }
552
553 /**
554 * A version of rangeCheck used by add and addAll.
555 */
556 private void rangeCheckForAdd(int index) {
557 if (index > size || index < 0)
558 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
559 }
560
561 /**
562 * Constructs an IndexOutOfBoundsException detail message.
563 * Of the many possible refactorings of the error handling code,
564 * this "outlining" performs best with both server and client VMs.
565 */
566 private String outOfBoundsMsg(int index) {
567 return "Index: "+index+", Size: "+size;
568 }
569
570 /**
571 * A version used in checking (fromIndex > toIndex) condition
572 */
573 private static String outOfBoundsMsg(int fromIndex, int toIndex) {
574 return "From Index: " + fromIndex + " > To Index: " + toIndex;
575 }
576
577 /**
578 * Returns an iterator over the elements in this list in proper sequence.
579 *
580 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
581 *
582 * @return an iterator over the elements in this list in proper sequence
583 */
584 public PrimitiveIntItr iterator() {
585 return new PrimitiveIntItr();
586 }
587
588 /**
589 * An optimized version of AbstractList.Itr
590 */
591 private class PrimitiveIntItr {
592 int cursor; // index of next element to return
593 int lastRet = -1; // index of last element returned; -1 if no such
594 int expectedModCount = modCount;
595
596 // prevent creating a synthetic constructor
597 PrimitiveIntItr() {}
598
599 public boolean hasNext() {
600 return cursor != size;
601 }
602
603 @SuppressWarnings("unchecked")
604 public PrimitiveInt next() {
605 checkForComodification();
606 int i = cursor;
607 if (i >= size)
608 throw new NoSuchElementException();
609 PrimitiveInt[] elementData = ArrayListPrimitiveInt.this.elementData;
610 if (i >= elementData.length)
611 throw new ConcurrentModificationException();
612 cursor = i + 1;
613 return (PrimitiveInt) elementData[lastRet = i];
614 }
615
616 public void remove() {
617 if (lastRet < 0)
618 throw new IllegalStateException();
619 checkForComodification();
620
621 try {
622 ArrayListPrimitiveInt.this.remove(lastRet);
623 cursor = lastRet;
624 lastRet = -1;
625 expectedModCount = modCount;
626 } catch (IndexOutOfBoundsException ex) {
627 throw new ConcurrentModificationException();
628 }
629 }
630
631 public void forEachRemaining(Consumer<? super PrimitiveInt> action) {
632 Objects.requireNonNull(action);
633 final int size = ArrayListPrimitiveInt.this.size;
634 int i = cursor;
635 if (i < size) {
636 final PrimitiveInt[] es = elementData;
637 if (i >= es.length)
638 throw new ConcurrentModificationException();
639 for (; i < size && modCount == expectedModCount; i++)
640 action.accept(elementAt(es, i));
641 // update once at end to reduce heap write traffic
642 cursor = i;
643 lastRet = i - 1;
644 checkForComodification();
645 }
646 }
647
648 final void checkForComodification() {
649 if (modCount != expectedModCount)
650 throw new ConcurrentModificationException();
651 }
652 }
653
654 static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
655
656 static int newLength(int oldLength, int minGrowth, int prefGrowth) {
657 // assert oldLength >= 0
658 // assert minGrowth > 0
659
660 int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
661 if (newLength - MAX_ARRAY_LENGTH <= 0) {
662 return newLength;
663 }
664 return hugeLength(oldLength, minGrowth);
665 }
666
667 private static int hugeLength(int oldLength, int minGrowth) {
668 int minLength = oldLength + minGrowth;
669 if (minLength < 0) { // overflow
670 throw new OutOfMemoryError("Required array length too large");
671 }
672 if (minLength <= MAX_ARRAY_LENGTH) {
673 return MAX_ARRAY_LENGTH;
674 }
675 return Integer.MAX_VALUE;
676 }
677
678 }