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