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 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
70 {
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
72 
73  using std::size_t;
74  using std::ptrdiff_t;
77  using std::_Construct;
78  using std::_Destroy;
79  using std::distance;
80  using std::vector;
81  using std::pair;
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  if (_M_equals(_M_get_key(__first->_M_val), __key))
902  {
903  _M_buckets[__n] = __first->_M_next;
904  _M_delete_node(__first);
905  ++__erased;
906  --_M_num_elements;
907  }
908  if (__saved_slot)
909  {
910  __next = __saved_slot->_M_next;
911  __saved_slot->_M_next = __next->_M_next;
912  _M_delete_node(__next);
913  ++__erased;
914  --_M_num_elements;
915  }
916  }
917  return __erased;
918  }
919 
920  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
921  void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
922  erase(const iterator& __it)
923  {
924  _Node* __p = __it._M_cur;
925  if (__p)
926  {
927  const size_type __n = _M_bkt_num(__p->_M_val);
928  _Node* __cur = _M_buckets[__n];
929 
930  if (__cur == __p)
931  {
932  _M_buckets[__n] = __cur->_M_next;
933  _M_delete_node(__cur);
934  --_M_num_elements;
935  }
936  else
937  {
938  _Node* __next = __cur->_M_next;
939  while (__next)
940  {
941  if (__next == __p)
942  {
943  __cur->_M_next = __next->_M_next;
944  _M_delete_node(__next);
945  --_M_num_elements;
946  break;
947  }
948  else
949  {
950  __cur = __next;
951  __next = __cur->_M_next;
952  }
953  }
954  }
955  }
956  }
957 
958  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
959  void
960  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
961  erase(iterator __first, iterator __last)
962  {
963  size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
964  : _M_buckets.size();
965 
966  size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
967  : _M_buckets.size();
968 
969  if (__first._M_cur == __last._M_cur)
970  return;
971  else if (__f_bucket == __l_bucket)
972  _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
973  else
974  {
975  _M_erase_bucket(__f_bucket, __first._M_cur, 0);
976  for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
977  _M_erase_bucket(__n, 0);
978  if (__l_bucket != _M_buckets.size())
979  _M_erase_bucket(__l_bucket, __last._M_cur);
980  }
981  }
982 
983  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
984  inline void
985  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
986  erase(const_iterator __first, const_iterator __last)
987  {
988  erase(iterator(const_cast<_Node*>(__first._M_cur),
989  const_cast<hashtable*>(__first._M_ht)),
990  iterator(const_cast<_Node*>(__last._M_cur),
991  const_cast<hashtable*>(__last._M_ht)));
992  }
993 
994  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
995  inline void
996  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
997  erase(const const_iterator& __it)
998  { erase(iterator(const_cast<_Node*>(__it._M_cur),
999  const_cast<hashtable*>(__it._M_ht))); }
1000 
1001  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1002  void
1003  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1004  resize(size_type __num_elements_hint)
1005  {
1006  const size_type __old_n = _M_buckets.size();
1007  if (__num_elements_hint > __old_n)
1008  {
1009  const size_type __n = _M_next_size(__num_elements_hint);
1010  if (__n > __old_n)
1011  {
1012  _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
1013  __try
1014  {
1015  for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1016  {
1017  _Node* __first = _M_buckets[__bucket];
1018  while (__first)
1019  {
1020  size_type __new_bucket = _M_bkt_num(__first->_M_val,
1021  __n);
1022  _M_buckets[__bucket] = __first->_M_next;
1023  __first->_M_next = __tmp[__new_bucket];
1024  __tmp[__new_bucket] = __first;
1025  __first = _M_buckets[__bucket];
1026  }
1027  }
1028  _M_buckets.swap(__tmp);
1029  }
1030  __catch(...)
1031  {
1032  for (size_type __bucket = 0; __bucket < __tmp.size();
1033  ++__bucket)
1034  {
1035  while (__tmp[__bucket])
1036  {
1037  _Node* __next = __tmp[__bucket]->_M_next;
1038  _M_delete_node(__tmp[__bucket]);
1039  __tmp[__bucket] = __next;
1040  }
1041  }
1042  __throw_exception_again;
1043  }
1044  }
1045  }
1046  }
1047 
1048  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1049  void
1050  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1051  _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1052  {
1053  _Node* __cur = _M_buckets[__n];
1054  if (__cur == __first)
1055  _M_erase_bucket(__n, __last);
1056  else
1057  {
1058  _Node* __next;
1059  for (__next = __cur->_M_next;
1060  __next != __first;
1061  __cur = __next, __next = __cur->_M_next)
1062  ;
1063  while (__next != __last)
1064  {
1065  __cur->_M_next = __next->_M_next;
1066  _M_delete_node(__next);
1067  __next = __cur->_M_next;
1068  --_M_num_elements;
1069  }
1070  }
1071  }
1072 
1073  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1074  void
1075  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1076  _M_erase_bucket(const size_type __n, _Node* __last)
1077  {
1078  _Node* __cur = _M_buckets[__n];
1079  while (__cur != __last)
1080  {
1081  _Node* __next = __cur->_M_next;
1082  _M_delete_node(__cur);
1083  __cur = __next;
1084  _M_buckets[__n] = __cur;
1085  --_M_num_elements;
1086  }
1087  }
1088 
1089  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1090  void
1091  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1092  clear()
1093  {
1094  if (_M_num_elements == 0)
1095  return;
1096 
1097  for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1098  {
1099  _Node* __cur = _M_buckets[__i];
1100  while (__cur != 0)
1101  {
1102  _Node* __next = __cur->_M_next;
1103  _M_delete_node(__cur);
1104  __cur = __next;
1105  }
1106  _M_buckets[__i] = 0;
1107  }
1108  _M_num_elements = 0;
1109  }
1110 
1111  template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1112  void
1113  hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1114  _M_copy_from(const hashtable& __ht)
1115  {
1116  _M_buckets.clear();
1117  _M_buckets.reserve(__ht._M_buckets.size());
1118  _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1119  __try
1120  {
1121  for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1122  const _Node* __cur = __ht._M_buckets[__i];
1123  if (__cur)
1124  {
1125  _Node* __local_copy = _M_new_node(__cur->_M_val);
1126  _M_buckets[__i] = __local_copy;
1127 
1128  for (_Node* __next = __cur->_M_next;
1129  __next;
1130  __cur = __next, __next = __cur->_M_next)
1131  {
1132  __local_copy->_M_next = _M_new_node(__next->_M_val);
1133  __local_copy = __local_copy->_M_next;
1134  }
1135  }
1136  }
1137  _M_num_elements = __ht._M_num_elements;
1138  }
1139  __catch(...)
1140  {
1141  clear();
1142  __throw_exception_again;
1143  }
1144  }
1145 
1146 _GLIBCXX_END_NAMESPACE_VERSION
1147 } // namespace
1148 
1149 #endif
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:87
constexpr const _Tp * begin(initializer_list< _Tp > __ils)
Return an iterator pointing to the first element of the initilizer_list.
void _Destroy(_Tp *__pointer)
Definition: stl_construct.h:93
Forward iterators support a superset of input iterator operations.
_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val)
Finds the first position in which val could be inserted without changing the ordering.
Definition: stl_algobase.h:936
constexpr size_t size() const
Returns the total number of bits.
Definition: bitset:1275
void _Construct(_T1 *__p, _Args &&...__args)
Definition: stl_construct.h:75
constexpr const _Tp * end(initializer_list< _Tp > __ils)
Return an iterator pointing to one past the last element of the initilizer_list.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
A standard container which offers fixed time access to individual elements in any order...
Definition: stl_vector.h:180
size_t count() const
Returns the number of bits which are set.
Definition: bitset:1270
Marking input iterators.
The standard allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manual...
Definition: allocator.h:66
void distance(_InputIterator __first, _InputIterator __last, _Distance &__n)
Definition: ext/iterator:105