Implement get nth offset in PackIndex.
Currently, the offset can only be retrieved by ObjectId or iterating all
of the entries. Add a method to lookup the offset by position in the
index sorted by SHA1.
Change-Id: I45e9ac8b752d1dab47b202753a1dcca7122b958e
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java
index aa3817e..7eeb0c0 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/file/PackIndexTestCase.java
@@ -158,6 +158,21 @@ public void testCompareEntriesOffsetsWithFindOffsets() {
}
/**
+ * Compare offset from iterator entries with output of getOffset() method.
+ */
+ @Test
+ public void testCompareEntriesOffsetsWithGetOffsets() {
+ int i = 0;
+ for (MutableEntry me : smallIdx) {
+ assertEquals(smallIdx.getOffset(i++), me.getOffset());
+ }
+ int j = 0;
+ for (MutableEntry me : denseIdx) {
+ assertEquals(denseIdx.getOffset(j++), me.getOffset());
+ }
+ }
+
+ /**
* Test partial results of iterator comparing to content of well-known
* (prepared) dense index, that may need multi-level indexing.
*/
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java
index 44baeb1..0040aea 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndex.java
@@ -245,6 +245,19 @@ public final ObjectId getObjectId(final int nthPosition) {
}
/**
+ * Get offset in a pack for the n-th object entry returned by
+ * {@link #iterator()}.
+ *
+ * @param nthPosition
+ * unsigned 32 bit position within the traversal of
+ * {@link #iterator()} for which the caller needs the offset. The
+ * first returned {@link MutableEntry} is 0, the second is 1,
+ * etc. Positions past 2**31-1 are negative, but still valid.
+ * @return the offset in a pack for the corresponding entry.
+ */
+ abstract long getOffset(long nthPosition);
+
+ /**
* Locate the file offset position for the requested object.
*
* @param objId
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java
index 8c381fb..2d574d8 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV1.java
@@ -113,15 +113,13 @@ public long getOffset64Count() {
return n64;
}
- @Override
- public ObjectId getObjectId(final long nthPosition) {
+ private int findLevelOne(final long nthPosition) {
int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);
- long base;
if (levelOne >= 0) {
// If we hit the bucket exactly the item is in the bucket, or
// any bucket before it which has the same object count.
//
- base = idxHeader[levelOne];
+ long base = idxHeader[levelOne];
while (levelOne > 0 && base == idxHeader[levelOne - 1])
levelOne--;
} else {
@@ -129,14 +127,31 @@ public ObjectId getObjectId(final long nthPosition) {
//
levelOne = -(levelOne + 1);
}
+ return levelOne;
+ }
- base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
- final int p = (int) (nthPosition - base);
+ private int getLevelTwo(final long nthPosition, final int levelOne) {
+ final long base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
+ return (int) (nthPosition - base);
+ }
+
+ @Override
+ public ObjectId getObjectId(final long nthPosition) {
+ final int levelOne = findLevelOne(nthPosition);
+ final int p = getLevelTwo(nthPosition, levelOne);
final int dataIdx = idOffset(p);
return ObjectId.fromRaw(idxdata[levelOne], dataIdx);
}
@Override
+ long getOffset(long nthPosition) {
+ final int levelOne = findLevelOne(nthPosition);
+ final int levelTwo = getLevelTwo(nthPosition, levelOne);
+ final int p = (4 + Constants.OBJECT_ID_LENGTH) * levelTwo;
+ return NB.decodeUInt32(idxdata[levelOne], p);
+ }
+
+ @Override
public long findOffset(final AnyObjectId objId) {
final int levelOne = objId.getFirstByte();
byte[] data = idxdata[levelOne];
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java
index 9b1a5f3..9d2caa2 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/file/PackIndexV2.java
@@ -170,15 +170,13 @@ public long getOffset64Count() {
return offset64.length / 8;
}
- @Override
- public ObjectId getObjectId(final long nthPosition) {
+ private int findLevelOne(final long nthPosition) {
int levelOne = Arrays.binarySearch(fanoutTable, nthPosition + 1);
- long base;
if (levelOne >= 0) {
// If we hit the bucket exactly the item is in the bucket, or
// any bucket before it which has the same object count.
//
- base = fanoutTable[levelOne];
+ long base = fanoutTable[levelOne];
while (levelOne > 0 && base == fanoutTable[levelOne - 1])
levelOne--;
} else {
@@ -186,19 +184,39 @@ public ObjectId getObjectId(final long nthPosition) {
//
levelOne = -(levelOne + 1);
}
+ return levelOne;
+ }
- base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
- final int p = (int) (nthPosition - base);
+ private int getLevelTwo(final long nthPosition, final int levelOne) {
+ final long base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
+ return (int) (nthPosition - base);
+ }
+
+ @Override
+ public ObjectId getObjectId(final long nthPosition) {
+ final int levelOne = findLevelOne(nthPosition);
+ final int p = getLevelTwo(nthPosition, levelOne);
final int p4 = p << 2;
return ObjectId.fromRaw(names[levelOne], p4 + p); // p * 5
}
@Override
+ public long getOffset(final long nthPosition) {
+ final int levelOne = findLevelOne(nthPosition);
+ final int levelTwo = getLevelTwo(nthPosition, levelOne);
+ return getOffset(levelOne, levelTwo);
+ }
+
+ @Override
public long findOffset(final AnyObjectId objId) {
final int levelOne = objId.getFirstByte();
final int levelTwo = binarySearchLevelTwo(objId, levelOne);
if (levelTwo == -1)
return -1;
+ return getOffset(levelOne, levelTwo);
+ }
+
+ private long getOffset(final int levelOne, final int levelTwo) {
final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);
if ((p & IS_O64) != 0)
return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
