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