OSDN Git Service

PR libstdc++/49060
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / backward / hashtable.h
1 // Hashtable implementation used by containers -*- C++ -*-
2
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
5 //
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)
10 // any later version.
11
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.
16
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.
20
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/>.
25
26 /*
27  * Copyright (c) 1996,1997
28  * Silicon Graphics Computer Systems, Inc.
29  *
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.
37  *
38  *
39  * Copyright (c) 1994
40  * Hewlett-Packard Company
41  *
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.
49  *
50  */
51
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).
55  */
56
57 #ifndef _BACKWARD_HASHTABLE_H
58 #define _BACKWARD_HASHTABLE_H 1
59
60 // Hashtable class, used to implement the hashed associative containers
61 // hash_set, hash_map, hash_multiset, and hash_multimap.
62
63 #include <vector>
64 #include <iterator>
65 #include <algorithm>
66 #include <bits/stl_function.h>
67 #include <backward/hash_fun.h>
68
69 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
70 {
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
72
73   using std::size_t;
74   using std::ptrdiff_t;
75   using std::forward_iterator_tag;
76   using std::input_iterator_tag;
77   using std::_Construct;
78   using std::_Destroy;
79   using std::distance;
80   using std::vector;
81   using std::pair;
82   using std::__iterator_category;
83
84   template<class _Val>
85     struct _Hashtable_node
86     {
87       _Hashtable_node* _M_next;
88       _Val _M_val;
89     };
90
91   template<class _Val, class _Key, class _HashFcn, class _ExtractKey, 
92            class _EqualKey, class _Alloc = std::allocator<_Val> >
93     class hashtable;
94
95   template<class _Val, class _Key, class _HashFcn,
96            class _ExtractKey, class _EqualKey, class _Alloc>
97     struct _Hashtable_iterator;
98
99   template<class _Val, class _Key, class _HashFcn,
100            class _ExtractKey, class _EqualKey, class _Alloc>
101     struct _Hashtable_const_iterator;
102
103   template<class _Val, class _Key, class _HashFcn,
104            class _ExtractKey, class _EqualKey, class _Alloc>
105     struct _Hashtable_iterator
106     {
107       typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
108         _Hashtable;
109       typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
110                                   _ExtractKey, _EqualKey, _Alloc>
111         iterator;
112       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
113                                         _ExtractKey, _EqualKey, _Alloc>
114         const_iterator;
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;
122       
123       _Node* _M_cur;
124       _Hashtable* _M_ht;
125
126       _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
127       : _M_cur(__n), _M_ht(__tab) { }
128
129       _Hashtable_iterator() { }
130
131       reference
132       operator*() const
133       { return _M_cur->_M_val; }
134
135       pointer
136       operator->() const
137       { return &(operator*()); }
138
139       iterator&
140       operator++();
141
142       iterator
143       operator++(int);
144
145       bool
146       operator==(const iterator& __it) const
147       { return _M_cur == __it._M_cur; }
148
149       bool
150       operator!=(const iterator& __it) const
151       { return _M_cur != __it._M_cur; }
152     };
153
154   template<class _Val, class _Key, class _HashFcn,
155            class _ExtractKey, class _EqualKey, class _Alloc>
156     struct _Hashtable_const_iterator
157     {
158       typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
159         _Hashtable;
160       typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
161                                   _ExtractKey,_EqualKey,_Alloc>
162         iterator;
163       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
164                                         _ExtractKey, _EqualKey, _Alloc>
165         const_iterator;
166       typedef _Hashtable_node<_Val> _Node;
167
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;
174       
175       const _Node* _M_cur;
176       const _Hashtable* _M_ht;
177
178       _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
179       : _M_cur(__n), _M_ht(__tab) { }
180
181       _Hashtable_const_iterator() { }
182
183       _Hashtable_const_iterator(const iterator& __it)
184       : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
185
186       reference
187       operator*() const
188       { return _M_cur->_M_val; }
189
190       pointer
191       operator->() const
192       { return &(operator*()); }
193
194       const_iterator&
195       operator++();
196
197       const_iterator
198       operator++(int);
199
200       bool
201       operator==(const const_iterator& __it) const
202       { return _M_cur == __it._M_cur; }
203
204       bool
205       operator!=(const const_iterator& __it) const
206       { return _M_cur != __it._M_cur; }
207     };
208
209   // Note: assumes long is at least 32 bits.
210   enum { _S_num_primes = 29 };
211
212   static const unsigned long __stl_prime_list[_S_num_primes] =
213     {
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
220     };
221
222   inline unsigned long
223   __stl_next_prime(unsigned long __n)
224   {
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;
229   }
230
231   // Forward declaration of operator==.  
232   template<class _Val, class _Key, class _HF, class _Ex,
233            class _Eq, class _All>
234     class hashtable;
235
236   template<class _Val, class _Key, class _HF, class _Ex,
237            class _Eq, class _All>
238     bool
239     operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
240                const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
241
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>
252     class hashtable
253     {
254     public:
255       typedef _Key key_type;
256       typedef _Val value_type;
257       typedef _HashFcn hasher;
258       typedef _EqualKey key_equal;
259
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;
266
267       hasher
268       hash_funct() const
269       { return _M_hash; }
270
271       key_equal
272       key_eq() const
273       { return _M_equals; }
274
275     private:
276       typedef _Hashtable_node<_Val> _Node;
277
278     public:
279       typedef typename _Alloc::template rebind<value_type>::other allocator_type;
280       allocator_type
281       get_allocator() const
282       { return _M_node_allocator; }
283
284     private:
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;
288
289       _Node_Alloc _M_node_allocator;
290
291       _Node*
292       _M_get_node()
293       { return _M_node_allocator.allocate(1); }
294
295       void
296       _M_put_node(_Node* __p)
297       { _M_node_allocator.deallocate(__p, 1); }
298
299     private:
300       hasher                _M_hash;
301       key_equal             _M_equals;
302       _ExtractKey           _M_get_key;
303       _Vector_type          _M_buckets;
304       size_type             _M_num_elements;
305       
306     public:
307       typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
308                                   _EqualKey, _Alloc>
309         iterator;
310       typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
311                                         _EqualKey, _Alloc>
312         const_iterator;
313
314       friend struct
315       _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
316
317       friend struct
318       _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
319                                 _EqualKey, _Alloc>;
320
321     public:
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); }
328
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); }
335
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); }
341
342       hashtable&
343       operator= (const hashtable& __ht)
344       {
345         if (&__ht != this)
346           {
347             clear();
348             _M_hash = __ht._M_hash;
349             _M_equals = __ht._M_equals;
350             _M_get_key = __ht._M_get_key;
351             _M_copy_from(__ht);
352           }
353         return *this;
354       }
355
356       ~hashtable()
357       { clear(); }
358
359       size_type
360       size() const
361       { return _M_num_elements; }
362
363       size_type
364       max_size() const
365       { return size_type(-1); }
366
367       bool
368       empty() const
369       { return size() == 0; }
370
371       void
372       swap(hashtable& __ht)
373       {
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);
379       }
380
381       iterator
382       begin()
383       {
384         for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
385           if (_M_buckets[__n])
386             return iterator(_M_buckets[__n], this);
387         return end();
388       }
389
390       iterator
391       end()
392       { return iterator(0, this); }
393
394       const_iterator
395       begin() const
396       {
397         for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
398           if (_M_buckets[__n])
399             return const_iterator(_M_buckets[__n], this);
400         return end();
401       }
402
403       const_iterator
404       end() const
405       { return const_iterator(0, this); }
406
407       template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq,
408                 class _Al>
409         friend bool
410         operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
411                    const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
412
413     public:
414       size_type
415       bucket_count() const
416       { return _M_buckets.size(); }
417
418       size_type
419       max_bucket_count() const
420       { return __stl_prime_list[(int)_S_num_primes - 1]; }
421
422       size_type
423       elems_in_bucket(size_type __bucket) const
424       {
425         size_type __result = 0;
426         for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
427           __result += 1;
428         return __result;
429       }
430
431       pair<iterator, bool>
432       insert_unique(const value_type& __obj)
433       {
434         resize(_M_num_elements + 1);
435         return insert_unique_noresize(__obj);
436       }
437
438       iterator
439       insert_equal(const value_type& __obj)
440       {
441         resize(_M_num_elements + 1);
442         return insert_equal_noresize(__obj);
443       }
444
445       pair<iterator, bool>
446       insert_unique_noresize(const value_type& __obj);
447
448       iterator
449       insert_equal_noresize(const value_type& __obj);
450
451       template<class _InputIterator>
452         void
453         insert_unique(_InputIterator __f, _InputIterator __l)
454         { insert_unique(__f, __l, __iterator_category(__f)); }
455
456       template<class _InputIterator>
457         void
458         insert_equal(_InputIterator __f, _InputIterator __l)
459         { insert_equal(__f, __l, __iterator_category(__f)); }
460
461       template<class _InputIterator>
462         void
463         insert_unique(_InputIterator __f, _InputIterator __l,
464                       input_iterator_tag)
465         {
466           for ( ; __f != __l; ++__f)
467             insert_unique(*__f);
468         }
469
470       template<class _InputIterator>
471         void
472         insert_equal(_InputIterator __f, _InputIterator __l,
473                      input_iterator_tag)
474         {
475           for ( ; __f != __l; ++__f)
476             insert_equal(*__f);
477         }
478
479       template<class _ForwardIterator>
480         void
481         insert_unique(_ForwardIterator __f, _ForwardIterator __l,
482                       forward_iterator_tag)
483         {
484           size_type __n = distance(__f, __l);
485           resize(_M_num_elements + __n);
486           for ( ; __n > 0; --__n, ++__f)
487             insert_unique_noresize(*__f);
488         }
489
490       template<class _ForwardIterator>
491         void
492         insert_equal(_ForwardIterator __f, _ForwardIterator __l,
493                      forward_iterator_tag)
494         {
495           size_type __n = distance(__f, __l);
496           resize(_M_num_elements + __n);
497           for ( ; __n > 0; --__n, ++__f)
498             insert_equal_noresize(*__f);
499         }
500
501       reference
502       find_or_insert(const value_type& __obj);
503
504       iterator
505       find(const key_type& __key)
506       {
507         size_type __n = _M_bkt_num_key(__key);
508         _Node* __first;
509         for (__first = _M_buckets[__n];
510              __first && !_M_equals(_M_get_key(__first->_M_val), __key);
511              __first = __first->_M_next)
512           { }
513         return iterator(__first, this);
514       }
515
516       const_iterator
517       find(const key_type& __key) const
518       {
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)
524           { }
525         return const_iterator(__first, this);
526       }
527
528       size_type
529       count(const key_type& __key) const
530       {
531         const size_type __n = _M_bkt_num_key(__key);
532         size_type __result = 0;
533         
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))
537             ++__result;
538         return __result;
539       }
540
541       pair<iterator, iterator>
542       equal_range(const key_type& __key);
543
544       pair<const_iterator, const_iterator>
545       equal_range(const key_type& __key) const;
546
547       size_type
548       erase(const key_type& __key);
549       
550       void
551       erase(const iterator& __it);
552
553       void
554       erase(iterator __first, iterator __last);
555
556       void
557       erase(const const_iterator& __it);
558
559       void
560       erase(const_iterator __first, const_iterator __last);
561
562       void
563       resize(size_type __num_elements_hint);
564
565       void
566       clear();
567
568     private:
569       size_type
570       _M_next_size(size_type __n) const
571       { return __stl_next_prime(__n); }
572
573       void
574       _M_initialize_buckets(size_type __n)
575       {
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);
579         _M_num_elements = 0;
580       }
581
582       size_type
583       _M_bkt_num_key(const key_type& __key) const
584       { return _M_bkt_num_key(__key, _M_buckets.size()); }
585
586       size_type
587       _M_bkt_num(const value_type& __obj) const
588       { return _M_bkt_num_key(_M_get_key(__obj)); }
589
590       size_type
591       _M_bkt_num_key(const key_type& __key, size_t __n) const
592       { return _M_hash(__key) % __n; }
593
594       size_type
595       _M_bkt_num(const value_type& __obj, size_t __n) const
596       { return _M_bkt_num_key(_M_get_key(__obj), __n); }
597
598       _Node*
599       _M_new_node(const value_type& __obj)
600       {
601         _Node* __n = _M_get_node();
602         __n->_M_next = 0;
603         __try
604           {
605             this->get_allocator().construct(&__n->_M_val, __obj);
606             return __n;
607           }
608         __catch(...)
609           {
610             _M_put_node(__n);
611             __throw_exception_again;
612           }
613       }
614
615       void
616       _M_delete_node(_Node* __n)
617       {
618         this->get_allocator().destroy(&__n->_M_val);
619         _M_put_node(__n);
620       }
621       
622       void
623       _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
624
625       void
626       _M_erase_bucket(const size_type __n, _Node* __last);
627
628       void
629       _M_copy_from(const hashtable& __ht);
630     };
631
632   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
633             class _All>
634     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
635     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
636     operator++()
637     {
638       const _Node* __old = _M_cur;
639       _M_cur = _M_cur->_M_next;
640       if (!_M_cur)
641         {
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];
645         }
646       return *this;
647     }
648
649   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
650             class _All>
651     inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
652     _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
653     operator++(int)
654     {
655       iterator __tmp = *this;
656       ++*this;
657       return __tmp;
658     }
659
660   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
661             class _All>
662     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
663     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
664     operator++()
665     {
666       const _Node* __old = _M_cur;
667       _M_cur = _M_cur->_M_next;
668       if (!_M_cur)
669         {
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];
673         }
674       return *this;
675     }
676
677   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
678             class _All>
679     inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
680     _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
681     operator++(int)
682     {
683       const_iterator __tmp = *this;
684       ++*this;
685       return __tmp;
686     }
687
688   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
689     bool
690     operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
691                const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
692     {
693       typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
694
695       if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
696         return false;
697
698       for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
699         {
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)
705             { } 
706           if (__cur1 || __cur2)
707             return false;
708           // Now check one's elements are in the other
709           for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
710                __cur1 = __cur1->_M_next)
711             {
712               bool _found__cur1 = false;
713               for (__cur2 = __ht2._M_buckets[__n];
714                    __cur2; __cur2 = __cur2->_M_next)
715                 {
716                   if (__cur1->_M_val == __cur2->_M_val)
717                     {
718                       _found__cur1 = true;
719                       break;
720                     }
721                 }
722               if (!_found__cur1)
723                 return false;
724             }
725         }
726       return true;
727     }
728
729   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
730     inline bool
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); }
734
735   template<class _Val, class _Key, class _HF, class _Extract, class _EqKey,
736             class _All>
737     inline void
738     swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
739          hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
740     { __ht1.swap(__ht2); }
741
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)
746     {
747       const size_type __n = _M_bkt_num(__obj);
748       _Node* __first = _M_buckets[__n];
749       
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);
753       
754       _Node* __tmp = _M_new_node(__obj);
755       __tmp->_M_next = __first;
756       _M_buckets[__n] = __tmp;
757       ++_M_num_elements;
758       return pair<iterator, bool>(iterator(__tmp, this), true);
759     }
760
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)
765     {
766       const size_type __n = _M_bkt_num(__obj);
767       _Node* __first = _M_buckets[__n];
768       
769       for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
770         if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
771           {
772             _Node* __tmp = _M_new_node(__obj);
773             __tmp->_M_next = __cur->_M_next;
774             __cur->_M_next = __tmp;
775             ++_M_num_elements;
776             return iterator(__tmp, this);
777           }
778
779       _Node* __tmp = _M_new_node(__obj);
780       __tmp->_M_next = __first;
781       _M_buckets[__n] = __tmp;
782       ++_M_num_elements;
783       return iterator(__tmp, this);
784     }
785
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)
790     {
791       resize(_M_num_elements + 1);
792
793       size_type __n = _M_bkt_num(__obj);
794       _Node* __first = _M_buckets[__n];
795       
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;
799       
800       _Node* __tmp = _M_new_node(__obj);
801       __tmp->_M_next = __first;
802       _M_buckets[__n] = __tmp;
803       ++_M_num_elements;
804       return __tmp->_M_val;
805     }
806
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)
812     {
813       typedef pair<iterator, iterator> _Pii;
814       const size_type __n = _M_bkt_num_key(__key);
815
816       for (_Node* __first = _M_buckets[__n]; __first;
817            __first = __first->_M_next)
818         if (_M_equals(_M_get_key(__first->_M_val), __key))
819           {
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)
825               if (_M_buckets[__m])
826                 return _Pii(iterator(__first, this),
827                             iterator(_M_buckets[__m], this));
828             return _Pii(iterator(__first, this), end());
829           }
830       return _Pii(end(), end());
831     }
832
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
838     {
839       typedef pair<const_iterator, const_iterator> _Pii;
840       const size_type __n = _M_bkt_num_key(__key);
841
842       for (const _Node* __first = _M_buckets[__n]; __first;
843            __first = __first->_M_next)
844         {
845           if (_M_equals(_M_get_key(__first->_M_val), __key))
846             {
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)
853                 if (_M_buckets[__m])
854                   return _Pii(const_iterator(__first, this),
855                               const_iterator(_M_buckets[__m], this));
856               return _Pii(const_iterator(__first, this), end());
857             }
858         }
859       return _Pii(end(), end());
860     }
861
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)
866     {
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;
871
872       if (__first)
873         {
874           _Node* __cur = __first;
875           _Node* __next = __cur->_M_next;
876           while (__next)
877             {
878               if (_M_equals(_M_get_key(__next->_M_val), __key))
879                 {
880                   if (&_M_get_key(__next->_M_val) != &__key)
881                     {
882                       __cur->_M_next = __next->_M_next;
883                       _M_delete_node(__next);
884                       __next = __cur->_M_next;
885                       ++__erased;
886                       --_M_num_elements;
887                     }
888                   else
889                     {
890                       __saved_slot = __cur;
891                       __cur = __next;
892                       __next = __cur->_M_next;
893                     }
894                 }
895               else
896                 {
897                   __cur = __next;
898                   __next = __cur->_M_next;
899                 }
900             }
901           bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key);
902           if (__saved_slot)
903             {
904               __next = __saved_slot->_M_next;
905               __saved_slot->_M_next = __next->_M_next;
906               _M_delete_node(__next);
907               ++__erased;
908               --_M_num_elements;
909             }
910           if (__delete_first)
911             {
912               _M_buckets[__n] = __first->_M_next;
913               _M_delete_node(__first);
914               ++__erased;
915               --_M_num_elements;
916             }
917         }
918       return __erased;
919     }
920
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)
924     {
925       _Node* __p = __it._M_cur;
926       if (__p)
927         {
928           const size_type __n = _M_bkt_num(__p->_M_val);
929           _Node* __cur = _M_buckets[__n];
930           
931           if (__cur == __p)
932             {
933               _M_buckets[__n] = __cur->_M_next;
934               _M_delete_node(__cur);
935               --_M_num_elements;
936             }
937           else
938             {
939               _Node* __next = __cur->_M_next;
940               while (__next)
941                 {
942                   if (__next == __p)
943                     {
944                       __cur->_M_next = __next->_M_next;
945                       _M_delete_node(__next);
946                       --_M_num_elements;
947                       break;
948                     }
949                   else
950                     {
951                       __cur = __next;
952                       __next = __cur->_M_next;
953                     }
954                 }
955             }
956         }
957     }
958
959   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
960     void
961     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
962     erase(iterator __first, iterator __last)
963     {
964       size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
965                                             : _M_buckets.size();
966
967       size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
968                                            : _M_buckets.size();
969
970       if (__first._M_cur == __last._M_cur)
971         return;
972       else if (__f_bucket == __l_bucket)
973         _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
974       else
975         {
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);
981         }
982     }
983
984   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
985     inline void
986     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
987     erase(const_iterator __first, const_iterator __last)
988     {
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)));
993     }
994
995   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
996     inline void
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))); }
1001
1002   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1003     void
1004     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1005     resize(size_type __num_elements_hint)
1006     {
1007       const size_type __old_n = _M_buckets.size();
1008       if (__num_elements_hint > __old_n)
1009         {
1010           const size_type __n = _M_next_size(__num_elements_hint);
1011           if (__n > __old_n)
1012             {
1013               _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
1014               __try
1015                 {
1016                   for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1017                     {
1018                       _Node* __first = _M_buckets[__bucket];
1019                       while (__first)
1020                         {
1021                           size_type __new_bucket = _M_bkt_num(__first->_M_val,
1022                                                               __n);
1023                           _M_buckets[__bucket] = __first->_M_next;
1024                           __first->_M_next = __tmp[__new_bucket];
1025                           __tmp[__new_bucket] = __first;
1026                           __first = _M_buckets[__bucket];
1027                         }
1028                     }
1029                   _M_buckets.swap(__tmp);
1030                 }
1031               __catch(...)
1032                 {
1033                   for (size_type __bucket = 0; __bucket < __tmp.size();
1034                        ++__bucket)
1035                     {
1036                       while (__tmp[__bucket])
1037                         {
1038                           _Node* __next = __tmp[__bucket]->_M_next;
1039                           _M_delete_node(__tmp[__bucket]);
1040                           __tmp[__bucket] = __next;
1041                         }
1042                     }
1043                   __throw_exception_again;
1044                 }
1045             }
1046         }
1047     }
1048
1049   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1050     void
1051     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1052     _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1053     {
1054       _Node* __cur = _M_buckets[__n];
1055       if (__cur == __first)
1056         _M_erase_bucket(__n, __last);
1057       else
1058         {
1059           _Node* __next;
1060           for (__next = __cur->_M_next;
1061                __next != __first;
1062                __cur = __next, __next = __cur->_M_next)
1063             ;
1064           while (__next != __last)
1065             {
1066               __cur->_M_next = __next->_M_next;
1067               _M_delete_node(__next);
1068               __next = __cur->_M_next;
1069               --_M_num_elements;
1070             }
1071         }
1072     }
1073
1074   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1075     void
1076     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1077     _M_erase_bucket(const size_type __n, _Node* __last)
1078     {
1079       _Node* __cur = _M_buckets[__n];
1080       while (__cur != __last)
1081         {
1082           _Node* __next = __cur->_M_next;
1083           _M_delete_node(__cur);
1084           __cur = __next;
1085           _M_buckets[__n] = __cur;
1086           --_M_num_elements;
1087         }
1088     }
1089
1090   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1091     void
1092     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1093     clear()
1094     {
1095       if (_M_num_elements == 0)
1096         return;
1097
1098       for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1099         {
1100           _Node* __cur = _M_buckets[__i];
1101           while (__cur != 0)
1102             {
1103               _Node* __next = __cur->_M_next;
1104               _M_delete_node(__cur);
1105               __cur = __next;
1106             }
1107           _M_buckets[__i] = 0;
1108         }
1109       _M_num_elements = 0;
1110     }
1111
1112   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1113     void
1114     hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1115     _M_copy_from(const hashtable& __ht)
1116     {
1117       _M_buckets.clear();
1118       _M_buckets.reserve(__ht._M_buckets.size());
1119       _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1120       __try
1121         {
1122           for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1123             const _Node* __cur = __ht._M_buckets[__i];
1124             if (__cur)
1125               {
1126                 _Node* __local_copy = _M_new_node(__cur->_M_val);
1127                 _M_buckets[__i] = __local_copy;
1128                 
1129                 for (_Node* __next = __cur->_M_next;
1130                      __next;
1131                      __cur = __next, __next = __cur->_M_next)
1132                   {
1133                     __local_copy->_M_next = _M_new_node(__next->_M_val);
1134                     __local_copy = __local_copy->_M_next;
1135                   }
1136               }
1137           }
1138           _M_num_elements = __ht._M_num_elements;
1139         }
1140       __catch(...)
1141         {
1142           clear();
1143           __throw_exception_again;
1144         }
1145     }
1146
1147 _GLIBCXX_END_NAMESPACE_VERSION
1148 } // namespace
1149
1150 #endif