PackIndex: expose the position of an object-id in the index

The primary index returns the offset in the pack for an
objectId. Internally it keeps the object-ids in lexicographical order,
but doesn't expose an API to find the position of an object-id in that
list. This is needed for the object-size index, that we want to store
as "position-in-idx, size".

Add a #findPosition(object-id) method to the PackIndex interface to
know where an object-id sits in the ordered list of ids in the pack.

Note that this index position is over the list of ordered object-ids,
while reverse-index position is over the list of objects in packed
order.

Change-Id: I89fa146599e347a26d3012d3477d7f5bbbda7ba4

3 files changed, 70 insertions, 7 deletions

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 942cc96745..f4f62d4205 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
@@ -241,6 +241,17 @@ public abstract class PackIndex
 	public abstract long findOffset(AnyObjectId objId);
 
 	/**
+	 * Locate the position of this id in the list of object-ids in the index
+	 *
+	 * @param objId
+	 *            name of the object to locate within the index
+	 * @return position of the object-id in the lexicographically ordered list
+	 *         of ids stored in this index; -1 if the object does not exist in
+	 *         this index and is thus not stored in the associated pack.
+	 */
+	public abstract int findPosition(AnyObjectId objId);
+
+	/**
 	 * Retrieve stored CRC32 checksum of the requested object raw-data
 	 * (including header).
 	 *
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 eb0ac6a062..fff410b4ce 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
@@ -32,6 +32,8 @@ import org.eclipse.jgit.util.NB;
 class PackIndexV1 extends PackIndex {
 	private static final int IDX_HDR_LEN = 256 * 4;
 
+	private static final int RECORD_SIZE = 4 + Constants.OBJECT_ID_LENGTH;
+
 	private final long[] idxHeader;
 
 	byte[][] idxdata;
@@ -131,8 +133,50 @@ class PackIndexV1 extends PackIndex {
 	public long findOffset(AnyObjectId objId) {
 		final int levelOne = objId.getFirstByte();
 		byte[] data = idxdata[levelOne];
-		if (data == null)
+		int pos = levelTwoPosition(objId, data);
+		if (pos < 0) {
+			return -1;
+		}
+		// The records are (offset, objectid), pos points to objectId
+		int b0 = data[pos - 4] & 0xff;
+		int b1 = data[pos - 3] & 0xff;
+		int b2 = data[pos - 2] & 0xff;
+		int b3 = data[pos - 1] & 0xff;
+		return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
+	}
+
+	/** {@inheritDoc} */
+	@Override
+	public int findPosition(AnyObjectId objId) {
+		int levelOne = objId.getFirstByte();
+		int levelTwo = levelTwoPosition(objId, idxdata[levelOne]);
+		if (levelTwo < 0) {
 			return -1;
+		}
+		long objsBefore = levelOne == 0 ? 0 : idxHeader[levelOne - 1];
+		return (int) objsBefore + ((levelTwo - 4) / RECORD_SIZE);
+	}
+
+	/**
+	 * Find position in level two data of this objectId
+	 *
+	 * Records are (offset, objectId), so to read the corresponding offset,
+	 * caller must substract from this position.
+	 *
+	 * @param objId
+	 *            ObjectId we are looking for
+	 * @param data
+	 *            Blob of second level data with a series of (offset, objectid)
+	 *            pairs where we should find objId
+	 *
+	 * @return position in the byte[] where the objectId starts. -1 if not
+	 *         found.
+	 */
+	private int levelTwoPosition(AnyObjectId objId, byte[] data) {
+		if (data == null || data.length == 0) {
+			return -1;
+		}
+
 		int high = data.length / (4 + Constants.OBJECT_ID_LENGTH);
 		int low = 0;
 		do {
@@ -142,11 +186,7 @@ class PackIndexV1 extends PackIndex {
 			if (cmp < 0)
 				high = mid;
 			else if (cmp == 0) {
-				int b0 = data[pos - 4] & 0xff;
-				int b1 = data[pos - 3] & 0xff;
-				int b2 = data[pos - 2] & 0xff;
-				int b3 = data[pos - 1] & 0xff;
-				return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
+				return pos;
 			} else
 				low = mid + 1;
 		} while (low < high);
@@ -204,7 +244,7 @@ class PackIndexV1 extends PackIndex {
 	}
 
 	private static int idOffset(int mid) {
-		return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
+		return (RECORD_SIZE * mid) + 4;
 	}
 
 	private class IndexV1Iterator extends EntriesIterator {
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 09397e316d..7a390060c7 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
@@ -192,6 +192,18 @@ class PackIndexV2 extends PackIndex {
 		return getOffset(levelOne, levelTwo);
 	}
 
+	/** {@inheritDoc} */
+	@Override
+	public int findPosition(AnyObjectId objId) {
+		int levelOne = objId.getFirstByte();
+		int levelTwo = binarySearchLevelTwo(objId, levelOne);
+		if (levelTwo < 0) {
+			return -1;
+		}
+		long objsBefore = levelOne == 0 ? 0 : fanoutTable[levelOne - 1];
+		return (int) objsBefore + levelTwo;
+	}
+
 	private long getOffset(int levelOne, int levelTwo) {
 		final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);
 		if ((p & IS_O64) != 0)