Re: [EGIT PATCH 05/20] Reverse pack index implementation: PackReverseIndex

["Shawn O. Pearce" <spearce@spearce.org>]

Marek Zawirski <marek.zawirski@gmail.com> wrote:
> Let us quickly find ObjectId or next object for specified offset in a
> pack, in O(log n) time.
...
> diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java
...
> +	/**
> +	 * Object ids corresponding to {@link #offsets32} and {@link #offsets64}.
> +	 */
> +	private final int names[];

This could be smaller if it was an array of indexes into the index,
rather than the ObjectId itself.  Thus we need only 1 int per object
and not 5 ints per object.

But I see why you are doing it; PackIndex.MutableEntry exposes the
ObjectId and not the nth position of the object within the index.

> +	PackReverseIndex(final PackIndex index) {
> +		final long count = index.getObjectCount();
> +		if (count > Integer.MAX_VALUE)
> +			throw new IllegalArgumentException(
> +					"Huge indexes (> 2^31 entries) are not supported by jgit, yet");

For what its worth, this limit is actually:

	Integer.MAX_VALUE / Constants.OBJECT_ID_LENGTH / 4

as you store the entire ObjectId data for the index in a single int[]
array called names.  So you'll get an ArrayIndexOutOfBoundsException
or maybe OutOfMemoryError when you try to build names later on, and
never really hit this case here.

> +	ObjectId findObject(final long offset) {
> +		if (offset <= Integer.MAX_VALUE) {
> +			final int i32 = Arrays.binarySearch(offsets32, (int) offset);
> +			if (i32 < 0)
> +				return null;
> +			final int iNames = i32 * Constants.OBJECT_ID_LENGTH / 4;

This probably should be:

	final int iNames = i32 * (Constants.OBJECT_ID_LENGTH / 4);

as then we don't overflow the precision of int when i32 is large.

> +			return ObjectId.fromRaw(names, iNames);
> +		} else {
> +			final int i64 = Arrays.binarySearch(offsets64, offset);
> +			if (i64 < 0)
> +				return null;
> +			final int iNames = (i64 + offsets32.length)
> +					* Constants.OBJECT_ID_LENGTH / 4;

Again, watch out for overflow.

-- 
Shawn.