[PATCH] commit.c: use the generic "sha1_pos" function for lookup sha1

Refactor binary search in "commit_graft_pos" function: use
generic "sha1_pos" function.

Signed-off-by: Dmitry S. Dolzhenko <redacted>
---
 commit.c | 24 +++++++++---------------
 1 file changed, 9 insertions(+), 15 deletions(-)

diff --git a/commit.c b/commit.c
index 6bf4fe0..8edaeb7 100644
--- a/commit.c
+++ b/commit.c

@@ -10,6 +10,7 @@
 #include "mergesort.h"
 #include "commit-slab.h"
 #include "prio-queue.h"
+#include "sha1-lookup.h"
  static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
 @@ -114,23 +115,16 @@ static unsigned long parse_commit_date(const char *buf, const char *tail)
 static struct commit_graft **commit_graft;
 static int commit_graft_alloc, commit_graft_nr;
 +static const unsigned char *commit_graft_sha1_access(size_t index, void *table)
+{
+	struct commit_graft **commit_graft_table = table;
+	return commit_graft_table[index]->sha1;
+}
+
 static int commit_graft_pos(const unsigned char *sha1)
 {
-	int lo, hi;
-	lo = 0;
-	hi = commit_graft_nr;
-	while (lo < hi) {
-		int mi = (lo + hi) / 2;
-		struct commit_graft *graft = commit_graft[mi];
-		int cmp = hashcmp(sha1, graft->sha1);
-		if (!cmp)
-			return mi;
-		if (cmp < 0)
-			hi = mi;
-		else
-			lo = mi + 1;
-	}
-	return -lo - 1;
+	return sha1_pos(sha1, commit_graft, commit_graft_nr,
+			   commit_graft_sha1_access);
 }
  int register_commit_graft(struct commit_graft *graft, int ignore_dups)

-- 
1.8.5.3

On Wed, Feb 26, 2014 at 02:07:47PM +0400, Dmitry S. Dolzhenko wrote:

Refactor binary search in "commit_graft_pos" function: use
generic "sha1_pos" function.

Sounds sensible.

A few administrative points for your patch:

  - we usually try to send patches inline, rather than as attachments.
    It almost looks like your mailer or a server on the path converted
    your mail to a multipart/mixed and stuck a useless empty attachment
    on the end.

  - Your patch did not apply for me, nor to the blobs mentioned in its
    header. Did you modify it after it was generated? I think this part
    in particular looks suspicious:

There are 3 context lines above, but only one below?

 @@ -114,23 +115,16 @@ static unsigned long parse_commit_date(const char *buf, const char *tail)
 static struct commit_graft **commit_graft;
 static int commit_graft_alloc, commit_graft_nr;
 +static const unsigned char *commit_graft_sha1_access(size_t index, void *table)
+{
+	struct commit_graft **commit_graft_table = table;
+	return commit_graft_table[index]->sha1;
+}
+

And here we have only two context lines, and the first addition line is
indented (making it look like a context line).

 static int commit_graft_pos(const unsigned char *sha1)
 {
-	int lo, hi;
-	lo = 0;
-	hi = commit_graft_nr;
-	while (lo < hi) {
-		int mi = (lo + hi) / 2;
-		struct commit_graft *graft = commit_graft[mi];
-		int cmp = hashcmp(sha1, graft->sha1);
-		if (!cmp)
-			return mi;
-		if (cmp < 0)
-			hi = mi;
-		else
-			lo = mi + 1;
-	}
-	return -lo - 1;
+	return sha1_pos(sha1, commit_graft, commit_graft_nr,
+			   commit_graft_sha1_access);

The patch itself looks correct.

-Peff

On Wed, Feb 26, 2014 at 5:07 PM, Dmitry S. Dolzhenko
[off-list ref] wrote:

Refactor binary search in "commit_graft_pos" function: use
generic "sha1_pos" function.

For fun, try to break your changes deliberately then run "make test"
and see if the failed tests can lead you back to this function. I hear
some people gather in irc. I think they could help you faster when you
need to track this code. Else get support from this mailing list. If
the test suite does not detect it at all, you can add new tests to
cover it.
-- 
Duy

Thank you for your remarks.  I'll try to fix my patch and send it again.