1 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
2 // Free Software Foundation, Inc.
4 // This file is part of the GNU ISO C++ Library. This library is free
5 // software; you can redistribute it and/or modify it under the
6 // terms of the GNU General Public License as published by the
7 // Free Software Foundation; either version 3, or (at your option)
10 // This library is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
15 // Under Section 7 of GPL version 3, you are granted additional
16 // permissions described in the GCC Runtime Library Exception, version
17 // 3.1, as published by the Free Software Foundation.
19 // You should have received a copy of the GNU General Public License and
20 // a copy of the GCC Runtime Library Exception along with this program;
21 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
22 // <http://www.gnu.org/licenses/>.
25 * Copyright (c) 1996,1997
26 * Silicon Graphics Computer Systems, Inc.
28 * Permission to use, copy, modify, distribute and sell this software
29 * and its documentation for any purpose is hereby granted without fee,
30 * provided that the above copyright notice appear in all copies and
31 * that both that copyright notice and this permission notice appear
32 * in supporting documentation. Silicon Graphics makes no
33 * representations about the suitability of this software for any
34 * purpose. It is provided "as is" without express or implied warranty.
38 * Hewlett-Packard Company
40 * Permission to use, copy, modify, distribute and sell this software
41 * and its documentation for any purpose is hereby granted without fee,
42 * provided that the above copyright notice appear in all copies and
43 * that both that copyright notice and this permission notice appear
44 * in supporting documentation. Hewlett-Packard Company makes no
45 * representations about the suitability of this software for any
46 * purpose. It is provided "as is" without express or implied warranty.
49 #ifndef __INTERPKERNELHASHTABLE_HXX__
50 #define __INTERPKERNELHASHTABLE_HXX__
52 #include "InterpKernelStlExt.hxx"
53 #include "InterpKernelHashFun.hxx"
60 namespace INTERP_KERNEL
63 struct _Hashtable_node
65 _Hashtable_node* _M_next;
69 template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
70 class _EqualKey, class _Alloc = std::allocator<_Val> >
73 template<class _Val, class _Key, class _HashFcn,
74 class _ExtractKey, class _EqualKey, class _Alloc>
75 struct _Hashtable_iterator;
77 template<class _Val, class _Key, class _HashFcn,
78 class _ExtractKey, class _EqualKey, class _Alloc>
79 struct _Hashtable_const_iterator;
81 template<class _Val, class _Key, class _HashFcn,
82 class _ExtractKey, class _EqualKey, class _Alloc>
83 struct _Hashtable_iterator
85 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
87 typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
88 _ExtractKey, _EqualKey, _Alloc>
90 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
91 _ExtractKey, _EqualKey, _Alloc>
93 typedef _Hashtable_node<_Val> _Node;
94 typedef std::forward_iterator_tag iterator_category;
95 typedef _Val value_type;
96 typedef std::ptrdiff_t difference_type;
97 typedef std::size_t size_type;
98 typedef _Val& reference;
99 typedef _Val* pointer;
104 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
105 : _M_cur(__n), _M_ht(__tab) { }
107 _Hashtable_iterator() { }
111 { return _M_cur->_M_val; }
115 { return &(operator*()); }
124 operator==(const iterator& __it) const
125 { return _M_cur == __it._M_cur; }
128 operator!=(const iterator& __it) const
129 { return _M_cur != __it._M_cur; }
132 template<class _Val, class _Key, class _HashFcn,
133 class _ExtractKey, class _EqualKey, class _Alloc>
134 struct _Hashtable_const_iterator
136 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
138 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
139 _ExtractKey,_EqualKey,_Alloc>
141 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
142 _ExtractKey, _EqualKey, _Alloc>
144 typedef _Hashtable_node<_Val> _Node;
146 typedef std::forward_iterator_tag iterator_category;
147 typedef _Val value_type;
148 typedef std::ptrdiff_t difference_type;
149 typedef std::size_t size_type;
150 typedef const _Val& reference;
151 typedef const _Val* pointer;
154 const _Hashtable* _M_ht;
156 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
157 : _M_cur(__n), _M_ht(__tab) { }
159 _Hashtable_const_iterator() { }
161 _Hashtable_const_iterator(const iterator& __it)
162 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
164 reference operator*() const { return _M_cur->_M_val; }
166 pointer operator->() const { return &(operator*()); }
168 const_iterator& operator++();
170 const_iterator operator++(int);
172 bool operator==(const const_iterator& __it) const { return _M_cur == __it._M_cur; }
174 bool operator!=(const const_iterator& __it) const { return _M_cur != __it._M_cur; }
177 // Note: assumes long is at least 32 bits.
178 enum { _S_num_primes = 28 };
180 static const unsigned long __stl_prime_list[_S_num_primes] =
182 53ul, 97ul, 193ul, 389ul, 769ul,
183 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
184 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
185 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
186 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
187 1610612741ul, 3221225473ul, 4294967291ul
191 __stl_next_prime(unsigned long __n)
193 const unsigned long* __first = __stl_prime_list;
194 const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
195 const unsigned long* pos = std::lower_bound(__first, __last, __n);
196 return pos == __last ? *(__last - 1) : *pos;
199 // Forward declaration of operator==.
200 template<class _Val, class _Key, class _HF, class _Ex,
201 class _Eq, class _All>
204 template<class _Val, class _Key, class _HF, class _Ex,
205 class _Eq, class _All>
206 bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
207 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
209 // Hashtables handle allocators a bit differently than other
210 // containers do. If we're using standard-conforming allocators, then
211 // a hashtable unconditionally has a member variable to hold its
212 // allocator, even if it so happens that all instances of the
213 // allocator type are identical. This is because, for hashtables,
214 // this extra storage is negligible. Additionally, a base class
215 // wouldn't serve any other purposes; it wouldn't, for example,
216 // simplify the exception-handling code.
217 template<class _Val, class _Key, class _HashFcn,
218 class _ExtractKey, class _EqualKey, class _Alloc>
222 typedef _Key key_type;
223 typedef _Val value_type;
224 typedef _HashFcn hasher;
225 typedef _EqualKey key_equal;
227 typedef std::size_t size_type;
228 typedef std::ptrdiff_t difference_type;
229 typedef value_type* pointer;
230 typedef const value_type* const_pointer;
231 typedef value_type& reference;
232 typedef const value_type& const_reference;
234 hasher hash_funct() const { return _M_hash; }
236 key_equal key_eq() const { return _M_equals; }
239 typedef _Hashtable_node<_Val> _Node;
242 typedef typename _Alloc::template rebind<value_type>::other allocator_type;
243 allocator_type get_allocator() const { return _M_node_allocator; }
246 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
247 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
248 typedef std::vector<_Node*, _Nodeptr_Alloc> _Vector_type;
250 _Node_Alloc _M_node_allocator;
252 _Node *_M_get_node() { return _M_node_allocator.allocate(1); }
254 void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); }
259 _ExtractKey _M_get_key;
260 _Vector_type _M_buckets;
261 size_type _M_num_elements;
264 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
267 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
272 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
275 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
279 hashtable(size_type __n, const _HashFcn& __hf,
280 const _EqualKey& __eql, const _ExtractKey& __ext,
281 const allocator_type& __a = allocator_type())
282 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
283 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
284 { _M_initialize_buckets(__n); }
286 hashtable(size_type __n, const _HashFcn& __hf,
287 const _EqualKey& __eql,
288 const allocator_type& __a = allocator_type())
289 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
290 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
291 { _M_initialize_buckets(__n); }
293 hashtable(const hashtable& __ht)
294 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
295 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
296 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
297 { _M_copy_from(__ht); }
299 hashtable& operator= (const hashtable& __ht)
304 _M_hash = __ht._M_hash;
305 _M_equals = __ht._M_equals;
306 _M_get_key = __ht._M_get_key;
315 size_type size() const { return _M_num_elements; }
317 size_type max_size() const { return size_type(-1); }
319 bool empty() const { return size() == 0; }
321 void swap(hashtable& __ht)
323 std::swap(_M_hash, __ht._M_hash);
324 std::swap(_M_equals, __ht._M_equals);
325 std::swap(_M_get_key, __ht._M_get_key);
326 _M_buckets.swap(__ht._M_buckets);
327 std::swap(_M_num_elements, __ht._M_num_elements);
332 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
334 return iterator(_M_buckets[__n], this);
338 iterator end() { return iterator(0, this); }
340 const_iterator begin() const
342 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
344 return const_iterator(_M_buckets[__n], this);
348 const_iterator end() const { return const_iterator(0, this); }
350 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, class _Al>
351 friend bool operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
352 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
355 size_type bucket_count() const { return _M_buckets.size(); }
357 size_type max_bucket_count() const { return __stl_prime_list[(int)_S_num_primes - 1]; }
359 size_type elems_in_bucket(size_type __bucket) const
361 size_type __result = 0;
362 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
367 std::pair<iterator, bool> insert_unique(const value_type& __obj)
369 resize(_M_num_elements + 1);
370 return insert_unique_noresize(__obj);
373 iterator insert_equal(const value_type& __obj)
375 resize(_M_num_elements + 1);
376 return insert_equal_noresize(__obj);
379 std::pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
381 iterator insert_equal_noresize(const value_type& __obj);
383 template<class _InputIterator>
384 void insert_unique(_InputIterator __f, _InputIterator __l)
385 { insert_unique(__f, __l, __iterator_category(__f)); }
387 template<class _InputIterator>
388 void insert_equal(_InputIterator __f, _InputIterator __l)
389 { insert_equal(__f, __l, __iterator_category(__f)); }
391 template<class _InputIterator>
392 void insert_unique(_InputIterator __f, _InputIterator __l,
393 std::input_iterator_tag)
395 for ( ; __f != __l; ++__f)
399 template<class _InputIterator>
400 void insert_equal(_InputIterator __f, _InputIterator __l,
401 std::input_iterator_tag)
403 for ( ; __f != __l; ++__f)
407 template<class _ForwardIterator>
408 void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
409 std::forward_iterator_tag)
411 size_type __n = std::distance(__f, __l);
412 resize(_M_num_elements + __n);
413 for ( ; __n > 0; --__n, ++__f)
414 insert_unique_noresize(*__f);
417 template<class _ForwardIterator>
419 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
420 std::forward_iterator_tag)
422 size_type __n = std::distance(__f, __l);
423 resize(_M_num_elements + __n);
424 for ( ; __n > 0; --__n, ++__f)
425 insert_equal_noresize(*__f);
428 reference find_or_insert(const value_type& __obj);
430 iterator find(const key_type& __key)
432 size_type __n = _M_bkt_num_key(__key);
434 for (__first = _M_buckets[__n];
435 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
436 __first = __first->_M_next)
438 return iterator(__first, this);
441 const_iterator find(const key_type& __key) const
443 size_type __n = _M_bkt_num_key(__key);
444 const _Node* __first;
445 for (__first = _M_buckets[__n];
446 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
447 __first = __first->_M_next)
449 return const_iterator(__first, this);
452 size_type count(const key_type& __key) const
454 const size_type __n = _M_bkt_num_key(__key);
455 size_type __result = 0;
456 for (const _Node* __cur = _M_buckets[__n]; __cur;
457 __cur = __cur->_M_next)
458 if (_M_equals(_M_get_key(__cur->_M_val), __key))
463 std::pair<iterator, iterator> equal_range(const key_type& __key);
465 std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const;
467 size_type erase(const key_type& __key);
469 void erase(const iterator& __it);
471 void erase(iterator __first, iterator __last);
473 void erase(const const_iterator& __it);
475 void erase(const_iterator __first, const_iterator __last);
477 void resize(size_type __num_elements_hint);
482 size_type _M_next_size(size_type __n) const { return __stl_next_prime(__n); }
484 void _M_initialize_buckets(size_type __n)
486 const size_type __n_buckets = _M_next_size(__n);
487 _M_buckets.reserve(__n_buckets);
488 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
492 size_type _M_bkt_num_key(const key_type& __key) const
493 { return _M_bkt_num_key(__key, _M_buckets.size()); }
495 size_type _M_bkt_num(const value_type& __obj) const
496 { return _M_bkt_num_key(_M_get_key(__obj)); }
498 size_type _M_bkt_num_key(const key_type& __key, std::size_t __n) const
499 { return _M_hash(__key) % __n; }
501 size_type _M_bkt_num(const value_type& __obj, std::size_t __n) const
502 { return _M_bkt_num_key(_M_get_key(__obj), __n); }
504 _Node* _M_new_node(const value_type& __obj)
506 _Node* __n = _M_get_node();
510 this->get_allocator().construct(&__n->_M_val, __obj);
520 void _M_delete_node(_Node* __n)
522 this->get_allocator().destroy(&__n->_M_val);
526 void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
528 void _M_erase_bucket(const size_type __n, _Node* __last);
530 void _M_copy_from(const hashtable& __ht);
533 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
534 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
535 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
538 const _Node* __old = _M_cur;
539 _M_cur = _M_cur->_M_next;
542 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
543 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
544 _M_cur = _M_ht->_M_buckets[__bucket];
549 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
550 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
551 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
554 iterator __tmp = *this;
559 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
560 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
561 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
564 const _Node* __old = _M_cur;
565 _M_cur = _M_cur->_M_next;
568 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
569 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
570 _M_cur = _M_ht->_M_buckets[__bucket];
575 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
577 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
578 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
581 const_iterator __tmp = *this;
586 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
587 bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
588 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
590 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
592 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
595 for (std::size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
597 _Node* __cur1 = __ht1._M_buckets[__n];
598 _Node* __cur2 = __ht2._M_buckets[__n];
599 // Check same length of lists
600 for (; __cur1 && __cur2;
601 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
603 if (__cur1 || __cur2)
605 // Now check one's elements are in the other
606 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
607 __cur1 = __cur1->_M_next)
609 bool _found__cur1 = false;
610 for (__cur2 = __ht2._M_buckets[__n];
611 __cur2; __cur2 = __cur2->_M_next)
613 if (__cur1->_M_val == __cur2->_M_val)
626 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
627 inline bool operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
628 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
629 { return !(__ht1 == __ht2); }
631 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, class _All>
632 inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
633 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
634 { __ht1.swap(__ht2); }
636 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
637 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
638 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
639 insert_unique_noresize(const value_type& __obj)
641 const size_type __n = _M_bkt_num(__obj);
642 _Node* __first = _M_buckets[__n];
644 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
645 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
646 return std::pair<iterator, bool>(iterator(__cur, this), false);
648 _Node* __tmp = _M_new_node(__obj);
649 __tmp->_M_next = __first;
650 _M_buckets[__n] = __tmp;
652 return std::pair<iterator, bool>(iterator(__tmp, this), true);
655 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
656 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
657 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
658 insert_equal_noresize(const value_type& __obj)
660 const size_type __n = _M_bkt_num(__obj);
661 _Node* __first = _M_buckets[__n];
663 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
664 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
666 _Node* __tmp = _M_new_node(__obj);
667 __tmp->_M_next = __cur->_M_next;
668 __cur->_M_next = __tmp;
670 return iterator(__tmp, this);
673 _Node* __tmp = _M_new_node(__obj);
674 __tmp->_M_next = __first;
675 _M_buckets[__n] = __tmp;
677 return iterator(__tmp, this);
680 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
681 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
682 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
683 find_or_insert(const value_type& __obj)
685 resize(_M_num_elements + 1);
687 size_type __n = _M_bkt_num(__obj);
688 _Node* __first = _M_buckets[__n];
690 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
691 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
692 return __cur->_M_val;
694 _Node* __tmp = _M_new_node(__obj);
695 __tmp->_M_next = __first;
696 _M_buckets[__n] = __tmp;
698 return __tmp->_M_val;
701 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
702 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
703 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
704 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key)
706 typedef std::pair<iterator, iterator> _Pii;
707 const size_type __n = _M_bkt_num_key(__key);
709 for (_Node* __first = _M_buckets[__n]; __first;
710 __first = __first->_M_next)
711 if (_M_equals(_M_get_key(__first->_M_val), __key))
713 for (_Node* __cur = __first->_M_next; __cur;
714 __cur = __cur->_M_next)
715 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
716 return _Pii(iterator(__first, this), iterator(__cur, this));
717 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
719 return _Pii(iterator(__first, this),
720 iterator(_M_buckets[__m], this));
721 return _Pii(iterator(__first, this), end());
723 return _Pii(end(), end());
726 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
727 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
728 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
729 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key) const
731 typedef std::pair<const_iterator, const_iterator> _Pii;
732 const size_type __n = _M_bkt_num_key(__key);
734 for (const _Node* __first = _M_buckets[__n]; __first;
735 __first = __first->_M_next)
737 if (_M_equals(_M_get_key(__first->_M_val), __key))
739 for (const _Node* __cur = __first->_M_next; __cur;
740 __cur = __cur->_M_next)
741 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
742 return _Pii(const_iterator(__first, this),
743 const_iterator(__cur, this));
744 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
746 return _Pii(const_iterator(__first, this),
747 const_iterator(_M_buckets[__m], this));
748 return _Pii(const_iterator(__first, this), end());
751 return _Pii(end(), end());
754 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
755 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
756 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const key_type& __key)
758 const size_type __n = _M_bkt_num_key(__key);
759 _Node* __first = _M_buckets[__n];
760 size_type __erased = 0;
764 _Node* __cur = __first;
765 _Node* __next = __cur->_M_next;
768 if (_M_equals(_M_get_key(__next->_M_val), __key))
770 __cur->_M_next = __next->_M_next;
771 _M_delete_node(__next);
772 __next = __cur->_M_next;
779 __next = __cur->_M_next;
782 if (_M_equals(_M_get_key(__first->_M_val), __key))
784 _M_buckets[__n] = __first->_M_next;
785 _M_delete_node(__first);
793 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
794 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const iterator& __it)
796 _Node* __p = __it._M_cur;
799 const size_type __n = _M_bkt_num(__p->_M_val);
800 _Node* __cur = _M_buckets[__n];
803 _M_buckets[__n] = __cur->_M_next;
804 _M_delete_node(__cur);
809 _Node* __next = __cur->_M_next;
814 __cur->_M_next = __next->_M_next;
815 _M_delete_node(__next);
822 __next = __cur->_M_next;
829 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
830 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(iterator __first, iterator __last)
832 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
834 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
836 if (__first._M_cur == __last._M_cur)
838 else if (__f_bucket == __l_bucket)
839 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
842 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
843 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
844 _M_erase_bucket(__n, 0);
845 if (__l_bucket != _M_buckets.size())
846 _M_erase_bucket(__l_bucket, __last._M_cur);
850 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
852 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
853 erase(const_iterator __first, const_iterator __last)
855 erase(iterator(const_cast<_Node*>(__first._M_cur),
856 const_cast<hashtable*>(__first._M_ht)),
857 iterator(const_cast<_Node*>(__last._M_cur),
858 const_cast<hashtable*>(__last._M_ht)));
861 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
862 inline void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const const_iterator& __it)
863 { erase(iterator(const_cast<_Node*>(__it._M_cur), const_cast<hashtable*>(__it._M_ht))); }
865 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
866 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::resize(size_type __num_elements_hint)
868 const size_type __old_n = _M_buckets.size();
869 if (__num_elements_hint > __old_n)
871 const size_type __n = _M_next_size(__num_elements_hint);
874 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
877 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
879 _Node* __first = _M_buckets[__bucket];
882 size_type __new_bucket = _M_bkt_num(__first->_M_val,__n);
883 _M_buckets[__bucket] = __first->_M_next;
884 __first->_M_next = __tmp[__new_bucket];
885 __tmp[__new_bucket] = __first;
886 __first = _M_buckets[__bucket];
889 _M_buckets.swap(__tmp);
893 for (size_type __bucket = 0; __bucket < __tmp.size();++__bucket)
895 while (__tmp[__bucket])
897 _Node* __next = __tmp[__bucket]->_M_next;
898 _M_delete_node(__tmp[__bucket]);
899 __tmp[__bucket] = __next;
908 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
909 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
911 _Node* __cur = _M_buckets[__n];
912 if (__cur == __first)
913 _M_erase_bucket(__n, __last);
917 for (__next = __cur->_M_next;
919 __cur = __next, __next = __cur->_M_next)
921 while (__next != __last)
923 __cur->_M_next = __next->_M_next;
924 _M_delete_node(__next);
925 __next = __cur->_M_next;
931 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
932 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __last)
934 _Node* __cur = _M_buckets[__n];
935 while (__cur != __last)
937 _Node* __next = __cur->_M_next;
938 _M_delete_node(__cur);
940 _M_buckets[__n] = __cur;
945 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
946 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::clear()
948 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
950 _Node* __cur = _M_buckets[__i];
953 _Node* __next = __cur->_M_next;
954 _M_delete_node(__cur);
962 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
963 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_copy_from(const hashtable& __ht)
966 _M_buckets.reserve(__ht._M_buckets.size());
967 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
970 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
971 const _Node* __cur = __ht._M_buckets[__i];
974 _Node* __local_copy = _M_new_node(__cur->_M_val);
975 _M_buckets[__i] = __local_copy;
976 for (_Node* __next = __cur->_M_next;
978 __cur = __next, __next = __cur->_M_next)
980 __local_copy->_M_next = _M_new_node(__next->_M_val);
981 __local_copy = __local_copy->_M_next;
985 _M_num_elements = __ht._M_num_elements;