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
RevLine 
[4d65515]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 {
[2a482ee]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>
[f8bbaa0]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>
[647b756]59 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
[f8bbaa0]60 {
[73e3791]61 using iterator = typename Tree::iterator;
62 using node_type = typename Tree::node_type;
[f8bbaa0]63
[647b756]64 auto it = lower_bound_const(tree, key);
[f8bbaa0]65
[73e3791]66 return iterator{const_cast<node_type*>(it.node()), it.end()};
[f8bbaa0]67 }
68
69 template<class Tree, class Key>
70 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
[2a482ee]71 {
[f8bbaa0]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;
[2a482ee]99 }
100
101 template<class Tree, class Key>
[647b756]102 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
[2a482ee]103 {
[73e3791]104 using iterator = typename Tree::iterator;
105 using node_type = typename Tree::node_type;
[647b756]106
107 auto it = upper_bound_const(tree, key);
108
[73e3791]109 return iterator{const_cast<node_type*>(it.node()), it.end()};
[2a482ee]110 }
111
112 template<class Tree, class Key>
[f8bbaa0]113 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
[2a482ee]114 {
[f8bbaa0]115 /**
116 * If key isn't in the tree, we get it's
[73e3791]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.
[f8bbaa0]121 */
122 auto it = lower_bound_const(tree, key);
123 if (it == tree.end())
124 return it;
125 else
[73e3791]126 return ++it;
[2a482ee]127 }
128
129 template<class Tree, class Key>
130 static pair<
131 typename Tree::iterator,
132 typename Tree::iterator
[f8bbaa0]133 > equal_range(Tree& tree, const Key& key)
[2a482ee]134 {
[f8bbaa0]135 return make_pair(
136 lower_bound(tree, key),
137 upper_bound(tree, key)
138 );
[2a482ee]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 {
[f8bbaa0]147 return make_pair(
148 lower_bound_const(tree, key),
149 upper_bound_const(tree, key)
150 );
[2a482ee]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)...};
[48f09f2f]170 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
[2a482ee]171
[7644d6e]172 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
[647b756]173 return make_pair(iterator{parent, false}, false);
[2a482ee]174
175 auto node = new node_type{move(val)};
[647b756]176
[73e3791]177 return insert(tree, node, parent);
[2a482ee]178 }
[4d65515]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
[48f09f2f]188 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
[7644d6e]189 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
[647b756]190 return make_pair(iterator{parent, false}, false);
[4d65515]191
192 auto node = new node_type{val};
[647b756]193
[73e3791]194 return insert(tree, node, parent);
[4d65515]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
[48f09f2f]205 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
[7644d6e]206 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
[647b756]207 return make_pair(iterator{parent, false}, false);
[4d65515]208
209 auto node = new node_type{forward<Value>(val)};
[73e3791]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 }
[647b756]243
244 return make_pair(iterator{node, false}, true);
[4d65515]245 }
246 };
247
248 struct rbtree_multi_policy
249 {
[647b756]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
[73e3791]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.
[647b756]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 {
[73e3791]348 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
[647b756]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>
[73e3791]412 static typename Tree::iterator insert(
413 Tree& tree, typename Tree::node_type* node,
414 typename Tree::node_type* = nullptr
415 )
[647b756]416 {
417 using iterator = typename Tree::iterator;
418
[73e3791]419 if (!node)
420 return tree.end();
421
[48f09f2f]422 auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
[73e3791]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 }
[647b756]447
448 return iterator{node, false};
449 }
[4d65515]450 };
451}
452
453#endif
454
Note: See TracBrowser for help on using the repository browser.