diff options
| -rw-r--r-- | libbutl/path-map.mxx | 10 | ||||
| -rw-r--r-- | libbutl/prefix-map.mxx | 14 | ||||
| -rw-r--r-- | libbutl/prefix-map.txx | 42 | ||||
| -rw-r--r-- | tests/prefix-map/driver.cxx | 12 |
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); + } } |