Marek Zawirski <marek.zawirski@xxxxxxxxx> 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.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
