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