diff options
author | Boris Kolpackov <boris@codesynthesis.com> | 2018-01-19 09:06:39 +0200 |
---|---|---|
committer | Boris Kolpackov <boris@codesynthesis.com> | 2018-01-19 09:06:39 +0200 |
commit | 3053f55528dbecb08ddb55fa94546a98af06e3e1 (patch) | |
tree | 6f9dc9fb9fe6c5593f1304f884d5c49c89bcad0b /libbutl/prefix-map.txx | |
parent | 89bc63fb386f0e4d6e2b21c0d806da1e8de0a34d (diff) |
Reimplement prefix_map::find_sup() to iterate over key, not entries
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 } } |