Store key hash in IdMap

14 files changed, 73 insertions, 61 deletions

diff --git a/src/client.cc b/src/client.cc
index b4531949..38cc7d89 100644
--- a/src/client.cc
+++ b/src/client.cc
@@ -256,17 +256,12 @@ void Client::check_if_buffer_needs_reloading()
         reload_buffer();
 }
 
-StringView Client::get_env_var(const String& name) const
+StringView Client::get_env_var(StringView name) const
 {
     auto it = m_env_vars.find(name);
     if (it == m_env_vars.end())
         return {};
-    return it->second;
-}
-
-StringView Client::get_env_var(StringView name) const
-{
-    return get_env_var(name.str());
+    return it->value;
 }
 
 void Client::on_option_changed(const Option& option)
diff --git a/src/client.hh b/src/client.hh
index 70c8f706..58df582e 100644
--- a/src/client.hh
+++ b/src/client.hh
@@ -50,7 +50,6 @@ public:
 
     void change_buffer(Buffer& buffer);
 
-    StringView get_env_var(const String& name) const;
     StringView get_env_var(StringView name) const;
 
 private:
diff --git a/src/command_manager.cc b/src/command_manager.cc
index 5d5920a2..7a4033da 100644
--- a/src/command_manager.cc
+++ b/src/command_manager.cc
@@ -340,7 +340,7 @@ String expand_token(const Token& token, const Context& context,
     {
         auto it = env_vars.find(content);
         if (it != env_vars.end())
-            return it->second;
+            return it->value;
         return ShellManager::instance().get_val(content, context);
     }
     case Token::Type::RawEval:
diff --git a/src/commands.cc b/src/commands.cc
index 3f8c06b3..b93114a8 100644
--- a/src/commands.cc
+++ b/src/commands.cc
@@ -584,7 +584,7 @@ const CommandDesc add_highlighter_cmd = {
             HighlighterRegistry& registry = HighlighterRegistry::instance();
             auto it = registry.find(params[0]);
             if (it != registry.end())
-                return format("{}:\n{}", params[0], indent(it->second.docstring));
+                return format("{}:\n{}", params[0], indent(it->value.docstring));
         }
         return "";
     },
@@ -605,7 +605,7 @@ const CommandDesc add_highlighter_cmd = {
         auto it = registry.find(name);
         if (it == registry.end())
             throw runtime_error(format("No such highlighter factory '{}'", name));
-        group.add_child(it->second.factory(highlighter_params));
+        group.add_child(it->value.factory(highlighter_params));
 
         if (context.has_window())
             context.window().force_redraw();
diff --git a/src/highlighter_group.cc b/src/highlighter_group.cc
index 3224cc8a..4a513bac 100644
--- a/src/highlighter_group.cc
+++ b/src/highlighter_group.cc
@@ -9,7 +9,7 @@ void HighlighterGroup::highlight(const Context& context, HighlightFlags flags,
                                  DisplayBuffer& display_buffer, BufferRange range)
 {
     for (auto& hl : m_highlighters)
-       hl.second->highlight(context, flags, display_buffer, range);
+       hl.value->highlight(context, flags, display_buffer, range);
 }
 
 void HighlighterGroup::add_child(HighlighterAndId&& hl)
@@ -17,7 +17,7 @@ void HighlighterGroup::add_child(HighlighterAndId&& hl)
     if (m_highlighters.contains(hl.first))
         throw runtime_error(format("duplicate id: '{}'", hl.first));
 
-    m_highlighters.append(std::move(hl));
+    m_highlighters.append({ std::move(hl.first), std::move(hl.second) });
 }
 
 void HighlighterGroup::remove_child(StringView id)
@@ -33,9 +33,9 @@ Highlighter& HighlighterGroup::get_child(StringView path)
     if (it == m_highlighters.end())
         throw child_not_found(format("no such id: '{}'", id));
     if (sep_it == path.end())
-        return *it->second;
+        return *it->value;
     else
-        return it->second->get_child({sep_it+1, path.end()});
+        return it->value->get_child({sep_it+1, path.end()});
 }
 
 Completions HighlighterGroup::complete_child(StringView path, ByteCount cursor_pos, bool group) const
@@ -48,10 +48,9 @@ Completions HighlighterGroup::complete_child(StringView path, ByteCount cursor_p
         return offset_pos(hl.complete_child(path.substr(offset), cursor_pos - offset, group), offset);
     }
 
-    using ValueType = HighlighterMap::value_type;
     auto c = transformed(filtered(m_highlighters,
-                                  [=](const ValueType& hl)
-                                  { return not group or hl.second->has_children(); }),
+                                  [=](const HighlighterMap::Element& hl)
+                                  { return not group or hl.value->has_children(); }),
                          HighlighterMap::get_id);
     return { 0, 0, complete(path, cursor_pos, c) };
 }
diff --git a/src/highlighters.cc b/src/highlighters.cc
index e76fb386..8dd420e1 100644
--- a/src/highlighters.cc
+++ b/src/highlighters.cc
@@ -1152,20 +1152,20 @@ public:
             if (apply_default and last_begin < begin->begin)
                 apply_highlighter(context, flags, display_buffer,
                                   correct(last_begin), correct(begin->begin),
-                                  default_group_it->second);
+                                  default_group_it->value);
 
             auto it = m_groups.find(begin->group);
             if (it == m_groups.end())
                 continue;
             apply_highlighter(context, flags, display_buffer,
                               correct(begin->begin), correct(begin->end),
-                              it->second);
+                              it->value);
             last_begin = begin->end;
         }
         if (apply_default and last_begin < display_range.end)
             apply_highlighter(context, flags, display_buffer,
                               correct(last_begin), range.end,
-                              default_group_it->second);
+                              default_group_it->value);
 
     }
 
@@ -1179,9 +1179,9 @@ public:
         if (it == m_groups.end())
             throw child_not_found(format("no such id: {}", id));
         if (sep_it == path.end())
-            return it->second;
+            return it->value;
         else
-            return it->second.get_child({sep_it+1, path.end()});
+            return it->value.get_child({sep_it+1, path.end()});
     }
 
     Completions complete_child(StringView path, ByteCount cursor_pos, bool group) const override
@@ -1194,7 +1194,7 @@ public:
             return offset_pos(hl.complete_child(path.substr(offset), cursor_pos - offset, group), offset);
         }
 
-        auto container = transformed(m_groups, IdMap<HighlighterGroup>::get_id);
+        auto container = transformed(m_groups, decltype(m_groups)::get_id);
         return { 0, 0, complete(path, cursor_pos, container) };
     }
 
diff --git a/src/hook_manager.cc b/src/hook_manager.cc
index 9cdfb10b..49a09f3b 100644
--- a/src/hook_manager.cc
+++ b/src/hook_manager.cc
@@ -21,7 +21,7 @@ void HookManager::remove_hooks(StringView group)
     if (group.empty())
         throw runtime_error("invalid id");
     for (auto& hooks : m_hook)
-        hooks.second.remove_all(group);
+        hooks.value.remove_all(group);
 }
 
 CandidateList HookManager::complete_hook_group(StringView prefix, ByteCount pos_in_token)
@@ -29,7 +29,7 @@ CandidateList HookManager::complete_hook_group(StringView prefix, ByteCount pos_
     CandidateList res;
     for (auto& list : m_hook)
     {
-        auto container = transformed(list.second, IdMap<HookFunc>::get_id);
+        auto container = transformed(list.value, decltype(list.value)::get_id);
         for (auto& c : complete(prefix, pos_in_token, container))
         {
             if (!contains(res, c))
@@ -51,21 +51,21 @@ void HookManager::run_hook(StringView hook_name,
 
     auto& disabled_hooks = context.options()["disabled_hooks"].get<Regex>();
     bool hook_error = false;
-    for (auto& hook : hook_list_it->second)
+    for (auto& hook : hook_list_it->value)
     {
-        if (not hook.first.empty() and not disabled_hooks.empty() and
-            regex_match(hook.first.begin(), hook.first.end(), disabled_hooks))
+        if (not hook.key.empty() and not disabled_hooks.empty() and
+            regex_match(hook.key.begin(), hook.key.end(), disabled_hooks))
             continue;
 
         try
         {
-            hook.second(param, context);
+            hook.value(param, context);
         }
         catch (runtime_error& err)
         {
             hook_error = true;
             write_to_debug_buffer(format("error running hook {}/{}: {}",
-                               hook_name, hook.first, err.what()));
+                               hook_name, hook.key, err.what()));
         }
     }
 
diff --git a/src/id_map.hh b/src/id_map.hh
index e4c331de..42bd4f2a 100644
--- a/src/id_map.hh
+++ b/src/id_map.hh
@@ -1,10 +1,11 @@
 #ifndef id_map_hh_INCLUDED
 #define id_map_hh_INCLUDED
 
-#include "containers.hh"
 #include "string.hh"
 #include "vector.hh"
 
+#include <algorithm>
+
 namespace Kakoune
 {
 
@@ -12,32 +13,49 @@ template<typename Value, MemoryDomain domain = MemoryDomain::Undefined>
 class IdMap
 {
 public:
-    using value_type = std::pair<String, Value>;
-    using container_type = Vector<value_type, domain>;
+    struct Element
+    {
+        Element(String k, Value v)
+            : key(std::move(k)), hash(hash_value(key)), value(std::move(v)) {}
+
+        String key;
+        size_t hash;
+        Value value;
+
+        bool operator==(const Element& other) const
+        {
+            return hash == other.hash and key == other.key and value == other.value;
+        }
+    };
+
+    using container_type = Vector<Element, domain>;
     using iterator = typename container_type::iterator;
     using const_iterator = typename container_type::const_iterator;
 
     IdMap() = default;
-    IdMap(std::initializer_list<value_type> val) : m_content{val} {}
+    IdMap(std::initializer_list<Element> val) : m_content{val} {}
 
-    void append(const value_type& value)
+    void append(const Element& value)
     {
         m_content.push_back(value);
     }
 
-    void append(value_type&& value)
+    void append(Element&& value)
     {
         m_content.push_back(std::move(value));
     }
 
     iterator find(StringView id)
     {
-        return Kakoune::find(transformed(m_content, get_id), id).base();
+        const size_t hash = hash_value(id);
+        return std::find_if(begin(), end(),
+                            [id, hash](const Element& e)
+                            { return e.hash == hash and e.key == id; });
     }
 
     const_iterator find(StringView id) const
     {
-        return Kakoune::find(transformed(m_content, get_id), id).base();
+        return const_cast<IdMap*>(this)->find(id);
     }
 
     bool contains(StringView id) const
@@ -54,8 +72,9 @@ public:
 
     void remove_all(StringView id)
     {
-        auto it = std::remove_if(begin(), end(),
-                                 [&](value_type& v){ return v.first == id; });
+        const size_t hash = hash_value(id);
+        auto it = std::remove_if(begin(), end(), [id, hash](const Element& e)
+                                 { return e.hash == hash and e.key == id; });
         m_content.erase(it, end());
     }
 
@@ -63,10 +82,10 @@ public:
     {
         auto it = find(id);
         if (it != m_content.end())
-            return it->second;
+            return it->value;
 
         append({ id.str(), Value{} });
-        return (m_content.end()-1)->second;
+        return (m_content.end()-1)->value;
     }
 
     template<MemoryDomain dom>
@@ -85,7 +104,7 @@ public:
     size_t size() const { return m_content.size(); }
     void clear() { m_content.clear(); }
 
-    static const String& get_id(const value_type& v) { return v.first; }
+    static const String& get_id(const Element& e) { return e.key; }
 
     bool empty() const { return m_content.empty(); }
 
diff --git a/src/ncurses_ui.cc b/src/ncurses_ui.cc
index 81adf298..574b071c 100644
--- a/src/ncurses_ui.cc
+++ b/src/ncurses_ui.cc
@@ -935,34 +935,34 @@ void NCursesUI::set_ui_options(const Options& options)
 {
     {
         auto it = options.find("ncurses_assistant");
-        if (it == options.end() or it->second == "clippy")
+        if (it == options.end() or it->value == "clippy")
             m_assistant = assistant_clippy;
-        else if (it->second == "cat")
+        else if (it->value == "cat")
             m_assistant = assistant_cat;
-        else if (it->second == "none" or it->second == "off")
+        else if (it->value == "none" or it->value == "off")
             m_assistant = ConstArrayView<StringView>{};
     }
 
     {
         auto it = options.find("ncurses_status_on_top");
         m_status_on_top = it != options.end() and
-            (it->second == "yes" or it->second == "true");
+            (it->value == "yes" or it->value == "true");
     }
 
     {
         auto it = options.find("ncurses_set_title");
         m_set_title = it == options.end() or
-            (it->second == "yes" or it->second == "true");
+            (it->value == "yes" or it->value == "true");
     }
 
     {
         auto wheel_down_it = options.find("ncurses_wheel_down_button");
         m_wheel_down_button = wheel_down_it != options.end() ?
-            str_to_int_ifp(wheel_down_it->second).value_or(2) : 2;
+            str_to_int_ifp(wheel_down_it->value).value_or(2) : 2;
 
         auto wheel_up_it = options.find("ncurses_wheel_up_button");
         m_wheel_up_button = wheel_up_it != options.end() ?
-            str_to_int_ifp(wheel_up_it->second).value_or(4) : 4;
+            str_to_int_ifp(wheel_up_it->value).value_or(4) : 4;
     }
 }
 
diff --git a/src/option_types.hh b/src/option_types.hh
index d04544dd..fce15ad6 100644
--- a/src/option_types.hh
+++ b/src/option_types.hh
@@ -75,8 +75,8 @@ String option_to_string(const IdMap<Value, domain>& opt)
     {
         if (it != begin(opt))
             res += list_separator;
-        String elem = escape(option_to_string(it->first), '=', '\\') + "=" +
-                      escape(option_to_string(it->second), '=', '\\');
+        String elem = escape(option_to_string(it->key), '=', '\\') + "=" +
+                      escape(option_to_string(it->value), '=', '\\');
         res += escape(elem, list_separator, '\\');
     }
     return res;
diff --git a/src/parameters_parser.cc b/src/parameters_parser.cc
index 6448cca5..8ea0fc81 100644
--- a/src/parameters_parser.cc
+++ b/src/parameters_parser.cc
@@ -7,7 +7,7 @@ String generate_switches_doc(const SwitchMap& switches)
 {
     String res;
     for (auto& sw : switches)
-        res += " -" + sw.first + (sw.second.takes_arg ? " <arg>: " : ": ") + sw.second.description + "\n";
+        res += " -" + sw.key + (sw.value.takes_arg ? " <arg>: " : ": ") + sw.value.description + "\n";
     return res;
 }
 
@@ -27,11 +27,11 @@ ParametersParser::ParametersParser(ParameterList params,
             if (it == m_desc.switches.end())
                 throw unknown_option(params[i]);
 
-            if (it->second.takes_arg)
+            if (it->value.takes_arg)
             {
                 ++i;
                 if (i == params.size() or params[i][0_byte] == '-')
-                   throw missing_option_value(it->first);
+                   throw missing_option_value(it->key);
             }
         }
         else
@@ -54,7 +54,7 @@ Optional<StringView> ParametersParser::get_switch(StringView name) const
     {
         const auto& param = m_params[i];
         if (param[0_byte] == '-' and param.substr(1_byte) == name)
-            return it->second.takes_arg ? m_params[i+1] : StringView{};
+            return it->value.takes_arg ? m_params[i+1] : StringView{};
 
         if (param == "--")
             break;
diff --git a/src/register_manager.cc b/src/register_manager.cc
index 502cb59d..e3f52bcb 100644
--- a/src/register_manager.cc
+++ b/src/register_manager.cc
@@ -71,7 +71,7 @@ Register& RegisterManager::operator[](StringView reg)
     auto it = reg_names.find(reg);
     if (it == reg_names.end())
         throw runtime_error(format("no such register: '{}'", reg));
-    return (*this)[it->second];
+    return (*this)[it->value];
 }
 
 Register& RegisterManager::operator[](Codepoint c)
diff --git a/src/remote.cc b/src/remote.cc
index d22ee6f8..0592d0a3 100644
--- a/src/remote.cc
+++ b/src/remote.cc
@@ -91,8 +91,8 @@ public:
         write<uint32_t>(map.size());
         for (auto& val : map)
         {
-            write(val.first);
-            write(val.second);
+            write(val.key);
+            write(val.value);
         }
     }
 
diff --git a/src/shell_manager.cc b/src/shell_manager.cc
index 1e29ba2d..e1d03ffd 100644
--- a/src/shell_manager.cc
+++ b/src/shell_manager.cc
@@ -111,7 +111,7 @@ std::pair<String, int> ShellManager::eval(
 
             auto local_var = env_vars.find(name);
             if (local_var != env_vars.end())
-                setenv(("kak_" + name).c_str(), local_var->second.c_str(), 1);
+                setenv(("kak_" + name).c_str(), local_var->value.c_str(), 1);
             else try
             {
                 String value = get_val(name, context);