source: mainline/uspace/lib/cpp/include/internal/rbtree_policies.hpp@ 73e3791

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 73e3791 was 73e3791, checked in by Dzejrou <dzejrou@…>, 7 years ago

cpp: revamped rbtree so that it now stores equivalent keys in a list
  • Property mode set to 100644
File size: 14.3 KB
Line 
1/*
2 * Copyright (c) 2018 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_INTERNAL_RBTREE_POLICIES
30#define LIBCPP_INTERNAL_RBTREE_POLICIES
31
32#include <internal/rbtree_node.hpp>
33#include <utility>
34
35namespace std::aux
36{
37 struct rbtree_single_policy
38 {
39 template<class Tree, class Key>
40 static typename Tree::size_type count(const Tree& tree, const Key& key)
41 {
42 return tree.find(key) == tree.end() ? 0 : 1;
43 }
44
45 template<class Tree, class Key>
46 static typename Tree::size_type erase(Tree& tree, const Key& key)
47 {
48 using size_type = typename Tree::size_type;
49
50 auto it = tree.find(key);
51 if (it == tree.end())
52 return size_type{};
53 else
54 tree.delete_node(it.node());
55 return size_type{1};
56 }
57
58 template<class Tree, class Key>
59 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
60 {
61 using iterator = typename Tree::iterator;
62 using node_type = typename Tree::node_type;
63
64 auto it = lower_bound_const(tree, key);
65
66 return iterator{const_cast<node_type*>(it.node()), it.end()};
67 }
68
69 template<class Tree, class Key>
70 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
71 {
72 using const_iterator = typename Tree::const_iterator;
73
74 auto node = tree.find_parent_for_insertion(key);
75 const_iterator it{node, false};
76 auto beg = tree.begin();
77 auto end = tree.end();
78
79 if (tree.key_compare_(tree.get_key(*it), key))
80 {
81 // Predecessor.
82 if (it != end)
83 return ++it;
84 else
85 return it;
86 }
87 else if (tree.key_compare_(key, tree.get_key(*it)))
88 {
89 // Successor.
90 if (it != beg)
91 return --it;
92 else
93 return it;
94 }
95 else // Perfect match.
96 return it;
97
98 return it;
99 }
100
101 template<class Tree, class Key>
102 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
103 {
104 using iterator = typename Tree::iterator;
105 using node_type = typename Tree::node_type;
106
107 auto it = upper_bound_const(tree, key);
108
109 return iterator{const_cast<node_type*>(it.node()), it.end()};
110 }
111
112 template<class Tree, class Key>
113 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
114 {
115 /**
116 * If key isn't in the tree, we get it's
117 * predecessor or tree.end(). If key is
118 * in the tree, we get it. So unless it
119 * is equal to end(), we can increment it
120 * to get the upper bound.
121 */
122 auto it = lower_bound_const(tree, key);
123 if (it == tree.end())
124 return it;
125 else
126 return ++it;
127 }
128
129 template<class Tree, class Key>
130 static pair<
131 typename Tree::iterator,
132 typename Tree::iterator
133 > equal_range(Tree& tree, const Key& key)
134 {
135 return make_pair(
136 lower_bound(tree, key),
137 upper_bound(tree, key)
138 );
139 }
140
141 template<class Tree, class Key>
142 static pair<
143 typename Tree::const_iterator,
144 typename Tree::const_iterator
145 > equal_range_const(const Tree& tree, const Key& key)
146 {
147 return make_pair(
148 lower_bound_const(tree, key),
149 upper_bound_const(tree, key)
150 );
151 }
152
153 /**
154 * Note: We have to duplicate code for emplace, insert(const&)
155 * and insert(&&) here, because the node (which makes distinction
156 * between the arguments) is only created if the value isn't
157 * in the tree already.
158 */
159
160 template<class Tree, class... Args>
161 static pair<
162 typename Tree::iterator, bool
163 > emplace(Tree& tree, Args&&... args)
164 {
165 using value_type = typename Tree::value_type;
166 using iterator = typename Tree::iterator;
167 using node_type = typename Tree::node_type;
168
169 auto val = value_type{forward<Args>(args)...};
170 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
171
172 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
173 return make_pair(iterator{parent, false}, false);
174
175 auto node = new node_type{move(val)};
176
177 return insert(tree, node, parent);
178 }
179
180 template<class Tree, class Value>
181 static pair<
182 typename Tree::iterator, bool
183 > insert(Tree& tree, const Value& val)
184 {
185 using iterator = typename Tree::iterator;
186 using node_type = typename Tree::node_type;
187
188 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
189 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
190 return make_pair(iterator{parent, false}, false);
191
192 auto node = new node_type{val};
193
194 return insert(tree, node, parent);
195 }
196
197 template<class Tree, class Value>
198 static pair<
199 typename Tree::iterator, bool
200 > insert(Tree& tree, Value&& val)
201 {
202 using iterator = typename Tree::iterator;
203 using node_type = typename Tree::node_type;
204
205 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
206 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
207 return make_pair(iterator{parent, false}, false);
208
209 auto node = new node_type{forward<Value>(val)};
210
211 return insert(tree, node, parent);
212 }
213
214 template<class Tree>
215 static pair<
216 typename Tree::iterator, bool
217 > insert(
218 Tree& tree, typename Tree::node_type* node,
219 typename Tree::node_type* parent
220 )
221 {
222 using iterator = typename Tree::iterator;
223
224 if (!node)
225 return make_pair(tree.end(), false);
226
227 ++tree.size_;
228 if (!parent)
229 {
230 node->color = rbcolor::black;
231 tree.root_ = node;
232 }
233 else
234 {
235 if (tree.keys_comp(tree.get_key(node->value), parent->value))
236 parent->add_left_child(node);
237 else
238 parent->add_right_child(node);
239
240 tree.repair_after_insert_(node);
241 tree.update_root_(node);
242 }
243
244 return make_pair(iterator{node, false}, true);
245 }
246 };
247
248 struct rbtree_multi_policy
249 {
250 template<class Tree, class Key>
251 static typename Tree::size_type count(const Tree& tree, const Key& key)
252 {
253 using size_type = typename Tree::size_type;
254
255 auto it = tree.find(key);
256 if (it == tree.end())
257 return size_type{};
258
259 size_type res{};
260 while (tree.keys_equal(tree.get_key(*it), key))
261 {
262 ++res;
263 ++it;
264 }
265
266 return res;
267 }
268
269 template<class Tree, class Key>
270 static typename Tree::size_type erase(Tree& tree, const Key& key)
271 {
272 using size_type = typename Tree::size_type;
273
274 auto it = tree.find(key);
275 if (it == tree.end())
276 return size_type{};
277
278 size_type res{};
279 while (tree.keys_equal(tree.get_key(*it), key))
280 {
281 ++res;
282 it = tree.erase(it);
283 }
284
285 return res;
286 }
287
288 template<class Tree, class Key>
289 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
290 {
291 auto it = lower_bound_const(tree, key);
292
293 return typename Tree::iterator{it.node(), it.end()};
294 }
295
296 template<class Tree, class Key>
297 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
298 {
299 using const_iterator = typename Tree::const_iterator;
300
301 auto node = tree.find_parent_for_insertion(key);
302 const_iterator it{node, false};
303 auto beg = tree.begin();
304 auto end = tree.end();
305
306 if (tree.keys_comp(key, *it))
307 --it; // Incase we are on a successor.
308 while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
309 --it; // Skip keys that are equal.
310 if (it != beg)
311 ++it; // If we moved all the way to the start, key is the smallest.
312
313 if (tree.key_compare_(tree.get_key(*it), key))
314 {
315 // Predecessor.
316 if (it != end)
317 return ++it;
318 else
319 return it;
320 }
321
322 return it;
323 }
324
325 template<class Tree, class Key>
326 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
327 {
328 auto it = upper_bound_const(tree, key);
329
330 return typename Tree::iterator{it.node(), it.end()};
331 }
332
333 template<class Tree, class Key>
334 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
335 {
336 /**
337 * If key isn't in the tree, we get it's
338 * predecessor or tree.end(). If key is
339 * in the tree, we get it. So unless it
340 * is equal to end(), we keep incrementing
341 * until we get to the next key.
342 */
343 auto it = lower_bound(tree, key);
344 if (it == tree.end())
345 return it;
346 else if (tree.keys_equal(tree.get_key(*it), key))
347 {
348 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
349 ++it;
350
351 return it;
352 }
353
354 return it;
355 }
356
357 template<class Tree, class Key>
358 static pair<
359 typename Tree::iterator,
360 typename Tree::iterator
361 > equal_range(const Tree& tree, const Key& key)
362 {
363 return make_pair(
364 lower_bound(tree, key),
365 upper_bound(tree, key)
366 );
367 }
368
369 template<class Tree, class Key>
370 static pair<
371 typename Tree::const_iterator,
372 typename Tree::const_iterator
373 > equal_range_const(const Tree& tree, const Key& key)
374 {
375 return make_pair(
376 lower_bound_const(tree, key),
377 upper_bound_const(tree, key)
378 );
379 }
380
381 template<class Tree, class... Args>
382 static typename Tree::iterator emplace(Tree& tree, Args&&... args)
383 {
384 using node_type = typename Tree::node_type;
385
386 auto node = node_type{forward<Args>(args)...};
387
388 return insert(tree, node);
389 }
390
391 template<class Tree, class Value>
392 static typename Tree::iterator insert(Tree& tree, const Value& val)
393 {
394 using node_type = typename Tree::node_type;
395
396 auto node = new node_type{val};
397
398 return insert(tree, node);
399 }
400
401 template<class Tree, class Value>
402 static typename Tree::iterator insert(Tree& tree, Value&& val)
403 {
404 using node_type = typename Tree::node_type;
405
406 auto node = new node_type{forward<Value>(val)};
407
408 return insert(tree, node);
409 }
410
411 template<class Tree>
412 static typename Tree::iterator insert(
413 Tree& tree, typename Tree::node_type* node,
414 typename Tree::node_type* = nullptr
415 )
416 {
417 using iterator = typename Tree::iterator;
418
419 if (!node)
420 return tree.end();
421
422 auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
423
424 ++tree.size_;
425 if (!parent)
426 {
427 node->color = rbcolor::black;
428 tree.root_ = node;
429 }
430 else
431 {
432 if (tree.keys_comp(tree.get_key(node->value), parent->value))
433 parent->add_left_child(node);
434 else if (tree.keys_comp(tree.get_key(parent->value), node->value))
435 parent->add_right_child(node);
436 else
437 {
438 parent->add(node); // List of nodes with equivalent keys.
439 tree.update_root_(parent);
440
441 return iterator{node, false};
442 }
443
444 tree.repair_after_insert_(node);
445 tree.update_root_(node);
446 }
447
448 return iterator{node, false};
449 }
450 };
451}
452
453#endif
454
Note: See TracBrowser for help on using the repository browser.