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