Use list instead of unordered_set in regex line_pool

2 files changed, 22 insertions, 4 deletions

diff --git a/libbuild2/script/regex.cxx b/libbuild2/script/regex.cxx
index 3f796b6..11ff8a1 100644
--- a/libbuild2/script/regex.cxx
+++ b/libbuild2/script/regex.cxx
@@ -75,15 +75,29 @@ namespace build2
                   string::traits_type::find (ex, 4, c) != nullptr)));
       }
 
+      template <typename S>
+      static inline const char_string*
+      find_or_insert (line_pool& p, S&& s)
+      {
+        auto i (find (p.strings.begin (), p.strings.end (), s));
+        if (i == p.strings.end ())
+        {
+          p.strings.push_front (forward<S> (s));
+          i = p.strings.begin ();
+        }
+
+        return &*i;
+      }
+
       line_char::
       line_char (const char_string& s, line_pool& p)
-          : line_char (&(*p.strings.emplace (s).first))
+          : line_char (find_or_insert (p, s))
       {
       }
 
       line_char::
       line_char (char_string&& s, line_pool& p)
-          : line_char (&(*p.strings.emplace (move (s)).first))
+          : line_char (find_or_insert (p, move (s)))
       {
       }
 
diff --git a/libbuild2/script/regex.hxx b/libbuild2/script/regex.hxx
index e043c99..f6cf566 100644
--- a/libbuild2/script/regex.hxx
+++ b/libbuild2/script/regex.hxx
@@ -9,7 +9,6 @@
 #include <locale>
 #include <string>        // basic_string
 #include <type_traits>   // make_unsigned, enable_if, is_*
-#include <unordered_set>
 
 #include <libbuild2/types.hxx>
 #include <libbuild2/utility.hxx>
@@ -59,7 +58,12 @@ namespace build2
         // Note that we assume the pool can be moved without invalidating
         // pointers to any already pooled entities.
         //
-        std::unordered_set<char_string> strings;
+        // Note that we used to use unordered_set for strings but (1) there is
+        // no general expectation that we will have many identical strings and
+        // (2) the number of strings is not expected to be large. So that felt
+        // like an overkill and we now use a list with linear search.
+        //
+        std::list<char_string> strings;
         std::list<char_regex> regexes;
       };