source: mainline/uspace/lib/cpp/include/internal/rbtree_policies.hpp@ 647b756

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

cpp: removed redundant code, eliminated some more code duplication, added more insert logic to the policy, added multi policy
  • 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
63 auto it = lower_bound_const(tree, key);
64
65 return iterator{it.node(), it.end()};
66 }
67
68 template<class Tree, class Key>
69 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
70 {
71 using const_iterator = typename Tree::const_iterator;
72
73 auto node = tree.find_parent_for_insertion(key);
74 const_iterator it{node, false};
75 auto beg = tree.begin();
76 auto end = tree.end();
77
78 if (tree.key_compare_(tree.get_key(*it), key))
79 {
80 // Predecessor.
81 if (it != end)
82 return ++it;
83 else
84 return it;
85 }
86 else if (tree.key_compare_(key, tree.get_key(*it)))
87 {
88 // Successor.
89 if (it != beg)
90 return --it;
91 else
92 return it;
93 }
94 else // Perfect match.
95 return it;
96
97 return it;
98 }
99
100 template<class Tree, class Key>
101 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
102 {
103 using iterator = typename Tree::iterator;
104
105 auto it = upper_bound_const(tree, key);
106
107 return iterator{it.node(), it.end()};
108 }
109
110 template<class Tree, class Key>
111 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
112 {
113 /**
114 * If key isn't in the tree, we get it's
115 * successor or tree.end(). If key is
116 * in the tree, we get it.
117 * In the first case, the successor is also
118 * the upper bound, so we just return it,
119 * otherwise (as long as it != end()) we
120 * increment.
121 */
122 auto it = lower_bound_const(tree, key);
123 if (it == tree.end())
124 return it;
125 else if (tree.keys_equal(key, *it))
126 return ++it;
127 else
128 return it;
129 }
130
131 template<class Tree, class Key>
132 static pair<
133 typename Tree::iterator,
134 typename Tree::iterator
135 > equal_range(Tree& tree, const Key& key)
136 {
137 return make_pair(
138 lower_bound(tree, key),
139 upper_bound(tree, key)
140 );
141 }
142
143 template<class Tree, class Key>
144 static pair<
145 typename Tree::const_iterator,
146 typename Tree::const_iterator
147 > equal_range_const(const Tree& tree, const Key& key)
148 {
149 return make_pair(
150 lower_bound_const(tree, key),
151 upper_bound_const(tree, key)
152 );
153 }
154
155 /**
156 * Note: We have to duplicate code for emplace, insert(const&)
157 * and insert(&&) here, because the node (which makes distinction
158 * between the arguments) is only created if the value isn't
159 * in the tree already.
160 */
161
162 template<class Tree, class... Args>
163 static pair<
164 typename Tree::iterator, bool
165 > emplace(Tree& tree, Args&&... args)
166 {
167 using value_type = typename Tree::value_type;
168 using iterator = typename Tree::iterator;
169 using node_type = typename Tree::node_type;
170
171 auto val = value_type{forward<Args>(args)...};
172 auto parent = tree.find_parent_for_insertion(val);
173 if (!parent)
174 {
175 tree.root_ = new node_type{move(val)};
176 ++tree.size_;
177
178 return make_pair(iterator{tree.root_, false}, true);
179 }
180
181 if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
182 return make_pair(iterator{parent, false}, false);
183
184 auto node = new node_type{move(val)};
185 if (tree.keys_comp(tree.get_key(val), parent->value))
186 parent->add_left_child(node);
187 else
188 parent->add_right_child(node);
189
190 ++tree.size_;
191 tree.repair_after_insert_(node);
192 tree.update_root_(node);
193
194 return make_pair(iterator{node, false}, true);
195 }
196
197 template<class Tree, class Value>
198 static pair<
199 typename Tree::iterator, bool
200 > insert(Tree& tree, const 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(val);
206 if (!parent)
207 {
208 tree.root_ = new node_type{val};
209 ++tree.size_;
210
211 return make_pair(iterator{tree.root_}, true);
212 }
213
214 if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
215 return make_pair(iterator{parent, false}, false);
216
217 auto node = new node_type{val};
218 if (tree.keys_comp(tree.get_key(val), parent->value))
219 parent->add_left_child(node);
220 else
221 parent->add_right_child(node);
222
223 ++tree.size_;
224 tree.repair_after_insert_(node);
225 tree.update_root_(node);
226
227 return make_pair(iterator{node, false}, true);
228 }
229
230 template<class Tree, class Value>
231 static pair<
232 typename Tree::iterator, bool
233 > insert(Tree& tree, Value&& val)
234 {
235 using iterator = typename Tree::iterator;
236 using node_type = typename Tree::node_type;
237
238 auto parent = tree.find_parent_for_insertion(val);
239 if (!parent)
240 {
241 tree.root_ = new node_type{forward<Value>(val)};
242 ++tree.size_;
243
244 return make_pair(iterator{tree.root_, false}, true);
245 }
246
247 if (tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
248 return make_pair(iterator{parent, false}, false);
249
250 auto node = new node_type{forward<Value>(val)};
251 if (tree.keys_comp(tree.get_key(val), parent->value))
252 parent->add_left_child(node);
253 else
254 parent->add_right_child(node);
255
256 ++tree.size_;
257 tree.repair_after_insert_(node);
258 tree.update_root_(node);
259
260 return make_pair(iterator{node, false}, true);
261 }
262 };
263
264 struct rbtree_multi_policy
265 {
266 template<class Tree, class Key>
267 static typename Tree::size_type count(const Tree& tree, const Key& key)
268 {
269 using size_type = typename Tree::size_type;
270
271 auto it = tree.find(key);
272 if (it == tree.end())
273 return size_type{};
274
275 size_type res{};
276 while (tree.keys_equal(tree.get_key(*it), key))
277 {
278 ++res;
279 ++it;
280 }
281
282 return res;
283 }
284
285 template<class Tree, class Key>
286 static typename Tree::size_type erase(Tree& tree, const Key& key)
287 {
288 using size_type = typename Tree::size_type;
289
290 auto it = tree.find(key);
291 if (it == tree.end())
292 return size_type{};
293
294 size_type res{};
295 while (tree.keys_equal(tree.get_key(*it), key))
296 {
297 ++res;
298 it = tree.erase(it);
299 }
300
301 return res;
302 }
303
304 template<class Tree, class Key>
305 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
306 {
307 auto it = lower_bound_const(tree, key);
308
309 return typename Tree::iterator{it.node(), it.end()};
310 }
311
312 template<class Tree, class Key>
313 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
314 {
315 using const_iterator = typename Tree::const_iterator;
316
317 auto node = tree.find_parent_for_insertion(key);
318 const_iterator it{node, false};
319 auto beg = tree.begin();
320 auto end = tree.end();
321
322 if (tree.keys_comp(key, *it))
323 --it; // Incase we are on a successor.
324 while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
325 --it; // Skip keys that are equal.
326 if (it != beg)
327 ++it; // If we moved all the way to the start, key is the smallest.
328
329 if (tree.key_compare_(tree.get_key(*it), key))
330 {
331 // Predecessor.
332 if (it != end)
333 return ++it;
334 else
335 return it;
336 }
337
338 return it;
339 }
340
341 template<class Tree, class Key>
342 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
343 {
344 auto it = upper_bound_const(tree, key);
345
346 return typename Tree::iterator{it.node(), it.end()};
347 }
348
349 template<class Tree, class Key>
350 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
351 {
352 /**
353 * If key isn't in the tree, we get it's
354 * successor or tree.end(). If key is
355 * in the tree, we get it.
356 * In the first case, the successor is also
357 * the upper bound, so we just return it,
358 * otherwise (as long as it != end()) we
359 * increment.
360 */
361 auto it = lower_bound(tree, key);
362 if (it == tree.end())
363 return it;
364 else if (tree.keys_equal(tree.get_key(*it), key))
365 {
366 while (tree.keys_equal(tree.get_key(*it), key))
367 ++it;
368
369 return it;
370 }
371
372 return it;
373 }
374
375 template<class Tree, class Key>
376 static pair<
377 typename Tree::iterator,
378 typename Tree::iterator
379 > equal_range(const Tree& tree, const Key& key)
380 {
381 return make_pair(
382 lower_bound(tree, key),
383 upper_bound(tree, key)
384 );
385 }
386
387 template<class Tree, class Key>
388 static pair<
389 typename Tree::const_iterator,
390 typename Tree::const_iterator
391 > equal_range_const(const Tree& tree, const Key& key)
392 {
393 return make_pair(
394 lower_bound_const(tree, key),
395 upper_bound_const(tree, key)
396 );
397 }
398
399 template<class Tree, class... Args>
400 static typename Tree::iterator emplace(Tree& tree, Args&&... args)
401 {
402 using node_type = typename Tree::node_type;
403
404 auto node = node_type{forward<Args>(args)...};
405
406 return insert(tree, node);
407 }
408
409 template<class Tree, class Value>
410 static typename Tree::iterator insert(Tree& tree, const Value& val)
411 {
412 using node_type = typename Tree::node_type;
413
414 auto node = new node_type{val};
415
416 return insert(tree, node);
417 }
418
419 template<class Tree, class Value>
420 static typename Tree::iterator insert(Tree& tree, Value&& val)
421 {
422 using node_type = typename Tree::node_type;
423
424 auto node = new node_type{forward<Value>(val)};
425
426 return insert(tree, node);
427 }
428
429 template<class Tree>
430 static typename Tree::iterator insert(Tree& tree, typename Tree::node_type* node)
431 {
432 using iterator = typename Tree::iterator;
433
434 auto parent = tree.find_parent_for_insertion(node->value);
435 if (!parent)
436 tree.root_ = node;
437 else if (tree.keys_comp(tree.get_key(node->value), parent->value))
438 parent->add_left_child(node);
439 else
440 parent->add_right_child(node);
441
442 ++tree.size_;
443 tree.repair_after_insert_(node);
444 tree.update_root_(node);
445
446 return iterator{node, false};
447 }
448 };
449}
450
451#endif
452
Note: See TracBrowser for help on using the repository browser.