/
pathset.h
158 lines (132 loc) · 3.75 KB
/
pathset.h
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
150
151
152
153
154
155
156
157
158
/**
* Copyright (c) 2014-present, The osquery authors
*
* This source code is licensed as defined by the LICENSE file found in the
* root directory of this source tree.
*
* SPDX-License-Identifier: (Apache-2.0 OR GPL-2.0-only)
*/
#pragma once
#include <set>
#include <string>
#include <vector>
#include <boost/noncopyable.hpp>
#include <boost/tokenizer.hpp>
#include <osquery/core/core.h>
#include <osquery/filesystem/filesystem.h>
#include <osquery/utils/mutex.h>
namespace osquery {
/**
* @brief multiset based implementation for path search.
*
* 'multiset' is used because with patterns we can search for equivalent keys.
* Since '/This/Path/is' ~= '/This/Path/%' ~= '/This/Path/%%' (equivalent).
*
* multiset is protected by lock. It is threadsafe.
*
* PathSet can take any of the two policies -
* 1. patternedPath - Path can contain pattern '%' and '%%'.
* Path components containing only '%' and '%%' are supported
* e.g. '/This/Path/%'.
* Path components containing partial patterns are not
* supported e.g. '/This/Path/xyz%' ('xyz%' will not be
* treated as pattern).
*/
template <typename PathType>
class PathSet : private boost::noncopyable {
public:
void insert(const std::string& str) {
auto pattern = str;
replaceGlobWildcards(pattern);
auto vpath = PathType::createVPath(pattern);
WriteLock lock(mset_lock_);
for (auto& path : vpath) {
paths_.insert(std::move(path));
}
}
bool find(const std::string& str) const {
auto path = PathType::createPath(str);
ReadLock lock(mset_lock_);
if (paths_.find(path) != paths_.end()) {
return true;
}
return false;
}
void clear() {
WriteLock lock(mset_lock_);
paths_.clear();
}
bool empty() const {
ReadLock lock(mset_lock_);
return paths_.empty();
}
private:
typedef typename PathType::Path Path;
typedef typename PathType::Compare Compare;
std::multiset<Path, Compare> paths_;
mutable Mutex mset_lock_;
};
class patternedPath {
public:
typedef boost::tokenizer<boost::char_separator<char>> tokenizer;
typedef std::vector<std::string> Path;
typedef std::vector<Path> VPath;
struct Compare {
bool operator()(const Path& lhs, const Path& rhs) const {
size_t psize = (lhs.size() < rhs.size()) ? lhs.size() : rhs.size();
unsigned ndx;
for (ndx = 0; ndx < psize; ++ndx) {
if (lhs[ndx] == "**" || rhs[ndx] == "**") {
return false;
}
if (lhs[ndx] == "*" || rhs[ndx] == "*") {
continue;
}
int rc = lhs[ndx].compare(rhs[ndx]);
if (rc > 0) {
return false;
}
if (rc < 0) {
return true;
}
}
if ((ndx == rhs.size() && rhs[ndx - 1] == "*") ||
(ndx == lhs.size() && lhs[ndx - 1] == "*")) {
return false;
}
return (lhs.size() < rhs.size());
}
};
static Path createPath(const std::string& str) {
boost::char_separator<char> sep{"/"};
tokenizer tokens(str, sep);
Path path;
if (str == "/") {
path.push_back("");
}
for (std::string component : tokens) {
path.push_back(std::move(component));
}
return path;
}
static VPath createVPath(const std::string& str) {
boost::char_separator<char> sep{"/"};
tokenizer tokens(str, sep);
VPath vpath;
Path path;
if (str == "/") {
path.push_back("");
}
for (std::string component : tokens) {
if (component == "**") {
vpath.push_back(path);
path.push_back(std::move(component));
break;
}
path.push_back(std::move(component));
}
vpath.push_back(std::move(path));
return vpath;
}
};
} // namespace osquery