BlockList.java
/*
* Copyright (C) 2011, Google Inc. and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
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];
}
}
}