[PATCH libxkbcommon v2 1/2] makekeys: use GNU gperf to generate perfect hashtables

[David Herrmann]

Hi Bill

On Thu, Oct 4, 2012 at 6:46 PM, Bill Spitzak <spitzak at gmail.com> wrote:
>
>
> David Herrmann wrote:
>>
>> Hi Bill
>>
>> On Thu, Oct 4, 2012 at 6:40 PM, Bill Spitzak <spitzak at gmail.com> wrote:
>>>
>>> David Herrmann wrote:
>>>
>>>>> So since makekeys is ugly and gperf is a bit excessive, maybe we should
>>>>> just keep it simple, what do you think?
>>>>
>>>>
>>>> Works all very nice here! Thanks, I am all in favor of this approach.
>>>> Reviewed-by: David Herrmann <dh.herrmann at googlemail.com>
>>>> No need to resend for the small fixes I suggested, though.
>>>>
>>>> I am working on a case-insensitive search based on this patch. I will
>>>> send it when done. The approach I am using is:
>>>> Use bsearch with strcasecmp() to find _one_ of the possible solutions
>>>> (not necessarily the first). Then I check the entries _before_ and
>>>> _after_ the one I found whether they are equal and then I use some
>>>> heuristic to return the lower-case keysym (that is, KEY_a, not KEY_A).
>>>
>>>
>>> Actually binary search can always find the first match (or the last one
>>> depending on exactly how it is written:
>>
>>
>> I don't need the first one. I need the one that is the lower-case keysym.
>
>
> What I meant is that you only have to look forward from the found item, not
> in both directions.

Depends how bsearch() is implemented. If it directly returns on
equality, then I cannot be sure. Please see man bsearch(3). It
explicitly mentions that the item returned is unspecified on
duplicates.

I we would use the algorithm you mentioned, then you're right. But the
bsearch() implementation might add additional conditions in the loop
which we cannot rely on to be not there.

Regards
David