1 // Hashtable implementation used by containers -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
27 * Copyright (c) 1996,1997
28 * Silicon Graphics Computer Systems, Inc.
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
40 * Hewlett-Packard Company
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Hewlett-Packard Company makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
52 /** @file backward/hashtable.h
53 * This file is a GNU extension to the Standard C++ Library (possibly
54 * containing extensions from the HP/SGI STL subset).
57 #ifndef _BACKWARD_HASHTABLE_H
58 #define _BACKWARD_HASHTABLE_H 1
60 // Hashtable class, used to implement the hashed associative containers
61 // hash_set, hash_map, hash_multiset, and hash_multimap.
66 #include <bits/stl_function.h>
67 #include <backward/hash_fun.h>
69 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
73 using std::forward_iterator_tag;
74 using std::input_iterator_tag;
75 using std::_Construct;
80 using std::__iterator_category;
83 struct _Hashtable_node
85 _Hashtable_node* _M_next;
89 template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
90 class _EqualKey, class _Alloc = std::allocator<_Val> >
93 template<class _Val, class _Key, class _HashFcn,
94 class _ExtractKey, class _EqualKey, class _Alloc>
95 struct _Hashtable_iterator;
97 template<class _Val, class _Key, class _HashFcn,
98 class _ExtractKey, class _EqualKey, class _Alloc>
99 struct _Hashtable_const_iterator;
101 template<class _Val, class _Key, class _HashFcn,
102 class _ExtractKey, class _EqualKey, class _Alloc>
103 struct _Hashtable_iterator
105 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
107 typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
108 _ExtractKey, _EqualKey, _Alloc>
110 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
111 _ExtractKey, _EqualKey, _Alloc>
113 typedef _Hashtable_node<_Val> _Node;
114 typedef forward_iterator_tag iterator_category;
115 typedef _Val value_type;
116 typedef ptrdiff_t difference_type;
117 typedef size_t size_type;
118 typedef _Val& reference;
119 typedef _Val* pointer;
124 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
125 : _M_cur(__n), _M_ht(__tab) { }
127 _Hashtable_iterator() { }
131 { return _M_cur->_M_val; }
135 { return &(operator*()); }
144 operator==(const iterator& __it) const
145 { return _M_cur == __it._M_cur; }
148 operator!=(const iterator& __it) const
149 { return _M_cur != __it._M_cur; }
152 template<class _Val, class _Key, class _HashFcn,
153 class _ExtractKey, class _EqualKey, class _Alloc>
154 struct _Hashtable_const_iterator
156 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
158 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
159 _ExtractKey,_EqualKey,_Alloc>
161 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
162 _ExtractKey, _EqualKey, _Alloc>
164 typedef _Hashtable_node<_Val> _Node;
166 typedef forward_iterator_tag iterator_category;
167 typedef _Val value_type;
168 typedef ptrdiff_t difference_type;
169 typedef size_t size_type;
170 typedef const _Val& reference;
171 typedef const _Val* pointer;
174 const _Hashtable* _M_ht;
176 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
177 : _M_cur(__n), _M_ht(__tab) { }
179 _Hashtable_const_iterator() { }
181 _Hashtable_const_iterator(const iterator& __it)
182 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
186 { return _M_cur->_M_val; }
190 { return &(operator*()); }
199 operator==(const const_iterator& __it) const
200 { return _M_cur == __it._M_cur; }
203 operator!=(const const_iterator& __it) const
204 { return _M_cur != __it._M_cur; }
207 // Note: assumes long is at least 32 bits.
208 enum { _S_num_primes = 28 };
210 static const unsigned long __stl_prime_list[_S_num_primes] =
212 53ul, 97ul, 193ul, 389ul, 769ul,
213 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
214 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
215 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
216 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
217 1610612741ul, 3221225473ul, 4294967291ul
221 __stl_next_prime(unsigned long __n)
223 const unsigned long* __first = __stl_prime_list;
224 const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
225 const unsigned long* pos = std::lower_bound(__first, __last, __n);
226 return pos == __last ? *(__last - 1) : *pos;
229 // Forward declaration of operator==.
230 template<class _Val, class _Key, class _HF, class _Ex,
231 class _Eq, class _All>
234 template<class _Val, class _Key, class _HF, class _Ex,
235 class _Eq, class _All>
237 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
238 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
240 // Hashtables handle allocators a bit differently than other
241 // containers do. If we're using standard-conforming allocators, then
242 // a hashtable unconditionally has a member variable to hold its
243 // allocator, even if it so happens that all instances of the
244 // allocator type are identical. This is because, for hashtables,
245 // this extra storage is negligible. Additionally, a base class
246 // wouldn't serve any other purposes; it wouldn't, for example,
247 // simplify the exception-handling code.
248 template<class _Val, class _Key, class _HashFcn,
249 class _ExtractKey, class _EqualKey, class _Alloc>
253 typedef _Key key_type;
254 typedef _Val value_type;
255 typedef _HashFcn hasher;
256 typedef _EqualKey key_equal;
258 typedef size_t size_type;
259 typedef ptrdiff_t difference_type;
260 typedef value_type* pointer;
261 typedef const value_type* const_pointer;
262 typedef value_type& reference;
263 typedef const value_type& const_reference;
271 { return _M_equals; }
274 typedef _Hashtable_node<_Val> _Node;
277 typedef typename _Alloc::template rebind<value_type>::other allocator_type;
279 get_allocator() const
280 { return _M_node_allocator; }
283 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
284 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
285 typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type;
287 _Node_Alloc _M_node_allocator;
291 { return _M_node_allocator.allocate(1); }
294 _M_put_node(_Node* __p)
295 { _M_node_allocator.deallocate(__p, 1); }
300 _ExtractKey _M_get_key;
301 _Vector_type _M_buckets;
302 size_type _M_num_elements;
305 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
308 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
313 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
316 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
320 hashtable(size_type __n, const _HashFcn& __hf,
321 const _EqualKey& __eql, const _ExtractKey& __ext,
322 const allocator_type& __a = allocator_type())
323 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
324 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
325 { _M_initialize_buckets(__n); }
327 hashtable(size_type __n, const _HashFcn& __hf,
328 const _EqualKey& __eql,
329 const allocator_type& __a = allocator_type())
330 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
331 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
332 { _M_initialize_buckets(__n); }
334 hashtable(const hashtable& __ht)
335 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
336 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
337 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
338 { _M_copy_from(__ht); }
341 operator= (const hashtable& __ht)
346 _M_hash = __ht._M_hash;
347 _M_equals = __ht._M_equals;
348 _M_get_key = __ht._M_get_key;
359 { return _M_num_elements; }
363 { return size_type(-1); }
367 { return size() == 0; }
370 swap(hashtable& __ht)
372 std::swap(_M_hash, __ht._M_hash);
373 std::swap(_M_equals, __ht._M_equals);
374 std::swap(_M_get_key, __ht._M_get_key);
375 _M_buckets.swap(__ht._M_buckets);
376 std::swap(_M_num_elements, __ht._M_num_elements);
382 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
384 return iterator(_M_buckets[__n], this);
390 { return iterator(0, this); }
395 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
397 return const_iterator(_M_buckets[__n], this);
403 { return const_iterator(0, this); }
405 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq,
408 operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
409 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
414 { return _M_buckets.size(); }
417 max_bucket_count() const
418 { return __stl_prime_list[(int)_S_num_primes - 1]; }
421 elems_in_bucket(size_type __bucket) const
423 size_type __result = 0;
424 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
430 insert_unique(const value_type& __obj)
432 resize(_M_num_elements + 1);
433 return insert_unique_noresize(__obj);
437 insert_equal(const value_type& __obj)
439 resize(_M_num_elements + 1);
440 return insert_equal_noresize(__obj);
444 insert_unique_noresize(const value_type& __obj);
447 insert_equal_noresize(const value_type& __obj);
449 template<class _InputIterator>
451 insert_unique(_InputIterator __f, _InputIterator __l)
452 { insert_unique(__f, __l, __iterator_category(__f)); }
454 template<class _InputIterator>
456 insert_equal(_InputIterator __f, _InputIterator __l)
457 { insert_equal(__f, __l, __iterator_category(__f)); }
459 template<class _InputIterator>
461 insert_unique(_InputIterator __f, _InputIterator __l,
464 for ( ; __f != __l; ++__f)
468 template<class _InputIterator>
470 insert_equal(_InputIterator __f, _InputIterator __l,
473 for ( ; __f != __l; ++__f)
477 template<class _ForwardIterator>
479 insert_unique(_ForwardIterator __f, _ForwardIterator __l,
480 forward_iterator_tag)
482 size_type __n = distance(__f, __l);
483 resize(_M_num_elements + __n);
484 for ( ; __n > 0; --__n, ++__f)
485 insert_unique_noresize(*__f);
488 template<class _ForwardIterator>
490 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
491 forward_iterator_tag)
493 size_type __n = distance(__f, __l);
494 resize(_M_num_elements + __n);
495 for ( ; __n > 0; --__n, ++__f)
496 insert_equal_noresize(*__f);
500 find_or_insert(const value_type& __obj);
503 find(const key_type& __key)
505 size_type __n = _M_bkt_num_key(__key);
507 for (__first = _M_buckets[__n];
508 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
509 __first = __first->_M_next)
511 return iterator(__first, this);
515 find(const key_type& __key) const
517 size_type __n = _M_bkt_num_key(__key);
518 const _Node* __first;
519 for (__first = _M_buckets[__n];
520 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
521 __first = __first->_M_next)
523 return const_iterator(__first, this);
527 count(const key_type& __key) const
529 const size_type __n = _M_bkt_num_key(__key);
530 size_type __result = 0;
532 for (const _Node* __cur = _M_buckets[__n]; __cur;
533 __cur = __cur->_M_next)
534 if (_M_equals(_M_get_key(__cur->_M_val), __key))
539 pair<iterator, iterator>
540 equal_range(const key_type& __key);
542 pair<const_iterator, const_iterator>
543 equal_range(const key_type& __key) const;
546 erase(const key_type& __key);
549 erase(const iterator& __it);
552 erase(iterator __first, iterator __last);
555 erase(const const_iterator& __it);
558 erase(const_iterator __first, const_iterator __last);
561 resize(size_type __num_elements_hint);
568 _M_next_size(size_type __n) const
569 { return __stl_next_prime(__n); }
572 _M_initialize_buckets(size_type __n)
574 const size_type __n_buckets = _M_next_size(__n);
575 _M_buckets.reserve(__n_buckets);
576 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
581 _M_bkt_num_key(const key_type& __key) const
582 { return _M_bkt_num_key(__key, _M_buckets.size()); }
585 _M_bkt_num(const value_type& __obj) const
586 { return _M_bkt_num_key(_M_get_key(__obj)); }
589 _M_bkt_num_key(const key_type& __key, size_t __n) const
590 { return _M_hash(__key) % __n; }
593 _M_bkt_num(const value_type& __obj, size_t __n) const
594 { return _M_bkt_num_key(_M_get_key(__obj), __n); }
597 _M_new_node(const value_type& __obj)
599 _Node* __n = _M_get_node();
603 this->get_allocator().construct(&__n->_M_val, __obj);
609 __throw_exception_again;
614 _M_delete_node(_Node* __n)
616 this->get_allocator().destroy(&__n->_M_val);
621 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
624 _M_erase_bucket(const size_type __n, _Node* __last);
627 _M_copy_from(const hashtable& __ht);
630 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
632 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
633 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
636 const _Node* __old = _M_cur;
637 _M_cur = _M_cur->_M_next;
640 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
641 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
642 _M_cur = _M_ht->_M_buckets[__bucket];
647 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
649 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
650 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
653 iterator __tmp = *this;
658 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
660 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
661 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
664 const _Node* __old = _M_cur;
665 _M_cur = _M_cur->_M_next;
668 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
669 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
670 _M_cur = _M_ht->_M_buckets[__bucket];
675 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
677 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
678 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
681 const_iterator __tmp = *this;
686 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
688 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
689 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
691 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
693 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
696 for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
698 _Node* __cur1 = __ht1._M_buckets[__n];
699 _Node* __cur2 = __ht2._M_buckets[__n];
700 // Check same length of lists
701 for (; __cur1 && __cur2;
702 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
704 if (__cur1 || __cur2)
706 // Now check one's elements are in the other
707 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
708 __cur1 = __cur1->_M_next)
710 bool _found__cur1 = false;
711 for (__cur2 = __ht2._M_buckets[__n];
712 __cur2; __cur2 = __cur2->_M_next)
714 if (__cur1->_M_val == __cur2->_M_val)
727 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
729 operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
730 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
731 { return !(__ht1 == __ht2); }
733 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey,
736 swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
737 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
738 { __ht1.swap(__ht2); }
740 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
741 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
742 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
743 insert_unique_noresize(const value_type& __obj)
745 const size_type __n = _M_bkt_num(__obj);
746 _Node* __first = _M_buckets[__n];
748 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
749 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
750 return pair<iterator, bool>(iterator(__cur, this), false);
752 _Node* __tmp = _M_new_node(__obj);
753 __tmp->_M_next = __first;
754 _M_buckets[__n] = __tmp;
756 return pair<iterator, bool>(iterator(__tmp, this), true);
759 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
760 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
761 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
762 insert_equal_noresize(const value_type& __obj)
764 const size_type __n = _M_bkt_num(__obj);
765 _Node* __first = _M_buckets[__n];
767 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
768 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
770 _Node* __tmp = _M_new_node(__obj);
771 __tmp->_M_next = __cur->_M_next;
772 __cur->_M_next = __tmp;
774 return iterator(__tmp, this);
777 _Node* __tmp = _M_new_node(__obj);
778 __tmp->_M_next = __first;
779 _M_buckets[__n] = __tmp;
781 return iterator(__tmp, this);
784 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
785 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
786 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
787 find_or_insert(const value_type& __obj)
789 resize(_M_num_elements + 1);
791 size_type __n = _M_bkt_num(__obj);
792 _Node* __first = _M_buckets[__n];
794 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
795 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
796 return __cur->_M_val;
798 _Node* __tmp = _M_new_node(__obj);
799 __tmp->_M_next = __first;
800 _M_buckets[__n] = __tmp;
802 return __tmp->_M_val;
805 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
806 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
807 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
808 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
809 equal_range(const key_type& __key)
811 typedef pair<iterator, iterator> _Pii;
812 const size_type __n = _M_bkt_num_key(__key);
814 for (_Node* __first = _M_buckets[__n]; __first;
815 __first = __first->_M_next)
816 if (_M_equals(_M_get_key(__first->_M_val), __key))
818 for (_Node* __cur = __first->_M_next; __cur;
819 __cur = __cur->_M_next)
820 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
821 return _Pii(iterator(__first, this), iterator(__cur, this));
822 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
824 return _Pii(iterator(__first, this),
825 iterator(_M_buckets[__m], this));
826 return _Pii(iterator(__first, this), end());
828 return _Pii(end(), end());
831 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
832 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
833 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
834 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
835 equal_range(const key_type& __key) const
837 typedef pair<const_iterator, const_iterator> _Pii;
838 const size_type __n = _M_bkt_num_key(__key);
840 for (const _Node* __first = _M_buckets[__n]; __first;
841 __first = __first->_M_next)
843 if (_M_equals(_M_get_key(__first->_M_val), __key))
845 for (const _Node* __cur = __first->_M_next; __cur;
846 __cur = __cur->_M_next)
847 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
848 return _Pii(const_iterator(__first, this),
849 const_iterator(__cur, this));
850 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
852 return _Pii(const_iterator(__first, this),
853 const_iterator(_M_buckets[__m], this));
854 return _Pii(const_iterator(__first, this), end());
857 return _Pii(end(), end());
860 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
861 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
862 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
863 erase(const key_type& __key)
865 const size_type __n = _M_bkt_num_key(__key);
866 _Node* __first = _M_buckets[__n];
867 size_type __erased = 0;
871 _Node* __cur = __first;
872 _Node* __next = __cur->_M_next;
875 if (_M_equals(_M_get_key(__next->_M_val), __key))
877 __cur->_M_next = __next->_M_next;
878 _M_delete_node(__next);
879 __next = __cur->_M_next;
886 __next = __cur->_M_next;
889 if (_M_equals(_M_get_key(__first->_M_val), __key))
891 _M_buckets[__n] = __first->_M_next;
892 _M_delete_node(__first);
900 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
901 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
902 erase(const iterator& __it)
904 _Node* __p = __it._M_cur;
907 const size_type __n = _M_bkt_num(__p->_M_val);
908 _Node* __cur = _M_buckets[__n];
912 _M_buckets[__n] = __cur->_M_next;
913 _M_delete_node(__cur);
918 _Node* __next = __cur->_M_next;
923 __cur->_M_next = __next->_M_next;
924 _M_delete_node(__next);
931 __next = __cur->_M_next;
938 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
940 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
941 erase(iterator __first, iterator __last)
943 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
946 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
949 if (__first._M_cur == __last._M_cur)
951 else if (__f_bucket == __l_bucket)
952 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
955 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
956 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
957 _M_erase_bucket(__n, 0);
958 if (__l_bucket != _M_buckets.size())
959 _M_erase_bucket(__l_bucket, __last._M_cur);
963 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
965 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
966 erase(const_iterator __first, const_iterator __last)
968 erase(iterator(const_cast<_Node*>(__first._M_cur),
969 const_cast<hashtable*>(__first._M_ht)),
970 iterator(const_cast<_Node*>(__last._M_cur),
971 const_cast<hashtable*>(__last._M_ht)));
974 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
976 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
977 erase(const const_iterator& __it)
978 { erase(iterator(const_cast<_Node*>(__it._M_cur),
979 const_cast<hashtable*>(__it._M_ht))); }
981 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
983 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
984 resize(size_type __num_elements_hint)
986 const size_type __old_n = _M_buckets.size();
987 if (__num_elements_hint > __old_n)
989 const size_type __n = _M_next_size(__num_elements_hint);
992 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
995 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
997 _Node* __first = _M_buckets[__bucket];
1000 size_type __new_bucket = _M_bkt_num(__first->_M_val,
1002 _M_buckets[__bucket] = __first->_M_next;
1003 __first->_M_next = __tmp[__new_bucket];
1004 __tmp[__new_bucket] = __first;
1005 __first = _M_buckets[__bucket];
1008 _M_buckets.swap(__tmp);
1012 for (size_type __bucket = 0; __bucket < __tmp.size();
1015 while (__tmp[__bucket])
1017 _Node* __next = __tmp[__bucket]->_M_next;
1018 _M_delete_node(__tmp[__bucket]);
1019 __tmp[__bucket] = __next;
1022 __throw_exception_again;
1028 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1030 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1031 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1033 _Node* __cur = _M_buckets[__n];
1034 if (__cur == __first)
1035 _M_erase_bucket(__n, __last);
1039 for (__next = __cur->_M_next;
1041 __cur = __next, __next = __cur->_M_next)
1043 while (__next != __last)
1045 __cur->_M_next = __next->_M_next;
1046 _M_delete_node(__next);
1047 __next = __cur->_M_next;
1053 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1055 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1056 _M_erase_bucket(const size_type __n, _Node* __last)
1058 _Node* __cur = _M_buckets[__n];
1059 while (__cur != __last)
1061 _Node* __next = __cur->_M_next;
1062 _M_delete_node(__cur);
1064 _M_buckets[__n] = __cur;
1069 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1071 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1074 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1076 _Node* __cur = _M_buckets[__i];
1079 _Node* __next = __cur->_M_next;
1080 _M_delete_node(__cur);
1083 _M_buckets[__i] = 0;
1085 _M_num_elements = 0;
1088 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1090 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1091 _M_copy_from(const hashtable& __ht)
1094 _M_buckets.reserve(__ht._M_buckets.size());
1095 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1098 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1099 const _Node* __cur = __ht._M_buckets[__i];
1102 _Node* __local_copy = _M_new_node(__cur->_M_val);
1103 _M_buckets[__i] = __local_copy;
1105 for (_Node* __next = __cur->_M_next;
1107 __cur = __next, __next = __cur->_M_next)
1109 __local_copy->_M_next = _M_new_node(__next->_M_val);
1110 __local_copy = __local_copy->_M_next;
1114 _M_num_elements = __ht._M_num_elements;
1119 __throw_exception_again;
1123 _GLIBCXX_END_NAMESPACE