Get rid of uses of unordered_set, vector is just simpler and faster...

6 files changed, 42 insertions, 65 deletions

diff --git a/src/event_manager.cc b/src/event_manager.cc
index c78e6861..bea70ab0 100644
--- a/src/event_manager.cc
+++ b/src/event_manager.cc
@@ -8,12 +8,12 @@ namespace Kakoune
 FDWatcher::FDWatcher(int fd, Callback callback)
     : m_fd{fd}, m_callback{std::move(callback)}
 {
-    EventManager::instance().m_fd_watchers.insert(this);
+    EventManager::instance().m_fd_watchers.push_back(this);
 }
 
 FDWatcher::~FDWatcher()
 {
-    EventManager::instance().m_fd_watchers.erase(this);
+    unordered_erase(EventManager::instance().m_fd_watchers, this);
 }
 
 void FDWatcher::run(EventMode mode)
@@ -31,13 +31,13 @@ Timer::Timer(TimePoint date, Callback callback, EventMode mode)
     : m_date{date}, m_callback{std::move(callback)}, m_mode(mode)
 {
     if (EventManager::has_instance())
-        EventManager::instance().m_timers.insert(this);
+        EventManager::instance().m_timers.push_back(this);
 }
 
 Timer::~Timer()
 {
     if (EventManager::has_instance())
-        EventManager::instance().m_timers.erase(this);
+        unordered_erase(EventManager::instance().m_timers, this);
 }
 
 void Timer::run(EventMode mode)
diff --git a/src/event_manager.hh b/src/event_manager.hh
index ed7a37c7..72245f0d 100644
--- a/src/event_manager.hh
+++ b/src/event_manager.hh
@@ -5,7 +5,7 @@
 #include "flags.hh"
 
 #include <chrono>
-#include <unordered_set>
+#include <vector>
 
 #include <sys/select.h>
 
@@ -83,8 +83,8 @@ public:
 private:
     friend class FDWatcher;
     friend class Timer;
-    std::unordered_set<FDWatcher*>  m_fd_watchers;
-    std::unordered_set<Timer*>      m_timers;
+    std::vector<FDWatcher*>  m_fd_watchers;
+    std::vector<Timer*>      m_timers;
     fd_set m_forced_fd;
 
     TimePoint        m_last;
diff --git a/src/insert_completer.cc b/src/insert_completer.cc
index 1e57afcb..a78c6073 100644
--- a/src/insert_completer.cc
+++ b/src/insert_completer.cc
@@ -93,14 +93,11 @@ InsertCompletion complete_word(const Buffer& buffer, ByteCoord cursor_pos)
     String current_word{begin, end};
 
     auto& word_db = get_word_db(buffer);
-    std::unordered_set<ComplAndDesc> matches;
-    auto bufmatches = subseq ? word_db.find_subsequence(prefix)
-                             : word_db.find_prefix(prefix);
-    for (auto& match : bufmatches)
-        matches.insert(ComplAndDesc{match, ""});
+    auto matches = subseq ? word_db.find_subsequence(prefix)
+                          : word_db.find_prefix(prefix);
 
     if (word_db.get_word_occurences(current_word) <= 1)
-        matches.erase(ComplAndDesc{current_word, ""});
+        unordered_erase(matches, current_word);
 
     if (other_buffers)
     {
@@ -109,17 +106,21 @@ InsertCompletion complete_word(const Buffer& buffer, ByteCoord cursor_pos)
             if (buf.get() == &buffer)
                 continue;
             auto& buf_word_db = get_word_db(*buf);
-            bufmatches = subseq ? buf_word_db.find_subsequence(prefix)
-                                : buf_word_db.find_prefix(prefix);
-            for (auto& match : bufmatches)
-                matches.insert(ComplAndDesc{match, ""});
+            auto bufmatches = subseq ? buf_word_db.find_subsequence(prefix)
+                                     : buf_word_db.find_prefix(prefix);
+            std::move(bufmatches.begin(), bufmatches.end(),
+                      std::back_inserter(matches));
         }
     }
-    matches.erase(ComplAndDesc{prefix, ""});
+    unordered_erase(matches, prefix);
+    std::sort(matches.begin(), matches.end());
+    matches.erase(std::unique(matches.begin(), matches.end()), matches.end());
+
     ComplAndDescList result;
-    std::copy(matches.begin(), matches.end(),
-              inserter(result, result.begin()));
-    std::sort(result.begin(), result.end());
+    result.reserve(matches.size());
+    for (auto& m : matches)
+        result.emplace_back(m, "");
+
     return { begin.coord(), cursor_pos, std::move(result), buffer.timestamp() };
 }
 
diff --git a/src/normal.cc b/src/normal.cc
index aeac320e..f19f88ec 100644
--- a/src/normal.cc
+++ b/src/normal.cc
@@ -973,6 +973,11 @@ void select_to_next_char(Context& context, NormalParams params)
     }, "select to next char","enter char to select to");
 }
 
+static bool is_basic_alpha(Codepoint c)
+{
+    return (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z');
+}
+
 void start_or_end_macro_recording(Context& context, NormalParams)
 {
     if (context.input_handler().is_recording())
@@ -980,7 +985,7 @@ void start_or_end_macro_recording(Context& context, NormalParams)
     else
         on_next_key_with_autoinfo(context, KeymapMode::None,
                                  [](Key key, Context& context) {
-            if (key.modifiers == Key::Modifiers::None and isalpha(key.key))
+            if (key.modifiers == Key::Modifiers::None and is_basic_alpha(key.key))
                 context.input_handler().start_recording(tolower(key.key));
         }, "record macro", "enter macro name ");
 }
@@ -995,18 +1000,19 @@ void replay_macro(Context& context, NormalParams params)
 {
     on_next_key_with_autoinfo(context, KeymapMode::None,
                              [params](Key key, Context& context) mutable {
-        if (key.modifiers == Key::Modifiers::None and isalpha(key.key))
+        if (key.modifiers == Key::Modifiers::None and is_basic_alpha(key.key))
         {
-            static std::unordered_set<char> running_macros;
+            static bool running_macros[26] = {};
             const char name = tolower(key.key);
-            if (contains(running_macros, name))
+            const size_t idx = (size_t)(name - 'a');
+            if (running_macros[idx])
                 throw runtime_error("recursive macros call detected");
 
             memoryview<String> reg_val = RegisterManager::instance()[name].values(context);
             if (not reg_val.empty())
             {
-                running_macros.insert(name);
-                auto stop = on_scope_end([&]{ running_macros.erase(name); });
+                running_macros[idx] = true;
+                auto stop = on_scope_end([&]{ running_macros[idx] = false; });
 
                 auto keys = parse_keys(reg_val[0]);
                 ScopedEdition edition(context);
diff --git a/src/option_types.hh b/src/option_types.hh
index b304f12b..739ab7a5 100644
--- a/src/option_types.hh
+++ b/src/option_types.hh
@@ -10,7 +10,6 @@
 #include <tuple>
 #include <vector>
 #include <unordered_map>
-#include <unordered_set>
 
 namespace Kakoune
 {
@@ -68,39 +67,6 @@ bool option_add(std::vector<T>& opt, const std::vector<T>& vec)
     return not vec.empty();
 }
 
-template<typename T>
-String option_to_string(const std::unordered_set<T>& opt)
-{
-    String res;
-    for (auto it = begin(opt); it != end(opt); ++it)
-    {
-        if (it != begin(opt))
-            res += list_separator;
-        res += escape(option_to_string(*it), list_separator, '\\');
-    }
-    return res;
-}
-
-template<typename T>
-void option_from_string(StringView str, std::unordered_set<T>& opt)
-{
-    opt.clear();
-    std::vector<String> elems = split(str, list_separator, '\\');
-    for (auto& elem: elems)
-    {
-        T opt_elem;
-        option_from_string(elem, opt_elem);
-        opt.insert(opt_elem);
-    }
-}
-
-template<typename T>
-bool option_add(std::unordered_set<T>& opt, const std::unordered_set<T>& set)
-{
-    std::copy(set.begin(), set.end(), std::inserter(opt, opt.begin()));
-    return not set.empty();
-}
-
 template<typename Key, typename Value>
 String option_to_string(const std::unordered_map<Key, Value>& opt)
 {
diff --git a/src/utils.hh b/src/utils.hh
index a71c7700..e4d392ff 100644
--- a/src/utils.hh
+++ b/src/utils.hh
@@ -7,7 +7,6 @@
 #include <algorithm>
 #include <memory>
 #include <vector>
-#include <unordered_set>
 
 namespace Kakoune
 {
@@ -113,10 +112,15 @@ bool contains(Container&& container, const T& value)
     return find(container, value) != end(container);
 }
 
-template<typename T1, typename T2>
-bool contains(const std::unordered_set<T1>& container, const T2& value)
+template<typename T, typename U>
+void unordered_erase(std::vector<T>& vec, U&& value)
 {
-    return container.find(value) != container.end();
+    auto it = find(vec, std::forward<U>(value));
+    if (it != vec.end())
+    {
+        std::swap(vec.back(), *it);
+        vec.pop_back();
+    }
 }
 
 template<typename Iterator, typename EndIterator, typename T>