aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBoris Kolpackov <boris@codesynthesis.com>2021-11-05 12:39:26 +0200
committerBoris Kolpackov <boris@codesynthesis.com>2021-11-05 12:39:26 +0200
commitbf1e5b6b8b73fed4ab1bfb40a1f362c255fe7029 (patch)
tree105ce0dd13f67f80f932958bb16323f8067b67d3
parent33b8b378fae1daa02550bc53c5e43c4dfc6819de (diff)
Improve prefix multiple support
-rw-r--r--libbutl/path-map.hxx8
-rw-r--r--libbutl/prefix-map.hxx33
-rw-r--r--libbutl/prefix-map.txx54
3 files changed, 93 insertions, 2 deletions
diff --git a/libbutl/path-map.hxx b/libbutl/path-map.hxx
index a7b3870..e3d776a 100644
--- a/libbutl/path-map.hxx
+++ b/libbutl/path-map.hxx
@@ -125,4 +125,12 @@ namespace butl
template <typename T>
using dir_path_map =
prefix_map<dir_path, T, dir_path::traits_type::directory_separator>;
+
+ template <typename T>
+ using path_multimap =
+ prefix_multimap<path, T, path::traits_type::directory_separator>;
+
+ template <typename T>
+ using dir_path_multimap =
+ prefix_multimap<dir_path, T, dir_path::traits_type::directory_separator>;
}
diff --git a/libbutl/prefix-map.hxx b/libbutl/prefix-map.hxx
index 9706ebd..0895d96 100644
--- a/libbutl/prefix-map.hxx
+++ b/libbutl/prefix-map.hxx
@@ -135,7 +135,6 @@ namespace butl
const_iterator
find_sup (const key_type&) const;
-
// As above but additionally evaluate a predicate on each matching entry
// returning the one for which it returns true.
//
@@ -148,6 +147,26 @@ namespace butl
find_sup_if (const key_type&, P) const;
};
+ template <typename M>
+ struct prefix_multimap_common: prefix_map_common<M>
+ {
+ typedef M map_type;
+ typedef typename map_type::key_type key_type;
+ typedef typename map_type::iterator iterator;
+ typedef typename map_type::const_iterator const_iterator;
+
+ using prefix_map_common<M>::prefix_map_common;
+
+ // Find the most qualified entries that are super-prefixes of the
+ // specified prefix.
+ //
+ std::pair<iterator, iterator>
+ sup_range (const key_type&);
+
+ std::pair<const_iterator, const_iterator>
+ sup_range (const key_type&) const;
+ };
+
template <typename M, typename prefix_map_common<M>::delimiter_type D>
struct prefix_map_impl: prefix_map_common<M>
{
@@ -158,6 +177,16 @@ namespace butl
: prefix_map_common<M> (std::move (i), D) {}
};
+ template <typename M, typename prefix_map_common<M>::delimiter_type D>
+ struct prefix_multimap_impl: prefix_multimap_common<M>
+ {
+ typedef typename prefix_multimap_common<M>::value_type value_type;
+
+ prefix_multimap_impl (): prefix_multimap_common<M> (D) {}
+ prefix_multimap_impl (std::initializer_list<value_type> i)
+ : prefix_multimap_common<M> (std::move (i), D) {}
+ };
+
template <typename K,
typename T,
typename compare_prefix<K>::delimiter_type D>
@@ -167,7 +196,7 @@ namespace butl
typename T,
typename compare_prefix<K>::delimiter_type D>
using prefix_multimap =
- prefix_map_impl<std::multimap<K, T, compare_prefix<K>>, D>;
+ prefix_multimap_impl<std::multimap<K, T, compare_prefix<K>>, D>;
}
#include <libbutl/prefix-map.txx>
diff --git a/libbutl/prefix-map.txx b/libbutl/prefix-map.txx
index 502119a..80664bf 100644
--- a/libbutl/prefix-map.txx
+++ b/libbutl/prefix-map.txx
@@ -197,4 +197,58 @@ namespace butl
return i;
#endif
}
+
+ template <typename M>
+ auto prefix_multimap_common<M>::
+ sup_range (const key_type& k) -> std::pair<iterator, iterator>
+ {
+#if 0
+ // TODO (see above).
+#else
+ // First look for the exact match before making any copies.
+ //
+ auto r (this->equal_range (k));
+
+ if (r.first == r.second)
+ {
+ const auto& c (this->key_comp ());
+
+ for (key_type p (k); c.prefix (p); )
+ {
+ r = this->equal_range (p);
+ if (r.first != r.second)
+ break;
+ }
+ }
+
+ return r;
+#endif
+ }
+
+ template <typename M>
+ auto prefix_multimap_common<M>::
+ sup_range (const key_type& k) const -> std::pair<const_iterator, const_iterator>
+ {
+#if 0
+ // TODO (see above).
+#else
+ // First look for the exact match before making any copies.
+ //
+ auto r (this->equal_range (k));
+
+ if (r.first == r.second)
+ {
+ const auto& c (this->key_comp ());
+
+ for (key_type p (k); c.prefix (p); )
+ {
+ r = this->equal_range (p);
+ if (r.first != r.second)
+ break;
+ }
+ }
+
+ return r;
+#endif
+ }
}