commit 40aeb19c855c6186242ac2e65c72b97a8fa90107
from: Stefan Sperling <stsp@stsp.name>
date: Fri Jun 22 11:03:45 2018 UTC

use binary search to find objects in pack index

commit - 0a554478f10b435812e7fc28336817616f75979b
commit + 40aeb19c855c6186242ac2e65c72b97a8fa90107
blob - 1c06e342deab2cbd8b559ac19788088ef3cfb16d
blob + 93c3e1d683c5a516e59d61b8e32df7dc5779e11a
--- lib/pack.c
+++ lib/pack.c
@@ -324,18 +324,24 @@ get_object_idx(struct got_packidx *packidx, struct got
 {
 	u_int8_t id0 = id->sha1[0];
 	uint32_t totobj = betoh32(packidx->hdr.fanout_table[0xff]);
-	int i = 0;
+	int left = 0, right = totobj - 1;
 
 	if (id0 > 0)
-		i = betoh32(packidx->hdr.fanout_table[id0 - 1]);
+		left = betoh32(packidx->hdr.fanout_table[id0 - 1]);
 
-	while (i < totobj) {
-		struct got_object_id *oid = &packidx->hdr.sorted_ids[i];
-		int cmp = got_object_id_cmp(id, oid);
+	while (left <= right) {
+		struct got_object_id *oid;
+		int i, cmp;
 
+		i = ((left + right) / 2);
+		oid = &packidx->hdr.sorted_ids[i];
+		cmp = got_object_id_cmp(id, oid);
 		if (cmp == 0)
 			return i;
-		i++;
+		else if (cmp > 0)
+			left = i + 1;
+		else if (cmp < 0)
+			right = i - 1;
 	}
 
 	return -1;