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