?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
GUI: Fix Tomato RAF theme for all builds. Compilation typo.
[tomato.git] / release / src-rt-6.x.4708 / toolchains / hndtools-arm-linux-2.6.36-uclibc-4.5.3 / arm-brcm-linux-uclibcgnueabi / include / c++ / 4.5.3 / bits / hashtable.h
blobc7aceb19f8e7c3342552ccbfd8c80a58d1a92b8f
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_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(_Hashtable&&);
213
214 _Hashtable&
215 operator=(const _Hashtable&);
216
217 ~_Hashtable();
218
219 void swap(_Hashtable&);
220
221 // Basic container operations
222 iterator
223 begin()
224 {
225 iterator __i(_M_buckets);
226 if (!__i._M_cur_node)
227 __i._M_incr_bucket();
228 return __i;
229 }
230
231 const_iterator
232 begin() const
233 {
234 const_iterator __i(_M_buckets);
235 if (!__i._M_cur_node)
236 __i._M_incr_bucket();
237 return __i;
238 }
239
240 iterator
241 end()
242 { return iterator(_M_buckets + _M_bucket_count); }
243
244 const_iterator
245 end() const
246 { return const_iterator(_M_buckets + _M_bucket_count); }
247
248 const_iterator
249 cbegin() const
250 {
251 const_iterator __i(_M_buckets);
252 if (!__i._M_cur_node)
253 __i._M_incr_bucket();
254 return __i;
255 }
256
257 const_iterator
258 cend() const
259 { return const_iterator(_M_buckets + _M_bucket_count); }
260
261 size_type
262 size() const
263 { return _M_element_count; }
264
265 bool
266 empty() const
267 { return size() == 0; }
268
269 allocator_type
270 get_allocator() const
271 { return allocator_type(_M_node_allocator); }
272
273 _Value_allocator_type
274 _M_get_Value_allocator() const
275 { return _Value_allocator_type(_M_node_allocator); }
276
277 size_type
278 max_size() const
279 { return _M_node_allocator.max_size(); }
280
281 // Observers
282 key_equal
283 key_eq() const
284 { return this->_M_eq; }
285
286 // hash_function, if present, comes from _Hash_code_base.
287
288 // Bucket operations
289 size_type
290 bucket_count() const
291 { return _M_bucket_count; }
292
293 size_type
294 max_bucket_count() const
295 { return max_size(); }
296
297 size_type
298 bucket_size(size_type __n) const
299 { return std::distance(begin(__n), end(__n)); }
300
301 size_type
302 bucket(const key_type& __k) const
303 {
304 return this->_M_bucket_index(__k, this->_M_hash_code(__k),
305 bucket_count());
306 }
307
308 local_iterator
309 begin(size_type __n)
310 { return local_iterator(_M_buckets[__n]); }
311
312 local_iterator
313 end(size_type)
314 { return local_iterator(0); }
315
316 const_local_iterator
317 begin(size_type __n) const
318 { return const_local_iterator(_M_buckets[__n]); }
319
320 const_local_iterator
321 end(size_type) const
322 { return const_local_iterator(0); }
323
324 // DR 691.
325 const_local_iterator
326 cbegin(size_type __n) const
327 { return const_local_iterator(_M_buckets[__n]); }
328
329 const_local_iterator
330 cend(size_type) const
331 { return const_local_iterator(0); }
332
333 float
334 load_factor() const
335 {
336 return static_cast<float>(size()) / static_cast<float>(bucket_count());
337 }
338
339 // max_load_factor, if present, comes from _Rehash_base.
340
341 // Generalization of max_load_factor. Extension, not found in TR1. Only
342 // useful if _RehashPolicy is something other than the default.
343 const _RehashPolicy&
344 __rehash_policy() const
345 { return _M_rehash_policy; }
346
347 void
348 __rehash_policy(const _RehashPolicy&);
349
350 // Lookup.
351 iterator
352 find(const key_type& __k);
353
354 const_iterator
355 find(const key_type& __k) const;
356
357 size_type
358 count(const key_type& __k) const;
359
360 std::pair<iterator, iterator>
361 equal_range(const key_type& __k);
362
363 std::pair<const_iterator, const_iterator>
364 equal_range(const key_type& __k) const;
365
366 private: // Find, insert and erase helper functions
367 // ??? This dispatching is a workaround for the fact that we don't
368 // have partial specialization of member templates; it would be
369 // better to just specialize insert on __unique_keys. There may be a
370 // cleaner workaround.
371 typedef typename std::conditional<__unique_keys,
372 std::pair<iterator, bool>,
373 iterator>::type
374 _Insert_Return_Type;
375
376 typedef typename std::conditional<__unique_keys,
377 std::_Select1st<_Insert_Return_Type>,
378 std::_Identity<_Insert_Return_Type>
379 >::type
380 _Insert_Conv_Type;
381
382 _Node*
383 _M_find_node(_Node*, const key_type&,
384 typename _Hashtable::_Hash_code_type) const;
385
386 iterator
387 _M_insert_bucket(const value_type&, size_type,
388 typename _Hashtable::_Hash_code_type);
389
390 std::pair<iterator, bool>
391 _M_insert(const value_type&, std::true_type);
392
393 iterator
394 _M_insert(const value_type&, std::false_type);
395
396 void
397 _M_erase_node(_Node*, _Node**);
398
399 public:
400 // Insert and erase
401 _Insert_Return_Type
402 insert(const value_type& __v)
403 { return _M_insert(__v, std::integral_constant<bool,
404 __unique_keys>()); }
405
406 iterator
407 insert(const_iterator, const value_type& __v)
408 { return iterator(_Insert_Conv_Type()(this->insert(__v))); }
409
410 template<typename _InputIterator>
411 void
412 insert(_InputIterator __first, _InputIterator __last);
413
414 void
415 insert(initializer_list<value_type> __l)
416 { this->insert(__l.begin(), __l.end()); }
417
418 iterator
419 erase(const_iterator);
420
421 size_type
422 erase(const key_type&);
423
424 iterator
425 erase(const_iterator, const_iterator);
426
427 void
428 clear();
429
430 // Set number of buckets to be appropriate for container of n element.
431 void rehash(size_type __n);
432
433 // DR 1189.
434 // reserve, if present, comes from _Rehash_base.
435
436 private:
437 // Unconditionally change size of bucket array to n.
438 void _M_rehash(size_type __n);
439 };
440
441
442 // Definitions of class template _Hashtable's out-of-line member functions.
443 template<typename _Key, typename _Value,
444 typename _Allocator, typename _ExtractKey, typename _Equal,
445 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
446 bool __chc, bool __cit, bool __uk>
447 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
448 _H1, _H2, _Hash, _RehashPolicy,
449 __chc, __cit, __uk>::_Node*
450 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
451 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
452 _M_allocate_node(const value_type& __v)
453 {
454 _Node* __n = _M_node_allocator.allocate(1);
455 __try
456 {
457 _M_node_allocator.construct(__n, __v);
458 __n->_M_next = 0;
459 return __n;
460 }
461 __catch(...)
462 {
463 _M_node_allocator.deallocate(__n, 1);
464 __throw_exception_again;
465 }
466 }
467
468 template<typename _Key, typename _Value,
469 typename _Allocator, typename _ExtractKey, typename _Equal,
470 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
471 bool __chc, bool __cit, bool __uk>
472 void
473 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
474 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
475 _M_deallocate_node(_Node* __n)
476 {
477 _M_node_allocator.destroy(__n);
478 _M_node_allocator.deallocate(__n, 1);
479 }
480
481 template<typename _Key, typename _Value,
482 typename _Allocator, typename _ExtractKey, typename _Equal,
483 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
484 bool __chc, bool __cit, bool __uk>
485 void
486 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
487 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
488 _M_deallocate_nodes(_Node** __array, size_type __n)
489 {
490 for (size_type __i = 0; __i < __n; ++__i)
491 {
492 _Node* __p = __array[__i];
493 while (__p)
494 {
495 _Node* __tmp = __p;
496 __p = __p->_M_next;
497 _M_deallocate_node(__tmp);
498 }
499 __array[__i] = 0;
500 }
501 }
502
503 template<typename _Key, typename _Value,
504 typename _Allocator, typename _ExtractKey, typename _Equal,
505 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
506 bool __chc, bool __cit, bool __uk>
507 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
508 _H1, _H2, _Hash, _RehashPolicy,
509 __chc, __cit, __uk>::_Node**
510 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
511 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
512 _M_allocate_buckets(size_type __n)
513 {
514 _Bucket_allocator_type __alloc(_M_node_allocator);
515
516 // We allocate one extra bucket to hold a sentinel, an arbitrary
517 // non-null pointer. Iterator increment relies on this.
518 _Node** __p = __alloc.allocate(__n + 1);
519 std::fill(__p, __p + __n, (_Node*) 0);
520 __p[__n] = reinterpret_cast<_Node*>(0x1000);
521 return __p;
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 void
529 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
530 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
531 _M_deallocate_buckets(_Node** __p, size_type __n)
532 {
533 _Bucket_allocator_type __alloc(_M_node_allocator);
534 __alloc.deallocate(__p, __n + 1);
535 }
536
537 template<typename _Key, typename _Value,
538 typename _Allocator, typename _ExtractKey, typename _Equal,
539 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
540 bool __chc, bool __cit, bool __uk>
541 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
542 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
543 _Hashtable(size_type __bucket_hint,
544 const _H1& __h1, const _H2& __h2, const _Hash& __h,
545 const _Equal& __eq, const _ExtractKey& __exk,
546 const allocator_type& __a)
547 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
548 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
549 _H1, _H2, _Hash, __chc>(__exk, __eq,
550 __h1, __h2, __h),
551 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
552 _M_node_allocator(__a),
553 _M_bucket_count(0),
554 _M_element_count(0),
555 _M_rehash_policy()
556 {
557 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
558 _M_buckets = _M_allocate_buckets(_M_bucket_count);
559 }
560
561 template<typename _Key, typename _Value,
562 typename _Allocator, typename _ExtractKey, typename _Equal,
563 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
564 bool __chc, bool __cit, bool __uk>
565 template<typename _InputIterator>
566 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
567 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
568 _Hashtable(_InputIterator __f, _InputIterator __l,
569 size_type __bucket_hint,
570 const _H1& __h1, const _H2& __h2, const _Hash& __h,
571 const _Equal& __eq, const _ExtractKey& __exk,
572 const allocator_type& __a)
573 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
574 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
575 _H1, _H2, _Hash, __chc>(__exk, __eq,
576 __h1, __h2, __h),
577 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
578 _M_node_allocator(__a),
579 _M_bucket_count(0),
580 _M_element_count(0),
581 _M_rehash_policy()
582 {
583 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
584 _M_rehash_policy.
585 _M_bkt_for_elements(__detail::
586 __distance_fw(__f,
587 __l)));
588 _M_buckets = _M_allocate_buckets(_M_bucket_count);
589 __try
590 {
591 for (; __f != __l; ++__f)
592 this->insert(*__f);
593 }
594 __catch(...)
595 {
596 clear();
597 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
598 __throw_exception_again;
599 }
600 }
601
602 template<typename _Key, typename _Value,
603 typename _Allocator, typename _ExtractKey, typename _Equal,
604 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
605 bool __chc, bool __cit, bool __uk>
606 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
607 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
608 _Hashtable(const _Hashtable& __ht)
609 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
610 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
611 _H1, _H2, _Hash, __chc>(__ht),
612 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
613 _M_node_allocator(__ht._M_node_allocator),
614 _M_bucket_count(__ht._M_bucket_count),
615 _M_element_count(__ht._M_element_count),
616 _M_rehash_policy(__ht._M_rehash_policy)
617 {
618 _M_buckets = _M_allocate_buckets(_M_bucket_count);
619 __try
620 {
621 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
622 {
623 _Node* __n = __ht._M_buckets[__i];
624 _Node** __tail = _M_buckets + __i;
625 while (__n)
626 {
627 *__tail = _M_allocate_node(__n->_M_v);
628 this->_M_copy_code(*__tail, __n);
629 __tail = &((*__tail)->_M_next);
630 __n = __n->_M_next;
631 }
632 }
633 }
634 __catch(...)
635 {
636 clear();
637 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
638 __throw_exception_again;
639 }
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(_Hashtable&& __ht)
649 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
650 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
651 _H1, _H2, _Hash, __chc>(__ht),
652 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
653 _M_node_allocator(__ht._M_node_allocator),
654 _M_bucket_count(__ht._M_bucket_count),
655 _M_element_count(__ht._M_element_count),
656 _M_rehash_policy(__ht._M_rehash_policy),
657 _M_buckets(__ht._M_buckets)
658 {
659 size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0);
660 __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt);
661 __ht._M_bucket_count = __n_bkt;
662 __ht._M_element_count = 0;
663 __ht._M_rehash_policy = _RehashPolicy();
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<_Key, _Value, _Allocator, _ExtractKey, _Equal,
673 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
674 operator=(const _Hashtable& __ht)
675 {
676 _Hashtable __tmp(__ht);
677 this->swap(__tmp);
678 return *this;
679 }
680
681 template<typename _Key, typename _Value,
682 typename _Allocator, typename _ExtractKey, typename _Equal,
683 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
684 bool __chc, bool __cit, bool __uk>
685 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
686 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
687 ~_Hashtable()
688 {
689 clear();
690 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
691 }
692
693 template<typename _Key, typename _Value,
694 typename _Allocator, typename _ExtractKey, typename _Equal,
695 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
696 bool __chc, bool __cit, bool __uk>
697 void
698 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
699 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
700 swap(_Hashtable& __x)
701 {
702 // The only base class with member variables is hash_code_base. We
703 // define _Hash_code_base::_M_swap because different specializations
704 // have different members.
705 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
706 _H1, _H2, _Hash, __chc>::_M_swap(__x);
707
708 // _GLIBCXX_RESOLVE_LIB_DEFECTS
709 // 431. Swapping containers with unequal allocators.
710 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
711 __x._M_node_allocator);
712
713 std::swap(_M_rehash_policy, __x._M_rehash_policy);
714 std::swap(_M_buckets, __x._M_buckets);
715 std::swap(_M_bucket_count, __x._M_bucket_count);
716 std::swap(_M_element_count, __x._M_element_count);
717 }
718
719 template<typename _Key, typename _Value,
720 typename _Allocator, typename _ExtractKey, typename _Equal,
721 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
722 bool __chc, bool __cit, bool __uk>
723 void
724 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
725 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
726 __rehash_policy(const _RehashPolicy& __pol)
727 {
728 _M_rehash_policy = __pol;
729 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
730 if (__n_bkt > _M_bucket_count)
731 _M_rehash(__n_bkt);
732 }
733
734 template<typename _Key, typename _Value,
735 typename _Allocator, typename _ExtractKey, typename _Equal,
736 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
737 bool __chc, bool __cit, bool __uk>
738 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
739 _H1, _H2, _Hash, _RehashPolicy,
740 __chc, __cit, __uk>::iterator
741 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
742 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
743 find(const key_type& __k)
744 {
745 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
746 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
747 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
748 return __p ? iterator(__p, _M_buckets + __n) : this->end();
749 }
750
751 template<typename _Key, typename _Value,
752 typename _Allocator, typename _ExtractKey, typename _Equal,
753 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
754 bool __chc, bool __cit, bool __uk>
755 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
756 _H1, _H2, _Hash, _RehashPolicy,
757 __chc, __cit, __uk>::const_iterator
758 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
759 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
760 find(const key_type& __k) const
761 {
762 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
763 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
764 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
765 return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
766 }
767
768 template<typename _Key, typename _Value,
769 typename _Allocator, typename _ExtractKey, typename _Equal,
770 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
771 bool __chc, bool __cit, bool __uk>
772 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
773 _H1, _H2, _Hash, _RehashPolicy,
774 __chc, __cit, __uk>::size_type
775 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
776 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
777 count(const key_type& __k) const
778 {
779 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
780 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
781 std::size_t __result = 0;
782 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
783 if (this->_M_compare(__k, __code, __p))
784 ++__result;
785 return __result;
786 }
787
788 template<typename _Key, typename _Value,
789 typename _Allocator, typename _ExtractKey, typename _Equal,
790 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
791 bool __chc, bool __cit, bool __uk>
792 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
793 _ExtractKey, _Equal, _H1,
794 _H2, _Hash, _RehashPolicy,
795 __chc, __cit, __uk>::iterator,
796 typename _Hashtable<_Key, _Value, _Allocator,
797 _ExtractKey, _Equal, _H1,
798 _H2, _Hash, _RehashPolicy,
799 __chc, __cit, __uk>::iterator>
800 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
801 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
802 equal_range(const key_type& __k)
803 {
804 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
805 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
806 _Node** __head = _M_buckets + __n;
807 _Node* __p = _M_find_node(*__head, __k, __code);
808
809 if (__p)
810 {
811 _Node* __p1 = __p->_M_next;
812 for (; __p1; __p1 = __p1->_M_next)
813 if (!this->_M_compare(__k, __code, __p1))
814 break;
815
816 iterator __first(__p, __head);
817 iterator __last(__p1, __head);
818 if (!__p1)
819 __last._M_incr_bucket();
820 return std::make_pair(__first, __last);
821 }
822 else
823 return std::make_pair(this->end(), this->end());
824 }
825
826 template<typename _Key, typename _Value,
827 typename _Allocator, typename _ExtractKey, typename _Equal,
828 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
829 bool __chc, bool __cit, bool __uk>
830 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
831 _ExtractKey, _Equal, _H1,
832 _H2, _Hash, _RehashPolicy,
833 __chc, __cit, __uk>::const_iterator,
834 typename _Hashtable<_Key, _Value, _Allocator,
835 _ExtractKey, _Equal, _H1,
836 _H2, _Hash, _RehashPolicy,
837 __chc, __cit, __uk>::const_iterator>
838 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
839 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
840 equal_range(const key_type& __k) const
841 {
842 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
843 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
844 _Node** __head = _M_buckets + __n;
845 _Node* __p = _M_find_node(*__head, __k, __code);
846
847 if (__p)
848 {
849 _Node* __p1 = __p->_M_next;
850 for (; __p1; __p1 = __p1->_M_next)
851 if (!this->_M_compare(__k, __code, __p1))
852 break;
853
854 const_iterator __first(__p, __head);
855 const_iterator __last(__p1, __head);
856 if (!__p1)
857 __last._M_incr_bucket();
858 return std::make_pair(__first, __last);
859 }
860 else
861 return std::make_pair(this->end(), this->end());
862 }
863
864 // Find the node whose key compares equal to k, beginning the search
865 // at p (usually the head of a bucket). Return nil if no node is found.
866 template<typename _Key, typename _Value,
867 typename _Allocator, typename _ExtractKey, typename _Equal,
868 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
869 bool __chc, bool __cit, bool __uk>
870 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
871 _Equal, _H1, _H2, _Hash, _RehashPolicy,
872 __chc, __cit, __uk>::_Node*
873 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
874 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
875 _M_find_node(_Node* __p, const key_type& __k,
876 typename _Hashtable::_Hash_code_type __code) const
877 {
878 for (; __p; __p = __p->_M_next)
879 if (this->_M_compare(__k, __code, __p))
880 return __p;
881 return false;
882 }
883
884 // Insert v in bucket n (assumes no element with its key already present).
885 template<typename _Key, typename _Value,
886 typename _Allocator, typename _ExtractKey, typename _Equal,
887 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
888 bool __chc, bool __cit, bool __uk>
889 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
890 _H1, _H2, _Hash, _RehashPolicy,
891 __chc, __cit, __uk>::iterator
892 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
893 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
894 _M_insert_bucket(const value_type& __v, size_type __n,
895 typename _Hashtable::_Hash_code_type __code)
896 {
897 std::pair<bool, std::size_t> __do_rehash
898 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
899 _M_element_count, 1);
900
901 // Allocate the new node before doing the rehash so that we don't
902 // do a rehash if the allocation throws.
903 _Node* __new_node = _M_allocate_node(__v);
904
905 __try
906 {
907 if (__do_rehash.first)
908 {
909 const key_type& __k = this->_M_extract(__v);
910 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
911 _M_rehash(__do_rehash.second);
912 }
913
914 __new_node->_M_next = _M_buckets[__n];
915 this->_M_store_code(__new_node, __code);
916 _M_buckets[__n] = __new_node;
917 ++_M_element_count;
918 return iterator(__new_node, _M_buckets + __n);
919 }
920 __catch(...)
921 {
922 _M_deallocate_node(__new_node);
923 __throw_exception_again;
924 }
925 }
926
927 // Insert v if no element with its key is already present.
928 template<typename _Key, typename _Value,
929 typename _Allocator, typename _ExtractKey, typename _Equal,
930 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
931 bool __chc, bool __cit, bool __uk>
932 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
933 _ExtractKey, _Equal, _H1,
934 _H2, _Hash, _RehashPolicy,
935 __chc, __cit, __uk>::iterator, bool>
936 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
937 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
938 _M_insert(const value_type& __v, std::true_type)
939 {
940 const key_type& __k = this->_M_extract(__v);
941 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
942 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
943
944 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
945 return std::make_pair(iterator(__p, _M_buckets + __n), false);
946 return std::make_pair(_M_insert_bucket(__v, __n, __code), true);
947 }
948
949 // Insert v unconditionally.
950 template<typename _Key, typename _Value,
951 typename _Allocator, typename _ExtractKey, typename _Equal,
952 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
953 bool __chc, bool __cit, bool __uk>
954 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
955 _H1, _H2, _Hash, _RehashPolicy,
956 __chc, __cit, __uk>::iterator
957 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
958 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
959 _M_insert(const value_type& __v, std::false_type)
960 {
961 std::pair<bool, std::size_t> __do_rehash
962 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
963 _M_element_count, 1);
964 if (__do_rehash.first)
965 _M_rehash(__do_rehash.second);
966
967 const key_type& __k = this->_M_extract(__v);
968 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
969 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
970
971 // First find the node, avoid leaking new_node if compare throws.
972 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
973 _Node* __new_node = _M_allocate_node(__v);
974
975 if (__prev)
976 {
977 __new_node->_M_next = __prev->_M_next;
978 __prev->_M_next = __new_node;
979 }
980 else
981 {
982 __new_node->_M_next = _M_buckets[__n];
983 _M_buckets[__n] = __new_node;
984 }
985 this->_M_store_code(__new_node, __code);
986
987 ++_M_element_count;
988 return iterator(__new_node, _M_buckets + __n);
989 }
990
991 // For erase(iterator) and erase(const_iterator).
992 template<typename _Key, typename _Value,
993 typename _Allocator, typename _ExtractKey, typename _Equal,
994 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
995 bool __chc, bool __cit, bool __uk>
996 void
997 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
998 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
999 _M_erase_node(_Node* __p, _Node** __b)
1000 {
1001 _Node* __cur = *__b;
1002 if (__cur == __p)
1003 *__b = __cur->_M_next;
1004 else
1005 {
1006 _Node* __next = __cur->_M_next;
1007 while (__next != __p)
1008 {
1009 __cur = __next;
1010 __next = __cur->_M_next;
1011 }
1012 __cur->_M_next = __next->_M_next;
1013 }
1014
1015 _M_deallocate_node(__p);
1016 --_M_element_count;
1017 }
1018
1019 template<typename _Key, typename _Value,
1020 typename _Allocator, typename _ExtractKey, typename _Equal,
1021 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1022 bool __chc, bool __cit, bool __uk>
1023 template<typename _InputIterator>
1024 void
1025 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1026 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1027 insert(_InputIterator __first, _InputIterator __last)
1028 {
1029 size_type __n_elt = __detail::__distance_fw(__first, __last);
1030 std::pair<bool, std::size_t> __do_rehash
1031 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1032 _M_element_count, __n_elt);
1033 if (__do_rehash.first)
1034 _M_rehash(__do_rehash.second);
1035
1036 for (; __first != __last; ++__first)
1037 this->insert(*__first);
1038 }
1039
1040 template<typename _Key, typename _Value,
1041 typename _Allocator, typename _ExtractKey, typename _Equal,
1042 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1043 bool __chc, bool __cit, bool __uk>
1044 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1045 _H1, _H2, _Hash, _RehashPolicy,
1046 __chc, __cit, __uk>::iterator
1047 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1048 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1049 erase(const_iterator __it)
1050 {
1051 iterator __result(__it._M_cur_node, __it._M_cur_bucket);
1052 ++__result;
1053 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
1054 return __result;
1055 }
1056
1057 template<typename _Key, typename _Value,
1058 typename _Allocator, typename _ExtractKey, typename _Equal,
1059 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1060 bool __chc, bool __cit, bool __uk>
1061 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1062 _H1, _H2, _Hash, _RehashPolicy,
1063 __chc, __cit, __uk>::size_type
1064 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1065 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1066 erase(const key_type& __k)
1067 {
1068 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1069 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1070 size_type __result = 0;
1071
1072 _Node** __slot = _M_buckets + __n;
1073 while (*__slot && !this->_M_compare(__k, __code, *__slot))
1074 __slot = &((*__slot)->_M_next);
1075
1076 _Node** __saved_slot = 0;
1077 while (*__slot && this->_M_compare(__k, __code, *__slot))
1078 {
1079 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1080 // 526. Is it undefined if a function in the standard changes
1081 // in parameters?
1082 if (&this->_M_extract((*__slot)->_M_v) != &__k)
1083 {
1084 _Node* __p = *__slot;
1085 *__slot = __p->_M_next;
1086 _M_deallocate_node(__p);
1087 --_M_element_count;
1088 ++__result;
1089 }
1090 else
1091 {
1092 __saved_slot = __slot;
1093 __slot = &((*__slot)->_M_next);
1094 }
1095 }
1096
1097 if (__saved_slot)
1098 {
1099 _Node* __p = *__saved_slot;
1100 *__saved_slot = __p->_M_next;
1101 _M_deallocate_node(__p);
1102 --_M_element_count;
1103 ++__result;
1104 }
1105
1106 return __result;
1107 }
1108
1109 // ??? This could be optimized by taking advantage of the bucket
1110 // structure, but it's not clear that it's worth doing. It probably
1111 // wouldn't even be an optimization unless the load factor is large.
1112 template<typename _Key, typename _Value,
1113 typename _Allocator, typename _ExtractKey, typename _Equal,
1114 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1115 bool __chc, bool __cit, bool __uk>
1116 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1117 _H1, _H2, _Hash, _RehashPolicy,
1118 __chc, __cit, __uk>::iterator
1119 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1120 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1121 erase(const_iterator __first, const_iterator __last)
1122 {
1123 while (__first != __last)
1124 __first = this->erase(__first);
1125 return iterator(__last._M_cur_node, __last._M_cur_bucket);
1126 }
1127
1128 template<typename _Key, typename _Value,
1129 typename _Allocator, typename _ExtractKey, typename _Equal,
1130 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1131 bool __chc, bool __cit, bool __uk>
1132 void
1133 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1134 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1135 clear()
1136 {
1137 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1138 _M_element_count = 0;
1139 }
1140
1141 template<typename _Key, typename _Value,
1142 typename _Allocator, typename _ExtractKey, typename _Equal,
1143 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1144 bool __chc, bool __cit, bool __uk>
1145 void
1146 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1147 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1148 rehash(size_type __n)
1149 {
1150 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1151 _M_rehash_policy._M_bkt_for_elements(_M_element_count
1152 + 1)));
1153 }
1154
1155 template<typename _Key, typename _Value,
1156 typename _Allocator, typename _ExtractKey, typename _Equal,
1157 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1158 bool __chc, bool __cit, bool __uk>
1159 void
1160 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1161 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1162 _M_rehash(size_type __n)
1163 {
1164 _Node** __new_array = _M_allocate_buckets(__n);
1165 __try
1166 {
1167 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1168 while (_Node* __p = _M_buckets[__i])
1169 {
1170 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1171 _M_buckets[__i] = __p->_M_next;
1172 __p->_M_next = __new_array[__new_index];
1173 __new_array[__new_index] = __p;
1174 }
1175 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1176 _M_bucket_count = __n;
1177 _M_buckets = __new_array;
1178 }
1179 __catch(...)
1180 {
1181 // A failure here means that a hash function threw an exception.
1182 // We can't restore the previous state without calling the hash
1183 // function again, so the only sensible recovery is to delete
1184 // everything.
1185 _M_deallocate_nodes(__new_array, __n);
1186 _M_deallocate_buckets(__new_array, __n);
1187 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1188 _M_element_count = 0;
1189 __throw_exception_again;
1190 }
1191 }
1192 }
1193
1194 #endif // _HASHTABLE_H
Tomato firmware and modifications.