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

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

From
Stefan Beller <sbeller@google.com>
Date
Sep 21, 2017, 17:29 UTC
Message-ID
<CAGZ79kZ5xcw3hw_aEp2ggLbC8AQm8DwpqK3+i5UO7s+aGzgXjQ@mail.gmail.com>
In-Reply-To
<20170921045932.b5y33fm7gao27ium@sigill.intra.peff.net>
On Wed, Sep 20, 2017 at 9:59 PM, Jeff King <peff@peff.net> wrote:
Show 7 quoted lines
>> But this compare function is not to order by the natural encoding order,
>> but it's used to detect the '0' at the end of prefix, which orders
>> before *any* unsigned char.
>
> It's not just detecting the "0". We care about the ordering overall (so
> that "refs/foo" comes after "refs/bar", and we know that "refs/bar/baz"
> cannot come after "refs/foo", and we can stop iterating).

refs/{foo,bar,bar/baz} is all ASCII, such that the ordering by byte value and byte position (2nd order) orders 'correctly'. correct in the sense as Git expects. But if you use other encodings, the natural encoding may differ from the arbitrary order that we have here. (Example utf-8 with BOM and smileys)

However these different orders do not matter (according to my initial conclusion), because we need (a) find out about '\0' and (b) only need only 'arbitrary' order (which is referred to by the " ordered" trait).

Show 7 quoted lines
>> Essentially compare_prefix wants to provide the same return
>> value as `strncmp(refname, prefix, min(strlen(refname), strlen(prefix)));`
>> except that it is optimized as we do not have to walk over a string
>> multiple times (to determine length and then pass it to compare).
>
> Hmm, yeah, I think that would be an equivalent. I didn't think of that,
> but as you say it would be less efficient.

I was just too lazy to check if we had the results of strlen around already, such that the comparison would be equally cheap, but more readable. Also IIRC later patches enhance this function, so we shall not make use of the strncmp function here.

> The patch is credited to me, but I actually screwed up the ordering by
> failing to do the unsigned cast. Michael fixed that part before posting
> it. :)

Thanks, Stefan

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