source: mainline/uspace/lib/cpp/include/internal/hash_table_policies.hpp@ 4f080f2a

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

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