Revert "Replace MyEventReceiver KeyList with std::unordered_set" (#10622)

This reverts commit 787561b29afdbc78769f68c2f5c4f2cff1b32340.

3 files changed, 111 insertions, 64 deletions

diff --git a/src/client/inputhandler.cpp b/src/client/inputhandler.cpp
index ee3e37ae9..608a405a8 100644
--- a/src/client/inputhandler.cpp
+++ b/src/client/inputhandler.cpp
@@ -112,7 +112,7 @@ bool MyEventReceiver::OnEvent(const SEvent &event)
 	// Remember whether each key is down or up
 	if (event.EventType == irr::EET_KEY_INPUT_EVENT) {
 		const KeyPress &keyCode = event.KeyInput;
-		if (keysListenedFor.count(keyCode)) {
+		if (keysListenedFor[keyCode]) {
 				// If the key is being held down then the OS may
 				// send a continuous stream of keydown events.
 				// In this case, we don't want to let this
@@ -120,15 +120,15 @@ bool MyEventReceiver::OnEvent(const SEvent &event)
 				// certain actions to repeat constantly.
 			if (event.KeyInput.PressedDown) {
 				if (!IsKeyDown(keyCode)) {
-					keyWasDown.insert(keyCode);
-					keyWasPressed.insert(keyCode);
+					keyWasDown.set(keyCode);
+					keyWasPressed.set(keyCode);
 				}
-				keyIsDown.insert(keyCode);
+				keyIsDown.set(keyCode);
 			} else {
 				if (IsKeyDown(keyCode))
-					keyWasReleased.insert(keyCode);
+					keyWasReleased.set(keyCode);
 
-				keyIsDown.erase(keyCode);
+				keyIsDown.unset(keyCode);
 			}
 
 			return true;
@@ -153,36 +153,36 @@ bool MyEventReceiver::OnEvent(const SEvent &event)
 		switch (event.MouseInput.Event) {
 		case EMIE_LMOUSE_PRESSED_DOWN:
 			key = "KEY_LBUTTON";
-			keyIsDown.insert(key);
-			keyWasDown.insert(key);
-			keyWasPressed.insert(key);
+			keyIsDown.set(key);
+			keyWasDown.set(key);
+			keyWasPressed.set(key);
 			break;
 		case EMIE_MMOUSE_PRESSED_DOWN:
 			key = "KEY_MBUTTON";
-			keyIsDown.insert(key);
-			keyWasDown.insert(key);
-			keyWasPressed.insert(key);
+			keyIsDown.set(key);
+			keyWasDown.set(key);
+			keyWasPressed.set(key);
 			break;
 		case EMIE_RMOUSE_PRESSED_DOWN:
 			key = "KEY_RBUTTON";
-			keyIsDown.insert(key);
-			keyWasDown.insert(key);
-			keyWasPressed.insert(key);
+			keyIsDown.set(key);
+			keyWasDown.set(key);
+			keyWasPressed.set(key);
 			break;
 		case EMIE_LMOUSE_LEFT_UP:
 			key = "KEY_LBUTTON";
-			keyIsDown.erase(key);
-			keyWasReleased.insert(key);
+			keyIsDown.unset(key);
+			keyWasReleased.set(key);
 			break;
 		case EMIE_MMOUSE_LEFT_UP:
 			key = "KEY_MBUTTON";
-			keyIsDown.erase(key);
-			keyWasReleased.insert(key);
+			keyIsDown.unset(key);
+			keyWasReleased.set(key);
 			break;
 		case EMIE_RMOUSE_LEFT_UP:
 			key = "KEY_RBUTTON";
-			keyIsDown.erase(key);
-			keyWasReleased.insert(key);
+			keyIsDown.unset(key);
+			keyWasReleased.set(key);
 			break;
 		case EMIE_MOUSE_WHEEL:
 			mouse_wheel += event.MouseInput.Wheel;
@@ -235,11 +235,7 @@ void RandomInputHandler::step(float dtime)
 		i.counter -= dtime;
 		if (i.counter < 0.0) {
 			i.counter = 0.1 * Rand(1, i.time_max);
-			KeyPress k = getKeySetting(i.key.c_str());
-			if (keydown.count(k))
-				keydown.erase(k);
-			else
-				keydown.insert(k);
+			keydown.toggle(getKeySetting(i.key.c_str()));
 		}
 	}
 	{
diff --git a/src/client/inputhandler.h b/src/client/inputhandler.h
index 885f34e05..def147a82 100644
--- a/src/client/inputhandler.h
+++ b/src/client/inputhandler.h
@@ -21,9 +21,9 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 
 #include "irrlichttypes_extrabloated.h"
 #include "joystick_controller.h"
+#include <list>
 #include "keycode.h"
 #include "renderingengine.h"
-#include <unordered_set>
 
 #ifdef HAVE_TOUCHSCREENGUI
 #include "gui/touchscreengui.h"
@@ -61,32 +61,98 @@ struct KeyCache
 	InputHandler *handler;
 };
 
+class KeyList : private std::list<KeyPress>
+{
+	typedef std::list<KeyPress> super;
+	typedef super::iterator iterator;
+	typedef super::const_iterator const_iterator;
+
+	virtual const_iterator find(const KeyPress &key) const
+	{
+		const_iterator f(begin());
+		const_iterator e(end());
+
+		while (f != e) {
+			if (*f == key)
+				return f;
+
+			++f;
+		}
+
+		return e;
+	}
+
+	virtual iterator find(const KeyPress &key)
+	{
+		iterator f(begin());
+		iterator e(end());
+
+		while (f != e) {
+			if (*f == key)
+				return f;
+
+			++f;
+		}
+
+		return e;
+	}
+
+public:
+	void clear() { super::clear(); }
+
+	void set(const KeyPress &key)
+	{
+		if (find(key) == end())
+			push_back(key);
+	}
+
+	void unset(const KeyPress &key)
+	{
+		iterator p(find(key));
+
+		if (p != end())
+			erase(p);
+	}
+
+	void toggle(const KeyPress &key)
+	{
+		iterator p(this->find(key));
+
+		if (p != end())
+			erase(p);
+		else
+			push_back(key);
+	}
+
+	bool operator[](const KeyPress &key) const { return find(key) != end(); }
+};
+
 class MyEventReceiver : public IEventReceiver
 {
 public:
 	// This is the one method that we have to implement
 	virtual bool OnEvent(const SEvent &event);
 
-	bool IsKeyDown(const KeyPress &keyCode) const { return keyIsDown.count(keyCode); }
+	bool IsKeyDown(const KeyPress &keyCode) const { return keyIsDown[keyCode]; }
 
 	// Checks whether a key was down and resets the state
 	bool WasKeyDown(const KeyPress &keyCode)
 	{
-		bool b = keyWasDown.count(keyCode);
+		bool b = keyWasDown[keyCode];
 		if (b)
-			keyWasDown.erase(keyCode);
+			keyWasDown.unset(keyCode);
 		return b;
 	}
 
 	// Checks whether a key was just pressed. State will be cleared
 	// in the subsequent iteration of Game::processPlayerInteraction
-	bool WasKeyPressed(const KeyPress &keycode) const { return keyWasPressed.count(keycode); }
+	bool WasKeyPressed(const KeyPress &keycode) const { return keyWasPressed[keycode]; }
 
 	// Checks whether a key was just released. State will be cleared
 	// in the subsequent iteration of Game::processPlayerInteraction
-	bool WasKeyReleased(const KeyPress &keycode) const { return keyWasReleased.count(keycode); }
+	bool WasKeyReleased(const KeyPress &keycode) const { return keyWasReleased[keycode]; }
 
-	void listenForKey(const KeyPress &keyCode) { keysListenedFor.insert(keyCode); }
+	void listenForKey(const KeyPress &keyCode) { keysListenedFor.set(keyCode); }
 	void dontListenForKeys() { keysListenedFor.clear(); }
 
 	s32 getMouseWheel()
@@ -132,20 +198,24 @@ public:
 #endif
 
 private:
-	//! The current state of keys
-	std::unordered_set<KeyPress> keyIsDown;
+	// The current state of keys
+	KeyList keyIsDown;
 
-	//! Whether a key was down
-	std::unordered_set<KeyPress> keyWasDown;
+	// Whether a key was down
+	KeyList keyWasDown;
 
-	//! Whether a key has just been pressed
-	std::unordered_set<KeyPress> keyWasPressed;
+	// Whether a key has just been pressed
+	KeyList keyWasPressed;
 
-	//! Whether a key has just been released
-	std::unordered_set<KeyPress> keyWasReleased;
+	// Whether a key has just been released
+	KeyList keyWasReleased;
 
-	//! List of keys we listen for
-	std::unordered_set<KeyPress> keysListenedFor;
+	// List of keys we listen for
+	// TODO perhaps the type of this is not really
+	// performant as KeyList is designed for few but
+	// often changing keys, and keysListenedFor is expected
+	// to change seldomly but contain lots of keys.
+	KeyList keysListenedFor;
 };
 
 class InputHandler
@@ -277,7 +347,7 @@ public:
 		return true;
 	}
 
-	virtual bool isKeyDown(GameKeyType k) { return keydown.count(keycache.key[k]); }
+	virtual bool isKeyDown(GameKeyType k) { return keydown[keycache.key[k]]; }
 	virtual bool wasKeyDown(GameKeyType k) { return false; }
 	virtual bool wasKeyPressed(GameKeyType k) { return false; }
 	virtual bool wasKeyReleased(GameKeyType k) { return false; }
@@ -292,7 +362,7 @@ public:
 	s32 Rand(s32 min, s32 max);
 
 private:
-	std::unordered_set<KeyPress> keydown;
+	KeyList keydown;
 	v2s32 mousepos;
 	v2s32 mousespeed;
 };
diff --git a/src/client/keycode.h b/src/client/keycode.h
index 263b722c7..7036705d1 100644
--- a/src/client/keycode.h
+++ b/src/client/keycode.h
@@ -24,20 +24,12 @@ with this program; if not, write to the Free Software Foundation, Inc.,
 #include <IEventReceiver.h>
 #include <string>
 
-class KeyPress;
-namespace std
-{
-	template <> struct hash<KeyPress>;
-}
-
 /* A key press, consisting of either an Irrlicht keycode
    or an actual char */
 
 class KeyPress
 {
 public:
-	friend struct std::hash<KeyPress>;
-
 	KeyPress() = default;
 
 	KeyPress(const char *name);
@@ -63,17 +55,6 @@ protected:
 	std::string m_name = "";
 };
 
-namespace std
-{
-	template <> struct hash<KeyPress>
-	{
-		size_t operator()(const KeyPress &key) const
-		{
-			return key.Key;
-		}
-	};
-}
-
 extern const KeyPress EscapeKey;
 extern const KeyPress CancelKey;