source: mainline/uspace/lib/cpp/include/internal/rbtree_policies.hpp@ 49fbfb5

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

cpp: added emplace and count to tree single policy and stubs for the rest in that policy
  • Property mode set to 100644
File size: 6.0 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>
46 static pair<
47 typename Tree::node_type*,
48 typename Tree::node_type*
49 > erase(const Tree& tree, const Key& key)
50 {
51 // TODO:
52 }
53
54 template<class Tree, class Key>
55 static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
56 {
57 // TODO:
58 }
59
60 template<class Tree, class Key>
61 static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
62 {
63 // TODO:
64 }
65
66 template<class Tree, class Key>
67 static pair<
68 typename Tree::iterator,
69 typename Tree::iterator
70 > equal_range(const Tree& tree, const Key& key)
71 {
72 // TODO:
73 }
74
75 template<class Tree, class Key>
76 static pair<
77 typename Tree::const_iterator,
78 typename Tree::const_iterator
79 > equal_range_const(const Tree& tree, const Key& key)
80 {
81 // TODO:
82 }
83
84 /**
85 * Note: We have to duplicate code for emplace, insert(const&)
86 * and insert(&&) here, because the node (which makes distinction
87 * between the arguments) is only created if the value isn't
88 * in the tree already.
89 */
90
91 template<class Tree, class... Args>
92 static pair<
93 typename Tree::iterator, bool
94 > emplace(Tree& tree, Args&&... args)
95 {
96 using value_type = typename Tree::value_type;
97 using iterator = typename Tree::iterator;
98 using node_type = typename Tree::node_type;
99
100 auto val = value_type{forward<Args>(args)...};
101 auto parent = tree.find_parent_for_insertion(val);
102 if (!parent)
103 {
104 tree.root_ = new node_type{move(val)};
105
106 return make_pair(iterator{tree.root_}, true);
107 }
108
109 if (tree.get_key(parent->value) == tree.get_key(val))
110 return make_pair(iterator{parent}, false);
111
112 auto node = new node_type{move(val)};
113 if (tree.keys_comp(tree.get_key(val), parent->value))
114 parent->add_left_child(node);
115 else
116 parent->add_right_child(node);
117
118 return make_pair(iterator{node}, true);
119 }
[4d65515]120
121 template<class Tree, class Value>
122 static pair<
123 typename Tree::iterator, bool
124 > insert(Tree& tree, const Value& val)
125 {
126 using iterator = typename Tree::iterator;
127 using node_type = typename Tree::node_type;
128
129 auto parent = tree.find_parent_for_insertion(val);
130 if (!parent)
131 {
132 tree.root_ = new node_type{val};
133
134 return make_pair(iterator{tree.root_}, true);
135 }
136
137 if (tree.get_key(parent->value) == tree.get_key(val))
138 return make_pair(iterator{parent}, false);
139
140 auto node = new node_type{val};
141 if (tree.keys_comp(tree.get_key(val), parent->value))
142 parent->add_left_child(node);
143 else
144 parent->add_right_child(node);
145
146 return make_pair(iterator{node}, true);
147 }
148
149 template<class Tree, class Value>
150 static pair<
151 typename Tree::iterator, bool
152 > insert(Tree& tree, Value&& val)
153 {
154 using iterator = typename Tree::iterator;
155 using node_type = typename Tree::node_type;
156
157 auto parent = tree.find_parent_for_insertion(val);
158 if (!parent)
159 {
160 tree.root_ = new node_type{forward<Value>(val)};
161
162 return make_pair(iterator{tree.root_}, true);
163 }
164
165 if (tree.get_key(parent->value) == tree.get_key(val))
166 return make_pair(iterator{parent}, false);
167
168 auto node = new node_type{forward<Value>(val)};
169 if (tree.keys_comp(tree.get_key(val), parent->value))
170 parent->add_left_child(node);
171 else
172 parent->add_right_child(node);
173
174 return make_pair(iterator{node}, true);
175 }
176 };
177
178 struct rbtree_multi_policy
179 {
180 // TODO:
181 };
182}
183
184#endif
185
Note: See TracBrowser for help on using the repository browser.