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

4 files changed, 73 insertions, 12 deletions

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 aa3817e3ad..7eeb0c0eaa 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 abstract class PackIndexTestCase extends RepositoryTestCase {
 	}
 
 	/**
+	 * 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 44baeb190c..0040aea713 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 abstract class PackIndex implements Iterable<PackIndex.MutableEntry> {
 	}
 
 	/**
+	 * 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 8c381fb830..2d574d80a0 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 @@ class PackIndexV1 extends PackIndex {
 		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 @@ class PackIndexV1 extends PackIndex {
 			//
 			levelOne = -(levelOne + 1);
 		}
+		return levelOne;
+	}
+
+	private int getLevelTwo(final long nthPosition, final int levelOne) {
+		final long base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
+		return (int) (nthPosition - base);
+	}
 
-		base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
-		final int p = (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 9b1a5f3ce1..9d2caa2e88 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 @@ class PackIndexV2 extends PackIndex {
 		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 @@ class PackIndexV2 extends PackIndex {
 			//
 			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)));