?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Import GCC-8 to a new vendor branch
[dragonfly.git] / contrib / gcc-8.0 / libstdc++-v3 / include / tr1 / hashtable.h
blob1eaaa99fc77c7837fd756fdfface41a07cd488c7
1 // TR1 hashtable.h header -*- C++ -*-
2
3 // Copyright (C) 2007-2018 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 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41
42 namespace tr1
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 begin()
219 {
220 iterator __i(_M_buckets);
221 if (!__i._M_cur_node)
222 __i._M_incr_bucket();
223 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 end()
237 { 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 size() const
245 { 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 _M_get_Value_allocator() const
257 { 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 insert(const value_type& __v)
375 { return _M_insert(__v, std::tr1::integral_constant<bool,
376 __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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
426 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
427 _M_allocate_node(const value_type& __v)
428 {
429 _Node* __n = _M_node_allocator.allocate(1);
430 __try
431 {
432 _M_get_Value_allocator().construct(&__n->_M_v, __v);
433 __n->_M_next = 0;
434 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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
449 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
450 _M_deallocate_node(_Node* __n)
451 {
452 _M_get_Value_allocator().destroy(&__n->_M_v);
453 _M_node_allocator.deallocate(__n, 1);
454 }
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 _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 for (size_type __i = 0; __i < __n; ++__i)
466 {
467 _Node* __p = __array[__i];
468 while (__p)
469 {
470 _Node* __tmp = __p;
471 __p = __p->_M_next;
472 _M_deallocate_node(__tmp);
473 }
474 __array[__i] = 0;
475 }
476 }
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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
486 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
487 _M_allocate_buckets(size_type __n)
488 {
489 _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 _Node** __p = __alloc.allocate(__n + 1);
494 std::fill(__p, __p + __n, (_Node*) 0);
495 __p[__n] = reinterpret_cast<_Node*>(0x1000);
496 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 _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 _Bucket_allocator_type __alloc(_M_node_allocator);
509 __alloc.deallocate(__p, __n + 1);
510 }
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 _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 _M_rehash_policy()
531 {
532 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
533 _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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
637 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
638 ~_Hashtable()
639 {
640 clear();
641 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
642 }
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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
693 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
694 find(const key_type& __k)
695 {
696 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
697 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
698 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
699 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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
752 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
753 equal_range(const key_type& __k)
754 {
755 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
756 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
757 _Node** __head = _M_buckets + __n;
758 _Node* __p = _M_find_node(*__head, __k, __code);
759
760 if (__p)
761 {
762 _Node* __p1 = __p->_M_next;
763 for (; __p1; __p1 = __p1->_M_next)
764 if (!this->_M_compare(__k, __code, __p1))
765 break;
766
767 iterator __first(__p, __head);
768 iterator __last(__p1, __head);
769 if (!__p1)
770 __last._M_incr_bucket();
771 return std::make_pair(__first, __last);
772 }
773 else
774 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 _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 for (; __p; __p = __p->_M_next)
830 if (this->_M_compare(__k, __code, __p))
831 return __p;
832 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 _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 _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 _Node* __new_node = _M_allocate_node(__v);
855
856 __try
857 {
858 if (__do_rehash.first)
859 {
860 const key_type& __k = this->_M_extract(__v);
861 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
862 _M_rehash(__do_rehash.second);
863 }
864
865 __new_node->_M_next = _M_buckets[__n];
866 this->_M_store_code(__new_node, __code);
867 _M_buckets[__n] = __new_node;
868 ++_M_element_count;
869 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 _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 const key_type& __k = this->_M_extract(__v);
892 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
893 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
894
895 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
896 return std::make_pair(iterator(__p, _M_buckets + __n), false);
897 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 _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 _M_element_count, 1);
915 if (__do_rehash.first)
916 _M_rehash(__do_rehash.second);
917
918 const key_type& __k = this->_M_extract(__v);
919 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
920 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 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
924 _Node* __new_node = _M_allocate_node(__v);
925
926 if (__prev)
927 {
928 __new_node->_M_next = __prev->_M_next;
929 __prev->_M_next = __new_node;
930 }
931 else
932 {
933 __new_node->_M_next = _M_buckets[__n];
934 _M_buckets[__n] = __new_node;
935 }
936 this->_M_store_code(__new_node, __code);
937
938 ++_M_element_count;
939 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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
977 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
978 insert(_InputIterator __first, _InputIterator __last)
979 {
980 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 _M_element_count, __n_elt);
984 if (__do_rehash.first)
985 _M_rehash(__do_rehash.second);
986
987 for (; __first != __last; ++__first)
988 this->insert(*__first);
989 }
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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1118 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1119 clear()
1120 {
1121 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1122 _M_element_count = 0;
1123 }
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 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1145 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1146 _M_rehash(size_type __n)
1147 {
1148 _Node** __new_array = _M_allocate_buckets(__n);
1149 __try
1150 {
1151 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1152 while (_Node* __p = _M_buckets[__i])
1153 {
1154 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1155 _M_buckets[__i] = __p->_M_next;
1156 __p->_M_next = __new_array[__new_index];
1157 __new_array[__new_index] = __p;
1158 }
1159 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1160 _M_bucket_count = __n;
1161 _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 }
1176 } // namespace tr1
1177
1178 _GLIBCXX_END_NAMESPACE_VERSION
1179 } // namespace std
1180
1181 #endif // _GLIBCXX_TR1_HASHTABLE_H
DragonFly BSD