1 // Hashtable implementation used by containers -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
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 2, 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 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
32 * Copyright (c) 1996,1997
33 * Silicon Graphics Computer Systems, Inc.
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Silicon Graphics makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
45 * Hewlett-Packard Company
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Hewlett-Packard Company makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
57 /** @file backward/hashtable.h
58 * This file is a GNU extension to the Standard C++ Library (possibly
59 * containing extensions from the HP/SGI STL subset).
63 #define _HASHTABLE_H 1
65 // Hashtable class, used to implement the hashed associative containers
66 // hash_set, hash_map, hash_multiset, and hash_multimap.
71 #include <bits/stl_function.h>
72 #include <backward/hash_fun.h>
74 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx
)
78 using std::forward_iterator_tag
;
79 using std::input_iterator_tag
;
80 using std::_Construct
;
85 using std::__iterator_category
;
88 struct _Hashtable_node
90 _Hashtable_node
* _M_next
;
94 template<class _Val
, class _Key
, class _HashFcn
, class _ExtractKey
,
95 class _EqualKey
, class _Alloc
= std::allocator
<_Val
> >
98 template<class _Val
, class _Key
, class _HashFcn
,
99 class _ExtractKey
, class _EqualKey
, class _Alloc
>
100 struct _Hashtable_iterator
;
102 template<class _Val
, class _Key
, class _HashFcn
,
103 class _ExtractKey
, class _EqualKey
, class _Alloc
>
104 struct _Hashtable_const_iterator
;
106 template<class _Val
, class _Key
, class _HashFcn
,
107 class _ExtractKey
, class _EqualKey
, class _Alloc
>
108 struct _Hashtable_iterator
110 typedef hashtable
<_Val
, _Key
, _HashFcn
, _ExtractKey
, _EqualKey
, _Alloc
>
112 typedef _Hashtable_iterator
<_Val
, _Key
, _HashFcn
,
113 _ExtractKey
, _EqualKey
, _Alloc
>
115 typedef _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
,
116 _ExtractKey
, _EqualKey
, _Alloc
>
118 typedef _Hashtable_node
<_Val
> _Node
;
119 typedef forward_iterator_tag iterator_category
;
120 typedef _Val value_type
;
121 typedef ptrdiff_t difference_type
;
122 typedef size_t size_type
;
123 typedef _Val
& reference
;
124 typedef _Val
* pointer
;
129 _Hashtable_iterator(_Node
* __n
, _Hashtable
* __tab
)
130 : _M_cur(__n
), _M_ht(__tab
) { }
132 _Hashtable_iterator() { }
136 { return _M_cur
->_M_val
; }
140 { return &(operator*()); }
149 operator==(const iterator
& __it
) const
150 { return _M_cur
== __it
._M_cur
; }
153 operator!=(const iterator
& __it
) const
154 { return _M_cur
!= __it
._M_cur
; }
157 template<class _Val
, class _Key
, class _HashFcn
,
158 class _ExtractKey
, class _EqualKey
, class _Alloc
>
159 struct _Hashtable_const_iterator
161 typedef hashtable
<_Val
, _Key
, _HashFcn
, _ExtractKey
, _EqualKey
, _Alloc
>
163 typedef _Hashtable_iterator
<_Val
,_Key
,_HashFcn
,
164 _ExtractKey
,_EqualKey
,_Alloc
>
166 typedef _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
,
167 _ExtractKey
, _EqualKey
, _Alloc
>
169 typedef _Hashtable_node
<_Val
> _Node
;
171 typedef forward_iterator_tag iterator_category
;
172 typedef _Val value_type
;
173 typedef ptrdiff_t difference_type
;
174 typedef size_t size_type
;
175 typedef const _Val
& reference
;
176 typedef const _Val
* pointer
;
179 const _Hashtable
* _M_ht
;
181 _Hashtable_const_iterator(const _Node
* __n
, const _Hashtable
* __tab
)
182 : _M_cur(__n
), _M_ht(__tab
) { }
184 _Hashtable_const_iterator() { }
186 _Hashtable_const_iterator(const iterator
& __it
)
187 : _M_cur(__it
._M_cur
), _M_ht(__it
._M_ht
) { }
191 { return _M_cur
->_M_val
; }
195 { return &(operator*()); }
204 operator==(const const_iterator
& __it
) const
205 { return _M_cur
== __it
._M_cur
; }
208 operator!=(const const_iterator
& __it
) const
209 { return _M_cur
!= __it
._M_cur
; }
212 // Note: assumes long is at least 32 bits.
213 enum { _S_num_primes
= 28 };
215 static const unsigned long __stl_prime_list
[_S_num_primes
] =
217 53ul, 97ul, 193ul, 389ul, 769ul,
218 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
219 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
220 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
221 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
222 1610612741ul, 3221225473ul, 4294967291ul
226 __stl_next_prime(unsigned long __n
)
228 const unsigned long* __first
= __stl_prime_list
;
229 const unsigned long* __last
= __stl_prime_list
+ (int)_S_num_primes
;
230 const unsigned long* pos
= std::lower_bound(__first
, __last
, __n
);
231 return pos
== __last
? *(__last
- 1) : *pos
;
234 // Forward declaration of operator==.
235 template<class _Val
, class _Key
, class _HF
, class _Ex
,
236 class _Eq
, class _All
>
239 template<class _Val
, class _Key
, class _HF
, class _Ex
,
240 class _Eq
, class _All
>
242 operator==(const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht1
,
243 const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht2
);
245 // Hashtables handle allocators a bit differently than other
246 // containers do. If we're using standard-conforming allocators, then
247 // a hashtable unconditionally has a member variable to hold its
248 // allocator, even if it so happens that all instances of the
249 // allocator type are identical. This is because, for hashtables,
250 // this extra storage is negligible. Additionally, a base class
251 // wouldn't serve any other purposes; it wouldn't, for example,
252 // simplify the exception-handling code.
253 template<class _Val
, class _Key
, class _HashFcn
,
254 class _ExtractKey
, class _EqualKey
, class _Alloc
>
258 typedef _Key key_type
;
259 typedef _Val value_type
;
260 typedef _HashFcn hasher
;
261 typedef _EqualKey key_equal
;
263 typedef size_t size_type
;
264 typedef ptrdiff_t difference_type
;
265 typedef value_type
* pointer
;
266 typedef const value_type
* const_pointer
;
267 typedef value_type
& reference
;
268 typedef const value_type
& const_reference
;
276 { return _M_equals
; }
279 typedef _Hashtable_node
<_Val
> _Node
;
282 typedef typename
_Alloc::template rebind
<value_type
>::other allocator_type
;
284 get_allocator() const
285 { return _M_node_allocator
; }
288 typedef typename
_Alloc::template rebind
<_Node
>::other _Node_Alloc
;
289 typedef typename
_Alloc::template rebind
<_Node
*>::other _Nodeptr_Alloc
;
290 typedef vector
<_Node
*, _Nodeptr_Alloc
> _Vector_type
;
292 _Node_Alloc _M_node_allocator
;
296 { return _M_node_allocator
.allocate(1); }
299 _M_put_node(_Node
* __p
)
300 { _M_node_allocator
.deallocate(__p
, 1); }
305 _ExtractKey _M_get_key
;
306 _Vector_type _M_buckets
;
307 size_type _M_num_elements
;
310 typedef _Hashtable_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
,
313 typedef _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
,
318 _Hashtable_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
, _EqualKey
, _Alloc
>;
321 _Hashtable_const_iterator
<_Val
, _Key
, _HashFcn
, _ExtractKey
,
325 hashtable(size_type __n
, const _HashFcn
& __hf
,
326 const _EqualKey
& __eql
, const _ExtractKey
& __ext
,
327 const allocator_type
& __a
= allocator_type())
328 : _M_node_allocator(__a
), _M_hash(__hf
), _M_equals(__eql
),
329 _M_get_key(__ext
), _M_buckets(__a
), _M_num_elements(0)
330 { _M_initialize_buckets(__n
); }
332 hashtable(size_type __n
, const _HashFcn
& __hf
,
333 const _EqualKey
& __eql
,
334 const allocator_type
& __a
= allocator_type())
335 : _M_node_allocator(__a
), _M_hash(__hf
), _M_equals(__eql
),
336 _M_get_key(_ExtractKey()), _M_buckets(__a
), _M_num_elements(0)
337 { _M_initialize_buckets(__n
); }
339 hashtable(const hashtable
& __ht
)
340 : _M_node_allocator(__ht
.get_allocator()), _M_hash(__ht
._M_hash
),
341 _M_equals(__ht
._M_equals
), _M_get_key(__ht
._M_get_key
),
342 _M_buckets(__ht
.get_allocator()), _M_num_elements(0)
343 { _M_copy_from(__ht
); }
346 operator= (const hashtable
& __ht
)
351 _M_hash
= __ht
._M_hash
;
352 _M_equals
= __ht
._M_equals
;
353 _M_get_key
= __ht
._M_get_key
;
364 { return _M_num_elements
; }
368 { return size_type(-1); }
372 { return size() == 0; }
375 swap(hashtable
& __ht
)
377 std::swap(_M_hash
, __ht
._M_hash
);
378 std::swap(_M_equals
, __ht
._M_equals
);
379 std::swap(_M_get_key
, __ht
._M_get_key
);
380 _M_buckets
.swap(__ht
._M_buckets
);
381 std::swap(_M_num_elements
, __ht
._M_num_elements
);
387 for (size_type __n
= 0; __n
< _M_buckets
.size(); ++__n
)
389 return iterator(_M_buckets
[__n
], this);
395 { return iterator(0, this); }
400 for (size_type __n
= 0; __n
< _M_buckets
.size(); ++__n
)
402 return const_iterator(_M_buckets
[__n
], this);
408 { return const_iterator(0, this); }
410 template<class _Vl
, class _Ky
, class _HF
, class _Ex
, class _Eq
,
413 operator==(const hashtable
<_Vl
, _Ky
, _HF
, _Ex
, _Eq
, _Al
>&,
414 const hashtable
<_Vl
, _Ky
, _HF
, _Ex
, _Eq
, _Al
>&);
419 { return _M_buckets
.size(); }
422 max_bucket_count() const
423 { return __stl_prime_list
[(int)_S_num_primes
- 1]; }
426 elems_in_bucket(size_type __bucket
) const
428 size_type __result
= 0;
429 for (_Node
* __n
= _M_buckets
[__bucket
]; __n
; __n
= __n
->_M_next
)
435 insert_unique(const value_type
& __obj
)
437 resize(_M_num_elements
+ 1);
438 return insert_unique_noresize(__obj
);
442 insert_equal(const value_type
& __obj
)
444 resize(_M_num_elements
+ 1);
445 return insert_equal_noresize(__obj
);
449 insert_unique_noresize(const value_type
& __obj
);
452 insert_equal_noresize(const value_type
& __obj
);
454 template<class _InputIterator
>
456 insert_unique(_InputIterator __f
, _InputIterator __l
)
457 { insert_unique(__f
, __l
, __iterator_category(__f
)); }
459 template<class _InputIterator
>
461 insert_equal(_InputIterator __f
, _InputIterator __l
)
462 { insert_equal(__f
, __l
, __iterator_category(__f
)); }
464 template<class _InputIterator
>
466 insert_unique(_InputIterator __f
, _InputIterator __l
,
469 for ( ; __f
!= __l
; ++__f
)
473 template<class _InputIterator
>
475 insert_equal(_InputIterator __f
, _InputIterator __l
,
478 for ( ; __f
!= __l
; ++__f
)
482 template<class _ForwardIterator
>
484 insert_unique(_ForwardIterator __f
, _ForwardIterator __l
,
485 forward_iterator_tag
)
487 size_type __n
= distance(__f
, __l
);
488 resize(_M_num_elements
+ __n
);
489 for ( ; __n
> 0; --__n
, ++__f
)
490 insert_unique_noresize(*__f
);
493 template<class _ForwardIterator
>
495 insert_equal(_ForwardIterator __f
, _ForwardIterator __l
,
496 forward_iterator_tag
)
498 size_type __n
= distance(__f
, __l
);
499 resize(_M_num_elements
+ __n
);
500 for ( ; __n
> 0; --__n
, ++__f
)
501 insert_equal_noresize(*__f
);
505 find_or_insert(const value_type
& __obj
);
508 find(const key_type
& __key
)
510 size_type __n
= _M_bkt_num_key(__key
);
512 for (__first
= _M_buckets
[__n
];
513 __first
&& !_M_equals(_M_get_key(__first
->_M_val
), __key
);
514 __first
= __first
->_M_next
)
516 return iterator(__first
, this);
520 find(const key_type
& __key
) const
522 size_type __n
= _M_bkt_num_key(__key
);
523 const _Node
* __first
;
524 for (__first
= _M_buckets
[__n
];
525 __first
&& !_M_equals(_M_get_key(__first
->_M_val
), __key
);
526 __first
= __first
->_M_next
)
528 return const_iterator(__first
, this);
532 count(const key_type
& __key
) const
534 const size_type __n
= _M_bkt_num_key(__key
);
535 size_type __result
= 0;
537 for (const _Node
* __cur
= _M_buckets
[__n
]; __cur
;
538 __cur
= __cur
->_M_next
)
539 if (_M_equals(_M_get_key(__cur
->_M_val
), __key
))
544 pair
<iterator
, iterator
>
545 equal_range(const key_type
& __key
);
547 pair
<const_iterator
, const_iterator
>
548 equal_range(const key_type
& __key
) const;
551 erase(const key_type
& __key
);
554 erase(const iterator
& __it
);
557 erase(iterator __first
, iterator __last
);
560 erase(const const_iterator
& __it
);
563 erase(const_iterator __first
, const_iterator __last
);
566 resize(size_type __num_elements_hint
);
573 _M_next_size(size_type __n
) const
574 { return __stl_next_prime(__n
); }
577 _M_initialize_buckets(size_type __n
)
579 const size_type __n_buckets
= _M_next_size(__n
);
580 _M_buckets
.reserve(__n_buckets
);
581 _M_buckets
.insert(_M_buckets
.end(), __n_buckets
, (_Node
*) 0);
586 _M_bkt_num_key(const key_type
& __key
) const
587 { return _M_bkt_num_key(__key
, _M_buckets
.size()); }
590 _M_bkt_num(const value_type
& __obj
) const
591 { return _M_bkt_num_key(_M_get_key(__obj
)); }
594 _M_bkt_num_key(const key_type
& __key
, size_t __n
) const
595 { return _M_hash(__key
) % __n
; }
598 _M_bkt_num(const value_type
& __obj
, size_t __n
) const
599 { return _M_bkt_num_key(_M_get_key(__obj
), __n
); }
602 _M_new_node(const value_type
& __obj
)
604 _Node
* __n
= _M_get_node();
608 this->get_allocator().construct(&__n
->_M_val
, __obj
);
614 __throw_exception_again
;
619 _M_delete_node(_Node
* __n
)
621 this->get_allocator().destroy(&__n
->_M_val
);
626 _M_erase_bucket(const size_type __n
, _Node
* __first
, _Node
* __last
);
629 _M_erase_bucket(const size_type __n
, _Node
* __last
);
632 _M_copy_from(const hashtable
& __ht
);
635 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
637 _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>&
638 _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
641 const _Node
* __old
= _M_cur
;
642 _M_cur
= _M_cur
->_M_next
;
645 size_type __bucket
= _M_ht
->_M_bkt_num(__old
->_M_val
);
646 while (!_M_cur
&& ++__bucket
< _M_ht
->_M_buckets
.size())
647 _M_cur
= _M_ht
->_M_buckets
[__bucket
];
652 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
654 inline _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>
655 _Hashtable_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
658 iterator __tmp
= *this;
663 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
665 _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>&
666 _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
669 const _Node
* __old
= _M_cur
;
670 _M_cur
= _M_cur
->_M_next
;
673 size_type __bucket
= _M_ht
->_M_bkt_num(__old
->_M_val
);
674 while (!_M_cur
&& ++__bucket
< _M_ht
->_M_buckets
.size())
675 _M_cur
= _M_ht
->_M_buckets
[__bucket
];
680 template<class _Val
, class _Key
, class _HF
, class _ExK
, class _EqK
,
682 inline _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>
683 _Hashtable_const_iterator
<_Val
, _Key
, _HF
, _ExK
, _EqK
, _All
>::
686 const_iterator __tmp
= *this;
691 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
693 operator==(const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht1
,
694 const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht2
)
696 typedef typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::_Node _Node
;
698 if (__ht1
._M_buckets
.size() != __ht2
._M_buckets
.size())
701 for (size_t __n
= 0; __n
< __ht1
._M_buckets
.size(); ++__n
)
703 _Node
* __cur1
= __ht1
._M_buckets
[__n
];
704 _Node
* __cur2
= __ht2
._M_buckets
[__n
];
705 // Check same length of lists
706 for (; __cur1
&& __cur2
;
707 __cur1
= __cur1
->_M_next
, __cur2
= __cur2
->_M_next
)
709 if (__cur1
|| __cur2
)
711 // Now check one's elements are in the other
712 for (__cur1
= __ht1
._M_buckets
[__n
] ; __cur1
;
713 __cur1
= __cur1
->_M_next
)
715 bool _found__cur1
= false;
716 for (__cur2
= __ht2
._M_buckets
[__n
];
717 __cur2
; __cur2
= __cur2
->_M_next
)
719 if (__cur1
->_M_val
== __cur2
->_M_val
)
732 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
734 operator!=(const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht1
,
735 const hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>& __ht2
)
736 { return !(__ht1
== __ht2
); }
738 template<class _Val
, class _Key
, class _HF
, class _Extract
, class _EqKey
,
741 swap(hashtable
<_Val
, _Key
, _HF
, _Extract
, _EqKey
, _All
>& __ht1
,
742 hashtable
<_Val
, _Key
, _HF
, _Extract
, _EqKey
, _All
>& __ht2
)
743 { __ht1
.swap(__ht2
); }
745 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
746 pair
<typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
, bool>
747 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
748 insert_unique_noresize(const value_type
& __obj
)
750 const size_type __n
= _M_bkt_num(__obj
);
751 _Node
* __first
= _M_buckets
[__n
];
753 for (_Node
* __cur
= __first
; __cur
; __cur
= __cur
->_M_next
)
754 if (_M_equals(_M_get_key(__cur
->_M_val
), _M_get_key(__obj
)))
755 return pair
<iterator
, bool>(iterator(__cur
, this), false);
757 _Node
* __tmp
= _M_new_node(__obj
);
758 __tmp
->_M_next
= __first
;
759 _M_buckets
[__n
] = __tmp
;
761 return pair
<iterator
, bool>(iterator(__tmp
, this), true);
764 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
765 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
766 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
767 insert_equal_noresize(const value_type
& __obj
)
769 const size_type __n
= _M_bkt_num(__obj
);
770 _Node
* __first
= _M_buckets
[__n
];
772 for (_Node
* __cur
= __first
; __cur
; __cur
= __cur
->_M_next
)
773 if (_M_equals(_M_get_key(__cur
->_M_val
), _M_get_key(__obj
)))
775 _Node
* __tmp
= _M_new_node(__obj
);
776 __tmp
->_M_next
= __cur
->_M_next
;
777 __cur
->_M_next
= __tmp
;
779 return iterator(__tmp
, this);
782 _Node
* __tmp
= _M_new_node(__obj
);
783 __tmp
->_M_next
= __first
;
784 _M_buckets
[__n
] = __tmp
;
786 return iterator(__tmp
, this);
789 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
790 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::reference
791 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
792 find_or_insert(const value_type
& __obj
)
794 resize(_M_num_elements
+ 1);
796 size_type __n
= _M_bkt_num(__obj
);
797 _Node
* __first
= _M_buckets
[__n
];
799 for (_Node
* __cur
= __first
; __cur
; __cur
= __cur
->_M_next
)
800 if (_M_equals(_M_get_key(__cur
->_M_val
), _M_get_key(__obj
)))
801 return __cur
->_M_val
;
803 _Node
* __tmp
= _M_new_node(__obj
);
804 __tmp
->_M_next
= __first
;
805 _M_buckets
[__n
] = __tmp
;
807 return __tmp
->_M_val
;
810 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
811 pair
<typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
,
812 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::iterator
>
813 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
814 equal_range(const key_type
& __key
)
816 typedef pair
<iterator
, iterator
> _Pii
;
817 const size_type __n
= _M_bkt_num_key(__key
);
819 for (_Node
* __first
= _M_buckets
[__n
]; __first
;
820 __first
= __first
->_M_next
)
821 if (_M_equals(_M_get_key(__first
->_M_val
), __key
))
823 for (_Node
* __cur
= __first
->_M_next
; __cur
;
824 __cur
= __cur
->_M_next
)
825 if (!_M_equals(_M_get_key(__cur
->_M_val
), __key
))
826 return _Pii(iterator(__first
, this), iterator(__cur
, this));
827 for (size_type __m
= __n
+ 1; __m
< _M_buckets
.size(); ++__m
)
829 return _Pii(iterator(__first
, this),
830 iterator(_M_buckets
[__m
], this));
831 return _Pii(iterator(__first
, this), end());
833 return _Pii(end(), end());
836 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
837 pair
<typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::const_iterator
,
838 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::const_iterator
>
839 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
840 equal_range(const key_type
& __key
) const
842 typedef pair
<const_iterator
, const_iterator
> _Pii
;
843 const size_type __n
= _M_bkt_num_key(__key
);
845 for (const _Node
* __first
= _M_buckets
[__n
]; __first
;
846 __first
= __first
->_M_next
)
848 if (_M_equals(_M_get_key(__first
->_M_val
), __key
))
850 for (const _Node
* __cur
= __first
->_M_next
; __cur
;
851 __cur
= __cur
->_M_next
)
852 if (!_M_equals(_M_get_key(__cur
->_M_val
), __key
))
853 return _Pii(const_iterator(__first
, this),
854 const_iterator(__cur
, this));
855 for (size_type __m
= __n
+ 1; __m
< _M_buckets
.size(); ++__m
)
857 return _Pii(const_iterator(__first
, this),
858 const_iterator(_M_buckets
[__m
], this));
859 return _Pii(const_iterator(__first
, this), end());
862 return _Pii(end(), end());
865 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
866 typename hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::size_type
867 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
868 erase(const key_type
& __key
)
870 const size_type __n
= _M_bkt_num_key(__key
);
871 _Node
* __first
= _M_buckets
[__n
];
872 size_type __erased
= 0;
876 _Node
* __cur
= __first
;
877 _Node
* __next
= __cur
->_M_next
;
880 if (_M_equals(_M_get_key(__next
->_M_val
), __key
))
882 __cur
->_M_next
= __next
->_M_next
;
883 _M_delete_node(__next
);
884 __next
= __cur
->_M_next
;
891 __next
= __cur
->_M_next
;
894 if (_M_equals(_M_get_key(__first
->_M_val
), __key
))
896 _M_buckets
[__n
] = __first
->_M_next
;
897 _M_delete_node(__first
);
905 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
906 void hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
907 erase(const iterator
& __it
)
909 _Node
* __p
= __it
._M_cur
;
912 const size_type __n
= _M_bkt_num(__p
->_M_val
);
913 _Node
* __cur
= _M_buckets
[__n
];
917 _M_buckets
[__n
] = __cur
->_M_next
;
918 _M_delete_node(__cur
);
923 _Node
* __next
= __cur
->_M_next
;
928 __cur
->_M_next
= __next
->_M_next
;
929 _M_delete_node(__next
);
936 __next
= __cur
->_M_next
;
943 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
945 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
946 erase(iterator __first
, iterator __last
)
948 size_type __f_bucket
= __first
._M_cur
? _M_bkt_num(__first
._M_cur
->_M_val
)
951 size_type __l_bucket
= __last
._M_cur
? _M_bkt_num(__last
._M_cur
->_M_val
)
954 if (__first
._M_cur
== __last
._M_cur
)
956 else if (__f_bucket
== __l_bucket
)
957 _M_erase_bucket(__f_bucket
, __first
._M_cur
, __last
._M_cur
);
960 _M_erase_bucket(__f_bucket
, __first
._M_cur
, 0);
961 for (size_type __n
= __f_bucket
+ 1; __n
< __l_bucket
; ++__n
)
962 _M_erase_bucket(__n
, 0);
963 if (__l_bucket
!= _M_buckets
.size())
964 _M_erase_bucket(__l_bucket
, __last
._M_cur
);
968 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
970 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
971 erase(const_iterator __first
, const_iterator __last
)
973 erase(iterator(const_cast<_Node
*>(__first
._M_cur
),
974 const_cast<hashtable
*>(__first
._M_ht
)),
975 iterator(const_cast<_Node
*>(__last
._M_cur
),
976 const_cast<hashtable
*>(__last
._M_ht
)));
979 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
981 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
982 erase(const const_iterator
& __it
)
983 { erase(iterator(const_cast<_Node
*>(__it
._M_cur
),
984 const_cast<hashtable
*>(__it
._M_ht
))); }
986 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
988 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
989 resize(size_type __num_elements_hint
)
991 const size_type __old_n
= _M_buckets
.size();
992 if (__num_elements_hint
> __old_n
)
994 const size_type __n
= _M_next_size(__num_elements_hint
);
997 _Vector_type
__tmp(__n
, (_Node
*)(0), _M_buckets
.get_allocator());
1000 for (size_type __bucket
= 0; __bucket
< __old_n
; ++__bucket
)
1002 _Node
* __first
= _M_buckets
[__bucket
];
1005 size_type __new_bucket
= _M_bkt_num(__first
->_M_val
,
1007 _M_buckets
[__bucket
] = __first
->_M_next
;
1008 __first
->_M_next
= __tmp
[__new_bucket
];
1009 __tmp
[__new_bucket
] = __first
;
1010 __first
= _M_buckets
[__bucket
];
1013 _M_buckets
.swap(__tmp
);
1017 for (size_type __bucket
= 0; __bucket
< __tmp
.size();
1020 while (__tmp
[__bucket
])
1022 _Node
* __next
= __tmp
[__bucket
]->_M_next
;
1023 _M_delete_node(__tmp
[__bucket
]);
1024 __tmp
[__bucket
] = __next
;
1027 __throw_exception_again
;
1033 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1035 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1036 _M_erase_bucket(const size_type __n
, _Node
* __first
, _Node
* __last
)
1038 _Node
* __cur
= _M_buckets
[__n
];
1039 if (__cur
== __first
)
1040 _M_erase_bucket(__n
, __last
);
1044 for (__next
= __cur
->_M_next
;
1046 __cur
= __next
, __next
= __cur
->_M_next
)
1048 while (__next
!= __last
)
1050 __cur
->_M_next
= __next
->_M_next
;
1051 _M_delete_node(__next
);
1052 __next
= __cur
->_M_next
;
1058 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1060 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1061 _M_erase_bucket(const size_type __n
, _Node
* __last
)
1063 _Node
* __cur
= _M_buckets
[__n
];
1064 while (__cur
!= __last
)
1066 _Node
* __next
= __cur
->_M_next
;
1067 _M_delete_node(__cur
);
1069 _M_buckets
[__n
] = __cur
;
1074 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1076 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1079 for (size_type __i
= 0; __i
< _M_buckets
.size(); ++__i
)
1081 _Node
* __cur
= _M_buckets
[__i
];
1084 _Node
* __next
= __cur
->_M_next
;
1085 _M_delete_node(__cur
);
1088 _M_buckets
[__i
] = 0;
1090 _M_num_elements
= 0;
1093 template<class _Val
, class _Key
, class _HF
, class _Ex
, class _Eq
, class _All
>
1095 hashtable
<_Val
, _Key
, _HF
, _Ex
, _Eq
, _All
>::
1096 _M_copy_from(const hashtable
& __ht
)
1099 _M_buckets
.reserve(__ht
._M_buckets
.size());
1100 _M_buckets
.insert(_M_buckets
.end(), __ht
._M_buckets
.size(), (_Node
*) 0);
1103 for (size_type __i
= 0; __i
< __ht
._M_buckets
.size(); ++__i
) {
1104 const _Node
* __cur
= __ht
._M_buckets
[__i
];
1107 _Node
* __local_copy
= _M_new_node(__cur
->_M_val
);
1108 _M_buckets
[__i
] = __local_copy
;
1110 for (_Node
* __next
= __cur
->_M_next
;
1112 __cur
= __next
, __next
= __cur
->_M_next
)
1114 __local_copy
->_M_next
= _M_new_node(__next
->_M_val
);
1115 __local_copy
= __local_copy
->_M_next
;
1119 _M_num_elements
= __ht
._M_num_elements
;
1124 __throw_exception_again
;
1128 _GLIBCXX_END_NAMESPACE