1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.internal.util;
18 
19 import android.compat.annotation.UnsupportedAppUsage;
20 import android.os.Build;
21 
22 /**
23  * A helper class that aims to provide comparable growth performance to ArrayList, but on primitive
24  * arrays. Common array operations are implemented for efficient use in dynamic containers.
25  *
26  * All methods in this class assume that the length of an array is equivalent to its capacity and
27  * NOT the number of elements in the array. The current size of the array is always passed in as a
28  * parameter.
29  *
30  * @hide
31  */
32 @android.ravenwood.annotation.RavenwoodKeepWholeClass
33 public final class GrowingArrayUtils {
34 
35     /**
36      * Appends an element to the end of the array, growing the array if there is no more room.
37      * @param array The array to which to append the element. This must NOT be null.
38      * @param currentSize The number of elements in the array. Must be less than or equal to
39      *                    array.length.
40      * @param element The element to append.
41      * @return the array to which the element was appended. This may be different than the given
42      *         array.
43      */
44     @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.R, trackingBug = 170729553)
append(T[] array, int currentSize, T element)45     public static <T> T[] append(T[] array, int currentSize, T element) {
46         assert currentSize <= array.length;
47 
48         if (currentSize + 1 > array.length) {
49             @SuppressWarnings("unchecked")
50             T[] newArray = ArrayUtils.newUnpaddedArray(
51                     (Class<T>) array.getClass().getComponentType(), growSize(currentSize));
52             System.arraycopy(array, 0, newArray, 0, currentSize);
53             array = newArray;
54         }
55         array[currentSize] = element;
56         return array;
57     }
58 
59     /**
60      * Primitive int version of {@link #append(Object[], int, Object)}.
61      */
62     @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.R, trackingBug = 170729553)
append(int[] array, int currentSize, int element)63     public static int[] append(int[] array, int currentSize, int element) {
64         assert currentSize <= array.length;
65 
66         if (currentSize + 1 > array.length) {
67             int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
68             System.arraycopy(array, 0, newArray, 0, currentSize);
69             array = newArray;
70         }
71         array[currentSize] = element;
72         return array;
73     }
74 
75     /**
76      * Primitive long version of {@link #append(Object[], int, Object)}.
77      */
append(long[] array, int currentSize, long element)78     public static long[] append(long[] array, int currentSize, long element) {
79         assert currentSize <= array.length;
80 
81         if (currentSize + 1 > array.length) {
82             long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
83             System.arraycopy(array, 0, newArray, 0, currentSize);
84             array = newArray;
85         }
86         array[currentSize] = element;
87         return array;
88     }
89 
90     /**
91      * Primitive boolean version of {@link #append(Object[], int, Object)}.
92      */
append(boolean[] array, int currentSize, boolean element)93     public static boolean[] append(boolean[] array, int currentSize, boolean element) {
94         assert currentSize <= array.length;
95 
96         if (currentSize + 1 > array.length) {
97             boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
98             System.arraycopy(array, 0, newArray, 0, currentSize);
99             array = newArray;
100         }
101         array[currentSize] = element;
102         return array;
103     }
104 
105     /**
106      * Primitive float version of {@link #append(Object[], int, Object)}.
107      */
append(float[] array, int currentSize, float element)108     public static float[] append(float[] array, int currentSize, float element) {
109         assert currentSize <= array.length;
110 
111         if (currentSize + 1 > array.length) {
112             float[] newArray = ArrayUtils.newUnpaddedFloatArray(growSize(currentSize));
113             System.arraycopy(array, 0, newArray, 0, currentSize);
114             array = newArray;
115         }
116         array[currentSize] = element;
117         return array;
118     }
119 
120     /**
121      * Inserts an element into the array at the specified index, growing the array if there is no
122      * more room.
123      *
124      * @param array The array to which to append the element. Must NOT be null.
125      * @param currentSize The number of elements in the array. Must be less than or equal to
126      *                    array.length.
127      * @param element The element to insert.
128      * @return the array to which the element was appended. This may be different than the given
129      *         array.
130      */
insert(T[] array, int currentSize, int index, T element)131     public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
132         assert currentSize <= array.length;
133 
134         if (currentSize + 1 <= array.length) {
135             System.arraycopy(array, index, array, index + 1, currentSize - index);
136             array[index] = element;
137             return array;
138         }
139 
140         @SuppressWarnings("unchecked")
141         T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
142                 growSize(currentSize));
143         System.arraycopy(array, 0, newArray, 0, index);
144         newArray[index] = element;
145         System.arraycopy(array, index, newArray, index + 1, array.length - index);
146         return newArray;
147     }
148 
149     /**
150      * Primitive int version of {@link #insert(Object[], int, int, Object)}.
151      */
insert(int[] array, int currentSize, int index, int element)152     public static int[] insert(int[] array, int currentSize, int index, int element) {
153         assert currentSize <= array.length;
154 
155         if (currentSize + 1 <= array.length) {
156             System.arraycopy(array, index, array, index + 1, currentSize - index);
157             array[index] = element;
158             return array;
159         }
160 
161         int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
162         System.arraycopy(array, 0, newArray, 0, index);
163         newArray[index] = element;
164         System.arraycopy(array, index, newArray, index + 1, array.length - index);
165         return newArray;
166     }
167 
168     /**
169      * Primitive long version of {@link #insert(Object[], int, int, Object)}.
170      */
insert(long[] array, int currentSize, int index, long element)171     public static long[] insert(long[] array, int currentSize, int index, long element) {
172         assert currentSize <= array.length;
173 
174         if (currentSize + 1 <= array.length) {
175             System.arraycopy(array, index, array, index + 1, currentSize - index);
176             array[index] = element;
177             return array;
178         }
179 
180         long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
181         System.arraycopy(array, 0, newArray, 0, index);
182         newArray[index] = element;
183         System.arraycopy(array, index, newArray, index + 1, array.length - index);
184         return newArray;
185     }
186 
187     /**
188      * Primitive boolean version of {@link #insert(Object[], int, int, Object)}.
189      */
insert(boolean[] array, int currentSize, int index, boolean element)190     public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) {
191         assert currentSize <= array.length;
192 
193         if (currentSize + 1 <= array.length) {
194             System.arraycopy(array, index, array, index + 1, currentSize - index);
195             array[index] = element;
196             return array;
197         }
198 
199         boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
200         System.arraycopy(array, 0, newArray, 0, index);
201         newArray[index] = element;
202         System.arraycopy(array, index, newArray, index + 1, array.length - index);
203         return newArray;
204     }
205 
206     /**
207      * Given the current size of an array, returns an ideal size to which the array should grow.
208      * This is typically double the given size, but should not be relied upon to do so in the
209      * future.
210      */
growSize(int currentSize)211     public static int growSize(int currentSize) {
212         return currentSize <= 4 ? 8 : currentSize * 2;
213     }
214 
215     // Uninstantiable
GrowingArrayUtils()216     private GrowingArrayUtils() {}
217 }
218