xref: /openbsd-src/gnu/gcc/libstdc++-v3/include/ext/hashtable.h (revision 404b540a9034ac75a6199ad1a32d1bbc7a0d4210)
1*404b540aSrobert // Hashtable implementation used by containers -*- C++ -*-
2*404b540aSrobert 
3*404b540aSrobert // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
4*404b540aSrobert // Free Software Foundation, Inc.
5*404b540aSrobert //
6*404b540aSrobert // This file is part of the GNU ISO C++ Library.  This library is free
7*404b540aSrobert // software; you can redistribute it and/or modify it under the
8*404b540aSrobert // terms of the GNU General Public License as published by the
9*404b540aSrobert // Free Software Foundation; either version 2, or (at your option)
10*404b540aSrobert // any later version.
11*404b540aSrobert 
12*404b540aSrobert // This library is distributed in the hope that it will be useful,
13*404b540aSrobert // but WITHOUT ANY WARRANTY; without even the implied warranty of
14*404b540aSrobert // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15*404b540aSrobert // GNU General Public License for more details.
16*404b540aSrobert 
17*404b540aSrobert // You should have received a copy of the GNU General Public License along
18*404b540aSrobert // with this library; see the file COPYING.  If not, write to the Free
19*404b540aSrobert // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20*404b540aSrobert // USA.
21*404b540aSrobert 
22*404b540aSrobert // As a special exception, you may use this file as part of a free software
23*404b540aSrobert // library without restriction.  Specifically, if other files instantiate
24*404b540aSrobert // templates or use macros or inline functions from this file, or you compile
25*404b540aSrobert // this file and link it with other files to produce an executable, this
26*404b540aSrobert // file does not by itself cause the resulting executable to be covered by
27*404b540aSrobert // the GNU General Public License.  This exception does not however
28*404b540aSrobert // invalidate any other reasons why the executable file might be covered by
29*404b540aSrobert // the GNU General Public License.
30*404b540aSrobert 
31*404b540aSrobert /*
32*404b540aSrobert  * Copyright (c) 1996,1997
33*404b540aSrobert  * Silicon Graphics Computer Systems, Inc.
34*404b540aSrobert  *
35*404b540aSrobert  * Permission to use, copy, modify, distribute and sell this software
36*404b540aSrobert  * and its documentation for any purpose is hereby granted without fee,
37*404b540aSrobert  * provided that the above copyright notice appear in all copies and
38*404b540aSrobert  * that both that copyright notice and this permission notice appear
39*404b540aSrobert  * in supporting documentation.  Silicon Graphics makes no
40*404b540aSrobert  * representations about the suitability of this software for any
41*404b540aSrobert  * purpose.  It is provided "as is" without express or implied warranty.
42*404b540aSrobert  *
43*404b540aSrobert  *
44*404b540aSrobert  * Copyright (c) 1994
45*404b540aSrobert  * Hewlett-Packard Company
46*404b540aSrobert  *
47*404b540aSrobert  * Permission to use, copy, modify, distribute and sell this software
48*404b540aSrobert  * and its documentation for any purpose is hereby granted without fee,
49*404b540aSrobert  * provided that the above copyright notice appear in all copies and
50*404b540aSrobert  * that both that copyright notice and this permission notice appear
51*404b540aSrobert  * in supporting documentation.  Hewlett-Packard Company makes no
52*404b540aSrobert  * representations about the suitability of this software for any
53*404b540aSrobert  * purpose.  It is provided "as is" without express or implied warranty.
54*404b540aSrobert  *
55*404b540aSrobert  */
56*404b540aSrobert 
57*404b540aSrobert /** @file ext/hashtable.h
58*404b540aSrobert  *  This file is a GNU extension to the Standard C++ Library (possibly
59*404b540aSrobert  *  containing extensions from the HP/SGI STL subset).
60*404b540aSrobert  */
61*404b540aSrobert 
62*404b540aSrobert #ifndef _HASHTABLE_H
63*404b540aSrobert #define _HASHTABLE_H 1
64*404b540aSrobert 
65*404b540aSrobert // Hashtable class, used to implement the hashed associative containers
66*404b540aSrobert // hash_set, hash_map, hash_multiset, and hash_multimap.
67*404b540aSrobert 
68*404b540aSrobert #include <vector>
69*404b540aSrobert #include <iterator>
70*404b540aSrobert #include <bits/stl_algo.h>
71*404b540aSrobert #include <bits/stl_function.h>
72*404b540aSrobert #include <ext/hash_fun.h>
73*404b540aSrobert 
74*404b540aSrobert _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
75*404b540aSrobert 
76*404b540aSrobert   using std::size_t;
77*404b540aSrobert   using std::ptrdiff_t;
78*404b540aSrobert   using std::forward_iterator_tag;
79*404b540aSrobert   using std::input_iterator_tag;
80*404b540aSrobert   using std::_Construct;
81*404b540aSrobert   using std::_Destroy;
82*404b540aSrobert   using std::distance;
83*404b540aSrobert   using std::vector;
84*404b540aSrobert   using std::pair;
85*404b540aSrobert   using std::__iterator_category;
86*404b540aSrobert 
87*404b540aSrobert   template<class _Val>
88*404b540aSrobert     struct _Hashtable_node
89*404b540aSrobert     {
90*404b540aSrobert       _Hashtable_node* _M_next;
91*404b540aSrobert       _Val _M_val;
92*404b540aSrobert     };
93*404b540aSrobert 
94*404b540aSrobert   template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
95*404b540aSrobert 	   class _EqualKey, class _Alloc = std::allocator<_Val> >
96*404b540aSrobert     class hashtable;
97*404b540aSrobert 
98*404b540aSrobert   template<class _Val, class _Key, class _HashFcn,
99*404b540aSrobert 	   class _ExtractKey, class _EqualKey, class _Alloc>
100*404b540aSrobert     struct _Hashtable_iterator;
101*404b540aSrobert 
102*404b540aSrobert   template<class _Val, class _Key, class _HashFcn,
103*404b540aSrobert 	   class _ExtractKey, class _EqualKey, class _Alloc>
104*404b540aSrobert     struct _Hashtable_const_iterator;
105*404b540aSrobert 
106*404b540aSrobert   template<class _Val, class _Key, class _HashFcn,
107*404b540aSrobert 	   class _ExtractKey, class _EqualKey, class _Alloc>
108*404b540aSrobert     struct _Hashtable_iterator
109*404b540aSrobert     {
110*404b540aSrobert       typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
111*404b540aSrobert         _Hashtable;
112*404b540aSrobert       typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
113*404b540aSrobert 				  _ExtractKey, _EqualKey, _Alloc>
114*404b540aSrobert         iterator;
115*404b540aSrobert       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
116*404b540aSrobert 					_ExtractKey, _EqualKey, _Alloc>
117*404b540aSrobert         const_iterator;
118*404b540aSrobert       typedef _Hashtable_node<_Val> _Node;
119*404b540aSrobert       typedef forward_iterator_tag iterator_category;
120*404b540aSrobert       typedef _Val value_type;
121*404b540aSrobert       typedef ptrdiff_t difference_type;
122*404b540aSrobert       typedef size_t size_type;
123*404b540aSrobert       typedef _Val& reference;
124*404b540aSrobert       typedef _Val* pointer;
125*404b540aSrobert 
126*404b540aSrobert       _Node* _M_cur;
127*404b540aSrobert       _Hashtable* _M_ht;
128*404b540aSrobert 
_Hashtable_iterator_Hashtable_iterator129*404b540aSrobert       _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
130*404b540aSrobert       : _M_cur(__n), _M_ht(__tab) { }
131*404b540aSrobert 
_Hashtable_iterator_Hashtable_iterator132*404b540aSrobert       _Hashtable_iterator() { }
133*404b540aSrobert 
134*404b540aSrobert       reference
135*404b540aSrobert       operator*() const
136*404b540aSrobert       { return _M_cur->_M_val; }
137*404b540aSrobert 
138*404b540aSrobert       pointer
139*404b540aSrobert       operator->() const
140*404b540aSrobert       { return &(operator*()); }
141*404b540aSrobert 
142*404b540aSrobert       iterator&
143*404b540aSrobert       operator++();
144*404b540aSrobert 
145*404b540aSrobert       iterator
146*404b540aSrobert       operator++(int);
147*404b540aSrobert 
148*404b540aSrobert       bool
149*404b540aSrobert       operator==(const iterator& __it) const
150*404b540aSrobert       { return _M_cur == __it._M_cur; }
151*404b540aSrobert 
152*404b540aSrobert       bool
153*404b540aSrobert       operator!=(const iterator& __it) const
154*404b540aSrobert       { return _M_cur != __it._M_cur; }
155*404b540aSrobert     };
156*404b540aSrobert 
157*404b540aSrobert   template<class _Val, class _Key, class _HashFcn,
158*404b540aSrobert 	   class _ExtractKey, class _EqualKey, class _Alloc>
159*404b540aSrobert     struct _Hashtable_const_iterator
160*404b540aSrobert     {
161*404b540aSrobert       typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
162*404b540aSrobert         _Hashtable;
163*404b540aSrobert       typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
164*404b540aSrobert 				  _ExtractKey,_EqualKey,_Alloc>
165*404b540aSrobert         iterator;
166*404b540aSrobert       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
167*404b540aSrobert 					_ExtractKey, _EqualKey, _Alloc>
168*404b540aSrobert         const_iterator;
169*404b540aSrobert       typedef _Hashtable_node<_Val> _Node;
170*404b540aSrobert 
171*404b540aSrobert       typedef forward_iterator_tag iterator_category;
172*404b540aSrobert       typedef _Val value_type;
173*404b540aSrobert       typedef ptrdiff_t difference_type;
174*404b540aSrobert       typedef size_t size_type;
175*404b540aSrobert       typedef const _Val& reference;
176*404b540aSrobert       typedef const _Val* pointer;
177*404b540aSrobert 
178*404b540aSrobert       const _Node* _M_cur;
179*404b540aSrobert       const _Hashtable* _M_ht;
180*404b540aSrobert 
_Hashtable_const_iterator_Hashtable_const_iterator181*404b540aSrobert       _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
182*404b540aSrobert       : _M_cur(__n), _M_ht(__tab) { }
183*404b540aSrobert 
_Hashtable_const_iterator_Hashtable_const_iterator184*404b540aSrobert       _Hashtable_const_iterator() { }
185*404b540aSrobert 
_Hashtable_const_iterator_Hashtable_const_iterator186*404b540aSrobert       _Hashtable_const_iterator(const iterator& __it)
187*404b540aSrobert       : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
188*404b540aSrobert 
189*404b540aSrobert       reference
190*404b540aSrobert       operator*() const
191*404b540aSrobert       { return _M_cur->_M_val; }
192*404b540aSrobert 
193*404b540aSrobert       pointer
194*404b540aSrobert       operator->() const
195*404b540aSrobert       { return &(operator*()); }
196*404b540aSrobert 
197*404b540aSrobert       const_iterator&
198*404b540aSrobert       operator++();
199*404b540aSrobert 
200*404b540aSrobert       const_iterator
201*404b540aSrobert       operator++(int);
202*404b540aSrobert 
203*404b540aSrobert       bool
204*404b540aSrobert       operator==(const const_iterator& __it) const
205*404b540aSrobert       { return _M_cur == __it._M_cur; }
206*404b540aSrobert 
207*404b540aSrobert       bool
208*404b540aSrobert       operator!=(const const_iterator& __it) const
209*404b540aSrobert       { return _M_cur != __it._M_cur; }
210*404b540aSrobert     };
211*404b540aSrobert 
212*404b540aSrobert   // Note: assumes long is at least 32 bits.
213*404b540aSrobert   enum { _S_num_primes = 28 };
214*404b540aSrobert 
215*404b540aSrobert   static const unsigned long __stl_prime_list[_S_num_primes] =
216*404b540aSrobert     {
217*404b540aSrobert       53ul,         97ul,         193ul,       389ul,       769ul,
218*404b540aSrobert       1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
219*404b540aSrobert       49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
220*404b540aSrobert       1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
221*404b540aSrobert       50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
222*404b540aSrobert       1610612741ul, 3221225473ul, 4294967291ul
223*404b540aSrobert     };
224*404b540aSrobert 
225*404b540aSrobert   inline unsigned long
__stl_next_prime(unsigned long __n)226*404b540aSrobert   __stl_next_prime(unsigned long __n)
227*404b540aSrobert   {
228*404b540aSrobert     const unsigned long* __first = __stl_prime_list;
229*404b540aSrobert     const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
230*404b540aSrobert     const unsigned long* pos = std::lower_bound(__first, __last, __n);
231*404b540aSrobert     return pos == __last ? *(__last - 1) : *pos;
232*404b540aSrobert   }
233*404b540aSrobert 
234*404b540aSrobert   // Forward declaration of operator==.
235*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex,
236*404b540aSrobert 	   class _Eq, class _All>
237*404b540aSrobert     class hashtable;
238*404b540aSrobert 
239*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex,
240*404b540aSrobert 	   class _Eq, class _All>
241*404b540aSrobert     bool
242*404b540aSrobert     operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
243*404b540aSrobert 	       const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
244*404b540aSrobert 
245*404b540aSrobert   // Hashtables handle allocators a bit differently than other
246*404b540aSrobert   // containers do.  If we're using standard-conforming allocators, then
247*404b540aSrobert   // a hashtable unconditionally has a member variable to hold its
248*404b540aSrobert   // allocator, even if it so happens that all instances of the
249*404b540aSrobert   // allocator type are identical.  This is because, for hashtables,
250*404b540aSrobert   // this extra storage is negligible.  Additionally, a base class
251*404b540aSrobert   // wouldn't serve any other purposes; it wouldn't, for example,
252*404b540aSrobert   // simplify the exception-handling code.
253*404b540aSrobert   template<class _Val, class _Key, class _HashFcn,
254*404b540aSrobert 	   class _ExtractKey, class _EqualKey, class _Alloc>
255*404b540aSrobert     class hashtable
256*404b540aSrobert     {
257*404b540aSrobert     public:
258*404b540aSrobert       typedef _Key key_type;
259*404b540aSrobert       typedef _Val value_type;
260*404b540aSrobert       typedef _HashFcn hasher;
261*404b540aSrobert       typedef _EqualKey key_equal;
262*404b540aSrobert 
263*404b540aSrobert       typedef size_t            size_type;
264*404b540aSrobert       typedef ptrdiff_t         difference_type;
265*404b540aSrobert       typedef value_type*       pointer;
266*404b540aSrobert       typedef const value_type* const_pointer;
267*404b540aSrobert       typedef value_type&       reference;
268*404b540aSrobert       typedef const value_type& const_reference;
269*404b540aSrobert 
270*404b540aSrobert       hasher
hash_funct()271*404b540aSrobert       hash_funct() const
272*404b540aSrobert       { return _M_hash; }
273*404b540aSrobert 
274*404b540aSrobert       key_equal
key_eq()275*404b540aSrobert       key_eq() const
276*404b540aSrobert       { return _M_equals; }
277*404b540aSrobert 
278*404b540aSrobert     private:
279*404b540aSrobert       typedef _Hashtable_node<_Val> _Node;
280*404b540aSrobert 
281*404b540aSrobert     public:
282*404b540aSrobert       typedef typename _Alloc::template rebind<value_type>::other allocator_type;
283*404b540aSrobert       allocator_type
get_allocator()284*404b540aSrobert       get_allocator() const
285*404b540aSrobert       { return _M_node_allocator; }
286*404b540aSrobert 
287*404b540aSrobert     private:
288*404b540aSrobert       typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
289*404b540aSrobert       typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
290*404b540aSrobert       typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type;
291*404b540aSrobert 
292*404b540aSrobert       _Node_Alloc _M_node_allocator;
293*404b540aSrobert 
294*404b540aSrobert       _Node*
_M_get_node()295*404b540aSrobert       _M_get_node()
296*404b540aSrobert       { return _M_node_allocator.allocate(1); }
297*404b540aSrobert 
298*404b540aSrobert       void
_M_put_node(_Node * __p)299*404b540aSrobert       _M_put_node(_Node* __p)
300*404b540aSrobert       { _M_node_allocator.deallocate(__p, 1); }
301*404b540aSrobert 
302*404b540aSrobert     private:
303*404b540aSrobert       hasher                _M_hash;
304*404b540aSrobert       key_equal             _M_equals;
305*404b540aSrobert       _ExtractKey           _M_get_key;
306*404b540aSrobert       _Vector_type          _M_buckets;
307*404b540aSrobert       size_type             _M_num_elements;
308*404b540aSrobert 
309*404b540aSrobert     public:
310*404b540aSrobert       typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
311*404b540aSrobert 				  _EqualKey, _Alloc>
312*404b540aSrobert         iterator;
313*404b540aSrobert       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
314*404b540aSrobert 					_EqualKey, _Alloc>
315*404b540aSrobert         const_iterator;
316*404b540aSrobert 
317*404b540aSrobert       friend struct
318*404b540aSrobert       _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
319*404b540aSrobert 
320*404b540aSrobert       friend struct
321*404b540aSrobert       _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
322*404b540aSrobert 				_EqualKey, _Alloc>;
323*404b540aSrobert 
324*404b540aSrobert     public:
325*404b540aSrobert       hashtable(size_type __n, const _HashFcn& __hf,
326*404b540aSrobert 		const _EqualKey& __eql, const _ExtractKey& __ext,
327*404b540aSrobert 		const allocator_type& __a = allocator_type())
328*404b540aSrobert       : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
329*404b540aSrobert 	_M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
330*404b540aSrobert       { _M_initialize_buckets(__n); }
331*404b540aSrobert 
332*404b540aSrobert       hashtable(size_type __n, const _HashFcn& __hf,
333*404b540aSrobert 		const _EqualKey& __eql,
334*404b540aSrobert 		const allocator_type& __a = allocator_type())
335*404b540aSrobert       : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
336*404b540aSrobert 	_M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
337*404b540aSrobert       { _M_initialize_buckets(__n); }
338*404b540aSrobert 
339*404b540aSrobert       hashtable(const hashtable& __ht)
340*404b540aSrobert       : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
341*404b540aSrobert       _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
342*404b540aSrobert       _M_buckets(__ht.get_allocator()), _M_num_elements(0)
343*404b540aSrobert       { _M_copy_from(__ht); }
344*404b540aSrobert 
345*404b540aSrobert       hashtable&
346*404b540aSrobert       operator= (const hashtable& __ht)
347*404b540aSrobert       {
348*404b540aSrobert 	if (&__ht != this)
349*404b540aSrobert 	  {
350*404b540aSrobert 	    clear();
351*404b540aSrobert 	    _M_hash = __ht._M_hash;
352*404b540aSrobert 	    _M_equals = __ht._M_equals;
353*404b540aSrobert 	    _M_get_key = __ht._M_get_key;
354*404b540aSrobert 	    _M_copy_from(__ht);
355*404b540aSrobert 	  }
356*404b540aSrobert 	return *this;
357*404b540aSrobert       }
358*404b540aSrobert 
359*404b540aSrobert       ~hashtable()
360*404b540aSrobert       { clear(); }
361*404b540aSrobert 
362*404b540aSrobert       size_type
363*404b540aSrobert       size() const
364*404b540aSrobert       { return _M_num_elements; }
365*404b540aSrobert 
366*404b540aSrobert       size_type
367*404b540aSrobert       max_size() const
368*404b540aSrobert       { return size_type(-1); }
369*404b540aSrobert 
370*404b540aSrobert       bool
371*404b540aSrobert       empty() const
372*404b540aSrobert       { return size() == 0; }
373*404b540aSrobert 
374*404b540aSrobert       void
375*404b540aSrobert       swap(hashtable& __ht)
376*404b540aSrobert       {
377*404b540aSrobert 	std::swap(_M_hash, __ht._M_hash);
378*404b540aSrobert 	std::swap(_M_equals, __ht._M_equals);
379*404b540aSrobert 	std::swap(_M_get_key, __ht._M_get_key);
380*404b540aSrobert 	_M_buckets.swap(__ht._M_buckets);
381*404b540aSrobert 	std::swap(_M_num_elements, __ht._M_num_elements);
382*404b540aSrobert       }
383*404b540aSrobert 
384*404b540aSrobert       iterator
385*404b540aSrobert       begin()
386*404b540aSrobert       {
387*404b540aSrobert 	for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
388*404b540aSrobert 	  if (_M_buckets[__n])
389*404b540aSrobert 	    return iterator(_M_buckets[__n], this);
390*404b540aSrobert 	return end();
391*404b540aSrobert       }
392*404b540aSrobert 
393*404b540aSrobert       iterator
394*404b540aSrobert       end()
395*404b540aSrobert       { return iterator(0, this); }
396*404b540aSrobert 
397*404b540aSrobert       const_iterator
398*404b540aSrobert       begin() const
399*404b540aSrobert       {
400*404b540aSrobert 	for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
401*404b540aSrobert 	  if (_M_buckets[__n])
402*404b540aSrobert 	    return const_iterator(_M_buckets[__n], this);
403*404b540aSrobert 	return end();
404*404b540aSrobert       }
405*404b540aSrobert 
406*404b540aSrobert       const_iterator
407*404b540aSrobert       end() const
408*404b540aSrobert       { return const_iterator(0, this); }
409*404b540aSrobert 
410*404b540aSrobert       template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq,
411*404b540aSrobert 		class _Al>
412*404b540aSrobert         friend bool
413*404b540aSrobert         operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
414*404b540aSrobert 		   const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
415*404b540aSrobert 
416*404b540aSrobert     public:
417*404b540aSrobert       size_type
418*404b540aSrobert       bucket_count() const
419*404b540aSrobert       { return _M_buckets.size(); }
420*404b540aSrobert 
421*404b540aSrobert       size_type
422*404b540aSrobert       max_bucket_count() const
423*404b540aSrobert       { return __stl_prime_list[(int)_S_num_primes - 1]; }
424*404b540aSrobert 
425*404b540aSrobert       size_type
426*404b540aSrobert       elems_in_bucket(size_type __bucket) const
427*404b540aSrobert       {
428*404b540aSrobert 	size_type __result = 0;
429*404b540aSrobert 	for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
430*404b540aSrobert 	  __result += 1;
431*404b540aSrobert 	return __result;
432*404b540aSrobert       }
433*404b540aSrobert 
434*404b540aSrobert       pair<iterator, bool>
435*404b540aSrobert       insert_unique(const value_type& __obj)
436*404b540aSrobert       {
437*404b540aSrobert 	resize(_M_num_elements + 1);
438*404b540aSrobert 	return insert_unique_noresize(__obj);
439*404b540aSrobert       }
440*404b540aSrobert 
441*404b540aSrobert       iterator
442*404b540aSrobert       insert_equal(const value_type& __obj)
443*404b540aSrobert       {
444*404b540aSrobert 	resize(_M_num_elements + 1);
445*404b540aSrobert 	return insert_equal_noresize(__obj);
446*404b540aSrobert       }
447*404b540aSrobert 
448*404b540aSrobert       pair<iterator, bool>
449*404b540aSrobert       insert_unique_noresize(const value_type& __obj);
450*404b540aSrobert 
451*404b540aSrobert       iterator
452*404b540aSrobert       insert_equal_noresize(const value_type& __obj);
453*404b540aSrobert 
454*404b540aSrobert       template<class _InputIterator>
455*404b540aSrobert         void
456*404b540aSrobert         insert_unique(_InputIterator __f, _InputIterator __l)
457*404b540aSrobert         { insert_unique(__f, __l, __iterator_category(__f)); }
458*404b540aSrobert 
459*404b540aSrobert       template<class _InputIterator>
460*404b540aSrobert         void
461*404b540aSrobert         insert_equal(_InputIterator __f, _InputIterator __l)
462*404b540aSrobert         { insert_equal(__f, __l, __iterator_category(__f)); }
463*404b540aSrobert 
464*404b540aSrobert       template<class _InputIterator>
465*404b540aSrobert         void
466*404b540aSrobert         insert_unique(_InputIterator __f, _InputIterator __l,
467*404b540aSrobert 		      input_iterator_tag)
468*404b540aSrobert         {
469*404b540aSrobert 	  for ( ; __f != __l; ++__f)
470*404b540aSrobert 	    insert_unique(*__f);
471*404b540aSrobert 	}
472*404b540aSrobert 
473*404b540aSrobert       template<class _InputIterator>
474*404b540aSrobert         void
475*404b540aSrobert         insert_equal(_InputIterator __f, _InputIterator __l,
476*404b540aSrobert 		     input_iterator_tag)
477*404b540aSrobert         {
478*404b540aSrobert 	  for ( ; __f != __l; ++__f)
479*404b540aSrobert 	    insert_equal(*__f);
480*404b540aSrobert 	}
481*404b540aSrobert 
482*404b540aSrobert       template<class _ForwardIterator>
483*404b540aSrobert         void
484*404b540aSrobert         insert_unique(_ForwardIterator __f, _ForwardIterator __l,
485*404b540aSrobert 		      forward_iterator_tag)
486*404b540aSrobert         {
487*404b540aSrobert 	  size_type __n = distance(__f, __l);
488*404b540aSrobert 	  resize(_M_num_elements + __n);
489*404b540aSrobert 	  for ( ; __n > 0; --__n, ++__f)
490*404b540aSrobert 	    insert_unique_noresize(*__f);
491*404b540aSrobert 	}
492*404b540aSrobert 
493*404b540aSrobert       template<class _ForwardIterator>
494*404b540aSrobert         void
495*404b540aSrobert         insert_equal(_ForwardIterator __f, _ForwardIterator __l,
496*404b540aSrobert 		     forward_iterator_tag)
497*404b540aSrobert         {
498*404b540aSrobert 	  size_type __n = distance(__f, __l);
499*404b540aSrobert 	  resize(_M_num_elements + __n);
500*404b540aSrobert 	  for ( ; __n > 0; --__n, ++__f)
501*404b540aSrobert 	    insert_equal_noresize(*__f);
502*404b540aSrobert 	}
503*404b540aSrobert 
504*404b540aSrobert       reference
505*404b540aSrobert       find_or_insert(const value_type& __obj);
506*404b540aSrobert 
507*404b540aSrobert       iterator
508*404b540aSrobert       find(const key_type& __key)
509*404b540aSrobert       {
510*404b540aSrobert 	size_type __n = _M_bkt_num_key(__key);
511*404b540aSrobert 	_Node* __first;
512*404b540aSrobert 	for (__first = _M_buckets[__n];
513*404b540aSrobert 	     __first && !_M_equals(_M_get_key(__first->_M_val), __key);
514*404b540aSrobert 	     __first = __first->_M_next)
515*404b540aSrobert 	  { }
516*404b540aSrobert 	return iterator(__first, this);
517*404b540aSrobert       }
518*404b540aSrobert 
519*404b540aSrobert       const_iterator
520*404b540aSrobert       find(const key_type& __key) const
521*404b540aSrobert       {
522*404b540aSrobert 	size_type __n = _M_bkt_num_key(__key);
523*404b540aSrobert 	const _Node* __first;
524*404b540aSrobert 	for (__first = _M_buckets[__n];
525*404b540aSrobert 	     __first && !_M_equals(_M_get_key(__first->_M_val), __key);
526*404b540aSrobert 	     __first = __first->_M_next)
527*404b540aSrobert 	  { }
528*404b540aSrobert 	return const_iterator(__first, this);
529*404b540aSrobert       }
530*404b540aSrobert 
531*404b540aSrobert       size_type
532*404b540aSrobert       count(const key_type& __key) const
533*404b540aSrobert       {
534*404b540aSrobert 	const size_type __n = _M_bkt_num_key(__key);
535*404b540aSrobert 	size_type __result = 0;
536*404b540aSrobert 
537*404b540aSrobert 	for (const _Node* __cur = _M_buckets[__n]; __cur;
538*404b540aSrobert 	     __cur = __cur->_M_next)
539*404b540aSrobert 	  if (_M_equals(_M_get_key(__cur->_M_val), __key))
540*404b540aSrobert 	    ++__result;
541*404b540aSrobert 	return __result;
542*404b540aSrobert       }
543*404b540aSrobert 
544*404b540aSrobert       pair<iterator, iterator>
545*404b540aSrobert       equal_range(const key_type& __key);
546*404b540aSrobert 
547*404b540aSrobert       pair<const_iterator, const_iterator>
548*404b540aSrobert       equal_range(const key_type& __key) const;
549*404b540aSrobert 
550*404b540aSrobert       size_type
551*404b540aSrobert       erase(const key_type& __key);
552*404b540aSrobert 
553*404b540aSrobert       void
554*404b540aSrobert       erase(const iterator& __it);
555*404b540aSrobert 
556*404b540aSrobert       void
557*404b540aSrobert       erase(iterator __first, iterator __last);
558*404b540aSrobert 
559*404b540aSrobert       void
560*404b540aSrobert       erase(const const_iterator& __it);
561*404b540aSrobert 
562*404b540aSrobert       void
563*404b540aSrobert       erase(const_iterator __first, const_iterator __last);
564*404b540aSrobert 
565*404b540aSrobert       void
566*404b540aSrobert       resize(size_type __num_elements_hint);
567*404b540aSrobert 
568*404b540aSrobert       void
569*404b540aSrobert       clear();
570*404b540aSrobert 
571*404b540aSrobert     private:
572*404b540aSrobert       size_type
573*404b540aSrobert       _M_next_size(size_type __n) const
574*404b540aSrobert       { return __stl_next_prime(__n); }
575*404b540aSrobert 
576*404b540aSrobert       void
577*404b540aSrobert       _M_initialize_buckets(size_type __n)
578*404b540aSrobert       {
579*404b540aSrobert 	const size_type __n_buckets = _M_next_size(__n);
580*404b540aSrobert 	_M_buckets.reserve(__n_buckets);
581*404b540aSrobert 	_M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
582*404b540aSrobert 	_M_num_elements = 0;
583*404b540aSrobert       }
584*404b540aSrobert 
585*404b540aSrobert       size_type
586*404b540aSrobert       _M_bkt_num_key(const key_type& __key) const
587*404b540aSrobert       { return _M_bkt_num_key(__key, _M_buckets.size()); }
588*404b540aSrobert 
589*404b540aSrobert       size_type
590*404b540aSrobert       _M_bkt_num(const value_type& __obj) const
591*404b540aSrobert       { return _M_bkt_num_key(_M_get_key(__obj)); }
592*404b540aSrobert 
593*404b540aSrobert       size_type
594*404b540aSrobert       _M_bkt_num_key(const key_type& __key, size_t __n) const
595*404b540aSrobert       { return _M_hash(__key) % __n; }
596*404b540aSrobert 
597*404b540aSrobert       size_type
598*404b540aSrobert       _M_bkt_num(const value_type& __obj, size_t __n) const
599*404b540aSrobert       { return _M_bkt_num_key(_M_get_key(__obj), __n); }
600*404b540aSrobert 
601*404b540aSrobert       _Node*
602*404b540aSrobert       _M_new_node(const value_type& __obj)
603*404b540aSrobert       {
604*404b540aSrobert 	_Node* __n = _M_get_node();
605*404b540aSrobert 	__n->_M_next = 0;
606*404b540aSrobert 	try
607*404b540aSrobert 	  {
608*404b540aSrobert 	    this->get_allocator().construct(&__n->_M_val, __obj);
609*404b540aSrobert 	    return __n;
610*404b540aSrobert 	  }
611*404b540aSrobert 	catch(...)
612*404b540aSrobert 	  {
613*404b540aSrobert 	    _M_put_node(__n);
614*404b540aSrobert 	    __throw_exception_again;
615*404b540aSrobert 	  }
616*404b540aSrobert       }
617*404b540aSrobert 
618*404b540aSrobert       void
619*404b540aSrobert       _M_delete_node(_Node* __n)
620*404b540aSrobert       {
621*404b540aSrobert 	this->get_allocator().destroy(&__n->_M_val);
622*404b540aSrobert 	_M_put_node(__n);
623*404b540aSrobert       }
624*404b540aSrobert 
625*404b540aSrobert       void
626*404b540aSrobert       _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
627*404b540aSrobert 
628*404b540aSrobert       void
629*404b540aSrobert       _M_erase_bucket(const size_type __n, _Node* __last);
630*404b540aSrobert 
631*404b540aSrobert       void
632*404b540aSrobert       _M_copy_from(const hashtable& __ht);
633*404b540aSrobert     };
634*404b540aSrobert 
635*404b540aSrobert   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
636*404b540aSrobert 	    class _All>
637*404b540aSrobert     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
638*404b540aSrobert     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
639*404b540aSrobert     operator++()
640*404b540aSrobert     {
641*404b540aSrobert       const _Node* __old = _M_cur;
642*404b540aSrobert       _M_cur = _M_cur->_M_next;
643*404b540aSrobert       if (!_M_cur)
644*404b540aSrobert 	{
645*404b540aSrobert 	  size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
646*404b540aSrobert 	  while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
647*404b540aSrobert 	    _M_cur = _M_ht->_M_buckets[__bucket];
648*404b540aSrobert 	}
649*404b540aSrobert       return *this;
650*404b540aSrobert     }
651*404b540aSrobert 
652*404b540aSrobert   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
653*404b540aSrobert 	    class _All>
654*404b540aSrobert     inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
655*404b540aSrobert     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
656*404b540aSrobert     operator++(int)
657*404b540aSrobert     {
658*404b540aSrobert       iterator __tmp = *this;
659*404b540aSrobert       ++*this;
660*404b540aSrobert       return __tmp;
661*404b540aSrobert     }
662*404b540aSrobert 
663*404b540aSrobert   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
664*404b540aSrobert 	    class _All>
665*404b540aSrobert     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
666*404b540aSrobert     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
667*404b540aSrobert     operator++()
668*404b540aSrobert     {
669*404b540aSrobert       const _Node* __old = _M_cur;
670*404b540aSrobert       _M_cur = _M_cur->_M_next;
671*404b540aSrobert       if (!_M_cur)
672*404b540aSrobert 	{
673*404b540aSrobert 	  size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
674*404b540aSrobert 	  while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
675*404b540aSrobert 	    _M_cur = _M_ht->_M_buckets[__bucket];
676*404b540aSrobert 	}
677*404b540aSrobert       return *this;
678*404b540aSrobert     }
679*404b540aSrobert 
680*404b540aSrobert   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
681*404b540aSrobert 	    class _All>
682*404b540aSrobert     inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
683*404b540aSrobert     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
684*404b540aSrobert     operator++(int)
685*404b540aSrobert     {
686*404b540aSrobert       const_iterator __tmp = *this;
687*404b540aSrobert       ++*this;
688*404b540aSrobert       return __tmp;
689*404b540aSrobert     }
690*404b540aSrobert 
691*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
692*404b540aSrobert     bool
693*404b540aSrobert     operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
694*404b540aSrobert 	       const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
695*404b540aSrobert     {
696*404b540aSrobert       typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
697*404b540aSrobert 
698*404b540aSrobert       if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
699*404b540aSrobert 	return false;
700*404b540aSrobert 
701*404b540aSrobert       for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
702*404b540aSrobert 	{
703*404b540aSrobert 	  _Node* __cur1 = __ht1._M_buckets[__n];
704*404b540aSrobert 	  _Node* __cur2 = __ht2._M_buckets[__n];
705*404b540aSrobert 	  // Check same length of lists
706*404b540aSrobert 	  for (; __cur1 && __cur2;
707*404b540aSrobert 	       __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
708*404b540aSrobert 	    { }
709*404b540aSrobert 	  if (__cur1 || __cur2)
710*404b540aSrobert 	    return false;
711*404b540aSrobert 	  // Now check one's elements are in the other
712*404b540aSrobert 	  for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
713*404b540aSrobert 	       __cur1 = __cur1->_M_next)
714*404b540aSrobert 	    {
715*404b540aSrobert 	      bool _found__cur1 = false;
716*404b540aSrobert 	      for (__cur2 = __ht2._M_buckets[__n];
717*404b540aSrobert 		   __cur2; __cur2 = __cur2->_M_next)
718*404b540aSrobert 		{
719*404b540aSrobert 		  if (__cur1->_M_val == __cur2->_M_val)
720*404b540aSrobert 		    {
721*404b540aSrobert 		      _found__cur1 = true;
722*404b540aSrobert 		      break;
723*404b540aSrobert 		    }
724*404b540aSrobert 		}
725*404b540aSrobert 	      if (!_found__cur1)
726*404b540aSrobert 		return false;
727*404b540aSrobert 	    }
728*404b540aSrobert 	}
729*404b540aSrobert       return true;
730*404b540aSrobert     }
731*404b540aSrobert 
732*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
733*404b540aSrobert     inline bool
734*404b540aSrobert     operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
735*404b540aSrobert 	       const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
736*404b540aSrobert     { return !(__ht1 == __ht2); }
737*404b540aSrobert 
738*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Extract, class _EqKey,
739*404b540aSrobert 	    class _All>
740*404b540aSrobert     inline void
741*404b540aSrobert     swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
742*404b540aSrobert 	 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
743*404b540aSrobert     { __ht1.swap(__ht2); }
744*404b540aSrobert 
745*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
746*404b540aSrobert     pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
747*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
748*404b540aSrobert     insert_unique_noresize(const value_type& __obj)
749*404b540aSrobert     {
750*404b540aSrobert       const size_type __n = _M_bkt_num(__obj);
751*404b540aSrobert       _Node* __first = _M_buckets[__n];
752*404b540aSrobert 
753*404b540aSrobert       for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
754*404b540aSrobert 	if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
755*404b540aSrobert 	  return pair<iterator, bool>(iterator(__cur, this), false);
756*404b540aSrobert 
757*404b540aSrobert       _Node* __tmp = _M_new_node(__obj);
758*404b540aSrobert       __tmp->_M_next = __first;
759*404b540aSrobert       _M_buckets[__n] = __tmp;
760*404b540aSrobert       ++_M_num_elements;
761*404b540aSrobert       return pair<iterator, bool>(iterator(__tmp, this), true);
762*404b540aSrobert     }
763*404b540aSrobert 
764*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
765*404b540aSrobert     typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
766*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
767*404b540aSrobert     insert_equal_noresize(const value_type& __obj)
768*404b540aSrobert     {
769*404b540aSrobert       const size_type __n = _M_bkt_num(__obj);
770*404b540aSrobert       _Node* __first = _M_buckets[__n];
771*404b540aSrobert 
772*404b540aSrobert       for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
773*404b540aSrobert 	if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
774*404b540aSrobert 	  {
775*404b540aSrobert 	    _Node* __tmp = _M_new_node(__obj);
776*404b540aSrobert 	    __tmp->_M_next = __cur->_M_next;
777*404b540aSrobert 	    __cur->_M_next = __tmp;
778*404b540aSrobert 	    ++_M_num_elements;
779*404b540aSrobert 	    return iterator(__tmp, this);
780*404b540aSrobert 	  }
781*404b540aSrobert 
782*404b540aSrobert       _Node* __tmp = _M_new_node(__obj);
783*404b540aSrobert       __tmp->_M_next = __first;
784*404b540aSrobert       _M_buckets[__n] = __tmp;
785*404b540aSrobert       ++_M_num_elements;
786*404b540aSrobert       return iterator(__tmp, this);
787*404b540aSrobert     }
788*404b540aSrobert 
789*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
790*404b540aSrobert     typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
791*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
792*404b540aSrobert     find_or_insert(const value_type& __obj)
793*404b540aSrobert     {
794*404b540aSrobert       resize(_M_num_elements + 1);
795*404b540aSrobert 
796*404b540aSrobert       size_type __n = _M_bkt_num(__obj);
797*404b540aSrobert       _Node* __first = _M_buckets[__n];
798*404b540aSrobert 
799*404b540aSrobert       for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
800*404b540aSrobert 	if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
801*404b540aSrobert 	  return __cur->_M_val;
802*404b540aSrobert 
803*404b540aSrobert       _Node* __tmp = _M_new_node(__obj);
804*404b540aSrobert       __tmp->_M_next = __first;
805*404b540aSrobert       _M_buckets[__n] = __tmp;
806*404b540aSrobert       ++_M_num_elements;
807*404b540aSrobert       return __tmp->_M_val;
808*404b540aSrobert     }
809*404b540aSrobert 
810*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
811*404b540aSrobert     pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
812*404b540aSrobert 	 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
813*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
814*404b540aSrobert     equal_range(const key_type& __key)
815*404b540aSrobert     {
816*404b540aSrobert       typedef pair<iterator, iterator> _Pii;
817*404b540aSrobert       const size_type __n = _M_bkt_num_key(__key);
818*404b540aSrobert 
819*404b540aSrobert       for (_Node* __first = _M_buckets[__n]; __first;
820*404b540aSrobert 	   __first = __first->_M_next)
821*404b540aSrobert 	if (_M_equals(_M_get_key(__first->_M_val), __key))
822*404b540aSrobert 	  {
823*404b540aSrobert 	    for (_Node* __cur = __first->_M_next; __cur;
824*404b540aSrobert 		 __cur = __cur->_M_next)
825*404b540aSrobert 	      if (!_M_equals(_M_get_key(__cur->_M_val), __key))
826*404b540aSrobert 		return _Pii(iterator(__first, this), iterator(__cur, this));
827*404b540aSrobert 	    for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
828*404b540aSrobert 	      if (_M_buckets[__m])
829*404b540aSrobert 		return _Pii(iterator(__first, this),
830*404b540aSrobert 			    iterator(_M_buckets[__m], this));
831*404b540aSrobert 	    return _Pii(iterator(__first, this), end());
832*404b540aSrobert 	  }
833*404b540aSrobert       return _Pii(end(), end());
834*404b540aSrobert     }
835*404b540aSrobert 
836*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
837*404b540aSrobert     pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
838*404b540aSrobert 	 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
839*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
840*404b540aSrobert     equal_range(const key_type& __key) const
841*404b540aSrobert     {
842*404b540aSrobert       typedef pair<const_iterator, const_iterator> _Pii;
843*404b540aSrobert       const size_type __n = _M_bkt_num_key(__key);
844*404b540aSrobert 
845*404b540aSrobert       for (const _Node* __first = _M_buckets[__n]; __first;
846*404b540aSrobert 	   __first = __first->_M_next)
847*404b540aSrobert 	{
848*404b540aSrobert 	  if (_M_equals(_M_get_key(__first->_M_val), __key))
849*404b540aSrobert 	    {
850*404b540aSrobert 	      for (const _Node* __cur = __first->_M_next; __cur;
851*404b540aSrobert 		   __cur = __cur->_M_next)
852*404b540aSrobert 		if (!_M_equals(_M_get_key(__cur->_M_val), __key))
853*404b540aSrobert 		  return _Pii(const_iterator(__first, this),
854*404b540aSrobert 			      const_iterator(__cur, this));
855*404b540aSrobert 	      for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
856*404b540aSrobert 		if (_M_buckets[__m])
857*404b540aSrobert 		  return _Pii(const_iterator(__first, this),
858*404b540aSrobert 			      const_iterator(_M_buckets[__m], this));
859*404b540aSrobert 	      return _Pii(const_iterator(__first, this), end());
860*404b540aSrobert 	    }
861*404b540aSrobert 	}
862*404b540aSrobert       return _Pii(end(), end());
863*404b540aSrobert     }
864*404b540aSrobert 
865*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
866*404b540aSrobert     typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
867*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
868*404b540aSrobert     erase(const key_type& __key)
869*404b540aSrobert     {
870*404b540aSrobert       const size_type __n = _M_bkt_num_key(__key);
871*404b540aSrobert       _Node* __first = _M_buckets[__n];
872*404b540aSrobert       size_type __erased = 0;
873*404b540aSrobert 
874*404b540aSrobert       if (__first)
875*404b540aSrobert 	{
876*404b540aSrobert 	  _Node* __cur = __first;
877*404b540aSrobert 	  _Node* __next = __cur->_M_next;
878*404b540aSrobert 	  while (__next)
879*404b540aSrobert 	    {
880*404b540aSrobert 	      if (_M_equals(_M_get_key(__next->_M_val), __key))
881*404b540aSrobert 		{
882*404b540aSrobert 		  __cur->_M_next = __next->_M_next;
883*404b540aSrobert 		  _M_delete_node(__next);
884*404b540aSrobert 		  __next = __cur->_M_next;
885*404b540aSrobert 		  ++__erased;
886*404b540aSrobert 		  --_M_num_elements;
887*404b540aSrobert 		}
888*404b540aSrobert 	      else
889*404b540aSrobert 		{
890*404b540aSrobert 		  __cur = __next;
891*404b540aSrobert 		  __next = __cur->_M_next;
892*404b540aSrobert 		}
893*404b540aSrobert 	    }
894*404b540aSrobert 	  if (_M_equals(_M_get_key(__first->_M_val), __key))
895*404b540aSrobert 	    {
896*404b540aSrobert 	      _M_buckets[__n] = __first->_M_next;
897*404b540aSrobert 	      _M_delete_node(__first);
898*404b540aSrobert 	      ++__erased;
899*404b540aSrobert 	      --_M_num_elements;
900*404b540aSrobert 	    }
901*404b540aSrobert 	}
902*404b540aSrobert       return __erased;
903*404b540aSrobert     }
904*404b540aSrobert 
905*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
906*404b540aSrobert     void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
907*404b540aSrobert     erase(const iterator& __it)
908*404b540aSrobert     {
909*404b540aSrobert       _Node* __p = __it._M_cur;
910*404b540aSrobert       if (__p)
911*404b540aSrobert 	{
912*404b540aSrobert 	  const size_type __n = _M_bkt_num(__p->_M_val);
913*404b540aSrobert 	  _Node* __cur = _M_buckets[__n];
914*404b540aSrobert 
915*404b540aSrobert 	  if (__cur == __p)
916*404b540aSrobert 	    {
917*404b540aSrobert 	      _M_buckets[__n] = __cur->_M_next;
918*404b540aSrobert 	      _M_delete_node(__cur);
919*404b540aSrobert 	      --_M_num_elements;
920*404b540aSrobert 	    }
921*404b540aSrobert 	  else
922*404b540aSrobert 	    {
923*404b540aSrobert 	      _Node* __next = __cur->_M_next;
924*404b540aSrobert 	      while (__next)
925*404b540aSrobert 		{
926*404b540aSrobert 		  if (__next == __p)
927*404b540aSrobert 		    {
928*404b540aSrobert 		      __cur->_M_next = __next->_M_next;
929*404b540aSrobert 		      _M_delete_node(__next);
930*404b540aSrobert 		      --_M_num_elements;
931*404b540aSrobert 		      break;
932*404b540aSrobert 		    }
933*404b540aSrobert 		  else
934*404b540aSrobert 		    {
935*404b540aSrobert 		      __cur = __next;
936*404b540aSrobert 		      __next = __cur->_M_next;
937*404b540aSrobert 		    }
938*404b540aSrobert 		}
939*404b540aSrobert 	    }
940*404b540aSrobert 	}
941*404b540aSrobert     }
942*404b540aSrobert 
943*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
944*404b540aSrobert     void
945*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
946*404b540aSrobert     erase(iterator __first, iterator __last)
947*404b540aSrobert     {
948*404b540aSrobert       size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
949*404b540aSrobert 	                                    : _M_buckets.size();
950*404b540aSrobert 
951*404b540aSrobert       size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
952*404b540aSrobert 	                                   : _M_buckets.size();
953*404b540aSrobert 
954*404b540aSrobert       if (__first._M_cur == __last._M_cur)
955*404b540aSrobert 	return;
956*404b540aSrobert       else if (__f_bucket == __l_bucket)
957*404b540aSrobert 	_M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
958*404b540aSrobert       else
959*404b540aSrobert 	{
960*404b540aSrobert 	  _M_erase_bucket(__f_bucket, __first._M_cur, 0);
961*404b540aSrobert 	  for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
962*404b540aSrobert 	    _M_erase_bucket(__n, 0);
963*404b540aSrobert 	  if (__l_bucket != _M_buckets.size())
964*404b540aSrobert 	    _M_erase_bucket(__l_bucket, __last._M_cur);
965*404b540aSrobert 	}
966*404b540aSrobert     }
967*404b540aSrobert 
968*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
969*404b540aSrobert     inline void
970*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
971*404b540aSrobert     erase(const_iterator __first, const_iterator __last)
972*404b540aSrobert     {
973*404b540aSrobert       erase(iterator(const_cast<_Node*>(__first._M_cur),
974*404b540aSrobert 		     const_cast<hashtable*>(__first._M_ht)),
975*404b540aSrobert 	    iterator(const_cast<_Node*>(__last._M_cur),
976*404b540aSrobert 		     const_cast<hashtable*>(__last._M_ht)));
977*404b540aSrobert     }
978*404b540aSrobert 
979*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
980*404b540aSrobert     inline void
981*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
982*404b540aSrobert     erase(const const_iterator& __it)
983*404b540aSrobert     { erase(iterator(const_cast<_Node*>(__it._M_cur),
984*404b540aSrobert 		     const_cast<hashtable*>(__it._M_ht))); }
985*404b540aSrobert 
986*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
987*404b540aSrobert     void
988*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
989*404b540aSrobert     resize(size_type __num_elements_hint)
990*404b540aSrobert     {
991*404b540aSrobert       const size_type __old_n = _M_buckets.size();
992*404b540aSrobert       if (__num_elements_hint > __old_n)
993*404b540aSrobert 	{
994*404b540aSrobert 	  const size_type __n = _M_next_size(__num_elements_hint);
995*404b540aSrobert 	  if (__n > __old_n)
996*404b540aSrobert 	    {
997*404b540aSrobert 	      _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
998*404b540aSrobert 	      try
999*404b540aSrobert 		{
1000*404b540aSrobert 		  for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1001*404b540aSrobert 		    {
1002*404b540aSrobert 		      _Node* __first = _M_buckets[__bucket];
1003*404b540aSrobert 		      while (__first)
1004*404b540aSrobert 			{
1005*404b540aSrobert 			  size_type __new_bucket = _M_bkt_num(__first->_M_val,
1006*404b540aSrobert 							      __n);
1007*404b540aSrobert 			  _M_buckets[__bucket] = __first->_M_next;
1008*404b540aSrobert 			  __first->_M_next = __tmp[__new_bucket];
1009*404b540aSrobert 			  __tmp[__new_bucket] = __first;
1010*404b540aSrobert 			  __first = _M_buckets[__bucket];
1011*404b540aSrobert 			}
1012*404b540aSrobert 		    }
1013*404b540aSrobert 		  _M_buckets.swap(__tmp);
1014*404b540aSrobert 		}
1015*404b540aSrobert 	      catch(...)
1016*404b540aSrobert 		{
1017*404b540aSrobert 		  for (size_type __bucket = 0; __bucket < __tmp.size();
1018*404b540aSrobert 		       ++__bucket)
1019*404b540aSrobert 		    {
1020*404b540aSrobert 		      while (__tmp[__bucket])
1021*404b540aSrobert 			{
1022*404b540aSrobert 			  _Node* __next = __tmp[__bucket]->_M_next;
1023*404b540aSrobert 			  _M_delete_node(__tmp[__bucket]);
1024*404b540aSrobert 			  __tmp[__bucket] = __next;
1025*404b540aSrobert 			}
1026*404b540aSrobert 		    }
1027*404b540aSrobert 		  __throw_exception_again;
1028*404b540aSrobert 		}
1029*404b540aSrobert 	    }
1030*404b540aSrobert 	}
1031*404b540aSrobert     }
1032*404b540aSrobert 
1033*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1034*404b540aSrobert     void
1035*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1036*404b540aSrobert     _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1037*404b540aSrobert     {
1038*404b540aSrobert       _Node* __cur = _M_buckets[__n];
1039*404b540aSrobert       if (__cur == __first)
1040*404b540aSrobert 	_M_erase_bucket(__n, __last);
1041*404b540aSrobert       else
1042*404b540aSrobert 	{
1043*404b540aSrobert 	  _Node* __next;
1044*404b540aSrobert 	  for (__next = __cur->_M_next;
1045*404b540aSrobert 	       __next != __first;
1046*404b540aSrobert 	       __cur = __next, __next = __cur->_M_next)
1047*404b540aSrobert 	    ;
1048*404b540aSrobert 	  while (__next != __last)
1049*404b540aSrobert 	    {
1050*404b540aSrobert 	      __cur->_M_next = __next->_M_next;
1051*404b540aSrobert 	      _M_delete_node(__next);
1052*404b540aSrobert 	      __next = __cur->_M_next;
1053*404b540aSrobert 	      --_M_num_elements;
1054*404b540aSrobert 	    }
1055*404b540aSrobert 	}
1056*404b540aSrobert     }
1057*404b540aSrobert 
1058*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1059*404b540aSrobert     void
1060*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1061*404b540aSrobert     _M_erase_bucket(const size_type __n, _Node* __last)
1062*404b540aSrobert     {
1063*404b540aSrobert       _Node* __cur = _M_buckets[__n];
1064*404b540aSrobert       while (__cur != __last)
1065*404b540aSrobert 	{
1066*404b540aSrobert 	  _Node* __next = __cur->_M_next;
1067*404b540aSrobert 	  _M_delete_node(__cur);
1068*404b540aSrobert 	  __cur = __next;
1069*404b540aSrobert 	  _M_buckets[__n] = __cur;
1070*404b540aSrobert 	  --_M_num_elements;
1071*404b540aSrobert 	}
1072*404b540aSrobert     }
1073*404b540aSrobert 
1074*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1075*404b540aSrobert     void
1076*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1077*404b540aSrobert     clear()
1078*404b540aSrobert     {
1079*404b540aSrobert       for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1080*404b540aSrobert 	{
1081*404b540aSrobert 	  _Node* __cur = _M_buckets[__i];
1082*404b540aSrobert 	  while (__cur != 0)
1083*404b540aSrobert 	    {
1084*404b540aSrobert 	      _Node* __next = __cur->_M_next;
1085*404b540aSrobert 	      _M_delete_node(__cur);
1086*404b540aSrobert 	      __cur = __next;
1087*404b540aSrobert 	    }
1088*404b540aSrobert 	  _M_buckets[__i] = 0;
1089*404b540aSrobert 	}
1090*404b540aSrobert       _M_num_elements = 0;
1091*404b540aSrobert     }
1092*404b540aSrobert 
1093*404b540aSrobert   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1094*404b540aSrobert     void
1095*404b540aSrobert     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1096*404b540aSrobert     _M_copy_from(const hashtable& __ht)
1097*404b540aSrobert     {
1098*404b540aSrobert       _M_buckets.clear();
1099*404b540aSrobert       _M_buckets.reserve(__ht._M_buckets.size());
1100*404b540aSrobert       _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1101*404b540aSrobert       try
1102*404b540aSrobert 	{
1103*404b540aSrobert 	  for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1104*404b540aSrobert 	    const _Node* __cur = __ht._M_buckets[__i];
1105*404b540aSrobert 	    if (__cur)
1106*404b540aSrobert 	      {
1107*404b540aSrobert 		_Node* __local_copy = _M_new_node(__cur->_M_val);
1108*404b540aSrobert 		_M_buckets[__i] = __local_copy;
1109*404b540aSrobert 
1110*404b540aSrobert 		for (_Node* __next = __cur->_M_next;
1111*404b540aSrobert 		     __next;
1112*404b540aSrobert 		     __cur = __next, __next = __cur->_M_next)
1113*404b540aSrobert 		  {
1114*404b540aSrobert 		    __local_copy->_M_next = _M_new_node(__next->_M_val);
1115*404b540aSrobert 		    __local_copy = __local_copy->_M_next;
1116*404b540aSrobert 		  }
1117*404b540aSrobert 	      }
1118*404b540aSrobert 	  }
1119*404b540aSrobert 	  _M_num_elements = __ht._M_num_elements;
1120*404b540aSrobert 	}
1121*404b540aSrobert       catch(...)
1122*404b540aSrobert 	{
1123*404b540aSrobert 	  clear();
1124*404b540aSrobert 	  __throw_exception_again;
1125*404b540aSrobert 	}
1126*404b540aSrobert     }
1127*404b540aSrobert 
1128*404b540aSrobert _GLIBCXX_END_NAMESPACE
1129*404b540aSrobert 
1130*404b540aSrobert #endif
1131