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

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

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