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.NoSuchElementException;
31 import java.util.Objects;
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<int>}.
39 */
40 public class ArrayListInt
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 *new () 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 int[] 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 int[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new int[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 int[] 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 ArrayListInt(int initialCapacity) {
89 if (initialCapacity > 0) {
90 this.elementData = new int[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 ArrayListInt() {
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 : 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 int[] 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 = Arrays.copyOf(elementData, newCapacity);
150 } else {
151 return elementData = new int[Math.max(DEFAULT_CAPACITY, minCapacity)];
152 }
153 }
154
155 private int[] 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(int 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(int o) {
198 return indexOfRange(o, 0, size);
199 }
200
201 int indexOfRange(int o, int start, int end) {
202 int[] es = elementData;
203 for (int i = start; i < end; i++) {
204 if (o == es[i]) {
205 return i;
206 }
207 }
208 return -1;
209 }
210
211 /**
212 * Returns the index of the last occurrence of the specified element
213 * in this list, or -1 if this list does not contain the element.
214 * More formally, returns the highest index {@code i} such that
215 * {@code Objects.equals(o, get(i))},
216 * or -1 if there is no such index.
217 */
218 public int lastIndexOf(int o) {
219 return lastIndexOfRange(o, 0, size);
220 }
221
222 int lastIndexOfRange(int o, int start, int end) {
223 int[] es = elementData;
224 {
225 for (int i = end - 1; i >= start; i--) {
226 if (o == es[i]) {
227 return i;
228 }
229 }
230 }
231 return -1;
232 }
233
234 /**
235 * Returns an array containing all of the elements in this list
236 * in proper sequence (from first to last element).
237 *
238 * <p>The returned array will be "safe" in that no references to it are
239 * maintained by this list. (In other words, this method must allocate
240 * a new array). The caller is thus free to modify the returned array.
241 *
242 * <p>This method acts as bridge between array-based and collection-based
243 * APIs.
244 *
245 * @return an array containing all of the elements in this list in
246 * proper sequence
247 */
248 public int[] toArray() {
249 return Arrays.copyOf(elementData, size);
250 }
251
252 // Positional Access Operations
253
254 @SuppressWarnings("unchecked")
255 int elementData(int index) {
256 return (int) elementData[index];
257 }
258
259 @SuppressWarnings("unchecked")
260 static int elementAt(int[] es, int index) {
261 return es[index];
262 }
263
264 /**
265 * Returns the element at the specified position in this list.
266 *
267 * @param index index of the element to return
268 * @return the element at the specified position in this list
269 * @throws IndexOutOfBoundsException {@inheritDoc}
270 */
271 public int get(int index) {
272 Objects.checkIndex(index, size);
273 return elementData(index);
274 }
275
276 /**
277 * Replaces the element at the specified position in this list with
278 * the specified element.
279 *
280 * @param index index of the element to replace
281 * @param element element to be stored at the specified position
282 * @return the element previously at the specified position
283 * @throws IndexOutOfBoundsException {@inheritDoc}
284 */
285 public int set(int index, int element) {
286 Objects.checkIndex(index, size);
287 int oldValue = elementData(index);
288 elementData[index] = element;
289 return oldValue;
290 }
291
292 /**
293 * This helper method split out from add(int) to keep method
294 * bytecode size under 35 (the -XX:MaxInlineSize default value),
295 * which helps when add(int) is called in a C1-compiled loop.
296 */
297 private void add(int e, int[] elementData, int s) {
298 if (s == elementData.length)
299 elementData = grow();
300 elementData[s] = e;
301 size = s + 1;
302 }
303
304 /**
305 * Appends the specified element to the end of this list.
306 *
307 * @param e element to be appended to this list
308 * @return {@code true} (as specified by {@link Collection#add})
309 */
310 public boolean add(int e) {
311 modCount++;
312 add(e, elementData, size);
313 return true;
314 }
315
316 /**
317 * Inserts the specified element at the specified position in this
318 * list. Shifts the element currently at that position (if any) and
319 * any subsequent elements to the right (adds one to their indices).
320 *
321 * @param index index at which the specified element is to be inserted
322 * @param element element to be inserted
323 * @throws IndexOutOfBoundsException {@inheritDoc}
324 */
325 public void add(int index, int element) {
326 rangeCheckForAdd(index);
327 modCount++;
328 final int s;
329 int[] elementData;
330 if ((s = size) == (elementData = this.elementData).length)
331 elementData = grow();
332 System.arraycopy(elementData, index,
333 elementData, index + 1,
334 s - index);
335 elementData[index] = element;
336 size = s + 1;
337 }
338
339 /**
340 * Removes the element at the specified position in this list.
341 * Shifts any subsequent elements to the left (subtracts one from their
342 * indices).
343 *
344 * @param index the index of the element to be removed
345 * @return the element that was removed from the list
346 * @throws IndexOutOfBoundsException {@inheritDoc}
347 */
348 public int remove(int index) {
349 Objects.checkIndex(index, size);
350 final int[] es = elementData;
351
352 int oldValue = (int) es[index];
353 fastRemove(es, index);
354
355 return oldValue;
356 }
357
358 /**
359 * {@inheritDoc}
360 */
361 public boolean equals(Object o) {
362 if (o == this) {
363 return true;
364 }
365
366 if (!(o instanceof ArrayListInt)) {
367 return false;
368 }
369
370 final int expectedModCount = modCount;
371 // ArrayList can be subclassed and given arbitrary behavior, but we can
372 // still deal with the common case where o is ArrayList precisely
373 boolean equal = equalsArrayList((ArrayListInt) o);
374
375 checkForComodification(expectedModCount);
376 return equal;
377 }
378
379 private boolean equalsArrayList(ArrayListInt other) {
380 final int otherModCount = other.modCount;
381 final int s = size;
382 boolean equal;
383 if (equal = (s == other.size)) {
384 final int[] otherEs = other.elementData;
385 final int[] es = elementData;
386 if (s > es.length || s > otherEs.length) {
387 throw new ConcurrentModificationException();
388 }
389 for (int i = 0; i < s; i++) {
390 if (es[i] != otherEs[i]) {
391 equal = false;
392 break;
393 }
394 }
395 }
396 other.checkForComodification(otherModCount);
397 return equal;
398 }
399
400 private void checkForComodification(final int expectedModCount) {
401 if (modCount != expectedModCount) {
402 throw new ConcurrentModificationException();
403 }
404 }
405
406 /**
407 * {@inheritDoc}
408 */
409 public int hashCode() {
410 int expectedModCount = modCount;
411 int hash = hashCodeRange(0, size);
412 checkForComodification(expectedModCount);
413 return hash;
414 }
415
416 int hashCodeRange(int from, int to) {
417 final int[] es = elementData;
418 if (to > es.length) {
419 throw new ConcurrentModificationException();
420 }
421 int hashCode = 1;
422 for (int i = from; i < to; i++) {
423 int e = es[i];
424 hashCode = 31 * hashCode + e;
425 }
426 return hashCode;
427 }
428
429 /**
430 * Removes the first occurrence of the specified element from this list,
431 * if it is present. If the list does not contain the element, it is
432 * unchanged. More formally, removes the element with the lowest index
433 * {@code i} such that
434 * {@code Objects.equals(o, get(i))}
435 * (if such an element exists). Returns {@code true} if this list
436 * contained the specified element (or equivalently, if this list
437 * changed as a result of the call).
438 *
439 * @param o element to be removed from this list, if present
440 * @return {@code true} if this list contained the specified element
441 */
442 public boolean removeC(int o) {
443 final int[] es = elementData;
444 final int size = this.size;
445 int i = 0;
446 found:
447 {
448 // if (o == null) {
449 // for (; i < size; i++)
450 // if (es[i] == null)
451 // break found;
452 // } else
453 {
454 for (; i < size; i++)
455 if (o == es[i])
456 break found;
457 }
458 return false;
459 }
460 fastRemove(es, i);
461 return true;
462 }
463
464 /**
465 * Private remove method that skips bounds checking and does not
466 * return the value removed.
467 */
468 private void fastRemove(int[] es, int i) {
469 modCount++;
470 final int newSize;
471 if ((newSize = size - 1) > i)
472 System.arraycopy(es, i + 1, es, i, newSize - i);
473 es[size = newSize] = 0;
474 }
475
476 /**
477 * Removes all of the elements from this list. The list will
478 * be empty after this call returns.
479 */
480 public void clear() {
481 modCount++;
482 final int[] es = elementData;
483 for (int to = size, i = size = 0; i < to; i++)
484 es[i] = 0;
485 }
486
487 /**
488 * Removes from this list all of the elements whose index is between
489 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
490 * Shifts any succeeding elements to the left (reduces their index).
491 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
492 * (If {@code toIndex==fromIndex}, this operation has no effect.)
493 *
494 * @throws IndexOutOfBoundsException if {@code fromIndex} or
495 * {@code toIndex} is out of range
496 * ({@code fromIndex < 0 ||
497 * toIndex > size() ||
498 * toIndex < fromIndex})
499 */
500 protected void removeRange(int fromIndex, int toIndex) {
501 if (fromIndex > toIndex) {
502 throw new IndexOutOfBoundsException(
503 outOfBoundsMsg(fromIndex, toIndex));
504 }
505 modCount++;
506 shiftTailOverGap(elementData, fromIndex, toIndex);
507 }
508
509 /** Erases the gap from lo to hi, by sliding down following elements. */
510 private void shiftTailOverGap(int[] es, int lo, int hi) {
511 System.arraycopy(es, hi, es, lo, size - hi);
512 for (int to = size, i = (size -= hi - lo); i < to; i++)
513 es[i] = 0;
514 }
515
516 /**
517 * A version of rangeCheck used by add and addAll.
518 */
519 private void rangeCheckForAdd(int index) {
520 if (index > size || index < 0)
521 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
522 }
523
524 /**
525 * Constructs an IndexOutOfBoundsException detail message.
526 * Of the many possible refactorings of the error handling code,
527 * this "outlining" performs best with both server and client VMs.
528 */
529 private String outOfBoundsMsg(int index) {
530 return "Index: "+index+", Size: "+size;
531 }
532
533 /**
534 * A version used in checking (fromIndex > toIndex) condition
535 */
536 private static String outOfBoundsMsg(int fromIndex, int toIndex) {
537 return "From Index: " + fromIndex + " > To Index: " + toIndex;
538 }
539
540 /**
541 * Returns an iterator over the elements in this list in proper sequence.
542 *
543 * <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
544 *
545 * @return an iterator over the elements in this list in proper sequence
546 */
547 public IntItr iterator() {
548 return new IntItr();
549 }
550
551 /**
552 * An optimized version of AbstractList.Itr
553 */
554 private class IntItr {
555 int cursor; // index of next element to return
556 int lastRet = -1; // index of last element returned; -1 if no such
557 int expectedModCount = modCount;
558
559 // prevent creating a synthetic constructor
560 IntItr() {}
561
562 public boolean hasNext() {
563 return cursor != size;
564 }
565
566 @SuppressWarnings("unchecked")
567 public int next() {
568 checkForComodification();
569 int i = cursor;
570 if (i >= size)
571 throw new NoSuchElementException();
572 int[] elementData = ArrayListInt.this.elementData;
573 if (i >= elementData.length)
574 throw new ConcurrentModificationException();
575 cursor = i + 1;
576 return (int) elementData[lastRet = i];
577 }
578
579 public void remove() {
580 if (lastRet < 0)
581 throw new IllegalStateException();
582 checkForComodification();
583
584 try {
585 ArrayListInt.this.remove(lastRet);
586 cursor = lastRet;
587 lastRet = -1;
588 expectedModCount = modCount;
589 } catch (IndexOutOfBoundsException ex) {
590 throw new ConcurrentModificationException();
591 }
592 }
593
594 public void forEachRemaining(IntConsumer action) {
595 Objects.requireNonNull(action);
596 final int size = ArrayListInt.this.size;
597 int i = cursor;
598 if (i < size) {
599 final int[] es = elementData;
600 if (i >= es.length)
601 throw new ConcurrentModificationException();
602 for (; i < size && modCount == expectedModCount; i++)
603 action.accept(elementAt(es, i));
604 // update once at end to reduce heap write traffic
605 cursor = i;
606 lastRet = i - 1;
607 checkForComodification();
608 }
609 }
610
611 final void checkForComodification() {
612 if (modCount != expectedModCount)
613 throw new ConcurrentModificationException();
614 }
615 }
616
617 static final int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
618
619 static int newLength(int oldLength, int minGrowth, int prefGrowth) {
620 // assert oldLength >= 0
621 // assert minGrowth > 0
622
623 int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
624 if (newLength - MAX_ARRAY_LENGTH <= 0) {
625 return newLength;
626 }
627 return hugeLength(oldLength, minGrowth);
628 }
629
630 private static int hugeLength(int oldLength, int minGrowth) {
631 int minLength = oldLength + minGrowth;
632 if (minLength < 0) { // overflow
633 throw new OutOfMemoryError("Required array length too large");
634 }
635 if (minLength <= MAX_ARRAY_LENGTH) {
636 return MAX_ARRAY_LENGTH;
637 }
638 return Integer.MAX_VALUE;
639 }
640 }