1 // Protocol Buffers - Google's data interchange format 2 // Copyright 2008 Google Inc. All rights reserved. 3 // 4 // Use of this source code is governed by a BSD-style 5 // license that can be found in the LICENSE file or at 6 // https://developers.google.com/open-source/licenses/bsd 7 8 package com.google.protobuf; 9 10 import static java.lang.Math.max; 11 12 import com.google.protobuf.Internal.ProtobufList; 13 import java.util.Arrays; 14 import java.util.RandomAccess; 15 16 /** Implements {@link ProtobufList} for non-primitive and {@link String} types. */ 17 final class ProtobufArrayList<E> extends AbstractProtobufList<E> implements RandomAccess { 18 19 private static final Object[] EMPTY_ARRAY = new Object[0]; 20 21 private static final ProtobufArrayList<Object> EMPTY_LIST = 22 new ProtobufArrayList<>(EMPTY_ARRAY, 0, false); 23 24 @SuppressWarnings("unchecked") // Guaranteed safe by runtime. emptyList()25 public static <E> ProtobufArrayList<E> emptyList() { 26 return (ProtobufArrayList<E>) EMPTY_LIST; 27 } 28 29 private E[] array; 30 private int size; 31 32 @SuppressWarnings("unchecked") ProtobufArrayList()33 ProtobufArrayList() { 34 this((E[]) EMPTY_ARRAY, 0, true); 35 } 36 ProtobufArrayList(E[] array, int size, boolean isMutable)37 private ProtobufArrayList(E[] array, int size, boolean isMutable) { 38 super(isMutable); 39 this.array = array; 40 this.size = size; 41 } 42 43 @SuppressWarnings("unchecked") // Casting an empty Object[] to a generic array is safe. 44 @Override mutableCopyWithCapacity(int capacity)45 public ProtobufArrayList<E> mutableCopyWithCapacity(int capacity) { 46 if (capacity < size) { 47 throw new IllegalArgumentException(); 48 } 49 50 E[] newArray = capacity == 0 ? (E[]) EMPTY_ARRAY : Arrays.copyOf(array, capacity); 51 52 return new ProtobufArrayList<E>(newArray, size, true); 53 } 54 55 @Override add(E element)56 public boolean add(E element) { 57 ensureIsMutable(); 58 59 if (size == array.length) { 60 int length = growSize(array.length); 61 E[] newArray = Arrays.copyOf(array, length); 62 63 array = newArray; 64 } 65 66 array[size++] = element; 67 modCount++; 68 69 return true; 70 } 71 growSize(int previousSize)72 private static int growSize(int previousSize) { 73 // Resize to 1.5x the size, rounding up to DEFAULT_CAPACITY. 74 return max(((previousSize * 3) / 2) + 1, DEFAULT_CAPACITY); 75 } 76 77 @Override add(int index, E element)78 public void add(int index, E element) { 79 ensureIsMutable(); 80 81 if (index < 0 || index > size) { 82 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)); 83 } 84 85 if (size < array.length) { 86 // Shift everything over to make room 87 System.arraycopy(array, index, array, index + 1, size - index); 88 } else { 89 int length = growSize(array.length); 90 E[] newArray = createArray(length); 91 92 // Copy the first part directly 93 System.arraycopy(array, 0, newArray, 0, index); 94 95 // Copy the rest shifted over by one to make room 96 System.arraycopy(array, index, newArray, index + 1, size - index); 97 array = newArray; 98 } 99 100 array[index] = element; 101 size++; 102 modCount++; 103 } 104 105 @Override get(int index)106 public E get(int index) { 107 ensureIndexInRange(index); 108 return array[index]; 109 } 110 111 @Override remove(int index)112 public E remove(int index) { 113 ensureIsMutable(); 114 ensureIndexInRange(index); 115 116 E value = array[index]; 117 if (index < size - 1) { 118 System.arraycopy(array, index + 1, array, index, size - index - 1); 119 } 120 121 size--; 122 modCount++; 123 return value; 124 } 125 126 @Override set(int index, E element)127 public E set(int index, E element) { 128 ensureIsMutable(); 129 ensureIndexInRange(index); 130 131 E toReturn = array[index]; 132 array[index] = element; 133 134 modCount++; 135 return toReturn; 136 } 137 138 @Override size()139 public int size() { 140 return size; 141 } 142 143 /** Ensures the backing array can fit at least minCapacity elements. */ 144 @SuppressWarnings("unchecked") // Casting an Object[] with no values inside to E[] is safe. ensureCapacity(int minCapacity)145 void ensureCapacity(int minCapacity) { 146 if (minCapacity <= array.length) { 147 return; 148 } 149 if (array.length == 0) { 150 array = (E[]) new Object[max(minCapacity, DEFAULT_CAPACITY)]; 151 return; 152 } 153 // To avoid quadratic copying when calling .addAllFoo(List) in a loop, we must not size to 154 // exactly the requested capacity, but must exponentially grow instead. This is similar 155 // behaviour to ArrayList. 156 int n = array.length; 157 while (n < minCapacity) { 158 n = growSize(n); 159 } 160 array = Arrays.copyOf(array, n); 161 } 162 163 @SuppressWarnings("unchecked") createArray(int capacity)164 private static <E> E[] createArray(int capacity) { 165 return (E[]) new Object[capacity]; 166 } 167 ensureIndexInRange(int index)168 private void ensureIndexInRange(int index) { 169 if (index < 0 || index >= size) { 170 throw new IndexOutOfBoundsException(makeOutOfBoundsExceptionMessage(index)); 171 } 172 } 173 makeOutOfBoundsExceptionMessage(int index)174 private String makeOutOfBoundsExceptionMessage(int index) { 175 return "Index:" + index + ", Size:" + size; 176 } 177 } 178