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 = 29 };
210 static const unsigned long __stl_prime_list[_S_num_primes] =
212 5ul, 53ul, 97ul, 193ul, 389ul,
213 769ul, 1543ul, 3079ul, 6151ul, 12289ul,
214 24593ul, 49157ul, 98317ul, 196613ul, 393241ul,
215 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul,
216 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul,
217 805306457ul, 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 _Node* __saved_slot = 0;
868 size_type __erased = 0;
872 _Node* __cur = __first;
873 _Node* __next = __cur->_M_next;
876 if (_M_equals(_M_get_key(__next->_M_val), __key))
878 if (&_M_get_key(__next->_M_val) != &__key)
880 __cur->_M_next = __next->_M_next;
881 _M_delete_node(__next);
882 __next = __cur->_M_next;
888 __saved_slot = __cur;
890 __next = __cur->_M_next;
896 __next = __cur->_M_next;
899 if (_M_equals(_M_get_key(__first->_M_val), __key))
901 _M_buckets[__n] = __first->_M_next;
902 _M_delete_node(__first);
908 __next = __saved_slot->_M_next;
909 __saved_slot->_M_next = __next->_M_next;
910 _M_delete_node(__next);
918 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
919 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
920 erase(const iterator& __it)
922 _Node* __p = __it._M_cur;
925 const size_type __n = _M_bkt_num(__p->_M_val);
926 _Node* __cur = _M_buckets[__n];
930 _M_buckets[__n] = __cur->_M_next;
931 _M_delete_node(__cur);
936 _Node* __next = __cur->_M_next;
941 __cur->_M_next = __next->_M_next;
942 _M_delete_node(__next);
949 __next = __cur->_M_next;
956 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
958 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
959 erase(iterator __first, iterator __last)
961 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
964 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
967 if (__first._M_cur == __last._M_cur)
969 else if (__f_bucket == __l_bucket)
970 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
973 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
974 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
975 _M_erase_bucket(__n, 0);
976 if (__l_bucket != _M_buckets.size())
977 _M_erase_bucket(__l_bucket, __last._M_cur);
981 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
983 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
984 erase(const_iterator __first, const_iterator __last)
986 erase(iterator(const_cast<_Node*>(__first._M_cur),
987 const_cast<hashtable*>(__first._M_ht)),
988 iterator(const_cast<_Node*>(__last._M_cur),
989 const_cast<hashtable*>(__last._M_ht)));
992 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
994 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
995 erase(const const_iterator& __it)
996 { erase(iterator(const_cast<_Node*>(__it._M_cur),
997 const_cast<hashtable*>(__it._M_ht))); }
999 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1001 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1002 resize(size_type __num_elements_hint)
1004 const size_type __old_n = _M_buckets.size();
1005 if (__num_elements_hint > __old_n)
1007 const size_type __n = _M_next_size(__num_elements_hint);
1010 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
1013 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1015 _Node* __first = _M_buckets[__bucket];
1018 size_type __new_bucket = _M_bkt_num(__first->_M_val,
1020 _M_buckets[__bucket] = __first->_M_next;
1021 __first->_M_next = __tmp[__new_bucket];
1022 __tmp[__new_bucket] = __first;
1023 __first = _M_buckets[__bucket];
1026 _M_buckets.swap(__tmp);
1030 for (size_type __bucket = 0; __bucket < __tmp.size();
1033 while (__tmp[__bucket])
1035 _Node* __next = __tmp[__bucket]->_M_next;
1036 _M_delete_node(__tmp[__bucket]);
1037 __tmp[__bucket] = __next;
1040 __throw_exception_again;
1046 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1048 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1049 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1051 _Node* __cur = _M_buckets[__n];
1052 if (__cur == __first)
1053 _M_erase_bucket(__n, __last);
1057 for (__next = __cur->_M_next;
1059 __cur = __next, __next = __cur->_M_next)
1061 while (__next != __last)
1063 __cur->_M_next = __next->_M_next;
1064 _M_delete_node(__next);
1065 __next = __cur->_M_next;
1071 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1073 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1074 _M_erase_bucket(const size_type __n, _Node* __last)
1076 _Node* __cur = _M_buckets[__n];
1077 while (__cur != __last)
1079 _Node* __next = __cur->_M_next;
1080 _M_delete_node(__cur);
1082 _M_buckets[__n] = __cur;
1087 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1089 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1092 if (_M_num_elements == 0)
1095 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1097 _Node* __cur = _M_buckets[__i];
1100 _Node* __next = __cur->_M_next;
1101 _M_delete_node(__cur);
1104 _M_buckets[__i] = 0;
1106 _M_num_elements = 0;
1109 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1111 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1112 _M_copy_from(const hashtable& __ht)
1115 _M_buckets.reserve(__ht._M_buckets.size());
1116 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1119 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1120 const _Node* __cur = __ht._M_buckets[__i];
1123 _Node* __local_copy = _M_new_node(__cur->_M_val);
1124 _M_buckets[__i] = __local_copy;
1126 for (_Node* __next = __cur->_M_next;
1128 __cur = __next, __next = __cur->_M_next)
1130 __local_copy->_M_next = _M_new_node(__next->_M_val);
1131 __local_copy = __local_copy->_M_next;
1135 _M_num_elements = __ht._M_num_elements;
1140 __throw_exception_again;
1144 _GLIBCXX_END_NAMESPACE