1 // Copyright (C) 2001-2014 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
20 // This library is distributed in the hope that it will be useful,
21 // but WITHOUT ANY WARRANTY; without even the implied warranty of
22 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23 // GNU General Public License for more details.
25 // Under Section 7 of GPL version 3, you are granted additional
26 // permissions described in the GCC Runtime Library Exception, version
27 // 3.1, as published by the Free Software Foundation.
29 // You should have received a copy of the GNU General Public License and
30 // a copy of the GCC Runtime Library Exception along with this program;
31 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
32 // <http://www.gnu.org/licenses/>.
35 * Copyright (c) 1996,1997
36 * Silicon Graphics Computer Systems, Inc.
38 * Permission to use, copy, modify, distribute and sell this software
39 * and its documentation for any purpose is hereby granted without fee,
40 * provided that the above copyright notice appear in all copies and
41 * that both that copyright notice and this permission notice appear
42 * in supporting documentation. Silicon Graphics makes no
43 * representations about the suitability of this software for any
44 * purpose. It is provided "as is" without express or implied warranty.
48 * Hewlett-Packard Company
50 * Permission to use, copy, modify, distribute and sell this software
51 * and its documentation for any purpose is hereby granted without fee,
52 * provided that the above copyright notice appear in all copies and
53 * that both that copyright notice and this permission notice appear
54 * in supporting documentation. Hewlett-Packard Company makes no
55 * representations about the suitability of this software for any
56 * purpose. It is provided "as is" without express or implied warranty.
59 #ifndef __INTERPKERNELHASHTABLE_HXX__
60 #define __INTERPKERNELHASHTABLE_HXX__
62 #include "InterpKernelStlExt.hxx"
63 #include "InterpKernelHashFun.hxx"
70 namespace INTERP_KERNEL
73 struct _Hashtable_node
75 _Hashtable_node* _M_next;
79 template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
80 class _EqualKey, class _Alloc = std::allocator<_Val> >
83 template<class _Val, class _Key, class _HashFcn,
84 class _ExtractKey, class _EqualKey, class _Alloc>
85 struct _Hashtable_iterator;
87 template<class _Val, class _Key, class _HashFcn,
88 class _ExtractKey, class _EqualKey, class _Alloc>
89 struct _Hashtable_const_iterator;
91 template<class _Val, class _Key, class _HashFcn,
92 class _ExtractKey, class _EqualKey, class _Alloc>
93 struct _Hashtable_iterator
95 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
97 typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
98 _ExtractKey, _EqualKey, _Alloc>
100 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
101 _ExtractKey, _EqualKey, _Alloc>
103 typedef _Hashtable_node<_Val> _Node;
104 typedef std::forward_iterator_tag iterator_category;
105 typedef _Val value_type;
106 typedef std::ptrdiff_t difference_type;
107 typedef std::size_t size_type;
108 typedef _Val& reference;
109 typedef _Val* pointer;
114 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
115 : _M_cur(__n), _M_ht(__tab) { }
117 _Hashtable_iterator() { }
121 { return _M_cur->_M_val; }
125 { return &(operator*()); }
134 operator==(const iterator& __it) const
135 { return _M_cur == __it._M_cur; }
138 operator!=(const iterator& __it) const
139 { return _M_cur != __it._M_cur; }
142 template<class _Val, class _Key, class _HashFcn,
143 class _ExtractKey, class _EqualKey, class _Alloc>
144 struct _Hashtable_const_iterator
146 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
148 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
149 _ExtractKey,_EqualKey,_Alloc>
151 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
152 _ExtractKey, _EqualKey, _Alloc>
154 typedef _Hashtable_node<_Val> _Node;
156 typedef std::forward_iterator_tag iterator_category;
157 typedef _Val value_type;
158 typedef std::ptrdiff_t difference_type;
159 typedef std::size_t size_type;
160 typedef const _Val& reference;
161 typedef const _Val* pointer;
164 const _Hashtable* _M_ht;
166 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
167 : _M_cur(__n), _M_ht(__tab) { }
169 _Hashtable_const_iterator() { }
171 _Hashtable_const_iterator(const iterator& __it)
172 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
174 reference operator*() const { return _M_cur->_M_val; }
176 pointer operator->() const { return &(operator*()); }
178 const_iterator& operator++();
180 const_iterator operator++(int);
182 bool operator==(const const_iterator& __it) const { return _M_cur == __it._M_cur; }
184 bool operator!=(const const_iterator& __it) const { return _M_cur != __it._M_cur; }
187 // Note: assumes long is at least 32 bits.
188 enum { _S_num_primes = 28 };
190 static const unsigned long __stl_prime_list[_S_num_primes] =
192 53ul, 97ul, 193ul, 389ul, 769ul,
193 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
194 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
195 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
196 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
197 1610612741ul, 3221225473ul, 4294967291ul
201 __stl_next_prime(unsigned long __n)
203 const unsigned long* __first = __stl_prime_list;
204 const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
205 const unsigned long* pos = std::lower_bound(__first, __last, __n);
206 return pos == __last ? *(__last - 1) : *pos;
209 // Forward declaration of operator==.
210 template<class _Val, class _Key, class _HF, class _Ex,
211 class _Eq, class _All>
214 template<class _Val, class _Key, class _HF, class _Ex,
215 class _Eq, class _All>
216 bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
217 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
219 // Hashtables handle allocators a bit differently than other
220 // containers do. If we're using standard-conforming allocators, then
221 // a hashtable unconditionally has a member variable to hold its
222 // allocator, even if it so happens that all instances of the
223 // allocator type are identical. This is because, for hashtables,
224 // this extra storage is negligible. Additionally, a base class
225 // wouldn't serve any other purposes; it wouldn't, for example,
226 // simplify the exception-handling code.
227 template<class _Val, class _Key, class _HashFcn,
228 class _ExtractKey, class _EqualKey, class _Alloc>
232 typedef _Key key_type;
233 typedef _Val value_type;
234 typedef _HashFcn hasher;
235 typedef _EqualKey key_equal;
237 typedef std::size_t size_type;
238 typedef std::ptrdiff_t difference_type;
239 typedef value_type* pointer;
240 typedef const value_type* const_pointer;
241 typedef value_type& reference;
242 typedef const value_type& const_reference;
244 hasher hash_funct() const { return _M_hash; }
246 key_equal key_eq() const { return _M_equals; }
249 typedef _Hashtable_node<_Val> _Node;
252 typedef typename _Alloc::template rebind<value_type>::other allocator_type;
253 allocator_type get_allocator() const { return _M_node_allocator; }
256 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
257 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
258 typedef std::vector<_Node*, _Nodeptr_Alloc> _Vector_type;
260 _Node_Alloc _M_node_allocator;
262 _Node *_M_get_node() { return _M_node_allocator.allocate(1); }
264 void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); }
269 _ExtractKey _M_get_key;
270 _Vector_type _M_buckets;
271 size_type _M_num_elements;
274 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
277 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
282 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
285 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
289 hashtable(size_type __n, const _HashFcn& __hf,
290 const _EqualKey& __eql, const _ExtractKey& __ext,
291 const allocator_type& __a = allocator_type())
292 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
293 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
294 { _M_initialize_buckets(__n); }
296 hashtable(size_type __n, const _HashFcn& __hf,
297 const _EqualKey& __eql,
298 const allocator_type& __a = allocator_type())
299 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
300 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
301 { _M_initialize_buckets(__n); }
303 hashtable(const hashtable& __ht)
304 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
305 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
306 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
307 { _M_copy_from(__ht); }
309 hashtable& operator= (const hashtable& __ht)
314 _M_hash = __ht._M_hash;
315 _M_equals = __ht._M_equals;
316 _M_get_key = __ht._M_get_key;
325 size_type size() const { return _M_num_elements; }
327 size_type max_size() const { return size_type(-1); }
329 bool empty() const { return size() == 0; }
331 void swap(hashtable& __ht)
333 std::swap(_M_hash, __ht._M_hash);
334 std::swap(_M_equals, __ht._M_equals);
335 std::swap(_M_get_key, __ht._M_get_key);
336 _M_buckets.swap(__ht._M_buckets);
337 std::swap(_M_num_elements, __ht._M_num_elements);
342 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
344 return iterator(_M_buckets[__n], this);
348 iterator end() { return iterator(0, this); }
350 const_iterator begin() const
352 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
354 return const_iterator(_M_buckets[__n], this);
358 const_iterator end() const { return const_iterator(0, this); }
360 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, class _Al>
361 friend bool operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
362 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
365 size_type bucket_count() const { return _M_buckets.size(); }
367 size_type max_bucket_count() const { return __stl_prime_list[(int)_S_num_primes - 1]; }
369 size_type elems_in_bucket(size_type __bucket) const
371 size_type __result = 0;
372 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
377 std::pair<iterator, bool> insert_unique(const value_type& __obj)
379 resize(_M_num_elements + 1);
380 return insert_unique_noresize(__obj);
383 iterator insert_equal(const value_type& __obj)
385 resize(_M_num_elements + 1);
386 return insert_equal_noresize(__obj);
389 std::pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
391 iterator insert_equal_noresize(const value_type& __obj);
393 template<class _InputIterator>
394 void insert_unique(_InputIterator __f, _InputIterator __l)
395 { insert_unique(__f, __l, __iterator_category(__f)); }
397 template<class _InputIterator>
398 void insert_equal(_InputIterator __f, _InputIterator __l)
399 { insert_equal(__f, __l, __iterator_category(__f)); }
401 template<class _InputIterator>
402 void insert_unique(_InputIterator __f, _InputIterator __l,
403 std::input_iterator_tag)
405 for ( ; __f != __l; ++__f)
409 template<class _InputIterator>
410 void insert_equal(_InputIterator __f, _InputIterator __l,
411 std::input_iterator_tag)
413 for ( ; __f != __l; ++__f)
417 template<class _ForwardIterator>
418 void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
419 std::forward_iterator_tag)
421 size_type __n = std::distance(__f, __l);
422 resize(_M_num_elements + __n);
423 for ( ; __n > 0; --__n, ++__f)
424 insert_unique_noresize(*__f);
427 template<class _ForwardIterator>
429 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
430 std::forward_iterator_tag)
432 size_type __n = std::distance(__f, __l);
433 resize(_M_num_elements + __n);
434 for ( ; __n > 0; --__n, ++__f)
435 insert_equal_noresize(*__f);
438 reference find_or_insert(const value_type& __obj);
440 iterator find(const key_type& __key)
442 size_type __n = _M_bkt_num_key(__key);
444 for (__first = _M_buckets[__n];
445 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
446 __first = __first->_M_next)
448 return iterator(__first, this);
451 const_iterator find(const key_type& __key) const
453 size_type __n = _M_bkt_num_key(__key);
454 const _Node* __first;
455 for (__first = _M_buckets[__n];
456 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
457 __first = __first->_M_next)
459 return const_iterator(__first, this);
462 size_type count(const key_type& __key) const
464 const size_type __n = _M_bkt_num_key(__key);
465 size_type __result = 0;
466 for (const _Node* __cur = _M_buckets[__n]; __cur;
467 __cur = __cur->_M_next)
468 if (_M_equals(_M_get_key(__cur->_M_val), __key))
473 std::pair<iterator, iterator> equal_range(const key_type& __key);
475 std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const;
477 size_type erase(const key_type& __key);
479 void erase(const iterator& __it);
481 void erase(iterator __first, iterator __last);
483 void erase(const const_iterator& __it);
485 void erase(const_iterator __first, const_iterator __last);
487 void resize(size_type __num_elements_hint);
492 size_type _M_next_size(size_type __n) const { return __stl_next_prime(__n); }
494 void _M_initialize_buckets(size_type __n)
496 const size_type __n_buckets = _M_next_size(__n);
497 _M_buckets.reserve(__n_buckets);
498 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
502 size_type _M_bkt_num_key(const key_type& __key) const
503 { return _M_bkt_num_key(__key, _M_buckets.size()); }
505 size_type _M_bkt_num(const value_type& __obj) const
506 { return _M_bkt_num_key(_M_get_key(__obj)); }
508 size_type _M_bkt_num_key(const key_type& __key, std::size_t __n) const
509 { return _M_hash(__key) % __n; }
511 size_type _M_bkt_num(const value_type& __obj, std::size_t __n) const
512 { return _M_bkt_num_key(_M_get_key(__obj), __n); }
514 _Node* _M_new_node(const value_type& __obj)
516 _Node* __n = _M_get_node();
520 this->get_allocator().construct(&__n->_M_val, __obj);
530 void _M_delete_node(_Node* __n)
532 this->get_allocator().destroy(&__n->_M_val);
536 void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
538 void _M_erase_bucket(const size_type __n, _Node* __last);
540 void _M_copy_from(const hashtable& __ht);
543 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
544 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
545 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
548 const _Node* __old = _M_cur;
549 _M_cur = _M_cur->_M_next;
552 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
553 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
554 _M_cur = _M_ht->_M_buckets[__bucket];
559 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
560 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
561 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
564 iterator __tmp = *this;
569 template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
570 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
571 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
574 const _Node* __old = _M_cur;
575 _M_cur = _M_cur->_M_next;
578 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
579 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
580 _M_cur = _M_ht->_M_buckets[__bucket];
585 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
587 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
588 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
591 const_iterator __tmp = *this;
596 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
597 bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
598 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
600 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
602 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
605 for (std::size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
607 _Node* __cur1 = __ht1._M_buckets[__n];
608 _Node* __cur2 = __ht2._M_buckets[__n];
609 // Check same length of lists
610 for (; __cur1 && __cur2;
611 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
613 if (__cur1 || __cur2)
615 // Now check one's elements are in the other
616 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
617 __cur1 = __cur1->_M_next)
619 bool _found__cur1 = false;
620 for (__cur2 = __ht2._M_buckets[__n];
621 __cur2; __cur2 = __cur2->_M_next)
623 if (__cur1->_M_val == __cur2->_M_val)
636 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
637 inline bool operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
638 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
639 { return !(__ht1 == __ht2); }
641 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, class _All>
642 inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
643 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
644 { __ht1.swap(__ht2); }
646 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
647 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
648 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
649 insert_unique_noresize(const value_type& __obj)
651 const size_type __n = _M_bkt_num(__obj);
652 _Node* __first = _M_buckets[__n];
654 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
655 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
656 return std::pair<iterator, bool>(iterator(__cur, this), false);
658 _Node* __tmp = _M_new_node(__obj);
659 __tmp->_M_next = __first;
660 _M_buckets[__n] = __tmp;
662 return std::pair<iterator, bool>(iterator(__tmp, this), true);
665 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
666 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
667 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
668 insert_equal_noresize(const value_type& __obj)
670 const size_type __n = _M_bkt_num(__obj);
671 _Node* __first = _M_buckets[__n];
673 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
674 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
676 _Node* __tmp = _M_new_node(__obj);
677 __tmp->_M_next = __cur->_M_next;
678 __cur->_M_next = __tmp;
680 return iterator(__tmp, this);
683 _Node* __tmp = _M_new_node(__obj);
684 __tmp->_M_next = __first;
685 _M_buckets[__n] = __tmp;
687 return iterator(__tmp, this);
690 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
691 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
692 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
693 find_or_insert(const value_type& __obj)
695 resize(_M_num_elements + 1);
697 size_type __n = _M_bkt_num(__obj);
698 _Node* __first = _M_buckets[__n];
700 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
701 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
702 return __cur->_M_val;
704 _Node* __tmp = _M_new_node(__obj);
705 __tmp->_M_next = __first;
706 _M_buckets[__n] = __tmp;
708 return __tmp->_M_val;
711 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
712 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
713 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
714 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key)
716 typedef std::pair<iterator, iterator> _Pii;
717 const size_type __n = _M_bkt_num_key(__key);
719 for (_Node* __first = _M_buckets[__n]; __first;
720 __first = __first->_M_next)
721 if (_M_equals(_M_get_key(__first->_M_val), __key))
723 for (_Node* __cur = __first->_M_next; __cur;
724 __cur = __cur->_M_next)
725 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
726 return _Pii(iterator(__first, this), iterator(__cur, this));
727 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
729 return _Pii(iterator(__first, this),
730 iterator(_M_buckets[__m], this));
731 return _Pii(iterator(__first, this), end());
733 return _Pii(end(), end());
736 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
737 std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
738 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
739 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key) const
741 typedef std::pair<const_iterator, const_iterator> _Pii;
742 const size_type __n = _M_bkt_num_key(__key);
744 for (const _Node* __first = _M_buckets[__n]; __first;
745 __first = __first->_M_next)
747 if (_M_equals(_M_get_key(__first->_M_val), __key))
749 for (const _Node* __cur = __first->_M_next; __cur;
750 __cur = __cur->_M_next)
751 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
752 return _Pii(const_iterator(__first, this),
753 const_iterator(__cur, this));
754 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
756 return _Pii(const_iterator(__first, this),
757 const_iterator(_M_buckets[__m], this));
758 return _Pii(const_iterator(__first, this), end());
761 return _Pii(end(), end());
764 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
765 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
766 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const key_type& __key)
768 const size_type __n = _M_bkt_num_key(__key);
769 _Node* __first = _M_buckets[__n];
770 size_type __erased = 0;
774 _Node* __cur = __first;
775 _Node* __next = __cur->_M_next;
778 if (_M_equals(_M_get_key(__next->_M_val), __key))
780 __cur->_M_next = __next->_M_next;
781 _M_delete_node(__next);
782 __next = __cur->_M_next;
789 __next = __cur->_M_next;
792 if (_M_equals(_M_get_key(__first->_M_val), __key))
794 _M_buckets[__n] = __first->_M_next;
795 _M_delete_node(__first);
803 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
804 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const iterator& __it)
806 _Node* __p = __it._M_cur;
809 const size_type __n = _M_bkt_num(__p->_M_val);
810 _Node* __cur = _M_buckets[__n];
813 _M_buckets[__n] = __cur->_M_next;
814 _M_delete_node(__cur);
819 _Node* __next = __cur->_M_next;
824 __cur->_M_next = __next->_M_next;
825 _M_delete_node(__next);
832 __next = __cur->_M_next;
839 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
840 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(iterator __first, iterator __last)
842 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
844 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
846 if (__first._M_cur == __last._M_cur)
848 else if (__f_bucket == __l_bucket)
849 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
852 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
853 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
854 _M_erase_bucket(__n, 0);
855 if (__l_bucket != _M_buckets.size())
856 _M_erase_bucket(__l_bucket, __last._M_cur);
860 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
862 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
863 erase(const_iterator __first, const_iterator __last)
865 erase(iterator(const_cast<_Node*>(__first._M_cur),
866 const_cast<hashtable*>(__first._M_ht)),
867 iterator(const_cast<_Node*>(__last._M_cur),
868 const_cast<hashtable*>(__last._M_ht)));
871 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
872 inline void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const const_iterator& __it)
873 { erase(iterator(const_cast<_Node*>(__it._M_cur), const_cast<hashtable*>(__it._M_ht))); }
875 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
876 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::resize(size_type __num_elements_hint)
878 const size_type __old_n = _M_buckets.size();
879 if (__num_elements_hint > __old_n)
881 const size_type __n = _M_next_size(__num_elements_hint);
884 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
887 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
889 _Node* __first = _M_buckets[__bucket];
892 size_type __new_bucket = _M_bkt_num(__first->_M_val,__n);
893 _M_buckets[__bucket] = __first->_M_next;
894 __first->_M_next = __tmp[__new_bucket];
895 __tmp[__new_bucket] = __first;
896 __first = _M_buckets[__bucket];
899 _M_buckets.swap(__tmp);
903 for (size_type __bucket = 0; __bucket < __tmp.size();++__bucket)
905 while (__tmp[__bucket])
907 _Node* __next = __tmp[__bucket]->_M_next;
908 _M_delete_node(__tmp[__bucket]);
909 __tmp[__bucket] = __next;
918 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
919 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
921 _Node* __cur = _M_buckets[__n];
922 if (__cur == __first)
923 _M_erase_bucket(__n, __last);
927 for (__next = __cur->_M_next;
929 __cur = __next, __next = __cur->_M_next)
931 while (__next != __last)
933 __cur->_M_next = __next->_M_next;
934 _M_delete_node(__next);
935 __next = __cur->_M_next;
941 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
942 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __last)
944 _Node* __cur = _M_buckets[__n];
945 while (__cur != __last)
947 _Node* __next = __cur->_M_next;
948 _M_delete_node(__cur);
950 _M_buckets[__n] = __cur;
955 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
956 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::clear()
958 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
960 _Node* __cur = _M_buckets[__i];
963 _Node* __next = __cur->_M_next;
964 _M_delete_node(__cur);
972 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
973 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_copy_from(const hashtable& __ht)
976 _M_buckets.reserve(__ht._M_buckets.size());
977 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
980 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
981 const _Node* __cur = __ht._M_buckets[__i];
984 _Node* __local_copy = _M_new_node(__cur->_M_val);
985 _M_buckets[__i] = __local_copy;
986 for (_Node* __next = __cur->_M_next;
988 __cur = __next, __next = __cur->_M_next)
990 __local_copy->_M_next = _M_new_node(__next->_M_val);
991 __local_copy = __local_copy->_M_next;
995 _M_num_elements = __ht._M_num_elements;