Re: [EGIT PATCH 05/20] Reverse pack index implementation: PackReverseIndex
- From
Shawn O. Pearce <spearce@spearce.org>
- Date
- Jun 16, 2008, 04:06 UTC
- Message-ID
- <20080616040635.GU11793@spearce.org>
- In-Reply-To
- <1213566349-25395-6-git-send-email-marek.zawirski@gmail.com>
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.
Show 5 quoted lines
> + 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.
Show 6 quoted lines
> + 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.
Show 7 quoted lines
> + 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.