has_dir_name(): do not get confused by characters < '/'

There is a bug in directory/file ("D/F") conflict checking optimization:
It assumes that such a conflict cannot happen if a newly added entry's
path is lexicgraphically "greater than" the last already-existing index
entry _and_ contains a directory separator that comes strictly after the
common prefix (`len > len_eq_offset`).

This assumption is incorrect, though: `a-` sorts _between_ `a` and
`a/b`, their common prefix is `a`, the slash comes after the common
prefix, and there is still a file/directory conflict.

Let's re-design this logic, taking these facts into consideration:

- It is impossible for a file to sort after another file with whose
  directory it conflicts because the trailing NUL byte is always smaller
  than any other character.

- Since there are quite a number of ASCII characters that sort before
  the slash (e.g. `-`, `.`, the space character), looking at the last
  already-existing index entry is not enough to determine whether there
  is a D/F conflict when the first character different from the
  existing last index entry's path is a slash.

  If it is not a slash, there cannot be a file/directory conflict.

  And if the existing index entry's first different character is a
  slash, it also cannot be a file/directory conflict because the
  optimization requires the newly-added entry's path to sort _after_ the
  existing entry's, and the conflicting file's path would not.

So let's fall back to the regular binary search whenever the newly-added
item's path differs in a slash character. If it does not, and it sorts
after the last index entry, there is no D/F conflict and the new index
entry can be safely appended.

This fix also nicely simplifies the logic and makes it much easier to
reason about, while the impact on performance should be negligible:
After this fix, the optimization will be skipped only when index
entry's paths differ in a slash and a space, `!`,  `"`,  `#`,  `$`,
`%`, `&`,  `'`,  | (  `)`,  `*`,  `+`,  `,`,  `-`, or  `.`, which should
be a rare situation.

Signed-off-by: Filip Hejsek <filip.hejsek@gmail.com>
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>

0 files changed, 0 insertions, 0 deletions