diff options
| author | Benjamin Kosnik <bkoz@gcc.gnu.org> | 2006-07-28 04:57:34 +0000 |
|---|---|---|
| committer | Benjamin Kosnik <bkoz@gcc.gnu.org> | 2006-07-28 04:57:34 +0000 |
| commit | b82f782bfb5c4383ac0bc1e37271ab3bbeb9304d (patch) | |
| tree | 81547eb1eadbf4669dec412581227155f1ad5c83 | |
| parent | 85661c41dd4fe35a4fd54c3679b94fa0ea2e902a (diff) | |
| download | gcc-b82f782bfb5c4383ac0bc1e37271ab3bbeb9304d.zip gcc-b82f782bfb5c4383ac0bc1e37271ab3bbeb9304d.tar.gz gcc-b82f782bfb5c4383ac0bc1e37271ab3bbeb9304d.tar.bz2 | |
PR libstdc++/19664 round 3
2006-07-27 Benjamin Kosnik <bkoz@wells.artheist.org>
PR libstdc++/19664 round 3
* include/Makefile.am (tr1_headers): Add hashtable_policy.h.
* include/Makefile.in: Regenerate.
* include/tr1/hashtable: Move policy classes into...
* include/tr1/hashtable_policy.h: ... this. New.
* src/globals_locale.cc: Move contents....
* src/locale_init.cc: ... to here, put in anonymous namespace.
* src/Makefile.am: Remove globals_locale.cc.
* src/Makefile.in: Regenerate.
* src/locale.cc: Convert __gnu_internal to anonymous namespace.
* src/debug.cc: Same.
* src/ext-inst.cc: Same.
* src/mt_allocator.cc: Same.
* src/pool_allocator.cc: Same.
* include/tr1/random: Convert std::tr1::_Private to anonymous
namespace.
* include/tr1/random.tcc: Same.
* include/tr1/hashtable: Move ::Internal to std::tr1::detail and
enclose bits that can actually be internal in in anonymous
namespace.
* include/tr1/unordered_set: Adjust explicit qualifications for
namespace changes.
* include/tr1/unordered_map: Same.
* include/tr1/cmath: Convert __gnu_internal to nested detail namespace.
* include/bits/cpp_type_traits.h: Move __type_type into anonymous
namespace.
* include/ext/rope: Change _Rope_constants to anonymous namespace.
* include/ext/ropeimpl.h: Same.
* src/ext-inst.cc: Same.
From-SVN: r115790
| -rw-r--r-- | libstdc++-v3/ChangeLog | 40 | ||||
| -rw-r--r-- | libstdc++-v3/include/Makefile.am | 1 | ||||
| -rw-r--r-- | libstdc++-v3/include/Makefile.in | 1 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/cpp_type_traits.h | 34 | ||||
| -rw-r--r-- | libstdc++-v3/include/ext/rope | 44 | ||||
| -rw-r--r-- | libstdc++-v3/include/ext/ropeimpl.h | 124 | ||||
| -rw-r--r-- | libstdc++-v3/include/tr1/cmath | 33 | ||||
| -rw-r--r-- | libstdc++-v3/include/tr1/hashtable | 971 | ||||
| -rw-r--r-- | libstdc++-v3/include/tr1/hashtable_policy.h | 893 | ||||
| -rw-r--r-- | libstdc++-v3/include/tr1/random | 38 | ||||
| -rw-r--r-- | libstdc++-v3/include/tr1/random.tcc | 60 | ||||
| -rw-r--r-- | libstdc++-v3/include/tr1/unordered_map | 69 | ||||
| -rw-r--r-- | libstdc++-v3/include/tr1/unordered_set | 57 | ||||
| -rw-r--r-- | libstdc++-v3/src/Makefile.am | 1 | ||||
| -rw-r--r-- | libstdc++-v3/src/Makefile.in | 47 | ||||
| -rw-r--r-- | libstdc++-v3/src/debug.cc | 8 | ||||
| -rw-r--r-- | libstdc++-v3/src/ext-inst.cc | 6 | ||||
| -rw-r--r-- | libstdc++-v3/src/globals_locale.cc | 210 | ||||
| -rw-r--r-- | libstdc++-v3/src/locale.cc | 6 | ||||
| -rw-r--r-- | libstdc++-v3/src/locale_init.cc | 217 | ||||
| -rw-r--r-- | libstdc++-v3/src/mt_allocator.cc | 76 | ||||
| -rw-r--r-- | libstdc++-v3/src/pool_allocator.cc | 4 |
22 files changed, 1441 insertions, 1499 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index e5c4057..fc42bdb 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,42 @@ +2006-07-27 Benjamin Kosnik <bkoz@wells.artheist.org> + + PR libstdc++/19664 round 3 + * include/Makefile.am (tr1_headers): Add hashtable_policy.h. + * include/Makefile.in: Regenerate. + * include/tr1/hashtable: Move policy classes into... + * include/tr1/hashtable_policy.h: ... this. New. + + * src/globals_locale.cc: Move contents.... + * src/locale_init.cc: ... to here, put in anonymous namespace. + * src/Makefile.am: Remove globals_locale.cc. + * src/Makefile.in: Regenerate. + + * src/locale.cc: Convert __gnu_internal to anonymous namespace. + * src/debug.cc: Same. + * src/ext-inst.cc: Same. + * src/mt_allocator.cc: Same. + * src/pool_allocator.cc: Same. + + * include/tr1/random: Convert std::tr1::_Private to anonymous + namespace. + * include/tr1/random.tcc: Same. + + * include/tr1/hashtable: Move ::Internal to std::tr1::detail and + enclose bits that can actually be internal in in anonymous + namespace. + * include/tr1/unordered_set: Adjust explicit qualifications for + namespace changes. + * include/tr1/unordered_map: Same. + + * include/tr1/cmath: Convert __gnu_internal to nested detail namespace. + + * include/bits/cpp_type_traits.h: Move __type_type into anonymous + namespace. + + * include/ext/rope: Change _Rope_constants to anonymous namespace. + * include/ext/ropeimpl.h: Same. + * src/ext-inst.cc: Same. + 2006-07-24 Paolo Carlini <pcarlini@suse.de> * include/tr1/cinttypes: Simply protect everything with @@ -31,6 +70,7 @@ 2006-07-21 Jason Merrill <jason@redhat.com> + PR libstdc++/19664 round 2 * libsupc++/eh_personality.cc: Wrap extern "C" function definitions in namespace __cxxabiv1. diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index ce4234d..271de28 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -591,6 +591,7 @@ tr1_headers = \ ${tr1_srcdir}/functional \ ${tr1_srcdir}/functional_iterate.h \ ${tr1_srcdir}/hashtable \ + ${tr1_srcdir}/hashtable_policy.h \ ${tr1_srcdir}/inttypes.h \ ${tr1_srcdir}/limits.h \ ${tr1_srcdir}/math.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index eeae3bb..a53f925 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -811,6 +811,7 @@ tr1_headers = \ ${tr1_srcdir}/functional \ ${tr1_srcdir}/functional_iterate.h \ ${tr1_srcdir}/hashtable \ + ${tr1_srcdir}/hashtable_policy.h \ ${tr1_srcdir}/inttypes.h \ ${tr1_srcdir}/limits.h \ ${tr1_srcdir}/math.h \ diff --git a/libstdc++-v3/include/bits/cpp_type_traits.h b/libstdc++-v3/include/bits/cpp_type_traits.h index 53823a8..f796b0c 100644 --- a/libstdc++-v3/include/bits/cpp_type_traits.h +++ b/libstdc++-v3/include/bits/cpp_type_traits.h @@ -70,19 +70,6 @@ // removed. // -// NB: g++ can not compile these if declared within the class -// __is_pod itself. -namespace __gnu_internal -{ - typedef char __one; - typedef char __two[2]; - - template<typename _Tp> - __one __test_type(int _Tp::*); - template<typename _Tp> - __two& __test_type(...); -} // namespace __gnu_internal - // Forward declaration hack, should really include this from somewhere. _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) @@ -352,16 +339,27 @@ _GLIBCXX_BEGIN_NAMESPACE(std) : public __traitor<__is_arithmetic<_Tp>, __is_pointer<_Tp> > { }; - // - // For the immediate use, the following is a good approximation - // + // NB: g++ can not compile these if declared within the class + // __is_pod itself. + namespace + { + typedef char __one; + typedef char __two[2]; + + template<typename _Tp> + __one __test_type(int _Tp::*); + + template<typename _Tp> + __two& __test_type(...); + } + + // For the immediate use, the following is a good approximation. template<typename _Tp> struct __is_pod { enum { - __value = (sizeof(__gnu_internal::__test_type<_Tp>(0)) - != sizeof(__gnu_internal::__one)) + __value = (sizeof(__test_type<_Tp>(0)) != sizeof(__one)) }; }; diff --git a/libstdc++-v3/include/ext/rope b/libstdc++-v3/include/ext/rope index 63e9fe9..059342f 100644 --- a/libstdc++-v3/include/ext/rope +++ b/libstdc++-v3/include/ext/rope @@ -1,6 +1,7 @@ // SGI's rope class -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 +// Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -66,6 +67,12 @@ #include <ext/memory> // For uninitialized_copy_n +namespace +{ + enum { _S_max_rope_depth = 45 }; + enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function}; +} + _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) using std::size_t; @@ -543,12 +550,6 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) # undef __ROPE_DEFINE_ALLOC }; - namespace _Rope_constants - { - enum { _S_max_rope_depth = 45 }; - enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function}; - } - template<class _CharT, class _Alloc> struct _Rope_RopeRep : public _Rope_rep_base<_CharT, _Alloc> @@ -557,7 +558,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) # endif { public: - _Rope_constants::_Tag _M_tag:8; + _Tag _M_tag:8; bool _M_is_balanced:8; unsigned char _M_depth; __GC_CONST _CharT* _M_c_string; @@ -573,7 +574,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) using _Rope_rep_base<_CharT, _Alloc>::get_allocator; - _Rope_RopeRep(_Rope_constants::_Tag __t, int __d, bool __b, size_t __size, + _Rope_RopeRep(_Tag __t, int __d, bool __b, size_t __size, allocator_type __a) : _Rope_rep_base<_CharT, _Alloc>(__size, __a), #ifndef __GC @@ -690,7 +691,7 @@ protected: _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, allocator_type __a) - : _Rope_RopeRep<_CharT, _Alloc>(_Rope_constants::_S_leaf, 0, true, + : _Rope_RopeRep<_CharT, _Alloc>(_S_leaf, 0, true, __size, __a), _M_data(__d) { if (_S_is_basic_char_type((_CharT *)0)) @@ -732,7 +733,7 @@ protected: _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l, _Rope_RopeRep<_CharT, _Alloc>* __r, allocator_type __a) - : _Rope_RopeRep<_CharT, _Alloc>(_Rope_constants::_S_concat, + : _Rope_RopeRep<_CharT, _Alloc>(::_S_concat, std::max(__l->_M_depth, __r->_M_depth) + 1, false, @@ -780,8 +781,7 @@ protected: _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size, bool __d, allocator_type __a) - : _Rope_RopeRep<_CharT, _Alloc>(_Rope_constants::_S_function, - 0, true, __size, __a) + : _Rope_RopeRep<_CharT, _Alloc>(::_S_function, 0, true, __size, __a) , _M_fn(__f) #ifndef __GC , _M_delete_when_done(__d) @@ -832,15 +832,15 @@ protected: { switch(_M_base->_M_tag) { - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: + case ::_S_function: + case ::_S_substringfn: { char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn; (*__fn)(__start_pos + _M_start, __req_len, __buffer); } break; - case _Rope_constants::_S_leaf: + case ::_S_leaf: { __GC_CONST _CharT* __s = ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data; @@ -864,7 +864,7 @@ protected: #ifndef __GC _M_base->_M_ref_nonnil(); #endif - this->_M_tag = _Rope_constants::_S_substringfn; + this->_M_tag = ::_S_substringfn; } virtual ~_Rope_RopeSubstring() throw() { @@ -1711,7 +1711,7 @@ protected: _CharT* __buffer); static const unsigned long - _S_min_len[_Rope_constants::_S_max_rope_depth + 1]; + _S_min_len[::_S_max_rope_depth + 1]; static bool _S_is_balanced(_RopeRep* __r) @@ -1961,7 +1961,7 @@ protected: { if (0 == this->_M_tree_ptr) return; - if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag && + if (::_S_leaf == this->_M_tree_ptr->_M_tag && ((_RopeLeaf*)this->_M_tree_ptr)->_M_data == this->_M_tree_ptr->_M_c_string) { @@ -2013,7 +2013,7 @@ protected: size_type max_size() const { - return _S_min_len[int(_Rope_constants::_S_max_rope_depth) - 1] - 1; + return _S_min_len[int(::_S_max_rope_depth) - 1] - 1; // Guarantees that the result can be sufficirntly // balanced. Longer ropes will probably still work, // but it's harder to make guarantees. @@ -2089,8 +2089,8 @@ protected: _Self_destruct_ptr __appendee(_S_substring(__s._M_root, __s._M_current_pos, __e._M_current_pos)); - _RopeRep* __result = - _S_concat(this->_M_tree_ptr, (_RopeRep*)__appendee); + _RopeRep* __result = _S_concat(this->_M_tree_ptr, + (_RopeRep*)__appendee); _S_unref(this->_M_tree_ptr); this->_M_tree_ptr = __result; return *this; diff --git a/libstdc++-v3/include/ext/ropeimpl.h b/libstdc++-v3/include/ext/ropeimpl.h index 9371dbb..c7827e3 100644 --- a/libstdc++-v3/include/ext/ropeimpl.h +++ b/libstdc++-v3/include/ext/ropeimpl.h @@ -1,6 +1,7 @@ // SGI's rope class implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 +// Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -77,13 +78,13 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) switch(__leaf->_M_tag) { - case _Rope_constants::_S_leaf: + case ::_S_leaf: __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data; __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); __x._M_buf_end = __x._M_buf_start + __leaf->_M_size; break; - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: + case ::_S_function: + case ::_S_substringfn: { size_t __len = _S_iterator_buf_len; size_t __buf_start_pos = __leaf_pos; @@ -116,7 +117,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) _Rope_iterator_base<_CharT, _Alloc>:: _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x) { - const _RopeRep* __path[int(_Rope_constants::_S_max_rope_depth) + 1]; + const _RopeRep* __path[int(::_S_max_rope_depth) + 1]; const _RopeRep* __curr_rope; int __curr_depth = -1; /* index into path */ size_t __curr_start_pos = 0; @@ -146,12 +147,12 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) __path[__curr_depth] = __curr_rope; switch(__curr_rope->_M_tag) { - case _Rope_constants::_S_leaf: - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: + case ::_S_leaf: + case ::_S_function: + case ::_S_substringfn: __x._M_leaf_pos = __curr_start_pos; goto done; - case _Rope_constants::_S_concat: + case ::_S_concat: { _Rope_RopeConcatenation<_CharT, _Alloc>* __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope; @@ -233,7 +234,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) __current_node = __c->_M_right; __x._M_path_end[++__current_index] = __current_node; __dirns |= 1; - while (_Rope_constants::_S_concat == __current_node->_M_tag) + while (::_S_concat == __current_node->_M_tag) { ++__current_index; if (int(_S_path_cache_len) == __current_index) @@ -377,7 +378,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) { switch(_M_tag) { - case _Rope_constants::_S_leaf: + case ::_S_leaf: { _Rope_RopeLeaf<_CharT, _Alloc>* __l = (_Rope_RopeLeaf<_CharT, _Alloc>*)this; @@ -385,7 +386,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) _L_deallocate(__l, 1); break; } - case _Rope_constants::_S_concat: + case ::_S_concat: { _Rope_RopeConcatenation<_CharT,_Alloc>* __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this; @@ -394,7 +395,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) _C_deallocate(__c, 1); break; } - case _Rope_constants::_S_function: + case ::_S_function: { _Rope_RopeFunction<_CharT, _Alloc>* __f = (_Rope_RopeFunction<_CharT, _Alloc>*)this; @@ -402,7 +403,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) _F_deallocate(__f, 1); break; } - case _Rope_constants::_S_substringfn: + case ::_S_substringfn: { _Rope_RopeSubstring<_CharT, _Alloc>* __ss = (_Rope_RopeSubstring<_CharT, _Alloc>*)this; @@ -502,7 +503,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) if (__depth > 20 && (__result->_M_size < 1000 - || __depth > size_t(_Rope_constants::_S_max_rope_depth))) + || __depth > size_t(::_S_max_rope_depth))) { _RopeRep* __balanced; @@ -540,15 +541,14 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) if (0 == __r) return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); - if (_Rope_constants::_S_leaf == __r->_M_tag + if (__r->_M_tag == ::_S_leaf && __r->_M_size + __slen <= size_t(_S_copy_max)) { __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); return __result; } - if (_Rope_constants::_S_concat == __r->_M_tag - && _Rope_constants::_S_leaf == ((_RopeConcatenation*) - __r)->_M_right->_M_tag) + if (::_S_concat == __r->_M_tag + && ::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag) { _RopeLeaf* __right = (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); @@ -605,17 +605,17 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) return __r; } if (__orig_size + __slen <= size_t(_S_copy_max) - && _Rope_constants::_S_leaf == __r->_M_tag) + && ::_S_leaf == __r->_M_tag) { __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); return __result; } - if (_Rope_constants::_S_concat == __r->_M_tag) + if (::_S_concat == __r->_M_tag) { _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*) __r)->_M_right); - if (_Rope_constants::_S_leaf == __right->_M_tag + if (::_S_leaf == __right->_M_tag && __right->_M_size + __slen <= size_t(_S_copy_max)) { _RopeRep* __new_right = @@ -665,17 +665,17 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) __left->_M_ref_nonnil(); return __left; } - if (_Rope_constants::_S_leaf == __right->_M_tag) + if (::_S_leaf == __right->_M_tag) { - if (_Rope_constants::_S_leaf == __left->_M_tag) + if (::_S_leaf == __left->_M_tag) { if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max)) return _S_leaf_concat_char_iter((_RopeLeaf*)__left, ((_RopeLeaf*)__right)->_M_data, __right->_M_size); } - else if (_Rope_constants::_S_concat == __left->_M_tag - && _Rope_constants::_S_leaf == ((_RopeConcatenation*) + else if (::_S_concat == __left->_M_tag + && ::_S_leaf == ((_RopeConcatenation*) __left)->_M_right->_M_tag) { _RopeLeaf* __leftright = @@ -740,7 +740,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) switch(__base->_M_tag) { - case _Rope_constants::_S_concat: + case ::_S_concat: { _RopeConcatenation* __c = (_RopeConcatenation*)__base; _RopeRep* __left = __c->_M_left; @@ -762,7 +762,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) __result = _S_concat(__left_result, __right_result); return __result; } - case _Rope_constants::_S_leaf: + case ::_S_leaf: { _RopeLeaf* __l = (_RopeLeaf*)__base; _RopeLeaf* __result; @@ -786,7 +786,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) #endif return __result; } - case _Rope_constants::_S_substringfn: + case ::_S_substringfn: // Avoid introducing multiple layers of substring nodes. { _RopeSubstring* __old = (_RopeSubstring*)__base; @@ -805,7 +805,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) } // *** else fall through: *** } - case _Rope_constants::_S_function: + case ::_S_function: { _RopeFunction* __f = (_RopeFunction*)__base; _CharT* __section; @@ -930,7 +930,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) return true; switch(__r->_M_tag) { - case _Rope_constants::_S_concat: + case ::_S_concat: { _RopeConcatenation* __conc = (_RopeConcatenation*)__r; _RopeRep* __left = __conc->_M_left; @@ -952,13 +952,13 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) } } return true; - case _Rope_constants::_S_leaf: + case ::_S_leaf: { _RopeLeaf* __l = (_RopeLeaf*)__r; return __c(__l->_M_data + __begin, __end - __begin); } - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: + case ::_S_function: + case ::_S_substringfn: { _RopeFunction* __f = (_RopeFunction*)__r; size_t __len = __end - __begin; @@ -1081,7 +1081,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) return __buffer; switch(__r->_M_tag) { - case _Rope_constants::_S_concat: + case ::_S_concat: { _RopeConcatenation* __c = (_RopeConcatenation*)__r; _RopeRep* __left = __c->_M_left; @@ -1089,13 +1089,13 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) _CharT* __rest = _S_flatten(__left, __buffer); return _S_flatten(__right, __rest); } - case _Rope_constants::_S_leaf: + case ::_S_leaf: { _RopeLeaf* __l = (_RopeLeaf*)__r; return copy_n(__l->_M_data, __l->_M_size, __buffer).second; } - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: + case ::_S_function: + case ::_S_substringfn: // We don't yet do anything with substring nodes. // This needs to be fixed before ropefiles will work well. { @@ -1121,7 +1121,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) printf("NULL\n"); return; } - if (_Rope_constants::_S_concat == __r->_M_tag) + if (_S_concat == __r->_M_tag) { _RopeConcatenation* __c = (_RopeConcatenation*)__r; _RopeRep* __left = __c->_M_left; @@ -1147,13 +1147,13 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) switch (__r->_M_tag) { - case _Rope_constants::_S_leaf: + case ::_S_leaf: __kind = "Leaf"; break; - case _Rope_constants::_S_function: + case ::_S_function: __kind = "Function"; break; - case _Rope_constants::_S_substringfn: + case ::_S_substringfn: __kind = "Function representing substring"; break; default: @@ -1186,7 +1186,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) template <class _CharT, class _Alloc> const unsigned long rope<_CharT, _Alloc>:: - _S_min_len[int(_Rope_constants::_S_max_rope_depth) + 1] = { + _S_min_len[int(::_S_max_rope_depth) + 1] = { /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, @@ -1205,7 +1205,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) rope<_CharT, _Alloc>:: _S_balance(_RopeRep* __r) { - _RopeRep* __forest[int(_Rope_constants::_S_max_rope_depth) + 1]; + _RopeRep* __forest[int(::_S_max_rope_depth) + 1]; _RopeRep* __result = 0; int __i; // Invariant: @@ -1214,12 +1214,12 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) // __forest[__i]._M_depth = __i // References from forest are included in refcount. - for (__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); ++__i) + for (__i = 0; __i <= int(::_S_max_rope_depth); ++__i) __forest[__i] = 0; try { _S_add_to_forest(__r, __forest); - for (__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); ++__i) + for (__i = 0; __i <= int(::_S_max_rope_depth); ++__i) if (0 != __forest[__i]) { #ifndef __GC @@ -1234,12 +1234,12 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) } catch(...) { - for(__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); __i++) + for(__i = 0; __i <= int(::_S_max_rope_depth); __i++) _S_unref(__forest[__i]); __throw_exception_again; } - if (__result->_M_depth > int(_Rope_constants::_S_max_rope_depth)) + if (__result->_M_depth > int(::_S_max_rope_depth)) __throw_length_error(__N("rope::_S_balance")); return(__result); } @@ -1307,7 +1307,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) __forest[__i]->_M_unref_nonnil(); __forest[__i] = 0; } - if (__i == int(_Rope_constants::_S_max_rope_depth) + if (__i == int(::_S_max_rope_depth) || __insertee->_M_size < _S_min_len[__i+1]) { __forest[__i] = __insertee; @@ -1330,7 +1330,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) { switch(__r->_M_tag) { - case _Rope_constants::_S_concat: + case ::_S_concat: { _RopeConcatenation* __c = (_RopeConcatenation*)__r; _RopeRep* __left = __c->_M_left; @@ -1345,13 +1345,13 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) __r = __left; } break; - case _Rope_constants::_S_leaf: + case ::_S_leaf: { _RopeLeaf* __l = (_RopeLeaf*)__r; return __l->_M_data[__i]; } - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: + case ::_S_function: + case ::_S_substringfn: { _RopeFunction* __f = (_RopeFunction*)__r; _CharT __result; @@ -1371,7 +1371,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) rope<_CharT, _Alloc>:: _S_fetch_ptr(_RopeRep* __r, size_type __i) { - _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth]; + _RopeRep* __clrstack[::_S_max_rope_depth]; size_t __csptr = 0; for(;;) @@ -1380,7 +1380,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) return 0; switch(__r->_M_tag) { - case _Rope_constants::_S_concat: + case ::_S_concat: { _RopeConcatenation* __c = (_RopeConcatenation*)__r; _RopeRep* __left = __c->_M_left; @@ -1397,7 +1397,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) __r = __left; } break; - case _Rope_constants::_S_leaf: + case ::_S_leaf: { _RopeLeaf* __l = (_RopeLeaf*)__r; if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) @@ -1411,8 +1411,8 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) } return __l->_M_data + __i; } - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: + case ::_S_function: + case ::_S_substringfn: return 0; } } @@ -1437,10 +1437,10 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) return -1; __left_len = __left->_M_size; __right_len = __right->_M_size; - if (_Rope_constants::_S_leaf == __left->_M_tag) + if (::_S_leaf == __left->_M_tag) { _RopeLeaf* __l = (_RopeLeaf*) __left; - if (_Rope_constants::_S_leaf == __right->_M_tag) + if (::_S_leaf == __right->_M_tag) { _RopeLeaf* __r = (_RopeLeaf*) __right; return lexicographical_compare_3way(__l->_M_data, @@ -1461,7 +1461,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) { const_iterator __lstart(__left, 0); const_iterator __lend(__left, __left_len); - if (_Rope_constants::_S_leaf == __right->_M_tag) + if (::_S_leaf == __right->_M_tag) { _RopeLeaf* __r = (_RopeLeaf*) __right; return lexicographical_compare_3way(__lstart, __lend, @@ -1637,7 +1637,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) return _S_empty_c_str; } __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string; - if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag + if (::_S_leaf == this->_M_tree_ptr->_M_tag && 0 != __old_c_string) return(__old_c_string); size_t __s = size(); diff --git a/libstdc++-v3/include/tr1/cmath b/libstdc++-v3/include/tr1/cmath index 74b4071..22c9f2e 100644 --- a/libstdc++-v3/include/tr1/cmath +++ b/libstdc++-v3/include/tr1/cmath @@ -146,21 +146,6 @@ #undef truncf #undef truncl -// Workaround for c++/21682. -namespace __gnu_internal -{ - template<typename _Tp, typename _Up> - inline typename - std::__enable_if<typename std::tr1::__promote_2<_Tp, _Up>::__type, - (std::__is_floating<_Tp>::__value - || std::__is_floating<_Up>::__value)>::__type - atan2(_Tp __y, _Up __x) - { - typedef typename std::tr1::__promote_2<_Tp, _Up>::__type __type; - return std::atan2(__type(__y), __type(__x)); - } -} - #endif // namespace std::tr1 @@ -381,10 +366,24 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) } using std::atan; - using std::atan2; // Workaround for c++/21682. - using __gnu_internal::atan2; + namespace detail + { + template<typename _Tp, typename _Up> + inline typename + std::__enable_if<typename std::tr1::__promote_2<_Tp, _Up>::__type, + (std::__is_floating<_Tp>::__value + || std::__is_floating<_Up>::__value)>::__type + atan2(_Tp __y, _Up __x) + { + typedef typename std::tr1::__promote_2<_Tp, _Up>::__type __type; + return std::atan2(__type(__y), __type(__x)); + } + } // namespace detail + + using std::atan2; + using detail::atan2; inline float atanh(float __x) diff --git a/libstdc++-v3/include/tr1/hashtable b/libstdc++-v3/include/tr1/hashtable index d5041f7..9a682db 100644 --- a/libstdc++-v3/include/tr1/hashtable +++ b/libstdc++-v3/include/tr1/hashtable @@ -38,8 +38,6 @@ // the differences between those four classes and partly to // accommodate policy choices that go beyond what TR1 calls for. -// ??? Arguably this should be Internal::hashtable, not std::tr1::hashtable. - // Class template hashtable attempts to encapsulate all reasonable // variation among hash tables that use chaining. It does not handle // open addressing. @@ -48,8 +46,8 @@ // M. Austern, "A Proposal to Add Hash Tables to the Standard // Library (revision 4)," WG21 Document N1456=03-0039, 2003. // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching. -// A. Tavori and V. Dreizin, "Generic Associative Containers", 2004. -// ??? Full citation? +// A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004. +// http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html #ifndef _TR1_HASHTABLE #define _TR1_HASHTABLE 1 @@ -62,882 +60,12 @@ #include <cmath> #include <bits/functexcept.h> #include <tr1/type_traits> // For true_type and false_type - -//---------------------------------------------------------------------- -// General utilities - -namespace Internal -{ - template<bool Flag, typename IfTrue, typename IfFalse> - struct IF; - - template<typename IfTrue, typename IfFalse> - struct IF<true, IfTrue, IfFalse> - { typedef IfTrue type; }; - - template <typename IfTrue, typename IfFalse> - struct IF<false, IfTrue, IfFalse> - { typedef IfFalse type; }; - - // Helper function: return distance(first, last) for forward - // iterators, or 0 for input iterators. - template<class Iterator> - inline typename std::iterator_traits<Iterator>::difference_type - distance_fw(Iterator first, Iterator last, std::input_iterator_tag) - { return 0; } - - template<class Iterator> - inline typename std::iterator_traits<Iterator>::difference_type - distance_fw(Iterator first, Iterator last, std::forward_iterator_tag) - { return std::distance(first, last); } - - template<class Iterator> - inline typename std::iterator_traits<Iterator>::difference_type - distance_fw(Iterator first, Iterator last) - { - typedef typename std::iterator_traits<Iterator>::iterator_category tag; - return distance_fw(first, last, tag()); - } - -} // namespace Internal - - -//---------------------------------------------------------------------- -// Auxiliary types used for all instantiations of hashtable: nodes -// and iterators. - -// Nodes, used to wrap elements stored in the hash table. A policy -// template parameter of class template hashtable controls whether -// nodes also store a hash code. In some cases (e.g. strings) this may -// be a performance win. - -namespace Internal -{ - template<typename Value, bool cache_hash_code> - struct hash_node; - - template<typename Value> - struct hash_node<Value, true> - { - Value m_v; - std::size_t hash_code; - hash_node* m_next; - }; - - template<typename Value> - struct hash_node<Value, false> - { - Value m_v; - hash_node* m_next; - }; - - // Local iterators, used to iterate within a bucket but not between - // buckets. - - template<typename Value, bool cache> - struct node_iterator_base - { - node_iterator_base(hash_node<Value, cache>* p) - : m_cur(p) { } - - void - incr() - { m_cur = m_cur->m_next; } - - hash_node<Value, cache>* m_cur; - }; - - template<typename Value, bool cache> - inline bool - operator==(const node_iterator_base<Value, cache>& x, - const node_iterator_base<Value, cache>& y) - { return x.m_cur == y.m_cur; } - - template<typename Value, bool cache> - inline bool - operator!=(const node_iterator_base<Value, cache>& x, - const node_iterator_base<Value, cache>& y) - { return x.m_cur != y.m_cur; } - - template<typename Value, bool constant_iterators, bool cache> - struct node_iterator - : public node_iterator_base<Value, cache> - { - typedef Value value_type; - typedef typename IF<constant_iterators, const Value*, Value*>::type - pointer; - typedef typename IF<constant_iterators, const Value&, Value&>::type - reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - node_iterator() - : node_iterator_base<Value, cache>(0) { } - - explicit - node_iterator(hash_node<Value, cache>* p) - : node_iterator_base<Value, cache>(p) { } - - reference - operator*() const - { return this->m_cur->m_v; } - - pointer - operator->() const - { return &this->m_cur->m_v; } - - node_iterator& - operator++() - { - this->incr(); - return *this; - } - - node_iterator - operator++(int) - { - node_iterator tmp(*this); - this->incr(); - return tmp; - } - }; - - template<typename Value, bool constant_iterators, bool cache> - struct node_const_iterator - : public node_iterator_base<Value, cache> - { - typedef Value value_type; - typedef const Value* pointer; - typedef const Value& reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - node_const_iterator() - : node_iterator_base<Value, cache>(0) { } - - explicit - node_const_iterator(hash_node<Value, cache>* p) - : node_iterator_base<Value, cache>(p) { } - - node_const_iterator(const node_iterator<Value, constant_iterators, - cache>& x) - : node_iterator_base<Value, cache>(x.m_cur) { } - - reference - operator*() const - { return this->m_cur->m_v; } - - pointer - operator->() const - { return &this->m_cur->m_v; } - - node_const_iterator& - operator++() - { - this->incr(); - return *this; - } - - node_const_iterator - operator++(int) - { - node_const_iterator tmp(*this); - this->incr(); - return tmp; - } - }; - - template<typename Value, bool cache> - struct hashtable_iterator_base - { - hashtable_iterator_base(hash_node<Value, cache>* node, - hash_node<Value, cache>** bucket) - : m_cur_node(node), m_cur_bucket(bucket) { } - - void - incr() - { - m_cur_node = m_cur_node->m_next; - if (!m_cur_node) - m_incr_bucket(); - } - - void - m_incr_bucket(); - - hash_node<Value, cache>* m_cur_node; - hash_node<Value, cache>** m_cur_bucket; - }; - - // Global iterators, used for arbitrary iteration within a hash - // table. Larger and more expensive than local iterators. - template<typename Value, bool cache> - void - hashtable_iterator_base<Value, cache>:: - m_incr_bucket() - { - ++m_cur_bucket; - - // This loop requires the bucket array to have a non-null sentinel. - while (!*m_cur_bucket) - ++m_cur_bucket; - m_cur_node = *m_cur_bucket; - } - - template<typename Value, bool cache> - inline bool - operator==(const hashtable_iterator_base<Value, cache>& x, - const hashtable_iterator_base<Value, cache>& y) - { return x.m_cur_node == y.m_cur_node; } - - template<typename Value, bool cache> - inline bool - operator!=(const hashtable_iterator_base<Value, cache>& x, - const hashtable_iterator_base<Value, cache>& y) - { return x.m_cur_node != y.m_cur_node; } - - template<typename Value, bool constant_iterators, bool cache> - struct hashtable_iterator - : public hashtable_iterator_base<Value, cache> - { - typedef Value value_type; - typedef typename IF<constant_iterators, const Value*, Value*>::type - pointer; - typedef typename IF<constant_iterators, const Value&, Value&>::type - reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - hashtable_iterator() - : hashtable_iterator_base<Value, cache>(0, 0) { } - - hashtable_iterator(hash_node<Value, cache>* p, - hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(p, b) { } - - explicit - hashtable_iterator(hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(*b, b) { } - - reference - operator*() const - { return this->m_cur_node->m_v; } - - pointer - operator->() const - { return &this->m_cur_node->m_v; } - - hashtable_iterator& - operator++() - { - this->incr(); - return *this; - } - - hashtable_iterator - operator++(int) - { - hashtable_iterator tmp(*this); - this->incr(); - return tmp; - } - }; - - template<typename Value, bool constant_iterators, bool cache> - struct hashtable_const_iterator - : public hashtable_iterator_base<Value, cache> - { - typedef Value value_type; - typedef const Value* pointer; - typedef const Value& reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - hashtable_const_iterator() - : hashtable_iterator_base<Value, cache>(0, 0) { } - - hashtable_const_iterator(hash_node<Value, cache>* p, - hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(p, b) { } - - explicit - hashtable_const_iterator(hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(*b, b) { } - - hashtable_const_iterator(const hashtable_iterator<Value, - constant_iterators, cache>& x) - : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { } - - reference - operator*() const - { return this->m_cur_node->m_v; } - - pointer - operator->() const - { return &this->m_cur_node->m_v; } - - hashtable_const_iterator& - operator++() - { - this->incr(); - return *this; - } - - hashtable_const_iterator - operator++(int) - { - hashtable_const_iterator tmp(*this); - this->incr(); - return tmp; - } - }; -} // namespace Internal - - -// ---------------------------------------------------------------------- -// Many of class template hashtable's template parameters are policy -// classes. These are defaults for the policies. - -namespace Internal -{ - // The two key extraction policies used by the *set and *map variants. - template<typename T> - struct identity - { - const T& - operator()(const T& t) const - { return t; } - }; - - template<typename Pair> - struct extract1st - { - const typename Pair::first_type& - operator()(const Pair& p) const - { return p.first; } - }; - - // Default range hashing function: use division to fold a large number - // into the range [0, N). - struct mod_range_hashing - { - typedef std::size_t first_argument_type; - typedef std::size_t second_argument_type; - typedef std::size_t result_type; - - result_type - operator()(first_argument_type r, second_argument_type N) const - { return r % N; } - }; - - // Default ranged hash function H. In principle it should be a - // function object composed from objects of type H1 and H2 such that - // h(k, N) = h2(h1(k), N), but that would mean making extra copies of - // h1 and h2. So instead we'll just use a tag to tell class template - // hashtable to do that composition. - struct default_ranged_hash { }; - - // Default value for rehash policy. Bucket size is (usually) the - // smallest prime that keeps the load factor small enough. - struct prime_rehash_policy - { - prime_rehash_policy(float z = 1.0); - - float - max_load_factor() const; - - // Return a bucket size no smaller than n. - std::size_t - next_bkt(std::size_t n) const; - - // Return a bucket count appropriate for n elements - std::size_t - bkt_for_elements(std::size_t n) const; - - // n_bkt is current bucket count, n_elt is current element count, - // and n_ins is number of elements to be inserted. Do we need to - // increase bucket count? If so, return make_pair(true, n), where n - // is the new bucket count. If not, return make_pair(false, 0). - std::pair<bool, std::size_t> - need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const; - - float m_max_load_factor; - float m_growth_factor; - mutable std::size_t m_next_resize; - }; - - // XXX This is a hack. prime_rehash_policy's member functions, and - // certainly the list of primes, should be defined in a .cc file. - // We're temporarily putting them in a header because we don't have a - // place to put TR1 .cc files yet. There's no good reason for any of - // prime_rehash_policy's member functions to be inline, and there's - // certainly no good reason for X<> to exist at all. - - struct lt - { - template<typename X, typename Y> - bool - operator()(X x, Y y) - { return x < y; } - }; - - template<int ulongsize = sizeof(unsigned long)> - struct X - { - static const int n_primes = ulongsize != 8 ? 256 : 256 + 48; - static const unsigned long primes[256 + 48 + 1]; - }; - - template<int ulongsize> - const int X<ulongsize>::n_primes; - - template<int ulongsize> - const unsigned long X<ulongsize>::primes[256 + 48 + 1] = - { - 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, - 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, - 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, - 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, - 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, - 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, - 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, - 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, - 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, - 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, - 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, - 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, - 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, - 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, - 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, - 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, - 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, - 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, - 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, - 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, - 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, - 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, - 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, - 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, - 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, - 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, - 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, - 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, - 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, - 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, - 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, - 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, - 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, - 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, - 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, - 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, - 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, - 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, - 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, - 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, - 4294967291ul, - // Sentinel, so we don't have to test the result of lower_bound, - // or, on 64-bit machines, rest of the table. - ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull, - (unsigned long)8589934583ull, - (unsigned long)12884901857ull, (unsigned long)17179869143ull, - (unsigned long)25769803693ull, (unsigned long)34359738337ull, - (unsigned long)51539607367ull, (unsigned long)68719476731ull, - (unsigned long)103079215087ull, (unsigned long)137438953447ull, - (unsigned long)206158430123ull, (unsigned long)274877906899ull, - (unsigned long)412316860387ull, (unsigned long)549755813881ull, - (unsigned long)824633720731ull, (unsigned long)1099511627689ull, - (unsigned long)1649267441579ull, (unsigned long)2199023255531ull, - (unsigned long)3298534883309ull, (unsigned long)4398046511093ull, - (unsigned long)6597069766607ull, (unsigned long)8796093022151ull, - (unsigned long)13194139533241ull, (unsigned long)17592186044399ull, - (unsigned long)26388279066581ull, (unsigned long)35184372088777ull, - (unsigned long)52776558133177ull, (unsigned long)70368744177643ull, - (unsigned long)105553116266399ull, (unsigned long)140737488355213ull, - (unsigned long)211106232532861ull, (unsigned long)281474976710597ull, - (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull, - (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull, - (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull, - (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull, - (unsigned long)144115188075855859ull, - (unsigned long)288230376151711717ull, - (unsigned long)576460752303423433ull, - (unsigned long)1152921504606846883ull, - (unsigned long)2305843009213693951ull, - (unsigned long)4611686018427387847ull, - (unsigned long)9223372036854775783ull, - (unsigned long)18446744073709551557ull, - (unsigned long)18446744073709551557ull - }; - - inline - prime_rehash_policy:: - prime_rehash_policy(float z) - : m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0) - { } - - inline float - prime_rehash_policy:: - max_load_factor() const - { return m_max_load_factor; } - - // Return a prime no smaller than n. - inline std::size_t - prime_rehash_policy:: - next_bkt(std::size_t n) const - { - const unsigned long* const last = X<>::primes + X<>::n_primes; - const unsigned long* p = std::lower_bound(X<>::primes, last, n); - m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return *p; - } - - // Return the smallest prime p such that alpha p >= n, where alpha - // is the load factor. - inline std::size_t - prime_rehash_policy:: - bkt_for_elements(std::size_t n) const - { - const unsigned long* const last = X<>::primes + X<>::n_primes; - const float min_bkts = n / m_max_load_factor; - const unsigned long* p = std::lower_bound(X<>::primes, last, - min_bkts, lt()); - m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return *p; - } - - // Finds the smallest prime p such that alpha p > n_elt + n_ins. - // If p > n_bkt, return make_pair(true, p); otherwise return - // make_pair(false, 0). In principle this isn't very different from - // bkt_for_elements. - - // The only tricky part is that we're caching the element count at - // which we need to rehash, so we don't have to do a floating-point - // multiply for every insertion. - - inline std::pair<bool, std::size_t> - prime_rehash_policy:: - need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const - { - if (n_elt + n_ins > m_next_resize) - { - float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor; - if (min_bkts > n_bkt) - { - min_bkts = std::max(min_bkts, m_growth_factor * n_bkt); - const unsigned long* const last = X<>::primes + X<>::n_primes; - const unsigned long* p = std::lower_bound(X<>::primes, last, - min_bkts, lt()); - m_next_resize = - static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return std::make_pair(true, *p); - } - else - { - m_next_resize = - static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor)); - return std::make_pair(false, 0); - } - } - else - return std::make_pair(false, 0); - } - -} // namespace Internal - - -//---------------------------------------------------------------------- -// Base classes for std::tr1::hashtable. We define these base classes -// because in some cases we want to do different things depending on -// the value of a policy class. In some cases the policy class affects -// which member functions and nested typedefs are defined; we handle that -// by specializing base class templates. Several of the base class templates -// need to access other members of class template hashtable, so we use -// the "curiously recurring template pattern" for them. - -namespace Internal -{ - // class template map_base. If the hashtable has a value type of the - // form pair<T1, T2> and a key extraction policy that returns the - // first part of the pair, the hashtable gets a mapped_type typedef. - // If it satisfies those criteria and also has unique keys, then it - // also gets an operator[]. - - template<typename K, typename V, typename Ex, bool unique, typename Hashtable> - struct map_base { }; - - template<typename K, typename Pair, typename Hashtable> - struct map_base<K, Pair, extract1st<Pair>, false, Hashtable> - { - typedef typename Pair::second_type mapped_type; - }; - - template<typename K, typename Pair, typename Hashtable> - struct map_base<K, Pair, extract1st<Pair>, true, Hashtable> - { - typedef typename Pair::second_type mapped_type; - - mapped_type& - operator[](const K& k); - }; - - template<typename K, typename Pair, typename Hashtable> - typename map_base<K, Pair, extract1st<Pair>, true, Hashtable>::mapped_type& - map_base<K, Pair, extract1st<Pair>, true, Hashtable>:: - operator[](const K& k) - { - Hashtable* h = static_cast<Hashtable*>(this); - typename Hashtable::hash_code_t code = h->m_hash_code(k); - std::size_t n = h->bucket_index(k, code, h->bucket_count()); - - typename Hashtable::node* p = h->m_find_node(h->m_buckets[n], k, code); - if (!p) - return h->m_insert_bucket(std::make_pair(k, mapped_type()), - n, code)->second; - return (p->m_v).second; - } - - // class template rehash_base. Give hashtable the max_load_factor - // functions iff the rehash policy is prime_rehash_policy. - template<typename RehashPolicy, typename Hashtable> - struct rehash_base { }; - - template<typename Hashtable> - struct rehash_base<prime_rehash_policy, Hashtable> - { - float - max_load_factor() const - { - const Hashtable* This = static_cast<const Hashtable*>(this); - return This->rehash_policy().max_load_factor(); - } - - void - max_load_factor(float z) - { - Hashtable* This = static_cast<Hashtable*>(this); - This->rehash_policy(prime_rehash_policy(z)); - } - }; - - // Class template hash_code_base. Encapsulates two policy issues that - // aren't quite orthogonal. - // (1) the difference between using a ranged hash function and using - // the combination of a hash function and a range-hashing function. - // In the former case we don't have such things as hash codes, so - // we have a dummy type as placeholder. - // (2) Whether or not we cache hash codes. Caching hash codes is - // meaningless if we have a ranged hash function. - // We also put the key extraction and equality comparison function - // objects here, for convenience. - - // Primary template: unused except as a hook for specializations. - - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H, - bool cache_hash_code> - struct hash_code_base; - - // Specialization: ranged hash function, no caching hash codes. H1 - // and H2 are provided but ignored. We define a dummy hash code type. - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false> - { - protected: - hash_code_base(const ExtractKey& ex, const Equal& eq, - const H1&, const H2&, const H& h) - : m_extract(ex), m_eq(eq), m_ranged_hash(h) { } - - typedef void* hash_code_t; - - hash_code_t - m_hash_code(const Key& k) const - { return 0; } - - std::size_t - bucket_index(const Key& k, hash_code_t, std::size_t N) const - { return m_ranged_hash(k, N); } - - std::size_t - bucket_index(const hash_node<Value, false>* p, std::size_t N) const - { return m_ranged_hash(m_extract(p->m_v), N); } - - bool - compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const - { return m_eq(k, m_extract(n->m_v)); } - - void - store_code(hash_node<Value, false>*, hash_code_t) const - { } - - void - copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const - { } - - void - m_swap(hash_code_base& x) - { - std::swap(m_extract, x.m_extract); - std::swap(m_eq, x.m_eq); - std::swap(m_ranged_hash, x.m_ranged_hash); - } - - protected: - ExtractKey m_extract; - Equal m_eq; - H m_ranged_hash; - }; - - - // No specialization for ranged hash function while caching hash codes. - // That combination is meaningless, and trying to do it is an error. - - - // Specialization: ranged hash function, cache hash codes. This - // combination is meaningless, so we provide only a declaration - // and no definition. - - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>; - - - // Specialization: hash function and range-hashing function, no - // caching of hash codes. H is provided but ignored. Provides - // typedef and accessor required by TR1. - - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, - default_ranged_hash, false> - { - typedef H1 hasher; - - hasher - hash_function() const - { return m_h1; } - - protected: - hash_code_base(const ExtractKey& ex, const Equal& eq, - const H1& h1, const H2& h2, const default_ranged_hash&) - : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } - - typedef std::size_t hash_code_t; - - hash_code_t - m_hash_code(const Key& k) const - { return m_h1(k); } - - std::size_t - bucket_index(const Key&, hash_code_t c, std::size_t N) const - { return m_h2(c, N); } - - std::size_t - bucket_index(const hash_node<Value, false>* p, std::size_t N) const - { return m_h2(m_h1(m_extract(p->m_v)), N); } - - bool - compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const - { return m_eq(k, m_extract(n->m_v)); } - - void - store_code(hash_node<Value, false>*, hash_code_t) const - { } - - void - copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const - { } - - void - m_swap(hash_code_base& x) - { - std::swap(m_extract, x.m_extract); - std::swap(m_eq, x.m_eq); - std::swap(m_h1, x.m_h1); - std::swap(m_h2, x.m_h2); - } - - protected: - ExtractKey m_extract; - Equal m_eq; - H1 m_h1; - H2 m_h2; - }; - - // Specialization: hash function and range-hashing function, - // caching hash codes. H is provided but ignored. Provides - // typedef and accessor required by TR1. - template<typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2> - struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, - default_ranged_hash, true> - { - typedef H1 hasher; - - hasher - hash_function() const - { return m_h1; } - - protected: - hash_code_base(const ExtractKey& ex, const Equal& eq, - const H1& h1, const H2& h2, const default_ranged_hash&) - : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } - - typedef std::size_t hash_code_t; - - hash_code_t - m_hash_code(const Key& k) const - { return m_h1(k); } - - std::size_t - bucket_index(const Key&, hash_code_t c, std::size_t N) const - { return m_h2(c, N); } - - std::size_t - bucket_index(const hash_node<Value, true>* p, std::size_t N) const - { return m_h2(p->hash_code, N); } - - bool - compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const - { return c == n->hash_code && m_eq(k, m_extract(n->m_v)); } - - void - store_code(hash_node<Value, true>* n, hash_code_t c) const - { n->hash_code = c; } - - void - copy_code(hash_node<Value, true>* to, - const hash_node<Value, true>* from) const - { to->hash_code = from->hash_code; } - - void - m_swap(hash_code_base& x) - { - std::swap(m_extract, x.m_extract); - std::swap(m_eq, x.m_eq); - std::swap(m_h1, x.m_h1); - std::swap(m_h2, x.m_h2); - } - - protected: - ExtractKey m_extract; - Equal m_eq; - H1 m_h1; - H2 m_h2; - }; - -} // namespace internal +#include <tr1/hashtable_policy.h> namespace std { _GLIBCXX_BEGIN_NAMESPACE(tr1) - //---------------------------------------------------------------------- // Class template hashtable, class definition. // Meaning of class template hashtable's template parameters @@ -994,27 +122,26 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // true for unordered_set and unordered_map, false for unordered_multiset // and unordered_multimap. - template<typename Key, typename Value, - typename Allocator, + template<typename Key, typename Value, typename Allocator, typename ExtractKey, typename Equal, - typename H1, typename H2, - typename H, typename RehashPolicy, + typename H1, typename H2, typename H, + typename RehashPolicy, bool cache_hash_code, bool constant_iterators, bool unique_keys> class hashtable - : public Internal::rehash_base<RehashPolicy, - hashtable<Key, Value, Allocator, ExtractKey, - Equal, H1, H2, H, RehashPolicy, - cache_hash_code, constant_iterators, - unique_keys> >, - public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, - cache_hash_code>, - public Internal::map_base<Key, Value, ExtractKey, unique_keys, - hashtable<Key, Value, Allocator, ExtractKey, - Equal, H1, H2, H, RehashPolicy, - cache_hash_code, constant_iterators, - unique_keys> > + : public detail::rehash_base<RehashPolicy, + hashtable<Key, Value, Allocator, ExtractKey, + Equal, H1, H2, H, RehashPolicy, + cache_hash_code, constant_iterators, + unique_keys> >, + public detail::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, + cache_hash_code>, + public detail::map_base<Key, Value, ExtractKey, unique_keys, + hashtable<Key, Value, Allocator, ExtractKey, + Equal, H1, H2, H, RehashPolicy, + cache_hash_code, constant_iterators, + unique_keys> > { public: typedef Allocator allocator_type; @@ -1028,31 +155,30 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) typedef typename Allocator::reference reference; typedef typename Allocator::const_reference const_reference; - typedef Internal::node_iterator<value_type, constant_iterators, + typedef detail::node_iterator<value_type, constant_iterators, cache_hash_code> local_iterator; - typedef Internal::node_const_iterator<value_type, constant_iterators, + typedef detail::node_const_iterator<value_type, constant_iterators, cache_hash_code> const_local_iterator; - typedef Internal::hashtable_iterator<value_type, constant_iterators, + typedef detail::hashtable_iterator<value_type, constant_iterators, cache_hash_code> iterator; - typedef Internal::hashtable_const_iterator<value_type, constant_iterators, + typedef detail::hashtable_const_iterator<value_type, constant_iterators, cache_hash_code> const_iterator; template<typename K, typename Pair, typename Hashtable> - friend struct Internal::map_base; + friend struct detail::map_base; private: - typedef Internal::hash_node<Value, cache_hash_code> node; + typedef detail::hash_node<Value, cache_hash_code> node; typedef typename Allocator::template rebind<node>::other node_allocator_t; typedef typename Allocator::template rebind<node*>::other bucket_allocator_t; - private: node_allocator_t m_node_allocator; node** m_buckets; size_type m_bucket_count; @@ -1074,7 +200,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void m_deallocate_buckets(node**, size_type n); - public: // Constructor, destructor, assignment, swap + public: + // Constructor, destructor, assignment, swap hashtable(size_type bucket_hint, const H1&, const H2&, const H&, const Equal&, const ExtractKey&, @@ -1096,7 +223,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void swap(hashtable&); - public: // Basic container operations + // Basic container operations iterator begin() { @@ -1139,14 +266,14 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) max_size() const { return m_node_allocator.max_size(); } - public: // Observers + // Observers key_equal key_eq() const { return this->m_eq; } // hash_function, if present, comes from hash_code_base. - public: // Bucket operations + // Bucket operations size_type bucket_count() const { return m_bucket_count; } @@ -1199,7 +326,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void rehash_policy(const RehashPolicy&); - public: // lookup + // Lookup. iterator find(const key_type& k); @@ -1220,13 +347,13 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // have partial specialization of member templates; it would be // better to just specialize insert on unique_keys. There may be a // cleaner workaround. - typedef typename Internal::IF<unique_keys, + typedef typename detail::IF<unique_keys, std::pair<iterator, bool>, iterator>::type Insert_Return_Type; - typedef typename Internal::IF<unique_keys, - Internal::extract1st<Insert_Return_Type>, - Internal::identity<Insert_Return_Type> + typedef typename detail::IF<unique_keys, + detail::extract1st<Insert_Return_Type>, + detail::identity<Insert_Return_Type> >::type Insert_Conv_Type; @@ -1247,7 +374,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void m_erase_node(node*, node**); - public: // Insert and erase + public: + // Insert and erase Insert_Return_Type insert(const value_type& v) { return m_insert(v, std::tr1::integral_constant<bool, unique_keys>()); } @@ -1282,7 +410,6 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) void clear(); - public: // Set number of buckets to be appropriate for container of n element. void rehash(size_type n); @@ -1292,9 +419,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) }; - //---------------------------------------------------------------------- // Definitions of class template hashtable's out-of-line member functions. - template<typename K, typename V, typename A, typename Ex, typename Eq, typename H1, typename H2, typename H, typename RP, @@ -1389,9 +514,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const H1& h1, const H2& h2, const H& h, const Eq& eq, const Ex& exk, const allocator_type& a) - : Internal::rehash_base<RP, hashtable>(), - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h), - Internal::map_base<K, V, Ex, u, hashtable>(), + : detail::rehash_base<RP, hashtable>(), + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h), + detail::map_base<K, V, Ex, u, hashtable>(), m_node_allocator(a), m_bucket_count(0), m_element_count(0), @@ -1412,10 +537,10 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const H1& h1, const H2& h2, const H& h, const Eq& eq, const Ex& exk, const allocator_type& a) - : Internal::rehash_base<RP, hashtable>(), - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, + : detail::rehash_base<RP, hashtable>(), + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h), - Internal::map_base<K, V, Ex, u, hashtable>(), + detail::map_base<K, V, Ex, u, hashtable>(), m_node_allocator(a), m_bucket_count(0), m_element_count(0), @@ -1423,7 +548,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) { m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint), m_rehash_policy. - bkt_for_elements(Internal:: + bkt_for_elements(detail:: distance_fw(f, l))); m_buckets = m_allocate_buckets(m_bucket_count); try @@ -1445,9 +570,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) bool c, bool ci, bool u> hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>:: hashtable(const hashtable& ht) - : Internal::rehash_base<RP, hashtable>(ht), - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht), - Internal::map_base<K, V, Ex, u, hashtable>(ht), + : detail::rehash_base<RP, hashtable>(ht), + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht), + detail::map_base<K, V, Ex, u, hashtable>(ht), m_node_allocator(ht.get_allocator()), m_bucket_count(ht.m_bucket_count), m_element_count(ht.m_element_count), @@ -1512,7 +637,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // The only base class with member variables is hash_code_base. We // define hash_code_base::m_swap because different specializations // have different members. - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x); + detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 431. Swapping containers with unequal allocators. @@ -1799,7 +924,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>:: insert(InIter first, InIter last) { - size_type n_elt = Internal::distance_fw(first, last); + size_type n_elt = detail::distance_fw(first, last); std::pair<bool, std::size_t> do_rehash = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt); if (do_rehash.first) diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h new file mode 100644 index 0000000..57b6e89 --- /dev/null +++ b/libstdc++-v3/include/tr1/hashtable_policy.h @@ -0,0 +1,893 @@ +// Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- + +// Copyright (C) 2005, 2006 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +/** @file + * This is a TR1 C++ Library header. + */ + +#ifndef _TR1_HASHTABLE_POLICY_H +#define _TR1_HASHTABLE_POLICY_H 1 + +namespace std +{ +_GLIBCXX_BEGIN_NAMESPACE(tr1) +namespace detail +{ +namespace +{ + // General utilities. + template<bool Flag, typename IfTrue, typename IfFalse> + struct IF; + + template<typename IfTrue, typename IfFalse> + struct IF<true, IfTrue, IfFalse> + { typedef IfTrue type; }; + + template <typename IfTrue, typename IfFalse> + struct IF<false, IfTrue, IfFalse> + { typedef IfFalse type; }; + + // Helper function: return distance(first, last) for forward + // iterators, or 0 for input iterators. + template<class Iterator> + inline typename std::iterator_traits<Iterator>::difference_type + distance_fw(Iterator first, Iterator last, std::input_iterator_tag) + { return 0; } + + template<class Iterator> + inline typename std::iterator_traits<Iterator>::difference_type + distance_fw(Iterator first, Iterator last, std::forward_iterator_tag) + { return std::distance(first, last); } + + template<class Iterator> + inline typename std::iterator_traits<Iterator>::difference_type + distance_fw(Iterator first, Iterator last) + { + typedef typename std::iterator_traits<Iterator>::iterator_category tag; + return distance_fw(first, last, tag()); + } + + // XXX This is a hack. prime_rehash_policy's member functions, and + // certainly the list of primes, should be defined in a .cc file. + // We're temporarily putting them in a header because we don't have a + // place to put TR1 .cc files yet. There's no good reason for any of + // prime_rehash_policy's member functions to be inline, and there's + // certainly no good reason for X<> to exist at all. + struct lt + { + template<typename X, typename Y> + bool + operator()(X x, Y y) + { return x < y; } + }; + + template<int ulongsize = sizeof(unsigned long)> + struct X + { + static const int n_primes = ulongsize != 8 ? 256 : 256 + 48; + static const unsigned long primes[256 + 48 + 1]; + }; + + template<int ulongsize> + const int X<ulongsize>::n_primes; + + template<int ulongsize> + const unsigned long X<ulongsize>::primes[256 + 48 + 1] = + { + 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, + 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, + 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, + 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, + 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, + 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, + 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, + 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, + 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, + 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, + 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, + 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, + 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, + 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, + 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, + 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, + 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, + 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, + 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, + 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, + 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, + 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, + 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, + 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, + 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, + 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, + 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, + 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, + 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, + 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, + 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, + 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, + 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, + 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, + 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, + 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, + 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, + 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, + 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, + 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, + 4294967291ul, + // Sentinel, so we don't have to test the result of lower_bound, + // or, on 64-bit machines, rest of the table. + ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull, + (unsigned long)8589934583ull, + (unsigned long)12884901857ull, (unsigned long)17179869143ull, + (unsigned long)25769803693ull, (unsigned long)34359738337ull, + (unsigned long)51539607367ull, (unsigned long)68719476731ull, + (unsigned long)103079215087ull, (unsigned long)137438953447ull, + (unsigned long)206158430123ull, (unsigned long)274877906899ull, + (unsigned long)412316860387ull, (unsigned long)549755813881ull, + (unsigned long)824633720731ull, (unsigned long)1099511627689ull, + (unsigned long)1649267441579ull, (unsigned long)2199023255531ull, + (unsigned long)3298534883309ull, (unsigned long)4398046511093ull, + (unsigned long)6597069766607ull, (unsigned long)8796093022151ull, + (unsigned long)13194139533241ull, (unsigned long)17592186044399ull, + (unsigned long)26388279066581ull, (unsigned long)35184372088777ull, + (unsigned long)52776558133177ull, (unsigned long)70368744177643ull, + (unsigned long)105553116266399ull, (unsigned long)140737488355213ull, + (unsigned long)211106232532861ull, (unsigned long)281474976710597ull, + (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull, + (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull, + (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull, + (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull, + (unsigned long)144115188075855859ull, + (unsigned long)288230376151711717ull, + (unsigned long)576460752303423433ull, + (unsigned long)1152921504606846883ull, + (unsigned long)2305843009213693951ull, + (unsigned long)4611686018427387847ull, + (unsigned long)9223372036854775783ull, + (unsigned long)18446744073709551557ull, + (unsigned long)18446744073709551557ull + }; +} // anonymous namespace + + // Auxiliary types used for all instantiations of hashtable: nodes + // and iterators. + + // Nodes, used to wrap elements stored in the hash table. A policy + // template parameter of class template hashtable controls whether + // nodes also store a hash code. In some cases (e.g. strings) this + // may be a performance win. + template<typename Value, bool cache_hash_code> + struct hash_node; + + template<typename Value> + struct hash_node<Value, true> + { + Value m_v; + std::size_t hash_code; + hash_node* m_next; + }; + + template<typename Value> + struct hash_node<Value, false> + { + Value m_v; + hash_node* m_next; + }; + + // Local iterators, used to iterate within a bucket but not between + // buckets. + template<typename Value, bool cache> + struct node_iterator_base + { + node_iterator_base(hash_node<Value, cache>* p) + : m_cur(p) { } + + void + incr() + { m_cur = m_cur->m_next; } + + hash_node<Value, cache>* m_cur; + }; + + template<typename Value, bool cache> + inline bool + operator==(const node_iterator_base<Value, cache>& x, + const node_iterator_base<Value, cache>& y) + { return x.m_cur == y.m_cur; } + + template<typename Value, bool cache> + inline bool + operator!=(const node_iterator_base<Value, cache>& x, + const node_iterator_base<Value, cache>& y) + { return x.m_cur != y.m_cur; } + + template<typename Value, bool constant_iterators, bool cache> + struct node_iterator + : public node_iterator_base<Value, cache> + { + typedef Value value_type; + typedef typename IF<constant_iterators, const Value*, Value*>::type + pointer; + typedef typename IF<constant_iterators, const Value&, Value&>::type + reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + node_iterator() + : node_iterator_base<Value, cache>(0) { } + + explicit + node_iterator(hash_node<Value, cache>* p) + : node_iterator_base<Value, cache>(p) { } + + reference + operator*() const + { return this->m_cur->m_v; } + + pointer + operator->() const + { return &this->m_cur->m_v; } + + node_iterator& + operator++() + { + this->incr(); + return *this; + } + + node_iterator + operator++(int) + { + node_iterator tmp(*this); + this->incr(); + return tmp; + } + }; + + template<typename Value, bool constant_iterators, bool cache> + struct node_const_iterator + : public node_iterator_base<Value, cache> + { + typedef Value value_type; + typedef const Value* pointer; + typedef const Value& reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + node_const_iterator() + : node_iterator_base<Value, cache>(0) { } + + explicit + node_const_iterator(hash_node<Value, cache>* p) + : node_iterator_base<Value, cache>(p) { } + + node_const_iterator(const node_iterator<Value, constant_iterators, + cache>& x) + : node_iterator_base<Value, cache>(x.m_cur) { } + + reference + operator*() const + { return this->m_cur->m_v; } + + pointer + operator->() const + { return &this->m_cur->m_v; } + + node_const_iterator& + operator++() + { + this->incr(); + return *this; + } + + node_const_iterator + operator++(int) + { + node_const_iterator tmp(*this); + this->incr(); + return tmp; + } + }; + + template<typename Value, bool cache> + struct hashtable_iterator_base + { + hashtable_iterator_base(hash_node<Value, cache>* node, + hash_node<Value, cache>** bucket) + : m_cur_node(node), m_cur_bucket(bucket) { } + + void + incr() + { + m_cur_node = m_cur_node->m_next; + if (!m_cur_node) + m_incr_bucket(); + } + + void + m_incr_bucket(); + + hash_node<Value, cache>* m_cur_node; + hash_node<Value, cache>** m_cur_bucket; + }; + + // Global iterators, used for arbitrary iteration within a hash + // table. Larger and more expensive than local iterators. + template<typename Value, bool cache> + void + hashtable_iterator_base<Value, cache>:: + m_incr_bucket() + { + ++m_cur_bucket; + + // This loop requires the bucket array to have a non-null sentinel. + while (!*m_cur_bucket) + ++m_cur_bucket; + m_cur_node = *m_cur_bucket; + } + + template<typename Value, bool cache> + inline bool + operator==(const hashtable_iterator_base<Value, cache>& x, + const hashtable_iterator_base<Value, cache>& y) + { return x.m_cur_node == y.m_cur_node; } + + template<typename Value, bool cache> + inline bool + operator!=(const hashtable_iterator_base<Value, cache>& x, + const hashtable_iterator_base<Value, cache>& y) + { return x.m_cur_node != y.m_cur_node; } + + template<typename Value, bool constant_iterators, bool cache> + struct hashtable_iterator + : public hashtable_iterator_base<Value, cache> + { + typedef Value value_type; + typedef typename IF<constant_iterators, const Value*, Value*>::type + pointer; + typedef typename IF<constant_iterators, const Value&, Value&>::type + reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + hashtable_iterator() + : hashtable_iterator_base<Value, cache>(0, 0) { } + + hashtable_iterator(hash_node<Value, cache>* p, + hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(p, b) { } + + explicit + hashtable_iterator(hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(*b, b) { } + + reference + operator*() const + { return this->m_cur_node->m_v; } + + pointer + operator->() const + { return &this->m_cur_node->m_v; } + + hashtable_iterator& + operator++() + { + this->incr(); + return *this; + } + + hashtable_iterator + operator++(int) + { + hashtable_iterator tmp(*this); + this->incr(); + return tmp; + } + }; + + template<typename Value, bool constant_iterators, bool cache> + struct hashtable_const_iterator + : public hashtable_iterator_base<Value, cache> + { + typedef Value value_type; + typedef const Value* pointer; + typedef const Value& reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + hashtable_const_iterator() + : hashtable_iterator_base<Value, cache>(0, 0) { } + + hashtable_const_iterator(hash_node<Value, cache>* p, + hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(p, b) { } + + explicit + hashtable_const_iterator(hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(*b, b) { } + + hashtable_const_iterator(const hashtable_iterator<Value, + constant_iterators, cache>& x) + : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { } + + reference + operator*() const + { return this->m_cur_node->m_v; } + + pointer + operator->() const + { return &this->m_cur_node->m_v; } + + hashtable_const_iterator& + operator++() + { + this->incr(); + return *this; + } + + hashtable_const_iterator + operator++(int) + { + hashtable_const_iterator tmp(*this); + this->incr(); + return tmp; + } + }; + + + // Many of class template hashtable's template parameters are policy + // classes. These are defaults for the policies. + + // The two key extraction policies used by the *set and *map variants. + // XXX pb_ds::type_to_type + template<typename T> + struct identity + { + const T& + operator()(const T& t) const + { return t; } + }; + + // XXX use std::_Select1st? + template<typename Pair> + struct extract1st + { + const typename Pair::first_type& + operator()(const Pair& p) const + { return p.first; } + }; + + // Default range hashing function: use division to fold a large number + // into the range [0, N). + struct mod_range_hashing + { + typedef std::size_t first_argument_type; + typedef std::size_t second_argument_type; + typedef std::size_t result_type; + + result_type + operator()(first_argument_type r, second_argument_type N) const + { return r % N; } + }; + + // Default ranged hash function H. In principle it should be a + // function object composed from objects of type H1 and H2 such that + // h(k, N) = h2(h1(k), N), but that would mean making extra copies of + // h1 and h2. So instead we'll just use a tag to tell class template + // hashtable to do that composition. + struct default_ranged_hash { }; + + // Default value for rehash policy. Bucket size is (usually) the + // smallest prime that keeps the load factor small enough. + struct prime_rehash_policy + { + prime_rehash_policy(float z = 1.0); + + float + max_load_factor() const; + + // Return a bucket size no smaller than n. + std::size_t + next_bkt(std::size_t n) const; + + // Return a bucket count appropriate for n elements + std::size_t + bkt_for_elements(std::size_t n) const; + + // n_bkt is current bucket count, n_elt is current element count, + // and n_ins is number of elements to be inserted. Do we need to + // increase bucket count? If so, return make_pair(true, n), where n + // is the new bucket count. If not, return make_pair(false, 0). + std::pair<bool, std::size_t> + need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const; + + float m_max_load_factor; + float m_growth_factor; + mutable std::size_t m_next_resize; + }; + + inline + prime_rehash_policy:: + prime_rehash_policy(float z) + : m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0) + { } + + inline float + prime_rehash_policy:: + max_load_factor() const + { return m_max_load_factor; } + + // Return a prime no smaller than n. + inline std::size_t + prime_rehash_policy:: + next_bkt(std::size_t n) const + { + const unsigned long* const last = X<>::primes + X<>::n_primes; + const unsigned long* p = std::lower_bound(X<>::primes, last, n); + m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); + return *p; + } + + // Return the smallest prime p such that alpha p >= n, where alpha + // is the load factor. + inline std::size_t + prime_rehash_policy:: + bkt_for_elements(std::size_t n) const + { + const unsigned long* const last = X<>::primes + X<>::n_primes; + const float min_bkts = n / m_max_load_factor; + const unsigned long* p = std::lower_bound(X<>::primes, last, + min_bkts, lt()); + m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); + return *p; + } + + // Finds the smallest prime p such that alpha p > n_elt + n_ins. + // If p > n_bkt, return make_pair(true, p); otherwise return + // make_pair(false, 0). In principle this isn't very different from + // bkt_for_elements. + + // The only tricky part is that we're caching the element count at + // which we need to rehash, so we don't have to do a floating-point + // multiply for every insertion. + + inline std::pair<bool, std::size_t> + prime_rehash_policy:: + need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const + { + if (n_elt + n_ins > m_next_resize) + { + float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor; + if (min_bkts > n_bkt) + { + min_bkts = std::max(min_bkts, m_growth_factor * n_bkt); + const unsigned long* const last = X<>::primes + X<>::n_primes; + const unsigned long* p = std::lower_bound(X<>::primes, last, + min_bkts, lt()); + m_next_resize = + static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); + return std::make_pair(true, *p); + } + else + { + m_next_resize = + static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor)); + return std::make_pair(false, 0); + } + } + else + return std::make_pair(false, 0); + } + + // Base classes for std::tr1::hashtable. We define these base + // classes because in some cases we want to do different things + // depending on the value of a policy class. In some cases the + // policy class affects which member functions and nested typedefs + // are defined; we handle that by specializing base class templates. + // Several of the base class templates need to access other members + // of class template hashtable, so we use the "curiously recurring + // template pattern" for them. + + // class template map_base. If the hashtable has a value type of the + // form pair<T1, T2> and a key extraction policy that returns the + // first part of the pair, the hashtable gets a mapped_type typedef. + // If it satisfies those criteria and also has unique keys, then it + // also gets an operator[]. + template<typename K, typename V, typename Ex, bool unique, typename Hashtable> + struct map_base { }; + + template<typename K, typename Pair, typename Hashtable> + struct map_base<K, Pair, extract1st<Pair>, false, Hashtable> + { + typedef typename Pair::second_type mapped_type; + }; + + template<typename K, typename Pair, typename Hashtable> + struct map_base<K, Pair, extract1st<Pair>, true, Hashtable> + { + typedef typename Pair::second_type mapped_type; + + mapped_type& + operator[](const K& k); + }; + + template<typename K, typename Pair, typename Hashtable> + typename map_base<K, Pair, extract1st<Pair>, true, Hashtable>::mapped_type& + map_base<K, Pair, extract1st<Pair>, true, Hashtable>:: + operator[](const K& k) + { + Hashtable* h = static_cast<Hashtable*>(this); + typename Hashtable::hash_code_t code = h->m_hash_code(k); + std::size_t n = h->bucket_index(k, code, h->bucket_count()); + + typename Hashtable::node* p = h->m_find_node(h->m_buckets[n], k, code); + if (!p) + return h->m_insert_bucket(std::make_pair(k, mapped_type()), + n, code)->second; + return (p->m_v).second; + } + + // class template rehash_base. Give hashtable the max_load_factor + // functions iff the rehash policy is prime_rehash_policy. + template<typename RehashPolicy, typename Hashtable> + struct rehash_base { }; + + template<typename Hashtable> + struct rehash_base<prime_rehash_policy, Hashtable> + { + float + max_load_factor() const + { + const Hashtable* This = static_cast<const Hashtable*>(this); + return This->rehash_policy().max_load_factor(); + } + + void + max_load_factor(float z) + { + Hashtable* This = static_cast<Hashtable*>(this); + This->rehash_policy(prime_rehash_policy(z)); + } + }; + + // Class template hash_code_base. Encapsulates two policy issues that + // aren't quite orthogonal. + // (1) the difference between using a ranged hash function and using + // the combination of a hash function and a range-hashing function. + // In the former case we don't have such things as hash codes, so + // we have a dummy type as placeholder. + // (2) Whether or not we cache hash codes. Caching hash codes is + // meaningless if we have a ranged hash function. + // We also put the key extraction and equality comparison function + // objects here, for convenience. + + // Primary template: unused except as a hook for specializations. + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2, typename H, + bool cache_hash_code> + struct hash_code_base; + + // Specialization: ranged hash function, no caching hash codes. H1 + // and H2 are provided but ignored. We define a dummy hash code type. + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2, typename H> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false> + { + protected: + hash_code_base(const ExtractKey& ex, const Equal& eq, + const H1&, const H2&, const H& h) + : m_extract(ex), m_eq(eq), m_ranged_hash(h) { } + + typedef void* hash_code_t; + + hash_code_t + m_hash_code(const Key& k) const + { return 0; } + + std::size_t + bucket_index(const Key& k, hash_code_t, std::size_t N) const + { return m_ranged_hash(k, N); } + + std::size_t + bucket_index(const hash_node<Value, false>* p, std::size_t N) const + { return m_ranged_hash(m_extract(p->m_v), N); } + + bool + compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const + { return m_eq(k, m_extract(n->m_v)); } + + void + store_code(hash_node<Value, false>*, hash_code_t) const + { } + + void + copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const + { } + + void + m_swap(hash_code_base& x) + { + std::swap(m_extract, x.m_extract); + std::swap(m_eq, x.m_eq); + std::swap(m_ranged_hash, x.m_ranged_hash); + } + + protected: + ExtractKey m_extract; + Equal m_eq; + H m_ranged_hash; + }; + + + // No specialization for ranged hash function while caching hash codes. + // That combination is meaningless, and trying to do it is an error. + + + // Specialization: ranged hash function, cache hash codes. This + // combination is meaningless, so we provide only a declaration + // and no definition. + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2, typename H> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>; + + + // Specialization: hash function and range-hashing function, no + // caching of hash codes. H is provided but ignored. Provides + // typedef and accessor required by TR1. + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, + default_ranged_hash, false> + { + typedef H1 hasher; + + hasher + hash_function() const + { return m_h1; } + + protected: + hash_code_base(const ExtractKey& ex, const Equal& eq, + const H1& h1, const H2& h2, const default_ranged_hash&) + : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } + + typedef std::size_t hash_code_t; + + hash_code_t + m_hash_code(const Key& k) const + { return m_h1(k); } + + std::size_t + bucket_index(const Key&, hash_code_t c, std::size_t N) const + { return m_h2(c, N); } + + std::size_t + bucket_index(const hash_node<Value, false>* p, std::size_t N) const + { return m_h2(m_h1(m_extract(p->m_v)), N); } + + bool + compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const + { return m_eq(k, m_extract(n->m_v)); } + + void + store_code(hash_node<Value, false>*, hash_code_t) const + { } + + void + copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const + { } + + void + m_swap(hash_code_base& x) + { + std::swap(m_extract, x.m_extract); + std::swap(m_eq, x.m_eq); + std::swap(m_h1, x.m_h1); + std::swap(m_h2, x.m_h2); + } + + protected: + ExtractKey m_extract; + Equal m_eq; + H1 m_h1; + H2 m_h2; + }; + + // Specialization: hash function and range-hashing function, + // caching hash codes. H is provided but ignored. Provides + // typedef and accessor required by TR1. + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, + default_ranged_hash, true> + { + typedef H1 hasher; + + hasher + hash_function() const + { return m_h1; } + + protected: + hash_code_base(const ExtractKey& ex, const Equal& eq, + const H1& h1, const H2& h2, const default_ranged_hash&) + : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } + + typedef std::size_t hash_code_t; + + hash_code_t + m_hash_code(const Key& k) const + { return m_h1(k); } + + std::size_t + bucket_index(const Key&, hash_code_t c, std::size_t N) const + { return m_h2(c, N); } + + std::size_t + bucket_index(const hash_node<Value, true>* p, std::size_t N) const + { return m_h2(p->hash_code, N); } + + bool + compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const + { return c == n->hash_code && m_eq(k, m_extract(n->m_v)); } + + void + store_code(hash_node<Value, true>* n, hash_code_t c) const + { n->hash_code = c; } + + void + copy_code(hash_node<Value, true>* to, + const hash_node<Value, true>* from) const + { to->hash_code = from->hash_code; } + + void + m_swap(hash_code_base& x) + { + std::swap(m_extract, x.m_extract); + std::swap(m_eq, x.m_eq); + std::swap(m_h1, x.m_h1); + std::swap(m_h2, x.m_h2); + } + + protected: + ExtractKey m_extract; + Equal m_eq; + H1 m_h1; + H2 m_h2; + }; +} // namespace detail +_GLIBCXX_END_NAMESPACE +} // namespace std::tr1 + +#endif // _TR1_HASHTABLE_POLICY_H + diff --git a/libstdc++-v3/include/tr1/random b/libstdc++-v3/include/tr1/random index 01ada8b..92a71af 100644 --- a/libstdc++-v3/include/tr1/random +++ b/libstdc++-v3/include/tr1/random @@ -61,7 +61,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) /* * Implementation-space details. */ - namespace _Private + namespace { // Type selectors -- are these already implemented elsewhere? template<bool, typename _TpTrue, typename _TpFalse> @@ -76,6 +76,16 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) typedef _TpFalse _Type; }; + template<typename _UIntType, int __w, bool = + __w < std::numeric_limits<_UIntType>::digits> + struct _Shift + { static const _UIntType __value = 0; }; + + template<typename _UIntType, int __w> + struct _Shift<_UIntType, __w, true> + { static const _UIntType __value = _UIntType(1) << __w; }; + } // anonymous namespace + /* * An adaptor class for converting the output of any Generator into * the input for a specific Distribution. @@ -124,17 +134,6 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) return __return_value; } - template<typename _UIntType, int __w, bool = - __w < std::numeric_limits<_UIntType>::digits> - struct _Shift - { static const _UIntType __value = 0; }; - - template<typename _UIntType, int __w> - struct _Shift<_UIntType, __w, true> - { static const _UIntType __value = _UIntType(1) << __w; }; - - } // namespace std::tr1::_Private - /** * Produces random numbers on a given disribution function using a un uniform @@ -152,7 +151,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) public: typedef _Engine engine_type; - typedef _Private::_Adaptor<_Engine, _Dist> engine_value_type; + typedef _Adaptor<_Engine, _Dist> engine_value_type; typedef _Dist distribution_type; typedef typename _Dist::result_type result_type; @@ -364,8 +363,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) operator()(); /** - * Compares two linear congruential random number generator objects of the - * same type for equality. + * Compares two linear congruential random number generator + * objects of the same type for equality. * * @param __lhs A linear congruential random number generator object. * @param __rhs Another linear congruential random number generator obj. @@ -378,8 +377,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) { return __lhs._M_x == __rhs._M_x; } /** - * Compares two linear congruential random number generator objects of the - * same type for inequality. + * Compares two linear congruential random number generator + * objects of the same type for inequality. * * @param __lhs A linear congruential random number generator object. * @param __rhs Another linear congruential random number generator obj. @@ -553,7 +552,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) result_type max() const - { return _Private::_Shift<_UIntType, __w>::__value - 1; } + { return _Shift<_UIntType, __w>::__value - 1; } result_type operator()(); @@ -1116,8 +1115,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) public: /** The type of the generated random value. */ - typedef typename _Private::_Select< - (sizeof(_Result_type1) > sizeof(_Result_type2)), + typedef typename _Select<(sizeof(_Result_type1) > sizeof(_Result_type2)), _Result_type1, _Result_type2>::_Type result_type; // parameter values diff --git a/libstdc++-v3/include/tr1/random.tcc b/libstdc++-v3/include/tr1/random.tcc index a3c263d..5ce415b 100644 --- a/libstdc++-v3/include/tr1/random.tcc +++ b/libstdc++-v3/include/tr1/random.tcc @@ -34,7 +34,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) /* * Implementation-space details. */ - namespace _Private + namespace { // General case for x = (ax + c) mod m -- use Schrage's algorithm to avoid // integer overflow. @@ -124,7 +124,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) { typedef unsigned long long _Type; }; #endif - } // namespace _Private + } // anonymous namespace /** @@ -136,11 +136,11 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) linear_congruential<_UIntType, __a, __c, __m>:: seed(unsigned long __x0) { - if ((_Private::__mod<_UIntType, 1, 0, __m>(__c) == 0) - && (_Private::__mod<_UIntType, 1, 0, __m>(__x0) == 0)) - _M_x = _Private::__mod<_UIntType, 1, 0, __m>(1); + if ((__mod<_UIntType, 1, 0, __m>(__c) == 0) + && (__mod<_UIntType, 1, 0, __m>(__x0) == 0)) + _M_x = __mod<_UIntType, 1, 0, __m>(1); else - _M_x = _Private::__mod<_UIntType, 1, 0, __m>(__x0); + _M_x = __mod<_UIntType, 1, 0, __m>(__x0); } /** @@ -153,11 +153,11 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) seed(_Gen& __g, false_type) { _UIntType __x0 = __g(); - if ((_Private::__mod<_UIntType, 1, 0, __m>(__c) == 0) - && (_Private::__mod<_UIntType, 1, 0, __m>(__x0) == 0)) - _M_x = _Private::__mod<_UIntType, 1, 0, __m>(1); + if ((__mod<_UIntType, 1, 0, __m>(__c) == 0) + && (__mod<_UIntType, 1, 0, __m>(__x0) == 0)) + _M_x = __mod<_UIntType, 1, 0, __m>(1); else - _M_x = _Private::__mod<_UIntType, 1, 0, __m>(__x0); + _M_x = __mod<_UIntType, 1, 0, __m>(__x0); } /** @@ -172,7 +172,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) typename linear_congruential<_UIntType, __a, __c, __m>::result_type linear_congruential<_UIntType, __a, __c, __m>:: min() const - { return (_Private::__mod<_UIntType, 1, 0, __m>(__c) == 0) ? 1 : 0; } + { return (__mod<_UIntType, 1, 0, __m>(__c) == 0) ? 1 : 0; } /** * Gets the maximum possible value of the generated range. @@ -193,7 +193,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) linear_congruential<_UIntType, __a, __c, __m>:: operator()() { - _M_x = _Private::__mod<_UIntType, __a, __c, __m>(_M_x); + _M_x = __mod<_UIntType, __a, __c, __m>(_M_x); return _M_x; } @@ -240,8 +240,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) __b, __t, __c, __l>:: seed(unsigned long __value) { - _M_x[0] = _Private::__mod<_UIntType, 1, 0, - _Private::_Shift<_UIntType, __w>::__value>(__value); + _M_x[0] = __mod<_UIntType, 1, 0, + _Shift<_UIntType, __w>::__value>(__value); for (int __i = 1; __i < state_size; ++__i) { @@ -249,8 +249,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) __x ^= __x >> (__w - 2); __x *= 1812433253ul; __x += __i; - _M_x[__i] = _Private::__mod<_UIntType, 1, 0, - _Private::_Shift<_UIntType, __w>::__value>(__x); + _M_x[__i] = __mod<_UIntType, 1, 0, + _Shift<_UIntType, __w>::__value>(__x); } _M_p = state_size; } @@ -265,8 +265,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) seed(_Gen& __gen, false_type) { for (int __i = 0; __i < state_size; ++__i) - _M_x[__i] = _Private::__mod<_UIntType, 1, 0, - _Private::_Shift<_UIntType, __w>::__value>(__gen()); + _M_x[__i] = __mod<_UIntType, 1, 0, + _Shift<_UIntType, __w>::__value>(__gen()); _M_p = state_size; } @@ -376,7 +376,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) __lcg(__value); for (int __i = 0; __i < long_lag; ++__i) - _M_x[__i] = _Private::__mod<_IntType, 1, 0, modulus>(__lcg()); + _M_x[__i] = __mod<_IntType, 1, 0, modulus>(__lcg()); _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0; _M_p = 0; @@ -390,10 +390,10 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) { const int __n = (std::numeric_limits<_IntType>::digits + 31) / 32; - typedef typename _Private::_Select<(sizeof(unsigned) == 4), + typedef typename _Select<(sizeof(unsigned) == 4), unsigned, unsigned long>::_Type _UInt32Type; - typedef typename _Private::_To_Unsigned_Type<_IntType>::_Type + typedef typename _To_Unsigned_Type<_IntType>::_Type _UIntType; for (int __i = 0; __i < long_lag; ++__i) @@ -402,11 +402,11 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) _UIntType __factor = 1; for (int __j = 0; __j < __n; ++__j) { - __tmp += (_Private::__mod<_UInt32Type, 1, 0, 0>(__gen()) + __tmp += (__mod<_UInt32Type, 1, 0, 0>(__gen()) * __factor); - __factor *= _Private::_Shift<_UIntType, 32>::__value; + __factor *= _Shift<_UIntType, 32>::__value; } - _M_x[__i] = _Private::__mod<_UIntType, 1, 0, modulus>(__tmp); + _M_x[__i] = __mod<_UIntType, 1, 0, modulus>(__tmp); } _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0; _M_p = 0; @@ -622,7 +622,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const std::streamsize __precision = __os.precision(); __os.flags(std::ios_base::scientific | std::ios_base::left); __os.fill(__os.widen(' ')); - __os.precision(_Private::_Max_digits10<double>::__value); + __os.precision(_Max_digits10<double>::__value); __os << __x.p(); @@ -644,7 +644,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const std::streamsize __precision = __os.precision(); __os.flags(std::ios_base::scientific | std::ios_base::left); __os.fill(__os.widen(' ')); - __os.precision(_Private::_Max_digits10<_RealType>::__value); + __os.precision(_Max_digits10<_RealType>::__value); __os << __x.p(); @@ -666,7 +666,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const _CharT __space = __os.widen(' '); __os.flags(std::ios_base::scientific | std::ios_base::left); __os.fill(__space); - __os.precision(_Private::_Max_digits10<_RealType>::__value); + __os.precision(_Max_digits10<_RealType>::__value); __os << __x.min() << __space << __x.max(); @@ -701,7 +701,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const std::streamsize __precision = __os.precision(); __os.flags(std::ios_base::scientific | std::ios_base::left); __os.fill(__os.widen(' ')); - __os.precision(_Private::_Max_digits10<_RealType>::__value); + __os.precision(_Max_digits10<_RealType>::__value); __os << __x.lambda(); @@ -764,7 +764,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const _CharT __space = __os.widen(' '); __os.flags(std::ios_base::scientific | std::ios_base::left); __os.fill(__space); - __os.precision(_Private::_Max_digits10<_RealType>::__value); + __os.precision(_Max_digits10<_RealType>::__value); __os << __x.mean() << __space << __x.sigma() << __space @@ -872,7 +872,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const std::streamsize __precision = __os.precision(); __os.flags(std::ios_base::scientific | std::ios_base::left); __os.fill(__os.widen(' ')); - __os.precision(_Private::_Max_digits10<_RealType>::__value); + __os.precision(_Max_digits10<_RealType>::__value); __os << __x.alpha(); diff --git a/libstdc++-v3/include/tr1/unordered_map b/libstdc++-v3/include/tr1/unordered_map index 207ddbf..6754941 100644 --- a/libstdc++-v3/include/tr1/unordered_map +++ b/libstdc++-v3/include/tr1/unordered_map @@ -43,29 +43,26 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // XXX When we get typedef templates these class definitions // will be unnecessary. - template<class Key, class T, class Hash = hash<Key>, class Pred = std::equal_to<Key>, class Alloc = std::allocator<std::pair<const Key, T> >, bool cache_hash_code = false> class unordered_map - : public hashtable <Key, std::pair<const Key, T>, - Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, false, true> + : public hashtable<Key, std::pair<const Key, T>, Alloc, + detail::extract1st<std::pair<const Key, T> >, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, + cache_hash_code, false, true> { - typedef hashtable <Key, std::pair<const Key, T>, - Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, false, true> - Base; + typedef hashtable<Key, std::pair<const Key, T>, Alloc, + detail::extract1st<std::pair<const Key, T> >, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, + cache_hash_code, false, true> + Base; public: typedef typename Base::size_type size_type; @@ -78,9 +75,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base(n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), a) + : Base(n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), + eql, detail::extract1st<std::pair<const Key, T> >(), a) { } template<typename InputIterator> @@ -89,9 +86,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (f, l, n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), a) + : Base (f, l, n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), + eql, detail::extract1st<std::pair<const Key, T> >(), a) { } }; @@ -103,18 +100,18 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) class unordered_multimap : public hashtable <Key, std::pair<const Key, T>, Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, + detail::extract1st<std::pair<const Key, T> >, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, cache_hash_code, false, false> { typedef hashtable <Key, std::pair<const Key, T>, Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, + detail::extract1st<std::pair<const Key, T> >, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, cache_hash_code, false, false> Base; @@ -129,9 +126,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), a) + : Base (n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), + eql, detail::extract1st<std::pair<const Key, T> >(), a) { } @@ -141,9 +138,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (f, l, n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), a) + : Base (f, l, n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), + eql, detail::extract1st<std::pair<const Key, T> >(), a) { } }; diff --git a/libstdc++-v3/include/tr1/unordered_set b/libstdc++-v3/include/tr1/unordered_set index 1e35c79..f3c7227 100644 --- a/libstdc++-v3/include/tr1/unordered_set +++ b/libstdc++-v3/include/tr1/unordered_set @@ -43,7 +43,6 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // XXX When we get typedef templates these class definitions // will be unnecessary. - template<class Value, class Hash = hash<Value>, class Pred = std::equal_to<Value>, @@ -51,17 +50,17 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) bool cache_hash_code = false> class unordered_set : public hashtable<Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, + detail::identity<Value>, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, cache_hash_code, true, true> { typedef hashtable<Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, + detail::identity<Value>, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, cache_hash_code, true, true> Base; @@ -76,9 +75,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), - eql, Internal::identity<Value>(), a) + : Base(n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), + eql, detail::identity<Value>(), a) { } template<typename InputIterator> @@ -87,9 +86,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (f, l, n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), - eql, Internal::identity<Value>(), a) + : Base(f, l, n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), + eql, detail::identity<Value>(), a) { } }; @@ -100,17 +99,17 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) bool cache_hash_code = false> class unordered_multiset : public hashtable <Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, + detail::identity<Value>, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, cache_hash_code, true, false> { typedef hashtable<Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, - Internal::default_ranged_hash, - Internal::prime_rehash_policy, + detail::identity<Value>, Pred, + Hash, detail::mod_range_hashing, + detail::default_ranged_hash, + detail::prime_rehash_policy, cache_hash_code, true, false> Base; @@ -125,9 +124,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), - eql, Internal::identity<Value>(), a) + : Base(n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), + eql, detail::identity<Value>(), a) { } @@ -137,9 +136,9 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (f, l, n, hf, Internal::mod_range_hashing(), - Internal::default_ranged_hash(), eql, - Internal::identity<Value>(), a) + : Base(f, l, n, hf, detail::mod_range_hashing(), + detail::default_ranged_hash(), eql, + detail::identity<Value>(), a) { } }; diff --git a/libstdc++-v3/src/Makefile.am b/libstdc++-v3/src/Makefile.am index d54b71e..47f8cee 100644 --- a/libstdc++-v3/src/Makefile.am +++ b/libstdc++-v3/src/Makefile.am @@ -138,7 +138,6 @@ sources = \ debug.cc \ debug_list.cc \ functexcept.cc \ - globals_locale.cc \ globals_io.cc \ ios.cc \ ios_failure.cc \ diff --git a/libstdc++-v3/src/Makefile.in b/libstdc++-v3/src/Makefile.in index 46e41b5..34b86e3 100644 --- a/libstdc++-v3/src/Makefile.in +++ b/libstdc++-v3/src/Makefile.in @@ -62,19 +62,19 @@ toolexeclibLTLIBRARIES_INSTALL = $(INSTALL) LTLIBRARIES = $(toolexeclib_LTLIBRARIES) am__libstdc___la_SOURCES_DIST = bitmap_allocator.cc pool_allocator.cc \ mt_allocator.cc codecvt.cc compatibility.cc complex_io.cc \ - ctype.cc debug.cc debug_list.cc functexcept.cc \ - globals_locale.cc globals_io.cc ios.cc ios_failure.cc \ - ios_init.cc ios_locale.cc limits.cc list.cc locale.cc \ - locale_init.cc locale_facets.cc localename.cc stdexcept.cc \ - strstream.cc tree.cc allocator-inst.cc concept-inst.cc \ - fstream-inst.cc ext-inst.cc ios-inst.cc iostream-inst.cc \ - istream-inst.cc istream.cc locale-inst.cc misc-inst.cc \ - ostream-inst.cc sstream-inst.cc streambuf-inst.cc streambuf.cc \ - string-inst.cc valarray-inst.cc wlocale-inst.cc \ - wstring-inst.cc atomicity.cc codecvt_members.cc \ - collate_members.cc ctype_members.cc messages_members.cc \ - monetary_members.cc numeric_members.cc time_members.cc \ - basic_file.cc c++locale.cc compatibility-ldbl.cc + ctype.cc debug.cc debug_list.cc functexcept.cc globals_io.cc \ + ios.cc ios_failure.cc ios_init.cc ios_locale.cc limits.cc \ + list.cc locale.cc locale_init.cc locale_facets.cc \ + localename.cc stdexcept.cc strstream.cc tree.cc \ + allocator-inst.cc concept-inst.cc fstream-inst.cc ext-inst.cc \ + ios-inst.cc iostream-inst.cc istream-inst.cc istream.cc \ + locale-inst.cc misc-inst.cc ostream-inst.cc sstream-inst.cc \ + streambuf-inst.cc streambuf.cc string-inst.cc valarray-inst.cc \ + wlocale-inst.cc wstring-inst.cc atomicity.cc \ + codecvt_members.cc collate_members.cc ctype_members.cc \ + messages_members.cc monetary_members.cc numeric_members.cc \ + time_members.cc basic_file.cc c++locale.cc \ + compatibility-ldbl.cc am__objects_1 = atomicity.lo codecvt_members.lo collate_members.lo \ ctype_members.lo messages_members.lo monetary_members.lo \ numeric_members.lo time_members.lo @@ -82,16 +82,16 @@ am__objects_2 = basic_file.lo c++locale.lo @GLIBCXX_LDBL_COMPAT_TRUE@am__objects_3 = compatibility-ldbl.lo am__objects_4 = bitmap_allocator.lo pool_allocator.lo mt_allocator.lo \ codecvt.lo compatibility.lo complex_io.lo ctype.lo debug.lo \ - debug_list.lo functexcept.lo globals_locale.lo globals_io.lo \ - ios.lo ios_failure.lo ios_init.lo ios_locale.lo limits.lo \ - list.lo locale.lo locale_init.lo locale_facets.lo \ - localename.lo stdexcept.lo strstream.lo tree.lo \ - allocator-inst.lo concept-inst.lo fstream-inst.lo ext-inst.lo \ - ios-inst.lo iostream-inst.lo istream-inst.lo istream.lo \ - locale-inst.lo misc-inst.lo ostream-inst.lo sstream-inst.lo \ - streambuf-inst.lo streambuf.lo string-inst.lo valarray-inst.lo \ - wlocale-inst.lo wstring-inst.lo $(am__objects_1) \ - $(am__objects_2) $(am__objects_3) + debug_list.lo functexcept.lo globals_io.lo ios.lo \ + ios_failure.lo ios_init.lo ios_locale.lo limits.lo list.lo \ + locale.lo locale_init.lo locale_facets.lo localename.lo \ + stdexcept.lo strstream.lo tree.lo allocator-inst.lo \ + concept-inst.lo fstream-inst.lo ext-inst.lo ios-inst.lo \ + iostream-inst.lo istream-inst.lo istream.lo locale-inst.lo \ + misc-inst.lo ostream-inst.lo sstream-inst.lo streambuf-inst.lo \ + streambuf.lo string-inst.lo valarray-inst.lo wlocale-inst.lo \ + wstring-inst.lo $(am__objects_1) $(am__objects_2) \ + $(am__objects_3) am_libstdc___la_OBJECTS = $(am__objects_4) libstdc___la_OBJECTS = $(am_libstdc___la_OBJECTS) DEFAULT_INCLUDES = -I. -I$(srcdir) -I$(top_builddir) @@ -344,7 +344,6 @@ sources = \ debug.cc \ debug_list.cc \ functexcept.cc \ - globals_locale.cc \ globals_io.cc \ ios.cc \ ios_failure.cc \ diff --git a/libstdc++-v3/src/debug.cc b/libstdc++-v3/src/debug.cc index 8becf33..9484556 100644 --- a/libstdc++-v3/src/debug.cc +++ b/libstdc++-v3/src/debug.cc @@ -39,10 +39,10 @@ using namespace std; -namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) +namespace { static __glibcxx_mutex_define_initialized(iterator_base_mutex); -} // namespace __gnu_internal +} namespace __gnu_debug { @@ -192,7 +192,7 @@ namespace __gnu_debug // Attach to the new sequence (if there is one) if (__seq) { - __gnu_cxx::lock sentry(__gnu_internal::iterator_base_mutex); + __gnu_cxx::lock sentry(iterator_base_mutex); _M_sequence = __seq; _M_version = _M_sequence->_M_version; _M_prior = 0; @@ -217,7 +217,7 @@ namespace __gnu_debug _Safe_iterator_base:: _M_detach() { - __gnu_cxx::lock sentry(__gnu_internal::iterator_base_mutex); + __gnu_cxx::lock sentry(iterator_base_mutex); if (_M_sequence) { // Remove us from this sequence's list diff --git a/libstdc++-v3/src/ext-inst.cc b/libstdc++-v3/src/ext-inst.cc index 35f0b16..1e356d6 100644 --- a/libstdc++-v3/src/ext-inst.cc +++ b/libstdc++-v3/src/ext-inst.cc @@ -34,15 +34,13 @@ #include <ext/rope> #include <ext/stdio_filebuf.h> -namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) +namespace { - const int min_len = __gnu_cxx::_Rope_constants::_S_max_rope_depth + 1; + const int min_len = _S_max_rope_depth + 1; } _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) - using namespace __gnu_internal; - template const unsigned long rope<char, std::allocator<char> >::_S_min_len[min_len]; diff --git a/libstdc++-v3/src/globals_locale.cc b/libstdc++-v3/src/globals_locale.cc deleted file mode 100644 index 56420ef..0000000 --- a/libstdc++-v3/src/globals_locale.cc +++ /dev/null @@ -1,210 +0,0 @@ -// Copyright (C) 2001, 2002, 2003, 2004, 2006 Free Software Foundation, Inc. -// -// This file is part of the GNU ISO C++ Library. This library is free -// software; you can redistribute it and/or modify it under the -// terms of the GNU General Public License as published by the -// Free Software Foundation; either version 2, or (at your option) -// any later version. - -// This library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU General Public License for more details. - -// You should have received a copy of the GNU General Public License along -// with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, -// USA. - -// As a special exception, you may use this file as part of a free software -// library without restriction. Specifically, if other files instantiate -// templates or use macros or inline functions from this file, or you compile -// this file and link it with other files to produce an executable, this -// file does not by itself cause the resulting executable to be covered by -// the GNU General Public License. This exception does not however -// invalidate any other reasons why the executable file might be covered by -// the GNU General Public License. - -#include <locale> - -// On AIX, and perhaps other systems, library initialization order is -// not guaranteed. For example, the static initializers for the main -// program might run before the static initializers for this library. -// That means that we cannot rely on static initialization in the -// library; there is no guarantee that things will get initialized in -// time. This file contains definitions of all global variables that -// require initialization as arrays of characters. - -// NB: asm directives can rename these non-exported, namespace -// __gnu_cxx symbols into exported, namespace std symbols with the -// appropriate symbol version name. -// The rename syntax is -// asm (".symver currentname,oldname@@GLIBCXX_3.2") -// In macro form: -// _GLIBCXX_ASM_SYMVER(currentname, oldname, GLIBCXX_3.2) - -namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) -{ - using namespace std; - - typedef char fake_locale_Impl[sizeof(locale::_Impl)] - __attribute__ ((aligned(__alignof__(locale::_Impl)))); - fake_locale_Impl c_locale_impl; - - typedef char fake_locale[sizeof(locale)] - __attribute__ ((aligned(__alignof__(locale)))); - fake_locale c_locale; - - typedef char fake_name_vec[sizeof(char*)] - __attribute__ ((aligned(__alignof__(char*)))); - fake_name_vec name_vec[6 + _GLIBCXX_NUM_CATEGORIES]; - - typedef char fake_names[sizeof(char[2])] - __attribute__ ((aligned(__alignof__(char[2])))); - fake_names name_c[6 + _GLIBCXX_NUM_CATEGORIES]; - - typedef char fake_facet_vec[sizeof(locale::facet*)] - __attribute__ ((aligned(__alignof__(locale::facet*)))); - fake_facet_vec facet_vec[_GLIBCXX_NUM_FACETS]; - - typedef char fake_cache_vec[sizeof(locale::facet*)] - __attribute__ ((aligned(__alignof__(locale::facet*)))); - fake_cache_vec cache_vec[_GLIBCXX_NUM_FACETS]; - - typedef char fake_ctype_c[sizeof(std::ctype<char>)] - __attribute__ ((aligned(__alignof__(std::ctype<char>)))); - fake_ctype_c ctype_c; - - typedef char fake_collate_c[sizeof(std::collate<char>)] - __attribute__ ((aligned(__alignof__(std::collate<char>)))); - fake_collate_c collate_c; - - typedef char fake_numpunct_c[sizeof(numpunct<char>)] - __attribute__ ((aligned(__alignof__(numpunct<char>)))); - fake_numpunct_c numpunct_c; - - typedef char fake_num_get_c[sizeof(num_get<char>)] - __attribute__ ((aligned(__alignof__(num_get<char>)))); - fake_num_get_c num_get_c; - - typedef char fake_num_put_c[sizeof(num_put<char>)] - __attribute__ ((aligned(__alignof__(num_put<char>)))); - fake_num_put_c num_put_c; - - typedef char fake_codecvt_c[sizeof(codecvt<char, char, mbstate_t>)] - __attribute__ ((aligned(__alignof__(codecvt<char, char, mbstate_t>)))); - fake_codecvt_c codecvt_c; - - typedef char fake_moneypunct_c[sizeof(moneypunct<char, true>)] - __attribute__ ((aligned(__alignof__(moneypunct<char, true>)))); - fake_moneypunct_c moneypunct_ct; - fake_moneypunct_c moneypunct_cf; - - typedef char fake_money_get_c[sizeof(money_get<char>)] - __attribute__ ((aligned(__alignof__(money_get<char>)))); - fake_money_get_c money_get_c; - - typedef char fake_money_put_c[sizeof(money_put<char>)] - __attribute__ ((aligned(__alignof__(money_put<char>)))); - fake_money_put_c money_put_c; - - typedef char fake_timepunct_c[sizeof(__timepunct<char>)] - __attribute__ ((aligned(__alignof__(__timepunct<char>)))); - fake_timepunct_c timepunct_c; - - typedef char fake_time_get_c[sizeof(time_get<char>)] - __attribute__ ((aligned(__alignof__(time_get<char>)))); - fake_time_get_c time_get_c; - - typedef char fake_time_put_c[sizeof(time_put<char>)] - __attribute__ ((aligned(__alignof__(time_put<char>)))); - fake_time_put_c time_put_c; - - typedef char fake_messages_c[sizeof(messages<char>)] - __attribute__ ((aligned(__alignof__(messages<char>)))); - fake_messages_c messages_c; - -#ifdef _GLIBCXX_USE_WCHAR_T - typedef char fake_wtype_w[sizeof(std::ctype<wchar_t>)] - __attribute__ ((aligned(__alignof__(std::ctype<wchar_t>)))); - fake_wtype_w ctype_w; - - typedef char fake_wollate_w[sizeof(std::collate<wchar_t>)] - __attribute__ ((aligned(__alignof__(std::collate<wchar_t>)))); - fake_wollate_w collate_w; - - typedef char fake_numpunct_w[sizeof(numpunct<wchar_t>)] - __attribute__ ((aligned(__alignof__(numpunct<wchar_t>)))); - fake_numpunct_w numpunct_w; - - typedef char fake_num_get_w[sizeof(num_get<wchar_t>)] - __attribute__ ((aligned(__alignof__(num_get<wchar_t>)))); - fake_num_get_w num_get_w; - - typedef char fake_num_put_w[sizeof(num_put<wchar_t>)] - __attribute__ ((aligned(__alignof__(num_put<wchar_t>)))); - fake_num_put_w num_put_w; - - typedef char fake_wodecvt_w[sizeof(codecvt<wchar_t, char, mbstate_t>)] - __attribute__ ((aligned(__alignof__(codecvt<wchar_t, char, mbstate_t>)))); - fake_wodecvt_w codecvt_w; - - typedef char fake_moneypunct_w[sizeof(moneypunct<wchar_t, true>)] - __attribute__ ((aligned(__alignof__(moneypunct<wchar_t, true>)))); - fake_moneypunct_w moneypunct_wt; - fake_moneypunct_w moneypunct_wf; - - typedef char fake_money_get_w[sizeof(money_get<wchar_t>)] - __attribute__ ((aligned(__alignof__(money_get<wchar_t>)))); - fake_money_get_w money_get_w; - - typedef char fake_money_put_w[sizeof(money_put<wchar_t>)] - __attribute__ ((aligned(__alignof__(money_put<wchar_t>)))); - fake_money_put_w money_put_w; - - typedef char fake_timepunct_w[sizeof(__timepunct<wchar_t>)] - __attribute__ ((aligned(__alignof__(__timepunct<wchar_t>)))); - fake_timepunct_w timepunct_w; - - typedef char fake_time_get_w[sizeof(time_get<wchar_t>)] - __attribute__ ((aligned(__alignof__(time_get<wchar_t>)))); - fake_time_get_w time_get_w; - - typedef char fake_time_put_w[sizeof(time_put<wchar_t>)] - __attribute__ ((aligned(__alignof__(time_put<wchar_t>)))); - fake_time_put_w time_put_w; - - typedef char fake_messages_w[sizeof(messages<wchar_t>)] - __attribute__ ((aligned(__alignof__(messages<wchar_t>)))); - fake_messages_w messages_w; -#endif - - // Storage for "C" locale caches. - typedef char fake_num_cache_c[sizeof(std::__numpunct_cache<char>)] - __attribute__ ((aligned(__alignof__(std::__numpunct_cache<char>)))); - fake_num_cache_c numpunct_cache_c; - - typedef char fake_money_cache_c[sizeof(std::__moneypunct_cache<char, true>)] - __attribute__ ((aligned(__alignof__(std::__moneypunct_cache<char, true>)))); - fake_money_cache_c moneypunct_cache_ct; - fake_money_cache_c moneypunct_cache_cf; - - typedef char fake_time_cache_c[sizeof(std::__timepunct_cache<char>)] - __attribute__ ((aligned(__alignof__(std::__timepunct_cache<char>)))); - fake_time_cache_c timepunct_cache_c; - -#ifdef _GLIBCXX_USE_WCHAR_T - typedef char fake_num_cache_w[sizeof(std::__numpunct_cache<wchar_t>)] - __attribute__ ((aligned(__alignof__(std::__numpunct_cache<wchar_t>)))); - fake_num_cache_w numpunct_cache_w; - - typedef char fake_money_cache_w[sizeof(std::__moneypunct_cache<wchar_t,true>)] - __attribute__ ((aligned(__alignof__(std::__moneypunct_cache<wchar_t,true>)))); - fake_money_cache_w moneypunct_cache_wt; - fake_money_cache_w moneypunct_cache_wf; - - typedef char fake_time_cache_w[sizeof(std::__timepunct_cache<wchar_t>)] - __attribute__ ((aligned(__alignof__(std::__timepunct_cache<wchar_t>)))); - fake_time_cache_w timepunct_cache_w; -#endif -} // namespace __gnu_internal diff --git a/libstdc++-v3/src/locale.cc b/libstdc++-v3/src/locale.cc index 93f5bc0..7bcf51d 100644 --- a/libstdc++-v3/src/locale.cc +++ b/libstdc++-v3/src/locale.cc @@ -35,9 +35,9 @@ #include <bits/atomicity.h> #include <bits/concurrence.h> -namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) +namespace { - // Mutex object for cache access + // Mutex object for cache access. static __glibcxx_mutex_define_initialized(locale_cache_mutex); } @@ -391,7 +391,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) locale::_Impl:: _M_install_cache(const facet* __cache, size_t __index) { - __gnu_cxx::lock sentry(__gnu_internal::locale_cache_mutex); + __gnu_cxx::lock sentry(locale_cache_mutex); if (_M_caches[__index] != 0) { // Some other thread got in first. diff --git a/libstdc++-v3/src/locale_init.cc b/libstdc++-v3/src/locale_init.cc index 6d6493e..3a4b6d1 100644 --- a/libstdc++-v3/src/locale_init.cc +++ b/libstdc++-v3/src/locale_init.cc @@ -35,72 +35,181 @@ #include <bits/atomicity.h> #include <bits/concurrence.h> -namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) +namespace { - // Defined in globals.cc. - extern std::locale c_locale; - extern std::locale::_Impl c_locale_impl; - - extern std::locale::facet* facet_vec[_GLIBCXX_NUM_FACETS]; - extern char* name_vec[6 + _GLIBCXX_NUM_CATEGORIES]; - extern char name_c[6 + _GLIBCXX_NUM_CATEGORIES][2]; - - extern std::ctype<char> ctype_c; - extern std::collate<char> collate_c; - extern std::numpunct<char> numpunct_c; - extern std::num_get<char> num_get_c; - extern std::num_put<char> num_put_c; - extern std::codecvt<char, char, mbstate_t> codecvt_c; - extern std::moneypunct<char, false> moneypunct_cf; - extern std::moneypunct<char, true> moneypunct_ct; - extern std::money_get<char> money_get_c; - extern std::money_put<char> money_put_c; - extern std::__timepunct<char> timepunct_c; - extern std::time_get<char> time_get_c; - extern std::time_put<char> time_put_c; - extern std::messages<char> messages_c; + using namespace std; + + typedef char fake_locale_Impl[sizeof(locale::_Impl)] + __attribute__ ((aligned(__alignof__(locale::_Impl)))); + fake_locale_Impl c_locale_impl; + + typedef char fake_locale[sizeof(locale)] + __attribute__ ((aligned(__alignof__(locale)))); + fake_locale c_locale; + + typedef char fake_name_vec[sizeof(char*)] + __attribute__ ((aligned(__alignof__(char*)))); + fake_name_vec name_vec[6 + _GLIBCXX_NUM_CATEGORIES]; + + typedef char fake_names[sizeof(char[2])] + __attribute__ ((aligned(__alignof__(char[2])))); + fake_names name_c[6 + _GLIBCXX_NUM_CATEGORIES]; + + typedef char fake_facet_vec[sizeof(locale::facet*)] + __attribute__ ((aligned(__alignof__(locale::facet*)))); + fake_facet_vec facet_vec[_GLIBCXX_NUM_FACETS]; + + typedef char fake_cache_vec[sizeof(locale::facet*)] + __attribute__ ((aligned(__alignof__(locale::facet*)))); + fake_cache_vec cache_vec[_GLIBCXX_NUM_FACETS]; + + typedef char fake_ctype_c[sizeof(std::ctype<char>)] + __attribute__ ((aligned(__alignof__(std::ctype<char>)))); + fake_ctype_c ctype_c; + + typedef char fake_collate_c[sizeof(std::collate<char>)] + __attribute__ ((aligned(__alignof__(std::collate<char>)))); + fake_collate_c collate_c; + + typedef char fake_numpunct_c[sizeof(numpunct<char>)] + __attribute__ ((aligned(__alignof__(numpunct<char>)))); + fake_numpunct_c numpunct_c; + + typedef char fake_num_get_c[sizeof(num_get<char>)] + __attribute__ ((aligned(__alignof__(num_get<char>)))); + fake_num_get_c num_get_c; + + typedef char fake_num_put_c[sizeof(num_put<char>)] + __attribute__ ((aligned(__alignof__(num_put<char>)))); + fake_num_put_c num_put_c; + + typedef char fake_codecvt_c[sizeof(codecvt<char, char, mbstate_t>)] + __attribute__ ((aligned(__alignof__(codecvt<char, char, mbstate_t>)))); + fake_codecvt_c codecvt_c; + + typedef char fake_moneypunct_c[sizeof(moneypunct<char, true>)] + __attribute__ ((aligned(__alignof__(moneypunct<char, true>)))); + fake_moneypunct_c moneypunct_ct; + fake_moneypunct_c moneypunct_cf; + + typedef char fake_money_get_c[sizeof(money_get<char>)] + __attribute__ ((aligned(__alignof__(money_get<char>)))); + fake_money_get_c money_get_c; + + typedef char fake_money_put_c[sizeof(money_put<char>)] + __attribute__ ((aligned(__alignof__(money_put<char>)))); + fake_money_put_c money_put_c; + + typedef char fake_timepunct_c[sizeof(__timepunct<char>)] + __attribute__ ((aligned(__alignof__(__timepunct<char>)))); + fake_timepunct_c timepunct_c; + + typedef char fake_time_get_c[sizeof(time_get<char>)] + __attribute__ ((aligned(__alignof__(time_get<char>)))); + fake_time_get_c time_get_c; + + typedef char fake_time_put_c[sizeof(time_put<char>)] + __attribute__ ((aligned(__alignof__(time_put<char>)))); + fake_time_put_c time_put_c; + + typedef char fake_messages_c[sizeof(messages<char>)] + __attribute__ ((aligned(__alignof__(messages<char>)))); + fake_messages_c messages_c; + #ifdef _GLIBCXX_USE_WCHAR_T - extern std::ctype<wchar_t> ctype_w; - extern std::collate<wchar_t> collate_w; - extern std::numpunct<wchar_t> numpunct_w; - extern std::num_get<wchar_t> num_get_w; - extern std::num_put<wchar_t> num_put_w; - extern std::codecvt<wchar_t, char, mbstate_t> codecvt_w; - extern std::moneypunct<wchar_t, false> moneypunct_wf; - extern std::moneypunct<wchar_t, true> moneypunct_wt; - extern std::money_get<wchar_t> money_get_w; - extern std::money_put<wchar_t> money_put_w; - extern std::__timepunct<wchar_t> timepunct_w; - extern std::time_get<wchar_t> time_get_w; - extern std::time_put<wchar_t> time_put_w; - extern std::messages<wchar_t> messages_w; + typedef char fake_wtype_w[sizeof(std::ctype<wchar_t>)] + __attribute__ ((aligned(__alignof__(std::ctype<wchar_t>)))); + fake_wtype_w ctype_w; + + typedef char fake_wollate_w[sizeof(std::collate<wchar_t>)] + __attribute__ ((aligned(__alignof__(std::collate<wchar_t>)))); + fake_wollate_w collate_w; + + typedef char fake_numpunct_w[sizeof(numpunct<wchar_t>)] + __attribute__ ((aligned(__alignof__(numpunct<wchar_t>)))); + fake_numpunct_w numpunct_w; + + typedef char fake_num_get_w[sizeof(num_get<wchar_t>)] + __attribute__ ((aligned(__alignof__(num_get<wchar_t>)))); + fake_num_get_w num_get_w; + + typedef char fake_num_put_w[sizeof(num_put<wchar_t>)] + __attribute__ ((aligned(__alignof__(num_put<wchar_t>)))); + fake_num_put_w num_put_w; + + typedef char fake_wodecvt_w[sizeof(codecvt<wchar_t, char, mbstate_t>)] + __attribute__ ((aligned(__alignof__(codecvt<wchar_t, char, mbstate_t>)))); + fake_wodecvt_w codecvt_w; + + typedef char fake_moneypunct_w[sizeof(moneypunct<wchar_t, true>)] + __attribute__ ((aligned(__alignof__(moneypunct<wchar_t, true>)))); + fake_moneypunct_w moneypunct_wt; + fake_moneypunct_w moneypunct_wf; + + typedef char fake_money_get_w[sizeof(money_get<wchar_t>)] + __attribute__ ((aligned(__alignof__(money_get<wchar_t>)))); + fake_money_get_w money_get_w; + + typedef char fake_money_put_w[sizeof(money_put<wchar_t>)] + __attribute__ ((aligned(__alignof__(money_put<wchar_t>)))); + fake_money_put_w money_put_w; + + typedef char fake_timepunct_w[sizeof(__timepunct<wchar_t>)] + __attribute__ ((aligned(__alignof__(__timepunct<wchar_t>)))); + fake_timepunct_w timepunct_w; + + typedef char fake_time_get_w[sizeof(time_get<wchar_t>)] + __attribute__ ((aligned(__alignof__(time_get<wchar_t>)))); + fake_time_get_w time_get_w; + + typedef char fake_time_put_w[sizeof(time_put<wchar_t>)] + __attribute__ ((aligned(__alignof__(time_put<wchar_t>)))); + fake_time_put_w time_put_w; + + typedef char fake_messages_w[sizeof(messages<wchar_t>)] + __attribute__ ((aligned(__alignof__(messages<wchar_t>)))); + fake_messages_w messages_w; #endif - // And the caches.... - extern std::locale::facet* cache_vec[_GLIBCXX_NUM_FACETS]; - extern std::__numpunct_cache<char> numpunct_cache_c; - extern std::__moneypunct_cache<char, false> moneypunct_cache_cf; - extern std::__moneypunct_cache<char, true> moneypunct_cache_ct; - extern std::__timepunct_cache<char> timepunct_cache_c; -#ifdef _GLIBCXX_USE_WCHAR_T - extern std::__numpunct_cache<wchar_t> numpunct_cache_w; - extern std::__moneypunct_cache<wchar_t, false> moneypunct_cache_wf; - extern std::__moneypunct_cache<wchar_t, true> moneypunct_cache_wt; - extern std::__timepunct_cache<wchar_t> timepunct_cache_w; + // Storage for "C" locale caches. + typedef char fake_num_cache_c[sizeof(std::__numpunct_cache<char>)] + __attribute__ ((aligned(__alignof__(std::__numpunct_cache<char>)))); + fake_num_cache_c numpunct_cache_c; + + typedef char fake_money_cache_c[sizeof(std::__moneypunct_cache<char, true>)] + __attribute__ ((aligned(__alignof__(std::__moneypunct_cache<char, true>)))); + fake_money_cache_c moneypunct_cache_ct; + fake_money_cache_c moneypunct_cache_cf; + + typedef char fake_time_cache_c[sizeof(std::__timepunct_cache<char>)] + __attribute__ ((aligned(__alignof__(std::__timepunct_cache<char>)))); + fake_time_cache_c timepunct_cache_c; + +#ifdef _GLIBCXX_USE_WCHAR_T + typedef char fake_num_cache_w[sizeof(std::__numpunct_cache<wchar_t>)] + __attribute__ ((aligned(__alignof__(std::__numpunct_cache<wchar_t>)))); + fake_num_cache_w numpunct_cache_w; + + typedef char fake_money_cache_w[sizeof(std::__moneypunct_cache<wchar_t,true>)] + __attribute__ ((aligned(__alignof__(std::__moneypunct_cache<wchar_t,true>)))); + fake_money_cache_w moneypunct_cache_wt; + fake_money_cache_w moneypunct_cache_wf; + + typedef char fake_time_cache_w[sizeof(std::__timepunct_cache<wchar_t>)] + __attribute__ ((aligned(__alignof__(std::__timepunct_cache<wchar_t>)))); + fake_time_cache_w timepunct_cache_w; #endif // Mutex object for locale initialization. static __glibcxx_mutex_define_initialized(locale_mutex); -} // namespace __gnu_internal +} // anonymous namespace _GLIBCXX_BEGIN_NAMESPACE(std) - using namespace __gnu_internal; - locale::locale() throw() : _M_impl(0) { _S_initialize(); - __gnu_cxx::lock sentry(__gnu_internal::locale_mutex); + __gnu_cxx::lock sentry(locale_mutex); _S_global->_M_add_reference(); _M_impl = _S_global; } @@ -111,7 +220,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _S_initialize(); _Impl* __old; { - __gnu_cxx::lock sentry(__gnu_internal::locale_mutex); + __gnu_cxx::lock sentry(locale_mutex); __old = _S_global; __other._M_impl->_M_add_reference(); _S_global = __other._M_impl; @@ -132,7 +241,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) locale::classic() { _S_initialize(); - return c_locale; + return reinterpret_cast<const locale&>(c_locale); } void diff --git a/libstdc++-v3/src/mt_allocator.cc b/libstdc++-v3/src/mt_allocator.cc index fa09ead..191f3a5 100644 --- a/libstdc++-v3/src/mt_allocator.cc +++ b/libstdc++-v3/src/mt_allocator.cc @@ -35,7 +35,7 @@ #include <bits/concurrence.h> #include <ext/mt_allocator.h> -namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) +namespace { #ifdef __GTHREADS struct __freelist @@ -64,17 +64,16 @@ namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) _M_destroy_thread_key(void* __id) { // Return this thread id record to the front of thread_freelist. - __gnu_cxx::lock sentry(__gnu_internal::freelist_mutex); + __gnu_cxx::lock sentry(freelist_mutex); size_t _M_id = reinterpret_cast<size_t>(__id); - using namespace __gnu_internal; typedef __gnu_cxx::__pool<true>::_Thread_record _Thread_record; _Thread_record* __tr = &freelist._M_thread_freelist_array[_M_id - 1]; __tr->_M_next = freelist._M_thread_freelist; freelist._M_thread_freelist = __tr; } #endif -} +} // anonymous namespace _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) @@ -466,10 +465,10 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) if (__gthread_active_p()) { { - __gnu_cxx::lock sentry(__gnu_internal::freelist_mutex); + __gnu_cxx::lock sentry(freelist_mutex); - if (!__gnu_internal::freelist._M_thread_freelist_array - || __gnu_internal::freelist._M_max_threads + if (!freelist._M_thread_freelist_array + || freelist._M_max_threads < _M_options._M_max_threads) { const size_t __k = sizeof(_Thread_record) @@ -492,22 +491,22 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) _M_thread_freelist[__i - 1]._M_next = NULL; _M_thread_freelist[__i - 1]._M_id = __i; - if (!__gnu_internal::freelist._M_thread_freelist_array) + if (!freelist._M_thread_freelist_array) { // Initialize per thread key to hold pointer to // _M_thread_freelist. - __gthread_key_create(&__gnu_internal::freelist._M_key, - __gnu_internal::_M_destroy_thread_key); - __gnu_internal::freelist._M_thread_freelist + __gthread_key_create(&freelist._M_key, + ::_M_destroy_thread_key); + freelist._M_thread_freelist = _M_thread_freelist; } else { _Thread_record* _M_old_freelist - = __gnu_internal::freelist._M_thread_freelist; + = freelist._M_thread_freelist; _Thread_record* _M_old_array - = __gnu_internal::freelist._M_thread_freelist_array; - __gnu_internal::freelist._M_thread_freelist + = freelist._M_thread_freelist_array; + freelist._M_thread_freelist = &_M_thread_freelist[_M_old_freelist - _M_old_array]; while (_M_old_freelist) { @@ -515,16 +514,16 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) if (_M_old_freelist->_M_next) next_id = _M_old_freelist->_M_next - _M_old_array; else - next_id = __gnu_internal::freelist._M_max_threads; + next_id = freelist._M_max_threads; _M_thread_freelist[_M_old_freelist->_M_id - 1]._M_next = &_M_thread_freelist[next_id]; _M_old_freelist = _M_old_freelist->_M_next; } ::operator delete(static_cast<void*>(_M_old_array)); } - __gnu_internal::freelist._M_thread_freelist_array + freelist._M_thread_freelist_array = _M_thread_freelist; - __gnu_internal::freelist._M_max_threads + freelist._M_max_threads = _M_options._M_max_threads; } } @@ -587,21 +586,21 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) // returns it's id. if (__gthread_active_p()) { - void* v = __gthread_getspecific(__gnu_internal::freelist._M_key); + void* v = __gthread_getspecific(freelist._M_key); size_t _M_id = (size_t)v; if (_M_id == 0) { { - __gnu_cxx::lock sentry(__gnu_internal::freelist_mutex); - if (__gnu_internal::freelist._M_thread_freelist) + __gnu_cxx::lock sentry(freelist_mutex); + if (freelist._M_thread_freelist) { - _M_id = __gnu_internal::freelist._M_thread_freelist->_M_id; - __gnu_internal::freelist._M_thread_freelist - = __gnu_internal::freelist._M_thread_freelist->_M_next; + _M_id = freelist._M_thread_freelist->_M_id; + freelist._M_thread_freelist + = freelist._M_thread_freelist->_M_next; } } - __gthread_setspecific(__gnu_internal::freelist._M_key, + __gthread_setspecific(freelist._M_key, (void*)_M_id); } return _M_id >= _M_options._M_max_threads ? 0 : _M_id; @@ -665,10 +664,10 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) if (__gthread_active_p()) { { - __gnu_cxx::lock sentry(__gnu_internal::freelist_mutex); + __gnu_cxx::lock sentry(freelist_mutex); - if (!__gnu_internal::freelist._M_thread_freelist_array - || __gnu_internal::freelist._M_max_threads + if (!freelist._M_thread_freelist_array + || freelist._M_max_threads < _M_options._M_max_threads) { const size_t __k = sizeof(_Thread_record) @@ -691,22 +690,21 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) _M_thread_freelist[__i - 1]._M_next = NULL; _M_thread_freelist[__i - 1]._M_id = __i; - if (!__gnu_internal::freelist._M_thread_freelist_array) + if (!freelist._M_thread_freelist_array) { // Initialize per thread key to hold pointer to // _M_thread_freelist. - __gthread_key_create(&__gnu_internal::freelist._M_key, - __gnu_internal::_M_destroy_thread_key); - __gnu_internal::freelist._M_thread_freelist - = _M_thread_freelist; + __gthread_key_create(&freelist._M_key, + ::_M_destroy_thread_key); + freelist._M_thread_freelist = _M_thread_freelist; } else { _Thread_record* _M_old_freelist - = __gnu_internal::freelist._M_thread_freelist; + = freelist._M_thread_freelist; _Thread_record* _M_old_array - = __gnu_internal::freelist._M_thread_freelist_array; - __gnu_internal::freelist._M_thread_freelist + = freelist._M_thread_freelist_array; + freelist._M_thread_freelist = &_M_thread_freelist[_M_old_freelist - _M_old_array]; while (_M_old_freelist) { @@ -714,17 +712,15 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) if (_M_old_freelist->_M_next) next_id = _M_old_freelist->_M_next - _M_old_array; else - next_id = __gnu_internal::freelist._M_max_threads; + next_id = freelist._M_max_threads; _M_thread_freelist[_M_old_freelist->_M_id - 1]._M_next = &_M_thread_freelist[next_id]; _M_old_freelist = _M_old_freelist->_M_next; } ::operator delete(static_cast<void*>(_M_old_array)); } - __gnu_internal::freelist._M_thread_freelist_array - = _M_thread_freelist; - __gnu_internal::freelist._M_max_threads - = _M_options._M_max_threads; + freelist._M_thread_freelist_array = _M_thread_freelist; + freelist._M_max_threads = _M_options._M_max_threads; } } diff --git a/libstdc++-v3/src/pool_allocator.cc b/libstdc++-v3/src/pool_allocator.cc index e9c770e..3044138 100644 --- a/libstdc++-v3/src/pool_allocator.cc +++ b/libstdc++-v3/src/pool_allocator.cc @@ -35,7 +35,7 @@ #include <cstdlib> #include <ext/pool_allocator.h> -namespace __gnu_internal _GLIBCXX_VISIBILITY(hidden) +namespace { static __glibcxx_mutex_define_initialized(palloc_init_mutex); } @@ -52,7 +52,7 @@ _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) mutex_type& __pool_alloc_base::_M_get_mutex() - { return __gnu_internal::palloc_init_mutex; } + { return palloc_init_mutex; } // Allocate memory in large chunks in order to avoid fragmenting the // heap too much. Assume that __n is properly aligned. We hold the |