git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH] interpret_nth_last_branch(): avoid traversing the reflogs twice

From
Junio C Hamano <gitster@pobox.com>
Date
Jan 19, 2009, 08:08 UTC
Message-ID
<7vprijra52.fsf@gitster.siamese.dyndns.org>
In-Reply-To
<alpine.DEB.1.00.0901182152010.3586@pacific.mpi-cbg.de>
Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
Show 14 quoted lines
> On Sat, 17 Jan 2009, Junio C Hamano wrote:
> ...
>> My HEAD reflog is 7MB long with 39000 entries, and among them, 13100
>> entries have "checkout: moving ".
>> 
>> I know I will never want to switch back to the 10000th from the last 
>> branch.  I am quite sure that I would forget which branch I was on after 
>> switching branches three or four times (hence my original hardcoded 
>> limitation of 10 which "should be plenty").  When I know I only have to 
>> keep track of 10 entries, having to keep track of 13100 entries, even if 
>> it is 36kB (it would actually be 260kB in my case) feels there is 
>> something wrong in the design.
>
> Hrm.  So let's leave it as a two-pass thing?
Well, I would rather be in favor of something like this.
-- >8 --
Subject: interpret_nth_last_branch(): avoid traversing the reflog twice

You can have quite a many reflog entries, but you typically won't recall which branch you were on after switching branches for more than several times.

Instead of reading the reflog twice, this reads the branch switching event and keeps the latest 16 (which is an arbitrary limitation that should be plenty) such entry, to switch back to the branch we were recently on.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 sha1_name.c              |   48 +++++++++++++++++++++------------------------
 t/t2012-checkout-last.sh |   44 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 66 insertions(+), 26 deletions(-)
diff --git a/sha1_name.c b/sha1_name.c
index 9e1538e..d6622f2 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -684,10 +684,11 @@ static int get_sha1_oneline(const char *prefix, unsigned char *sha1)
 	return retval;
 }
 
+#define MAX_PREVIOUS_BRANCH 16
+
 struct grab_nth_branch_switch_cbdata {
-	int counting;
-	int nth;
-	struct strbuf *buf;
+	long cnt;
+	struct strbuf buf[MAX_PREVIOUS_BRANCH];
 };
 
 static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
@@ -697,6 +698,7 @@ 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 ");
@@ -711,16 +713,9 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
 	if (target[len] == '\n' && !strncmp(match, target, len))
 		return 0;
 
-	if (cb->counting) {
-		cb->nth++;
-		return 0;
-	}
-
-	if (cb->nth-- <= 0) {
-		strbuf_reset(cb->buf);
-		strbuf_add(cb->buf, match, len);
-		return 1;
-	}
+	nth = cb->cnt++ % MAX_PREVIOUS_BRANCH;
+	strbuf_reset(&cb->buf[nth]);
+	strbuf_add(&cb->buf[nth], match, len);
 	return 0;
 }
 
@@ -737,7 +732,8 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
  */
 int interpret_nth_last_branch(const char *name, struct strbuf *buf)
 {
-	int nth;
+	long nth;
+	int i;
 	struct grab_nth_branch_switch_cbdata cb;
 	const char *brace;
 	char *num_end;
@@ -750,19 +746,19 @@ int interpret_nth_last_branch(const char *name, struct strbuf *buf)
 	nth = strtol(name+3, &num_end, 10);
 	if (num_end != brace)
 		return -1;
-
-	cb.counting = 1;
-	cb.nth = 0;
-	cb.buf = buf;
-	for_each_reflog_ent("HEAD", grab_nth_branch_switch, &cb);
-
-	if (cb.nth < nth)
-		return 0;
-
-	cb.counting = 0;
-	cb.nth -= nth;
-	cb.buf = buf;
+	if (nth <= 0 || MAX_PREVIOUS_BRANCH < nth)
+		return -1;
+	for (i = 0; i < MAX_PREVIOUS_BRANCH; i++)
+		strbuf_init(&cb.buf[i], 20);
+	cb.cnt = 0;
 	for_each_reflog_ent("HEAD", grab_nth_branch_switch, &cb);
+	if (cb.cnt < nth)
+		return -1;
+	i = (cb.cnt + MAX_PREVIOUS_BRANCH - nth) % MAX_PREVIOUS_BRANCH;
+	strbuf_reset(buf);
+	strbuf_add(buf, cb.buf[i].buf, cb.buf[i].len);
+	for (i = 0; i < MAX_PREVIOUS_BRANCH; i++)
+		strbuf_release(&cb.buf[i]);
 
 	return brace-name+1;
 }
diff --git a/t/t2012-checkout-last.sh b/t/t2012-checkout-last.sh
index 320f6eb..87b30a2 100755
--- a/t/t2012-checkout-last.sh
+++ b/t/t2012-checkout-last.sh
@@ -47,4 +47,48 @@ test_expect_success '"checkout -" detaches again' '
 	test_must_fail git symbolic-ref HEAD
 '
 
+test_expect_success 'more switches' '
+	for i in 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
+	do
+		git checkout -b branch$i
+	done
+'
+
+more_switches () {
+	for i in 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
+	do
+		git checkout branch$i
+	done
+}
+
+test_expect_success 'switch to the last' '
+	more_switches &&
+	git checkout @{-1} &&
+	test "z$(git symbolic-ref HEAD)" = "zrefs/heads/branch2"
+'
+
+test_expect_success 'switch to second from the last' '
+	more_switches &&
+	git checkout @{-2} &&
+	test "z$(git symbolic-ref HEAD)" = "zrefs/heads/branch3"
+'
+
+test_expect_success 'switch to third from the last' '
+	more_switches &&
+	git checkout @{-3} &&
+	test "z$(git symbolic-ref HEAD)" = "zrefs/heads/branch4"
+'
+
+test_expect_success 'switch to fourth from the last' '
+	more_switches &&
+	git checkout @{-4} &&
+	test "z$(git symbolic-ref HEAD)" = "zrefs/heads/branch5"
+'
+
+test_expect_success 'switch to twelfth from the last' '
+	more_switches &&
+	git checkout @{-12} &&
+	test "z$(git symbolic-ref HEAD)" = "zrefs/heads/branch13"
+'
+
 test_done

-- 
1.6.1.245.gdd9f9
Previous: Johannes SchindelinNext: Junio C Hamano
Message 35 of 56 in “N-th last checked out branch”
  1. 0/6 N-th last checked out branchThomas Rast, Jan 17, 2009
  2. 1/6 reflog: refactor parsing and checkingThomas Rast, Jan 17, 2009
  3. 2/6 reflog: refactor log open+mmapThomas Rast, Jan 17, 2009
  4. 3/6 reflog: make for_each_reflog_ent use mmapThomas Rast, Jan 17, 2009
  5. 4/6 reflog: add backwards iteratorThomas Rast, Jan 17, 2009
  6. 5/6 sha1_name: implement @{-N} syntax for N-th last checked outThomas Rast, Jan 17, 2009
  7. 6/6 checkout: implement '@{-N}' and '-' special abbreviationsThomas Rast, Jan 17, 2009
  8. Johannes SchindelinJan 17, 2009
  9. Johannes SchindelinJan 17, 2009
  10. Johannes SchindelinJan 17, 2009
  11. Thomas RastJan 17, 2009
  12. 1/2 sha1_name: implement @{-N} syntax for N-th last checked outThomas Rast, Jan 17, 2009
  13. 2/2 checkout: implement '@{-N}' and '-' special abbreviationsThomas Rast, Jan 17, 2009
  14. interpret_nth_last_branch(): avoid traversing the reflogs twiceJohannes Schindelin, Jan 17, 2009
  15. 0/5 N-th last checked out branchThomas Rast, Jan 17, 2009
  16. 1/5 checkout: implement "@{-N}" shortcut name for N-th last branchThomas Rast, Jan 17, 2009
  17. 2/5 sha1_name: tweak @{-N} lookupThomas Rast, Jan 17, 2009
  18. 3/5 sha1_name: support @{-N} syntax in get_sha1()Thomas Rast, Jan 17, 2009
  19. 4/5 checkout: implement "-" abbreviation, add docs and testsThomas Rast, Jan 17, 2009
  20. 5/5 interpret_nth_last_branch(): avoid traversing the reflogs twiceThomas Rast, Jan 17, 2009
  21. 6/5 Fix parsing of @{-1}@{1}Johannes Schindelin, Jan 17, 2009
  22. Junio C HamanoJan 17, 2009
  23. Johannes SchindelinJan 17, 2009
  24. Junio C HamanoJan 17, 2009
  25. Johannes SchindelinJan 17, 2009
  26. Junio C HamanoJan 17, 2009
  27. Junio C HamanoJan 18, 2009
  28. Johannes SchindelinJan 17, 2009
  29. Junio C HamanoJan 17, 2009
  30. Johannes SchindelinJan 17, 2009
  31. Junio C HamanoJan 18, 2009
  32. Johannes SchindelinJan 18, 2009
  33. Junio C HamanoJan 18, 2009
  34. Johannes SchindelinJan 18, 2009
  35. Junio C HamanoJan 19, 2009
  36. Junio C HamanoJan 19, 2009
  37. Johannes SchindelinJan 19, 2009
  38. Thomas RastJan 20, 2009
  39. Johannes SchindelinJan 20, 2009
  40. Thomas RastJan 20, 2009
  41. interpret_nth_last_branch(): plug small memleakJunio C Hamano, Jan 20, 2009
  42. Johannes SchindelinJan 20, 2009
  43. Introduce for_each_recent_reflog_ent().Junio C Hamano, Jan 20, 2009
  44. Johannes SchindelinJan 20, 2009
  45. Junio C HamanoJan 20, 2009
  46. Fix invalid memory accessJohannes Schindelin, Jan 21, 2009
  47. Junio C HamanoJan 21, 2009
  48. Thomas RastJan 21, 2009
  49. Junio C HamanoJan 21, 2009
  50. Johannes SchindelinJan 21, 2009
  51. Thomas RastJan 24, 2009
  52. t1505: remove debugging cruftThomas Rast, Jan 24, 2009
  53. Junio C HamanoJan 25, 2009
  54. Johannes SchindelinJan 21, 2009
  55. @{-<n>}: avoid crash with corrupt reflogJohannes Schindelin, Jan 19, 2009
  56. Johannes SchindelinJan 19, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.