Shawn O. Pearce wrote:
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.
Hmm, that's smart.
I can change array of names to second level indices, but I think that in
such a case PackReverseIndex should be an inner class of PackIndex and
some refactor/additional assumptions at PackIndex may be needed. What do
you think?
+ 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.
Right, my faults.
--
Marek Zawirski [zawir]
marek.zawirski@xxxxxxxxx
--
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
