32 _GLIBCXX_BEGIN_NAMESPACE_TR1
38 template<
class _Iterator>
39 inline typename std::iterator_traits<_Iterator>::difference_type
40 __distance_fw(_Iterator __first, _Iterator __last,
44 template<
class _Iterator>
45 inline typename std::iterator_traits<_Iterator>::difference_type
46 __distance_fw(_Iterator __first, _Iterator __last,
50 template<
class _Iterator>
51 inline typename std::iterator_traits<_Iterator>::difference_type
52 __distance_fw(_Iterator __first, _Iterator __last)
54 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
55 return __distance_fw(__first, __last, _Tag());
58 template<
typename _RAIter,
typename _Tp>
60 __lower_bound(_RAIter __first, _RAIter __last,
const _Tp& __val)
62 typedef typename std::iterator_traits<_RAIter>::difference_type _DType;
64 _DType __len = __last - __first;
67 _DType __half = __len >> 1;
68 _RAIter __middle = __first + __half;
69 if (*__middle < __val)
73 __len = __len - __half - 1;
88 template<
typename _Value,
bool __cache_hash_code>
91 template<
typename _Value>
92 struct _Hash_node<_Value, true>
95 std::size_t _M_hash_code;
98 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
99 template<
typename... _Args>
100 _Hash_node(_Args&&... __args)
101 : _M_v(std::forward<_Args>(__args)...),
102 _M_hash_code(), _M_next() { }
106 template<
typename _Value>
107 struct _Hash_node<_Value, false>
112 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
113 template<
typename... _Args>
114 _Hash_node(_Args&&... __args)
115 : _M_v(std::forward<_Args>(__args)...),
122 template<
typename _Value,
bool __cache>
123 struct _Node_iterator_base
125 _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
130 { _M_cur = _M_cur->_M_next; }
132 _Hash_node<_Value, __cache>* _M_cur;
135 template<
typename _Value,
bool __cache>
137 operator==(
const _Node_iterator_base<_Value, __cache>& __x,
138 const _Node_iterator_base<_Value, __cache>& __y)
139 {
return __x._M_cur == __y._M_cur; }
141 template<
typename _Value,
bool __cache>
143 operator!=(
const _Node_iterator_base<_Value, __cache>& __x,
144 const _Node_iterator_base<_Value, __cache>& __y)
145 {
return __x._M_cur != __y._M_cur; }
147 template<
typename _Value,
bool __constant_iterators,
bool __cache>
148 struct _Node_iterator
149 :
public _Node_iterator_base<_Value, __cache>
151 typedef _Value value_type;
153 __gnu_cxx::__conditional_type<__constant_iterators,
154 const _Value*, _Value*>::__type
157 __gnu_cxx::__conditional_type<__constant_iterators,
158 const _Value&, _Value&>::__type
160 typedef std::ptrdiff_t difference_type;
164 : _Node_iterator_base<_Value, __cache>(0) { }
167 _Node_iterator(_Hash_node<_Value, __cache>* __p)
168 : _Node_iterator_base<_Value, __cache>(__p) { }
172 {
return this->_M_cur->_M_v; }
176 {
return &this->_M_cur->_M_v; }
188 _Node_iterator __tmp(*
this);
194 template<
typename _Value,
bool __constant_iterators,
bool __cache>
195 struct _Node_const_iterator
196 :
public _Node_iterator_base<_Value, __cache>
198 typedef _Value value_type;
199 typedef const _Value* pointer;
200 typedef const _Value& reference;
201 typedef std::ptrdiff_t difference_type;
204 _Node_const_iterator()
205 : _Node_iterator_base<_Value, __cache>(0) { }
208 _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
209 : _Node_iterator_base<_Value, __cache>(__p) { }
211 _Node_const_iterator(
const _Node_iterator<_Value, __constant_iterators,
213 : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
217 {
return this->_M_cur->_M_v; }
221 {
return &this->_M_cur->_M_v; }
223 _Node_const_iterator&
233 _Node_const_iterator __tmp(*
this);
239 template<
typename _Value,
bool __cache>
240 struct _Hashtable_iterator_base
242 _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
243 _Hash_node<_Value, __cache>** __bucket)
244 : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
249 _M_cur_node = _M_cur_node->_M_next;
257 _Hash_node<_Value, __cache>* _M_cur_node;
258 _Hash_node<_Value, __cache>** _M_cur_bucket;
263 template<
typename _Value,
bool __cache>
265 _Hashtable_iterator_base<_Value, __cache>::
271 while (!*_M_cur_bucket)
273 _M_cur_node = *_M_cur_bucket;
276 template<
typename _Value,
bool __cache>
278 operator==(
const _Hashtable_iterator_base<_Value, __cache>& __x,
279 const _Hashtable_iterator_base<_Value, __cache>& __y)
280 {
return __x._M_cur_node == __y._M_cur_node; }
282 template<
typename _Value,
bool __cache>
284 operator!=(
const _Hashtable_iterator_base<_Value, __cache>& __x,
285 const _Hashtable_iterator_base<_Value, __cache>& __y)
286 {
return __x._M_cur_node != __y._M_cur_node; }
288 template<
typename _Value,
bool __constant_iterators,
bool __cache>
289 struct _Hashtable_iterator
290 :
public _Hashtable_iterator_base<_Value, __cache>
292 typedef _Value value_type;
294 __gnu_cxx::__conditional_type<__constant_iterators,
295 const _Value*, _Value*>::__type
298 __gnu_cxx::__conditional_type<__constant_iterators,
299 const _Value&, _Value&>::__type
301 typedef std::ptrdiff_t difference_type;
304 _Hashtable_iterator()
305 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
307 _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
308 _Hash_node<_Value, __cache>** __b)
309 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
312 _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
313 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
317 {
return this->_M_cur_node->_M_v; }
321 {
return &this->_M_cur_node->_M_v; }
333 _Hashtable_iterator __tmp(*
this);
339 template<
typename _Value,
bool __constant_iterators,
bool __cache>
340 struct _Hashtable_const_iterator
341 :
public _Hashtable_iterator_base<_Value, __cache>
343 typedef _Value value_type;
344 typedef const _Value* pointer;
345 typedef const _Value& reference;
346 typedef std::ptrdiff_t difference_type;
349 _Hashtable_const_iterator()
350 : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
352 _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
353 _Hash_node<_Value, __cache>** __b)
354 : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
357 _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
358 : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
360 _Hashtable_const_iterator(
const _Hashtable_iterator<_Value,
361 __constant_iterators, __cache>& __x)
362 : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
363 __x._M_cur_bucket) { }
367 {
return this->_M_cur_node->_M_v; }
371 {
return &this->_M_cur_node->_M_v; }
373 _Hashtable_const_iterator&
380 _Hashtable_const_iterator
383 _Hashtable_const_iterator __tmp(*
this);
395 struct _Mod_range_hashing
397 typedef std::size_t first_argument_type;
398 typedef std::size_t second_argument_type;
399 typedef std::size_t result_type;
402 operator()(first_argument_type __num, second_argument_type __den)
const
403 {
return __num % __den; }
411 struct _Default_ranged_hash { };
415 struct _Prime_rehash_policy
417 _Prime_rehash_policy(
float __z = 1.0)
418 : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { }
421 max_load_factor()
const
422 {
return _M_max_load_factor; }
426 _M_next_bkt(std::size_t __n)
const;
430 _M_bkt_for_elements(std::size_t __n)
const;
437 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
438 std::size_t __n_ins)
const;
440 enum { _S_n_primes =
sizeof(
unsigned long) != 8 ? 256 : 256 + 48 };
442 float _M_max_load_factor;
443 float _M_growth_factor;
444 mutable std::size_t _M_next_resize;
447 extern const unsigned long __prime_list[];
454 _Prime_rehash_policy::
455 _M_next_bkt(std::size_t __n)
const
457 const unsigned long* __p = __lower_bound(__prime_list, __prime_list
460 static_cast<std::size_t
>(__builtin_ceil(*__p * _M_max_load_factor));
467 _Prime_rehash_policy::
468 _M_bkt_for_elements(std::size_t __n)
const
470 const float __min_bkts = __n / _M_max_load_factor;
471 const unsigned long* __p = __lower_bound(__prime_list, __prime_list
472 + _S_n_primes, __min_bkts);
474 static_cast<std::size_t
>(__builtin_ceil(*__p * _M_max_load_factor));
488 _Prime_rehash_policy::
489 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
490 std::size_t __n_ins)
const
492 if (__n_elt + __n_ins > _M_next_resize)
494 float __min_bkts = ((float(__n_ins) + float(__n_elt))
495 / _M_max_load_factor);
496 if (__min_bkts > __n_bkt)
498 __min_bkts =
std::max(__min_bkts, _M_growth_factor * __n_bkt);
499 const unsigned long* __p =
500 __lower_bound(__prime_list, __prime_list + _S_n_primes,
502 _M_next_resize =
static_cast<std::size_t
>
503 (__builtin_ceil(*__p * _M_max_load_factor));
504 return std::make_pair(
true, *__p);
508 _M_next_resize =
static_cast<std::size_t
>
509 (__builtin_ceil(__n_bkt * _M_max_load_factor));
510 return std::make_pair(
false, 0);
514 return std::make_pair(
false, 0);
531 template<
typename _Key,
typename _Value,
typename _Ex,
bool __unique,
533 struct _Map_base { };
535 template<
typename _Key,
typename _Pair,
typename _Hashtable>
536 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
538 typedef typename _Pair::second_type mapped_type;
541 template<
typename _Key,
typename _Pair,
typename _Hashtable>
542 struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
544 typedef typename _Pair::second_type mapped_type;
547 operator[](
const _Key& __k);
549 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
556 at(
const _Key& __k)
const;
560 template<
typename _Key,
typename _Pair,
typename _Hashtable>
561 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
562 true, _Hashtable>::mapped_type&
563 _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
true, _Hashtable>::
564 operator[](
const _Key& __k)
566 _Hashtable* __h =
static_cast<_Hashtable*
>(
this);
567 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
568 std::size_t __n = __h->_M_bucket_index(__k, __code,
569 __h->_M_bucket_count);
571 typename _Hashtable::_Node* __p =
572 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
574 return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
575 __n, __code)->second;
576 return (__p->_M_v).second;
579 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
580 template<
typename _Key,
typename _Pair,
typename _Hashtable>
581 typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
582 true, _Hashtable>::mapped_type&
583 _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
true, _Hashtable>::
586 _Hashtable* __h =
static_cast<_Hashtable*
>(
this);
587 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
588 std::size_t __n = __h->_M_bucket_index(__k, __code,
589 __h->_M_bucket_count);
591 typename _Hashtable::_Node* __p =
592 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
594 __throw_out_of_range(__N(
"_Map_base::at"));
595 return (__p->_M_v).second;
598 template<
typename _Key,
typename _Pair,
typename _Hashtable>
599 const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
600 true, _Hashtable>::mapped_type&
601 _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
true, _Hashtable>::
602 at(
const _Key& __k)
const
604 const _Hashtable* __h =
static_cast<const _Hashtable*
>(
this);
605 typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
606 std::size_t __n = __h->_M_bucket_index(__k, __code,
607 __h->_M_bucket_count);
609 typename _Hashtable::_Node* __p =
610 __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
612 __throw_out_of_range(__N(
"_Map_base::at"));
613 return (__p->_M_v).second;
619 template<
typename _RehashPolicy,
typename _Hashtable>
620 struct _Rehash_base { };
622 template<
typename _Hashtable>
623 struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
626 max_load_factor()
const
628 const _Hashtable* __this =
static_cast<const _Hashtable*
>(
this);
629 return __this->__rehash_policy().max_load_factor();
633 max_load_factor(
float __z)
635 _Hashtable* __this =
static_cast<_Hashtable*
>(
this);
636 __this->__rehash_policy(_Prime_rehash_policy(__z));
652 template<
typename _Key,
typename _Value,
653 typename _ExtractKey,
typename _Equal,
654 typename _H1,
typename _H2,
typename _Hash,
655 bool __cache_hash_code>
656 struct _Hash_code_base;
660 template<
typename _Key,
typename _Value,
661 typename _ExtractKey,
typename _Equal,
662 typename _H1,
typename _H2,
typename _Hash>
663 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
667 _Hash_code_base(
const _ExtractKey& __ex,
const _Equal& __eq,
668 const _H1&,
const _H2&,
const _Hash& __h)
669 : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
671 typedef void* _Hash_code_type;
674 _M_hash_code(
const _Key& __key)
const
678 _M_bucket_index(
const _Key& __k, _Hash_code_type,
679 std::size_t __n)
const
680 {
return _M_ranged_hash(__k, __n); }
683 _M_bucket_index(
const _Hash_node<_Value, false>* __p,
684 std::size_t __n)
const
685 {
return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
688 _M_compare(
const _Key& __k, _Hash_code_type,
689 _Hash_node<_Value, false>* __n)
const
690 {
return _M_eq(__k, _M_extract(__n->_M_v)); }
693 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type)
const
697 _M_copy_code(_Hash_node<_Value, false>*,
698 const _Hash_node<_Value, false>*)
const
702 _M_swap(_Hash_code_base& __x)
704 std::swap(_M_extract, __x._M_extract);
705 std::swap(_M_eq, __x._M_eq);
706 std::swap(_M_ranged_hash, __x._M_ranged_hash);
710 _ExtractKey _M_extract;
712 _Hash _M_ranged_hash;
723 template<
typename _Key,
typename _Value,
724 typename _ExtractKey,
typename _Equal,
725 typename _H1,
typename _H2,
typename _Hash>
726 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
732 template<
typename _Key,
typename _Value,
733 typename _ExtractKey,
typename _Equal,
734 typename _H1,
typename _H2>
735 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
736 _Default_ranged_hash, false>
741 hash_function()
const
745 _Hash_code_base(
const _ExtractKey& __ex,
const _Equal& __eq,
746 const _H1& __h1,
const _H2& __h2,
747 const _Default_ranged_hash&)
748 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
750 typedef std::size_t _Hash_code_type;
753 _M_hash_code(
const _Key& __k)
const
754 {
return _M_h1(__k); }
757 _M_bucket_index(
const _Key&, _Hash_code_type __c,
758 std::size_t __n)
const
759 {
return _M_h2(__c, __n); }
762 _M_bucket_index(
const _Hash_node<_Value, false>* __p,
763 std::size_t __n)
const
764 {
return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
767 _M_compare(
const _Key& __k, _Hash_code_type,
768 _Hash_node<_Value, false>* __n)
const
769 {
return _M_eq(__k, _M_extract(__n->_M_v)); }
772 _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type)
const
776 _M_copy_code(_Hash_node<_Value, false>*,
777 const _Hash_node<_Value, false>*)
const
781 _M_swap(_Hash_code_base& __x)
783 std::swap(_M_extract, __x._M_extract);
784 std::swap(_M_eq, __x._M_eq);
785 std::swap(_M_h1, __x._M_h1);
786 std::swap(_M_h2, __x._M_h2);
790 _ExtractKey _M_extract;
799 template<
typename _Key,
typename _Value,
800 typename _ExtractKey,
typename _Equal,
801 typename _H1,
typename _H2>
802 struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
803 _Default_ranged_hash, true>
808 hash_function()
const
812 _Hash_code_base(
const _ExtractKey& __ex,
const _Equal& __eq,
813 const _H1& __h1,
const _H2& __h2,
814 const _Default_ranged_hash&)
815 : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
817 typedef std::size_t _Hash_code_type;
820 _M_hash_code(
const _Key& __k)
const
821 {
return _M_h1(__k); }
824 _M_bucket_index(
const _Key&, _Hash_code_type __c,
825 std::size_t __n)
const
826 {
return _M_h2(__c, __n); }
829 _M_bucket_index(
const _Hash_node<_Value, true>* __p,
830 std::size_t __n)
const
831 {
return _M_h2(__p->_M_hash_code, __n); }
834 _M_compare(
const _Key& __k, _Hash_code_type __c,
835 _Hash_node<_Value, true>* __n)
const
836 {
return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
839 _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c)
const
840 { __n->_M_hash_code = __c; }
843 _M_copy_code(_Hash_node<_Value, true>* __to,
844 const _Hash_node<_Value, true>* __from)
const
845 { __to->_M_hash_code = __from->_M_hash_code; }
848 _M_swap(_Hash_code_base& __x)
850 std::swap(_M_extract, __x._M_extract);
851 std::swap(_M_eq, __x._M_eq);
852 std::swap(_M_h1, __x._M_h1);
853 std::swap(_M_h2, __x._M_h2);
857 _ExtractKey _M_extract;
864 _GLIBCXX_END_NAMESPACE_TR1
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
pair holds two objects of arbitrary type.
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Forward iterators support a superset of input iterator operations.