From 9d273406df9becf1471065b34324f18b9eec894a Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Sun, 27 Nov 2022 13:09:58 +0200
Subject: [PATCH] Reimplement reverse key lookup with a sorted vector

It's more efficient than map due to compact storage.
---
 source/input/keys.cpp | 25 +++++++++++++++----------
 1 file changed, 15 insertions(+), 10 deletions(-)

diff --git a/source/input/keys.cpp b/source/input/keys.cpp
index 9b3349a..d5687ae 100644
--- a/source/input/keys.cpp
+++ b/source/input/keys.cpp
@@ -1,6 +1,7 @@
 #include "keys.h"
-#include <map>
 #include <stdexcept>
+#include <vector>
+#include <msp/core/algorithm.h>
 #include <msp/strings/format.h>
 
 using namespace std;
@@ -12,21 +13,25 @@ extern unsigned sys_keymap[];
 
 unsigned key_from_sys(unsigned code)
 {
-	static bool init_done = false;
-	static map<unsigned, unsigned> reverse_map;
+	struct MappedKey
+	{
+		unsigned code;
+		Key key;
+	};
+
+	static vector<MappedKey> reverse_map;
 
-	if(!init_done)
+	if(reverse_map.empty())
 	{
 		for(unsigned i=0; i<N_KEYS_; ++i)
 			if(sys_keymap[i])
-				reverse_map[sys_keymap[i]] = i;
-
-		init_done = true;
+				reverse_map.push_back({ sys_keymap[i], static_cast<Key>(i) });
+		sort_member(reverse_map, &MappedKey::code);
 	}
 
-	auto i = reverse_map.find(code);
-	if(i!=reverse_map.end())
-		return i->second;
+	auto i = lower_bound_member(reverse_map, code, &MappedKey::code);
+	if(i!=reverse_map.end() && i->code==code)
+		return i->key;
 
 	return 0;
 }
-- 
2.43.0