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

From: Junio C Hamano <gitster@pobox.com>
Date: Jan 5, 2013, 22:39 UTC
Message-ID: <7vmwwnp84p.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1357421206-5014-2-git-send-email-apelisse@gmail.com>

Antoine Pelisse <apelisse@gmail.com> writes:

Show 10 quoted lines

> 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?