< prev index next >

src/java.base/share/classes/java/util/ArrayList.java

Print this page
rev 54892 : imported patch 8223593-Refactor-code-for-reallocating-storage
   1 /*
   2  * Copyright (c) 1997, 2018, 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 java.util;
  27 
  28 import java.util.function.Consumer;
  29 import java.util.function.Predicate;
  30 import java.util.function.UnaryOperator;
  31 import jdk.internal.access.SharedSecrets;

  32 
  33 /**
  34  * Resizable-array implementation of the {@code List} interface.  Implements
  35  * all optional list operations, and permits all elements, including
  36  * {@code null}.  In addition to implementing the {@code List} interface,
  37  * this class provides methods to manipulate the size of the array that is
  38  * used internally to store the list.  (This class is roughly equivalent to
  39  * {@code Vector}, except that it is unsynchronized.)
  40  *
  41  * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
  42  * {@code iterator}, and {@code listIterator} operations run in constant
  43  * time.  The {@code add} operation runs in <i>amortized constant time</i>,
  44  * that is, adding n elements requires O(n) time.  All of the other operations
  45  * run in linear time (roughly speaking).  The constant factor is low compared
  46  * to that for the {@code LinkedList} implementation.
  47  *
  48  * <p>Each {@code ArrayList} instance has a <i>capacity</i>.  The capacity is
  49  * the size of the array used to store the elements in the list.  It is always
  50  * at least as large as the list size.  As elements are added to an ArrayList,
  51  * its capacity grows automatically.  The details of the growth policy are not


 202         }
 203     }
 204 
 205     /**
 206      * Increases the capacity of this {@code ArrayList} instance, if
 207      * necessary, to ensure that it can hold at least the number of elements
 208      * specified by the minimum capacity argument.
 209      *
 210      * @param minCapacity the desired minimum capacity
 211      */
 212     public void ensureCapacity(int minCapacity) {
 213         if (minCapacity > elementData.length
 214             && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 215                  && minCapacity <= DEFAULT_CAPACITY)) {
 216             modCount++;
 217             grow(minCapacity);
 218         }
 219     }
 220 
 221     /**
 222      * The maximum size of array to allocate (unless necessary).
 223      * Some VMs reserve some header words in an array.
 224      * Attempts to allocate larger arrays may result in
 225      * OutOfMemoryError: Requested array size exceeds VM limit
 226      */
 227     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 228 
 229     /**
 230      * Increases the capacity to ensure that it can hold at least the
 231      * number of elements specified by the minimum capacity argument.
 232      *
 233      * @param minCapacity the desired minimum capacity
 234      * @throws OutOfMemoryError if minCapacity is less than zero
 235      */
 236     private Object[] grow(int minCapacity) {
 237         return elementData = Arrays.copyOf(elementData,
 238                                            newCapacity(minCapacity));







 239     }
 240 
 241     private Object[] grow() {
 242         return grow(size + 1);
 243     }
 244 
 245     /**
 246      * Returns a capacity at least as large as the given minimum capacity.
 247      * Returns the current capacity increased by 50% if that suffices.
 248      * Will not return a capacity greater than MAX_ARRAY_SIZE unless
 249      * the given minimum capacity is greater than MAX_ARRAY_SIZE.
 250      *
 251      * @param minCapacity the desired minimum capacity
 252      * @throws OutOfMemoryError if minCapacity is less than zero
 253      */
 254     private int newCapacity(int minCapacity) {
 255         // overflow-conscious code
 256         int oldCapacity = elementData.length;
 257         int newCapacity = oldCapacity + (oldCapacity >> 1);
 258         if (newCapacity - minCapacity <= 0) {
 259             if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
 260                 return Math.max(DEFAULT_CAPACITY, minCapacity);
 261             if (minCapacity < 0) // overflow
 262                 throw new OutOfMemoryError();
 263             return minCapacity;
 264         }
 265         return (newCapacity - MAX_ARRAY_SIZE <= 0)
 266             ? newCapacity
 267             : hugeCapacity(minCapacity);
 268     }
 269 
 270     private static int hugeCapacity(int minCapacity) {
 271         if (minCapacity < 0) // overflow
 272             throw new OutOfMemoryError();
 273         return (minCapacity > MAX_ARRAY_SIZE)
 274             ? Integer.MAX_VALUE
 275             : MAX_ARRAY_SIZE;
 276     }
 277 
 278     /**
 279      * Returns the number of elements in this list.
 280      *
 281      * @return the number of elements in this list
 282      */
 283     public int size() {
 284         return size;
 285     }
 286 
 287     /**
 288      * Returns {@code true} if this list contains no elements.
 289      *
 290      * @return {@code true} if this list contains no elements
 291      */
 292     public boolean isEmpty() {
 293         return size == 0;
 294     }
 295 


   1 /*
   2  * Copyright (c) 1997, 2019, 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 java.util;
  27 
  28 import java.util.function.Consumer;
  29 import java.util.function.Predicate;
  30 import java.util.function.UnaryOperator;
  31 import jdk.internal.access.SharedSecrets;
  32 import jdk.internal.util.ArraysSupport;
  33 
  34 /**
  35  * Resizable-array implementation of the {@code List} interface.  Implements
  36  * all optional list operations, and permits all elements, including
  37  * {@code null}.  In addition to implementing the {@code List} interface,
  38  * this class provides methods to manipulate the size of the array that is
  39  * used internally to store the list.  (This class is roughly equivalent to
  40  * {@code Vector}, except that it is unsynchronized.)
  41  *
  42  * <p>The {@code size}, {@code isEmpty}, {@code get}, {@code set},
  43  * {@code iterator}, and {@code listIterator} operations run in constant
  44  * time.  The {@code add} operation runs in <i>amortized constant time</i>,
  45  * that is, adding n elements requires O(n) time.  All of the other operations
  46  * run in linear time (roughly speaking).  The constant factor is low compared
  47  * to that for the {@code LinkedList} implementation.
  48  *
  49  * <p>Each {@code ArrayList} instance has a <i>capacity</i>.  The capacity is
  50  * the size of the array used to store the elements in the list.  It is always
  51  * at least as large as the list size.  As elements are added to an ArrayList,
  52  * its capacity grows automatically.  The details of the growth policy are not


 203         }
 204     }
 205 
 206     /**
 207      * Increases the capacity of this {@code ArrayList} instance, if
 208      * necessary, to ensure that it can hold at least the number of elements
 209      * specified by the minimum capacity argument.
 210      *
 211      * @param minCapacity the desired minimum capacity
 212      */
 213     public void ensureCapacity(int minCapacity) {
 214         if (minCapacity > elementData.length
 215             && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 216                  && minCapacity <= DEFAULT_CAPACITY)) {
 217             modCount++;
 218             grow(minCapacity);
 219         }
 220     }
 221 
 222     /**








 223      * Increases the capacity to ensure that it can hold at least the
 224      * number of elements specified by the minimum capacity argument.
 225      *
 226      * @param minCapacity the desired minimum capacity
 227      * @throws OutOfMemoryError if minCapacity is less than zero
 228      */
 229     private Object[] grow(int minCapacity) {
 230         int oldCapacity = elementData.length;
 231         if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
 232             int newCapacity = ArraysSupport.calcLength(oldCapacity,
 233                     minCapacity - oldCapacity, /* minimum growth */
 234                     oldCapacity >> 1           /* preferred growth */);
 235             return elementData = Arrays.copyOf(elementData, newCapacity);
 236         } else {
 237             return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
 238         }
 239     }
 240 
 241     private Object[] grow() {
 242         return grow(size + 1);

































 243     }
 244 
 245     /**
 246      * Returns the number of elements in this list.
 247      *
 248      * @return the number of elements in this list
 249      */
 250     public int size() {
 251         return size;
 252     }
 253 
 254     /**
 255      * Returns {@code true} if this list contains no elements.
 256      *
 257      * @return {@code true} if this list contains no elements
 258      */
 259     public boolean isEmpty() {
 260         return size == 0;
 261     }
 262 


< prev index next >