1 // TR1 hashtable.h header -*- C++ -*-
2
3 // Copyright (C) 2007-2022 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @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
_GLIBCXX_VISIBILITY(default)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
1192