BlockList.java

  1. /*
  2.  * Copyright (C) 2011, Google Inc. and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  11. package org.eclipse.jgit.util;

  13. import java.util.AbstractList;
  14. import java.util.Arrays;
  15. import java.util.Iterator;
  16. import java.util.NoSuchElementException;

  18. /**
  19.  * Random access list that allocates entries in blocks.
  20.  * <p>
  21.  * Unlike {@link java.util.ArrayList}, this type does not need to reallocate the
  22.  * internal array in order to expand the capacity of the list. Access to any
  23.  * element is constant time, but requires two array lookups instead of one.
  24.  * <p>
  25.  * To handle common usages, {@link #add(Object)} and {@link #iterator()} use
  26.  * internal code paths to amortize out the second array lookup, making addition
  27.  * and simple iteration closer to one array operation per element processed.
  28.  * <p>
  29.  * Similar to {@code ArrayList}, adding or removing from any position except the
  30.  * end of the list requires O(N) time to copy all elements between the
  31.  * modification point and the end of the list. Applications are strongly
  32.  * encouraged to not use this access pattern with this list implementation.
  33.  *
  34.  * @param <T>
  35.  *            type of list element.
  36.  */
  37. public class BlockList<T> extends AbstractList<T> {
  38.     private static final int BLOCK_BITS = 10;

  40.     static final int BLOCK_SIZE = 1 << BLOCK_BITS;

  42.     private static final int BLOCK_MASK = BLOCK_SIZE - 1;

  44.     T[][] directory;

  46.     int size;

  48.     private int tailDirIdx;

  50.     private int tailBlkIdx;

  52.     private T[] tailBlock;

  54.     /**
  55.      * Initialize an empty list.
  56.      */
  57.     public BlockList() {
  58.         directory = BlockList.<T> newDirectory(256);
  59.         directory[0] = BlockList.<T> newBlock();
  60.         tailBlock = directory[0];
  61.     }

  63.     /**
  64.      * Initialize an empty list with an expected capacity.
  65.      *
  66.      * @param capacity
  67.      *            number of elements expected to be in the list.
  68.      */
  69.     public BlockList(int capacity) {
  70.         int dirSize = toDirectoryIndex(capacity);
  71.         if ((capacity & BLOCK_MASK) != 0 || dirSize == 0)
  72.             dirSize++;
  73.         directory = BlockList.<T> newDirectory(dirSize);
  74.         directory[0] = BlockList.<T> newBlock();
  75.         tailBlock = directory[0];
  76.     }

  78.     /** {@inheritDoc} */
  79.     @Override
  80.     public int size() {
  81.         return size;
  82.     }

  84.     /** {@inheritDoc} */
  85.     @Override
  86.     public void clear() {
  87.         for (T[] block : directory) {
  88.             if (block != null)
  89.                 Arrays.fill(block, null);
  90.         }
  91.         size = 0;
  92.         tailDirIdx = 0;
  93.         tailBlkIdx = 0;
  94.         tailBlock = directory[0];
  95.     }

  97.     /** {@inheritDoc} */
  98.     @Override
  99.     public T get(int index) {
  100.         if (index < 0 || size <= index)
  101.             throw new IndexOutOfBoundsException(String.valueOf(index));
  102.         return directory[toDirectoryIndex(index)][toBlockIndex(index)];
  103.     }

  105.     /** {@inheritDoc} */
  106.     @Override
  107.     public T set(int index, T element) {
  108.         if (index < 0 || size <= index)
  109.             throw new IndexOutOfBoundsException(String.valueOf(index));
  110.         T[] blockRef = directory[toDirectoryIndex(index)];
  111.         int blockIdx = toBlockIndex(index);
  112.         T old = blockRef[blockIdx];
  113.         blockRef[blockIdx] = element;
  114.         return old;
  115.     }

  117.     /**
  118.      * Quickly append all elements of another BlockList.
  119.      *
  120.      * @param src
  121.      *            the list to copy elements from.
  122.      */
  123.     public void addAll(BlockList<T> src) {
  124.         if (src.size == 0)
  125.             return;

  127.         int srcDirIdx = 0;
  128.         for (; srcDirIdx < src.tailDirIdx; srcDirIdx++)
  129.             addAll(src.directory[srcDirIdx], 0, BLOCK_SIZE);
  130.         if (src.tailBlkIdx != 0)
  131.             addAll(src.tailBlock, 0, src.tailBlkIdx);
  132.     }

  134.     /**
  135.      * Quickly append all elements from an array.
  136.      *
  137.      * @param src
  138.      *            the source array.
  139.      * @param srcIdx
  140.      *            first index to copy.
  141.      * @param srcCnt
  142.      *            number of elements to copy.
  143.      */
  144.     public void addAll(T[] src, int srcIdx, int srcCnt) {
  145.         while (0 < srcCnt) {
  146.             int i = tailBlkIdx;
  147.             int n = Math.min(srcCnt, BLOCK_SIZE - i);
  148.             if (n == 0) {
  149.                 // Our tail is full, expand by one.
  150.                 add(src[srcIdx++]);
  151.                 srcCnt--;
  152.                 continue;
  153.             }

  155.             System.arraycopy(src, srcIdx, tailBlock, i, n);
  156.             tailBlkIdx += n;
  157.             size += n;
  158.             srcIdx += n;
  159.             srcCnt -= n;
  160.         }
  161.     }

  163.     /** {@inheritDoc} */
  164.     @Override
  165.     public boolean add(T element) {
  166.         int i = tailBlkIdx;
  167.         if (i < BLOCK_SIZE) {
  168.             // Fast-path: Append to current tail block.
  169.             tailBlock[i] = element;
  170.             tailBlkIdx = i + 1;
  171.             size++;
  172.             return true;
  173.         }

  175.         // Slow path: Move to the next block, expanding if necessary.
  176.         if (++tailDirIdx == directory.length) {
  177.             T[][] newDir = BlockList.<T> newDirectory(directory.length << 1);
  178.             System.arraycopy(directory, 0, newDir, 0, directory.length);
  179.             directory = newDir;
  180.         }

  182.         T[] blockRef = directory[tailDirIdx];
  183.         if (blockRef == null) {
  184.             blockRef = BlockList.<T> newBlock();
  185.             directory[tailDirIdx] = blockRef;
  186.         }
  187.         blockRef[0] = element;
  188.         tailBlock = blockRef;
  189.         tailBlkIdx = 1;
  190.         size++;
  191.         return true;
  192.     }

  194.     /** {@inheritDoc} */
  195.     @Override
  196.     public void add(int index, T element) {
  197.         if (index == size) {
  198.             // Fast-path: append onto the end of the list.
  199.             add(element);

  201.         } else if (index < 0 || size < index) {
  202.             throw new IndexOutOfBoundsException(String.valueOf(index));

  204.         } else {
  205.             // Slow-path: the list needs to expand and insert.
  206.             // Do this the naive way, callers shouldn't abuse
  207.             // this class by entering this code path.
  208.             //
  209.             add(null); // expand the list by one
  210.             for (int oldIdx = size - 2; index <= oldIdx; oldIdx--)
  211.                 set(oldIdx + 1, get(oldIdx));
  212.             set(index, element);
  213.         }
  214.     }

  216.     /** {@inheritDoc} */
  217.     @Override
  218.     public T remove(int index) {
  219.         if (index == size - 1) {
  220.             // Fast-path: remove the last element.
  221.             T[] blockRef = directory[toDirectoryIndex(index)];
  222.             int blockIdx = toBlockIndex(index);
  223.             T old = blockRef[blockIdx];
  224.             blockRef[blockIdx] = null;
  225.             size--;
  226.             if (0 < tailBlkIdx)
  227.                 tailBlkIdx--;
  228.             else
  229.                 resetTailBlock();
  230.             return old;

  232.         } else if (index < 0 || size <= index) {
  233.             throw new IndexOutOfBoundsException(String.valueOf(index));

  235.         } else {
  236.             // Slow-path: the list needs to contract and remove.
  237.             // Do this the naive way, callers shouldn't abuse
  238.             // this class by entering this code path.
  239.             //
  240.             T old = get(index);
  241.             for (; index < size - 1; index++)
  242.                 set(index, get(index + 1));
  243.             set(size - 1, null);
  244.             size--;
  245.             resetTailBlock();
  246.             return old;
  247.         }
  248.     }

  250.     private void resetTailBlock() {
  251.         tailDirIdx = toDirectoryIndex(size);
  252.         tailBlkIdx = toBlockIndex(size);
  253.         tailBlock = directory[tailDirIdx];
  254.     }

  256.     /** {@inheritDoc} */
  257.     @Override
  258.     public Iterator<T> iterator() {
  259.         return new MyIterator();
  260.     }

  262.     static final int toDirectoryIndex(int index) {
  263.         return index >>> BLOCK_BITS;
  264.     }

  266.     static final int toBlockIndex(int index) {
  267.         return index & BLOCK_MASK;
  268.     }

  270.     @SuppressWarnings("unchecked")
  271.     private static <T> T[][] newDirectory(int size) {
  272.         return (T[][]) new Object[size][];
  273.     }

  275.     @SuppressWarnings("unchecked")
  276.     private static <T> T[] newBlock() {
  277.         return (T[]) new Object[BLOCK_SIZE];
  278.     }

  280.     private class MyIterator implements Iterator<T> {
  281.         private int index;

  283.         private int dirIdx;

  285.         private int blkIdx;

  287.         private T[] block = directory[0];

  289.         @Override
  290.         public boolean hasNext() {
  291.             return index < size;
  292.         }

  294.         @Override
  295.         public T next() {
  296.             if (size <= index)
  297.                 throw new NoSuchElementException();

  299.             T res = block[blkIdx];
  300.             if (++blkIdx == BLOCK_SIZE) {
  301.                 if (++dirIdx < directory.length)
  302.                     block = directory[dirIdx];
  303.                 else
  304.                     block = null;
  305.                 blkIdx = 0;
  306.             }
  307.             index++;
  308.             return res;
  309.         }

  311.         @Override
  312.         public void remove() {
  313.             if (index == 0)
  314.                 throw new IllegalStateException();

  316.             BlockList.this.remove(--index);

  318.             dirIdx = toDirectoryIndex(index);
  319.             blkIdx = toBlockIndex(index);
  320.             block = directory[dirIdx];
  321.         }
  322.     }
  323. }
Created with JaCoCo 0.8.6.202009150832