source: mainline/uspace/lib/cpp/include/__bits/adt/hash_table_policies.hpp

Last change on this file was a853075, checked in by Dzejrou <dzejrou@…>, 7 years ago

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