perf(keycodes): use hashy for string lookup

This is slightly faster than the binary search as per the benchmark, and
allows handling the vim/vim#16821 situation in generator code.

4 files changed, 78 insertions, 81 deletions

diff --git a/src/gen/gen_keycodes.lua b/src/gen/gen_keycodes.lua
index 118eac2579..53f0c24e58 100644
--- a/src/gen/gen_keycodes.lua
+++ b/src/gen/gen_keycodes.lua
@@ -1,49 +1,86 @@
 local names_file = arg[1]
 
+local hashy = require('gen.hashy')
 local keycodes = require('nvim.keycodes')
 
-local names_tgt = assert(io.open(names_file, 'w'))
+local keycode_names = keycodes.names
 
---- @type [string, string, integer][]
-local keycode_names = {}
-for i, keycode in ipairs(keycodes.names) do
-  table.insert(keycode_names, { keycode[1], keycode[2], i })
-end
-table.sort(keycode_names, function(keycode_a, keycode_b)
-  return keycode_a[2]:lower() < keycode_b[2]:lower()
-end)
+--- @type table<string,integer>
+--- Maps lower-case key names to their original indexes.
+local name_orig_idx = {}
 
 --- @type table<string,integer>
-local alt_name_idx = {}
+--- Maps keys to the original indexes of their preferred names.
+local key_orig_idx = {}
+
+--- @type [string, string][]
+--- When multiple keys have the same name (e.g. TAB and K_TAB), only the first one
+--- is added to the two tables above, and the other keys are added here.
+local extra_keys = {}
+
 for i, keycode in ipairs(keycode_names) do
   local key = keycode[1]
-  local alt_idx = alt_name_idx[key]
-  if alt_idx == nil or keycode_names[alt_idx][3] > keycode[3] then
-    alt_name_idx[key] = i
+  local name = keycode[2]
+  local name_lower = name:lower()
+  if name_orig_idx[name_lower] == nil then
+    name_orig_idx[name_lower] = i
+    if key_orig_idx[key] == nil then
+      key_orig_idx[key] = i
+    end
+  else
+    table.insert(extra_keys, keycode)
+  end
+end
+
+local hashorder = vim.tbl_keys(name_orig_idx)
+table.sort(hashorder)
+local hashfun
+hashorder, hashfun = hashy.hashy_hash('get_special_key_code', hashorder, function(idx)
+  return 'key_names_table[' .. idx .. '].name.data'
+end, true)
+
+--- @type table<string,integer>
+--- Maps keys to the (after hash) indexes of the entries with preferred names.
+local key_hash_idx = {}
+
+for i, lower_name in ipairs(hashorder) do
+  local orig_idx = name_orig_idx[lower_name]
+  local key = keycode_names[orig_idx][1]
+  if key_orig_idx[key] == orig_idx then
+    key_hash_idx[key] = i
   end
 end
 
+local names_tgt = assert(io.open(names_file, 'w'))
 names_tgt:write([[
 static const struct key_name_entry {
-  int key;                 ///< Special key code or ascii value
-  String name;             ///< Name of key
-  const String *alt_name;  ///< Pointer to alternative key name
-                           ///< (may be NULL or point to the name in another entry)
+  int key;                  ///< Special key code or ascii value
+  String name;              ///< Name of key
+  const String *pref_name;  ///< Pointer to preferred key name
+                            ///< (may be NULL or point to the name in another entry)
 } key_names_table[] = {]])
 
-for i, keycode in ipairs(keycode_names) do
+for i, lower_name in ipairs(hashorder) do
+  local keycode = keycode_names[name_orig_idx[lower_name]]
   local key = keycode[1]
   local name = keycode[2]
-  local alt_idx = alt_name_idx[key]
+  local pref_idx = key_hash_idx[key]
   names_tgt:write(
-    ('\n  {%s, {"%s", %d}, %s},'):format(
+    ('\n  {%s, {"%s", %u}, %s},'):format(
       key,
       name,
       #name,
-      alt_idx == i and 'NULL' or ('&key_names_table[%d].name'):format(alt_idx - 1)
+      pref_idx == i and 'NULL' or ('&key_names_table[%u].name'):format(pref_idx - 1)
     )
   )
 end
 
-names_tgt:write('\n};\n')
+for _, keycode in ipairs(extra_keys) do
+  local key = keycode[1]
+  local name = keycode[2]
+  names_tgt:write(('\n  {%s, {"%s", %u}, NULL},'):format(key, name, #name))
+end
+
+names_tgt:write('\n};\n\n')
+names_tgt:write('static ' .. hashfun)
 names_tgt:close()
diff --git a/src/gen/hashy.lua b/src/gen/hashy.lua
index 74b7655324..48292bfc0e 100644
--- a/src/gen/hashy.lua
+++ b/src/gen/hashy.lua
@@ -54,7 +54,7 @@ function M.build_pos_hash(strings)
   return len_pos_buckets, maxlen, worst_buck_size
 end
 
-function M.switcher(put, tab, maxlen, worst_buck_size)
+function M.switcher(put, tab, maxlen, worst_buck_size, lower)
   local neworder = {} --- @type string[]
   put '  switch (len) {\n'
   local bucky = worst_buck_size > 1
@@ -66,7 +66,7 @@ function M.switcher(put, tab, maxlen, worst_buck_size)
       local keys = vim.tbl_keys(posbuck)
       if #keys > 1 then
         table.sort(keys)
-        put('switch (str[' .. (pos - 1) .. ']) {\n')
+        put(('switch (%s(str[%s])) {\n'):format(lower and 'TOLOWER_ASC' or '', pos - 1))
         for _, c in ipairs(keys) do
           local buck = posbuck[c]
           local startidx = #neworder
@@ -102,7 +102,7 @@ function M.switcher(put, tab, maxlen, worst_buck_size)
   return neworder
 end
 
-function M.hashy_hash(name, strings, access)
+function M.hashy_hash(name, strings, access, lower)
   local stats = {}
   local put = function(str)
     table.insert(stats, str)
@@ -116,27 +116,27 @@ function M.hashy_hash(name, strings, access)
   else
     put('  int low = -1;\n')
   end
-  local neworder = M.switcher(put, len_pos_buckets, maxlen, worst_buck_size)
+  local neworder = M.switcher(put, len_pos_buckets, maxlen, worst_buck_size, lower)
   if maxlen == 1 then
     put([[
   return -1;
 ]])
   elseif worst_buck_size > 1 then
-    put([[
+    put(([[
   for (int i = low; i < high; i++) {
-    if (!memcmp(str, ]] .. access('i') .. [[, len)) {
+    if (!%s(str, %s, len)) {
       return i;
     }
   }
   return -1;
-]])
+]]):format(lower and 'mb_strnicmp' or 'memcmp', access('i')))
   else
-    put([[
-  if (low < 0 || memcmp(str, ]] .. access('low') .. [[, len)) {
+    put(([[
+  if (low < 0 || %s(str, %s, len)) {
     return -1;
   }
   return low;
-]])
+]]):format(lower and 'mb_strnicmp' or 'memcmp', access('low')))
   end
   put '}\n\n'
   return neworder, table.concat(stats)
diff --git a/src/nvim/keycodes.c b/src/nvim/keycodes.c
index 5ab6a718ef..9cb2321eee 100644
--- a/src/nvim/keycodes.c
+++ b/src/nvim/keycodes.c
@@ -338,8 +338,8 @@ char *get_special_key_name(int c, int modifiers)
       }
     }
   } else {            // use name of special key
-    const String *s = key_names_table[table_idx].alt_name != NULL
-                      ? key_names_table[table_idx].alt_name
+    const String *s = key_names_table[table_idx].pref_name != NULL
+                      ? key_names_table[table_idx].pref_name
                       : &key_names_table[table_idx].name;
 
     if ((int)s->size + idx + 2 <= MAX_KEY_NAME_LEN) {
@@ -601,44 +601,6 @@ int find_special_key_in_table(int c)
   return -1;
 }
 
-/// Compare two 'struct key_name_entry' structures.
-/// Note that the target string (p1) may contain additional trailing characters
-/// that should not factor into the comparison. Example:
-/// 'LeftMouse>", "<LeftMouse>"] ...'
-/// should match with
-/// 'LeftMouse'.
-/// These characters are identified by ascii_isident().
-static int cmp_key_name_entry(const void *a, const void *b)
-{
-  const char *p1 = ((struct key_name_entry *)a)->name.data;
-  const char *p2 = ((struct key_name_entry *)b)->name.data;
-  int result = 0;
-
-  if (p1 == p2) {
-    return 0;
-  }
-
-  while (ascii_isident(*p1) && *p2 != NUL) {
-    if ((result = TOLOWER_ASC(*p1) - TOLOWER_ASC(*p2)) != 0) {
-      break;
-    }
-    p1++;
-    p2++;
-  }
-
-  if (result == 0) {
-    if (*p2 == NUL) {
-      if (ascii_isident(*p1)) {
-        result = 1;
-      }
-    } else {
-      result = -1;
-    }
-  }
-
-  return result;
-}
-
 /// Find the special key with the given name
 ///
 /// @param[in]  name  Name of the special. Does not have to end with NUL, it is
@@ -654,17 +616,13 @@ int get_special_key_code(const char *name)
     return TERMCAP2KEY((uint8_t)name[2], (uint8_t)name[3]);
   }
 
-  struct key_name_entry target = { .name.data = (char *)name };
-  struct key_name_entry *entry = bsearch(&target,
-                                         &key_names_table,
-                                         ARRAY_SIZE(key_names_table),
-                                         sizeof(key_names_table[0]),
-                                         cmp_key_name_entry);
-  if (entry != NULL) {
-    return entry->key;
+  const char *name_end = name;
+  while (ascii_isident(*name_end)) {
+    name_end++;
   }
 
-  return 0;
+  int idx = get_special_key_code_hash(name, (size_t)(name_end - name));
+  return idx >= 0 ? key_names_table[idx].key : 0;
 }
 
 /// Look up the given mouse code to return the relevant information in the other arguments.
diff --git a/src/nvim/keycodes.lua b/src/nvim/keycodes.lua
index c6158b0b84..04f09eb005 100644
--- a/src/nvim/keycodes.lua
+++ b/src/nvim/keycodes.lua
@@ -1,5 +1,7 @@
 return {
   --- @type [string, string][] List of [key, name] tuples.
+  --- For keys with multiple names, put the preferred name first.
+  --- For multiple keys with the same name, put the preferred key first.
   names = {
     { [[' ']], 'Space' },
     { [[TAB]], 'Tab' },