Commit d5904eb865374ee10aa928ea6d4bbde099cc2ff9
2013-08-14T06:38:37
Merge pull request #1782 from libgit2/vmg/no-lookup Do not use the "experimental" lookup mode
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
diff --git a/src/oid.h b/src/oid.h
index 077d0a4..cfe7ca1 100644
--- a/src/oid.h
+++ b/src/oid.h
@@ -9,17 +9,8 @@
#include "git2/oid.h"
-/*
- * Compare two oid structures.
- *
- * @param a first oid structure.
- * @param b second oid structure.
- * @return <0, 0, >0 if a < b, a == b, a > b.
- */
-GIT_INLINE(int) git_oid__cmp(const git_oid *a, const git_oid *b)
+GIT_INLINE(int) git_oid__hashcmp(const unsigned char *sha1, const unsigned char *sha2)
{
- const unsigned char *sha1 = a->id;
- const unsigned char *sha2 = b->id;
int i;
for (i = 0; i < GIT_OID_RAWSZ; i++, sha1++, sha2++) {
@@ -30,4 +21,16 @@ GIT_INLINE(int) git_oid__cmp(const git_oid *a, const git_oid *b)
return 0;
}
+/*
+ * Compare two oid structures.
+ *
+ * @param a first oid structure.
+ * @param b second oid structure.
+ * @return <0, 0, >0 if a < b, a == b, a > b.
+ */
+GIT_INLINE(int) git_oid__cmp(const git_oid *a, const git_oid *b)
+{
+ return git_oid__hashcmp(a->id, b->id);
+}
+
#endif
diff --git a/src/pack.c b/src/pack.c
index d7e6a1e..e7fb9f1 100644
--- a/src/pack.c
+++ b/src/pack.c
@@ -1110,8 +1110,11 @@ static int pack_entry_find_offset(
short_oid->id[0], short_oid->id[1], short_oid->id[2], lo, hi, p->num_objects);
#endif
- /* Use git.git lookup code */
+#ifdef GIT_USE_LOOKUP
pos = sha1_entry_pos(index, stride, 0, lo, hi, p->num_objects, short_oid->id);
+#else
+ pos = sha1_position(index, stride, lo, hi, short_oid->id);
+#endif
if (pos >= 0) {
/* An object matching exactly the oid was found */
diff --git a/src/sha1_lookup.c b/src/sha1_lookup.c
index b7e66cc..ce067ca 100644
--- a/src/sha1_lookup.c
+++ b/src/sha1_lookup.c
@@ -9,6 +9,7 @@
#include "sha1_lookup.h"
#include "common.h"
+#include "oid.h"
/*
* Conventional binary search loop looks like this:
@@ -123,7 +124,7 @@ int sha1_entry_pos(const void *table,
lov = (lov << 8) | lo_key[ofs_0+1];
kyv = (kyv << 8) | key[ofs_0+1];
}
- assert(lov < hiv);
+ assert(lov <= hiv);
if (kyv < lov)
return -1 - lo;
@@ -176,3 +177,26 @@ int sha1_entry_pos(const void *table,
} while (lo < hi);
return -((int)lo)-1;
}
+
+int sha1_position(const void *table,
+ size_t stride,
+ unsigned lo, unsigned hi,
+ const unsigned char *key)
+{
+ const unsigned char *base = table;
+
+ do {
+ unsigned mi = (lo + hi) / 2;
+ int cmp = git_oid__hashcmp(base + mi * stride, key);
+
+ if (!cmp)
+ return mi;
+
+ if (cmp > 0)
+ hi = mi;
+ else
+ lo = mi+1;
+ } while (lo < hi);
+
+ return -((int)lo)-1;
+}
diff --git a/src/sha1_lookup.h b/src/sha1_lookup.h
index 9a35372..3799620 100644
--- a/src/sha1_lookup.h
+++ b/src/sha1_lookup.h
@@ -15,4 +15,9 @@ int sha1_entry_pos(const void *table,
unsigned lo, unsigned hi, unsigned nr,
const unsigned char *key);
+int sha1_position(const void *table,
+ size_t stride,
+ unsigned lo, unsigned hi,
+ const unsigned char *key);
+
#endif