From e3bf8b04654d4131be6ea4be670e66827b489d2e Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Thu, 18 Jan 2018 11:39:56 +0200 Subject: Move find_sup() from path_map to prefix_map and fix --- libbutl/path-map.mxx | 35 +++-------------------------- libbutl/prefix-map.mxx | 35 +++++++++++++++++++---------- libbutl/prefix-map.txx | 60 ++++++++++++++++++++++++++++++++++++++++++++++---- 3 files changed, 82 insertions(+), 48 deletions(-) (limited to 'libbutl') diff --git a/libbutl/path-map.mxx b/libbutl/path-map.mxx index c526a89..2697a48 100644 --- a/libbutl/path-map.mxx +++ b/libbutl/path-map.mxx @@ -126,39 +126,10 @@ LIBBUTL_MODEXPORT namespace butl // Note that the delimiter character is not used (is_delimiter() from // path_traits is used instead). // - template - struct path_map_impl: prefix_map - { - using base = prefix_map; - using base::base; - - using iterator = typename base::iterator; - using const_iterator = typename base::const_iterator; - - // Find the most qualified entry that is a superpath of this path. - // - iterator - find_sup (const P& p) - { - // Get the greatest less than, if any. We might still not be a sub. Note - // also that we still have to check the last element if upper_bound() - // returned end(). - // - auto i (this->upper_bound (p)); - return i == this->begin () || !p.sub ((--i)->first) ? this->end () : i; - } - - const_iterator - find_sup (const P& p) const - { - auto i (this->upper_bound (p)); - return i == this->begin () || !p.sub ((--i)->first) ? this->end () : i; - } - }; - template - using path_map = path_map_impl; + using path_map = prefix_map; template - using dir_path_map = path_map_impl; + using dir_path_map = + prefix_map; } diff --git a/libbutl/prefix-map.mxx b/libbutl/prefix-map.mxx index 95a4f3b..882f46e 100644 --- a/libbutl/prefix-map.mxx +++ b/libbutl/prefix-map.mxx @@ -28,18 +28,18 @@ import std.core; LIBBUTL_MODEXPORT namespace butl { - // A map of hierarchical "paths", e.g., 'foo.bar' or 'foo/bar' with - // the ability to retrieve a range of entries that have a specific - // prefix. The '.' and '/' above are the delimiter characters. + // A map of hierarchical "paths", e.g., 'foo.bar' or 'foo/bar' with the + // ability to retrieve a range of entries that have a specific prefix as + // well as finding the most qualified entry for specific path. The '.' and + // '/' above are the delimiter characters. // - // Note that as a special rule, the default implementation of - // compare_prefix treats empty key as everyone's prefix even if - // the paths don't start with the delimiter (useful to represent - // a "root path"). + // Note that as a special rule, the default implementation of compare_prefix + // treats empty key as everyone's prefix even if the paths don't start with + // the delimiter (useful to represent a "root path"). // - // Implementation-wise, the idea is to pretend that each key ends - // with the delimiter. This way we automatically avoid matching - // 'foobar' as having a prefix 'foo'. + // Implementation-wise, the idea is to pretend that each key ends with the + // delimiter. This way we automatically avoid matching 'foobar' as having a + // prefix 'foo'. // template struct compare_prefix; @@ -120,11 +120,22 @@ LIBBUTL_MODEXPORT namespace butl prefix_map_common (std::initializer_list i, delimiter_type d) : map_type (std::move (i), compare_type (d)) {} + // Find all the entries that are sub-prefixes of the specified prefix. + // std::pair - find_prefix (const key_type&); + find_sub (const key_type&); std::pair - find_prefix (const key_type&) const; + find_sub (const key_type&) const; + + // Find the most qualified entry that is a super-prefix of the specified + // prefix. + // + iterator + find_sup (const key_type&); + + const_iterator + find_sup (const key_type&) const; }; template ::delimiter_type D> diff --git a/libbutl/prefix-map.txx b/libbutl/prefix-map.txx index efcee88..fb50570 100644 --- a/libbutl/prefix-map.txx +++ b/libbutl/prefix-map.txx @@ -6,14 +6,16 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason. { template auto prefix_map_common:: - find_prefix (const key_type& k) -> std::pair + find_sub (const key_type& k) -> std::pair { + const auto& c (this->key_comp ()); + std::pair r; r.first = this->lower_bound (k); for (r.second = r.first; r.second != this->end (); ++r.second) { - if (!this->key_comp ().prefix (k, r.second->first)) + if (!c.prefix (k, r.second->first)) break; } @@ -22,18 +24,68 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason. template auto prefix_map_common:: - find_prefix (const key_type& k) const -> + find_sub (const key_type& k) const -> std::pair { + const auto& c (this->key_comp ()); + std::pair r; r.first = this->lower_bound (k); for (r.second = r.first; r.second != this->end (); ++r.second) { - if (!this->key_comp ().prefix (k, r.second->first)) + if (!c.prefix (k, r.second->first)) break; } return r; } + + template + auto prefix_map_common:: + find_sup (const key_type& k) -> iterator + { + // There seems to be only two possible algorithms here: + // + // 1. Iterate over the key: get progressively outer prefixes and look + // for a match in the map. + // + // 2. Iterate over entries: get the upper bound for the key and iterate + // backwards looking for a prefix. + // + // 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). + // + // 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). + // + const auto& c (this->key_comp ()); + + for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; ) + { + --i; + if (c.prefix (i->first, k)) + return i; + } + + return this->end (); + } + + template + auto prefix_map_common:: + find_sup (const key_type& k) const -> const_iterator + { + const auto& c (this->key_comp ()); + + for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; ) + { + --i; + if (c.prefix (i->first, k)) + return i; + } + + return this->end (); + } } -- cgit v1.1