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

[Bill Spitzak]

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:

   a = 0;
   b = size;
   while (a < b) {
     c = (a+b)/2;
     if (table[c] < key)
       a = c+1;
     else
       b = c;
   }
   table[a] is now the first item >= key

I believe for a table of a few hundred entries that does not change, a 
binary search is going to be faster than a typical hash table. 
Especially if the table is sorted at compile-time (typical hash tables 
are very hard to write in such a way that the table is pre-filled at 
compile time).