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