Resurect idvaluemap, order of traversal matters

This reverts commit 2b9b161d424c1168636042adc6678bb3df2be3f9.

7 files changed, 123 insertions, 50 deletions

diff --git a/src/completion.hh b/src/completion.hh
index eb1d4fa6..44726dd3 100644
--- a/src/completion.hh
+++ b/src/completion.hh
@@ -5,7 +5,6 @@
 
 #include <vector>
 #include <functional>
-#include <unordered_map>
 
 namespace Kakoune
 {
@@ -41,34 +40,5 @@ inline Completions complete_nothing(const Context& context, CompletionFlags,
     return Completions(cursor_pos, cursor_pos);
 }
 
-template<typename Condition, typename Value>
-CandidateList complete_key_if(const std::unordered_map<String, Value>& map,
-                              const String& prefix,
-                              ByteCount cursor_pos,
-                              Condition condition)
-{
-    String real_prefix = prefix.substr(0, cursor_pos);
-    CandidateList result;
-    for (auto& value : map)
-    {
-        if (not condition(value))
-            continue;
-
-        if (prefix_match(value.first, real_prefix))
-            result.push_back(value.first);
-    }
-    return result;
-}
-
-template<typename Value>
-CandidateList complete_key(const std::unordered_map<String, Value>& map,
-                           const String& prefix,
-                           ByteCount cursor_pos)
-{
-    return complete_key_if(
-        map, prefix, cursor_pos,
-        [](const std::pair<String, Value>&) { return true; });
-}
-
 }
 #endif // completion_hh_INCLUDED
diff --git a/src/function_group.hh b/src/function_group.hh
index 82e4fc7c..739b7ffb 100644
--- a/src/function_group.hh
+++ b/src/function_group.hh
@@ -2,10 +2,8 @@
 #define function_group_hh_INCLUDED
 
 #include "exception.hh"
+#include "idvaluemap.hh"
 #include "string.hh"
-#include "completion.hh"
-
-#include <unordered_map>
 
 namespace Kakoune
 {
@@ -25,14 +23,14 @@ public:
 
     void append(FunctionAndId&& function)
     {
-        if (m_functions.find(function.first) != m_functions.end())
+        if (m_functions.contains(function.first))
             throw runtime_error("duplicate id: " + function.first);
 
-        m_functions.insert(std::forward<FunctionAndId>(function));
+        m_functions.append(std::forward<FunctionAndId>(function));
     }
     void remove(const String& id)
     {
-        m_functions.erase(id);
+        m_functions.remove(id);
     }
 
     FunctionGroup& get_group(const String& id)
@@ -48,20 +46,19 @@ public:
 
     CandidateList complete_id(const String& prefix, ByteCount cursor_pos) const
     {
-        return complete_key(m_functions, prefix, cursor_pos);
+        return m_functions.complete_id(prefix, cursor_pos);
     }
 
     CandidateList complete_group_id(const String& prefix, ByteCount cursor_pos) const
     {
-        return complete_key_if(
-            m_functions, prefix, cursor_pos,
-            [](const FunctionAndId& func) {
+        return m_functions.complete_id_if(
+            prefix, cursor_pos, [](const FunctionAndId& func) {
                 return func.second.template target<FunctionGroup>() != nullptr;
             });
     }
 
 private:
-    std::unordered_map<String, Function> m_functions;
+    idvaluemap<String, Function> m_functions;
 };
 
 }
diff --git a/src/function_registry.hh b/src/function_registry.hh
index 03d8c09d..2197efcc 100644
--- a/src/function_registry.hh
+++ b/src/function_registry.hh
@@ -2,10 +2,9 @@
 #define function_registry_h_INCLUDED
 
 #include "completion.hh"
+#include "idvaluemap.hh"
 #include "string.hh"
 
-#include <unordered_map>
-
 namespace Kakoune
 {
 
@@ -21,8 +20,8 @@ class FunctionRegistry
 public:
     void register_func(const String& name, const FunctionType& function)
     {
-        kak_assert(m_functions.find(name) == m_functions.end());
-        m_functions[name] = function;
+        kak_assert(not m_functions.contains(name));
+        m_functions.append(std::make_pair(name, function));
     }
 
     const FunctionType& operator[](const String& name) const
@@ -35,11 +34,11 @@ public:
 
     CandidateList complete_name(const String& prefix, ByteCount cursor_pos)
     {
-        return complete_key(m_functions, prefix, cursor_pos);
+        return m_functions.complete_id(prefix, cursor_pos);
     }
 
 private:
-    std::unordered_map<String, FunctionType> m_functions;
+    idvaluemap<String, FunctionType> m_functions;
 };
 
 }
diff --git a/src/hook_manager.cc b/src/hook_manager.cc
index 6cff65b5..344b6ce0 100644
--- a/src/hook_manager.cc
+++ b/src/hook_manager.cc
@@ -8,7 +8,7 @@ namespace Kakoune
 void HookManager::add_hook(const String& hook_name, String id, HookFunc hook)
 {
     auto& hooks = m_hook[hook_name];
-    hooks.insert({std::move(id), std::move(hook)});
+    hooks.append({std::move(id), std::move(hook)});
 }
 
 void HookManager::remove_hooks(const String& id)
@@ -16,7 +16,7 @@ void HookManager::remove_hooks(const String& id)
     if (id.empty())
         throw runtime_error("invalid id");
     for (auto& hooks : m_hook)
-        hooks.second.erase(id);
+        hooks.second.remove_all(id);
 }
 
 void HookManager::run_hook(const String& hook_name,
diff --git a/src/hook_manager.hh b/src/hook_manager.hh
index d9d224e6..ac2ce8f5 100644
--- a/src/hook_manager.hh
+++ b/src/hook_manager.hh
@@ -1,6 +1,7 @@
 #ifndef hook_manager_hh_INCLUDED
 #define hook_manager_hh_INCLUDED
 
+#include "idvaluemap.hh"
 #include "utils.hh"
 
 #include <unordered_map>
@@ -28,7 +29,7 @@ private:
     friend class GlobalHooks;
 
     HookManager* m_parent;
-    std::unordered_map<String, std::unordered_multimap<String, HookFunc>> m_hook;
+    std::unordered_map<String, idvaluemap<String, HookFunc>> m_hook;
 };
 
 class GlobalHooks : public HookManager,
diff --git a/src/idvaluemap.hh b/src/idvaluemap.hh
new file mode 100644
index 00000000..9efbdd68
--- /dev/null
+++ b/src/idvaluemap.hh
@@ -0,0 +1,105 @@
+#ifndef idvaluemap_hh_INCLUDED
+#define idvaluemap_hh_INCLUDED
+
+#include "completion.hh"
+
+#include <vector>
+
+namespace Kakoune
+{
+
+template<typename Id, typename Value>
+class idvaluemap
+{
+public:
+    typedef std::pair<Id, Value> value_type;
+    typedef std::vector<value_type> container_type;
+    typedef typename container_type::iterator iterator;
+    typedef typename container_type::const_iterator const_iterator;
+
+    void append(const value_type& value)
+    {
+        m_content.push_back(value);
+    }
+
+    void append(value_type&& value)
+    {
+        m_content.push_back(std::move(value));
+    }
+
+    iterator find(const Id& id)
+    {
+        for (auto it = begin(); it != end(); ++it)
+        {
+            if (it->first == id)
+                return it;
+        }
+        return end();
+    }
+
+    const_iterator find(const Id& id) const
+    {
+        for (auto it = begin(); it != end(); ++it)
+        {
+            if (it->first == id)
+                return it;
+        }
+        return end();
+    }
+
+    bool contains(const Id& id) const
+    {
+        return find(id) != end();
+    }
+
+    void remove(const Id& id)
+    {
+        auto it = find(id);
+        if (it != end())
+            m_content.erase(it);
+    }
+
+    void remove_all(const Id& id)
+    {
+        for (auto it = find(id); it != end(); it = find(id))
+            m_content.erase(it);
+    }
+
+    template<typename Condition>
+    CandidateList complete_id_if(const String& prefix,
+                                 ByteCount cursor_pos,
+                                 Condition condition) const
+    {
+        String real_prefix = prefix.substr(0, cursor_pos);
+        CandidateList result;
+        for (auto& value : m_content)
+        {
+            if (not condition(value))
+                continue;
+
+            String id_str = value.first;
+            if (prefix_match(id_str, real_prefix))
+                result.push_back(std::move(id_str));
+        }
+        return result;
+    }
+
+    CandidateList complete_id(const String& prefix,
+                              ByteCount cursor_pos) const
+    {
+        return complete_id_if(
+            prefix, cursor_pos, [](const value_type&) { return true; });
+    }
+
+    iterator       begin()       { return m_content.begin(); }
+    iterator       end()         { return m_content.end(); }
+    const_iterator begin() const { return m_content.begin(); }
+    const_iterator end()   const { return m_content.end(); }
+
+private:
+    container_type m_content;
+};
+
+}
+
+#endif // idvaluemap_hh_INCLUDED
diff --git a/src/keymap_manager.hh b/src/keymap_manager.hh
index caf4174a..c9887a6b 100644
--- a/src/keymap_manager.hh
+++ b/src/keymap_manager.hh
@@ -1,6 +1,7 @@
 #ifndef keymap_manager_hh_INCLUDED
 #define keymap_manager_hh_INCLUDED
 
+#include "idvaluemap.hh"
 #include "keys.hh"
 #include "utils.hh"