aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--libbutl/path-map.mxx10
-rw-r--r--libbutl/prefix-map.mxx14
-rw-r--r--libbutl/prefix-map.txx42
-rw-r--r--tests/prefix-map/driver.cxx12
4 files changed, 77 insertions, 1 deletions
diff --git a/libbutl/path-map.mxx b/libbutl/path-map.mxx
index 2697a48..95fd54b 100644
--- a/libbutl/path-map.mxx
+++ b/libbutl/path-map.mxx
@@ -79,6 +79,16 @@ LIBBUTL_MODEXPORT namespace butl
root (ks) ? string_type () : ks);
}
+ bool
+ prefix (key_type& k) const
+ {
+ if (k.empty ())
+ return false;
+
+ k.make_directory ();
+ return true;
+ }
+
protected:
bool
prefix (const string_type& p, const string_type& k) const
diff --git a/libbutl/prefix-map.mxx b/libbutl/prefix-map.mxx
index 882f46e..85d7635 100644
--- a/libbutl/prefix-map.mxx
+++ b/libbutl/prefix-map.mxx
@@ -71,6 +71,20 @@ LIBBUTL_MODEXPORT namespace butl
compare (p.c_str (), pn, k.c_str (), pn == kn ? pn : pn + 1) == 0);
}
+ // If the key is not empty, convert the key to its prefix and return
+ // true. Return false otherwise.
+ //
+ bool
+ prefix (K& k) const
+ {
+ if (k.empty ())
+ return false;
+
+ size_type p (k.rfind (d_));
+ k.resize (p != K::npos ? p : 0);
+ return true;
+ }
+
protected:
int
compare (const C* x, size_type xn,
diff --git a/libbutl/prefix-map.txx b/libbutl/prefix-map.txx
index fb50570..fc94409 100644
--- a/libbutl/prefix-map.txx
+++ b/libbutl/prefix-map.txx
@@ -55,12 +55,15 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
//
// 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).
+ // limit it to a single allocation by reusing the key instance).
//
// 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).
//
+ // Tests have shown that (2) can be significantly faster than (1).
+ //
+#if 0
const auto& c (this->key_comp ());
for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; )
@@ -71,12 +74,32 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
}
return this->end ();
+#else
+ // First look for the exact match before making any copies.
+ //
+ auto i (this->find (k)), e (this->end ());
+
+ if (i == e)
+ {
+ const auto& c (this->key_comp ());
+
+ for (key_type p (k); c.prefix (p); )
+ {
+ i = this->find (p);
+ if (i != e)
+ break;
+ }
+ }
+
+ return i;
+#endif
}
template <typename M>
auto prefix_map_common<M>::
find_sup (const key_type& k) const -> const_iterator
{
+#if 0
const auto& c (this->key_comp ());
for (auto i (this->upper_bound (k)), b (this->begin ()); i != b; )
@@ -87,5 +110,22 @@ LIBBUTL_MODEXPORT namespace butl //@@ MOD Clang needs this for some reason.
}
return this->end ();
+#else
+ auto i (this->find (k)), e (this->end ());
+
+ if (i == e)
+ {
+ const auto& c (this->key_comp ());
+
+ for (key_type p (k); c.prefix (p); )
+ {
+ i = this->find (p);
+ if (i != e)
+ break;
+ }
+ }
+
+ return i;
+#endif
}
}
diff --git a/tests/prefix-map/driver.cxx b/tests/prefix-map/driver.cxx
index 2fb8a99..70afc30 100644
--- a/tests/prefix-map/driver.cxx
+++ b/tests/prefix-map/driver.cxx
@@ -201,4 +201,16 @@ main ()
assert (i != e && i->second == 7);
}
}
+
+ {
+ // Test the special empty prefix logic.
+ //
+ pm m ({{"", 1}});
+
+ auto e (m.end ());
+
+ assert (m.find_sup ("") != e);
+ assert (m.find_sup ("foo") != e);
+ assert (m.find_sup ("foo.bar") != e);
+ }
}