aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--build/prefix_map119
-rw-r--r--build/prefix_map.txx42
-rw-r--r--tests/build/prefix_map/buildfile2
-rw-r--r--tests/build/prefix_map/driver.cxx156
4 files changed, 319 insertions, 0 deletions
diff --git a/build/prefix_map b/build/prefix_map
new file mode 100644
index 0000000..13388b2
--- /dev/null
+++ b/build/prefix_map
@@ -0,0 +1,119 @@
+// file : build/prefix_map -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// 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
+{
+ template <typename K>
+ struct compare_prefix;
+
+ template <typename C>
+ struct compare_prefix<std::basic_string<C>>
+ {
+ typedef std::basic_string<C> K;
+
+ typedef C char_type;
+ typedef typename K::size_type size_type;
+ typedef typename K::traits_type traits_type;
+
+ explicit
+ compare_prefix (C 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 compare (
+ p.c_str (), pn, k.c_str (), pn == k.size () ? pn : pn + 1) == 0;
+ }
+
+ 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:
+ C d_;
+ };
+
+ // 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.
+ //
+ // 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 M>
+ struct prefix_map_impl: 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 map_type::iterator iterator;
+ typedef typename map_type::const_iterator const_iterator;
+
+ explicit
+ prefix_map_impl (typename compare_type::char_type delimiter)
+ : map_type (compare_type (delimiter)) {}
+
+ prefix_map_impl (std::initializer_list<value_type> init,
+ typename compare_type::char_type delimiter)
+ : map_type (std::move (init), compare_type (delimiter)) {}
+
+ std::pair<iterator, iterator>
+ find (const key_type&);
+
+ std::pair<const_iterator, const_iterator>
+ find (const key_type&) const;
+ };
+
+ template <typename K, typename T>
+ using prefix_map = prefix_map_impl<std::map<K, T, compare_prefix<K>>>;
+
+ template <typename K, typename T>
+ using prefix_multimap =
+ prefix_map_impl<std::multimap<K, T, compare_prefix<K>>>;
+}
+
+#include <build/prefix_map.txx>
+
+#endif // BUILD_PREFIX_MAP
diff --git a/build/prefix_map.txx b/build/prefix_map.txx
new file mode 100644
index 0000000..17a8ca0
--- /dev/null
+++ b/build/prefix_map.txx
@@ -0,0 +1,42 @@
+// file : build/prefix_map.txx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// license : MIT; see accompanying LICENSE file
+
+namespace build
+{
+ template <typename M>
+ auto prefix_map_impl<M>::
+ find (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_impl<M>::
+ find (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/tests/build/prefix_map/buildfile b/tests/build/prefix_map/buildfile
new file mode 100644
index 0000000..dbef7db
--- /dev/null
+++ b/tests/build/prefix_map/buildfile
@@ -0,0 +1,2 @@
+exe{driver}: obj{driver}
+obj{driver}: cxx{driver}
diff --git a/tests/build/prefix_map/driver.cxx b/tests/build/prefix_map/driver.cxx
new file mode 100644
index 0000000..ba9478c
--- /dev/null
+++ b/tests/build/prefix_map/driver.cxx
@@ -0,0 +1,156 @@
+// file : tests/build/prefix_map/driver.cxx -*- C++ -*-
+// copyright : Copyright (c) 2014-2015 Code Synthesis Tools CC
+// 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 (""));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("foo"));
+ assert (r.first == r.second);
+ }
+ }
+
+ {
+ pm m {{{"foo", 1}}, '.'};
+
+ {
+ auto r (m.find (""));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fo"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fox"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fooo"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("foo.bar"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("foo"));
+ assert (r.first != r.second && r.first->second == 1 &&
+ ++r.first == r.second);
+ }
+ }
+
+ {
+ pm m {{{"foo", 1}, {"bar", 2}}, '.'};
+
+ {
+ auto r (m.find (""));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fo"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fox"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fooo"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("foo.bar"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("foo"));
+ assert (r.first != r.second && r.first->second == 1 &&
+ ++r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("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 (""));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fo"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fox"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("fooo"));
+ assert (r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("foo.bar"));
+ assert (r.first != r.second && r.first->second == 4 &&
+ ++r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("foo.fox"));
+ assert (r.first != r.second && r.first->second == 5 &&
+ ++r.first == r.second);
+ }
+
+ {
+ auto r (m.find ("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);
+ }
+ }
+}
generated by cgit v1.1 at 2024-11-04 14:04:19 +0000