1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
// file : libbutl/path-map.hxx -*- C++ -*-
// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd
// license : MIT; see accompanying LICENSE file
#ifndef LIBBUTL_PATH_MAP_HXX
#define LIBBUTL_PATH_MAP_HXX
#include <algorithm> // min()
#include <libbutl/path.hxx>
#include <libbutl/prefix-map.hxx>
namespace butl
{
// prefix_map for filesystem paths
//
// Important: the paths should be normalized but can use different case
// on case-insensitive platforms.
//
// Note that the path's representation of POSIX root ('/') is
// inconsistent in that we have a trailing delimiter at the end of
// the path (its "proper" representation would have been an empty
// string but that would have clashed with empty paths). To work
// around this snag, this implementation, during key comparison,
// detects '/' and treats it as empty. Note that the map will
// still store the key as you have first inserted it. So if you
// want a particular representation (i.e., empty or '/'), pre-
// populate the map with it.
//
template <typename C, typename K>
struct compare_prefix<basic_path<C, K>>
{
typedef basic_path<C, K> key_type;
typedef C delimiter_type;
typedef typename key_type::string_type string_type;
typedef typename key_type::size_type size_type;
typedef typename key_type::traits traits_type;
explicit
compare_prefix (delimiter_type) {}
bool
operator() (const key_type& x, const key_type& y) const
{
const string_type& xs (x.string ());
const string_type& ys (y.string ());
return compare (xs.c_str (),
root (xs) ? 0 : xs.size (),
ys.c_str (),
root (ys) ? 0 : ys.size ()) < 0;
}
bool
prefix (const key_type& p, const key_type& k) const
{
const string_type& ps (p.string ());
const string_type& ks (k.string ());
return prefix (root (ps) ? string_type () : ps,
root (ks) ? string_type () : ks);
}
protected:
bool
prefix (const string_type& p, const string_type& k) const
{
// The same code as in prefix_map but using our compare().
//
size_type pn (p.size ()), kn (k.size ());
return pn == 0 || // Empty key is always a prefix.
(pn <= kn &&
compare (p.c_str (), pn, k.c_str (), pn == kn ? 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, n, y, n));
if (r == 0)
{
// Pretend there is a delimiter characters at the end of the
// shorter string.
//
char xc (xn > n ? x[n] : (xn++, traits_type::directory_separator));
char yc (yn > n ? y[n] : (yn++, traits_type::directory_separator));
r = traits_type::compare (&xc, 1, &yc, 1);
// If we are still equal, then compare the lengths.
//
if (r == 0)
r = (xn == yn ? 0 : (xn < yn ? -1 : 1));
}
return r;
}
static bool
root (const string_type& p)
{
return p.size () == 1 && key_type::traits::is_separator (p[0]);
}
};
// Note that the delimiter character is not used (is_delimiter() from
// path_traits is used instead).
//
template <typename P, typename T>
struct path_map_impl: prefix_map<P, T, P::traits::directory_separator>
{
using base = prefix_map<P, T, P::traits::directory_separator>;
using base::base;
using iterator = typename base::iterator;
using const_iterator = typename base::const_iterator;
// Find the most qualified entry of which this path is a sub-path.
//
iterator
find_sub (const P& p)
{
// Get the greatest less than, if any. We might still not be a sub. Note
// also that we still have to check the last element if upper_bound()
// returned end().
//
auto i (this->upper_bound (p));
return i == this->begin () || !p.sub ((--i)->first) ? this->end () : i;
}
const_iterator
find_sub (const P& p) const
{
auto i (this->upper_bound (p));
return i == this->begin () || !p.sub ((--i)->first) ? this->end () : i;
}
};
template <typename T>
using path_map = path_map_impl<path, T>;
template <typename T>
using dir_path_map = path_map_impl<dir_path, T>;
}
#endif // LIBBUTL_PATH_MAP_HXX
|
