Line data Source code
1 : /**
2 : * @file
3 : *
4 : * @brief
5 : *
6 : * @copyright BSD License (see LICENSE.md or https://www.libelektra.org)
7 : */
8 :
9 : #include <keyset.hpp>
10 :
11 : #include <cassert>
12 : #include <iostream>
13 : #include <map>
14 : #include <string>
15 :
16 : namespace kdb
17 : {
18 :
19 : /**
20 : * @brief Search for nth level in a name
21 : *
22 : * @param k the key to search in
23 : * @param n the level
24 : *
25 : * nth_level_of_name(Key("user:/hello", KEY_END), 0) -> "user:"
26 : * nth_level_of_name(Key("user:/hello", KEY_END), 1) -> "hello"
27 : *
28 : * @return the searched string (without slashes)
29 : */
30 0 : std::string nth_level_of_name (Key k, unsigned long n)
31 : {
32 0 : size_t prev = 0;
33 0 : std::string name = k.getName ();
34 :
35 0 : for (unsigned long i = 0; i < n; ++i)
36 : {
37 0 : size_t pos = name.find ("/", prev);
38 0 : prev = pos + 1;
39 : }
40 :
41 0 : return name.substr (prev, name.find ("/", prev) - prev);
42 : }
43 :
44 : /**
45 : * @brief The number of levels a name has
46 : *
47 : * @param k the key to search within
48 : *
49 : * @return the hierarchy depth of a key
50 : */
51 0 : unsigned long name_depth (Key k)
52 : {
53 0 : std::string name = k.getName ();
54 0 : size_t pos = name.find ("/", 0);
55 0 : unsigned long depth = 0;
56 :
57 0 : while (pos != std::string::npos)
58 : {
59 0 : pos = name.find ("/", pos + 1);
60 0 : ++depth;
61 : }
62 :
63 0 : return depth;
64 : }
65 :
66 : /**
67 : * @brief Visitor (of Visitor pattern)
68 : */
69 : class Visitor
70 : {
71 : public:
72 : virtual void visit (std::string name, unsigned long depth, Key k) = 0;
73 : };
74 :
75 : class KeyHierarchy;
76 :
77 : /**
78 : * @brief A KeyNode builds up the structure of the KeyHierarchy
79 : *
80 : * Every KeyNode contains children (subnodes).
81 : * KeyNodes that are for structure only, do not contain a Key (0-key)
82 : * other KeyNodes have a reference to a key
83 : */
84 0 : class KeyNode
85 : {
86 : public:
87 : typedef std::map<std::string, KeyNode> KeyNodeMap;
88 : typedef KeyNodeMap::iterator KeyNodeIterator;
89 :
90 0 : KeyNode (unsigned long depth, Key k = static_cast<ckdb::Key *> (nullptr)) : m_self (k), m_subnodes (), m_depth (depth)
91 : {
92 : }
93 :
94 : /**
95 : * @brief (Recursively) add or update a key to nodes
96 : *
97 : * If the key exists, it will be updated
98 : *
99 : * If the key does not exist, node(s) will be created
100 : *
101 : * @param k the key to add
102 : * @param depth current depth of recursion
103 : */
104 0 : void add (Key k, unsigned long depth)
105 : {
106 0 : assert (k);
107 0 : assert (m_self ? m_self.isBelow (k) : true);
108 0 : depth++;
109 :
110 0 : if (m_self.isDirectBelow (k) || depth == name_depth (k))
111 : {
112 0 : for (auto & elem : m_subnodes)
113 : {
114 0 : if (elem.first == k.getBaseName ())
115 : {
116 : // found node, update it
117 0 : elem.second.m_self = k;
118 0 : return;
119 : }
120 : }
121 : // will add new subnode (direct below+not found)
122 0 : m_subnodes.insert (std::make_pair (k.getBaseName (), KeyNode (depth, k)));
123 0 : return;
124 : }
125 :
126 0 : for (auto & elem : m_subnodes)
127 : {
128 0 : if (k.isBelow (elem.second.m_self))
129 : {
130 : // found subnode, call recursively
131 0 : elem.second.add (k, depth);
132 0 : return;
133 : }
134 : }
135 :
136 : // create a structure key (without key, only name)
137 0 : std::string name = nth_level_of_name (k, depth);
138 0 : std::pair<KeyNodeIterator, bool> p = m_subnodes.insert (std::make_pair (name, KeyNode (depth)));
139 : // structure keys get a null key
140 0 : auto it = p.first;
141 0 : it->second.add (k, depth);
142 : }
143 :
144 : /**
145 : * @brief Accept a visitor for iteration
146 : *
147 : * @param visitor defines the action
148 : */
149 0 : void accept (Visitor & visitor)
150 : {
151 0 : for (auto & elem : m_subnodes)
152 : {
153 0 : visitor.visit (elem.first, elem.second.m_depth, elem.second.m_self);
154 0 : elem.second.accept (visitor);
155 : }
156 0 : }
157 :
158 : private:
159 : friend class KeyHierarchy; // they are tightly coupled
160 :
161 : Key m_self;
162 : KeyNodeMap m_subnodes;
163 : unsigned long m_depth;
164 : };
165 :
166 : /**
167 : * @brief Builds up a hierarchy of Keys
168 : *
169 : * Also keeps a KeySet in sync with what is in the hierarchy.
170 : * The keys will be shared between the keyset and the hierarchy.
171 : */
172 0 : class KeyHierarchy
173 : {
174 : public:
175 0 : explicit KeyHierarchy (KeySet & keyset) : m_userRootNode (0), m_systemRootNode (0), m_keyset (keyset)
176 : {
177 0 : add (keyset);
178 0 : }
179 :
180 : /**
181 : * @brief Add all keys of a keyset
182 : *
183 : * Will not update the underlying keyset (is fixed at
184 : * construction)
185 : *
186 : * @param ks
187 : */
188 0 : void add (KeySet const & ks)
189 : {
190 0 : for (auto && k : ks)
191 : {
192 0 : add (k);
193 : }
194 0 : }
195 :
196 : /**
197 : * @brief Add a single key to hierarchy
198 : *
199 : * @param k the key to add
200 : */
201 0 : void add (Key k)
202 : {
203 : // update root nodes
204 0 : if (k.getName () == "user:/")
205 : {
206 0 : m_userRootNode.m_self = k;
207 : }
208 0 : else if (k.getName () == "system:/")
209 : {
210 0 : m_systemRootNode.m_self = k;
211 : }
212 : // if it is not a root node, update hierarchy
213 0 : else if (k.isUser ())
214 : {
215 0 : m_userRootNode.add (k, 0);
216 : }
217 : else
218 : {
219 0 : m_systemRootNode.add (k, 0);
220 : }
221 :
222 : // update keyset
223 0 : m_keyset.lookup (k, KDB_O_POP);
224 0 : m_keyset.append (k);
225 0 : }
226 :
227 : /**
228 : * @brief Allow visitor to traverse the hierarchy
229 : *
230 : * @param visitor to traverse
231 : */
232 0 : void accept (Visitor & visitor)
233 : {
234 0 : visitor.visit ("user:/", 0, m_userRootNode.m_self);
235 0 : m_userRootNode.accept (visitor);
236 0 : visitor.visit ("system:/", 0, m_systemRootNode.m_self);
237 0 : m_systemRootNode.accept (visitor);
238 0 : }
239 :
240 : private:
241 : KeyNode m_userRootNode;
242 : KeyNode m_systemRootNode;
243 :
244 : KeySet & m_keyset;
245 : };
246 : } // namespace kdb
247 :
248 :
249 : /**
250 : * @brief Example visitor that prints the hierarchy
251 : */
252 : class PrintVisitor : public kdb::Visitor
253 : {
254 : public:
255 0 : void visit (std::string name, unsigned long depth, kdb::Key k) override
256 : {
257 0 : for (unsigned long i = 0; i < depth; ++i)
258 : {
259 0 : std::cout << " ";
260 : }
261 :
262 0 : std::cout << name;
263 :
264 0 : if (k)
265 : {
266 0 : std::cout << "(" << k.getName () << ") = " << k.getString ();
267 : }
268 :
269 0 : std::cout << std::endl;
270 0 : }
271 : };
272 :
273 0 : int main ()
274 : {
275 0 : using namespace kdb;
276 0 : KeySet ks;
277 0 : KeyHierarchy kh (ks);
278 0 : kh.add (Key ("user:/hello", KEY_VALUE, "Hello world", KEY_END));
279 0 : PrintVisitor pv;
280 0 : kh.accept (pv);
281 0 : std::cout << std::endl;
282 :
283 0 : kh.add (Key ("system:/b/s/t", KEY_VALUE, "Below", KEY_END));
284 0 : kh.accept (pv);
285 0 : std::cout << std::endl;
286 :
287 0 : kh.add (Key ("system:/b/s/t", KEY_VALUE, "Updated", KEY_END));
288 0 : kh.accept (pv);
289 0 : std::cout << std::endl;
290 :
291 0 : kh.add (Key ("system:/", KEY_VALUE, "root value", KEY_END));
292 0 : kh.accept (pv);
293 0 : }
|
