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

[PATCH v3 02/21] prefix_ref_iterator: break when we leave the prefix

From
Michael Haggerty <mhagger@alum.mit.edu>
Date
Sep 25, 2017, 07:59 UTC
Message-ID
<ff88edea0574e10597d86e3fd2e6390994dad277.1506325610.git.mhagger@alum.mit.edu>
In-Reply-To
<cover.1506325610.git.mhagger@alum.mit.edu>
From: Jeff King <peff@peff.net>

If the underlying iterator is ordered, then `prefix_ref_iterator` can stop as soon as it sees a refname that comes after the prefix. This will rarely make a big difference now, because `ref_cache_iterator` only iterates over the directory containing the prefix (and usually the prefix will span a whole directory anyway). But if *hint, hint* a future reference backend doesn't itself know where to stop the iteration, then this optimization will be a big win.

Note that there is no guarantee that the underlying iterator doesn't include output preceding the prefix, so we have to skip over any unwanted references before we get to the ones that we want.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs/iterator.c | 32 +++++++++++++++++++++++++++++++-
 1 file changed, 31 insertions(+), 1 deletion(-)
diff --git a/refs/iterator.c b/refs/iterator.c
index c475360f0a..bd35da4e62 100644
--- a/refs/iterator.c
+++ b/refs/iterator.c
@@ -287,6 +287,20 @@ struct prefix_ref_iterator {
 	int trim;
 };
 
+/* Return -1, 0, 1 if refname is before, inside, or after the prefix. */
+static int compare_prefix(const char *refname, const char *prefix)
+{
+	while (*prefix) {
+		if (*refname != *prefix)
+			return ((unsigned char)*refname < (unsigned char)*prefix) ? -1 : +1;
+
+		refname++;
+		prefix++;
+	}
+
+	return 0;
+}
+
 static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)
 {
 	struct prefix_ref_iterator *iter =
@@ -294,9 +308,25 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator)
 	int ok;
 
 	while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) {
-		if (!starts_with(iter->iter0->refname, iter->prefix))
+		int cmp = compare_prefix(iter->iter0->refname, iter->prefix);
+
+		if (cmp < 0)
 			continue;
 
+		if (cmp > 0) {
+			/*
+			 * If the source iterator is ordered, then we
+			 * can stop the iteration as soon as we see a
+			 * refname that comes after the prefix:
+			 */
+			if (iter->iter0->ordered) {
+				ok = ref_iterator_abort(iter->iter0);
+				break;
+			} else {
+				continue;
+			}
+		}
+
 		if (iter->trim) {
 			/*
 			 * It is nonsense to trim off characters that

-- 
2.14.1
Previous: Michael HaggertyNext: Michael Haggerty
Message 3 of 24 in “Read `packed-refs` using mmap()”
  1. 00/21 Read `packed-refs` using mmap()Michael Haggerty, Sep 25, 2017
  2. 01/21 ref_iterator: keep track of whether the iterator output is orderedMichael Haggerty, Sep 25, 2017
  3. 02/21 prefix_ref_iterator: break when we leave the prefixMichael Haggerty, Sep 25, 2017
  4. 03/21 packed_ref_cache: add a backlink to the associated `packed_ref_store`Michael Haggerty, Sep 25, 2017
  5. 04/21 die_unterminated_line(), die_invalid_line(): new functionsMichael Haggerty, Sep 25, 2017
  6. 05/21 read_packed_refs(): use mmap to read the `packed-refs` fileMichael Haggerty, Sep 25, 2017
  7. 06/21 read_packed_refs(): only check for a header at the top of the fileMichael Haggerty, Sep 25, 2017
  8. 07/21 read_packed_refs(): make parsing of the header line more robustMichael Haggerty, Sep 25, 2017
  9. 09/21 packed_ref_cache: remember the file-wide peeling stateMichael Haggerty, Sep 25, 2017
  10. 08/21 read_packed_refs(): read references with minimal copyingMichael Haggerty, Sep 25, 2017
  11. 10/21 mmapped_ref_iterator: add iterator over a packed-refs fileMichael Haggerty, Sep 25, 2017
  12. 12/21 packed-backend.c: reorder some definitionsMichael Haggerty, Sep 25, 2017
  13. 13/21 packed_ref_cache: keep the `packed-refs` file mmapped if possibleMichael Haggerty, Sep 25, 2017
  14. 14/21 read_packed_refs(): ensure that references are ordered when readMichael Haggerty, Sep 25, 2017
  15. 11/21 mmapped_ref_iterator_advance(): no peeled value for broken refsMichael Haggerty, Sep 25, 2017
  16. 15/21 packed_ref_iterator_begin(): iterate using `mmapped_ref_iterator`Michael Haggerty, Sep 25, 2017
  17. 16/21 packed_read_raw_ref(): read the reference from the mmapped bufferMichael Haggerty, Sep 25, 2017
  18. 17/21 ref_store: implement `refs_peel_ref()` genericallyMichael Haggerty, Sep 25, 2017
  19. 18/21 packed_ref_store: get rid of the `ref_cache` entirelyMichael Haggerty, Sep 25, 2017
  20. 20/21 mmapped_ref_iterator: inline into `packed_ref_iterator`Michael Haggerty, Sep 25, 2017
  21. 19/21 ref_cache: remove support for storing peeled valuesMichael Haggerty, Sep 25, 2017
  22. 21/21 packed-backend.c: rename a bunch of things and update commentsMichael Haggerty, Sep 25, 2017
  23. Jeff KingSep 25, 2017
  24. Junio C HamanoSep 29, 2017

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.