Top Description Inners Fields Constructors Methods
org.eclipse.jgit.util

public Class BlockList<T>

extends AbstractList<T>
Class Inheritance
Type Parameters
<T>
type of list element.
Imports
java.util.AbstractList, .Arrays, .Iterator, .NoSuchElementException
Random access list that allocates entries in blocks.

Unlike 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.

To handle common usages, add(Object) and 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.

Similar to 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.

Nested and Inner Type Summary

Modifier and TypeClass and Description
private class
BlockList.MyIterator

Field Summary

Modifier and TypeField and Description
private static final int
BLOCK_BITS

private static final int
BLOCK_MASK

pack-priv static final int
BLOCK_SIZE

pack-priv T[][]
directory

pack-priv int
size

private int
tailBlkIdx

private T[]
tailBlock

private int
tailDirIdx

Inherited from java.util.AbstractList:
modCount

Constructor Summary

AccessConstructor and Description
public
BlockList()

Initialize an empty list.

public
BlockList(int
number of elements expected to be in the list.
capacity)

Initialize an empty list with an expected capacity.

Method Summary

Modifier and TypeMethod and Description
public boolean
add(T
element to be appended to this list
element)

Overrides java.util.AbstractList.add.

Implements java.util.List.add, java.util.Collection.add.

Appends the specified element to the end of this list (optional operation).

public void
add(int
index at which the specified element is to be inserted
index, T
element to be inserted
element)

Overrides java.util.AbstractList.add.

Implements java.util.List.add.

Inserts the specified element at the specified position in this list (optional operation).

public void
addAll(BlockList<T>
the list to copy elements from.
src)

Quickly append all elements of another BlockList.

public void
addAll(T[]
the source array.
src, int
first index to copy.
srcIdx, int
number of elements to copy.
srcCnt)

Quickly append all elements from an array.

public void
clear()

Overrides java.util.AbstractList.clear.

Implements java.util.List.clear, java.util.Collection.clear.

Removes all of the elements from this list (optional operation).

public T
get(int
index of the element to return
index)

Implements abstract java.util.AbstractList.get.

Implements java.util.List.get.

Returns the element at the specified position in this list.

public Iterator<T>
iterator()

Overrides java.util.AbstractList.iterator.

Implements java.util.List.iterator, java.util.Collection.iterator.

Returns an iterator over the elements in this list in proper sequence.

private static <T> T[]
newBlock()

private static <T> T[][]
newDirectory(int size)

public T
remove(int
the index of the element to be removed
index)

Overrides java.util.AbstractList.remove.

Implements java.util.List.remove.

Removes the element at the specified position in this list (optional operation).

private void
resetTailBlock()

public T
set(int
index of the element to replace
index, T
element to be stored at the specified position
element)

Overrides java.util.AbstractList.set.

Implements java.util.List.set.

Replaces the element at the specified position in this list with the specified element (optional operation).

public int
size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.List.size, java.util.Collection.size.

Returns the number of elements in this list.

pack-priv static final int
toBlockIndex(int index)

pack-priv static final int
toDirectoryIndex(int index)

Inherited from java.util.AbstractList:
addAllequalshashCodeindexOflastIndexOflistIteratorlistIteratorremoveRangesubList

Field Detail

BLOCK_BITSback to summary
private static final int BLOCK_BITS
BLOCK_MASKback to summary
private static final int BLOCK_MASK
BLOCK_SIZEback to summary
pack-priv static final int BLOCK_SIZE
directoryback to summary
pack-priv T[][] directory
sizeback to summary
pack-priv int size
tailBlkIdxback to summary
private int tailBlkIdx
tailBlockback to summary
private T[] tailBlock
tailDirIdxback to summary
private int tailDirIdx

Constructor Detail

BlockListback to summary
public BlockList()

Initialize an empty list.

BlockListback to summary
public BlockList(int capacity)

Initialize an empty list with an expected capacity.

Parameters
capacity:int

number of elements expected to be in the list.

Method Detail

addback to summary
public boolean add(T element)

Overrides java.util.AbstractList.add.

Implements java.util.List.add, java.util.Collection.add.

Doc from java.util.AbstractList.add.

Appends the specified element to the end of this list (optional operation).

Lists that support this operation may place limitations on what elements may be added to this list. In particular, some lists will refuse to add null elements, and others will impose restrictions on the type of elements that may be added. List classes should clearly specify in their documentation any restrictions on what elements may be added.

Parameters
element:T

element to be appended to this list

Returns:boolean

true (as specified by Collection#add)

Annotations
@Override
addback to summary
public void add(int index, T element)

Overrides java.util.AbstractList.add.

Implements java.util.List.add.

Doc from java.util.AbstractList.add.

Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Parameters
index:int

Doc from java.util.List.add.

index at which the specified element is to be inserted

element:T

Doc from java.util.List.add.

element to be inserted

Annotations
@Override
addAllback to summary
public void addAll(BlockList<T> src)

Quickly append all elements of another BlockList.

Parameters
src:BlockList<T>

the list to copy elements from.

addAllback to summary
public void addAll(T[] src, int srcIdx, int srcCnt)

Quickly append all elements from an array.

Parameters
src:T[]

the source array.

srcIdx:int

first index to copy.

srcCnt:int

number of elements to copy.

clearback to summary
public void clear()

Overrides java.util.AbstractList.clear.

Implements java.util.List.clear, java.util.Collection.clear.

Doc from java.util.AbstractList.clear.

Removes all of the elements from this list (optional operation). The list will be empty after this call returns.

Annotations
@Override
getback to summary
public T get(int index)

Implements abstract java.util.AbstractList.get.

Implements java.util.List.get.

Doc from java.util.AbstractList.get.

Returns the element at the specified position in this list.

Parameters
index:int

Doc from java.util.List.get.

index of the element to return

Returns:T

Doc from java.util.List.get.

the element at the specified position in this list

Annotations
@Override
iteratorback to summary
public Iterator<T> iterator()

Overrides java.util.AbstractList.iterator.

Implements java.util.List.iterator, java.util.Collection.iterator.

Doc from java.util.AbstractList.iterator.

Returns an iterator over the elements in this list in proper sequence.

Returns:Iterator<T>

an iterator over the elements in this list in proper sequence

Annotations
@Override
newBlockback to summary
private static <T> T[] newBlock()
Annotations
@SuppressWarnings:unchecked
newDirectoryback to summary
private static <T> T[][] newDirectory(int size)
Annotations
@SuppressWarnings:unchecked
removeback to summary
public T remove(int index)

Overrides java.util.AbstractList.remove.

Implements java.util.List.remove.

Doc from java.util.AbstractList.remove.

Removes the element at the specified position in this list (optional operation). Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the list.

Parameters
index:int

Doc from java.util.List.remove.

the index of the element to be removed

Returns:T

Doc from java.util.List.remove.

the element previously at the specified position

Annotations
@Override
resetTailBlockback to summary
private void resetTailBlock()
setback to summary
public T set(int index, T element)

Overrides java.util.AbstractList.set.

Implements java.util.List.set.

Doc from java.util.AbstractList.set.

Replaces the element at the specified position in this list with the specified element (optional operation).

Parameters
index:int

Doc from java.util.List.set.

index of the element to replace

element:T

Doc from java.util.List.set.

element to be stored at the specified position

Returns:T

Doc from java.util.List.set.

the element previously at the specified position

Annotations
@Override
sizeback to summary
public int size()

Implements abstract java.util.AbstractCollection.size.

Implements java.util.List.size, java.util.Collection.size.

Doc from java.util.List.size.

Returns the number of elements in this list. If this list contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Returns:int

the number of elements in this list

Annotations
@Override
toBlockIndexback to summary
pack-priv static final int toBlockIndex(int index)
toDirectoryIndexback to summary
pack-priv static final int toDirectoryIndex(int index)
org.eclipse.jgit.util back to summary

private Class BlockList.MyIterator

extends Object
implements Iterator<T>
Class Inheritance
All Implemented Interfaces
java.util.Iterator

Field Summary

Modifier and TypeField and Description
private int
blkIdx

private T[]
block

private int
dirIdx

private int
index

Constructor Summary

AccessConstructor and Description
private
MyIterator()

Method Summary

Modifier and TypeMethod and Description
public boolean
hasNext()

Implements java.util.Iterator.hasNext.

Returns true if the iteration has more elements.

public T
next()

Implements java.util.Iterator.next.

Returns the next element in the iteration.

public void
remove()

Overrides default java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation).

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

blkIdxback to summary
private int blkIdx
blockback to summary
private T[] block
dirIdxback to summary
private int dirIdx
indexback to summary
private int index

Constructor Detail

MyIteratorback to summary
private MyIterator()

Method Detail

hasNextback to summary
public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean

true if the iteration has more elements

Annotations
@Override
nextback to summary
public T next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Returns:T

the next element in the iteration

Annotations
@Override
removeback to summary
public void remove()

Overrides default java.util.Iterator.remove.

Doc from java.util.Iterator.remove.

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next.

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method, unless an overriding class has specified a concurrent modification policy.

The behavior of an iterator is unspecified if this method is called after a call to the forEachRemaining method.

Annotations
@Override