1 // Copyright (C) 2007-2019 CEA/DEN, EDF R&D
3 // This library is free software; you can redistribute it and/or
4 // modify it under the terms of the GNU Lesser General Public
5 // License as published by the Free Software Foundation; either
6 // version 2.1 of the License, or (at your option) any later version.
8 // This library is distributed in the hope that it will be useful,
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 // Lesser General Public License for more details.
13 // You should have received a copy of the GNU Lesser General Public
14 // License along with this library; if not, write to the Free Software
15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
19 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
20 // Free Software Foundation, Inc.
22 // This file is part of the GNU ISO C++ Library. This library is free
23 // software; you can redistribute it and/or modify it under the
24 // terms of the GNU General Public License as published by the
25 // Free Software Foundation; either version 3, or (at your option)
28 // This library is distributed in the hope that it will be useful,
29 // but WITHOUT ANY WARRANTY; without even the implied warranty of
30 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 // GNU General Public License for more details.
33 // Under Section 7 of GPL version 3, you are granted additional
34 // permissions described in the GCC Runtime Library Exception, version
35 // 3.1, as published by the Free Software Foundation.
37 // You should have received a copy of the GNU General Public License and
38 // a copy of the GCC Runtime Library Exception along with this program;
39 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
40 // <http://www.gnu.org/licenses/>.
43 * Copyright (c) 1996,1997
44 * Silicon Graphics Computer Systems, Inc.
46 * Permission to use, copy, modify, distribute and sell this software
47 * and its documentation for any purpose is hereby granted without fee,
48 * provided that the above copyright notice appear in all copies and
49 * that both that copyright notice and this permission notice appear
50 * in supporting documentation. Silicon Graphics makes no
51 * representations about the suitability of this software for any
52 * purpose. It is provided "as is" without express or implied warranty.
56 * Hewlett-Packard Company
58 * Permission to use, copy, modify, distribute and sell this software
59 * and its documentation for any purpose is hereby granted without fee,
60 * provided that the above copyright notice appear in all copies and
61 * that both that copyright notice and this permission notice appear
62 * in supporting documentation. Hewlett-Packard Company makes no
63 * representations about the suitability of this software for any
64 * purpose. It is provided "as is" without express or implied warranty.
67 #ifndef __INTERPKERNELHASHTABLE_HXX__
68 #define __INTERPKERNELHASHTABLE_HXX__
70 #include "InterpKernelStlExt.hxx"
71 #include "InterpKernelHashFun.hxx"
78 namespace INTERP_KERNEL
81 struct _Hashtable_node
83 _Hashtable_node* _M_next;
87 template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
88 class _EqualKey, class _Alloc = std::allocator<_Val> >
91 template<class _Val, class _Key, class _HashFcn,
92 class _ExtractKey, class _EqualKey, class _Alloc>
93 struct _Hashtable_iterator;
95 template<class _Val, class _Key, class _HashFcn,
96 class _ExtractKey, class _EqualKey, class _Alloc>
97 struct _Hashtable_const_iterator;
99 template<class _Val, class _Key, class _HashFcn,
100 class _ExtractKey, class _EqualKey, class _Alloc>
101 struct _Hashtable_iterator
103 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
105 typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
106 _ExtractKey, _EqualKey, _Alloc>
108 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
109 _ExtractKey, _EqualKey, _Alloc>
111 typedef _Hashtable_node<_Val> _Node;
112 typedef std::forward_iterator_tag iterator_category;
113 typedef _Val value_type;
114 typedef std::ptrdiff_t difference_type;
115 typedef std::size_t size_type;
116 typedef _Val& reference;
117 typedef _Val* pointer;
122 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
123 : _M_cur(__n), _M_ht(__tab) { }
125 _Hashtable_iterator() { }
129 { return _M_cur->_M_val; }
133 { return &(operator*()); }
142 operator==(const iterator& __it) const
143 { return _M_cur == __it._M_cur; }
146 operator!=(const iterator& __it) const
147 { return _M_cur != __it._M_cur; }
150 template<class _Val, class _Key, class _HashFcn,
151 class _ExtractKey, class _EqualKey, class _Alloc>
152 struct _Hashtable_const_iterator
154 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
156 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
157 _ExtractKey,_EqualKey,_Alloc>
159 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
160 _ExtractKey, _EqualKey, _Alloc>
162 typedef _Hashtable_node<_Val> _Node;
164 typedef std::forward_iterator_tag iterator_category;
165 typedef _Val value_type;
166 typedef std::ptrdiff_t difference_type;
167 typedef std::size_t size_type;
168 typedef const _Val& reference;
169 typedef const _Val* pointer;
172 const _Hashtable* _M_ht;
174 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
175 : _M_cur(__n), _M_ht(__tab) { }
177 _Hashtable_const_iterator() { }
179 _Hashtable_const_iterator(const iterator& __it)
180 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
182 reference operator*() const { return _M_cur->_M_val; }
184 pointer operator->() const { return &(operator*()); }
186 const_iterator& operator++();
188 const_iterator operator++(int);
190 bool operator==(const const_iterator& __it) const { return _M_cur == __it._M_cur; }
192 bool operator!=(const const_iterator& __it) const { return _M_cur != __it._M_cur; }
195 // Note: assumes long is at least 32 bits.
196 enum { _S_num_primes = 28 };
198 static const unsigned long long __stl_prime_list[_S_num_primes] =
200 53ull, 97ull, 193ull, 389ull, 769ull,
201 1543ull, 3079ull, 6151ull, 12289ull, 24593ull,
202 49157ull, 98317ull, 196613ull, 393241ull, 786433ull,
203 1572869ull, 3145739ull, 6291469ull, 12582917ull, 25165843ull,
204 50331653ull, 100663319ull, 201326611ull, 402653189ull, 805306457ull,
205 1610612741ull, 3221225473ull, 4294967291ull
208 inline unsigned long long
209 __stl_next_prime(unsigned long long __n)
211 const unsigned long long* __first = __stl_prime_list;
212 const unsigned long long* __last = __stl_prime_list + (int)_S_num_primes;
213 const unsigned long long* pos = std::lower_bound(__first, __last, __n);
214 return pos == __last ? *(__last - 1) : *pos;
217 // Forward declaration of operator==.
218 template<class _Val, class _Key, class _HF, class _Ex,
219 class _Eq, class _All>
222 template<class _Val, class _Key, class _HF, class _Ex,
223 class _Eq, class _All>
224 bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
225 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
227 // Hashtables handle allocators a bit differently than other
228 // containers do. If we're using standard-conforming allocators, then
229 // a hashtable unconditionally has a member variable to hold its
230 // allocator, even if it so happens that all instances of the
231 // allocator type are identical. This is because, for hashtables,
232 // this extra storage is negligible. Additionally, a base class
233 // wouldn't serve any other purposes; it wouldn't, for example,
234 // simplify the exception-handling code.
235 template<class _Val, class _Key, class _HashFcn,
236 class _ExtractKey, class _EqualKey, class _Alloc>
240 typedef _Key key_type;
241 typedef _Val value_type;
242 typedef _HashFcn hasher;
243 typedef _EqualKey key_equal;
245 typedef std::size_t size_type;
246 typedef std::ptrdiff_t difference_type;
247 typedef value_type* pointer;
248 typedef const value_type* const_pointer;
249 typedef value_type& reference;
250 typedef const value_type& const_reference;
252 hasher hash_funct() const { return _M_hash; }
254 key_equal key_eq() const { return _M_equals; }
257 typedef _Hashtable_node<_Val> _Node;
260 typedef typename _Alloc::template rebind<value_type>::other allocator_type;
261 allocator_type get_allocator() const { return _M_node_allocator; }
264 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
265 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
266 typedef std::vector<_Node*, _Nodeptr_Alloc> _Vector_type;
268 _Node_Alloc _M_node_allocator;
270 _Node *_M_get_node() { return _M_node_allocator.allocate(1); }
272 void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); }
277 _ExtractKey _M_get_key;
278 _Vector_type _M_buckets;
279 size_type _M_num_elements;
282 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
285 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
290 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
293 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
297 hashtable(size_type __n, const _HashFcn& __hf,
298 const _EqualKey& __eql, const _ExtractKey& __ext,
299 const allocator_type& __a = allocator_type())
300 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
301 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
302 { _M_initialize_buckets(__n); }
304 hashtable(size_type __n, const _HashFcn& __hf,
305 const _EqualKey& __eql,
306 const allocator_type& __a = allocator_type())
307 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
308 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
309 { _M_initialize_buckets(__n); }
311 hashtable(const hashtable& __ht)
312 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
313 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
314 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
315 { _M_copy_from(__ht); }
317 hashtable& operator= (const hashtable& __ht)
322 _M_hash = __ht._M_hash;
323 _M_equals = __ht._M_equals;
324 _M_get_key = __ht._M_get_key;
333 size_type size() const { return _M_num_elements; }
335 size_type max_size() const { return size_type(-1); }
337 bool empty() const { return size() == 0; }
339 void swap(hashtable& __ht)
341 std::swap(_M_hash, __ht._M_hash);
342 std::swap(_M_equals, __ht._M_equals);
343 std::swap(_M_get_key, __ht._M_get_key);
344 _M_buckets.swap(__ht._M_buckets);
345 std::swap(_M_num_elements, __ht._M_num_elements);
350 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
352 return iterator(_M_buckets[__n], this);
356 iterator end() { return iterator(0, this); }
358 const_iterator begin() const
360 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
362 return const_iterator(_M_buckets[__n], this);
366 const_iterator end() const { return const_iterator(0, this); }
368 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, class _Al>
369 friend bool operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
370 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
373 size_type bucket_count() const { return _M_buckets.size(); }
375 size_type max_bucket_count() const { return __stl_prime_list[(int)_S_num_primes - 1]; }
377 size_type elems_in_bucket(size_type __bucket) const
379 size_type __result = 0;
380 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
385 std::pair<iterator, bool> insert_unique(const value_type& __obj)
387 resize(_M_num_elements + 1);
388 return insert_unique_noresize(__obj);
391 iterator insert_equal(const value_type& __obj)
393 resize(_M_num_elements + 1);
394 return insert_equal_noresize(__obj);
397 std::pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
399 iterator insert_equal_noresize(const value_type& __obj);
401 template<class _InputIterator>
402 void insert_unique(_InputIterator __f, _InputIterator __l)
403 { insert_unique(__f, __l, __iterator_category(__f)); }
405 template<class _InputIterator>
406 void insert_equal(_InputIterator __f, _InputIterator __l)
407 { insert_equal(__f, __l, __iterator_category(__f)); }
409 template<class _InputIterator>
410 void insert_unique(_InputIterator __f, _InputIterator __l,
411 std::input_iterator_tag)
413 for ( ; __f != __l; ++__f)
417 template<class _InputIterator>
418 void insert_equal(_InputIterator __f, _InputIterator __l,
419 std::input_iterator_tag)
421 for ( ; __f != __l; ++__f)
425 template<class _ForwardIterator>
426 void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
427 std::forward_iterator_tag)
429 size_type __n = std::distance(__f, __l);
430 resize(_M_num_elements + __n);
431 for ( ; __n > 0; --__n, ++__f)
432 insert_unique_noresize(*__f);
435 template<class _ForwardIterator>
437 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
438 std::forward_iterator_tag)
440 size_type __n = std::distance(__f, __l);
441 resize(_M_num_elements + __n);
442 for ( ; __n > 0; --__n, ++__f)
443 insert_equal_noresize(*__f);
446 reference find_or_insert(const value_type& __obj);
448 iterator find(const key_type& __key)
450 size_type __n = _M_bkt_num_key(__key);
452 for (__first = _M_buckets[__n];
453 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
454 __first = __first->_M_next)
456 return iterator(__first, this);
459 const_iterator find(const key_type& __key) const
461 size_type __n = _M_bkt_num_key(__key);
462 const _Node* __first;
463 for (__first = _M_buckets[__n];
464 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
465 __first = __first->_M_next)
467 return const_iterator(__first, this);
470 size_type count(const key_type& __key) const
472 const size_type __n = _M_bkt_num_key(__key);
473 size_type __result = 0;
474 for (const _Node* __cur = _M_buckets[__n]; __cur;
475 __cur = __cur->_M_next)
476 if (_M_equals(_M_get_key(__cur->_M_val), __key))
481 std::pair<iterator, iterator> equal_range(const key_type& __key);
483 std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const;
485 size_type erase(const key_type& __key);
487 void erase(const iterator& __it);
489 void erase(iterator __first, iterator __last);
491 void erase(const const_iterator& __it);
493 void erase(const_iterator __first, const_iterator __last);
495 void resize(size_type __num_elements_hint);
500 size_type _M_next_size(size_type __n) const { return static_cast<size_type>(__stl_next_prime(__n)); }
502 void _M_initialize_buckets(size_type __n)
504 const size_type __n_buckets = _M_next_size(__n);
505 _M_buckets.reserve(__n_buckets);
506 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
510 size_type _M_bkt_num_key(const key_type& __key) const
511 { return _M_bkt_num_key(__key, _M_buckets.size()); }
513 size_type _M_bkt_num(const value_type& __obj) const
514 { return _M_bkt_num_key(_M_get_key(__obj)); }
516 size_type _M_bkt_num_key(const key_type& __key, std::size_t __n) const
517 { return _M_hash(__key) % __n; }
519 size_type _M_bkt_num(const value_type& __obj, std::size_t __n) const
520 { return _M_bkt_num_key(_M_get_key(__obj), __n); }
522 _Node* _M_new_node(const value_type& __obj)
524 _Node* __n = _M_get_node();
528 this->get_allocator().construct(&__n->_M_val, __obj);
538 void _M_delete_node(_Node* __n)
540 this->get_allocator().destroy(&__n->_M_val);
544 void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
546 void _M_erase_bucket(const size_type __n, _Node* __last);
548 void _M_copy_from(const hashtable& __ht);
551 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
552 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
553 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
556 const _Node* __old = _M_cur;
557 _M_cur = _M_cur->_M_next;
560 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
561 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
562 _M_cur = _M_ht->_M_buckets[__bucket];
567 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
568 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
569 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
572 iterator __tmp = *this;
577 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
578 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
579 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
582 const _Node* __old = _M_cur;
583 _M_cur = _M_cur->_M_next;
586 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
587 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
588 _M_cur = _M_ht->_M_buckets[__bucket];
593 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
595 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
596 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
599 const_iterator __tmp = *this;
604 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
605 bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
606 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
608 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
610 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
613 for (std::size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
615 _Node* __cur1 = __ht1._M_buckets[__n];
616 _Node* __cur2 = __ht2._M_buckets[__n];
617 // Check same length of lists
618 for (; __cur1 && __cur2;
619 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
621 if (__cur1 || __cur2)
623 // Now check one's elements are in the other
624 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
625 __cur1 = __cur1->_M_next)
627 bool _found__cur1 = false;
628 for (__cur2 = __ht2._M_buckets[__n];
629 __cur2; __cur2 = __cur2->_M_next)
631 if (__cur1->_M_val == __cur2->_M_val)
644 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
645 inline bool operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
646 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
647 { return !(__ht1 == __ht2); }
649 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, class _All>
650 inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
651 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
652 { __ht1.swap(__ht2); }
654 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
655 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
656 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
657 insert_unique_noresize(const value_type& __obj)
659 const size_type __n = _M_bkt_num(__obj);
660 _Node* __first = _M_buckets[__n];
662 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
663 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
664 return std::pair<iterator, bool>(iterator(__cur, this), false);
666 _Node* __tmp = _M_new_node(__obj);
667 __tmp->_M_next = __first;
668 _M_buckets[__n] = __tmp;
670 return std::pair<iterator, bool>(iterator(__tmp, this), true);
673 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
674 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
675 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
676 insert_equal_noresize(const value_type& __obj)
678 const size_type __n = _M_bkt_num(__obj);
679 _Node* __first = _M_buckets[__n];
681 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
682 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
684 _Node* __tmp = _M_new_node(__obj);
685 __tmp->_M_next = __cur->_M_next;
686 __cur->_M_next = __tmp;
688 return iterator(__tmp, this);
691 _Node* __tmp = _M_new_node(__obj);
692 __tmp->_M_next = __first;
693 _M_buckets[__n] = __tmp;
695 return iterator(__tmp, this);
698 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
699 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
700 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
701 find_or_insert(const value_type& __obj)
703 resize(_M_num_elements + 1);
705 size_type __n = _M_bkt_num(__obj);
706 _Node* __first = _M_buckets[__n];
708 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
709 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
710 return __cur->_M_val;
712 _Node* __tmp = _M_new_node(__obj);
713 __tmp->_M_next = __first;
714 _M_buckets[__n] = __tmp;
716 return __tmp->_M_val;
719 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
720 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
721 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
722 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key)
724 typedef std::pair<iterator, iterator> _Pii;
725 const size_type __n = _M_bkt_num_key(__key);
727 for (_Node* __first = _M_buckets[__n]; __first;
728 __first = __first->_M_next)
729 if (_M_equals(_M_get_key(__first->_M_val), __key))
731 for (_Node* __cur = __first->_M_next; __cur;
732 __cur = __cur->_M_next)
733 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
734 return _Pii(iterator(__first, this), iterator(__cur, this));
735 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
737 return _Pii(iterator(__first, this),
738 iterator(_M_buckets[__m], this));
739 return _Pii(iterator(__first, this), end());
741 return _Pii(end(), end());
744 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
745 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
746 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
747 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key) const
749 typedef std::pair<const_iterator, const_iterator> _Pii;
750 const size_type __n = _M_bkt_num_key(__key);
752 for (const _Node* __first = _M_buckets[__n]; __first;
753 __first = __first->_M_next)
755 if (_M_equals(_M_get_key(__first->_M_val), __key))
757 for (const _Node* __cur = __first->_M_next; __cur;
758 __cur = __cur->_M_next)
759 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
760 return _Pii(const_iterator(__first, this),
761 const_iterator(__cur, this));
762 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
764 return _Pii(const_iterator(__first, this),
765 const_iterator(_M_buckets[__m], this));
766 return _Pii(const_iterator(__first, this), end());
769 return _Pii(end(), end());
772 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
773 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
774 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const key_type& __key)
776 const size_type __n = _M_bkt_num_key(__key);
777 _Node* __first = _M_buckets[__n];
778 size_type __erased = 0;
782 _Node* __cur = __first;
783 _Node* __next = __cur->_M_next;
786 if (_M_equals(_M_get_key(__next->_M_val), __key))
788 __cur->_M_next = __next->_M_next;
789 _M_delete_node(__next);
790 __next = __cur->_M_next;
797 __next = __cur->_M_next;
800 if (_M_equals(_M_get_key(__first->_M_val), __key))
802 _M_buckets[__n] = __first->_M_next;
803 _M_delete_node(__first);
811 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
812 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const iterator& __it)
814 _Node* __p = __it._M_cur;
817 const size_type __n = _M_bkt_num(__p->_M_val);
818 _Node* __cur = _M_buckets[__n];
821 _M_buckets[__n] = __cur->_M_next;
822 _M_delete_node(__cur);
827 _Node* __next = __cur->_M_next;
832 __cur->_M_next = __next->_M_next;
833 _M_delete_node(__next);
840 __next = __cur->_M_next;
847 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
848 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(iterator __first, iterator __last)
850 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
852 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
854 if (__first._M_cur == __last._M_cur)
856 else if (__f_bucket == __l_bucket)
857 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
860 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
861 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
862 _M_erase_bucket(__n, 0);
863 if (__l_bucket != _M_buckets.size())
864 _M_erase_bucket(__l_bucket, __last._M_cur);
868 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
870 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
871 erase(const_iterator __first, const_iterator __last)
873 erase(iterator(const_cast<_Node*>(__first._M_cur),
874 const_cast<hashtable*>(__first._M_ht)),
875 iterator(const_cast<_Node*>(__last._M_cur),
876 const_cast<hashtable*>(__last._M_ht)));
879 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
880 inline void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const const_iterator& __it)
881 { erase(iterator(const_cast<_Node*>(__it._M_cur), const_cast<hashtable*>(__it._M_ht))); }
883 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
884 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::resize(size_type __num_elements_hint)
886 const size_type __old_n = _M_buckets.size();
887 if (__num_elements_hint > __old_n)
889 const size_type __n = _M_next_size(__num_elements_hint);
892 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
895 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
897 _Node* __first = _M_buckets[__bucket];
900 size_type __new_bucket = _M_bkt_num(__first->_M_val,__n);
901 _M_buckets[__bucket] = __first->_M_next;
902 __first->_M_next = __tmp[__new_bucket];
903 __tmp[__new_bucket] = __first;
904 __first = _M_buckets[__bucket];
907 _M_buckets.swap(__tmp);
911 for (size_type __bucket = 0; __bucket < __tmp.size();++__bucket)
913 while (__tmp[__bucket])
915 _Node* __next = __tmp[__bucket]->_M_next;
916 _M_delete_node(__tmp[__bucket]);
917 __tmp[__bucket] = __next;
926 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
927 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
929 _Node* __cur = _M_buckets[__n];
930 if (__cur == __first)
931 _M_erase_bucket(__n, __last);
935 for (__next = __cur->_M_next;
937 __cur = __next, __next = __cur->_M_next)
939 while (__next != __last)
941 __cur->_M_next = __next->_M_next;
942 _M_delete_node(__next);
943 __next = __cur->_M_next;
949 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
950 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __last)
952 _Node* __cur = _M_buckets[__n];
953 while (__cur != __last)
955 _Node* __next = __cur->_M_next;
956 _M_delete_node(__cur);
958 _M_buckets[__n] = __cur;
963 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
964 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::clear()
966 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
968 _Node* __cur = _M_buckets[__i];
971 _Node* __next = __cur->_M_next;
972 _M_delete_node(__cur);
980 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
981 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_copy_from(const hashtable& __ht)
984 _M_buckets.reserve(__ht._M_buckets.size());
985 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
988 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
989 const _Node* __cur = __ht._M_buckets[__i];
992 _Node* __local_copy = _M_new_node(__cur->_M_val);
993 _M_buckets[__i] = __local_copy;
994 for (_Node* __next = __cur->_M_next;
996 __cur = __next, __next = __cur->_M_next)
998 __local_copy->_M_next = _M_new_node(__next->_M_val);
999 __local_copy = __local_copy->_M_next;
1003 _M_num_elements = __ht._M_num_elements;