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 namespace __gnu_cxx
_GLIBCXX_VISIBILITY(default)
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
75 using std::forward_iterator_tag
;
76 using std::input_iterator_tag
;
77 using std::_Construct
;
82 using std::__iterator_category
;
85 struct _Hashtable_node
87 _Hashtable_node
* _M_next
;
91 template<class _Val
, class _Key
, class _HashFcn
, class _ExtractKey
,
92 class _EqualKey
, class _Alloc
= std::allocator
<_Val
> >
95 template<class _Val
, class _Key
, class _HashFcn
,
96 class _ExtractKey
, class _EqualKey
, class _Alloc
>
97 struct _Hashtable_iterator
;
99 template<class _Val
, class _Key
, class _HashFcn
,
100 class _ExtractKey
, class _EqualKey
, class _Alloc
>
101 struct _Hashtable_const_iterator
;
103 template<class _Val
, class _Key
, class _HashFcn
,
104 class _ExtractKey
, class _EqualKey
, class _Alloc
>
105 struct _Hashtable_iterator
107 typedef hashtable
<_Val
, _Key
, _HashFcn
, _ExtractKey
, _EqualKey
, _Alloc
>
109 typedef _Hashtable_iterator
<_Val
, _Key
, _HashFcn
,
110 _ExtractKey
, _EqualKey
, _Alloc
>
112 typedef _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
,
113 _ExtractKey
, _EqualKey
, _Alloc
>
115 typedef _Hashtable_node
<_Val
> _Node
;
116 typedef forward_iterator_tag iterator_category
;
117 typedef _Val value_type
;
118 typedef ptrdiff_t difference_type
;
119 typedef size_t size_type
;
120 typedef _Val
& reference
;
121 typedef _Val
* pointer
;
126 _Hashtable_iterator(_Node
* __n
, _Hashtable
* __tab
)
127 : _M_cur(__n
), _M_ht(__tab
) { }
129 _Hashtable_iterator() { }
133 { return _M_cur
->_M_val
; }
137 { return &(operator*()); }
146 operator==(const iterator
& __it
) const
147 { return _M_cur
== __it
._M_cur
; }
150 operator!=(const iterator
& __it
) const
151 { return _M_cur
!= __it
._M_cur
; }
154 template<class _Val
, class _Key
, class _HashFcn
,
155 class _ExtractKey
, class _EqualKey
, class _Alloc
>
156 struct _Hashtable_const_iterator
158 typedef hashtable
<_Val
, _Key
, _HashFcn
, _ExtractKey
, _EqualKey
, _Alloc
>
160 typedef _Hashtable_iterator
<_Val
,_Key
,_HashFcn
,
161 _ExtractKey
,_EqualKey
,_Alloc
>
163 typedef _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
,
164 _ExtractKey
, _EqualKey
, _Alloc
>
166 typedef _Hashtable_node
<_Val
> _Node
;
168 typedef forward_iterator_tag iterator_category
;
169 typedef _Val value_type
;
170 typedef ptrdiff_t difference_type
;
171 typedef size_t size_type
;
172 typedef const _Val
& reference
;
173 typedef const _Val
* pointer
;
176 const _Hashtable
* _M_ht
;
178 _Hashtable_const_iterator(const _Node
* __n
, const _Hashtable
* __tab
)
179 : _M_cur(__n
), _M_ht(__tab
) { }
181 _Hashtable_const_iterator() { }
183 _Hashtable_const_iterator(const iterator
& __it
)
184 : _M_cur(__it
._M_cur
), _M_ht(__it
._M_ht
) { }
188 { return _M_cur
->_M_val
; }
192 { return &(operator*()); }
201 operator==(const const_iterator
& __it
) const
202 { return _M_cur
== __it
._M_cur
; }
205 operator!=(const const_iterator
& __it
) const
206 { return _M_cur
!= __it
._M_cur
; }
209 // Note: assumes long is at least 32 bits.
210 enum { _S_num_primes
= 29 };
212 static const unsigned long __stl_prime_list
[_S_num_primes
] =
214 5ul, 53ul, 97ul, 193ul, 389ul,
215 769ul, 1543ul, 3079ul, 6151ul, 12289ul,
216 24593ul, 49157ul, 98317ul, 196613ul, 393241ul,
217 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul,
218 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul,
219 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
223 __stl_next_prime(unsigned long __n
)
225 const unsigned long* __first
= __stl_prime_list
;
226 const unsigned long* __last
= __stl_prime_list
+ (int)_S_num_primes
;
227 const unsigned long* pos
= std::lower_bound(__first
, __last
, __n
);
228 return pos
== __last
? *(__last
- 1) : *pos
;
231 // Forward declaration of operator==.
232 template<class _Val
, class _Key
, class _HF
, class _Ex
,
233 class _Eq
, class _All
>
236 template<class _Val
, class _Key
, class _HF
, class _Ex
,
237 class _Eq
, class _All
>
239 operator==(const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht1
,
240 const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht2
);
242 // Hashtables handle allocators a bit differently than other
243 // containers do. If we're using standard-conforming allocators, then
244 // a hashtable unconditionally has a member variable to hold its
245 // allocator, even if it so happens that all instances of the
246 // allocator type are identical. This is because, for hashtables,
247 // this extra storage is negligible. Additionally, a base class
248 // wouldn't serve any other purposes; it wouldn't, for example,
249 // simplify the exception-handling code.
250 template<class _Val
, class _Key
, class _HashFcn
,
251 class _ExtractKey
, class _EqualKey
, class _Alloc
>
255 typedef _Key key_type
;
256 typedef _Val value_type
;
257 typedef _HashFcn hasher
;
258 typedef _EqualKey key_equal
;
260 typedef size_t size_type
;
261 typedef ptrdiff_t difference_type
;
262 typedef value_type
* pointer
;
263 typedef const value_type
* const_pointer
;
264 typedef value_type
& reference
;
265 typedef const value_type
& const_reference
;
273 { return _M_equals
; }
276 typedef _Hashtable_node
<_Val
> _Node
;
279 typedef typename
_Alloc::template rebind
<value_type
>::other allocator_type
;
281 get_allocator() const
282 { return _M_node_allocator
; }
285 typedef typename
_Alloc::template rebind
<_Node
>::other _Node_Alloc
;
286 typedef typename
_Alloc::template rebind
<_Node
*>::other _Nodeptr_Alloc
;
287 typedef vector
<_Node
*, _Nodeptr_Alloc
> _Vector_type
;
289 _Node_Alloc _M_node_allocator
;
293 { return _M_node_allocator
.allocate(1); }
296 _M_put_node(_Node
* __p
)
297 { _M_node_allocator
.deallocate(__p
, 1); }
302 _ExtractKey _M_get_key
;
303 _Vector_type _M_buckets
;
304 size_type _M_num_elements
;
307 typedef _Hashtable_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
,
310 typedef _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
,
315 _Hashtable_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
, _EqualKey
, _Alloc
>;
318 _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
,
322 hashtable(size_type __n
, const _HashFcn
& __hf
,
323 const _EqualKey
& __eql
, const _ExtractKey
& __ext
,
324 const allocator_type
& __a
= allocator_type())
325 : _M_node_allocator(__a
), _M_hash(__hf
), _M_equals(__eql
),
326 _M_get_key(__ext
), _M_buckets(__a
), _M_num_elements(0)
327 { _M_initialize_buckets(__n
); }
329 hashtable(size_type __n
, const _HashFcn
& __hf
,
330 const _EqualKey
& __eql
,
331 const allocator_type
& __a
= allocator_type())
332 : _M_node_allocator(__a
), _M_hash(__hf
), _M_equals(__eql
),
333 _M_get_key(_ExtractKey()), _M_buckets(__a
), _M_num_elements(0)
334 { _M_initialize_buckets(__n
); }
336 hashtable(const hashtable
& __ht
)
337 : _M_node_allocator(__ht
.get_allocator()), _M_hash(__ht
._M_hash
),
338 _M_equals(__ht
._M_equals
), _M_get_key(__ht
._M_get_key
),
339 _M_buckets(__ht
.get_allocator()), _M_num_elements(0)
340 { _M_copy_from(__ht
); }
343 operator= (const hashtable
& __ht
)
348 _M_hash
= __ht
._M_hash
;
349 _M_equals
= __ht
._M_equals
;
350 _M_get_key
= __ht
._M_get_key
;
361 { return _M_num_elements
; }
365 { return size_type(-1); }
369 { return size() == 0; }
372 swap(hashtable
& __ht
)
374 std::swap(_M_hash
, __ht
._M_hash
);
375 std::swap(_M_equals
, __ht
._M_equals
);
376 std::swap(_M_get_key
, __ht
._M_get_key
);
377 _M_buckets
.swap(__ht
._M_buckets
);
378 std::swap(_M_num_elements
, __ht
._M_num_elements
);
384 for (size_type __n
= 0; __n
< _M_buckets
.size(); ++__n
)
386 return iterator(_M_buckets
[__n
], this);
392 { return iterator(0, this); }
397 for (size_type __n
= 0; __n
< _M_buckets
.size(); ++__n
)
399 return const_iterator(_M_buckets
[__n
], this);
405 { return const_iterator(0, this); }
407 template<class _Vl
, class _Ky
, class _HF
, class _Ex
, class _Eq
,
410 operator==(const hashtable
<_Vl
, _Ky
, _HF
, _Ex
, _Eq
, _Al
>&,
411 const hashtable
<_Vl
, _Ky
, _HF
, _Ex
, _Eq
, _Al
>&);
416 { return _M_buckets
.size(); }
419 max_bucket_count() const
420 { return __stl_prime_list
[(int)_S_num_primes
- 1]; }
423 elems_in_bucket(size_type __bucket
) const
425 size_type __result
= 0;
426 for (_Node
* __n
= _M_buckets
[__bucket
]; __n
; __n
= __n
->_M_next
)
432 insert_unique(const value_type
& __obj
)
434 resize(_M_num_elements
+ 1);
435 return insert_unique_noresize(__obj
);
439 insert_equal(const value_type
& __obj
)
441 resize(_M_num_elements
+ 1);
442 return insert_equal_noresize(__obj
);
446 insert_unique_noresize(const value_type
& __obj
);
449 insert_equal_noresize(const value_type
& __obj
);
451 template<class _InputIterator
>
453 insert_unique(_InputIterator __f
, _InputIterator __l
)
454 { insert_unique(__f
, __l
, __iterator_category(__f
)); }
456 template<class _InputIterator
>
458 insert_equal(_InputIterator __f
, _InputIterator __l
)
459 { insert_equal(__f
, __l
, __iterator_category(__f
)); }
461 template<class _InputIterator
>
463 insert_unique(_InputIterator __f
, _InputIterator __l
,
466 for ( ; __f
!= __l
; ++__f
)
470 template<class _InputIterator
>
472 insert_equal(_InputIterator __f
, _InputIterator __l
,
475 for ( ; __f
!= __l
; ++__f
)
479 template<class _ForwardIterator
>
481 insert_unique(_ForwardIterator __f
, _ForwardIterator __l
,
482 forward_iterator_tag
)
484 size_type __n
= distance(__f
, __l
);
485 resize(_M_num_elements
+ __n
);
486 for ( ; __n
> 0; --__n
, ++__f
)
487 insert_unique_noresize(*__f
);
490 template<class _ForwardIterator
>
492 insert_equal(_ForwardIterator __f
, _ForwardIterator __l
,
493 forward_iterator_tag
)
495 size_type __n
= distance(__f
, __l
);
496 resize(_M_num_elements
+ __n
);
497 for ( ; __n
> 0; --__n
, ++__f
)
498 insert_equal_noresize(*__f
);
502 find_or_insert(const value_type
& __obj
);
505 find(const key_type
& __key
)
507 size_type __n
= _M_bkt_num_key(__key
);
509 for (__first
= _M_buckets
[__n
];
510 __first
&& !_M_equals(_M_get_key(__first
->_M_val
), __key
);
511 __first
= __first
->_M_next
)
513 return iterator(__first
, this);
517 find(const key_type
& __key
) const
519 size_type __n
= _M_bkt_num_key(__key
);
520 const _Node
* __first
;
521 for (__first
= _M_buckets
[__n
];
522 __first
&& !_M_equals(_M_get_key(__first
->_M_val
), __key
);
523 __first
= __first
->_M_next
)
525 return const_iterator(__first
, this);
529 count(const key_type
& __key
) const
531 const size_type __n
= _M_bkt_num_key(__key
);
532 size_type __result
= 0;
534 for (const _Node
* __cur
= _M_buckets
[__n
]; __cur
;
535 __cur
= __cur
->_M_next
)
536 if (_M_equals(_M_get_key(__cur
->_M_val
), __key
))
541 pair
<iterator
, iterator
>
542 equal_range(const key_type
& __key
);
544 pair
<const_iterator
, const_iterator
>
545 equal_range(const key_type
& __key
) const;
548 erase(const key_type
& __key
);
551 erase(const iterator
& __it
);
554 erase(iterator __first
, iterator __last
);
557 erase(const const_iterator
& __it
);
560 erase(const_iterator __first
, const_iterator __last
);
563 resize(size_type __num_elements_hint
);
570 _M_next_size(size_type __n
) const
571 { return __stl_next_prime(__n
); }
574 _M_initialize_buckets(size_type __n
)
576 const size_type __n_buckets
= _M_next_size(__n
);
577 _M_buckets
.reserve(__n_buckets
);
578 _M_buckets
.insert(_M_buckets
.end(), __n_buckets
, (_Node
*) 0);
583 _M_bkt_num_key(const key_type
& __key
) const
584 { return _M_bkt_num_key(__key
, _M_buckets
.size()); }
587 _M_bkt_num(const value_type
& __obj
) const
588 { return _M_bkt_num_key(_M_get_key(__obj
)); }
591 _M_bkt_num_key(const key_type
& __key
, size_t __n
) const
592 { return _M_hash(__key
) % __n
; }
595 _M_bkt_num(const value_type
& __obj
, size_t __n
) const
596 { return _M_bkt_num_key(_M_get_key(__obj
), __n
); }
599 _M_new_node(const value_type
& __obj
)
601 _Node
* __n
= _M_get_node();
605 this->get_allocator().construct(&__n
->_M_val
, __obj
);
611 __throw_exception_again
;
616 _M_delete_node(_Node
* __n
)
618 this->get_allocator().destroy(&__n
->_M_val
);
623 _M_erase_bucket(const size_type __n
, _Node
* __first
, _Node
* __last
);
626 _M_erase_bucket(const size_type __n
, _Node
* __last
);
629 _M_copy_from(const hashtable
& __ht
);
632 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
634 _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>&
635 _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
638 const _Node
* __old
= _M_cur
;
639 _M_cur
= _M_cur
->_M_next
;
642 size_type __bucket
= _M_ht
->_M_bkt_num(__old
->_M_val
);
643 while (!_M_cur
&& ++__bucket
< _M_ht
->_M_buckets
.size())
644 _M_cur
= _M_ht
->_M_buckets
[__bucket
];
649 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
651 inline _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>
652 _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
655 iterator __tmp
= *this;
660 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
662 _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>&
663 _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
666 const _Node
* __old
= _M_cur
;
667 _M_cur
= _M_cur
->_M_next
;
670 size_type __bucket
= _M_ht
->_M_bkt_num(__old
->_M_val
);
671 while (!_M_cur
&& ++__bucket
< _M_ht
->_M_buckets
.size())
672 _M_cur
= _M_ht
->_M_buckets
[__bucket
];
677 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
679 inline _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>
680 _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
683 const_iterator __tmp
= *this;
688 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
690 operator==(const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht1
,
691 const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht2
)
693 typedef typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::_Node _Node
;
695 if (__ht1
._M_buckets
.size() != __ht2
._M_buckets
.size())
698 for (size_t __n
= 0; __n
< __ht1
._M_buckets
.size(); ++__n
)
700 _Node
* __cur1
= __ht1
._M_buckets
[__n
];
701 _Node
* __cur2
= __ht2
._M_buckets
[__n
];
702 // Check same length of lists
703 for (; __cur1
&& __cur2
;
704 __cur1
= __cur1
->_M_next
, __cur2
= __cur2
->_M_next
)
706 if (__cur1
|| __cur2
)
708 // Now check one's elements are in the other
709 for (__cur1
= __ht1
._M_buckets
[__n
] ; __cur1
;
710 __cur1
= __cur1
->_M_next
)
712 bool _found__cur1
= false;
713 for (__cur2
= __ht2
._M_buckets
[__n
];
714 __cur2
; __cur2
= __cur2
->_M_next
)
716 if (__cur1
->_M_val
== __cur2
->_M_val
)
729 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
731 operator!=(const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht1
,
732 const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht2
)
733 { return !(__ht1
== __ht2
); }
735 template<class _Val
, class _Key
, class _HF
, class _Extract
, class _EqKey
,
738 swap(hashtable
<_Val
, _Key
, _HF
, _Extract
, _EqKey
, _All
>& __ht1
,
739 hashtable
<_Val
, _Key
, _HF
, _Extract
, _EqKey
, _All
>& __ht2
)
740 { __ht1
.swap(__ht2
); }
742 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
743 pair
<typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
, bool>
744 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
745 insert_unique_noresize(const value_type
& __obj
)
747 const size_type __n
= _M_bkt_num(__obj
);
748 _Node
* __first
= _M_buckets
[__n
];
750 for (_Node
* __cur
= __first
; __cur
; __cur
= __cur
->_M_next
)
751 if (_M_equals(_M_get_key(__cur
->_M_val
), _M_get_key(__obj
)))
752 return pair
<iterator
, bool>(iterator(__cur
, this), false);
754 _Node
* __tmp
= _M_new_node(__obj
);
755 __tmp
->_M_next
= __first
;
756 _M_buckets
[__n
] = __tmp
;
758 return pair
<iterator
, bool>(iterator(__tmp
, this), true);
761 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
762 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
763 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
764 insert_equal_noresize(const value_type
& __obj
)
766 const size_type __n
= _M_bkt_num(__obj
);
767 _Node
* __first
= _M_buckets
[__n
];
769 for (_Node
* __cur
= __first
; __cur
; __cur
= __cur
->_M_next
)
770 if (_M_equals(_M_get_key(__cur
->_M_val
), _M_get_key(__obj
)))
772 _Node
* __tmp
= _M_new_node(__obj
);
773 __tmp
->_M_next
= __cur
->_M_next
;
774 __cur
->_M_next
= __tmp
;
776 return iterator(__tmp
, this);
779 _Node
* __tmp
= _M_new_node(__obj
);
780 __tmp
->_M_next
= __first
;
781 _M_buckets
[__n
] = __tmp
;
783 return iterator(__tmp
, this);
786 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
787 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::reference
788 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
789 find_or_insert(const value_type
& __obj
)
791 resize(_M_num_elements
+ 1);
793 size_type __n
= _M_bkt_num(__obj
);
794 _Node
* __first
= _M_buckets
[__n
];
796 for (_Node
* __cur
= __first
; __cur
; __cur
= __cur
->_M_next
)
797 if (_M_equals(_M_get_key(__cur
->_M_val
), _M_get_key(__obj
)))
798 return __cur
->_M_val
;
800 _Node
* __tmp
= _M_new_node(__obj
);
801 __tmp
->_M_next
= __first
;
802 _M_buckets
[__n
] = __tmp
;
804 return __tmp
->_M_val
;
807 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
808 pair
<typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
,
809 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
>
810 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
811 equal_range(const key_type
& __key
)
813 typedef pair
<iterator
, iterator
> _Pii
;
814 const size_type __n
= _M_bkt_num_key(__key
);
816 for (_Node
* __first
= _M_buckets
[__n
]; __first
;
817 __first
= __first
->_M_next
)
818 if (_M_equals(_M_get_key(__first
->_M_val
), __key
))
820 for (_Node
* __cur
= __first
->_M_next
; __cur
;
821 __cur
= __cur
->_M_next
)
822 if (!_M_equals(_M_get_key(__cur
->_M_val
), __key
))
823 return _Pii(iterator(__first
, this), iterator(__cur
, this));
824 for (size_type __m
= __n
+ 1; __m
< _M_buckets
.size(); ++__m
)
826 return _Pii(iterator(__first
, this),
827 iterator(_M_buckets
[__m
], this));
828 return _Pii(iterator(__first
, this), end());
830 return _Pii(end(), end());
833 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
834 pair
<typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::const_iterator
,
835 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::const_iterator
>
836 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
837 equal_range(const key_type
& __key
) const
839 typedef pair
<const_iterator
, const_iterator
> _Pii
;
840 const size_type __n
= _M_bkt_num_key(__key
);
842 for (const _Node
* __first
= _M_buckets
[__n
]; __first
;
843 __first
= __first
->_M_next
)
845 if (_M_equals(_M_get_key(__first
->_M_val
), __key
))
847 for (const _Node
* __cur
= __first
->_M_next
; __cur
;
848 __cur
= __cur
->_M_next
)
849 if (!_M_equals(_M_get_key(__cur
->_M_val
), __key
))
850 return _Pii(const_iterator(__first
, this),
851 const_iterator(__cur
, this));
852 for (size_type __m
= __n
+ 1; __m
< _M_buckets
.size(); ++__m
)
854 return _Pii(const_iterator(__first
, this),
855 const_iterator(_M_buckets
[__m
], this));
856 return _Pii(const_iterator(__first
, this), end());
859 return _Pii(end(), end());
862 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
863 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::size_type
864 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
865 erase(const key_type
& __key
)
867 const size_type __n
= _M_bkt_num_key(__key
);
868 _Node
* __first
= _M_buckets
[__n
];
869 _Node
* __saved_slot
= 0;
870 size_type __erased
= 0;
874 _Node
* __cur
= __first
;
875 _Node
* __next
= __cur
->_M_next
;
878 if (_M_equals(_M_get_key(__next
->_M_val
), __key
))
880 if (&_M_get_key(__next
->_M_val
) != &__key
)
882 __cur
->_M_next
= __next
->_M_next
;
883 _M_delete_node(__next
);
884 __next
= __cur
->_M_next
;
890 __saved_slot
= __cur
;
892 __next
= __cur
->_M_next
;
898 __next
= __cur
->_M_next
;
901 bool __delete_first
= _M_equals(_M_get_key(__first
->_M_val
), __key
);
904 __next
= __saved_slot
->_M_next
;
905 __saved_slot
->_M_next
= __next
->_M_next
;
906 _M_delete_node(__next
);
912 _M_buckets
[__n
] = __first
->_M_next
;
913 _M_delete_node(__first
);
921 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
922 void hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
923 erase(const iterator
& __it
)
925 _Node
* __p
= __it
._M_cur
;
928 const size_type __n
= _M_bkt_num(__p
->_M_val
);
929 _Node
* __cur
= _M_buckets
[__n
];
933 _M_buckets
[__n
] = __cur
->_M_next
;
934 _M_delete_node(__cur
);
939 _Node
* __next
= __cur
->_M_next
;
944 __cur
->_M_next
= __next
->_M_next
;
945 _M_delete_node(__next
);
952 __next
= __cur
->_M_next
;
959 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
961 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
962 erase(iterator __first
, iterator __last
)
964 size_type __f_bucket
= __first
._M_cur
? _M_bkt_num(__first
._M_cur
->_M_val
)
967 size_type __l_bucket
= __last
._M_cur
? _M_bkt_num(__last
._M_cur
->_M_val
)
970 if (__first
._M_cur
== __last
._M_cur
)
972 else if (__f_bucket
== __l_bucket
)
973 _M_erase_bucket(__f_bucket
, __first
._M_cur
, __last
._M_cur
);
976 _M_erase_bucket(__f_bucket
, __first
._M_cur
, 0);
977 for (size_type __n
= __f_bucket
+ 1; __n
< __l_bucket
; ++__n
)
978 _M_erase_bucket(__n
, 0);
979 if (__l_bucket
!= _M_buckets
.size())
980 _M_erase_bucket(__l_bucket
, __last
._M_cur
);
984 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
986 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
987 erase(const_iterator __first
, const_iterator __last
)
989 erase(iterator(const_cast<_Node
*>(__first
._M_cur
),
990 const_cast<hashtable
*>(__first
._M_ht
)),
991 iterator(const_cast<_Node
*>(__last
._M_cur
),
992 const_cast<hashtable
*>(__last
._M_ht
)));
995 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
997 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
998 erase(const const_iterator
& __it
)
999 { erase(iterator(const_cast<_Node
*>(__it
._M_cur
),
1000 const_cast<hashtable
*>(__it
._M_ht
))); }
1002 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1004 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1005 resize(size_type __num_elements_hint
)
1007 const size_type __old_n
= _M_buckets
.size();
1008 if (__num_elements_hint
> __old_n
)
1010 const size_type __n
= _M_next_size(__num_elements_hint
);
1013 _Vector_type
__tmp(__n
, (_Node
*)(0), _M_buckets
.get_allocator());
1016 for (size_type __bucket
= 0; __bucket
< __old_n
; ++__bucket
)
1018 _Node
* __first
= _M_buckets
[__bucket
];
1021 size_type __new_bucket
= _M_bkt_num(__first
->_M_val
,
1023 _M_buckets
[__bucket
] = __first
->_M_next
;
1024 __first
->_M_next
= __tmp
[__new_bucket
];
1025 __tmp
[__new_bucket
] = __first
;
1026 __first
= _M_buckets
[__bucket
];
1029 _M_buckets
.swap(__tmp
);
1033 for (size_type __bucket
= 0; __bucket
< __tmp
.size();
1036 while (__tmp
[__bucket
])
1038 _Node
* __next
= __tmp
[__bucket
]->_M_next
;
1039 _M_delete_node(__tmp
[__bucket
]);
1040 __tmp
[__bucket
] = __next
;
1043 __throw_exception_again
;
1049 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1051 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1052 _M_erase_bucket(const size_type __n
, _Node
* __first
, _Node
* __last
)
1054 _Node
* __cur
= _M_buckets
[__n
];
1055 if (__cur
== __first
)
1056 _M_erase_bucket(__n
, __last
);
1060 for (__next
= __cur
->_M_next
;
1062 __cur
= __next
, __next
= __cur
->_M_next
)
1064 while (__next
!= __last
)
1066 __cur
->_M_next
= __next
->_M_next
;
1067 _M_delete_node(__next
);
1068 __next
= __cur
->_M_next
;
1074 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1076 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1077 _M_erase_bucket(const size_type __n
, _Node
* __last
)
1079 _Node
* __cur
= _M_buckets
[__n
];
1080 while (__cur
!= __last
)
1082 _Node
* __next
= __cur
->_M_next
;
1083 _M_delete_node(__cur
);
1085 _M_buckets
[__n
] = __cur
;
1090 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1092 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1095 if (_M_num_elements
== 0)
1098 for (size_type __i
= 0; __i
< _M_buckets
.size(); ++__i
)
1100 _Node
* __cur
= _M_buckets
[__i
];
1103 _Node
* __next
= __cur
->_M_next
;
1104 _M_delete_node(__cur
);
1107 _M_buckets
[__i
] = 0;
1109 _M_num_elements
= 0;
1112 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1114 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1115 _M_copy_from(const hashtable
& __ht
)
1118 _M_buckets
.reserve(__ht
._M_buckets
.size());
1119 _M_buckets
.insert(_M_buckets
.end(), __ht
._M_buckets
.size(), (_Node
*) 0);
1122 for (size_type __i
= 0; __i
< __ht
._M_buckets
.size(); ++__i
) {
1123 const _Node
* __cur
= __ht
._M_buckets
[__i
];
1126 _Node
* __local_copy
= _M_new_node(__cur
->_M_val
);
1127 _M_buckets
[__i
] = __local_copy
;
1129 for (_Node
* __next
= __cur
->_M_next
;
1131 __cur
= __next
, __next
= __cur
->_M_next
)
1133 __local_copy
->_M_next
= _M_new_node(__next
->_M_val
);
1134 __local_copy
= __local_copy
->_M_next
;
1138 _M_num_elements
= __ht
._M_num_elements
;
1143 __throw_exception_again
;
1147 _GLIBCXX_END_NAMESPACE_VERSION