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

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