STLdoc
STLdocumentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Functions
hashtable.h File Reference
#include <tr1/hashtable_policy.h>

Go to the source code of this file.

Functions

namespace std _GLIBCXX_VISIBILITY (default)
 

Detailed Description

This is an internal header file, included by other library headers. Do not attempt to use it directly. {tr1/unordered_set, tr1/unordered_map}

Function Documentation

namespace std _GLIBCXX_VISIBILITY ( default  )
39 {
40 namespace tr1
41 {
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
43 
44  // Class template _Hashtable, class definition.
45 
46  // Meaning of class template _Hashtable's template parameters
47 
48  // _Key and _Value: arbitrary CopyConstructible types.
49 
50  // _Allocator: an allocator type ([lib.allocator.requirements]) whose
51  // value type is Value. As a conforming extension, we allow for
52  // value type != Value.
53 
54  // _ExtractKey: function object that takes a object of type Value
55  // and returns a value of type _Key.
56 
57  // _Equal: function object that takes two objects of type k and returns
58  // a bool-like value that is true if the two objects are considered equal.
59 
60  // _H1: the hash function. A unary function object with argument type
61  // Key and result type size_t. Return values should be distributed
62  // over the entire range [0, numeric_limits<size_t>:::max()].
63 
64  // _H2: the range-hashing function (in the terminology of Tavori and
65  // Dreizin). A binary function object whose argument types and result
66  // type are all size_t. Given arguments r and N, the return value is
67  // in the range [0, N).
68 
69  // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
70  // whose argument types are _Key and size_t and whose result type is
71  // size_t. Given arguments k and N, the return value is in the range
72  // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
73  // than the default, _H1 and _H2 are ignored.
74 
75  // _RehashPolicy: Policy class with three members, all of which govern
76  // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
77  // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
78  // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
79  // determines whether, if the current bucket count is n_bkt and the
80  // current element count is n_elt, we need to increase the bucket
81  // count. If so, returns make_pair(true, n), where n is the new
82  // bucket count. If not, returns make_pair(false, <anything>).
83 
84  // ??? Right now it is hard-wired that the number of buckets never
85  // shrinks. Should we allow _RehashPolicy to change that?
86 
87  // __cache_hash_code: bool. true if we store the value of the hash
88  // function along with the value. This is a time-space tradeoff.
89  // Storing it may improve lookup speed by reducing the number of times
90  // we need to call the Equal function.
91 
92  // __constant_iterators: bool. true if iterator and const_iterator are
93  // both constant iterator types. This is true for unordered_set and
94  // unordered_multiset, false for unordered_map and unordered_multimap.
95 
96  // __unique_keys: bool. true if the return value of _Hashtable::count(k)
97  // is always at most one, false if it may be an arbitrary number. This
98  // true for unordered_set and unordered_map, false for unordered_multiset
99  // and unordered_multimap.
100 
101  template<typename _Key, typename _Value, typename _Allocator,
102  typename _ExtractKey, typename _Equal,
103  typename _H1, typename _H2, typename _Hash,
104  typename _RehashPolicy,
105  bool __cache_hash_code,
106  bool __constant_iterators,
107  bool __unique_keys>
108  class _Hashtable
109  : public __detail::_Rehash_base<_RehashPolicy,
110  _Hashtable<_Key, _Value, _Allocator,
111  _ExtractKey,
112  _Equal, _H1, _H2, _Hash,
113  _RehashPolicy,
114  __cache_hash_code,
115  __constant_iterators,
116  __unique_keys> >,
117  public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
118  _H1, _H2, _Hash, __cache_hash_code>,
119  public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
120  _Hashtable<_Key, _Value, _Allocator,
121  _ExtractKey,
122  _Equal, _H1, _H2, _Hash,
123  _RehashPolicy,
124  __cache_hash_code,
125  __constant_iterators,
126  __unique_keys> >
127  {
128  public:
129  typedef _Allocator allocator_type;
130  typedef _Value value_type;
131  typedef _Key key_type;
132  typedef _Equal key_equal;
133  // mapped_type, if present, comes from _Map_base.
134  // hasher, if present, comes from _Hash_code_base.
135  typedef typename _Allocator::difference_type difference_type;
136  typedef typename _Allocator::size_type size_type;
137  typedef typename _Allocator::pointer pointer;
138  typedef typename _Allocator::const_pointer const_pointer;
139  typedef typename _Allocator::reference reference;
140  typedef typename _Allocator::const_reference const_reference;
141 
142  typedef __detail::_Node_iterator<value_type, __constant_iterators,
143  __cache_hash_code>
144  local_iterator;
145  typedef __detail::_Node_const_iterator<value_type,
146  __constant_iterators,
147  __cache_hash_code>
148  const_local_iterator;
149 
150  typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
151  __cache_hash_code>
152  iterator;
153  typedef __detail::_Hashtable_const_iterator<value_type,
154  __constant_iterators,
155  __cache_hash_code>
156  const_iterator;
157 
158  template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
159  typename _Hashtable2>
160  friend struct __detail::_Map_base;
161 
162  private:
163  typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
164  typedef typename _Allocator::template rebind<_Node>::other
165  _Node_allocator_type;
166  typedef typename _Allocator::template rebind<_Node*>::other
167  _Bucket_allocator_type;
168 
169  typedef typename _Allocator::template rebind<_Value>::other
170  _Value_allocator_type;
171 
172  _Node_allocator_type _M_node_allocator;
173  _Node** _M_buckets;
174  size_type _M_bucket_count;
175  size_type _M_element_count;
176  _RehashPolicy _M_rehash_policy;
177 
178  _Node*
179  _M_allocate_node(const value_type& __v);
180 
181  void
182  _M_deallocate_node(_Node* __n);
183 
184  void
185  _M_deallocate_nodes(_Node**, size_type);
186 
187  _Node**
188  _M_allocate_buckets(size_type __n);
189 
190  void
191  _M_deallocate_buckets(_Node**, size_type __n);
192 
193  public:
194  // Constructor, destructor, assignment, swap
195  _Hashtable(size_type __bucket_hint,
196  const _H1&, const _H2&, const _Hash&,
197  const _Equal&, const _ExtractKey&,
198  const allocator_type&);
199 
200  template<typename _InputIterator>
201  _Hashtable(_InputIterator __first, _InputIterator __last,
202  size_type __bucket_hint,
203  const _H1&, const _H2&, const _Hash&,
204  const _Equal&, const _ExtractKey&,
205  const allocator_type&);
206 
207  _Hashtable(const _Hashtable&);
208 
209  _Hashtable&
210  operator=(const _Hashtable&);
211 
212  ~_Hashtable();
213 
214  void swap(_Hashtable&);
215 
216  // Basic container operations
217  iterator
218  begin()
219  {
220  iterator __i(_M_buckets);
221  if (!__i._M_cur_node)
222  __i._M_incr_bucket();
223  return __i;
224  }
225 
226  const_iterator
227  begin() const
228  {
229  const_iterator __i(_M_buckets);
230  if (!__i._M_cur_node)
231  __i._M_incr_bucket();
232  return __i;
233  }
234 
235  iterator
236  end()
237  { return iterator(_M_buckets + _M_bucket_count); }
238 
239  const_iterator
240  end() const
241  { return const_iterator(_M_buckets + _M_bucket_count); }
242 
243  size_type
244  size() const
245  { return _M_element_count; }
246 
247  bool
248  empty() const
249  { return size() == 0; }
250 
251  allocator_type
252  get_allocator() const
253  { return allocator_type(_M_node_allocator); }
254 
255  _Value_allocator_type
256  _M_get_Value_allocator() const
257  { return _Value_allocator_type(_M_node_allocator); }
258 
259  size_type
260  max_size() const
261  { return _M_node_allocator.max_size(); }
262 
263  // Observers
264  key_equal
265  key_eq() const
266  { return this->_M_eq; }
267 
268  // hash_function, if present, comes from _Hash_code_base.
269 
270  // Bucket operations
271  size_type
272  bucket_count() const
273  { return _M_bucket_count; }
274 
275  size_type
276  max_bucket_count() const
277  { return max_size(); }
278 
279  size_type
280  bucket_size(size_type __n) const
281  { return std::distance(begin(__n), end(__n)); }
282 
283  size_type
284  bucket(const key_type& __k) const
285  {
286  return this->_M_bucket_index(__k, this->_M_hash_code(__k),
287  bucket_count());
288  }
289 
290  local_iterator
291  begin(size_type __n)
292  { return local_iterator(_M_buckets[__n]); }
293 
294  local_iterator
295  end(size_type)
296  { return local_iterator(0); }
297 
298  const_local_iterator
299  begin(size_type __n) const
300  { return const_local_iterator(_M_buckets[__n]); }
301 
302  const_local_iterator
303  end(size_type) const
304  { return const_local_iterator(0); }
305 
306  float
307  load_factor() const
308  {
309  return static_cast<float>(size()) / static_cast<float>(bucket_count());
310  }
311 
312  // max_load_factor, if present, comes from _Rehash_base.
313 
314  // Generalization of max_load_factor. Extension, not found in TR1. Only
315  // useful if _RehashPolicy is something other than the default.
316  const _RehashPolicy&
317  __rehash_policy() const
318  { return _M_rehash_policy; }
319 
320  void
321  __rehash_policy(const _RehashPolicy&);
322 
323  // Lookup.
324  iterator
325  find(const key_type& __k);
326 
327  const_iterator
328  find(const key_type& __k) const;
329 
330  size_type
331  count(const key_type& __k) const;
332 
333  std::pair<iterator, iterator>
334  equal_range(const key_type& __k);
335 
336  std::pair<const_iterator, const_iterator>
337  equal_range(const key_type& __k) const;
338 
339  private: // Find, insert and erase helper functions
340  // ??? This dispatching is a workaround for the fact that we don't
341  // have partial specialization of member templates; it would be
342  // better to just specialize insert on __unique_keys. There may be a
343  // cleaner workaround.
344  typedef typename __gnu_cxx::__conditional_type<__unique_keys,
345  std::pair<iterator, bool>, iterator>::__type
346  _Insert_Return_Type;
347 
348  typedef typename __gnu_cxx::__conditional_type<__unique_keys,
349  std::_Select1st<_Insert_Return_Type>,
350  std::_Identity<_Insert_Return_Type>
351  >::__type
352  _Insert_Conv_Type;
353 
354  _Node*
355  _M_find_node(_Node*, const key_type&,
356  typename _Hashtable::_Hash_code_type) const;
357 
358  iterator
359  _M_insert_bucket(const value_type&, size_type,
360  typename _Hashtable::_Hash_code_type);
361 
362  std::pair<iterator, bool>
363  _M_insert(const value_type&, std::tr1::true_type);
364 
365  iterator
366  _M_insert(const value_type&, std::tr1::false_type);
367 
368  void
369  _M_erase_node(_Node*, _Node**);
370 
371  public:
372  // Insert and erase
373  _Insert_Return_Type
374  insert(const value_type& __v)
375  { return _M_insert(__v, std::tr1::integral_constant<bool,
376  __unique_keys>()); }
377 
378  iterator
379  insert(iterator, const value_type& __v)
380  { return iterator(_Insert_Conv_Type()(this->insert(__v))); }
381 
382  const_iterator
383  insert(const_iterator, const value_type& __v)
384  { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); }
385 
386  template<typename _InputIterator>
387  void
388  insert(_InputIterator __first, _InputIterator __last);
389 
390  iterator
391  erase(iterator);
392 
393  const_iterator
394  erase(const_iterator);
395 
396  size_type
397  erase(const key_type&);
398 
399  iterator
400  erase(iterator, iterator);
401 
402  const_iterator
403  erase(const_iterator, const_iterator);
404 
405  void
406  clear();
407 
408  // Set number of buckets to be appropriate for container of n element.
409  void rehash(size_type __n);
410 
411  private:
412  // Unconditionally change size of bucket array to n.
413  void _M_rehash(size_type __n);
414  };
415 
416 
417  // Definitions of class template _Hashtable's out-of-line member functions.
418  template<typename _Key, typename _Value,
419  typename _Allocator, typename _ExtractKey, typename _Equal,
420  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
421  bool __chc, bool __cit, bool __uk>
422  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
423  _H1, _H2, _Hash, _RehashPolicy,
424  __chc, __cit, __uk>::_Node*
425  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
426  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
427  _M_allocate_node(const value_type& __v)
428  {
429  _Node* __n = _M_node_allocator.allocate(1);
430  __try
431  {
432  _M_get_Value_allocator().construct(&__n->_M_v, __v);
433  __n->_M_next = 0;
434  return __n;
435  }
436  __catch(...)
437  {
438  _M_node_allocator.deallocate(__n, 1);
439  __throw_exception_again;
440  }
441  }
442 
443  template<typename _Key, typename _Value,
444  typename _Allocator, typename _ExtractKey, typename _Equal,
445  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
446  bool __chc, bool __cit, bool __uk>
447  void
448  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
449  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
450  _M_deallocate_node(_Node* __n)
451  {
452  _M_get_Value_allocator().destroy(&__n->_M_v);
453  _M_node_allocator.deallocate(__n, 1);
454  }
455 
456  template<typename _Key, typename _Value,
457  typename _Allocator, typename _ExtractKey, typename _Equal,
458  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
459  bool __chc, bool __cit, bool __uk>
460  void
461  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
462  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
463  _M_deallocate_nodes(_Node** __array, size_type __n)
464  {
465  for (size_type __i = 0; __i < __n; ++__i)
466  {
467  _Node* __p = __array[__i];
468  while (__p)
469  {
470  _Node* __tmp = __p;
471  __p = __p->_M_next;
472  _M_deallocate_node(__tmp);
473  }
474  __array[__i] = 0;
475  }
476  }
477 
478  template<typename _Key, typename _Value,
479  typename _Allocator, typename _ExtractKey, typename _Equal,
480  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
481  bool __chc, bool __cit, bool __uk>
482  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
483  _H1, _H2, _Hash, _RehashPolicy,
484  __chc, __cit, __uk>::_Node**
485  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
486  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
487  _M_allocate_buckets(size_type __n)
488  {
489  _Bucket_allocator_type __alloc(_M_node_allocator);
490 
491  // We allocate one extra bucket to hold a sentinel, an arbitrary
492  // non-null pointer. Iterator increment relies on this.
493  _Node** __p = __alloc.allocate(__n + 1);
494  std::fill(__p, __p + __n, (_Node*) 0);
495  __p[__n] = reinterpret_cast<_Node*>(0x1000);
496  return __p;
497  }
498 
499  template<typename _Key, typename _Value,
500  typename _Allocator, typename _ExtractKey, typename _Equal,
501  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
502  bool __chc, bool __cit, bool __uk>
503  void
504  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
505  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
506  _M_deallocate_buckets(_Node** __p, size_type __n)
507  {
508  _Bucket_allocator_type __alloc(_M_node_allocator);
509  __alloc.deallocate(__p, __n + 1);
510  }
511 
512  template<typename _Key, typename _Value,
513  typename _Allocator, typename _ExtractKey, typename _Equal,
514  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
515  bool __chc, bool __cit, bool __uk>
516  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
517  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
518  _Hashtable(size_type __bucket_hint,
519  const _H1& __h1, const _H2& __h2, const _Hash& __h,
520  const _Equal& __eq, const _ExtractKey& __exk,
521  const allocator_type& __a)
522  : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
523  __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
524  _H1, _H2, _Hash, __chc>(__exk, __eq,
525  __h1, __h2, __h),
526  __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
527  _M_node_allocator(__a),
528  _M_bucket_count(0),
529  _M_element_count(0),
530  _M_rehash_policy()
531  {
532  _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
533  _M_buckets = _M_allocate_buckets(_M_bucket_count);
534  }
535 
536  template<typename _Key, typename _Value,
537  typename _Allocator, typename _ExtractKey, typename _Equal,
538  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
539  bool __chc, bool __cit, bool __uk>
540  template<typename _InputIterator>
541  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
542  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
543  _Hashtable(_InputIterator __f, _InputIterator __l,
544  size_type __bucket_hint,
545  const _H1& __h1, const _H2& __h2, const _Hash& __h,
546  const _Equal& __eq, const _ExtractKey& __exk,
547  const allocator_type& __a)
548  : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
549  __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
550  _H1, _H2, _Hash, __chc>(__exk, __eq,
551  __h1, __h2, __h),
552  __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
553  _M_node_allocator(__a),
554  _M_bucket_count(0),
555  _M_element_count(0),
556  _M_rehash_policy()
557  {
558  _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
559  _M_rehash_policy.
560  _M_bkt_for_elements(__detail::
561  __distance_fw(__f,
562  __l)));
563  _M_buckets = _M_allocate_buckets(_M_bucket_count);
564  __try
565  {
566  for (; __f != __l; ++__f)
567  this->insert(*__f);
568  }
569  __catch(...)
570  {
571  clear();
572  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
573  __throw_exception_again;
574  }
575  }
576 
577  template<typename _Key, typename _Value,
578  typename _Allocator, typename _ExtractKey, typename _Equal,
579  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
580  bool __chc, bool __cit, bool __uk>
581  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
582  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
583  _Hashtable(const _Hashtable& __ht)
584  : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
585  __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
586  _H1, _H2, _Hash, __chc>(__ht),
587  __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
588  _M_node_allocator(__ht._M_node_allocator),
589  _M_bucket_count(__ht._M_bucket_count),
590  _M_element_count(__ht._M_element_count),
591  _M_rehash_policy(__ht._M_rehash_policy)
592  {
593  _M_buckets = _M_allocate_buckets(_M_bucket_count);
594  __try
595  {
596  for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
597  {
598  _Node* __n = __ht._M_buckets[__i];
599  _Node** __tail = _M_buckets + __i;
600  while (__n)
601  {
602  *__tail = _M_allocate_node(__n->_M_v);
603  this->_M_copy_code(*__tail, __n);
604  __tail = &((*__tail)->_M_next);
605  __n = __n->_M_next;
606  }
607  }
608  }
609  __catch(...)
610  {
611  clear();
612  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
613  __throw_exception_again;
614  }
615  }
616 
617  template<typename _Key, typename _Value,
618  typename _Allocator, typename _ExtractKey, typename _Equal,
619  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
620  bool __chc, bool __cit, bool __uk>
621  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
622  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>&
623  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
624  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
625  operator=(const _Hashtable& __ht)
626  {
627  _Hashtable __tmp(__ht);
628  this->swap(__tmp);
629  return *this;
630  }
631 
632  template<typename _Key, typename _Value,
633  typename _Allocator, typename _ExtractKey, typename _Equal,
634  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
635  bool __chc, bool __cit, bool __uk>
636  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
637  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
638  ~_Hashtable()
639  {
640  clear();
641  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
642  }
643 
644  template<typename _Key, typename _Value,
645  typename _Allocator, typename _ExtractKey, typename _Equal,
646  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
647  bool __chc, bool __cit, bool __uk>
648  void
649  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
650  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
651  swap(_Hashtable& __x)
652  {
653  // The only base class with member variables is hash_code_base. We
654  // define _Hash_code_base::_M_swap because different specializations
655  // have different members.
656  __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
657  _H1, _H2, _Hash, __chc>::_M_swap(__x);
658 
659  // _GLIBCXX_RESOLVE_LIB_DEFECTS
660  // 431. Swapping containers with unequal allocators.
661  std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
662  __x._M_node_allocator);
663 
664  std::swap(_M_rehash_policy, __x._M_rehash_policy);
665  std::swap(_M_buckets, __x._M_buckets);
666  std::swap(_M_bucket_count, __x._M_bucket_count);
667  std::swap(_M_element_count, __x._M_element_count);
668  }
669 
670  template<typename _Key, typename _Value,
671  typename _Allocator, typename _ExtractKey, typename _Equal,
672  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
673  bool __chc, bool __cit, bool __uk>
674  void
675  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
676  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
677  __rehash_policy(const _RehashPolicy& __pol)
678  {
679  _M_rehash_policy = __pol;
680  size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
681  if (__n_bkt > _M_bucket_count)
682  _M_rehash(__n_bkt);
683  }
684 
685  template<typename _Key, typename _Value,
686  typename _Allocator, typename _ExtractKey, typename _Equal,
687  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
688  bool __chc, bool __cit, bool __uk>
689  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
690  _H1, _H2, _Hash, _RehashPolicy,
691  __chc, __cit, __uk>::iterator
692  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
693  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
694  find(const key_type& __k)
695  {
696  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
697  std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
698  _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
699  return __p ? iterator(__p, _M_buckets + __n) : this->end();
700  }
701 
702  template<typename _Key, typename _Value,
703  typename _Allocator, typename _ExtractKey, typename _Equal,
704  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
705  bool __chc, bool __cit, bool __uk>
706  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
707  _H1, _H2, _Hash, _RehashPolicy,
708  __chc, __cit, __uk>::const_iterator
709  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
710  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
711  find(const key_type& __k) const
712  {
713  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
714  std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
715  _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
716  return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
717  }
718 
719  template<typename _Key, typename _Value,
720  typename _Allocator, typename _ExtractKey, typename _Equal,
721  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
722  bool __chc, bool __cit, bool __uk>
723  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
724  _H1, _H2, _Hash, _RehashPolicy,
725  __chc, __cit, __uk>::size_type
726  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
727  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
728  count(const key_type& __k) const
729  {
730  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
731  std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
732  std::size_t __result = 0;
733  for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
734  if (this->_M_compare(__k, __code, __p))
735  ++__result;
736  return __result;
737  }
738 
739  template<typename _Key, typename _Value,
740  typename _Allocator, typename _ExtractKey, typename _Equal,
741  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
742  bool __chc, bool __cit, bool __uk>
743  std::pair<typename _Hashtable<_Key, _Value, _Allocator,
744  _ExtractKey, _Equal, _H1,
745  _H2, _Hash, _RehashPolicy,
746  __chc, __cit, __uk>::iterator,
747  typename _Hashtable<_Key, _Value, _Allocator,
748  _ExtractKey, _Equal, _H1,
749  _H2, _Hash, _RehashPolicy,
750  __chc, __cit, __uk>::iterator>
751  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
752  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
753  equal_range(const key_type& __k)
754  {
755  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
756  std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
757  _Node** __head = _M_buckets + __n;
758  _Node* __p = _M_find_node(*__head, __k, __code);
759 
760  if (__p)
761  {
762  _Node* __p1 = __p->_M_next;
763  for (; __p1; __p1 = __p1->_M_next)
764  if (!this->_M_compare(__k, __code, __p1))
765  break;
766 
767  iterator __first(__p, __head);
768  iterator __last(__p1, __head);
769  if (!__p1)
770  __last._M_incr_bucket();
771  return std::make_pair(__first, __last);
772  }
773  else
774  return std::make_pair(this->end(), this->end());
775  }
776 
777  template<typename _Key, typename _Value,
778  typename _Allocator, typename _ExtractKey, typename _Equal,
779  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
780  bool __chc, bool __cit, bool __uk>
781  std::pair<typename _Hashtable<_Key, _Value, _Allocator,
782  _ExtractKey, _Equal, _H1,
783  _H2, _Hash, _RehashPolicy,
784  __chc, __cit, __uk>::const_iterator,
785  typename _Hashtable<_Key, _Value, _Allocator,
786  _ExtractKey, _Equal, _H1,
787  _H2, _Hash, _RehashPolicy,
788  __chc, __cit, __uk>::const_iterator>
789  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
790  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
791  equal_range(const key_type& __k) const
792  {
793  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
794  std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
795  _Node** __head = _M_buckets + __n;
796  _Node* __p = _M_find_node(*__head, __k, __code);
797 
798  if (__p)
799  {
800  _Node* __p1 = __p->_M_next;
801  for (; __p1; __p1 = __p1->_M_next)
802  if (!this->_M_compare(__k, __code, __p1))
803  break;
804 
805  const_iterator __first(__p, __head);
806  const_iterator __last(__p1, __head);
807  if (!__p1)
808  __last._M_incr_bucket();
809  return std::make_pair(__first, __last);
810  }
811  else
812  return std::make_pair(this->end(), this->end());
813  }
814 
815  // Find the node whose key compares equal to k, beginning the search
816  // at p (usually the head of a bucket). Return zero if no node is found.
817  template<typename _Key, typename _Value,
818  typename _Allocator, typename _ExtractKey, typename _Equal,
819  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
820  bool __chc, bool __cit, bool __uk>
821  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
822  _Equal, _H1, _H2, _Hash, _RehashPolicy,
823  __chc, __cit, __uk>::_Node*
824  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
825  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
826  _M_find_node(_Node* __p, const key_type& __k,
827  typename _Hashtable::_Hash_code_type __code) const
828  {
829  for (; __p; __p = __p->_M_next)
830  if (this->_M_compare(__k, __code, __p))
831  return __p;
832  return 0;
833  }
834 
835  // Insert v in bucket n (assumes no element with its key already present).
836  template<typename _Key, typename _Value,
837  typename _Allocator, typename _ExtractKey, typename _Equal,
838  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
839  bool __chc, bool __cit, bool __uk>
840  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
841  _H1, _H2, _Hash, _RehashPolicy,
842  __chc, __cit, __uk>::iterator
843  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
844  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
845  _M_insert_bucket(const value_type& __v, size_type __n,
846  typename _Hashtable::_Hash_code_type __code)
847  {
848  std::pair<bool, std::size_t> __do_rehash
849  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
850  _M_element_count, 1);
851 
852  // Allocate the new node before doing the rehash so that we don't
853  // do a rehash if the allocation throws.
854  _Node* __new_node = _M_allocate_node(__v);
855 
856  __try
857  {
858  if (__do_rehash.first)
859  {
860  const key_type& __k = this->_M_extract(__v);
861  __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
862  _M_rehash(__do_rehash.second);
863  }
864 
865  __new_node->_M_next = _M_buckets[__n];
866  this->_M_store_code(__new_node, __code);
867  _M_buckets[__n] = __new_node;
868  ++_M_element_count;
869  return iterator(__new_node, _M_buckets + __n);
870  }
871  __catch(...)
872  {
873  _M_deallocate_node(__new_node);
874  __throw_exception_again;
875  }
876  }
877 
878  // Insert v if no element with its key is already present.
879  template<typename _Key, typename _Value,
880  typename _Allocator, typename _ExtractKey, typename _Equal,
881  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
882  bool __chc, bool __cit, bool __uk>
883  std::pair<typename _Hashtable<_Key, _Value, _Allocator,
884  _ExtractKey, _Equal, _H1,
885  _H2, _Hash, _RehashPolicy,
886  __chc, __cit, __uk>::iterator, bool>
887  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
888  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
889  _M_insert(const value_type& __v, std::tr1::true_type)
890  {
891  const key_type& __k = this->_M_extract(__v);
892  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
893  size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
894 
895  if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
896  return std::make_pair(iterator(__p, _M_buckets + __n), false);
897  return std::make_pair(_M_insert_bucket(__v, __n, __code), true);
898  }
899 
900  // Insert v unconditionally.
901  template<typename _Key, typename _Value,
902  typename _Allocator, typename _ExtractKey, typename _Equal,
903  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
904  bool __chc, bool __cit, bool __uk>
905  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
906  _H1, _H2, _Hash, _RehashPolicy,
907  __chc, __cit, __uk>::iterator
908  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
909  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
910  _M_insert(const value_type& __v, std::tr1::false_type)
911  {
912  std::pair<bool, std::size_t> __do_rehash
913  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
914  _M_element_count, 1);
915  if (__do_rehash.first)
916  _M_rehash(__do_rehash.second);
917 
918  const key_type& __k = this->_M_extract(__v);
919  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
920  size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
921 
922  // First find the node, avoid leaking new_node if compare throws.
923  _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
924  _Node* __new_node = _M_allocate_node(__v);
925 
926  if (__prev)
927  {
928  __new_node->_M_next = __prev->_M_next;
929  __prev->_M_next = __new_node;
930  }
931  else
932  {
933  __new_node->_M_next = _M_buckets[__n];
934  _M_buckets[__n] = __new_node;
935  }
936  this->_M_store_code(__new_node, __code);
937 
938  ++_M_element_count;
939  return iterator(__new_node, _M_buckets + __n);
940  }
941 
942  // For erase(iterator) and erase(const_iterator).
943  template<typename _Key, typename _Value,
944  typename _Allocator, typename _ExtractKey, typename _Equal,
945  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
946  bool __chc, bool __cit, bool __uk>
947  void
948  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
949  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
950  _M_erase_node(_Node* __p, _Node** __b)
951  {
952  _Node* __cur = *__b;
953  if (__cur == __p)
954  *__b = __cur->_M_next;
955  else
956  {
957  _Node* __next = __cur->_M_next;
958  while (__next != __p)
959  {
960  __cur = __next;
961  __next = __cur->_M_next;
962  }
963  __cur->_M_next = __next->_M_next;
964  }
965 
966  _M_deallocate_node(__p);
967  --_M_element_count;
968  }
969 
970  template<typename _Key, typename _Value,
971  typename _Allocator, typename _ExtractKey, typename _Equal,
972  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
973  bool __chc, bool __cit, bool __uk>
974  template<typename _InputIterator>
975  void
976  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
977  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
978  insert(_InputIterator __first, _InputIterator __last)
979  {
980  size_type __n_elt = __detail::__distance_fw(__first, __last);
981  std::pair<bool, std::size_t> __do_rehash
982  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
983  _M_element_count, __n_elt);
984  if (__do_rehash.first)
985  _M_rehash(__do_rehash.second);
986 
987  for (; __first != __last; ++__first)
988  this->insert(*__first);
989  }
990 
991  template<typename _Key, typename _Value,
992  typename _Allocator, typename _ExtractKey, typename _Equal,
993  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
994  bool __chc, bool __cit, bool __uk>
995  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
996  _H1, _H2, _Hash, _RehashPolicy,
997  __chc, __cit, __uk>::iterator
998  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
999  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1000  erase(iterator __it)
1001  {
1002  iterator __result = __it;
1003  ++__result;
1004  _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
1005  return __result;
1006  }
1007 
1008  template<typename _Key, typename _Value,
1009  typename _Allocator, typename _ExtractKey, typename _Equal,
1010  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1011  bool __chc, bool __cit, bool __uk>
1012  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1013  _H1, _H2, _Hash, _RehashPolicy,
1014  __chc, __cit, __uk>::const_iterator
1015  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1016  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1017  erase(const_iterator __it)
1018  {
1019  const_iterator __result = __it;
1020  ++__result;
1021  _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
1022  return __result;
1023  }
1024 
1025  template<typename _Key, typename _Value,
1026  typename _Allocator, typename _ExtractKey, typename _Equal,
1027  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1028  bool __chc, bool __cit, bool __uk>
1029  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1030  _H1, _H2, _Hash, _RehashPolicy,
1031  __chc, __cit, __uk>::size_type
1032  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1033  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1034  erase(const key_type& __k)
1035  {
1036  typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1037  std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1038  size_type __result = 0;
1039 
1040  _Node** __slot = _M_buckets + __n;
1041  while (*__slot && !this->_M_compare(__k, __code, *__slot))
1042  __slot = &((*__slot)->_M_next);
1043 
1044  _Node** __saved_slot = 0;
1045  while (*__slot && this->_M_compare(__k, __code, *__slot))
1046  {
1047  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1048  // 526. Is it undefined if a function in the standard changes
1049  // in parameters?
1050  if (&this->_M_extract((*__slot)->_M_v) != &__k)
1051  {
1052  _Node* __p = *__slot;
1053  *__slot = __p->_M_next;
1054  _M_deallocate_node(__p);
1055  --_M_element_count;
1056  ++__result;
1057  }
1058  else
1059  {
1060  __saved_slot = __slot;
1061  __slot = &((*__slot)->_M_next);
1062  }
1063  }
1064 
1065  if (__saved_slot)
1066  {
1067  _Node* __p = *__saved_slot;
1068  *__saved_slot = __p->_M_next;
1069  _M_deallocate_node(__p);
1070  --_M_element_count;
1071  ++__result;
1072  }
1073 
1074  return __result;
1075  }
1076 
1077  // ??? This could be optimized by taking advantage of the bucket
1078  // structure, but it's not clear that it's worth doing. It probably
1079  // wouldn't even be an optimization unless the load factor is large.
1080  template<typename _Key, typename _Value,
1081  typename _Allocator, typename _ExtractKey, typename _Equal,
1082  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1083  bool __chc, bool __cit, bool __uk>
1084  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1085  _H1, _H2, _Hash, _RehashPolicy,
1086  __chc, __cit, __uk>::iterator
1087  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1088  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1089  erase(iterator __first, iterator __last)
1090  {
1091  while (__first != __last)
1092  __first = this->erase(__first);
1093  return __last;
1094  }
1095 
1096  template<typename _Key, typename _Value,
1097  typename _Allocator, typename _ExtractKey, typename _Equal,
1098  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1099  bool __chc, bool __cit, bool __uk>
1100  typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1101  _H1, _H2, _Hash, _RehashPolicy,
1102  __chc, __cit, __uk>::const_iterator
1103  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1104  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1105  erase(const_iterator __first, const_iterator __last)
1106  {
1107  while (__first != __last)
1108  __first = this->erase(__first);
1109  return __last;
1110  }
1111 
1112  template<typename _Key, typename _Value,
1113  typename _Allocator, typename _ExtractKey, typename _Equal,
1114  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1115  bool __chc, bool __cit, bool __uk>
1116  void
1117  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1118  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1119  clear()
1120  {
1121  _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1122  _M_element_count = 0;
1123  }
1124 
1125  template<typename _Key, typename _Value,
1126  typename _Allocator, typename _ExtractKey, typename _Equal,
1127  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1128  bool __chc, bool __cit, bool __uk>
1129  void
1130  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1131  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1132  rehash(size_type __n)
1133  {
1134  _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1135  _M_rehash_policy._M_bkt_for_elements(_M_element_count
1136  + 1)));
1137  }
1138 
1139  template<typename _Key, typename _Value,
1140  typename _Allocator, typename _ExtractKey, typename _Equal,
1141  typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1142  bool __chc, bool __cit, bool __uk>
1143  void
1144  _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1145  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1146  _M_rehash(size_type __n)
1147  {
1148  _Node** __new_array = _M_allocate_buckets(__n);
1149  __try
1150  {
1151  for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1152  while (_Node* __p = _M_buckets[__i])
1153  {
1154  std::size_t __new_index = this->_M_bucket_index(__p, __n);
1155  _M_buckets[__i] = __p->_M_next;
1156  __p->_M_next = __new_array[__new_index];
1157  __new_array[__new_index] = __p;
1158  }
1159  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1160  _M_bucket_count = __n;
1161  _M_buckets = __new_array;
1162  }
1163  __catch(...)
1164  {
1165  // A failure here means that a hash function threw an exception.
1166  // We can't restore the previous state without calling the hash
1167  // function again, so the only sensible recovery is to delete
1168  // everything.
1169  _M_deallocate_nodes(__new_array, __n);
1170  _M_deallocate_buckets(__new_array, __n);
1171  _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1172  _M_element_count = 0;
1173  __throw_exception_again;
1174  }
1175  }
1176 
1177 _GLIBCXX_END_NAMESPACE_VERSION
1178 } // namespace tr1
1179 } // namespace std
__try
#define __try
Definition: exception_defines.h:35
__throw_exception_again
#define __throw_exception_again
Definition: exception_defines.h:37
__gnu_parallel::max
const _Tp & max(const _Tp &__a, const _Tp &__b)
Equivalent to std::max.
Definition: base.h:150
size_t
__SIZE_TYPE__ size_t
Definition: stddef.h:212
__gnu_pbds::detail::true_type
std::tr1::integral_constant< int, 1 > true_type
Definition: type_utils.hpp:70
__catch
#define __catch(X)
Definition: exception_defines.h:36
std::__exception_ptr::swap
void swap(exception_ptr &__lhs, exception_ptr &__rhs)
Definition: exception_ptr.h:160
__gnu_pbds::detail::false_type
std::tr1::integral_constant< int, 0 > false_type
Definition: type_utils.hpp:71
Generated on Sat Jul 22 2017 14:41:10 for STLdoc by   doxygen 1.8.6