source: mainline/uspace/lib/cpp/include/internal/rbtree_policies.hpp@ 48f09f2f

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

cpp: rbtree::find_parent_for_insertion now uses key_type instead of value_type, this caused problems with map::operator[]
  • Property mode set to 100644
File size: 12.8 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(tree.get_key(val));
173
174 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
175 return make_pair(iterator{parent, false}, false);
176
177 auto node = new node_type{move(val)};
178 tree.insert_node(node, parent);
179
180 return make_pair(iterator{node, false}, true);
181 }
182
183 template<class Tree, class Value>
184 static pair<
185 typename Tree::iterator, bool
186 > insert(Tree& tree, const Value& val)
187 {
188 using iterator = typename Tree::iterator;
189 using node_type = typename Tree::node_type;
190
191 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
192 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
193 return make_pair(iterator{parent, false}, false);
194
195 auto node = new node_type{val};
196 tree.insert_node(node, parent);
197
198 return make_pair(iterator{node, false}, true);
199 }
200
201 template<class Tree, class Value>
202 static pair<
203 typename Tree::iterator, bool
204 > insert(Tree& tree, Value&& val)
205 {
206 using iterator = typename Tree::iterator;
207 using node_type = typename Tree::node_type;
208
209 auto parent = tree.find_parent_for_insertion(tree.get_key(val));
210 if (parent && tree.keys_equal(tree.get_key(parent->value), tree.get_key(val)))
211 return make_pair(iterator{parent, false}, false);
212
213 auto node = new node_type{forward<Value>(val)};
214 tree.insert_node(node, parent);
215
216 return make_pair(iterator{node, false}, true);
217 }
218 };
219
220 struct rbtree_multi_policy
221 {
222 template<class Tree, class Key>
223 static typename Tree::size_type count(const Tree& tree, const Key& key)
224 {
225 using size_type = typename Tree::size_type;
226
227 auto it = tree.find(key);
228 if (it == tree.end())
229 return size_type{};
230
231 size_type res{};
232 while (tree.keys_equal(tree.get_key(*it), key))
233 {
234 ++res;
235 ++it;
236 }
237
238 return res;
239 }
240
241 template<class Tree, class Key>
242 static typename Tree::size_type erase(Tree& tree, const Key& key)
243 {
244 using size_type = typename Tree::size_type;
245
246 auto it = tree.find(key);
247 if (it == tree.end())
248 return size_type{};
249
250 size_type res{};
251 while (tree.keys_equal(tree.get_key(*it), key))
252 {
253 ++res;
254 it = tree.erase(it);
255 }
256
257 return res;
258 }
259
260 template<class Tree, class Key>
261 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
262 {
263 auto it = lower_bound_const(tree, key);
264
265 return typename Tree::iterator{it.node(), it.end()};
266 }
267
268 template<class Tree, class Key>
269 static typename Tree::const_iterator lower_bound_const(const Tree& tree, const Key& key)
270 {
271 using const_iterator = typename Tree::const_iterator;
272
273 auto node = tree.find_parent_for_insertion(key);
274 const_iterator it{node, false};
275 auto beg = tree.begin();
276 auto end = tree.end();
277
278 if (tree.keys_comp(key, *it))
279 --it; // Incase we are on a successor.
280 while (tree.keys_equal(tree.get_key(*it), key) && it != beg)
281 --it; // Skip keys that are equal.
282 if (it != beg)
283 ++it; // If we moved all the way to the start, key is the smallest.
284
285 if (tree.key_compare_(tree.get_key(*it), key))
286 {
287 // Predecessor.
288 if (it != end)
289 return ++it;
290 else
291 return it;
292 }
293
294 return it;
295 }
296
297 template<class Tree, class Key>
298 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
299 {
300 auto it = upper_bound_const(tree, key);
301
302 return typename Tree::iterator{it.node(), it.end()};
303 }
304
305 template<class Tree, class Key>
306 static typename Tree::const_iterator upper_bound_const(const Tree& tree, const Key& key)
307 {
308 /**
309 * If key isn't in the tree, we get it's
310 * successor or tree.end(). If key is
311 * in the tree, we get it.
312 * In the first case, the successor is also
313 * the upper bound, so we just return it,
314 * otherwise (as long as it != end()) we
315 * increment.
316 */
317 auto it = lower_bound(tree, key);
318 if (it == tree.end())
319 return it;
320 else if (tree.keys_equal(tree.get_key(*it), key))
321 {
322 while (tree.keys_equal(tree.get_key(*it), key))
323 ++it;
324
325 return it;
326 }
327
328 return it;
329 }
330
331 template<class Tree, class Key>
332 static pair<
333 typename Tree::iterator,
334 typename Tree::iterator
335 > equal_range(const Tree& tree, const Key& key)
336 {
337 return make_pair(
338 lower_bound(tree, key),
339 upper_bound(tree, key)
340 );
341 }
342
343 template<class Tree, class Key>
344 static pair<
345 typename Tree::const_iterator,
346 typename Tree::const_iterator
347 > equal_range_const(const Tree& tree, const Key& key)
348 {
349 return make_pair(
350 lower_bound_const(tree, key),
351 upper_bound_const(tree, key)
352 );
353 }
354
355 template<class Tree, class... Args>
356 static typename Tree::iterator emplace(Tree& tree, Args&&... args)
357 {
358 using node_type = typename Tree::node_type;
359
360 auto node = node_type{forward<Args>(args)...};
361
362 return insert(tree, node);
363 }
364
365 template<class Tree, class Value>
366 static typename Tree::iterator insert(Tree& tree, const Value& val)
367 {
368 using node_type = typename Tree::node_type;
369
370 auto node = new node_type{val};
371
372 return insert(tree, node);
373 }
374
375 template<class Tree, class Value>
376 static typename Tree::iterator insert(Tree& tree, Value&& val)
377 {
378 using node_type = typename Tree::node_type;
379
380 auto node = new node_type{forward<Value>(val)};
381
382 return insert(tree, node);
383 }
384
385 template<class Tree>
386 static typename Tree::iterator insert(Tree& tree, typename Tree::node_type* node)
387 {
388 using iterator = typename Tree::iterator;
389
390 auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
391 tree.insert_node(node, parent);
392
393 return iterator{node, false};
394 }
395 };
396}
397
398#endif
399
Note: See TracBrowser for help on using the repository browser.