Re: [PATCH 01/10] list_lookup: create case and length search

[Junio C Hamano <gitster@pobox.com>]

Antoine Pelisse <apelisse@gmail.com> writes:

> Create a new function to look-up a string in a string_list, but:
>  - add a new parameter to ignore case differences
>  - add a length parameter to search for a substring
>
> The idea is to avoid several copies (lowering a string before searching
> it when we just want to ignore case), or copying a substring of a bigger
> string to search it in the string_list
>
> Signed-off-by: Antoine Pelisse <apelisse@gmail.com>
> ---

I did not read beyond the log message and the function signature of
the updated get_entry_index(), but it strikes me insane to build a
sorted list using case sensitive full string comarison and then to
look for an element in that list using a different comparison
criteria (e.g. case insensitive comparison) and to expect the
bisection search to still work.  Shouldn't the codepath that builds
the string-list be sorting the list in case insensitive way from the
beginning if this were to work correctly?

It seems to suggest to me that this "are the keys case sensitive?"
bit belongs to the entire struct string_list structure as its
property (similar to the way "do the keys need to be strdup'ed?"
bit), not something you would flip per invocation basis of the
lookup function.

Also isn't size_t an unsigned type?  What does it even mean to pass
"-1" to it, and propagate it down to strncmp()?

If you have a list sorted by a key, and if you want to query it with
a partial prefix of a possibly valid key, I think you shouldn't have
to add the "length search" at all. The existing look up function
would return the location in the list that short key would have been
inserted, which would come before the first entry that your short
key is a prefix of, so the caller can iterate the list from there to
find all entries.  In other words, if existing list has "aaa",
"bba", and "bbc", and you want to grab entries that begin with "bb",
you can ask for "bb" to the loop up function, which would say "the
key does not exist in the list, but it would be inserted before this
'bba' entry".  Then you can discover that "bba" and "bbc" both
matches the shortened key you have, no?