| /* |
| * Copyright (C) 2011, Google Inc. |
| * and other copyright owners as documented in the project's IP log. |
| * |
| * This program and the accompanying materials are made available |
| * under the terms of the Eclipse Distribution License v1.0 which |
| * accompanies this distribution, is reproduced below, and is |
| * available at http://www.eclipse.org/org/documents/edl-v10.php |
| * |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or |
| * without modification, are permitted provided that the following |
| * conditions are met: |
| * |
| * - Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * - Redistributions in binary form must reproduce the above |
| * copyright notice, this list of conditions and the following |
| * disclaimer in the documentation and/or other materials provided |
| * with the distribution. |
| * |
| * - Neither the name of the Eclipse Foundation, Inc. nor the |
| * names of its contributors may be used to endorse or promote |
| * products derived from this software without specific prior |
| * written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND |
| * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, |
| * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER |
| * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF |
| * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| package org.eclipse.jgit.util; |
| |
| import java.util.AbstractList; |
| import java.util.Arrays; |
| import java.util.Iterator; |
| import java.util.NoSuchElementException; |
| |
| /** |
| * Random access list that allocates entries in blocks. |
| * <p> |
| * Unlike {@link java.util.ArrayList}, this type does not need to reallocate the |
| * internal array in order to expand the capacity of the list. Access to any |
| * element is constant time, but requires two array lookups instead of one. |
| * <p> |
| * To handle common usages, {@link #add(Object)} and {@link #iterator()} use |
| * internal code paths to amortize out the second array lookup, making addition |
| * and simple iteration closer to one array operation per element processed. |
| * <p> |
| * Similar to {@code ArrayList}, adding or removing from any position except the |
| * end of the list requires O(N) time to copy all elements between the |
| * modification point and the end of the list. Applications are strongly |
| * encouraged to not use this access pattern with this list implementation. |
| * |
| * @param <T> |
| * type of list element. |
| */ |
| public class BlockList<T> extends AbstractList<T> { |
| private static final int BLOCK_BITS = 10; |
| |
| static final int BLOCK_SIZE = 1 << BLOCK_BITS; |
| |
| private static final int BLOCK_MASK = BLOCK_SIZE - 1; |
| |
| T[][] directory; |
| |
| int size; |
| |
| private int tailDirIdx; |
| |
| private int tailBlkIdx; |
| |
| private T[] tailBlock; |
| |
| /** |
| * Initialize an empty list. |
| */ |
| public BlockList() { |
| directory = BlockList.<T> newDirectory(256); |
| directory[0] = BlockList.<T> newBlock(); |
| tailBlock = directory[0]; |
| } |
| |
| /** |
| * Initialize an empty list with an expected capacity. |
| * |
| * @param capacity |
| * number of elements expected to be in the list. |
| */ |
| public BlockList(int capacity) { |
| int dirSize = toDirectoryIndex(capacity); |
| if ((capacity & BLOCK_MASK) != 0 || dirSize == 0) |
| dirSize++; |
| directory = BlockList.<T> newDirectory(dirSize); |
| directory[0] = BlockList.<T> newBlock(); |
| tailBlock = directory[0]; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void clear() { |
| for (T[] block : directory) { |
| if (block != null) |
| Arrays.fill(block, null); |
| } |
| size = 0; |
| tailDirIdx = 0; |
| tailBlkIdx = 0; |
| tailBlock = directory[0]; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public T get(int index) { |
| if (index < 0 || size <= index) |
| throw new IndexOutOfBoundsException(String.valueOf(index)); |
| return directory[toDirectoryIndex(index)][toBlockIndex(index)]; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public T set(int index, T element) { |
| if (index < 0 || size <= index) |
| throw new IndexOutOfBoundsException(String.valueOf(index)); |
| T[] blockRef = directory[toDirectoryIndex(index)]; |
| int blockIdx = toBlockIndex(index); |
| T old = blockRef[blockIdx]; |
| blockRef[blockIdx] = element; |
| return old; |
| } |
| |
| /** |
| * Quickly append all elements of another BlockList. |
| * |
| * @param src |
| * the list to copy elements from. |
| */ |
| public void addAll(BlockList<T> src) { |
| if (src.size == 0) |
| return; |
| |
| int srcDirIdx = 0; |
| for (; srcDirIdx < src.tailDirIdx; srcDirIdx++) |
| addAll(src.directory[srcDirIdx], 0, BLOCK_SIZE); |
| if (src.tailBlkIdx != 0) |
| addAll(src.tailBlock, 0, src.tailBlkIdx); |
| } |
| |
| /** |
| * Quickly append all elements from an array. |
| * |
| * @param src |
| * the source array. |
| * @param srcIdx |
| * first index to copy. |
| * @param srcCnt |
| * number of elements to copy. |
| */ |
| public void addAll(T[] src, int srcIdx, int srcCnt) { |
| while (0 < srcCnt) { |
| int i = tailBlkIdx; |
| int n = Math.min(srcCnt, BLOCK_SIZE - i); |
| if (n == 0) { |
| // Our tail is full, expand by one. |
| add(src[srcIdx++]); |
| srcCnt--; |
| continue; |
| } |
| |
| System.arraycopy(src, srcIdx, tailBlock, i, n); |
| tailBlkIdx += n; |
| size += n; |
| srcIdx += n; |
| srcCnt -= n; |
| } |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public boolean add(T element) { |
| int i = tailBlkIdx; |
| if (i < BLOCK_SIZE) { |
| // Fast-path: Append to current tail block. |
| tailBlock[i] = element; |
| tailBlkIdx = i + 1; |
| size++; |
| return true; |
| } |
| |
| // Slow path: Move to the next block, expanding if necessary. |
| if (++tailDirIdx == directory.length) { |
| T[][] newDir = BlockList.<T> newDirectory(directory.length << 1); |
| System.arraycopy(directory, 0, newDir, 0, directory.length); |
| directory = newDir; |
| } |
| |
| T[] blockRef = directory[tailDirIdx]; |
| if (blockRef == null) { |
| blockRef = BlockList.<T> newBlock(); |
| directory[tailDirIdx] = blockRef; |
| } |
| blockRef[0] = element; |
| tailBlock = blockRef; |
| tailBlkIdx = 1; |
| size++; |
| return true; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void add(int index, T element) { |
| if (index == size) { |
| // Fast-path: append onto the end of the list. |
| add(element); |
| |
| } else if (index < 0 || size < index) { |
| throw new IndexOutOfBoundsException(String.valueOf(index)); |
| |
| } else { |
| // Slow-path: the list needs to expand and insert. |
| // Do this the naive way, callers shouldn't abuse |
| // this class by entering this code path. |
| // |
| add(null); // expand the list by one |
| for (int oldIdx = size - 2; index <= oldIdx; oldIdx--) |
| set(oldIdx + 1, get(oldIdx)); |
| set(index, element); |
| } |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public T remove(int index) { |
| if (index == size - 1) { |
| // Fast-path: remove the last element. |
| T[] blockRef = directory[toDirectoryIndex(index)]; |
| int blockIdx = toBlockIndex(index); |
| T old = blockRef[blockIdx]; |
| blockRef[blockIdx] = null; |
| size--; |
| if (0 < tailBlkIdx) |
| tailBlkIdx--; |
| else |
| resetTailBlock(); |
| return old; |
| |
| } else if (index < 0 || size <= index) { |
| throw new IndexOutOfBoundsException(String.valueOf(index)); |
| |
| } else { |
| // Slow-path: the list needs to contract and remove. |
| // Do this the naive way, callers shouldn't abuse |
| // this class by entering this code path. |
| // |
| T old = get(index); |
| for (; index < size - 1; index++) |
| set(index, get(index + 1)); |
| set(size - 1, null); |
| size--; |
| resetTailBlock(); |
| return old; |
| } |
| } |
| |
| private void resetTailBlock() { |
| tailDirIdx = toDirectoryIndex(size); |
| tailBlkIdx = toBlockIndex(size); |
| tailBlock = directory[tailDirIdx]; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Iterator<T> iterator() { |
| return new MyIterator(); |
| } |
| |
| static final int toDirectoryIndex(int index) { |
| return index >>> BLOCK_BITS; |
| } |
| |
| static final int toBlockIndex(int index) { |
| return index & BLOCK_MASK; |
| } |
| |
| @SuppressWarnings("unchecked") |
| private static <T> T[][] newDirectory(int size) { |
| return (T[][]) new Object[size][]; |
| } |
| |
| @SuppressWarnings("unchecked") |
| private static <T> T[] newBlock() { |
| return (T[]) new Object[BLOCK_SIZE]; |
| } |
| |
| private class MyIterator implements Iterator<T> { |
| private int index; |
| |
| private int dirIdx; |
| |
| private int blkIdx; |
| |
| private T[] block = directory[0]; |
| |
| @Override |
| public boolean hasNext() { |
| return index < size; |
| } |
| |
| @Override |
| public T next() { |
| if (size <= index) |
| throw new NoSuchElementException(); |
| |
| T res = block[blkIdx]; |
| if (++blkIdx == BLOCK_SIZE) { |
| if (++dirIdx < directory.length) |
| block = directory[dirIdx]; |
| else |
| block = null; |
| blkIdx = 0; |
| } |
| index++; |
| return res; |
| } |
| |
| @Override |
| public void remove() { |
| if (index == 0) |
| throw new IllegalStateException(); |
| |
| BlockList.this.remove(--index); |
| |
| dirIdx = toDirectoryIndex(index); |
| blkIdx = toBlockIndex(index); |
| block = directory[dirIdx]; |
| } |
| } |
| } |