vim-patch:partial:9.1.1179: too many strlen() calls in misc2.c

Problem:  too many strlen() calls in misc2.c
Solution: refactor misc2.c and use bsearch() instead of a linear search
          to find matches in the key_names_table array (John Marriott).

This commit changes misc2.c to use bsearch() to perform string searches of
the key_names_table array.

Implementation detail:
- Some entries in this array have alternate names. Add field alt_name to
  point to the alternate name.
- Some entries in this array are only available if a given feature is
  defined. Keep them in the array, but add a boolean field enabled to
  indicate if the record can be used or not. If the feature is not
  available, the corresponding enabled field is set to FALSE.

In my measurements running the test suite on a huge non-gui build on
linux, the number of string comparisons in get_special_key_code():
Before (linear search): 2,214,957
After (binary search): 297,770

A side effect of this is 1477 calls to STRLEN() in
get_special_key_name() for the same test run are no longer necessary.

closes: vim/vim#16788

https://github.com/vim/vim/commit/4a1e6dacbb2cc833353983bea7eac38191c9d3b4

Skip the mouse shape changes.

Co-authored-by: John Marriott <basilisk@internode.on.net>

1 files changed, 36 insertions, 6 deletions

diff --git a/src/gen/gen_keycodes.lua b/src/gen/gen_keycodes.lua
index fff5b59396..118eac2579 100644
--- a/src/gen/gen_keycodes.lua
+++ b/src/gen/gen_keycodes.lua
@@ -1,19 +1,49 @@
 local names_file = arg[1]
 
 local keycodes = require('nvim.keycodes')
-local keycode_names = keycodes.names
 
 local names_tgt = assert(io.open(names_file, 'w'))
 
+--- @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>
+local alt_name_idx = {}
+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
+  end
+end
+
 names_tgt:write([[
 static const struct key_name_entry {
-  int key;           ///< Special key code or ascii value
-  const char *name;  ///< Name of key
+  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)
 } key_names_table[] = {]])
 
-for _, keycode in ipairs(keycode_names) do
-  names_tgt:write(('\n  {%s, "%s"},'):format(keycode[1], keycode[2]))
+for i, keycode in ipairs(keycode_names) do
+  local key = keycode[1]
+  local name = keycode[2]
+  local alt_idx = alt_name_idx[key]
+  names_tgt:write(
+    ('\n  {%s, {"%s", %d}, %s},'):format(
+      key,
+      name,
+      #name,
+      alt_idx == i and 'NULL' or ('&key_names_table[%d].name'):format(alt_idx - 1)
+    )
+  )
 end
 
-names_tgt:write('\n  {0, NULL},\n};\n')
+names_tgt:write('\n};\n')
 names_tgt:close()