JGit 7.2.0.202503040940-r · org.eclipse.jgit.internal.storage.pack.DeltaIndex

Index of blocks in a source file.

The index can be passed a result buffer, and output an instruction sequence that transforms the source buffer used by the index into the result buffer. The instruction sequence can be executed by org.eclipse.jgit.internal.storage.pack.BinaryDelta to recreate the result buffer.

An index stores the entire contents of the source buffer, but also a table of block identities mapped to locations where the block appears in the source buffer. The mapping table uses 12 bytes for every 16 bytes of source buffer, and is therefore ~75% of the source buffer size. The overall index is ~1.75x the size of the source buffer. This relationship holds for any JVM, as only a constant number of objects are allocated per index. Callers can use the method getIndexSize() to obtain a reasonably accurate estimate of the complete heap space used by this index.

A DeltaIndex is thread-safe. Concurrent threads can use the same index to encode delta instructions for different result buffers.

Field Summary

Modifier and Type	Field and Description
pack-priv static final int	BLKSZ Number of bytes in a block.
private final long[]	entries Pairs of block hash value and `src` offsets.
private static final int	MAX_CHAIN_LENGTH Maximum number of positions to consider for a given content hash.
private final byte[]	src Original source file that we indexed.
private static final int[]	T
private final int[]	table Pointers into the `entries` table, indexed by block hash.
private final int	tableMask Mask to make block hashes into an array index for `table`.
private static final int[]	U

Constructor Summary

Access	Constructor and Description
public	DeltaIndex(byte[] the source file's raw contents. The buffer will be held by the index instance to facilitate matching, and therefore must not be modified by the caller. sourceBuffer) Construct an index from the source file.

Method Summary

Modifier and Type	Method and Description
private void	copyEntries(DeltaIndexScanner scan)
private int	countEntries(DeltaIndexScanner scan)
public void	encode(OutputStream stream to receive the delta instructions that can transform this index's source buffer into `res`. This stream should be buffered, as instructions are written directly to it in small bursts. out, byte[] the desired result buffer. The generated instructions will recreate this buffer when applied to the source buffer stored within this index. res) Generate a delta sequence to recreate the result buffer.
public boolean	Returns: true if the delta is smaller than deltaSizeLimit; false if the encoder aborted because the encoded delta instructions would be longer than deltaSizeLimit bytes. encode(OutputStream stream to receive the delta instructions that can transform this index's source buffer into `res`. This stream should be buffered, as instructions are written directly to it in small bursts. If the caller might need to discard the instructions (such as when deltaSizeLimit would be exceeded) the caller is responsible for discarding or rewinding the stream when this method returns false. out, byte[] the desired result buffer. The generated instructions will recreate this buffer when applied to the source buffer stored within this index. res, int maximum number of bytes that the delta instructions can occupy. If the generated instructions would be longer than this amount, this method returns false. If 0, there is no limit on the length of delta created. deltaSizeLimit) Generate a delta sequence to recreate the result buffer.
public static long	Returns: estimated size. Approximately `1.75 * sourceLength`. estimateIndexSize(int length of the source, in bytes. sourceLength) Estimate the size of an index for a given source.
private static int	fwdmatch(byte[] res, int resPtr, byte[] src, int srcPtr)
public long	Returns: an approximation of the number of bytes used by this index in memory. The size includes the cached source buffer size from `getSourceSize()`, as well as a rough approximation of JVM object overheads. getIndexSize() Get an estimate of the memory required by this index.
public long	Returns: size of the source buffer this index has scanned. getSourceSize() Get size of the source buffer this index has scanned.
pack-priv static int	hashBlock(byte[] raw, int ptr)
private static int	keyOf(long ent)
private static int	negmatch(byte[] res, int resPtr, byte[] src, int srcPtr, int limit)
private DeltaEncoder	newEncoder(OutputStream out, long resSize, int limit)
private static long	sizeOf(byte[] b)
private static long	sizeOf(int[] b)
private static long	sizeOf(long[] b)
private static int	sizeOfArray(int entSize, int len)
private static int	step(int hash, byte toRemove, byte toAdd)
public String	toString() Overrides java.lang.Object.toString. Returns a string representation of the object.
private static int	valOf(long ent)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll wait wait wait

Field Detail

BLKSZ	back to summary
pack-priv static final int BLKSZ Number of bytes in a block.

entries back to summary

entries	back to summary
private final long[] entries Pairs of block hash value and `src` offsets. The very first entry in this table at index 0 is always empty, this is to allow fast evaluation when `table` has no values under any given slot. Remaining entries are pairs of integers, with the upper 32 bits holding the block hash and the lower 32 bits holding the source offset.

private final long[] entries

Pairs of block hash value and src offsets.

The very first entry in this table at index 0 is always empty, this is to allow fast evaluation when table has no values under any given slot. Remaining entries are pairs of integers, with the upper 32 bits holding the block hash and the lower 32 bits holding the source offset.

MAX_CHAIN_LENGTH	back to summary
private static final int MAX_CHAIN_LENGTH Maximum number of positions to consider for a given content hash. All positions with the same content hash are stored into a single chain. The chain size is capped to ensure delta encoding stays linear time at O(len_src + len_dst) rather than quadratic at O(len_src * len_dst).

MAX_CHAIN_LENGTH

back to summary

private static final int MAX_CHAIN_LENGTH

Maximum number of positions to consider for a given content hash.

All positions with the same content hash are stored into a single chain. The chain size is capped to ensure delta encoding stays linear time at O(len_src + len_dst) rather than quadratic at O(len_src * len_dst).

src	back to summary
private final byte[] src Original source file that we indexed.

T	back to summary
private static final int[] T

table back to summary

table	back to summary
private final int[] table Pointers into the `entries` table, indexed by block hash. A block hash is masked with `tableMask` to become the array index of this table. The value stored here is the first index within `entries` that starts the consecutive list of blocks with that same masked hash. If there are no matching blocks, 0 is stored instead. Note that this table is always a power of 2 in size, to support fast normalization of a block hash into an array index.

private final int[] table

Pointers into the entries table, indexed by block hash.

A block hash is masked with tableMask to become the array index of this table. The value stored here is the first index within entries that starts the consecutive list of blocks with that same masked hash. If there are no matching blocks, 0 is stored instead.

Note that this table is always a power of 2 in size, to support fast normalization of a block hash into an array index.

tableMask	back to summary
private final int tableMask Mask to make block hashes into an array index for `table`.

U	back to summary
private static final int[] U

Constructor Detail

DeltaIndex	back to summary
public DeltaIndex(byte[] sourceBuffer) Construct an index from the source file. Parameters sourceBuffer:byte[] the source file's raw contents. The buffer will be held by the index instance to facilitate matching, and therefore must not be modified by the caller.

DeltaIndex

back to summary

public DeltaIndex(byte[] sourceBuffer)

Construct an index from the source file.

Parameters

sourceBuffer:byte[]: the source file's raw contents. The buffer will be held by the index instance to facilitate matching, and therefore must not be modified by the caller.

Method Detail

copyEntries	back to summary
private void copyEntries(DeltaIndexScanner scan)

countEntries	back to summary
private int countEntries(DeltaIndexScanner scan)

encode back to summary

encode	back to summary
public void encode(OutputStream out, byte[] res) throws IOException Generate a delta sequence to recreate the result buffer. There is no limit on the size of the delta sequence created. This is the same as `encode(out, res, 0)`. Parameters out:OutputStream stream to receive the delta instructions that can transform this index's source buffer into `res`. This stream should be buffered, as instructions are written directly to it in small bursts. res:byte[] the desired result buffer. The generated instructions will recreate this buffer when applied to the source buffer stored within this index. Exceptions IOException: the output stream refused to write the instructions.

public void encode(OutputStream out, byte[] res) throws IOException

Generate a delta sequence to recreate the result buffer.

There is no limit on the size of the delta sequence created. This is the same as encode(out, res, 0).

Parameters

out:OutputStream: stream to receive the delta instructions that can transform this index's source buffer into res. This stream should be buffered, as instructions are written directly to it in small bursts.
res:byte[]: the desired result buffer. The generated instructions will recreate this buffer when applied to the source buffer stored within this index.

Exceptions

IOException:: the output stream refused to write the instructions.

encode back to summary

encode	back to summary
public boolean encode(OutputStream out, byte[] res, int deltaSizeLimit) throws IOException Generate a delta sequence to recreate the result buffer. Parameters out:OutputStream stream to receive the delta instructions that can transform this index's source buffer into `res`. This stream should be buffered, as instructions are written directly to it in small bursts. If the caller might need to discard the instructions (such as when deltaSizeLimit would be exceeded) the caller is responsible for discarding or rewinding the stream when this method returns false. res:byte[] the desired result buffer. The generated instructions will recreate this buffer when applied to the source buffer stored within this index. deltaSizeLimit:int maximum number of bytes that the delta instructions can occupy. If the generated instructions would be longer than this amount, this method returns false. If 0, there is no limit on the length of delta created. Returns:boolean true if the delta is smaller than deltaSizeLimit; false if the encoder aborted because the encoded delta instructions would be longer than deltaSizeLimit bytes. Exceptions IOException: the output stream refused to write the instructions.

public boolean encode(OutputStream out, byte[] res, int deltaSizeLimit) throws IOException

Generate a delta sequence to recreate the result buffer.

Parameters

out:OutputStream: stream to receive the delta instructions that can transform this index's source buffer into res. This stream should be buffered, as instructions are written directly to it in small bursts. If the caller might need to discard the instructions (such as when deltaSizeLimit would be exceeded) the caller is responsible for discarding or rewinding the stream when this method returns false.
res:byte[]: the desired result buffer. The generated instructions will recreate this buffer when applied to the source buffer stored within this index.
deltaSizeLimit:int: maximum number of bytes that the delta instructions can occupy. If the generated instructions would be longer than this amount, this method returns false. If 0, there is no limit on the length of delta created.

Returns:boolean

true if the delta is smaller than deltaSizeLimit; false if the encoder aborted because the encoded delta instructions would be longer than deltaSizeLimit bytes.

Exceptions

IOException:: the output stream refused to write the instructions.

estimateIndexSize back to summary

estimateIndexSize	back to summary
public static long estimateIndexSize(int sourceLength) Estimate the size of an index for a given source. This is roughly a worst-case estimate. The actual index may be smaller. Parameters sourceLength:int length of the source, in bytes. Returns:long estimated size. Approximately `1.75 * sourceLength`.

public static long estimateIndexSize(int sourceLength)

Estimate the size of an index for a given source.

This is roughly a worst-case estimate. The actual index may be smaller.

Parameters

sourceLength:int: length of the source, in bytes.

Returns:long

estimated size. Approximately 1.75 * sourceLength.

fwdmatch	back to summary
private static int fwdmatch(byte[] res, int resPtr, byte[] src, int srcPtr)

getIndexSize back to summary

getIndexSize	back to summary
public long getIndexSize() Get an estimate of the memory required by this index. Returns:long an approximation of the number of bytes used by this index in memory. The size includes the cached source buffer size from `getSourceSize()`, as well as a rough approximation of JVM object overheads.

public long getIndexSize()

Get an estimate of the memory required by this index.

Returns:long: an approximation of the number of bytes used by this index in memory. The size includes the cached source buffer size from getSourceSize(), as well as a rough approximation of JVM object overheads.

getSourceSize	back to summary
public long getSourceSize() Get size of the source buffer this index has scanned. Returns:long size of the source buffer this index has scanned.

getSourceSize

back to summary

public long getSourceSize()

Get size of the source buffer this index has scanned.

Returns:long: size of the source buffer this index has scanned.

hashBlock	back to summary
pack-priv static int hashBlock(byte[] raw, int ptr)

keyOf	back to summary
private static int keyOf(long ent)

negmatch	back to summary
private static int negmatch(byte[] res, int resPtr, byte[] src, int srcPtr, int limit)

newEncoder	back to summary
private DeltaEncoder newEncoder(OutputStream out, long resSize, int limit) throws IOException

sizeOf	back to summary
private static long sizeOf(byte[] b)

sizeOf	back to summary
private static long sizeOf(int[] b)

sizeOf	back to summary
private static long sizeOf(long[] b)

sizeOfArray	back to summary
private static int sizeOfArray(int entSize, int len)

step	back to summary
private static int step(int hash, byte toRemove, byte toAdd)

toString back to summary

toString	back to summary
public String toString() Overrides java.lang.Object.toString. Doc from java.lang.Object.toString. Returns a string representation of the object. Satisfying this method's contract implies a non-`null` result must be returned. Returns:String a string representation of the object Annotations @Override @SuppressWarnings:nls

public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object. Satisfying this method's contract implies a non-null result must be returned.

Returns:String

a string representation of the object

Annotations

@Override
@SuppressWarnings:nls

valOf	back to summary
private static int valOf(long ent)

public Class DeltaIndex

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail