reflog: add for_each_reflog_ent_reverse() API

"git checkout -" is a short-hand for "git checkout @{-1}" and the
"@{nth}" notation for a negative number is to find nth previous
checkout in the reflog of the HEAD to determine the name of the
branch the user was on.  We would want to find the nth most recent
reflog entry that matches "checkout: moving from X to Y" for this.

Unfortunately, reflog is implemented as an append-only file, and the
API to iterate over its entries, for_each_reflog_ent(), reads the
file in order, giving the entries from the oldest to newer.  For the
purpose of finding nth most recent one, this API forces us to record
the last n entries in a rotating buffer and give the result out only
after we read everything.  To optimize for a common case of finding
the nth most recent one for a small value of n, we also have a side
API for_each_recent_reflog_ent() that starts reading near the end of
the file, but it still has to read the entries in the "wrong" order.
The implementation of understanding @{-1} uses this interface.

This all becomes unnecessary if we add an API to let us iterate over
reflog entries in the reverse order, from the newest to older.

Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 18 insertions, 30 deletions

diff --git a/sha1_name.c b/sha1_name.c
index 95003c7..635cd13 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -856,8 +856,8 @@ static int get_sha1_oneline(const char *prefix, unsigned char *sha1,
 }
 
 struct grab_nth_branch_switch_cbdata {
-	long cnt, alloc;
-	struct strbuf *buf;
+	int remaining;
+	struct strbuf buf;
 };
 
 static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
@@ -867,7 +867,6 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
 	struct grab_nth_branch_switch_cbdata *cb = cb_data;
 	const char *match = NULL, *target = NULL;
 	size_t len;
-	int nth;
 
 	if (!prefixcmp(message, "checkout: moving from ")) {
 		match = message + strlen("checkout: moving from ");
@@ -876,11 +875,12 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
 
 	if (!match || !target)
 		return 0;
-
-	len = target - match;
-	nth = cb->cnt++ % cb->alloc;
-	strbuf_reset(&cb->buf[nth]);
-	strbuf_add(&cb->buf[nth], match, len);
+	if (--(cb->remaining) == 0) {
+		len = target - match;
+		strbuf_reset(&cb->buf);
+		strbuf_add(&cb->buf, match, len);
+		return 1; /* we are done */
+	}
 	return 0;
 }
 
@@ -891,7 +891,7 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
 static int interpret_nth_prior_checkout(const char *name, struct strbuf *buf)
 {
 	long nth;
-	int i, retval;
+	int retval;
 	struct grab_nth_branch_switch_cbdata cb;
 	const char *brace;
 	char *num_end;
@@ -901,34 +901,22 @@ static int interpret_nth_prior_checkout(const char *name, struct strbuf *buf)
 	brace = strchr(name, '}');
 	if (!brace)
 		return -1;
-	nth = strtol(name+3, &num_end, 10);
+	nth = strtol(name + 3, &num_end, 10);
 	if (num_end != brace)
 		return -1;
 	if (nth <= 0)
 		return -1;
-	cb.alloc = nth;
-	cb.buf = xmalloc(nth * sizeof(struct strbuf));
-	for (i = 0; i < nth; i++)
-		strbuf_init(&cb.buf[i], 20);
-	cb.cnt = 0;
+	cb.remaining = nth;
+	strbuf_init(&cb.buf, 20);
+
 	retval = 0;
-	for_each_recent_reflog_ent("HEAD", grab_nth_branch_switch, 40960, &cb);
-	if (cb.cnt < nth) {
-		cb.cnt = 0;
-		for_each_reflog_ent("HEAD", grab_nth_branch_switch, &cb);
+	if (0 < for_each_reflog_ent_reverse("HEAD", grab_nth_branch_switch, &cb)) {
+		strbuf_reset(buf);
+		strbuf_add(buf, cb.buf.buf, cb.buf.len);
+		retval = brace - name + 1;
 	}
-	if (cb.cnt < nth)
-		goto release_return;
-	i = cb.cnt % nth;
-	strbuf_reset(buf);
-	strbuf_add(buf, cb.buf[i].buf, cb.buf[i].len);
-	retval = brace-name+1;
-
-release_return:
-	for (i = 0; i < nth; i++)
-		strbuf_release(&cb.buf[i]);
-	free(cb.buf);
 
+	strbuf_release(&cb.buf);
 	return retval;
 }