From bf1e5b6b8b73fed4ab1bfb40a1f362c255fe7029 Mon Sep 17 00:00:00 2001
From: Boris Kolpackov <boris@codesynthesis.com>
Date: Fri, 5 Nov 2021 12:39:26 +0200
Subject: Improve prefix multiple support

---
 libbutl/path-map.hxx   |  8 ++++++++
 libbutl/prefix-map.hxx | 33 ++++++++++++++++++++++++++++--
 libbutl/prefix-map.txx | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++
 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
+  }
 }
-- 
cgit v1.1