1 // Hashtable implementation used by containers -*- C++ -*-
2
3 // Copyright (C) 2001-2020 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
_GLIBCXX_VISIBILITY(default)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 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
116 : _M_cur(__n), _M_ht(__tab) { }
117
118 _Hashtable_iterator() { }
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 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
168 : _M_cur(__n), _M_ht(__tab) { }
169
170 _Hashtable_const_iterator() { }
171
172 _Hashtable_const_iterator(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, __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 hashtable(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 hashtable(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 hashtable(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 ~hashtable()
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(_M_num_elements + 1);
447 return insert_unique_noresize(__obj);
448 }
449
450 iterator
451 insert_equal(const value_type& __obj)
452 {
453 resize(_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(_M_num_elements + __n);
498 for ( ; __n > 0; --__n, ++__f)
499 insert_unique_noresize(*__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(_M_num_elements + __n);
509 for ( ; __n > 0; --__n, ++__f)
510 insert_equal_noresize(*__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(__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(__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(_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(__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(__next);
923 ++__erased;
924 --_M_num_elements;
925 }
926 if (__delete_first)
927 {
928 _M_buckets[__n] = __first->_M_next;
929 _M_delete_node(__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(__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(__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(__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(__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(__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(__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(__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(__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(__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