1 | // Hashtable implementation used by containers -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2021 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, or (at your option) |
9 | // any later version. |
10 | |
11 | // This library is distributed in the hope that it will be useful, |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | // GNU General Public License for more details. |
15 | |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version |
18 | // 3.1, as published by the Free Software Foundation. |
19 | |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
23 | // <http://www.gnu.org/licenses/>. |
24 | |
25 | /* |
26 | * Copyright (c) 1996,1997 |
27 | * Silicon Graphics Computer Systems, Inc. |
28 | * |
29 | * Permission to use, copy, modify, distribute and sell this software |
30 | * and its documentation for any purpose is hereby granted without fee, |
31 | * provided that the above copyright notice appear in all copies and |
32 | * that both that copyright notice and this permission notice appear |
33 | * in supporting documentation. Silicon Graphics makes no |
34 | * representations about the suitability of this software for any |
35 | * purpose. It is provided "as is" without express or implied warranty. |
36 | * |
37 | * |
38 | * Copyright (c) 1994 |
39 | * Hewlett-Packard Company |
40 | * |
41 | * Permission to use, copy, modify, distribute and sell this software |
42 | * and its documentation for any purpose is hereby granted without fee, |
43 | * provided that the above copyright notice appear in all copies and |
44 | * that both that copyright notice and this permission notice appear |
45 | * in supporting documentation. Hewlett-Packard Company makes no |
46 | * representations about the suitability of this software for any |
47 | * purpose. It is provided "as is" without express or implied warranty. |
48 | * |
49 | */ |
50 | |
51 | /** @file backward/hashtable.h |
52 | * This file is a GNU extension to the Standard C++ Library (possibly |
53 | * containing extensions from the HP/SGI STL subset). |
54 | */ |
55 | |
56 | #ifndef _BACKWARD_HASHTABLE_H |
57 | #define _BACKWARD_HASHTABLE_H 1 |
58 | |
59 | // Hashtable class, used to implement the hashed associative containers |
60 | // hash_set, hash_map, hash_multiset, and hash_multimap. |
61 | |
62 | #include <vector> |
63 | #include <iterator> |
64 | #include <algorithm> |
65 | #include <bits/stl_function.h> |
66 | #include <ext/alloc_traits.h> |
67 | #include <backward/hash_fun.h> |
68 | |
69 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
70 | { |
71 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
72 | |
73 | template<class _Val> |
74 | struct _Hashtable_node |
75 | { |
76 | _Hashtable_node* _M_next; |
77 | _Val _M_val; |
78 | }; |
79 | |
80 | template<class _Val, class _Key, class _HashFcn, class _ExtractKey, |
81 | class _EqualKey, class _Alloc = std::allocator<_Val> > |
82 | class hashtable; |
83 | |
84 | template<class _Val, class _Key, class _HashFcn, |
85 | class _ExtractKey, class _EqualKey, class _Alloc> |
86 | struct _Hashtable_iterator; |
87 | |
88 | template<class _Val, class _Key, class _HashFcn, |
89 | class _ExtractKey, class _EqualKey, class _Alloc> |
90 | struct _Hashtable_const_iterator; |
91 | |
92 | template<class _Val, class _Key, class _HashFcn, |
93 | class _ExtractKey, class _EqualKey, class _Alloc> |
94 | struct _Hashtable_iterator |
95 | { |
96 | typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> |
97 | _Hashtable; |
98 | typedef _Hashtable_iterator<_Val, _Key, _HashFcn, |
99 | _ExtractKey, _EqualKey, _Alloc> |
100 | iterator; |
101 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, |
102 | _ExtractKey, _EqualKey, _Alloc> |
103 | const_iterator; |
104 | typedef _Hashtable_node<_Val> _Node; |
105 | typedef std::forward_iterator_tag iterator_category; |
106 | typedef _Val value_type; |
107 | typedef std::ptrdiff_t difference_type; |
108 | typedef std::size_t size_type; |
109 | typedef _Val& reference; |
110 | typedef _Val* pointer; |
111 | |
112 | _Node* _M_cur; |
113 | _Hashtable* _M_ht; |
114 | |
115 | (_Node* __n, _Hashtable* __tab) |
116 | : _M_cur(__n), _M_ht(__tab) { } |
117 | |
118 | () { } |
119 | |
120 | reference |
121 | operator*() const |
122 | { return _M_cur->_M_val; } |
123 | |
124 | pointer |
125 | operator->() const |
126 | { return &(operator*()); } |
127 | |
128 | iterator& |
129 | operator++(); |
130 | |
131 | iterator |
132 | operator++(int); |
133 | |
134 | bool |
135 | operator==(const iterator& __it) const |
136 | { return _M_cur == __it._M_cur; } |
137 | |
138 | bool |
139 | operator!=(const iterator& __it) const |
140 | { return _M_cur != __it._M_cur; } |
141 | }; |
142 | |
143 | template<class _Val, class _Key, class _HashFcn, |
144 | class _ExtractKey, class _EqualKey, class _Alloc> |
145 | struct _Hashtable_const_iterator |
146 | { |
147 | typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> |
148 | _Hashtable; |
149 | typedef _Hashtable_iterator<_Val,_Key,_HashFcn, |
150 | _ExtractKey,_EqualKey,_Alloc> |
151 | iterator; |
152 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, |
153 | _ExtractKey, _EqualKey, _Alloc> |
154 | const_iterator; |
155 | typedef _Hashtable_node<_Val> _Node; |
156 | |
157 | typedef std::forward_iterator_tag iterator_category; |
158 | typedef _Val value_type; |
159 | typedef std::ptrdiff_t difference_type; |
160 | typedef std::size_t size_type; |
161 | typedef const _Val& reference; |
162 | typedef const _Val* pointer; |
163 | |
164 | const _Node* _M_cur; |
165 | const _Hashtable* _M_ht; |
166 | |
167 | (const _Node* __n, const _Hashtable* __tab) |
168 | : _M_cur(__n), _M_ht(__tab) { } |
169 | |
170 | () { } |
171 | |
172 | (const iterator& __it) |
173 | : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { } |
174 | |
175 | reference |
176 | operator*() const |
177 | { return _M_cur->_M_val; } |
178 | |
179 | pointer |
180 | operator->() const |
181 | { return &(operator*()); } |
182 | |
183 | const_iterator& |
184 | operator++(); |
185 | |
186 | const_iterator |
187 | operator++(int); |
188 | |
189 | bool |
190 | operator==(const const_iterator& __it) const |
191 | { return _M_cur == __it._M_cur; } |
192 | |
193 | bool |
194 | operator!=(const const_iterator& __it) const |
195 | { return _M_cur != __it._M_cur; } |
196 | }; |
197 | |
198 | // Note: assumes long is at least 32 bits. |
199 | enum { _S_num_primes = 29 }; |
200 | |
201 | template<typename _PrimeType> |
202 | struct _Hashtable_prime_list |
203 | { |
204 | static const _PrimeType __stl_prime_list[_S_num_primes]; |
205 | |
206 | static const _PrimeType* |
207 | _S_get_prime_list(); |
208 | }; |
209 | |
210 | template<typename _PrimeType> const _PrimeType |
211 | _Hashtable_prime_list<_PrimeType>::__stl_prime_list[_S_num_primes] = |
212 | { |
213 | 5ul, 53ul, 97ul, 193ul, 389ul, |
214 | 769ul, 1543ul, 3079ul, 6151ul, 12289ul, |
215 | 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, |
216 | 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, |
217 | 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, |
218 | 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul |
219 | }; |
220 | |
221 | template<class _PrimeType> inline const _PrimeType* |
222 | _Hashtable_prime_list<_PrimeType>::_S_get_prime_list() |
223 | { |
224 | return __stl_prime_list; |
225 | } |
226 | |
227 | inline unsigned long |
228 | __stl_next_prime(unsigned long __n) |
229 | { |
230 | const unsigned long* __first = _Hashtable_prime_list<unsigned long>::_S_get_prime_list(); |
231 | const unsigned long* __last = __first + (int)_S_num_primes; |
232 | const unsigned long* pos = std::lower_bound(__first, __last, val: __n); |
233 | return pos == __last ? *(__last - 1) : *pos; |
234 | } |
235 | |
236 | // Forward declaration of operator==. |
237 | template<class _Val, class _Key, class _HF, class _Ex, |
238 | class _Eq, class _All> |
239 | class hashtable; |
240 | |
241 | template<class _Val, class _Key, class _HF, class _Ex, |
242 | class _Eq, class _All> |
243 | bool |
244 | operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, |
245 | const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); |
246 | |
247 | // Hashtables handle allocators a bit differently than other |
248 | // containers do. If we're using standard-conforming allocators, then |
249 | // a hashtable unconditionally has a member variable to hold its |
250 | // allocator, even if it so happens that all instances of the |
251 | // allocator type are identical. This is because, for hashtables, |
252 | // this extra storage is negligible. Additionally, a base class |
253 | // wouldn't serve any other purposes; it wouldn't, for example, |
254 | // simplify the exception-handling code. |
255 | template<class _Val, class _Key, class _HashFcn, |
256 | class _ExtractKey, class _EqualKey, class _Alloc> |
257 | class hashtable |
258 | { |
259 | public: |
260 | typedef _Key key_type; |
261 | typedef _Val value_type; |
262 | typedef _HashFcn hasher; |
263 | typedef _EqualKey key_equal; |
264 | |
265 | typedef std::size_t size_type; |
266 | typedef std::ptrdiff_t difference_type; |
267 | typedef value_type* pointer; |
268 | typedef const value_type* const_pointer; |
269 | typedef value_type& reference; |
270 | typedef const value_type& const_reference; |
271 | |
272 | hasher |
273 | hash_funct() const |
274 | { return _M_hash; } |
275 | |
276 | key_equal |
277 | key_eq() const |
278 | { return _M_equals; } |
279 | |
280 | private: |
281 | typedef _Hashtable_node<_Val> _Node; |
282 | |
283 | public: |
284 | typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template |
285 | rebind<value_type>::other allocator_type; |
286 | |
287 | allocator_type |
288 | get_allocator() const |
289 | { return _M_node_allocator; } |
290 | |
291 | private: |
292 | typedef __gnu_cxx::__alloc_traits<allocator_type> _Alloc_traits; |
293 | typedef typename _Alloc_traits::template rebind<_Node>::other |
294 | _Node_Alloc; |
295 | typedef typename _Alloc_traits::template rebind<_Node*>::other |
296 | _Nodeptr_Alloc; |
297 | typedef std::vector<_Node*, _Nodeptr_Alloc> _Vector_type; |
298 | |
299 | _Node_Alloc _M_node_allocator; |
300 | |
301 | _Node* |
302 | _M_get_node() |
303 | { return _M_node_allocator.allocate(1); } |
304 | |
305 | void |
306 | _M_put_node(_Node* __p) |
307 | { _M_node_allocator.deallocate(__p, 1); } |
308 | |
309 | private: |
310 | hasher _M_hash; |
311 | key_equal _M_equals; |
312 | _ExtractKey _M_get_key; |
313 | _Vector_type _M_buckets; |
314 | size_type _M_num_elements; |
315 | |
316 | public: |
317 | typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, |
318 | _EqualKey, _Alloc> |
319 | iterator; |
320 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, |
321 | _EqualKey, _Alloc> |
322 | const_iterator; |
323 | |
324 | friend struct |
325 | _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; |
326 | |
327 | friend struct |
328 | _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, |
329 | _EqualKey, _Alloc>; |
330 | |
331 | public: |
332 | (size_type __n, const _HashFcn& __hf, |
333 | const _EqualKey& __eql, const _ExtractKey& __ext, |
334 | const allocator_type& __a = allocator_type()) |
335 | : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), |
336 | _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) |
337 | { _M_initialize_buckets(__n); } |
338 | |
339 | (size_type __n, const _HashFcn& __hf, |
340 | const _EqualKey& __eql, |
341 | const allocator_type& __a = allocator_type()) |
342 | : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), |
343 | _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) |
344 | { _M_initialize_buckets(__n); } |
345 | |
346 | (const hashtable& __ht) |
347 | : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), |
348 | _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), |
349 | _M_buckets(__ht.get_allocator()), _M_num_elements(0) |
350 | { _M_copy_from(__ht); } |
351 | |
352 | hashtable& |
353 | operator= (const hashtable& __ht) |
354 | { |
355 | if (&__ht != this) |
356 | { |
357 | clear(); |
358 | _M_hash = __ht._M_hash; |
359 | _M_equals = __ht._M_equals; |
360 | _M_get_key = __ht._M_get_key; |
361 | _M_copy_from(__ht); |
362 | } |
363 | return *this; |
364 | } |
365 | |
366 | () |
367 | { clear(); } |
368 | |
369 | size_type |
370 | size() const |
371 | { return _M_num_elements; } |
372 | |
373 | size_type |
374 | max_size() const |
375 | { return size_type(-1); } |
376 | |
377 | _GLIBCXX_NODISCARD bool |
378 | empty() const |
379 | { return size() == 0; } |
380 | |
381 | void |
382 | swap(hashtable& __ht) |
383 | { |
384 | std::swap(_M_hash, __ht._M_hash); |
385 | std::swap(_M_equals, __ht._M_equals); |
386 | std::swap(_M_get_key, __ht._M_get_key); |
387 | _M_buckets.swap(__ht._M_buckets); |
388 | std::swap(_M_num_elements, __ht._M_num_elements); |
389 | } |
390 | |
391 | iterator |
392 | begin() |
393 | { |
394 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) |
395 | if (_M_buckets[__n]) |
396 | return iterator(_M_buckets[__n], this); |
397 | return end(); |
398 | } |
399 | |
400 | iterator |
401 | end() |
402 | { return iterator(0, this); } |
403 | |
404 | const_iterator |
405 | begin() const |
406 | { |
407 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) |
408 | if (_M_buckets[__n]) |
409 | return const_iterator(_M_buckets[__n], this); |
410 | return end(); |
411 | } |
412 | |
413 | const_iterator |
414 | end() const |
415 | { return const_iterator(0, this); } |
416 | |
417 | template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, |
418 | class _Al> |
419 | friend bool |
420 | operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, |
421 | const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); |
422 | |
423 | public: |
424 | size_type |
425 | bucket_count() const |
426 | { return _M_buckets.size(); } |
427 | |
428 | size_type |
429 | max_bucket_count() const |
430 | { return _Hashtable_prime_list<unsigned long>:: |
431 | _S_get_prime_list()[(int)_S_num_primes - 1]; |
432 | } |
433 | |
434 | size_type |
435 | elems_in_bucket(size_type __bucket) const |
436 | { |
437 | size_type __result = 0; |
438 | for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) |
439 | __result += 1; |
440 | return __result; |
441 | } |
442 | |
443 | std::pair<iterator, bool> |
444 | insert_unique(const value_type& __obj) |
445 | { |
446 | resize(num_elements_hint: _M_num_elements + 1); |
447 | return insert_unique_noresize(__obj); |
448 | } |
449 | |
450 | iterator |
451 | insert_equal(const value_type& __obj) |
452 | { |
453 | resize(num_elements_hint: _M_num_elements + 1); |
454 | return insert_equal_noresize(__obj); |
455 | } |
456 | |
457 | std::pair<iterator, bool> |
458 | insert_unique_noresize(const value_type& __obj); |
459 | |
460 | iterator |
461 | insert_equal_noresize(const value_type& __obj); |
462 | |
463 | template<class _InputIterator> |
464 | void |
465 | insert_unique(_InputIterator __f, _InputIterator __l) |
466 | { insert_unique(__f, __l, std::__iterator_category(__f)); } |
467 | |
468 | template<class _InputIterator> |
469 | void |
470 | insert_equal(_InputIterator __f, _InputIterator __l) |
471 | { insert_equal(__f, __l, std::__iterator_category(__f)); } |
472 | |
473 | template<class _InputIterator> |
474 | void |
475 | insert_unique(_InputIterator __f, _InputIterator __l, |
476 | std::input_iterator_tag) |
477 | { |
478 | for ( ; __f != __l; ++__f) |
479 | insert_unique(*__f); |
480 | } |
481 | |
482 | template<class _InputIterator> |
483 | void |
484 | insert_equal(_InputIterator __f, _InputIterator __l, |
485 | std::input_iterator_tag) |
486 | { |
487 | for ( ; __f != __l; ++__f) |
488 | insert_equal(*__f); |
489 | } |
490 | |
491 | template<class _ForwardIterator> |
492 | void |
493 | insert_unique(_ForwardIterator __f, _ForwardIterator __l, |
494 | std::forward_iterator_tag) |
495 | { |
496 | size_type __n = std::distance(__f, __l); |
497 | resize(num_elements_hint: _M_num_elements + __n); |
498 | for ( ; __n > 0; --__n, ++__f) |
499 | insert_unique_noresize(obj: *__f); |
500 | } |
501 | |
502 | template<class _ForwardIterator> |
503 | void |
504 | insert_equal(_ForwardIterator __f, _ForwardIterator __l, |
505 | std::forward_iterator_tag) |
506 | { |
507 | size_type __n = std::distance(__f, __l); |
508 | resize(num_elements_hint: _M_num_elements + __n); |
509 | for ( ; __n > 0; --__n, ++__f) |
510 | insert_equal_noresize(obj: *__f); |
511 | } |
512 | |
513 | reference |
514 | find_or_insert(const value_type& __obj); |
515 | |
516 | iterator |
517 | find(const key_type& __key) |
518 | { |
519 | size_type __n = _M_bkt_num_key(__key); |
520 | _Node* __first; |
521 | for (__first = _M_buckets[__n]; |
522 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); |
523 | __first = __first->_M_next) |
524 | { } |
525 | return iterator(__first, this); |
526 | } |
527 | |
528 | const_iterator |
529 | find(const key_type& __key) const |
530 | { |
531 | size_type __n = _M_bkt_num_key(__key); |
532 | const _Node* __first; |
533 | for (__first = _M_buckets[__n]; |
534 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); |
535 | __first = __first->_M_next) |
536 | { } |
537 | return const_iterator(__first, this); |
538 | } |
539 | |
540 | size_type |
541 | count(const key_type& __key) const |
542 | { |
543 | const size_type __n = _M_bkt_num_key(__key); |
544 | size_type __result = 0; |
545 | |
546 | for (const _Node* __cur = _M_buckets[__n]; __cur; |
547 | __cur = __cur->_M_next) |
548 | if (_M_equals(_M_get_key(__cur->_M_val), __key)) |
549 | ++__result; |
550 | return __result; |
551 | } |
552 | |
553 | std::pair<iterator, iterator> |
554 | equal_range(const key_type& __key); |
555 | |
556 | std::pair<const_iterator, const_iterator> |
557 | equal_range(const key_type& __key) const; |
558 | |
559 | size_type |
560 | erase(const key_type& __key); |
561 | |
562 | void |
563 | erase(const iterator& __it); |
564 | |
565 | void |
566 | erase(iterator __first, iterator __last); |
567 | |
568 | void |
569 | erase(const const_iterator& __it); |
570 | |
571 | void |
572 | erase(const_iterator __first, const_iterator __last); |
573 | |
574 | void |
575 | resize(size_type __num_elements_hint); |
576 | |
577 | void |
578 | clear(); |
579 | |
580 | private: |
581 | size_type |
582 | _M_next_size(size_type __n) const |
583 | { return __stl_next_prime(__n); } |
584 | |
585 | void |
586 | _M_initialize_buckets(size_type __n) |
587 | { |
588 | const size_type __n_buckets = _M_next_size(__n); |
589 | _M_buckets.reserve(__n_buckets); |
590 | _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); |
591 | _M_num_elements = 0; |
592 | } |
593 | |
594 | size_type |
595 | _M_bkt_num_key(const key_type& __key) const |
596 | { return _M_bkt_num_key(__key, _M_buckets.size()); } |
597 | |
598 | size_type |
599 | _M_bkt_num(const value_type& __obj) const |
600 | { return _M_bkt_num_key(_M_get_key(__obj)); } |
601 | |
602 | size_type |
603 | _M_bkt_num_key(const key_type& __key, std::size_t __n) const |
604 | { return _M_hash(__key) % __n; } |
605 | |
606 | size_type |
607 | _M_bkt_num(const value_type& __obj, std::size_t __n) const |
608 | { return _M_bkt_num_key(_M_get_key(__obj), __n); } |
609 | |
610 | _Node* |
611 | _M_new_node(const value_type& __obj) |
612 | { |
613 | _Node* __n = _M_get_node(); |
614 | __n->_M_next = 0; |
615 | __try |
616 | { |
617 | allocator_type __a = this->get_allocator(); |
618 | _Alloc_traits::construct(__a, &__n->_M_val, __obj); |
619 | return __n; |
620 | } |
621 | __catch(...) |
622 | { |
623 | _M_put_node(p: __n); |
624 | __throw_exception_again; |
625 | } |
626 | } |
627 | |
628 | void |
629 | _M_delete_node(_Node* __n) |
630 | { |
631 | allocator_type __a = this->get_allocator(); |
632 | _Alloc_traits::destroy(__a, &__n->_M_val); |
633 | _M_put_node(p: __n); |
634 | } |
635 | |
636 | void |
637 | _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); |
638 | |
639 | void |
640 | _M_erase_bucket(const size_type __n, _Node* __last); |
641 | |
642 | void |
643 | _M_copy_from(const hashtable& __ht); |
644 | }; |
645 | |
646 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, |
647 | class _All> |
648 | _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& |
649 | _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: |
650 | operator++() |
651 | { |
652 | const _Node* __old = _M_cur; |
653 | _M_cur = _M_cur->_M_next; |
654 | if (!_M_cur) |
655 | { |
656 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); |
657 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) |
658 | _M_cur = _M_ht->_M_buckets[__bucket]; |
659 | } |
660 | return *this; |
661 | } |
662 | |
663 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, |
664 | class _All> |
665 | inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> |
666 | _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: |
667 | operator++(int) |
668 | { |
669 | iterator __tmp = *this; |
670 | ++*this; |
671 | return __tmp; |
672 | } |
673 | |
674 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, |
675 | class _All> |
676 | _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& |
677 | _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: |
678 | operator++() |
679 | { |
680 | const _Node* __old = _M_cur; |
681 | _M_cur = _M_cur->_M_next; |
682 | if (!_M_cur) |
683 | { |
684 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); |
685 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) |
686 | _M_cur = _M_ht->_M_buckets[__bucket]; |
687 | } |
688 | return *this; |
689 | } |
690 | |
691 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, |
692 | class _All> |
693 | inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> |
694 | _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: |
695 | operator++(int) |
696 | { |
697 | const_iterator __tmp = *this; |
698 | ++*this; |
699 | return __tmp; |
700 | } |
701 | |
702 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
703 | bool |
704 | operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, |
705 | const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) |
706 | { |
707 | typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; |
708 | |
709 | if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) |
710 | return false; |
711 | |
712 | for (std::size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) |
713 | { |
714 | _Node* __cur1 = __ht1._M_buckets[__n]; |
715 | _Node* __cur2 = __ht2._M_buckets[__n]; |
716 | // Check same length of lists |
717 | for (; __cur1 && __cur2; |
718 | __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) |
719 | { } |
720 | if (__cur1 || __cur2) |
721 | return false; |
722 | // Now check one's elements are in the other |
723 | for (__cur1 = __ht1._M_buckets[__n] ; __cur1; |
724 | __cur1 = __cur1->_M_next) |
725 | { |
726 | bool _found__cur1 = false; |
727 | for (__cur2 = __ht2._M_buckets[__n]; |
728 | __cur2; __cur2 = __cur2->_M_next) |
729 | { |
730 | if (__cur1->_M_val == __cur2->_M_val) |
731 | { |
732 | _found__cur1 = true; |
733 | break; |
734 | } |
735 | } |
736 | if (!_found__cur1) |
737 | return false; |
738 | } |
739 | } |
740 | return true; |
741 | } |
742 | |
743 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
744 | inline bool |
745 | operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, |
746 | const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) |
747 | { return !(__ht1 == __ht2); } |
748 | |
749 | template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, |
750 | class _All> |
751 | inline void |
752 | swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, |
753 | hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) |
754 | { __ht1.swap(__ht2); } |
755 | |
756 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
757 | std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, |
758 | bool> |
759 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
760 | insert_unique_noresize(const value_type& __obj) |
761 | { |
762 | const size_type __n = _M_bkt_num(__obj); |
763 | _Node* __first = _M_buckets[__n]; |
764 | |
765 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
766 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) |
767 | return std::pair<iterator, bool>(iterator(__cur, this), false); |
768 | |
769 | _Node* __tmp = _M_new_node(__obj); |
770 | __tmp->_M_next = __first; |
771 | _M_buckets[__n] = __tmp; |
772 | ++_M_num_elements; |
773 | return std::pair<iterator, bool>(iterator(__tmp, this), true); |
774 | } |
775 | |
776 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
777 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator |
778 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
779 | insert_equal_noresize(const value_type& __obj) |
780 | { |
781 | const size_type __n = _M_bkt_num(__obj); |
782 | _Node* __first = _M_buckets[__n]; |
783 | |
784 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
785 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) |
786 | { |
787 | _Node* __tmp = _M_new_node(__obj); |
788 | __tmp->_M_next = __cur->_M_next; |
789 | __cur->_M_next = __tmp; |
790 | ++_M_num_elements; |
791 | return iterator(__tmp, this); |
792 | } |
793 | |
794 | _Node* __tmp = _M_new_node(__obj); |
795 | __tmp->_M_next = __first; |
796 | _M_buckets[__n] = __tmp; |
797 | ++_M_num_elements; |
798 | return iterator(__tmp, this); |
799 | } |
800 | |
801 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
802 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference |
803 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
804 | find_or_insert(const value_type& __obj) |
805 | { |
806 | resize(num_elements_hint: _M_num_elements + 1); |
807 | |
808 | size_type __n = _M_bkt_num(__obj); |
809 | _Node* __first = _M_buckets[__n]; |
810 | |
811 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) |
812 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) |
813 | return __cur->_M_val; |
814 | |
815 | _Node* __tmp = _M_new_node(__obj); |
816 | __tmp->_M_next = __first; |
817 | _M_buckets[__n] = __tmp; |
818 | ++_M_num_elements; |
819 | return __tmp->_M_val; |
820 | } |
821 | |
822 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
823 | std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, |
824 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> |
825 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
826 | equal_range(const key_type& __key) |
827 | { |
828 | typedef std::pair<iterator, iterator> _Pii; |
829 | const size_type __n = _M_bkt_num_key(__key); |
830 | |
831 | for (_Node* __first = _M_buckets[__n]; __first; |
832 | __first = __first->_M_next) |
833 | if (_M_equals(_M_get_key(__first->_M_val), __key)) |
834 | { |
835 | for (_Node* __cur = __first->_M_next; __cur; |
836 | __cur = __cur->_M_next) |
837 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) |
838 | return _Pii(iterator(__first, this), iterator(__cur, this)); |
839 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) |
840 | if (_M_buckets[__m]) |
841 | return _Pii(iterator(__first, this), |
842 | iterator(_M_buckets[__m], this)); |
843 | return _Pii(iterator(__first, this), end()); |
844 | } |
845 | return _Pii(end(), end()); |
846 | } |
847 | |
848 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
849 | std::pair< |
850 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, |
851 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> |
852 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
853 | equal_range(const key_type& __key) const |
854 | { |
855 | typedef std::pair<const_iterator, const_iterator> _Pii; |
856 | const size_type __n = _M_bkt_num_key(__key); |
857 | |
858 | for (const _Node* __first = _M_buckets[__n]; __first; |
859 | __first = __first->_M_next) |
860 | { |
861 | if (_M_equals(_M_get_key(__first->_M_val), __key)) |
862 | { |
863 | for (const _Node* __cur = __first->_M_next; __cur; |
864 | __cur = __cur->_M_next) |
865 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) |
866 | return _Pii(const_iterator(__first, this), |
867 | const_iterator(__cur, this)); |
868 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) |
869 | if (_M_buckets[__m]) |
870 | return _Pii(const_iterator(__first, this), |
871 | const_iterator(_M_buckets[__m], this)); |
872 | return _Pii(const_iterator(__first, this), end()); |
873 | } |
874 | } |
875 | return _Pii(end(), end()); |
876 | } |
877 | |
878 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
879 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type |
880 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
881 | erase(const key_type& __key) |
882 | { |
883 | const size_type __n = _M_bkt_num_key(__key); |
884 | _Node* __first = _M_buckets[__n]; |
885 | _Node* __saved_slot = 0; |
886 | size_type __erased = 0; |
887 | |
888 | if (__first) |
889 | { |
890 | _Node* __cur = __first; |
891 | _Node* __next = __cur->_M_next; |
892 | while (__next) |
893 | { |
894 | if (_M_equals(_M_get_key(__next->_M_val), __key)) |
895 | { |
896 | if (&_M_get_key(__next->_M_val) != &__key) |
897 | { |
898 | __cur->_M_next = __next->_M_next; |
899 | _M_delete_node(n: __next); |
900 | __next = __cur->_M_next; |
901 | ++__erased; |
902 | --_M_num_elements; |
903 | } |
904 | else |
905 | { |
906 | __saved_slot = __cur; |
907 | __cur = __next; |
908 | __next = __cur->_M_next; |
909 | } |
910 | } |
911 | else |
912 | { |
913 | __cur = __next; |
914 | __next = __cur->_M_next; |
915 | } |
916 | } |
917 | bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key); |
918 | if (__saved_slot) |
919 | { |
920 | __next = __saved_slot->_M_next; |
921 | __saved_slot->_M_next = __next->_M_next; |
922 | _M_delete_node(n: __next); |
923 | ++__erased; |
924 | --_M_num_elements; |
925 | } |
926 | if (__delete_first) |
927 | { |
928 | _M_buckets[__n] = __first->_M_next; |
929 | _M_delete_node(n: __first); |
930 | ++__erased; |
931 | --_M_num_elements; |
932 | } |
933 | } |
934 | return __erased; |
935 | } |
936 | |
937 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
938 | void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
939 | erase(const iterator& __it) |
940 | { |
941 | _Node* __p = __it._M_cur; |
942 | if (__p) |
943 | { |
944 | const size_type __n = _M_bkt_num(__p->_M_val); |
945 | _Node* __cur = _M_buckets[__n]; |
946 | |
947 | if (__cur == __p) |
948 | { |
949 | _M_buckets[__n] = __cur->_M_next; |
950 | _M_delete_node(n: __cur); |
951 | --_M_num_elements; |
952 | } |
953 | else |
954 | { |
955 | _Node* __next = __cur->_M_next; |
956 | while (__next) |
957 | { |
958 | if (__next == __p) |
959 | { |
960 | __cur->_M_next = __next->_M_next; |
961 | _M_delete_node(n: __next); |
962 | --_M_num_elements; |
963 | break; |
964 | } |
965 | else |
966 | { |
967 | __cur = __next; |
968 | __next = __cur->_M_next; |
969 | } |
970 | } |
971 | } |
972 | } |
973 | } |
974 | |
975 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
976 | void |
977 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
978 | erase(iterator __first, iterator __last) |
979 | { |
980 | size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) |
981 | : _M_buckets.size(); |
982 | |
983 | size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) |
984 | : _M_buckets.size(); |
985 | |
986 | if (__first._M_cur == __last._M_cur) |
987 | return; |
988 | else if (__f_bucket == __l_bucket) |
989 | _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); |
990 | else |
991 | { |
992 | _M_erase_bucket(__f_bucket, __first._M_cur, 0); |
993 | for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) |
994 | _M_erase_bucket(__n, 0); |
995 | if (__l_bucket != _M_buckets.size()) |
996 | _M_erase_bucket(__l_bucket, __last._M_cur); |
997 | } |
998 | } |
999 | |
1000 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
1001 | inline void |
1002 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
1003 | erase(const_iterator __first, const_iterator __last) |
1004 | { |
1005 | erase(iterator(const_cast<_Node*>(__first._M_cur), |
1006 | const_cast<hashtable*>(__first._M_ht)), |
1007 | iterator(const_cast<_Node*>(__last._M_cur), |
1008 | const_cast<hashtable*>(__last._M_ht))); |
1009 | } |
1010 | |
1011 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
1012 | inline void |
1013 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
1014 | erase(const const_iterator& __it) |
1015 | { erase(iterator(const_cast<_Node*>(__it._M_cur), |
1016 | const_cast<hashtable*>(__it._M_ht))); } |
1017 | |
1018 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
1019 | void |
1020 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
1021 | resize(size_type __num_elements_hint) |
1022 | { |
1023 | const size_type __old_n = _M_buckets.size(); |
1024 | if (__num_elements_hint > __old_n) |
1025 | { |
1026 | const size_type __n = _M_next_size(n: __num_elements_hint); |
1027 | if (__n > __old_n) |
1028 | { |
1029 | _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator()); |
1030 | __try |
1031 | { |
1032 | for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) |
1033 | { |
1034 | _Node* __first = _M_buckets[__bucket]; |
1035 | while (__first) |
1036 | { |
1037 | size_type __new_bucket = _M_bkt_num(__first->_M_val, |
1038 | __n); |
1039 | _M_buckets[__bucket] = __first->_M_next; |
1040 | __first->_M_next = __tmp[__new_bucket]; |
1041 | __tmp[__new_bucket] = __first; |
1042 | __first = _M_buckets[__bucket]; |
1043 | } |
1044 | } |
1045 | _M_buckets.swap(__tmp); |
1046 | } |
1047 | __catch(...) |
1048 | { |
1049 | for (size_type __bucket = 0; __bucket < __tmp.size(); |
1050 | ++__bucket) |
1051 | { |
1052 | while (__tmp[__bucket]) |
1053 | { |
1054 | _Node* __next = __tmp[__bucket]->_M_next; |
1055 | _M_delete_node(n: __tmp[__bucket]); |
1056 | __tmp[__bucket] = __next; |
1057 | } |
1058 | } |
1059 | __throw_exception_again; |
1060 | } |
1061 | } |
1062 | } |
1063 | } |
1064 | |
1065 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
1066 | void |
1067 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
1068 | _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) |
1069 | { |
1070 | _Node* __cur = _M_buckets[__n]; |
1071 | if (__cur == __first) |
1072 | _M_erase_bucket(__n, __last); |
1073 | else |
1074 | { |
1075 | _Node* __next; |
1076 | for (__next = __cur->_M_next; |
1077 | __next != __first; |
1078 | __cur = __next, __next = __cur->_M_next) |
1079 | ; |
1080 | while (__next != __last) |
1081 | { |
1082 | __cur->_M_next = __next->_M_next; |
1083 | _M_delete_node(n: __next); |
1084 | __next = __cur->_M_next; |
1085 | --_M_num_elements; |
1086 | } |
1087 | } |
1088 | } |
1089 | |
1090 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
1091 | void |
1092 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
1093 | _M_erase_bucket(const size_type __n, _Node* __last) |
1094 | { |
1095 | _Node* __cur = _M_buckets[__n]; |
1096 | while (__cur != __last) |
1097 | { |
1098 | _Node* __next = __cur->_M_next; |
1099 | _M_delete_node(n: __cur); |
1100 | __cur = __next; |
1101 | _M_buckets[__n] = __cur; |
1102 | --_M_num_elements; |
1103 | } |
1104 | } |
1105 | |
1106 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
1107 | void |
1108 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
1109 | clear() |
1110 | { |
1111 | if (_M_num_elements == 0) |
1112 | return; |
1113 | |
1114 | for (size_type __i = 0; __i < _M_buckets.size(); ++__i) |
1115 | { |
1116 | _Node* __cur = _M_buckets[__i]; |
1117 | while (__cur != 0) |
1118 | { |
1119 | _Node* __next = __cur->_M_next; |
1120 | _M_delete_node(n: __cur); |
1121 | __cur = __next; |
1122 | } |
1123 | _M_buckets[__i] = 0; |
1124 | } |
1125 | _M_num_elements = 0; |
1126 | } |
1127 | |
1128 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
1129 | void |
1130 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: |
1131 | _M_copy_from(const hashtable& __ht) |
1132 | { |
1133 | _M_buckets.clear(); |
1134 | _M_buckets.reserve(__ht._M_buckets.size()); |
1135 | _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); |
1136 | __try |
1137 | { |
1138 | for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { |
1139 | const _Node* __cur = __ht._M_buckets[__i]; |
1140 | if (__cur) |
1141 | { |
1142 | _Node* __local_copy = _M_new_node(obj: __cur->_M_val); |
1143 | _M_buckets[__i] = __local_copy; |
1144 | |
1145 | for (_Node* __next = __cur->_M_next; |
1146 | __next; |
1147 | __cur = __next, __next = __cur->_M_next) |
1148 | { |
1149 | __local_copy->_M_next = _M_new_node(obj: __next->_M_val); |
1150 | __local_copy = __local_copy->_M_next; |
1151 | } |
1152 | } |
1153 | } |
1154 | _M_num_elements = __ht._M_num_elements; |
1155 | } |
1156 | __catch(...) |
1157 | { |
1158 | clear(); |
1159 | __throw_exception_again; |
1160 | } |
1161 | } |
1162 | |
1163 | _GLIBCXX_END_NAMESPACE_VERSION |
1164 | } // namespace |
1165 | |
1166 | #endif |
1167 | |