visus
/
toolchain-gcc-arm-embedded
Watch 1
Star 0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2 Commits
1 Branch
Branch: main
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'main'
${ noResults }
toolchain-gcc-arm-embedded/arm-none-eabi/include/c++/10.2.1/tr1/hashtable.h

1192 lines
41KB
Raw Permalink Blame History 

  1. // TR1 hashtable.h header -*- C++ -*-

  2. 

  3. // Copyright (C) 2007-2020 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. /** @file tr1/hashtable.h

  26.  *  This is an internal header file, included by other library headers.

  27.  *  Do not attempt to use it directly.

  28.  *  @headername{tr1/unordered_set, tr1/unordered_map}

  29.  */

  30. 

  31. #ifndef _GLIBCXX_TR1_HASHTABLE_H

  32. #define _GLIBCXX_TR1_HASHTABLE_H 1

  33. 

  34. #pragma GCC system_header

  35. 

  36. #include <tr1/hashtable_policy.h>

  37. #include <ext/alloc_traits.h>

  38. 

  39. namespace std _GLIBCXX_VISIBILITY(default)

  40. {

  41. _GLIBCXX_BEGIN_NAMESPACE_VERSION

  42. 

  43. namespace tr1

  44. {

  45.   // Class template _Hashtable, class definition.

  46. 

  47.   // Meaning of class template _Hashtable's template parameters

  48. 

  49.   // _Key and _Value: arbitrary CopyConstructible types.

  50. 

  51.   // _Allocator: an allocator type ([lib.allocator.requirements]) whose

  52.   // value type is Value.  As a conforming extension, we allow for

  53.   // value type != Value.

  54. 

  55.   // _ExtractKey: function object that takes a object of type Value

  56.   // and returns a value of type _Key.

  57. 

  58.   // _Equal: function object that takes two objects of type k and returns

  59.   // a bool-like value that is true if the two objects are considered equal.

  60. 

  61.   // _H1: the hash function.  A unary function object with argument type

  62.   // Key and result type size_t.  Return values should be distributed

  63.   // over the entire range [0, numeric_limits<size_t>:::max()].

  64. 

  65.   // _H2: the range-hashing function (in the terminology of Tavori and

  66.   // Dreizin).  A binary function object whose argument types and result

  67.   // type are all size_t.  Given arguments r and N, the return value is

  68.   // in the range [0, N).

  69. 

  70.   // _Hash: the ranged hash function (Tavori and Dreizin). A binary function

  71.   // whose argument types are _Key and size_t and whose result type is

  72.   // size_t.  Given arguments k and N, the return value is in the range

  73.   // [0, N).  Default: hash(k, N) = h2(h1(k), N).  If _Hash is anything other

  74.   // than the default, _H1 and _H2 are ignored.

  75. 

  76.   // _RehashPolicy: Policy class with three members, all of which govern

  77.   // the bucket count. _M_next_bkt(n) returns a bucket count no smaller

  78.   // than n.  _M_bkt_for_elements(n) returns a bucket count appropriate

  79.   // for an element count of n.  _M_need_rehash(n_bkt, n_elt, n_ins)

  80.   // determines whether, if the current bucket count is n_bkt and the

  81.   // current element count is n_elt, we need to increase the bucket

  82.   // count.  If so, returns make_pair(true, n), where n is the new

  83.   // bucket count.  If not, returns make_pair(false, <anything>).

  84. 

  85.   // ??? Right now it is hard-wired that the number of buckets never

  86.   // shrinks.  Should we allow _RehashPolicy to change that?

  87. 

  88.   // __cache_hash_code: bool.  true if we store the value of the hash

  89.   // function along with the value.  This is a time-space tradeoff.

  90.   // Storing it may improve lookup speed by reducing the number of times

  91.   // we need to call the Equal function.

  92. 

  93.   // __constant_iterators: bool.  true if iterator and const_iterator are

  94.   // both constant iterator types.  This is true for unordered_set and

  95.   // unordered_multiset, false for unordered_map and unordered_multimap.

  96. 

  97.   // __unique_keys: bool.  true if the return value of _Hashtable::count(k)

  98.   // is always at most one, false if it may be an arbitrary number.  This

  99.   // true for unordered_set and unordered_map, false for unordered_multiset

  100.   // and unordered_multimap.

  101. 

  102.   template<typename _Key, typename _Value, typename _Allocator,

  103. 	   typename _ExtractKey, typename _Equal,

  104. 	   typename _H1, typename _H2, typename _Hash,

  105. 	   typename _RehashPolicy,

  106. 	   bool __cache_hash_code,

  107. 	   bool __constant_iterators,

  108. 	   bool __unique_keys>

  109.     class _Hashtable

  110.     : public __detail::_Rehash_base<_RehashPolicy,

  111. 				    _Hashtable<_Key, _Value, _Allocator,

  112. 					       _ExtractKey,

  113. 					       _Equal, _H1, _H2, _Hash,

  114. 					       _RehashPolicy,

  115. 					       __cache_hash_code,

  116. 					       __constant_iterators,

  117. 					       __unique_keys> >,

  118.       public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,

  119. 				       _H1, _H2, _Hash, __cache_hash_code>,

  120.       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,

  121. 				 _Hashtable<_Key, _Value, _Allocator,

  122. 					    _ExtractKey,

  123. 					    _Equal, _H1, _H2, _Hash,

  124. 					    _RehashPolicy,

  125. 					    __cache_hash_code,

  126. 					    __constant_iterators,

  127. 					    __unique_keys> >

  128.     {

  129.       typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits;

  130. 

  131.     public:

  132.       typedef _Allocator                                  allocator_type;

  133.       typedef _Value                                      value_type;

  134.       typedef _Key                                        key_type;

  135.       typedef _Equal                                      key_equal;

  136.       // mapped_type, if present, comes from _Map_base.

  137.       // hasher, if present, comes from _Hash_code_base.

  138.       typedef typename _Allocator::difference_type        difference_type;

  139.       typedef typename _Allocator::size_type              size_type;

  140.       typedef typename _Alloc_traits::pointer             pointer;

  141.       typedef typename _Alloc_traits::const_pointer       const_pointer;

  142.       typedef typename _Alloc_traits::reference           reference;

  143.       typedef typename _Alloc_traits::const_reference     const_reference;

  144. 

  145.       typedef __detail::_Node_iterator<value_type, __constant_iterators,

  146. 				       __cache_hash_code>

  147. 							  local_iterator;

  148.       typedef __detail::_Node_const_iterator<value_type,

  149. 					     __constant_iterators,

  150. 					     __cache_hash_code>

  151. 							  const_local_iterator;

  152. 

  153.       typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,

  154. 					    __cache_hash_code>

  155. 							  iterator;

  156.       typedef __detail::_Hashtable_const_iterator<value_type,

  157. 						  __constant_iterators,

  158. 						  __cache_hash_code>

  159. 							  const_iterator;

  160. 

  161.       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,

  162. 	       typename _Hashtable2>

  163. 	friend struct __detail::_Map_base;

  164. 

  165.     private:

  166.       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;

  167.       typedef typename _Alloc_traits::template rebind<_Node>::other

  168. 						      _Node_allocator_type;

  169.       typedef typename _Alloc_traits::template rebind<_Node*>::other

  170. 						      _Bucket_allocator_type;

  171. 

  172.       typedef typename _Alloc_traits::template rebind<_Value>::other

  173. 						      _Value_allocator_type;

  174. 

  175.       _Node_allocator_type   _M_node_allocator;

  176.       _Node**                _M_buckets;

  177.       size_type              _M_bucket_count;

  178.       size_type              _M_element_count;

  179.       _RehashPolicy          _M_rehash_policy;

  180. 

  181.       _Node*

  182.       _M_allocate_node(const value_type& __v);

  183. 

  184.       void

  185.       _M_deallocate_node(_Node* __n);

  186. 

  187.       void

  188.       _M_deallocate_nodes(_Node**, size_type);

  189. 

  190.       _Node**

  191.       _M_allocate_buckets(size_type __n);

  192. 

  193.       void

  194.       _M_deallocate_buckets(_Node**, size_type __n);

  195. 

  196.     public:

  197.       // Constructor, destructor, assignment, swap

  198.       _Hashtable(size_type __bucket_hint,

  199. 		 const _H1&, const _H2&, const _Hash&,

  200. 		 const _Equal&, const _ExtractKey&,

  201. 		 const allocator_type&);

  202. 

  203.       template<typename _InputIterator>

  204. 	_Hashtable(_InputIterator __first, _InputIterator __last,

  205. 		   size_type __bucket_hint,

  206. 		   const _H1&, const _H2&, const _Hash&,

  207. 		   const _Equal&, const _ExtractKey&,

  208. 		   const allocator_type&);

  209. 

  210.       _Hashtable(const _Hashtable&);

  211. 

  212.       _Hashtable&

  213.       operator=(const _Hashtable&);

  214. 

  215.       ~_Hashtable();

  216. 

  217.       void swap(_Hashtable&);

  218. 

  219.       // Basic container operations

  220.       iterator

  221.       begin()

  222.       {

  223. 	iterator __i(_M_buckets);

  224. 	if (!__i._M_cur_node)

  225. 	  __i._M_incr_bucket();

  226. 	return __i;

  227.       }

  228. 

  229.       const_iterator

  230.       begin() const

  231.       {

  232. 	const_iterator __i(_M_buckets);

  233. 	if (!__i._M_cur_node)

  234. 	  __i._M_incr_bucket();

  235. 	return __i;

  236.       }

  237. 

  238.       iterator

  239.       end()

  240.       { return iterator(_M_buckets + _M_bucket_count); }

  241. 

  242.       const_iterator

  243.       end() const

  244.       { return const_iterator(_M_buckets + _M_bucket_count); }

  245. 

  246.       size_type

  247.       size() const

  248.       { return _M_element_count; }

  249. 

  250.       _GLIBCXX_NODISCARD bool

  251.       empty() const

  252.       { return size() == 0; }

  253. 

  254.       allocator_type

  255.       get_allocator() const

  256.       { return allocator_type(_M_node_allocator); }

  257. 

  258.       _Value_allocator_type

  259.       _M_get_Value_allocator() const

  260.       { return _Value_allocator_type(_M_node_allocator); }

  261. 

  262.       size_type

  263.       max_size() const

  264.       {

  265. 	typedef __gnu_cxx::__alloc_traits<_Node_allocator_type> _Traits;

  266. 	return _Traits::max_size(_M_node_allocator);

  267.       }

  268. 

  269.       // Observers

  270.       key_equal

  271.       key_eq() const

  272.       { return this->_M_eq; }

  273. 

  274.       // hash_function, if present, comes from _Hash_code_base.

  275. 

  276.       // Bucket operations

  277.       size_type

  278.       bucket_count() const

  279.       { return _M_bucket_count; }

  280. 

  281.       size_type

  282.       max_bucket_count() const

  283.       { return max_size(); }

  284. 

  285.       size_type

  286.       bucket_size(size_type __n) const

  287.       { return std::distance(begin(__n), end(__n)); }

  288. 

  289.       size_type

  290.       bucket(const key_type& __k) const

  291.       {

  292. 	return this->_M_bucket_index(__k, this->_M_hash_code(__k),

  293. 				     bucket_count());

  294.       }

  295. 

  296.       local_iterator

  297.       begin(size_type __n)

  298.       { return local_iterator(_M_buckets[__n]); }

  299. 

  300.       local_iterator

  301.       end(size_type)

  302.       { return local_iterator(0); }

  303. 

  304.       const_local_iterator

  305.       begin(size_type __n) const

  306.       { return const_local_iterator(_M_buckets[__n]); }

  307. 

  308.       const_local_iterator

  309.       end(size_type) const

  310.       { return const_local_iterator(0); }

  311. 

  312.       float

  313.       load_factor() const

  314.       {

  315. 	return static_cast<float>(size()) / static_cast<float>(bucket_count());

  316.       }

  317. 

  318.       // max_load_factor, if present, comes from _Rehash_base.

  319. 

  320.       // Generalization of max_load_factor.  Extension, not found in TR1.  Only

  321.       // useful if _RehashPolicy is something other than the default.

  322.       const _RehashPolicy&

  323.       __rehash_policy() const

  324.       { return _M_rehash_policy; }

  325. 

  326.       void

  327.       __rehash_policy(const _RehashPolicy&);

  328. 

  329.       // Lookup.

  330.       iterator

  331.       find(const key_type& __k);

  332. 

  333.       const_iterator

  334.       find(const key_type& __k) const;

  335. 

  336.       size_type

  337.       count(const key_type& __k) const;

  338. 

  339.       std::pair<iterator, iterator>

  340.       equal_range(const key_type& __k);

  341. 

  342.       std::pair<const_iterator, const_iterator>

  343.       equal_range(const key_type& __k) const;

  344. 

  345.     private:			// Find, insert and erase helper functions

  346.       // ??? This dispatching is a workaround for the fact that we don't

  347.       // have partial specialization of member templates; it would be

  348.       // better to just specialize insert on __unique_keys.  There may be a

  349.       // cleaner workaround.

  350.       typedef typename __gnu_cxx::__conditional_type<__unique_keys,

  351. 		       	    std::pair<iterator, bool>, iterator>::__type

  352. 	_Insert_Return_Type;

  353. 

  354.       typedef typename __gnu_cxx::__conditional_type<__unique_keys,

  355. 					  std::_Select1st<_Insert_Return_Type>,

  356. 				  	  std::_Identity<_Insert_Return_Type>

  357. 				   >::__type

  358. 	_Insert_Conv_Type;

  359. 

  360.       _Node*

  361.       _M_find_node(_Node*, const key_type&,

  362. 		   typename _Hashtable::_Hash_code_type) const;

  363. 

  364.       iterator

  365.       _M_insert_bucket(const value_type&, size_type,

  366. 		       typename _Hashtable::_Hash_code_type);

  367. 

  368.       std::pair<iterator, bool>

  369.       _M_insert(const value_type&, std::tr1::true_type);

  370. 

  371.       iterator

  372.       _M_insert(const value_type&, std::tr1::false_type);

  373. 

  374.       void

  375.       _M_erase_node(_Node*, _Node**);

  376. 

  377.     public:

  378.       // Insert and erase

  379.       _Insert_Return_Type

  380.       insert(const value_type& __v)

  381.       { return _M_insert(__v, std::tr1::integral_constant<bool,

  382. 			 __unique_keys>()); }

  383. 

  384.       iterator

  385.       insert(iterator, const value_type& __v)

  386.       { return iterator(_Insert_Conv_Type()(this->insert(__v))); }

  387. 

  388.       const_iterator

  389.       insert(const_iterator, const value_type& __v)

  390.       { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); }

  391. 

  392.       template<typename _InputIterator>

  393. 	void

  394. 	insert(_InputIterator __first, _InputIterator __last);

  395. 

  396.       iterator

  397.       erase(iterator);

  398. 

  399.       const_iterator

  400.       erase(const_iterator);

  401. 

  402.       size_type

  403.       erase(const key_type&);

  404. 

  405.       iterator

  406.       erase(iterator, iterator);

  407. 

  408.       const_iterator

  409.       erase(const_iterator, const_iterator);

  410. 

  411.       void

  412.       clear();

  413. 

  414.       // Set number of buckets to be appropriate for container of n element.

  415.       void rehash(size_type __n);

  416. 

  417.     private:

  418.       // Unconditionally change size of bucket array to n.

  419.       void _M_rehash(size_type __n);

  420.     };

  421. 

  422. 

  423.   // Definitions of class template _Hashtable's out-of-line member functions.

  424.   template<typename _Key, typename _Value,

  425. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  426. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  427. 	   bool __chc, bool __cit, bool __uk>

  428.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  429. 			_H1, _H2, _Hash, _RehashPolicy,

  430. 			__chc, __cit, __uk>::_Node*

  431.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  432. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  433.     _M_allocate_node(const value_type& __v)

  434.     {

  435.       _Node* __n = _M_node_allocator.allocate(1);

  436.       __try

  437. 	{

  438. 	  _Value_allocator_type __a = _M_get_Value_allocator();

  439. 	  typedef __gnu_cxx::__alloc_traits<_Value_allocator_type> _Traits;

  440. 	  _Traits::construct(__a, &__n->_M_v, __v);

  441. 	  __n->_M_next = 0;

  442. 	  return __n;

  443. 	}

  444.       __catch(...)

  445. 	{

  446. 	  _M_node_allocator.deallocate(__n, 1);

  447. 	  __throw_exception_again;

  448. 	}

  449.     }

  450. 

  451.   template<typename _Key, typename _Value,

  452. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  453. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  454. 	   bool __chc, bool __cit, bool __uk>

  455.     void

  456.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  457. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  458.     _M_deallocate_node(_Node* __n)

  459.     {

  460.       _Value_allocator_type __a = _M_get_Value_allocator();

  461.       typedef __gnu_cxx::__alloc_traits<_Value_allocator_type> _Traits;

  462.       _Traits::destroy(__a, &__n->_M_v);

  463.       _M_node_allocator.deallocate(__n, 1);

  464.     }

  465. 

  466.   template<typename _Key, typename _Value,

  467. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  468. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  469. 	   bool __chc, bool __cit, bool __uk>

  470.     void

  471.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  472. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  473.     _M_deallocate_nodes(_Node** __array, size_type __n)

  474.     {

  475.       for (size_type __i = 0; __i < __n; ++__i)

  476. 	{

  477. 	  _Node* __p = __array[__i];

  478. 	  while (__p)

  479. 	    {

  480. 	      _Node* __tmp = __p;

  481. 	      __p = __p->_M_next;

  482. 	      _M_deallocate_node(__tmp);

  483. 	    }

  484. 	  __array[__i] = 0;

  485. 	}

  486.     }

  487. 

  488.   template<typename _Key, typename _Value,

  489. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  490. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  491. 	   bool __chc, bool __cit, bool __uk>

  492.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  493. 			_H1, _H2, _Hash, _RehashPolicy,

  494. 			__chc, __cit, __uk>::_Node**

  495.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  496. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  497.     _M_allocate_buckets(size_type __n)

  498.     {

  499.       _Bucket_allocator_type __alloc(_M_node_allocator);

  500. 

  501.       // We allocate one extra bucket to hold a sentinel, an arbitrary

  502.       // non-null pointer.  Iterator increment relies on this.

  503.       _Node** __p = __alloc.allocate(__n + 1);

  504.       std::fill(__p, __p + __n, (_Node*) 0);

  505.       __p[__n] = reinterpret_cast<_Node*>(0x1000);

  506.       return __p;

  507.     }

  508. 

  509.   template<typename _Key, typename _Value,

  510. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  511. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  512. 	   bool __chc, bool __cit, bool __uk>

  513.     void

  514.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  515. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  516.     _M_deallocate_buckets(_Node** __p, size_type __n)

  517.     {

  518.       _Bucket_allocator_type __alloc(_M_node_allocator);

  519.       __alloc.deallocate(__p, __n + 1);

  520.     }

  521. 

  522.   template<typename _Key, typename _Value,

  523. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  524. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  525. 	   bool __chc, bool __cit, bool __uk>

  526.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  527. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  528.     _Hashtable(size_type __bucket_hint,

  529. 	       const _H1& __h1, const _H2& __h2, const _Hash& __h,

  530. 	       const _Equal& __eq, const _ExtractKey& __exk,

  531. 	       const allocator_type& __a)

  532.     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),

  533.       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,

  534. 				_H1, _H2, _Hash, __chc>(__exk, __eq,

  535. 							__h1, __h2, __h),

  536.       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),

  537.       _M_node_allocator(__a),

  538.       _M_bucket_count(0),

  539.       _M_element_count(0),

  540.       _M_rehash_policy()

  541.     {

  542.       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);

  543.       _M_buckets = _M_allocate_buckets(_M_bucket_count);

  544.     }

  545. 

  546.   template<typename _Key, typename _Value,

  547. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  548. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  549. 	   bool __chc, bool __cit, bool __uk>

  550.     template<typename _InputIterator>

  551.       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  552. 		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  553.       _Hashtable(_InputIterator __f, _InputIterator __l,

  554. 		 size_type __bucket_hint,

  555. 		 const _H1& __h1, const _H2& __h2, const _Hash& __h,

  556. 		 const _Equal& __eq, const _ExtractKey& __exk,

  557. 		 const allocator_type& __a)

  558.       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),

  559. 	__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,

  560. 				  _H1, _H2, _Hash, __chc>(__exk, __eq,

  561. 							  __h1, __h2, __h),

  562. 	__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),

  563. 	_M_node_allocator(__a),

  564. 	_M_bucket_count(0),

  565. 	_M_element_count(0),

  566. 	_M_rehash_policy()

  567.       {

  568. 	_M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),

  569. 				   _M_rehash_policy.

  570. 				   _M_bkt_for_elements(__detail::

  571. 						       __distance_fw(__f,

  572. 								     __l)));

  573. 	_M_buckets = _M_allocate_buckets(_M_bucket_count);

  574. 	__try

  575. 	  {

  576. 	    for (; __f != __l; ++__f)

  577. 	      this->insert(*__f);

  578. 	  }

  579. 	__catch(...)

  580. 	  {

  581. 	    clear();

  582. 	    _M_deallocate_buckets(_M_buckets, _M_bucket_count);

  583. 	    __throw_exception_again;

  584. 	  }

  585.       }

  586. 

  587.   template<typename _Key, typename _Value,

  588. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  589. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  590. 	   bool __chc, bool __cit, bool __uk>

  591.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  592. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  593.     _Hashtable(const _Hashtable& __ht)

  594.     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),

  595.       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,

  596. 				_H1, _H2, _Hash, __chc>(__ht),

  597.       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),

  598.       _M_node_allocator(__ht._M_node_allocator),

  599.       _M_bucket_count(__ht._M_bucket_count),

  600.       _M_element_count(__ht._M_element_count),

  601.       _M_rehash_policy(__ht._M_rehash_policy)

  602.     {

  603.       _M_buckets = _M_allocate_buckets(_M_bucket_count);

  604.       __try

  605. 	{

  606. 	  for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)

  607. 	    {

  608. 	      _Node* __n = __ht._M_buckets[__i];

  609. 	      _Node** __tail = _M_buckets + __i;

  610. 	      while (__n)

  611. 		{

  612. 		  *__tail = _M_allocate_node(__n->_M_v);

  613. 		  this->_M_copy_code(*__tail, __n);

  614. 		  __tail = &((*__tail)->_M_next);

  615. 		  __n = __n->_M_next;

  616. 		}

  617. 	    }

  618. 	}

  619.       __catch(...)

  620. 	{

  621. 	  clear();

  622. 	  _M_deallocate_buckets(_M_buckets, _M_bucket_count);

  623. 	  __throw_exception_again;

  624. 	}

  625.     }

  626. 

  627.   template<typename _Key, typename _Value,

  628. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  629. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  630. 	   bool __chc, bool __cit, bool __uk>

  631.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  632. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>&

  633.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  634. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  635.     operator=(const _Hashtable& __ht)

  636.     {

  637.       _Hashtable __tmp(__ht);

  638.       this->swap(__tmp);

  639.       return *this;

  640.     }

  641. 

  642.   template<typename _Key, typename _Value,

  643. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  644. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  645. 	   bool __chc, bool __cit, bool __uk>

  646.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  647. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  648.     ~_Hashtable()

  649.     {

  650.       clear();

  651.       _M_deallocate_buckets(_M_buckets, _M_bucket_count);

  652.     }

  653. 

  654.   template<typename _Key, typename _Value,

  655. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  656. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  657. 	   bool __chc, bool __cit, bool __uk>

  658.     void

  659.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  660. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  661.     swap(_Hashtable& __x)

  662.     {

  663.       // The only base class with member variables is hash_code_base.  We

  664.       // define _Hash_code_base::_M_swap because different specializations

  665.       // have different members.

  666.       __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,

  667. 	_H1, _H2, _Hash, __chc>::_M_swap(__x);

  668. 

  669.       // _GLIBCXX_RESOLVE_LIB_DEFECTS

  670.       // 431. Swapping containers with unequal allocators.

  671.       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,

  672. 							__x._M_node_allocator);

  673. 

  674.       std::swap(_M_rehash_policy, __x._M_rehash_policy);

  675.       std::swap(_M_buckets, __x._M_buckets);

  676.       std::swap(_M_bucket_count, __x._M_bucket_count);

  677.       std::swap(_M_element_count, __x._M_element_count);

  678.     }

  679. 

  680.   template<typename _Key, typename _Value,

  681. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  682. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  683. 	   bool __chc, bool __cit, bool __uk>

  684.     void

  685.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  686. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  687.     __rehash_policy(const _RehashPolicy& __pol)

  688.     {

  689.       _M_rehash_policy = __pol;

  690.       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);

  691.       if (__n_bkt > _M_bucket_count)

  692. 	_M_rehash(__n_bkt);

  693.     }

  694. 

  695.   template<typename _Key, typename _Value,

  696. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  697. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  698. 	   bool __chc, bool __cit, bool __uk>

  699.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  700. 			_H1, _H2, _Hash, _RehashPolicy,

  701. 			__chc, __cit, __uk>::iterator

  702.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  703. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  704.     find(const key_type& __k)

  705.     {

  706.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  707.       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  708.       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);

  709.       return __p ? iterator(__p, _M_buckets + __n) : this->end();

  710.     }

  711. 

  712.   template<typename _Key, typename _Value,

  713. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  714. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  715. 	   bool __chc, bool __cit, bool __uk>

  716.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  717. 			_H1, _H2, _Hash, _RehashPolicy,

  718. 			__chc, __cit, __uk>::const_iterator

  719.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  720. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  721.     find(const key_type& __k) const

  722.     {

  723.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  724.       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  725.       _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);

  726.       return __p ? const_iterator(__p, _M_buckets + __n) : this->end();

  727.     }

  728. 

  729.   template<typename _Key, typename _Value,

  730. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  731. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  732. 	   bool __chc, bool __cit, bool __uk>

  733.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  734. 			_H1, _H2, _Hash, _RehashPolicy,

  735. 			__chc, __cit, __uk>::size_type

  736.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  737. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  738.     count(const key_type& __k) const

  739.     {

  740.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  741.       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  742.       std::size_t __result = 0;

  743.       for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)

  744. 	if (this->_M_compare(__k, __code, __p))

  745. 	  ++__result;

  746.       return __result;

  747.     }

  748. 

  749.   template<typename _Key, typename _Value,

  750. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  751. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  752. 	   bool __chc, bool __cit, bool __uk>

  753.     std::pair<typename _Hashtable<_Key, _Value, _Allocator,

  754. 				  _ExtractKey, _Equal, _H1,

  755. 				  _H2, _Hash, _RehashPolicy,

  756. 				  __chc, __cit, __uk>::iterator,

  757. 	      typename _Hashtable<_Key, _Value, _Allocator,

  758. 				  _ExtractKey, _Equal, _H1,

  759. 				  _H2, _Hash, _RehashPolicy,

  760. 				  __chc, __cit, __uk>::iterator>

  761.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  762. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  763.     equal_range(const key_type& __k)

  764.     {

  765.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  766.       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  767.       _Node** __head = _M_buckets + __n;

  768.       _Node* __p = _M_find_node(*__head, __k, __code);

  769. 

  770.       if (__p)

  771. 	{

  772. 	  _Node* __p1 = __p->_M_next;

  773. 	  for (; __p1; __p1 = __p1->_M_next)

  774. 	    if (!this->_M_compare(__k, __code, __p1))

  775. 	      break;

  776. 

  777. 	  iterator __first(__p, __head);

  778. 	  iterator __last(__p1, __head);

  779. 	  if (!__p1)

  780. 	    __last._M_incr_bucket();

  781. 	  return std::make_pair(__first, __last);

  782. 	}

  783.       else

  784. 	return std::make_pair(this->end(), this->end());

  785.     }

  786. 

  787.   template<typename _Key, typename _Value,

  788. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  789. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  790. 	   bool __chc, bool __cit, bool __uk>

  791.     std::pair<typename _Hashtable<_Key, _Value, _Allocator,

  792. 				  _ExtractKey, _Equal, _H1,

  793. 				  _H2, _Hash, _RehashPolicy,

  794. 				  __chc, __cit, __uk>::const_iterator,

  795. 	      typename _Hashtable<_Key, _Value, _Allocator,

  796. 				  _ExtractKey, _Equal, _H1,

  797. 				  _H2, _Hash, _RehashPolicy,

  798. 				  __chc, __cit, __uk>::const_iterator>

  799.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  800. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  801.     equal_range(const key_type& __k) const

  802.     {

  803.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  804.       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  805.       _Node** __head = _M_buckets + __n;

  806.       _Node* __p = _M_find_node(*__head, __k, __code);

  807. 

  808.       if (__p)

  809. 	{

  810. 	  _Node* __p1 = __p->_M_next;

  811. 	  for (; __p1; __p1 = __p1->_M_next)

  812. 	    if (!this->_M_compare(__k, __code, __p1))

  813. 	      break;

  814. 

  815. 	  const_iterator __first(__p, __head);

  816. 	  const_iterator __last(__p1, __head);

  817. 	  if (!__p1)

  818. 	    __last._M_incr_bucket();

  819. 	  return std::make_pair(__first, __last);

  820. 	}

  821.       else

  822. 	return std::make_pair(this->end(), this->end());

  823.     }

  824. 

  825.   // Find the node whose key compares equal to k, beginning the search

  826.   // at p (usually the head of a bucket).  Return zero if no node is found.

  827.   template<typename _Key, typename _Value,

  828. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  829. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  830. 	   bool __chc, bool __cit, bool __uk>

  831.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,

  832. 			_Equal, _H1, _H2, _Hash, _RehashPolicy,

  833. 			__chc, __cit, __uk>::_Node*

  834.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  835. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  836.     _M_find_node(_Node* __p, const key_type& __k,

  837. 		typename _Hashtable::_Hash_code_type __code) const

  838.     {

  839.       for (; __p; __p = __p->_M_next)

  840. 	if (this->_M_compare(__k, __code, __p))

  841. 	  return __p;

  842.       return 0;

  843.     }

  844. 

  845.   // Insert v in bucket n (assumes no element with its key already present).

  846.   template<typename _Key, typename _Value,

  847. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  848. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  849. 	   bool __chc, bool __cit, bool __uk>

  850.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  851. 			_H1, _H2, _Hash, _RehashPolicy,

  852. 			__chc, __cit, __uk>::iterator

  853.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  854. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  855.     _M_insert_bucket(const value_type& __v, size_type __n,

  856. 		    typename _Hashtable::_Hash_code_type __code)

  857.     {

  858.       std::pair<bool, std::size_t> __do_rehash

  859. 	= _M_rehash_policy._M_need_rehash(_M_bucket_count,

  860. 					  _M_element_count, 1);

  861. 

  862.       // Allocate the new node before doing the rehash so that we don't

  863.       // do a rehash if the allocation throws.

  864.       _Node* __new_node = _M_allocate_node(__v);

  865. 

  866.       __try

  867. 	{

  868. 	  if (__do_rehash.first)

  869. 	    {

  870. 	      const key_type& __k = this->_M_extract(__v);

  871. 	      __n = this->_M_bucket_index(__k, __code, __do_rehash.second);

  872. 	      _M_rehash(__do_rehash.second);

  873. 	    }

  874. 

  875. 	  __new_node->_M_next = _M_buckets[__n];

  876. 	  this->_M_store_code(__new_node, __code);

  877. 	  _M_buckets[__n] = __new_node;

  878. 	  ++_M_element_count;

  879. 	  return iterator(__new_node, _M_buckets + __n);

  880. 	}

  881.       __catch(...)

  882. 	{

  883. 	  _M_deallocate_node(__new_node);

  884. 	  __throw_exception_again;

  885. 	}

  886.     }

  887. 

  888.   // Insert v if no element with its key is already present.

  889.   template<typename _Key, typename _Value,

  890. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  891. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  892. 	   bool __chc, bool __cit, bool __uk>

  893.     std::pair<typename _Hashtable<_Key, _Value, _Allocator,

  894. 				  _ExtractKey, _Equal, _H1,

  895. 				  _H2, _Hash, _RehashPolicy,

  896. 				  __chc, __cit, __uk>::iterator, bool>

  897.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  898. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  899.   _M_insert(const value_type& __v, std::tr1::true_type)

  900.     {

  901.       const key_type& __k = this->_M_extract(__v);

  902.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  903.       size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  904. 

  905.       if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))

  906. 	return std::make_pair(iterator(__p, _M_buckets + __n), false);

  907.       return std::make_pair(_M_insert_bucket(__v, __n, __code), true);

  908.     }

  909. 

  910.   // Insert v unconditionally.

  911.   template<typename _Key, typename _Value,

  912. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  913. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  914. 	   bool __chc, bool __cit, bool __uk>

  915.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  916. 			_H1, _H2, _Hash, _RehashPolicy,

  917. 			__chc, __cit, __uk>::iterator

  918.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  919. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  920.     _M_insert(const value_type& __v, std::tr1::false_type)

  921.     {

  922.       std::pair<bool, std::size_t> __do_rehash

  923. 	= _M_rehash_policy._M_need_rehash(_M_bucket_count,

  924. 					  _M_element_count, 1);

  925.       if (__do_rehash.first)

  926. 	_M_rehash(__do_rehash.second);

  927. 

  928.       const key_type& __k = this->_M_extract(__v);

  929.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  930.       size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  931. 

  932.       // First find the node, avoid leaking new_node if compare throws.

  933.       _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);

  934.       _Node* __new_node = _M_allocate_node(__v);

  935. 

  936.       if (__prev)

  937. 	{

  938. 	  __new_node->_M_next = __prev->_M_next;

  939. 	  __prev->_M_next = __new_node;

  940. 	}

  941.       else

  942. 	{

  943. 	  __new_node->_M_next = _M_buckets[__n];

  944. 	  _M_buckets[__n] = __new_node;

  945. 	}

  946.       this->_M_store_code(__new_node, __code);

  947. 

  948.       ++_M_element_count;

  949.       return iterator(__new_node, _M_buckets + __n);

  950.     }

  951. 

  952.   // For erase(iterator) and erase(const_iterator).

  953.   template<typename _Key, typename _Value,

  954. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  955. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  956. 	   bool __chc, bool __cit, bool __uk>

  957.     void

  958.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  959. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  960.     _M_erase_node(_Node* __p, _Node** __b)

  961.     {

  962.       _Node* __cur = *__b;

  963.       if (__cur == __p)

  964. 	*__b = __cur->_M_next;

  965.       else

  966. 	{

  967. 	  _Node* __next = __cur->_M_next;

  968. 	  while (__next != __p)

  969. 	    {

  970. 	      __cur = __next;

  971. 	      __next = __cur->_M_next;

  972. 	    }

  973. 	  __cur->_M_next = __next->_M_next;

  974. 	}

  975. 

  976.       _M_deallocate_node(__p);

  977.       --_M_element_count;

  978.     }

  979. 

  980.   template<typename _Key, typename _Value,

  981. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  982. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  983. 	   bool __chc, bool __cit, bool __uk>

  984.     template<typename _InputIterator>

  985.       void

  986.       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  987. 		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  988.       insert(_InputIterator __first, _InputIterator __last)

  989.       {

  990. 	size_type __n_elt = __detail::__distance_fw(__first, __last);

  991. 	std::pair<bool, std::size_t> __do_rehash

  992. 	  = _M_rehash_policy._M_need_rehash(_M_bucket_count,

  993. 					    _M_element_count, __n_elt);

  994. 	if (__do_rehash.first)

  995. 	  _M_rehash(__do_rehash.second);

  996. 

  997. 	for (; __first != __last; ++__first)

  998. 	  this->insert(*__first);

  999.       }

  1000. 

  1001.   template<typename _Key, typename _Value,

  1002. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1003. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1004. 	   bool __chc, bool __cit, bool __uk>

  1005.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1006. 			_H1, _H2, _Hash, _RehashPolicy,

  1007. 			__chc, __cit, __uk>::iterator

  1008.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1009. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1010.     erase(iterator __it)

  1011.     {

  1012.       iterator __result = __it;

  1013.       ++__result;

  1014.       _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);

  1015.       return __result;

  1016.     }

  1017. 

  1018.   template<typename _Key, typename _Value,

  1019. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1020. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1021. 	   bool __chc, bool __cit, bool __uk>

  1022.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1023. 			_H1, _H2, _Hash, _RehashPolicy,

  1024. 			__chc, __cit, __uk>::const_iterator

  1025.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1026. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1027.     erase(const_iterator __it)

  1028.     {

  1029.       const_iterator __result = __it;

  1030.       ++__result;

  1031.       _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);

  1032.       return __result;

  1033.     }

  1034. 

  1035.   template<typename _Key, typename _Value,

  1036. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1037. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1038. 	   bool __chc, bool __cit, bool __uk>

  1039.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1040. 			_H1, _H2, _Hash, _RehashPolicy,

  1041. 			__chc, __cit, __uk>::size_type

  1042.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1043. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1044.     erase(const key_type& __k)

  1045.     {

  1046.       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);

  1047.       std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);

  1048.       size_type __result = 0;

  1049. 

  1050.       _Node** __slot = _M_buckets + __n;

  1051.       while (*__slot && !this->_M_compare(__k, __code, *__slot))

  1052. 	__slot = &((*__slot)->_M_next);

  1053. 

  1054.       _Node** __saved_slot = 0;

  1055.       while (*__slot && this->_M_compare(__k, __code, *__slot))

  1056. 	{

  1057. 	  // _GLIBCXX_RESOLVE_LIB_DEFECTS

  1058. 	  // 526. Is it undefined if a function in the standard changes

  1059. 	  // in parameters?

  1060. 	  if (&this->_M_extract((*__slot)->_M_v) != &__k)

  1061. 	    {

  1062. 	      _Node* __p = *__slot;

  1063. 	      *__slot = __p->_M_next;

  1064. 	      _M_deallocate_node(__p);

  1065. 	      --_M_element_count;

  1066. 	      ++__result;

  1067. 	    }

  1068. 	  else

  1069. 	    {

  1070. 	      __saved_slot = __slot;

  1071. 	      __slot = &((*__slot)->_M_next);

  1072. 	    }

  1073. 	}

  1074. 

  1075.       if (__saved_slot)

  1076. 	{

  1077. 	  _Node* __p = *__saved_slot;

  1078. 	  *__saved_slot = __p->_M_next;

  1079. 	  _M_deallocate_node(__p);

  1080. 	  --_M_element_count;

  1081. 	  ++__result;

  1082. 	}

  1083. 

  1084.       return __result;

  1085.     }

  1086. 

  1087.   // ??? This could be optimized by taking advantage of the bucket

  1088.   // structure, but it's not clear that it's worth doing.  It probably

  1089.   // wouldn't even be an optimization unless the load factor is large.

  1090.   template<typename _Key, typename _Value,

  1091. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1092. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1093. 	   bool __chc, bool __cit, bool __uk>

  1094.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1095. 			_H1, _H2, _Hash, _RehashPolicy,

  1096. 			__chc, __cit, __uk>::iterator

  1097.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1098. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1099.     erase(iterator __first, iterator __last)

  1100.     {

  1101.       while (__first != __last)

  1102. 	__first = this->erase(__first);

  1103.       return __last;

  1104.     }

  1105. 

  1106.   template<typename _Key, typename _Value,

  1107. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1108. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1109. 	   bool __chc, bool __cit, bool __uk>

  1110.     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1111. 			_H1, _H2, _Hash, _RehashPolicy,

  1112. 			__chc, __cit, __uk>::const_iterator

  1113.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1114. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1115.     erase(const_iterator __first, const_iterator __last)

  1116.     {

  1117.       while (__first != __last)

  1118. 	__first = this->erase(__first);

  1119.       return __last;

  1120.     }

  1121. 

  1122.   template<typename _Key, typename _Value,

  1123. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1124. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1125. 	   bool __chc, bool __cit, bool __uk>

  1126.     void

  1127.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1128. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1129.     clear()

  1130.     {

  1131.       _M_deallocate_nodes(_M_buckets, _M_bucket_count);

  1132.       _M_element_count = 0;

  1133.     }

  1134. 

  1135.   template<typename _Key, typename _Value,

  1136. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1137. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1138. 	   bool __chc, bool __cit, bool __uk>

  1139.     void

  1140.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1141. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1142.     rehash(size_type __n)

  1143.     {

  1144.       _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),

  1145. 			 _M_rehash_policy._M_bkt_for_elements(_M_element_count

  1146. 							      + 1)));

  1147.     }

  1148. 

  1149.   template<typename _Key, typename _Value,

  1150. 	   typename _Allocator, typename _ExtractKey, typename _Equal,

  1151. 	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,

  1152. 	   bool __chc, bool __cit, bool __uk>

  1153.     void

  1154.     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,

  1155. 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::

  1156.     _M_rehash(size_type __n)

  1157.     {

  1158.       _Node** __new_array = _M_allocate_buckets(__n);

  1159.       __try

  1160. 	{

  1161. 	  for (size_type __i = 0; __i < _M_bucket_count; ++__i)

  1162. 	    while (_Node* __p = _M_buckets[__i])

  1163. 	      {

  1164. 		std::size_t __new_index = this->_M_bucket_index(__p, __n);

  1165. 		_M_buckets[__i] = __p->_M_next;

  1166. 		__p->_M_next = __new_array[__new_index];

  1167. 		__new_array[__new_index] = __p;

  1168. 	      }

  1169. 	  _M_deallocate_buckets(_M_buckets, _M_bucket_count);

  1170. 	  _M_bucket_count = __n;

  1171. 	  _M_buckets = __new_array;

  1172. 	}

  1173.       __catch(...)

  1174. 	{

  1175. 	  // A failure here means that a hash function threw an exception.

  1176. 	  // We can't restore the previous state without calling the hash

  1177. 	  // function again, so the only sensible recovery is to delete

  1178. 	  // everything.

  1179. 	  _M_deallocate_nodes(__new_array, __n);

  1180. 	  _M_deallocate_buckets(__new_array, __n);

  1181. 	  _M_deallocate_nodes(_M_buckets, _M_bucket_count);

  1182. 	  _M_element_count = 0;

  1183. 	  __throw_exception_again;

  1184. 	}

  1185.     }

  1186. } // namespace tr1

  1187. 

  1188. _GLIBCXX_END_NAMESPACE_VERSION

  1189. } // namespace std

  1190. 

  1191. #endif // _GLIBCXX_TR1_HASHTABLE_H