source: mainline/uspace/lib/cpp/include/__bits/adt/rbtree_policies.hpp@ b57a3ee

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

cpp: refactored the library layout, everything from the impl directory was moved to the bits directory for the sake of consistency, updated copyright notices and include guards
  • Property mode set to 100644
File size: 14.5 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_BITS_ADT_RBTREE_POLICIES
30#define LIBCPP_BITS_ADT_RBTREE_POLICIES
31
32#include <__bits/adt/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 (it != tree.end() && 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 (it != tree.end() && 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{
294 const_cast<typename Tree::node_type*>(it.node()), it.end()
295 };
296 }
297
298 template<class Tree, class Key>
299 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
300 {
301 using const_iterator = typename Tree::const_iterator;
302
303 auto node = tree.find_parent_for_insertion(key);
304 const_iterator it{node, false};
305 auto beg = tree.begin();
306 auto end = tree.end();
307
308 if (tree.keys_comp(key, *it))
309 --it; // Incase we are on a successor.
310 while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
311 --it; // Skip keys that are equal.
312 if (it != beg)
313 ++it; // If we moved all the way to the start, key is the smallest.
314
315 if (tree.key_compare_(tree.get_key(*it), key))
316 {
317 // Predecessor.
318 if (it != end)
319 return ++it;
320 else
321 return it;
322 }
323
324 return it;
325 }
326
327 template<class Tree, class Key>
328 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
329 {
330 auto it = upper_bound_const(tree, key);
331
332 return typename Tree::iterator{
333 const_cast<typename Tree::node_type*>(it.node()), it.end()
334 };
335 }
336
337 template<class Tree, class Key>
338 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
339 {
340 /**
341 * If key isn't in the tree, we get it's
342 * predecessor or tree.end(). If key is
343 * in the tree, we get it. So unless it
344 * is equal to end(), we keep incrementing
345 * until we get to the next key.
346 */
347 auto it = lower_bound(tree, key);
348 if (it == tree.end())
349 return it;
350 else if (tree.keys_equal(tree.get_key(*it), key))
351 {
352 while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
353 ++it;
354
355 return it;
356 }
357
358 return it;
359 }
360
361 template<class Tree, class Key>
362 static pair<
363 typename Tree::iterator,
364 typename Tree::iterator
365 > equal_range(const Tree& tree, const Key& key)
366 {
367 return make_pair(
368 lower_bound(tree, key),
369 upper_bound(tree, key)
370 );
371 }
372
373 template<class Tree, class Key>
374 static pair<
375 typename Tree::const_iterator,
376 typename Tree::const_iterator
377 > equal_range_const(const Tree& tree, const Key& key)
378 {
379 return make_pair(
380 lower_bound_const(tree, key),
381 upper_bound_const(tree, key)
382 );
383 }
384
385 template<class Tree, class... Args>
386 static typename Tree::iterator emplace(Tree& tree, Args&&... args)
387 {
388 using node_type = typename Tree::node_type;
389
390 auto node = new node_type{forward<Args>(args)...};
391
392 return insert(tree, node);
393 }
394
395 template<class Tree, class Value>
396 static typename Tree::iterator insert(Tree& tree, const Value& val)
397 {
398 using node_type = typename Tree::node_type;
399
400 auto node = new node_type{val};
401
402 return insert(tree, node);
403 }
404
405 template<class Tree, class Value>
406 static typename Tree::iterator insert(Tree& tree, Value&& val)
407 {
408 using node_type = typename Tree::node_type;
409
410 auto node = new node_type{forward<Value>(val)};
411
412 return insert(tree, node);
413 }
414
415 template<class Tree>
416 static typename Tree::iterator insert(
417 Tree& tree, typename Tree::node_type* node,
418 typename Tree::node_type* = nullptr
419 )
420 {
421 using iterator = typename Tree::iterator;
422
423 if (!node)
424 return tree.end();
425
426 auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
427
428 ++tree.size_;
429 if (!parent)
430 {
431 node->color = rbcolor::black;
432 tree.root_ = node;
433 }
434 else
435 {
436 if (tree.keys_comp(tree.get_key(node->value), parent->value))
437 parent->add_left_child(node);
438 else if (tree.keys_comp(tree.get_key(parent->value), node->value))
439 parent->add_right_child(node);
440 else
441 {
442 parent->add(node); // List of nodes with equivalent keys.
443 tree.update_root_(parent);
444
445 return iterator{node, false};
446 }
447
448 tree.repair_after_insert_(node);
449 tree.update_root_(node);
450 }
451
452 return iterator{node, false};
453 }
454 };
455}
456
457#endif
458
Note: See TracBrowser for help on using the repository browser.