{"thread":{"id":"33109","subject":"[PATCH 3/3] reflog: add for_each_reflog_ent_reverse() API","startedAt":"2013-03-08T21:53:41Z","lastAt":"2013-03-08T21:53:44Z","messageCount":4,"participants":["Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"210857","messageId":"1362779624-15513-1-git-send-email-gitster@pobox.com","threadId":"33109","inReplyTo":null,"subject":"[PATCH 0/3] Enumerating reflog entries in a wrong order","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-08T21:53:41Z","receivedAt":"2013-03-08T21:53:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The for_each_reflog_ent() function yields reflog entries from the\noldest to newer, and is inefficient when we know what we are looking\nfor are near the newest end (e.g. \"find the nth newest reflog entry\nthat matches 'checkout: moving from X to Y'\").  To optimize for the\ncommon case, we introduced for_each_recent_reflog_ent() to scan only\nthe newest part (i.e. tail) of the reflog file, but it is difficult\nto use this function correctly.\n\nJust bite the bullet and stop working around the API that reads the\nfile in a wrong order.  The new for_each_reflog_ent_reverse()\nfunction gives us reflog entries from the newest to older.\n\nJunio C Hamano (3):\n  for_each_reflog_ent(): extract a helper to process a single entry\n  for_each_recent_reflog_ent(): simplify opening of a reflog file\n  reflog: add for_each_reflog_ent_reverse() API\n\n refs.c      | 161 +++++++++++++++++++++++++++++++++++++++++++-----------------\n refs.h      |   2 +-\n sha1_name.c |  48 +++++++-----------\n 3 files changed, 134 insertions(+), 77 deletions(-)\n\n-- \n1.8.2-rc3-189-g94c4d42\n"},{"id":"210858","messageId":"1362779624-15513-2-git-send-email-gitster@pobox.com","threadId":"33109","inReplyTo":"1362779624-15513-1-git-send-email-gitster@pobox.com","subject":"[PATCH 1/3] for_each_reflog_ent(): extract a helper to process a single entry","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-08T21:53:42Z","receivedAt":"2013-03-08T21:53:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Split the logic that takes a single line of reflog entry in a strbuf\nparses it and calls the callback function out of the loop into a\nseparate helper function.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n refs.c | 59 ++++++++++++++++++++++++++++++-----------------------------\n 1 file changed, 30 insertions(+), 29 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex da74a2b..9f702a7 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -2290,6 +2290,34 @@ int read_ref_at(const char *refname, unsigned long at_time, int cnt,\n \treturn 1;\n }\n \n+static int show_one_reflog_ent(struct strbuf *sb, each_reflog_ent_fn fn, void *cb_data)\n+{\n+\tunsigned char osha1[20], nsha1[20];\n+\tchar *email_end, *message;\n+\tunsigned long timestamp;\n+\tint tz;\n+\n+\t/* old SP new SP name <email> SP time TAB msg LF */\n+\tif (sb->len < 83 || sb->buf[sb->len - 1] != '\\n' ||\n+\t    get_sha1_hex(sb->buf, osha1) || sb->buf[40] != ' ' ||\n+\t    get_sha1_hex(sb->buf + 41, nsha1) || sb->buf[81] != ' ' ||\n+\t    !(email_end = strchr(sb->buf + 82, '>')) ||\n+\t    email_end[1] != ' ' ||\n+\t    !(timestamp = strtoul(email_end + 2, &message, 10)) ||\n+\t    !message || message[0] != ' ' ||\n+\t    (message[1] != '+' && message[1] != '-') ||\n+\t    !isdigit(message[2]) || !isdigit(message[3]) ||\n+\t    !isdigit(message[4]) || !isdigit(message[5]))\n+\t\treturn 0; /* corrupt? */\n+\temail_end[1] = '\\0';\n+\ttz = strtol(message + 1, NULL, 10);\n+\tif (message[6] != '\\t')\n+\t\tmessage += 6;\n+\telse\n+\t\tmessage += 7;\n+\treturn fn(osha1, nsha1, sb->buf + 82, timestamp, tz, message, cb_data);\n+}\n+\n int for_each_recent_reflog_ent(const char *refname, each_reflog_ent_fn fn, long ofs, void *cb_data)\n {\n \tconst char *logfile;\n@@ -2314,35 +2342,8 @@ int for_each_recent_reflog_ent(const char *refname, each_reflog_ent_fn fn, long\n \t\t}\n \t}\n \n-\twhile (!strbuf_getwholeline(&sb, logfp, '\\n')) {\n-\t\tunsigned char osha1[20], nsha1[20];\n-\t\tchar *email_end, *message;\n-\t\tunsigned long timestamp;\n-\t\tint tz;\n-\n-\t\t/* old SP new SP name <email> SP time TAB msg LF */\n-\t\tif (sb.len < 83 || sb.buf[sb.len - 1] != '\\n' ||\n-\t\t    get_sha1_hex(sb.buf, osha1) || sb.buf[40] != ' ' ||\n-\t\t    get_sha1_hex(sb.buf + 41, nsha1) || sb.buf[81] != ' ' ||\n-\t\t    !(email_end = strchr(sb.buf + 82, '>')) ||\n-\t\t    email_end[1] != ' ' ||\n-\t\t    !(timestamp = strtoul(email_end + 2, &message, 10)) ||\n-\t\t    !message || message[0] != ' ' ||\n-\t\t    (message[1] != '+' && message[1] != '-') ||\n-\t\t    !isdigit(message[2]) || !isdigit(message[3]) ||\n-\t\t    !isdigit(message[4]) || !isdigit(message[5]))\n-\t\t\tcontinue; /* corrupt? */\n-\t\temail_end[1] = '\\0';\n-\t\ttz = strtol(message + 1, NULL, 10);\n-\t\tif (message[6] != '\\t')\n-\t\t\tmessage += 6;\n-\t\telse\n-\t\t\tmessage += 7;\n-\t\tret = fn(osha1, nsha1, sb.buf + 82, timestamp, tz, message,\n-\t\t\t cb_data);\n-\t\tif (ret)\n-\t\t\tbreak;\n-\t}\n+\twhile (!ret && !strbuf_getwholeline(&sb, logfp, '\\n'))\n+\t\tret = show_one_reflog_ent(&sb, fn, cb_data);\n \tfclose(logfp);\n \tstrbuf_release(&sb);\n \treturn ret;\n-- \n1.8.2-rc3-189-g94c4d42\n"},{"id":"210859","messageId":"1362779624-15513-3-git-send-email-gitster@pobox.com","threadId":"33109","inReplyTo":"1362779624-15513-1-git-send-email-gitster@pobox.com","subject":"[PATCH 2/3] for_each_recent_reflog_ent(): simplify opening of a reflog file","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-08T21:53:43Z","receivedAt":"2013-03-08T21:53:43Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"There is no reason to use a temporary variable logfile.\n---\n refs.c | 4 +---\n 1 file changed, 1 insertion(+), 3 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 9f702a7..e302521 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -2320,13 +2320,11 @@ static int show_one_reflog_ent(struct strbuf *sb, each_reflog_ent_fn fn, void *c\n \n int for_each_recent_reflog_ent(const char *refname, each_reflog_ent_fn fn, long ofs, void *cb_data)\n {\n-\tconst char *logfile;\n \tFILE *logfp;\n \tstruct strbuf sb = STRBUF_INIT;\n \tint ret = 0;\n \n-\tlogfile = git_path(\"logs/%s\", refname);\n-\tlogfp = fopen(logfile, \"r\");\n+\tlogfp = fopen(git_path(\"logs/%s\", refname), \"r\");\n \tif (!logfp)\n \t\treturn -1;\n \n-- \n1.8.2-rc3-189-g94c4d42\n"},{"id":"210856","messageId":"1362779624-15513-4-git-send-email-gitster@pobox.com","threadId":"33109","inReplyTo":"1362779624-15513-1-git-send-email-gitster@pobox.com","subject":"[PATCH 3/3] reflog: add for_each_reflog_ent_reverse() API","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-08T21:53:44Z","receivedAt":"2013-03-08T21:53:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"git checkout -\" is a short-hand for \"git checkout @{-1}\" and the\n\"@{nth}\" notation for a negative number is to find nth previous\ncheckout in the reflog of the HEAD to determine the name of the\nbranch the user was on.  We would want to find the nth most recent\nreflog entry that matches \"checkout: moving from X to Y\" for this.\n\nUnfortunately, reflog is implemented as an append-only file, and the\nAPI to iterate over its entries, for_each_reflog_ent(), reads the\nfile in order, giving the entries from oldest to newer.  For the\npurpose of finding nth most recent one, this API makes us to record\nthe last n entries in a rotating buffer and give the result out only\nafter we read everything.  To optimize for a common case of finding\nthe nth most recent one for a small value of n, we also have a side\nAPI for_each_recent_reflog_ent() that starts reading near the end of\nthe file, but it still reads the entries in the \"wrong\" order.  The\nimplementation of understanding @{-1} uses this interface.\n\nThis all becomes unnecessary if we had an API to let us iterate over\nreflog entries in the reverse order, from the newest to older.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n refs.c      | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++----------\n refs.h      |   2 +-\n sha1_name.c |  48 +++++++++++-----------------\n 3 files changed, 105 insertions(+), 47 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex e302521..8e24060 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -2318,30 +2318,89 @@ static int show_one_reflog_ent(struct strbuf *sb, each_reflog_ent_fn fn, void *c\n \treturn fn(osha1, nsha1, sb->buf + 82, timestamp, tz, message, cb_data);\n }\n \n-int for_each_recent_reflog_ent(const char *refname, each_reflog_ent_fn fn, long ofs, void *cb_data)\n+static char *find_beginning_of_line(char *bob, char *scan)\n+{\n+\twhile (bob < scan && *(--scan) != '\\n')\n+\t\t; /* keep scanning backwards */\n+\t/*\n+\t * Return either beginning of the buffer, or LF at the end of\n+\t * the previous line.\n+\t */\n+\treturn scan;\n+}\n+\n+int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn, void *cb_data)\n {\n-\tFILE *logfp;\n \tstruct strbuf sb = STRBUF_INIT;\n-\tint ret = 0;\n+\tFILE *logfp;\n+\tlong pos;\n+\tint ret = 0, at_tail = 1;\n \n \tlogfp = fopen(git_path(\"logs/%s\", refname), \"r\");\n \tif (!logfp)\n \t\treturn -1;\n \n-\tif (ofs) {\n-\t\tstruct stat statbuf;\n-\t\tif (fstat(fileno(logfp), &statbuf) ||\n-\t\t    statbuf.st_size < ofs ||\n-\t\t    fseek(logfp, -ofs, SEEK_END) ||\n-\t\t    strbuf_getwholeline(&sb, logfp, '\\n')) {\n-\t\t\tfclose(logfp);\n-\t\t\tstrbuf_release(&sb);\n-\t\t\treturn -1;\n+\t/* Jump to the end */\n+\tif (fseek(logfp, 0, SEEK_END) < 0)\n+\t\treturn error(\"cannot seek back reflog for %s: %s\",\n+\t\t\t     refname, strerror(errno));\n+\tpos = ftell(logfp);\n+\twhile (!ret && 0 < pos) {\n+\t\tint cnt;\n+\t\tsize_t nread;\n+\t\tchar buf[BUFSIZ];\n+\t\tchar *endp, *scanp;\n+\n+\t\t/* Fill next block from the end */\n+\t\tcnt = (sizeof(buf) < pos) ? sizeof(buf) : pos;\n+\t\tif (fseek(logfp, pos - cnt, SEEK_SET))\n+\t\t\treturn error(\"cannot seek back reflog for %s: %s\",\n+\t\t\t\t     refname, strerror(errno));\n+\t\tnread = fread(buf, cnt, 1, logfp);\n+\t\tif (nread < 0)\n+\t\t\treturn error(\"cannot read %d bytes from reflog for %s: %s\",\n+\t\t\t\t     cnt, refname, strerror(errno));\n+\t\tpos -= cnt;\n+\n+\t\tscanp = endp = buf + cnt;\n+\t\tif (at_tail && scanp[-1] == '\\n')\n+\t\t\t/* Looking at the final LF at the end of the file */\n+\t\t\tscanp--;\n+\t\tat_tail = 0;\n+\n+\t\twhile (buf < scanp) {\n+\t\t\t/*\n+\t\t\t * terminating LF of the previous line, or the beginning\n+\t\t\t * of the buffer.\n+\t\t\t */\n+\t\t\tchar *bp;\n+\n+\t\t\tbp = find_beginning_of_line(buf, scanp);\n+\n+\t\t\tif (*bp != '\\n') {\n+\t\t\t\tstrbuf_splice(&sb, 0, 0, buf, endp - buf);\n+\t\t\t\tif (pos)\n+\t\t\t\t\tbreak; /* need to fill another block */\n+\t\t\t\tscanp = buf - 1; /* leave loop */\n+\t\t\t} else {\n+\t\t\t\t/*\n+\t\t\t\t * (bp + 1) thru endp is the beginning of the\n+\t\t\t\t * current line we have in sb\n+\t\t\t\t */\n+\t\t\t\tstrbuf_splice(&sb, 0, 0, bp + 1, endp - (bp + 1));\n+\t\t\t\tscanp = bp;\n+\t\t\t\tendp = bp + 1;\n+\t\t\t}\n+\t\t\tret = show_one_reflog_ent(&sb, fn, cb_data);\n+\t\t\tstrbuf_reset(&sb);\n+\t\t\tif (ret)\n+\t\t\t\tbreak;\n \t\t}\n-\t}\n \n-\twhile (!ret && !strbuf_getwholeline(&sb, logfp, '\\n'))\n+\t}\n+\tif (!ret && sb.len)\n \t\tret = show_one_reflog_ent(&sb, fn, cb_data);\n+\n \tfclose(logfp);\n \tstrbuf_release(&sb);\n \treturn ret;\n@@ -2349,9 +2408,20 @@ int for_each_recent_reflog_ent(const char *refname, each_reflog_ent_fn fn, long\n \n int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_data)\n {\n-\treturn for_each_recent_reflog_ent(refname, fn, 0, cb_data);\n-}\n+\tFILE *logfp;\n+\tstruct strbuf sb = STRBUF_INIT;\n+\tint ret = 0;\n+\n+\tlogfp = fopen(git_path(\"logs/%s\", refname), \"r\");\n+\tif (!logfp)\n+\t\treturn -1;\n \n+\twhile (!ret && !strbuf_getwholeline(&sb, logfp, '\\n'))\n+\t\tret = show_one_reflog_ent(&sb, fn, cb_data);\n+\tfclose(logfp);\n+\tstrbuf_release(&sb);\n+\treturn ret;\n+}\n /*\n  * Call fn for each reflog in the namespace indicated by name.  name\n  * must be empty or end with '/'.  Name will be used as a scratch\ndiff --git a/refs.h b/refs.h\nindex d6c2fe2..a62b9db 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -103,7 +103,7 @@ extern int read_ref_at(const char *refname, unsigned long at_time, int cnt,\n /* iterate over reflog entries */\n typedef int each_reflog_ent_fn(unsigned char *osha1, unsigned char *nsha1, const char *, unsigned long, int, const char *, void *);\n int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_data);\n-int for_each_recent_reflog_ent(const char *refname, each_reflog_ent_fn fn, long, void *cb_data);\n+int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn, void *cb_data);\n \n /*\n  * Calls the specified function for each reflog file until it returns nonzero,\ndiff --git a/sha1_name.c b/sha1_name.c\nindex 95003c7..635cd13 100644\n--- a/sha1_name.c\n+++ b/sha1_name.c\n@@ -856,8 +856,8 @@ static int get_sha1_oneline(const char *prefix, unsigned char *sha1,\n }\n \n struct grab_nth_branch_switch_cbdata {\n-\tlong cnt, alloc;\n-\tstruct strbuf *buf;\n+\tint remaining;\n+\tstruct strbuf buf;\n };\n \n static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,\n@@ -867,7 +867,6 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,\n \tstruct grab_nth_branch_switch_cbdata *cb = cb_data;\n \tconst char *match = NULL, *target = NULL;\n \tsize_t len;\n-\tint nth;\n \n \tif (!prefixcmp(message, \"checkout: moving from \")) {\n \t\tmatch = message + strlen(\"checkout: moving from \");\n@@ -876,11 +875,12 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,\n \n \tif (!match || !target)\n \t\treturn 0;\n-\n-\tlen = target - match;\n-\tnth = cb->cnt++ % cb->alloc;\n-\tstrbuf_reset(&cb->buf[nth]);\n-\tstrbuf_add(&cb->buf[nth], match, len);\n+\tif (--(cb->remaining) == 0) {\n+\t\tlen = target - match;\n+\t\tstrbuf_reset(&cb->buf);\n+\t\tstrbuf_add(&cb->buf, match, len);\n+\t\treturn 1; /* we are done */\n+\t}\n \treturn 0;\n }\n \n@@ -891,7 +891,7 @@ static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,\n static int interpret_nth_prior_checkout(const char *name, struct strbuf *buf)\n {\n \tlong nth;\n-\tint i, retval;\n+\tint retval;\n \tstruct grab_nth_branch_switch_cbdata cb;\n \tconst char *brace;\n \tchar *num_end;\n@@ -901,34 +901,22 @@ static int interpret_nth_prior_checkout(const char *name, struct strbuf *buf)\n \tbrace = strchr(name, '}');\n \tif (!brace)\n \t\treturn -1;\n-\tnth = strtol(name+3, &num_end, 10);\n+\tnth = strtol(name + 3, &num_end, 10);\n \tif (num_end != brace)\n \t\treturn -1;\n \tif (nth <= 0)\n \t\treturn -1;\n-\tcb.alloc = nth;\n-\tcb.buf = xmalloc(nth * sizeof(struct strbuf));\n-\tfor (i = 0; i < nth; i++)\n-\t\tstrbuf_init(&cb.buf[i], 20);\n-\tcb.cnt = 0;\n+\tcb.remaining = nth;\n+\tstrbuf_init(&cb.buf, 20);\n+\n \tretval = 0;\n-\tfor_each_recent_reflog_ent(\"HEAD\", grab_nth_branch_switch, 40960, &cb);\n-\tif (cb.cnt < nth) {\n-\t\tcb.cnt = 0;\n-\t\tfor_each_reflog_ent(\"HEAD\", grab_nth_branch_switch, &cb);\n+\tif (0 < for_each_reflog_ent_reverse(\"HEAD\", grab_nth_branch_switch, &cb)) {\n+\t\tstrbuf_reset(buf);\n+\t\tstrbuf_add(buf, cb.buf.buf, cb.buf.len);\n+\t\tretval = brace - name + 1;\n \t}\n-\tif (cb.cnt < nth)\n-\t\tgoto release_return;\n-\ti = cb.cnt % nth;\n-\tstrbuf_reset(buf);\n-\tstrbuf_add(buf, cb.buf[i].buf, cb.buf[i].len);\n-\tretval = brace-name+1;\n-\n-release_return:\n-\tfor (i = 0; i < nth; i++)\n-\t\tstrbuf_release(&cb.buf[i]);\n-\tfree(cb.buf);\n \n+\tstrbuf_release(&cb.buf);\n \treturn retval;\n }\n \n-- \n1.8.2-rc3-189-g94c4d42\n"}]}