Reimplement prefix_map::find_sup() to iterate over key, not entries

4 files changed, 77 insertions, 1 deletions

diff --git a/libbutl/path-map.mxx b/libbutl/path-map.mxx
index 2697a48..95fd54b 100644
--- a/libbutl/path-map.mxx
+++ b/libbutl/path-map.mxx
@@ -79,6 +79,16 @@ LIBBUTL_MODEXPORT namespace butl
                      root (ks) ? string_type () : ks);
     }
 
+    bool
+    prefix (key_type& k) const
+    {
+      if (k.empty ())
+        return false;
+
+      k.make_directory ();
+      return true;
+    }
+
   protected:
     bool
     prefix (const string_type& p, const string_type& k) const
diff --git a/libbutl/prefix-map.mxx b/libbutl/prefix-map.mxx
index 882f46e..85d7635 100644
--- a/libbutl/prefix-map.mxx
+++ b/libbutl/prefix-map.mxx
@@ -71,6 +71,20 @@ LIBBUTL_MODEXPORT namespace butl
          compare (p.c_str (), pn, k.c_str (), pn == kn ? pn : pn + 1) == 0);
     }
 
+    // If the key is not empty, convert the key to its prefix and return
+    // true. Return false otherwise.
+    //
+    bool
+    prefix (K& k) const
+    {
+      if (k.empty ())
+        return false;
+
+      size_type p (k.rfind (d_));
+      k.resize (p != K::npos ? p : 0);
+      return true;
+    }
+
   protected:
     int
     compare (const C* x, size_type xn,
diff --git a/libbutl/prefix-map.txx b/libbutl/prefix-map.txx
index fb50570..fc94409 100644
--- a/libbutl/prefix-map.txx
+++ b/libbutl/prefix-map.txx
@@ -55,12 +55,15 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
     //
     // The drawback of the first approach is that we have to create a new key
     // which will most likely involve a memory allocation (we can probably
-    // limit it to a single allocation by reusing the key).
+    // limit it to a single allocation by reusing the key instance).
     //
     // The drawback of the second approch is that we may have a lot of entries
     // between the lower bound and the prefix (in contrast, keys normally only
     // have a handful of components).
     //
+    // Tests have shown that (2) can be significantly faster than (1).
+    //
+#if 0
     const auto& c (this->key_comp ());
 
     for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; )
@@ -71,12 +74,32 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
     }
 
     return this->end ();
+#else
+    // First look for the exact match before making any copies.
+    //
+    auto i (this->find (k)), e (this->end ());
+
+    if (i == e)
+    {
+      const auto& c (this->key_comp ());
+
+      for (key_type p (k); c.prefix (p); )
+      {
+        i = this->find (p);
+        if (i != e)
+          break;
+      }
+    }
+
+    return i;
+#endif
   }
 
   template <typename M>
   auto prefix_map_common<M>::
   find_sup (const key_type& k) const -> const_iterator
   {
+#if 0
     const auto& c (this->key_comp ());
 
     for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; )
@@ -87,5 +110,22 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
     }
 
     return this->end ();
+#else
+    auto i (this->find (k)), e (this->end ());
+
+    if (i == e)
+    {
+      const auto& c (this->key_comp ());
+
+      for (key_type p (k); c.prefix (p); )
+      {
+        i = this->find (p);
+        if (i != e)
+          break;
+      }
+    }
+
+    return i;
+#endif
   }
 }
diff --git a/tests/prefix-map/driver.cxx b/tests/prefix-map/driver.cxx
index 2fb8a99..70afc30 100644
--- a/tests/prefix-map/driver.cxx
+++ b/tests/prefix-map/driver.cxx
@@ -201,4 +201,16 @@ main ()
       assert (i != e && i->second == 7);
     }
   }
+
+  {
+    // Test the special empty prefix logic.
+    //
+    pm m ({{"", 1}});
+
+    auto e (m.end ());
+
+    assert (m.find_sup ("") != e);
+    assert (m.find_sup ("foo") != e);
+    assert (m.find_sup ("foo.bar") != e);
+  }
 }