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 public final class GrowingArrayUtils {
33 
34     /**
35      * Appends an element to the end of the array, growing the array if there is no more room.
36      * @param array The array to which to append the element. This must NOT be null.
37      * @param currentSize The number of elements in the array. Must be less than or equal to
38      *                    array.length.
39      * @param element The element to append.
40      * @return the array to which the element was appended. This may be different than the given
41      *         array.
42      */
43     @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.R, trackingBug = 170729553)
append(T[] array, int currentSize, T element)44     public static <T> T[] append(T[] array, int currentSize, T element) {
45         assert currentSize <= array.length;
46 
47         if (currentSize + 1 > array.length) {
48             @SuppressWarnings("unchecked")
49             T[] newArray = ArrayUtils.newUnpaddedArray(
50                     (Class<T>) array.getClass().getComponentType(), growSize(currentSize));
51             System.arraycopy(array, 0, newArray, 0, currentSize);
52             array = newArray;
53         }
54         array[currentSize] = element;
55         return array;
56     }
57 
58     /**
59      * Primitive int version of {@link #append(Object[], int, Object)}.
60      */
61     @UnsupportedAppUsage(maxTargetSdk = Build.VERSION_CODES.R, trackingBug = 170729553)
append(int[] array, int currentSize, int element)62     public static int[] append(int[] array, int currentSize, int element) {
63         assert currentSize <= array.length;
64 
65         if (currentSize + 1 > array.length) {
66             int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
67             System.arraycopy(array, 0, newArray, 0, currentSize);
68             array = newArray;
69         }
70         array[currentSize] = element;
71         return array;
72     }
73 
74     /**
75      * Primitive long version of {@link #append(Object[], int, Object)}.
76      */
append(long[] array, int currentSize, long element)77     public static long[] append(long[] array, int currentSize, long element) {
78         assert currentSize <= array.length;
79 
80         if (currentSize + 1 > array.length) {
81             long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
82             System.arraycopy(array, 0, newArray, 0, currentSize);
83             array = newArray;
84         }
85         array[currentSize] = element;
86         return array;
87     }
88 
89     /**
90      * Primitive boolean version of {@link #append(Object[], int, Object)}.
91      */
append(boolean[] array, int currentSize, boolean element)92     public static boolean[] append(boolean[] array, int currentSize, boolean element) {
93         assert currentSize <= array.length;
94 
95         if (currentSize + 1 > array.length) {
96             boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
97             System.arraycopy(array, 0, newArray, 0, currentSize);
98             array = newArray;
99         }
100         array[currentSize] = element;
101         return array;
102     }
103 
104     /**
105      * Primitive float version of {@link #append(Object[], int, Object)}.
106      */
append(float[] array, int currentSize, float element)107     public static float[] append(float[] array, int currentSize, float element) {
108         assert currentSize <= array.length;
109 
110         if (currentSize + 1 > array.length) {
111             float[] newArray = ArrayUtils.newUnpaddedFloatArray(growSize(currentSize));
112             System.arraycopy(array, 0, newArray, 0, currentSize);
113             array = newArray;
114         }
115         array[currentSize] = element;
116         return array;
117     }
118 
119     /**
120      * Inserts an element into the array at the specified index, growing the array if there is no
121      * more room.
122      *
123      * @param array The array to which to append the element. Must NOT be null.
124      * @param currentSize The number of elements in the array. Must be less than or equal to
125      *                    array.length.
126      * @param element The element to insert.
127      * @return the array to which the element was appended. This may be different than the given
128      *         array.
129      */
insert(T[] array, int currentSize, int index, T element)130     public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
131         assert currentSize <= array.length;
132 
133         if (currentSize + 1 <= array.length) {
134             System.arraycopy(array, index, array, index + 1, currentSize - index);
135             array[index] = element;
136             return array;
137         }
138 
139         @SuppressWarnings("unchecked")
140         T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
141                 growSize(currentSize));
142         System.arraycopy(array, 0, newArray, 0, index);
143         newArray[index] = element;
144         System.arraycopy(array, index, newArray, index + 1, array.length - index);
145         return newArray;
146     }
147 
148     /**
149      * Primitive int version of {@link #insert(Object[], int, int, Object)}.
150      */
insert(int[] array, int currentSize, int index, int element)151     public static int[] insert(int[] array, int currentSize, int index, int element) {
152         assert currentSize <= array.length;
153 
154         if (currentSize + 1 <= array.length) {
155             System.arraycopy(array, index, array, index + 1, currentSize - index);
156             array[index] = element;
157             return array;
158         }
159 
160         int[] newArray = ArrayUtils.newUnpaddedIntArray(growSize(currentSize));
161         System.arraycopy(array, 0, newArray, 0, index);
162         newArray[index] = element;
163         System.arraycopy(array, index, newArray, index + 1, array.length - index);
164         return newArray;
165     }
166 
167     /**
168      * Primitive long version of {@link #insert(Object[], int, int, Object)}.
169      */
insert(long[] array, int currentSize, int index, long element)170     public static long[] insert(long[] array, int currentSize, int index, long element) {
171         assert currentSize <= array.length;
172 
173         if (currentSize + 1 <= array.length) {
174             System.arraycopy(array, index, array, index + 1, currentSize - index);
175             array[index] = element;
176             return array;
177         }
178 
179         long[] newArray = ArrayUtils.newUnpaddedLongArray(growSize(currentSize));
180         System.arraycopy(array, 0, newArray, 0, index);
181         newArray[index] = element;
182         System.arraycopy(array, index, newArray, index + 1, array.length - index);
183         return newArray;
184     }
185 
186     /**
187      * Primitive boolean version of {@link #insert(Object[], int, int, Object)}.
188      */
insert(boolean[] array, int currentSize, int index, boolean element)189     public static boolean[] insert(boolean[] array, int currentSize, int index, boolean element) {
190         assert currentSize <= array.length;
191 
192         if (currentSize + 1 <= array.length) {
193             System.arraycopy(array, index, array, index + 1, currentSize - index);
194             array[index] = element;
195             return array;
196         }
197 
198         boolean[] newArray = ArrayUtils.newUnpaddedBooleanArray(growSize(currentSize));
199         System.arraycopy(array, 0, newArray, 0, index);
200         newArray[index] = element;
201         System.arraycopy(array, index, newArray, index + 1, array.length - index);
202         return newArray;
203     }
204 
205     /**
206      * Given the current size of an array, returns an ideal size to which the array should grow.
207      * This is typically double the given size, but should not be relied upon to do so in the
208      * future.
209      */
growSize(int currentSize)210     public static int growSize(int currentSize) {
211         return currentSize <= 4 ? 8 : currentSize * 2;
212     }
213 
214     // Uninstantiable
GrowingArrayUtils()215     private GrowingArrayUtils() {}
216 }
217