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