MultiPackIndex: Add and implement #resolve() method

The reader offers the resolve functionality to find object ids with
certain prefix. The basic implementation iterates through packs and
calls resolve in their indexes. With multipack index, we can answer
the resolve directly for all the packs included.

Offer a resolve() method and implement it in the multipack index.

Change-Id: If5679652f149a41afe568c719ba40b291ae1b917

2 files changed, 75 insertions, 1 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndex.java
index 845576d8c2..15b52391b8 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndex.java
@@ -10,7 +10,11 @@
 
 package org.eclipse.jgit.internal.storage.midx;
 
+import java.util.Set;
+
+import org.eclipse.jgit.lib.AbbreviatedObjectId;
 import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.ObjectId;
 
 /**
  * An index over multiple packs
@@ -48,6 +52,20 @@ public interface MultiPackIndex {
 	PackOffset find(AnyObjectId objectId);
 
 	/**
+	 * Find objects matching the prefix abbreviation.
+	 *
+	 * @param matches
+	 *            set to add any located ObjectIds to. This is an output
+	 *            parameter.
+	 * @param id
+	 *            prefix to search for.
+	 * @param matchLimit
+	 *            maximum number of results to return. At most this many
+	 *            ObjectIds should be added to matches before returning.
+	 */
+	void resolve(Set<ObjectId> matches, AbbreviatedObjectId id, int matchLimit);
+
+	/**
 	 * Memory size of this multipack index
 	 *
 	 * @return size of this multipack index in memory, in bytes
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndexV1.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndexV1.java
index bb122c7a01..be752cc4b5 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndexV1.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/midx/MultiPackIndexV1.java
@@ -12,12 +12,15 @@ package org.eclipse.jgit.internal.storage.midx;
 
 import java.nio.charset.StandardCharsets;
 import java.util.Arrays;
+import java.util.Set;
 
 import org.eclipse.jgit.annotations.NonNull;
 import org.eclipse.jgit.annotations.Nullable;
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.internal.storage.midx.MultiPackIndexLoader.MultiPackIndexFormatException;
+import org.eclipse.jgit.lib.AbbreviatedObjectId;
 import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.util.NB;
 
 /**
@@ -69,6 +72,12 @@ class MultiPackIndexV1 implements MultiPackIndex {
 	}
 
 	@Override
+	public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
+			int matchLimit) {
+		idx.resolve(matches, id, matchLimit);
+	}
+
+	@Override
 	public long getMemorySize() {
 		int packNamesSize = Arrays.stream(packNames)
 				.mapToInt(s -> s.getBytes(StandardCharsets.UTF_8).length).sum();
@@ -146,7 +155,8 @@ class MultiPackIndexV1 implements MultiPackIndex {
 		}
 
 		long getMemorySize() {
-			return (long)byteArrayLengh(offsets) + byteArrayLengh(largeOffsets);
+			return (long) byteArrayLengh(offsets)
+					+ byteArrayLengh(largeOffsets);
 		}
 	}
 
@@ -226,6 +236,52 @@ class MultiPackIndexV1 implements MultiPackIndex {
 			return -1;
 		}
 
+		void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
+				int matchLimit) {
+			if (matches.size() >= matchLimit) {
+				return;
+			}
+
+			if (oidLookup.length == 0) {
+				return;
+			}
+
+			int high = fanoutTable[id.getFirstByte()];
+			int low = id.getFirstByte() == 0 ? 0
+					: fanoutTable[id.getFirstByte() - 1];
+			do {
+				int p = (low + high) >>> 1;
+				int cmp = id.prefixCompare(oidLookup, idOffset(p));
+				if (cmp < 0) {
+					high = p;
+					continue;
+				}
+
+				if (cmp > 0) {
+					low = p + 1;
+					continue;
+				}
+
+				// Got a match.
+				// We may have landed in the middle of the matches. Move
+				// backwards to the start of matches, then walk forwards.
+				while (0 < p
+						&& id.prefixCompare(oidLookup, idOffset(p - 1)) == 0) {
+					p--;
+				}
+				while (p < high && id.prefixCompare(oidLookup, idOffset(p)) == 0
+						&& matches.size() < matchLimit) {
+					matches.add(ObjectId.fromRaw(oidLookup, idOffset(p)));
+					p++;
+				}
+				return;
+			} while (low < high);
+		}
+
+		private int idOffset(int position) {
+			return position * hashLength;
+		}
+
 		long getMemorySize() {
 			return 4L + byteArrayLengh(oidLookup) + (FANOUT * 4);
 		}