diff options
Diffstat (limited to 'libbutl/prefix-map.txx')
| -rw-r--r-- | libbutl/prefix-map.txx | 42 |
1 files changed, 41 insertions, 1 deletions
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 } } |