Move prefix-map from build2 to libbutl

8 files changed, 42 insertions, 368 deletions

diff --git a/build/path-map b/build/path-map
index b95f2a6..8355ccc 100644
--- a/build/path-map
+++ b/build/path-map
@@ -5,11 +5,15 @@
 #ifndef BUILD_PATH_MAP
 #define BUILD_PATH_MAP
 
+#include <butl/prefix-map>
+
 #include <build/path>
-#include <build/prefix-map>
 
-namespace build
+namespace butl
 {
+
+  // @@ Remove butl:: when move to libbutl.
+
   // prefix_map for paths
   //
   // The paths should be normalized.
@@ -25,9 +29,9 @@ namespace build
   // it.
   //
   template <typename C, typename K>
-  struct compare_prefix<basic_path<C, K>>: compare_prefix<std::basic_string<C>>
+  struct compare_prefix<build::basic_path<C, K>>: compare_prefix<std::basic_string<C>>
   {
-    typedef basic_path<C, K> key_type;
+    typedef build::basic_path<C, K> key_type;
 
     typedef C delimiter_type;
     typedef std::basic_string<C> string_type;
@@ -69,13 +73,16 @@ namespace build
 #endif
     }
   };
+}
 
+namespace build
+{
   template <typename T>
-  using path_map = prefix_map<path, T, path::traits::directory_separator>;
+  using path_map = butl::prefix_map<path, T, path::traits::directory_separator>;
 
   template <typename T>
   using dir_path_map =
-    prefix_map<dir_path, T, dir_path::traits::directory_separator>;
+    butl::prefix_map<dir_path, T, dir_path::traits::directory_separator>;
 }
 
 #endif // BUILD_PATH_MAP
diff --git a/build/prefix-map b/build/prefix-map
deleted file mode 100644
index 885d284..0000000
--- a/build/prefix-map
+++ /dev/null
@@ -1,140 +0,0 @@
-// file      : build/prefix-map -*- C++ -*-
-// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
-// license   : MIT; see accompanying LICENSE file
-
-#ifndef BUILD_PREFIX_MAP
-#define BUILD_PREFIX_MAP
-
-#include <map>
-#include <string>
-#include <utility>   // move()
-#include <algorithm> // min()
-
-namespace build
-{
-  // 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.
-  //
-  // 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'.
-  //
-  template <typename K>
-  struct compare_prefix;
-
-  template <typename C>
-  struct compare_prefix<std::basic_string<C>>
-  {
-    typedef std::basic_string<C> K;
-
-    typedef C delimiter_type;
-    typedef typename K::size_type size_type;
-    typedef typename K::traits_type traits_type;
-
-    explicit
-    compare_prefix (delimiter_type d): d_ (d) {}
-
-    bool
-    operator() (const K& x, const K& y) const
-    {
-      return compare (x.c_str (), x.size (), y.c_str (), y.size ()) < 0;
-    }
-
-    // Note: doesn't check for k.size () being at least p.size ().
-    //
-    bool
-    prefix (const K& p, const K& k) const
-    {
-      size_type pn (p.size ());
-      return pn == 0 || // Empty key is always a prefix.
-        compare (
-          p.c_str (), pn, k.c_str (), pn == k.size () ? pn : pn + 1) == 0;
-    }
-
-  protected:
-    int
-    compare (const C* x, size_type xn,
-             const C* y, size_type yn) const
-    {
-      size_type n (std::min (xn, yn));
-      int r (traits_type::compare (x, y, n));
-
-      if (r == 0)
-      {
-        // Pretend there is the delimiter characters at the end of the
-        // shorter string.
-        //
-        char xc (xn > n ? x[n] : (xn++, d_));
-        char yc (yn > n ? y[n] : (yn++, d_));
-        r = traits_type::compare (&xc, &yc, 1);
-
-        // If we are still equal, then compare the lengths.
-        //
-        if (r == 0)
-          r = (xn == yn ? 0 : (xn < yn ? -1 : 1));
-      }
-
-      return r;
-    }
-
-  private:
-    delimiter_type d_;
-  };
-
-  template <typename M>
-  struct prefix_map_common: M
-  {
-    typedef M map_type;
-    typedef typename map_type::key_type key_type;
-    typedef typename map_type::value_type value_type;
-    typedef typename map_type::key_compare compare_type;
-    typedef typename compare_type::delimiter_type delimiter_type;
-
-    typedef typename map_type::iterator iterator;
-    typedef typename map_type::const_iterator const_iterator;
-
-    explicit
-    prefix_map_common (delimiter_type d)
-        : map_type (compare_type (d)) {}
-
-    prefix_map_common (std::initializer_list<value_type> i, delimiter_type d)
-        : map_type (std::move (i), compare_type (d)) {}
-
-    std::pair<iterator, iterator>
-    find_prefix (const key_type&);
-
-    std::pair<const_iterator, const_iterator>
-    find_prefix (const key_type&) const;
-  };
-
-  template <typename M, typename prefix_map_common<M>::delimiter_type D>
-  struct prefix_map_impl: prefix_map_common<M>
-  {
-    typedef typename prefix_map_common<M>::value_type value_type;
-
-    prefix_map_impl (): prefix_map_common<M> (D) {}
-    prefix_map_impl (std::initializer_list<value_type> i)
-        : prefix_map_common<M> (std::move (i), D) {}
-  };
-
-  template <typename K,
-            typename T,
-            typename compare_prefix<K>::delimiter_type D>
-  using prefix_map = prefix_map_impl<std::map<K, T, compare_prefix<K>>, D>;
-
-  template <typename K,
-            typename T,
-            typename compare_prefix<K>::delimiter_type D>
-  using prefix_multimap =
-    prefix_map_impl<std::multimap<K, T, compare_prefix<K>>, D>;
-}
-
-#include <build/prefix-map.txx>
-
-#endif // BUILD_PREFIX_MAP
diff --git a/build/prefix-map.txx b/build/prefix-map.txx
deleted file mode 100644
index 528fd3c..0000000
--- a/build/prefix-map.txx
+++ /dev/null
@@ -1,43 +0,0 @@
-// file      : build/prefix-map.txx -*- C++ -*-
-// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
-// license   : MIT; see accompanying LICENSE file
-
-namespace build
-{
-  template <typename M>
-  auto prefix_map_common<M>::
-  find_prefix (const key_type& k) -> std::pair<iterator, iterator>
-  {
-    std::pair<iterator, iterator> 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))
-        break;
-    }
-
-    return r;
-  }
-
-  template <typename M>
-  auto prefix_map_common<M>::
-  find_prefix (const key_type& k) const ->
-    std::pair<const_iterator, const_iterator>
-  {
-    std::pair<const_iterator, const_iterator> 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))
-        break;
-    }
-
-    return r;
-  }
-}
diff --git a/build/rule b/build/rule
index 32e8c66..04d3650 100644
--- a/build/rule
+++ b/build/rule
@@ -10,9 +10,10 @@
 #include <functional>     // reference_wrapper
 #include <unordered_map>
 
+#include <butl/prefix-map>
+
 #include <build/target>
 #include <build/operation>
-#include <build/prefix-map>
 
 namespace build
 {
@@ -28,7 +29,7 @@ namespace build
 
   using target_rule_map = std::unordered_map<
     std::type_index,
-    prefix_multimap<std::string, std::reference_wrapper<rule>, '.'>>;
+    butl::prefix_multimap<std::string, std::reference_wrapper<rule>, '.'>>;
 
   using operation_rule_map = std::unordered_map<operation_id, target_rule_map>;
 
diff --git a/build/variable b/build/variable
index 0cd411d..42f0787 100644
--- a/build/variable
+++ b/build/variable
@@ -14,9 +14,10 @@
 #include <typeindex>
 #include <unordered_set>
 
+#include <butl/prefix-map>
+
 #include <build/path>
 #include <build/name>
-#include <build/prefix-map>
 
 namespace build
 {
@@ -207,24 +208,10 @@ namespace std
   };
 }
 
-namespace build
+namespace butl
 {
-  // variable_pool
-  //
-  struct variable_set: std::unordered_set<variable>
-  {
-    // @@ Need to check/set type?
-    //
-    const variable&
-    find (std::string name) {return *emplace (std::move (name)).first;}
-  };
-
-  extern variable_set variable_pool;
-
-  // variable_map
-  //
   template <>
-  struct compare_prefix<variable_cref>: compare_prefix<std::string>
+  struct compare_prefix<build::variable_cref>: compare_prefix<std::string>
   {
     typedef compare_prefix<std::string> base;
 
@@ -232,22 +219,38 @@ namespace build
     compare_prefix (char d): base (d) {}
 
     bool
-    operator() (const variable& x, const variable& y) const
+    operator() (const build::variable& x, const build::variable& y) const
     {
       return base::operator() (x.name, y.name);
     }
 
     bool
-    prefix (const variable& p, const variable& k) const
+    prefix (const build::variable& p, const build::variable& k) const
     {
       return base::prefix (p.name, k.name);
     }
   };
+}
 
-  struct variable_map: prefix_map<variable_cref, value_ptr, '.'>
+namespace build
+{
+  // variable_pool
+  //
+  struct variable_set: std::unordered_set<variable>
   {
-    typedef prefix_map<variable_cref, value_ptr, '.'> base;
+    // @@ Need to check/set type?
+    //
+    const variable&
+    find (std::string name) {return *emplace (std::move (name)).first;}
+  };
+
+  extern variable_set variable_pool;
 
+  // variable_map
+  //
+  using variable_map_base = butl::prefix_map<variable_cref, value_ptr, '.'>;
+  struct variable_map: variable_map_base
+  {
     value_proxy
     operator[] (const variable& var) const
     {
@@ -268,7 +271,7 @@ namespace build
     value_proxy
     assign (const variable& var)
     {
-      return value_proxy (&base::operator[] (var), this);
+      return value_proxy (&variable_map_base::operator[] (var), this);
     }
 
     value_proxy
diff --git a/tests/build/buildfile b/tests/build/buildfile
index 99a0a6f..19ea46e 100644
--- a/tests/build/buildfile
+++ b/tests/build/buildfile
@@ -1,4 +1,4 @@
-d=path/ prefix-map/
+d=path/
 
 .: $d
 include $d
diff --git a/tests/build/prefix-map/buildfile b/tests/build/prefix-map/buildfile
deleted file mode 100644
index a72d02f..0000000
--- a/tests/build/prefix-map/buildfile
+++ /dev/null
@@ -1 +0,0 @@
-exe{driver}: cxx{driver}
diff --git a/tests/build/prefix-map/driver.cxx b/tests/build/prefix-map/driver.cxx
deleted file mode 100644
index bbbd472..0000000
--- a/tests/build/prefix-map/driver.cxx
+++ /dev/null
@@ -1,153 +0,0 @@
-// file      : tests/build/prefix-map/driver.cxx -*- C++ -*-
-// copyright : Copyright (c) 2014-2015 Code Synthesis Ltd
-// license   : MIT; see accompanying LICENSE file
-
-#include <string>
-#include <cassert>
-#include <iostream>
-
-#include <build/prefix-map>
-
-using namespace std;
-using namespace build;
-
-int
-main ()
-{
-  typedef prefix_map<string, int, '.'> pm;
-
-  {
-    const pm m;
-
-    {
-      auto r (m.find_prefix (""));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo"));
-      assert (r.first == r.second);
-    }
-  }
-
-  {
-    pm m {{{"foo", 1}}};
-
-    {
-      auto r (m.find_prefix (""));
-      assert (r.first != r.second && r.first->second == 1 &&
-              ++r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fo"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fox"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fooo"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo.bar"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo"));
-      assert (r.first != r.second && r.first->second == 1 &&
-              ++r.first == r.second);
-    }
-  }
-
-  {
-    pm m {{{"foo", 1}, {"bar", 2}}};
-
-    {
-      auto r (m.find_prefix (""));
-      assert (r.first != r.second && r.first->second == 2 &&
-              ++r.first != r.second && r.first->second == 1 &&
-              ++r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fo"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fox"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fooo"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo.bar"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo"));
-      assert (r.first != r.second && r.first->second == 1 &&
-              ++r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("bar"));
-      assert (r.first != r.second && r.first->second == 2 &&
-              ++r.first == r.second);
-    }
-  }
-
-  {
-    pm m (
-      {{"boo", 1},
-       {"foo", 2}, {"fooa", 3}, {"foo.bar", 4}, {"foo.fox", 5},
-       {"xoo", 5}});
-
-    {
-      auto r (m.find_prefix ("fo"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fox"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("fooo"));
-      assert (r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo.bar"));
-      assert (r.first != r.second && r.first->second == 4 &&
-              ++r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo.fox"));
-      assert (r.first != r.second && r.first->second == 5 &&
-              ++r.first == r.second);
-    }
-
-    {
-      auto r (m.find_prefix ("foo"));
-      assert (r.first != r.second && r.first->second == 2 &&
-              ++r.first != r.second && r.first->second == 4 &&
-              ++r.first != r.second && r.first->second == 5 &&
-              ++r.first == r.second);
-    }
-  }
-}