source: mainline/uspace/lib/cpp/include/__bits/hash_table_policies.hpp@ 2e53e83d

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

cpp: changed internal to bits to avoid include space pollusion, fixed old std::hel:: bugs in files that weren't touched since
  • Property mode set to 100644
File size: 13.0 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_HASH_TABLE_POLICIES
30#define LIBCPP_BITS_HASH_TABLE_POLICIES
31
32#include <tuple>
33#include <utility>
34
35namespace std::aux
36{
37 struct hash_single_policy
38 {
39 template<class Table, class Key>
40 static typename Table::size_type count(const Table& table, const Key& key)
41 {
42 return table.find(key) == table.end() ? 0 : 1;
43 }
44
45 template<class Table, class Key>
46 static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)
47 {
48 auto idx = table.get_bucket_idx_(key);
49 return make_tuple(
50 &table.table_[idx],
51 table.table_[idx].head,
52 idx
53 );
54 }
55
56 template<class Table, class Key>
57 static typename Table::size_type erase(Table& table, const Key& key)
58 {
59 auto idx = table.get_bucket_idx_(key);
60 auto head = table.table_[idx].head;
61 auto current = head;
62
63 if (!current)
64 return 0;
65
66 do
67 {
68 if (table.keys_equal(key, current->value))
69 {
70 --table.size_;
71
72 if (current == head)
73 {
74 if (current->next != head)
75 table.table_[idx].head = current->next;
76 else
77 table.table_[idx].head = nullptr;
78 }
79
80 current->unlink();
81 delete current;
82
83 return 1;
84 }
85 else
86 current = current->next;
87 }
88 while (current != head);
89
90 return 0;
91 }
92
93 template<class Table, class Key>
94 static pair<
95 typename Table::iterator,
96 typename Table::iterator
97 > equal_range(Table& table, const Key& key)
98 {
99 auto it = table.find(key);
100 return make_pair(it, ++it);
101 }
102
103 template<class Table, class Key>
104 static pair<
105 typename Table::const_iterator,
106 typename Table::const_iterator
107 > equal_range_const(const Table& table, const Key& key)
108 { // Note: We cannot overload by return type, so we use a different name.
109 auto it = table.find(key);
110 return make_pair(it, ++it);
111 }
112
113 /**
114 * Note: We have to duplicate code for emplace, insert(const&)
115 * and insert(&&) here, because the node (which makes distinction
116 * between the arguments) is only created if the value isn't
117 * in the table already.
118 */
119
120 template<class Table, class... Args>
121 static pair<
122 typename Table::iterator, bool
123 > emplace(Table& table, Args&&... args)
124 {
125 using value_type = typename Table::value_type;
126 using node_type = typename Table::node_type;
127 using iterator = typename Table::iterator;
128
129 table.increment_size();
130
131 auto val = value_type{forward<Args>(args)...};
132 const auto& key = table.get_key(val);
133 auto [bucket, target, idx] = table.find_insertion_spot(key);
134
135 if (!bucket)
136 return make_pair(table.end(), false);
137
138 if (target && table.keys_equal(key, target->value))
139 {
140 table.decrement_size();
141
142 return make_pair(
143 iterator{
144 table.table(), idx, table.bucket_count(),
145 target
146 },
147 false
148 );
149 }
150 else
151 {
152 auto node = new node_type{move(val)};
153 bucket->prepend(node);
154
155 return make_pair(iterator{
156 table.table(), idx,
157 table.bucket_count(),
158 node
159 }, true);
160 }
161 }
162
163 template<class Table, class Value>
164 static pair<
165 typename Table::iterator, bool
166 > insert(Table& table, const Value& val)
167 {
168 using node_type = typename Table::node_type;
169 using iterator = typename Table::iterator;
170
171 table.increment_size();
172
173 const auto& key = table.get_key(val);
174 auto [bucket, target, idx] = table.find_insertion_spot(key);
175
176 if (!bucket)
177 return make_pair(table.end(), false);
178
179 if (target && table.keys_equal(key, target->value))
180 {
181 table.decrement_size();
182
183 return make_pair(
184 iterator{
185 table.table(), idx, table.bucket_count(),
186 target
187 },
188 false
189 );
190 }
191 else
192 {
193 auto node = new node_type{val};
194 bucket->prepend(node);
195
196 return make_pair(iterator{
197 table.table(), idx,
198 table.bucket_count(),
199 node
200 }, true);
201 }
202 }
203
204 template<class Table, class Value>
205 static pair<
206 typename Table::iterator, bool
207 > insert(Table& table, Value&& val)
208 {
209 using value_type = typename Table::value_type;
210 using node_type = typename Table::node_type;
211 using iterator = typename Table::iterator;
212
213 table.increment_size();
214
215 const auto& key = table.get_key(val);
216 auto [bucket, target, idx] = table.find_insertion_spot(key);
217
218 if (!bucket)
219 return make_pair(table.end(), false);
220
221 if (target && table.keys_equal(key, target->value))
222 {
223 table.decrement_size();
224
225 return make_pair(
226 iterator{
227 table.table(), idx, table.bucket_count(),
228 target
229 },
230 false
231 );
232 }
233 else
234 {
235 auto node = new node_type{forward<value_type>(val)};
236 bucket->prepend(node);
237
238 return make_pair(iterator{
239 table.table(), idx,
240 table.bucket_count(),
241 node
242 }, true);
243 }
244 }
245 };
246
247 struct hash_multi_policy
248 {
249 template<class Table, class Key>
250 static typename Table::size_type count(const Table& table, const Key& key)
251 {
252 auto head = table.table_[table.get_bucket_idx_(key)].head;
253 if (!head)
254 return 0;
255
256 auto current = head;
257 typename Table::size_type res = 0;
258 do
259 {
260 if (table.keys_equal(key, current->value))
261 ++res;
262
263 current = current->next;
264 }
265 while (current != head);
266
267 return res;
268 }
269
270 template<class Table, class Key>
271 static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)
272 {
273 auto idx = table.get_bucket_idx_(key);
274 auto head = table.table_[idx].head;
275
276 if (head)
277 {
278 auto current = head;
279 do
280 {
281 if (table.keys_equal(key, current->value))
282 {
283 return make_tuple(
284 &table.table_[idx],
285 current,
286 idx
287 );
288 }
289
290 current = current->next;
291 } while (current != head);
292 }
293
294 return make_tuple(
295 &table.table_[idx],
296 table.table_[idx].head,
297 idx
298 );
299 }
300
301 template<class Table, class Key>
302 static typename Table::size_type erase(Table& table, const Key& key)
303 {
304 auto idx = table.get_bucket_idx_(key);
305 auto head = table.table_[idx].head;
306 auto current = head;
307 table.table_[idx].head = nullptr;
308
309 if (!current)
310 return 0;
311
312 /**
313 * We traverse the list and delete if the keys
314 * equal, if they don't we append the nodes back
315 * to the bucket.
316 */
317 typename Table::size_type res{};
318
319 do
320 {
321 auto tmp = current;
322 current = current->next;
323
324 if (!table.keys_equal(key, tmp->value))
325 table.table_[idx].append(tmp);
326 else
327 {
328 ++res;
329 --table.size_;
330
331 delete tmp;
332 }
333 }
334 while (current != head);
335
336 return res;
337 }
338
339 template<class Table, class Key>
340 static pair<
341 typename Table::iterator,
342 typename Table::iterator
343 > equal_range(Table& table, const Key& key)
344 {
345 auto first = table.find(key);
346 if (first == table.end())
347 return make_pair(table.end(), table.end());
348
349 auto last = first;
350 do
351 {
352 ++last;
353 } while (table.keys_equal(key, *last));
354
355 return make_pair(first, last);
356 }
357
358 template<class Table, class Key>
359 static pair<
360 typename Table::const_iterator,
361 typename Table::const_iterator
362 > equal_range_const(const Table& table, const Key& key)
363 {
364 auto first = table.find(key);
365 if (first == table.end())
366 return make_pair(table.end(), table.end());
367
368 auto last = first;
369 do
370 {
371 ++last;
372 } while (table.keys_equal(key, *last));
373
374 return make_pair(first, last);
375 }
376
377 template<class Table, class... Args>
378 static typename Table::iterator emplace(Table& table, Args&&... args)
379 {
380 using node_type = typename Table::node_type;
381
382 auto node = new node_type{forward<Args>(args)...};
383
384 return insert(table, node);
385 }
386
387 template<class Table, class Value>
388 static typename Table::iterator insert(Table& table, const Value& val)
389 {
390 using node_type = typename Table::node_type;
391
392 auto node = new node_type{val};
393
394 return insert(table, node);
395 }
396
397 template<class Table, class Value>
398 static typename Table::iterator insert(Table& table, Value&& val)
399 {
400 using value_type = typename Table::value_type;
401 using node_type = typename Table::node_type;
402
403 auto node = new node_type{forward<value_type>(val)};
404
405 return insert(table, node);
406 }
407
408 template<class Table>
409 static typename Table::iterator insert(Table& table, typename Table::node_type* node)
410 {
411 using iterator = typename Table::iterator;
412
413 table.increment_size();
414
415 const auto& key = table.get_key(node->value);
416 auto [bucket, target, idx] = table.find_insertion_spot(key);
417
418 if (!bucket)
419 table.end();
420
421 if (target && table.keys_equal(key, target->value))
422 target->append(node);
423 else
424 bucket->prepend(node);
425
426 return iterator{
427 table.table(), idx,
428 table.bucket_count(),
429 node
430 };
431 }
432 };
433}
434
435#endif
Note: See TracBrowser for help on using the repository browser.