From ae4a7d92ed31eeacb6c8728e33b7af0fde87268c Mon Sep 17 00:00:00 2001 From: paolo Date: Tue, 19 Sep 2006 09:07:56 +0000 Subject: [PATCH] 2006-09-19 Paolo Carlini * include/tr1/hashtable_policy.h: Uglify all the names. * include/tr1/hashtable: Likewise. * include/tr1/unordered_map: Likewise. * include/tr1/unordered_set: Likewise. * include/tr1/functional: Uglify struct hash names. * include/tr1/cmath: Uglify namespace detail to __detail. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@117052 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 9 + libstdc++-v3/include/tr1/cmath | 24 +- libstdc++-v3/include/tr1/functional | 214 ++--- libstdc++-v3/include/tr1/hashtable | 1278 ++++++++++++++------------- libstdc++-v3/include/tr1/hashtable_policy.h | 760 ++++++++-------- libstdc++-v3/include/tr1/unordered_map | 182 ++-- libstdc++-v3/include/tr1/unordered_set | 174 ++-- 7 files changed, 1396 insertions(+), 1245 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index d0c8d63a5b5..0d8622b71ad 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,12 @@ +2006-09-19 Paolo Carlini + + * include/tr1/hashtable_policy.h: Uglify all the names. + * include/tr1/hashtable: Likewise. + * include/tr1/unordered_map: Likewise. + * include/tr1/unordered_set: Likewise. + * include/tr1/functional: Uglify struct hash names. + * include/tr1/cmath: Uglify namespace detail to __detail. + 2006-09-18 Benjamin Kosnik * testsuite/util/regression/res_mng: Remove. diff --git a/libstdc++-v3/include/tr1/cmath b/libstdc++-v3/include/tr1/cmath index 1b9cc8adb6f..0e3320decc0 100644 --- a/libstdc++-v3/include/tr1/cmath +++ b/libstdc++-v3/include/tr1/cmath @@ -368,21 +368,23 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) using std::atan; // Workaround for c++/21682. - namespace detail + namespace __detail { template - inline typename __gnu_cxx::__enable_if::__value - || std::__is_floating<_Up>::__value, - typename std::tr1::__promote_2<_Tp, _Up>::__type>::__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 + inline typename + __gnu_cxx::__enable_if::__value + || std::__is_floating<_Up>::__value, + typename + std::tr1::__promote_2<_Tp, _Up>::__type>::__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; + using __detail::atan2; inline float atanh(float __x) diff --git a/libstdc++-v3/include/tr1/functional b/libstdc++-v3/include/tr1/functional index b9afe4b2b4f..ef85e5b7ab0 100644 --- a/libstdc++-v3/include/tr1/functional +++ b/libstdc++-v3/include/tr1/functional @@ -1,6 +1,6 @@ // TR1 functional header -*- C++ -*- -// Copyright (C) 2004, 2005 Free Software Foundation, Inc. +// Copyright (C) 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 @@ -106,7 +106,7 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) */ template struct _Weak_result_type_impl - : _Maybe_get_result_type<_Has_result_type<_Functor>::value, _Functor> + : _Maybe_get_result_type<_Has_result_type<_Functor>::value, _Functor> { }; @@ -214,33 +214,33 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // Not a unary_function or binary_function, so try a weak result type template struct _Reference_wrapper_base_impl - : _Weak_result_type<_Tp> + : _Weak_result_type<_Tp> { }; // unary_function but not binary_function template struct _Reference_wrapper_base_impl - : unary_function + : unary_function { }; // binary_function but not unary_function template struct _Reference_wrapper_base_impl - : binary_function + : binary_function { }; // both unary_function and binary_function. import result_type to // avoid conflicts. template struct _Reference_wrapper_base_impl - : unary_function, - binary_function + : unary_function, + binary_function { typedef typename _Tp::result_type result_type; }; @@ -255,82 +255,82 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) */ template struct _Reference_wrapper_base - : _Reference_wrapper_base_impl< - _Derives_from_unary_function<_Tp>::value, - _Derives_from_binary_function<_Tp>::value, - _Tp> + : _Reference_wrapper_base_impl< + _Derives_from_unary_function<_Tp>::value, + _Derives_from_binary_function<_Tp>::value, + _Tp> { }; // - a function type (unary) template struct _Reference_wrapper_base<_Res(_T1)> - : unary_function<_T1, _Res> + : unary_function<_T1, _Res> { }; // - a function type (binary) template struct _Reference_wrapper_base<_Res(_T1, _T2)> - : binary_function<_T1, _T2, _Res> + : binary_function<_T1, _T2, _Res> { }; // - a function pointer type (unary) template struct _Reference_wrapper_base<_Res(*)(_T1)> - : unary_function<_T1, _Res> + : unary_function<_T1, _Res> { }; // - a function pointer type (binary) template struct _Reference_wrapper_base<_Res(*)(_T1, _T2)> - : binary_function<_T1, _T2, _Res> + : binary_function<_T1, _T2, _Res> { }; // - a pointer to member function type (unary, no qualifiers) template struct _Reference_wrapper_base<_Res (_T1::*)()> - : unary_function<_T1*, _Res> + : unary_function<_T1*, _Res> { }; // - a pointer to member function type (binary, no qualifiers) template struct _Reference_wrapper_base<_Res (_T1::*)(_T2)> - : binary_function<_T1*, _T2, _Res> + : binary_function<_T1*, _T2, _Res> { }; // - a pointer to member function type (unary, const) template struct _Reference_wrapper_base<_Res (_T1::*)() const> - : unary_function + : unary_function { }; // - a pointer to member function type (binary, const) template struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const> - : binary_function + : binary_function { }; // - a pointer to member function type (unary, volatile) template struct _Reference_wrapper_base<_Res (_T1::*)() volatile> - : unary_function + : unary_function { }; // - a pointer to member function type (binary, volatile) template struct _Reference_wrapper_base<_Res (_T1::*)(_T2) volatile> - : binary_function + : binary_function { }; // - a pointer to member function type (unary, const volatile) template struct _Reference_wrapper_base<_Res (_T1::*)() const volatile> - : unary_function + : unary_function { }; // - a pointer to member function type (binary, const volatile) template struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const volatile> - : binary_function + : binary_function { }; template @@ -452,10 +452,10 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) public: template struct _Result_type - : _Mem_fn_const_or_non< - _Res, - (sizeof(__sfinae_types::__two) - == sizeof(__check_const<_Tp>(__get_ref<_Tp>(), (_Tp*)0)))> + : _Mem_fn_const_or_non< + _Res, + (sizeof(__sfinae_types::__two) + == sizeof(__check_const<_Tp>(__get_ref<_Tp>(), (_Tp*)0)))> { }; template @@ -463,11 +463,11 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) template struct result<_CVMem(_Tp)> - : public _Result_type<_Tp> { }; + : public _Result_type<_Tp> { }; template struct result<_CVMem(_Tp&)> - : public _Result_type<_Tp> { }; + : public _Result_type<_Tp> { }; explicit _Mem_fn(_Res _Class::*__pm) : __pm(__pm) { } @@ -1100,37 +1100,37 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) template struct hash; -#define tr1_hashtable_define_trivial_hash(T) \ +#define _TR1_hashtable_define_trivial_hash(_Tp) \ template<> \ - struct hash \ - : public std::unary_function \ + struct hash<_Tp> \ + : public std::unary_function<_Tp, std::size_t> \ { \ std::size_t \ - operator()(T val) const \ - { return static_cast(val); } \ + operator()(_Tp __val) const \ + { return static_cast(__val); } \ } - tr1_hashtable_define_trivial_hash(bool); - tr1_hashtable_define_trivial_hash(char); - tr1_hashtable_define_trivial_hash(signed char); - tr1_hashtable_define_trivial_hash(unsigned char); - tr1_hashtable_define_trivial_hash(wchar_t); - tr1_hashtable_define_trivial_hash(short); - tr1_hashtable_define_trivial_hash(int); - tr1_hashtable_define_trivial_hash(long); - tr1_hashtable_define_trivial_hash(unsigned short); - tr1_hashtable_define_trivial_hash(unsigned int); - tr1_hashtable_define_trivial_hash(unsigned long); + _TR1_hashtable_define_trivial_hash(bool); + _TR1_hashtable_define_trivial_hash(char); + _TR1_hashtable_define_trivial_hash(signed char); + _TR1_hashtable_define_trivial_hash(unsigned char); + _TR1_hashtable_define_trivial_hash(wchar_t); + _TR1_hashtable_define_trivial_hash(short); + _TR1_hashtable_define_trivial_hash(int); + _TR1_hashtable_define_trivial_hash(long); + _TR1_hashtable_define_trivial_hash(unsigned short); + _TR1_hashtable_define_trivial_hash(unsigned int); + _TR1_hashtable_define_trivial_hash(unsigned long); -#undef tr1_hashtable_define_trivial_hash +#undef _TR1_hashtable_define_trivial_hash - template - struct hash - : public std::unary_function + template + struct hash<_Tp*> + : public std::unary_function<_Tp*, std::size_t> { std::size_t - operator()(T* p) const - { return reinterpret_cast(p); } + operator()(_Tp* __p) const + { return reinterpret_cast(__p); } }; // Fowler / Noll / Vo (FNV) Hash (type FNV-1a) @@ -1138,47 +1138,48 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // Dummy generic implementation (for sizeof(size_t) != 4, 8). template - struct Fnv_hash + struct _Fnv_hash { static std::size_t - hash(const char* first, std::size_t length) + hash(const char* __first, std::size_t __length) { - std::size_t result = 0; - for (; length > 0; --length) - result = (result * 131) + *first++; - return result; + std::size_t __result = 0; + for (; __length > 0; --__length) + __result = (__result * 131) + *__first++; + return __result; } }; template<> - struct Fnv_hash<4> + struct _Fnv_hash<4> { static std::size_t - hash(const char* first, std::size_t length) + hash(const char* __first, std::size_t __length) { - std::size_t result = static_cast(2166136261UL); - for (; length > 0; --length) + std::size_t __result = static_cast(2166136261UL); + for (; __length > 0; --__length) { - result ^= (std::size_t)*first++; - result *= 16777619UL; + __result ^= (std::size_t)*__first++; + __result *= 16777619UL; } - return result; + return __result; } }; template<> - struct Fnv_hash<8> + struct _Fnv_hash<8> { static std::size_t - hash(const char* first, std::size_t length) + hash(const char* __first, std::size_t __length) { - std::size_t result = static_cast(14695981039346656037ULL); - for (; length > 0; --length) + std::size_t __result = + static_cast(14695981039346656037ULL); + for (; __length > 0; --__length) { - result ^= (std::size_t)*first++; - result *= 1099511628211ULL; + __result ^= (std::size_t)*__first++; + __result *= 1099511628211ULL; } - return result; + return __result; } }; @@ -1190,8 +1191,8 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) : public std::unary_function { std::size_t - operator()(const std::string& s) const - { return Fnv_hash<>::hash(s.data(), s.length()); } + operator()(const std::string& __s) const + { return _Fnv_hash<>::hash(__s.data(), __s.length()); } }; #ifdef _GLIBCXX_USE_WCHAR_T @@ -1200,10 +1201,10 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) : public std::unary_function { std::size_t - operator()(const std::wstring& s) const + operator()(const std::wstring& __s) const { - return Fnv_hash<>::hash(reinterpret_cast(s.data()), - s.length() * sizeof(wchar_t)); + return _Fnv_hash<>::hash(reinterpret_cast(__s.data()), + __s.length() * sizeof(wchar_t)); } }; #endif @@ -1213,15 +1214,15 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) : public std::unary_function { std::size_t - operator()(float fval) const + operator()(float __fval) const { - std::size_t result = 0; + std::size_t __result = 0; // 0 and -0 both hash to zero. - if (fval != 0.0f) - result = Fnv_hash<>::hash(reinterpret_cast(&fval), - sizeof(fval)); - return result; + if (__fval != 0.0f) + __result = _Fnv_hash<>::hash(reinterpret_cast(&__fval), + sizeof(__fval)); + return __result; } }; @@ -1230,15 +1231,15 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) : public std::unary_function { std::size_t - operator()(double dval) const + operator()(double __dval) const { - std::size_t result = 0; + std::size_t __result = 0; // 0 and -0 both hash to zero. - if (dval != 0.0) - result = Fnv_hash<>::hash(reinterpret_cast(&dval), - sizeof(dval)); - return result; + if (__dval != 0.0) + __result = _Fnv_hash<>::hash(reinterpret_cast(&__dval), + sizeof(__dval)); + return __result; } }; @@ -1249,29 +1250,30 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) : public std::unary_function { std::size_t - operator()(long double ldval) const + operator()(long double __ldval) const { - std::size_t result = 0; + std::size_t __result = 0; - int exponent; - ldval = std::frexp(ldval, &exponent); - ldval = ldval < 0.0l ? -(ldval + 0.5l) : ldval; + int __exponent; + __ldval = std::frexp(__ldval, &__exponent); + __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval; - const long double mult = std::numeric_limits::max() + 1.0l; - ldval *= mult; + const long double __mult = + std::numeric_limits::max() + 1.0l; + __ldval *= __mult; // Try to use all the bits of the mantissa (really necessary only // on 32-bit targets, at least for 80-bit floating point formats). - const std::size_t hibits = (std::size_t)ldval; - ldval = (ldval - (long double)hibits) * mult; + const std::size_t __hibits = (std::size_t)__ldval; + __ldval = (__ldval - (long double)__hibits) * __mult; - const std::size_t coeff = + const std::size_t __coeff = (std::numeric_limits::max() / std::numeric_limits::max_exponent); - result = hibits + (std::size_t)ldval + coeff * exponent; + __result = __hibits + (std::size_t)__ldval + __coeff * __exponent; - return result; + return __result; } }; diff --git a/libstdc++-v3/include/tr1/hashtable b/libstdc++-v3/include/tr1/hashtable index 47d04ebf98b..07ac6a881a8 100644 --- a/libstdc++-v3/include/tr1/hashtable +++ b/libstdc++-v3/include/tr1/hashtable @@ -66,40 +66,40 @@ namespace std { _GLIBCXX_BEGIN_NAMESPACE(tr1) - // Class template hashtable, class definition. + // Class template _Hashtable, class definition. - // Meaning of class template hashtable's template parameters + // Meaning of class template _Hashtable's template parameters - // Key and Value: arbitrary CopyConstructible types. + // _Key and _Value: arbitrary CopyConstructible types. - // Allocator: an allocator type ([lib.allocator.requirements]) whose + // _Allocator: an allocator type ([lib.allocator.requirements]) whose // value type is Value. - // ExtractKey: function object that takes a object of type Value - // and returns a value of type Key. + // _ExtractKey: function object that takes a object of type Value + // and returns a value of type _Key. - // Equal: function object that takes two objects of type k and returns + // _Equal: function object that takes two objects of type k and returns // a bool-like value that is true if the two objects are considered equal. - // H1: the hash function. A unary function object with argument type + // _H1: the hash function. A unary function object with argument type // Key and result type size_t. Return values should be distributed // over the entire range [0, numeric_limits:::max()]. - // H2: the range-hashing function (in the terminology of Tavori and + // _H2: the range-hashing function (in the terminology of Tavori and // Dreizin). A binary function object whose argument types and result // type are all size_t. Given arguments r and N, the return value is // in the range [0, N). - // H: the ranged hash function (Tavori and Dreizin). A binary function - // whose argument types are Key and size_t and whose result type is + // _Hash: the ranged hash function (Tavori and Dreizin). A binary function + // whose argument types are _Key and size_t and whose result type is // size_t. Given arguments k and N, the return value is in the range - // [0, N). Default: h(k, N) = h2(h1(k), N). If H is anything other - // than the default, H1 and H2 are ignored. + // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other + // than the default, _H1 and _H2 are ignored. - // RehashPolicy: Policy class with three members, all of which govern - // the bucket count. n_bkt(n) returns a bucket count no smaller - // than n. bkt_for_elements(n) returns a bucket count appropriate - // for an element count of n. need_rehash(n_bkt, n_elt, n_ins) + // _RehashPolicy: Policy class with three members, all of which govern + // the bucket count. _M_next_bkt(n) returns a bucket count no smaller + // than n. _M_bkt_for_elements(n) returns a bucket count appropriate + // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) // determines whether, if the current bucket count is n_bkt and the // current element count is n_elt, we need to increase the bucket // count. If so, returns make_pair(true, n), where n is the new @@ -108,151 +108,159 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // ??? Right now it is hard-wired that the number of buckets never // shrinks. Should we allow RehashPolicy to change that? - // cache_hash_code: bool. true if we store the value of the hash + // __cache_hash_code: bool. true if we store the value of the hash // function along with the value. This is a time-space tradeoff. // Storing it may improve lookup speed by reducing the number of times // we need to call the Equal function. - // constant_iterators: bool. true if iterator and const_iterator are + // __constant_iterators: bool. true if iterator and const_iterator are // both constant iterator types. This is true for unordered_set and // unordered_multiset, false for unordered_map and unordered_multimap. - // unique_keys: bool. true if the return value of hashtable::count(k) + // __unique_keys: bool. true if the return value of _Hashtable::count(k) // is always at most one, false if it may be an arbitrary number. This // true for unordered_set and unordered_map, false for unordered_multiset // and unordered_multimap. - template - class hashtable - : public detail::rehash_base >, - public detail::hash_code_base, - public detail::map_base > + template + class _Hashtable + : public __detail::_Rehash_base<_RehashPolicy, + _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, + __cache_hash_code, + __constant_iterators, + __unique_keys> >, + public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __cache_hash_code>, + public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, + _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, + _Equal, _H1, _H2, _Hash, + _RehashPolicy, + __cache_hash_code, + __constant_iterators, + __unique_keys> > { public: - typedef Allocator allocator_type; - typedef Value value_type; - typedef Key key_type; - typedef Equal key_equal; + typedef _Allocator allocator_type; + typedef _Value value_type; + typedef _Key key_type; + typedef _Equal key_equal; // mapped_type, if present, comes from map_base. // hasher, if present, comes from hash_code_base. - typedef typename Allocator::difference_type difference_type; - typedef typename Allocator::size_type size_type; - typedef typename Allocator::reference reference; - typedef typename Allocator::const_reference const_reference; + typedef typename _Allocator::difference_type difference_type; + typedef typename _Allocator::size_type size_type; + typedef typename _Allocator::reference reference; + typedef typename _Allocator::const_reference const_reference; - typedef detail::node_iterator + typedef __detail::_Node_iterator local_iterator; - typedef detail::node_const_iterator + typedef __detail::_Node_const_iterator const_local_iterator; - typedef detail::hashtable_iterator + typedef __detail::_Hashtable_iterator iterator; - typedef detail::hashtable_const_iterator + typedef __detail::_Hashtable_const_iterator const_iterator; - template - friend struct detail::map_base; + template + friend struct __detail::_Map_base; private: - typedef detail::hash_node node; - typedef typename Allocator::template rebind::other - node_allocator_t; - typedef typename Allocator::template rebind::other - bucket_allocator_t; - - node_allocator_t m_node_allocator; - node** m_buckets; - size_type m_bucket_count; - size_type m_element_count; - RehashPolicy m_rehash_policy; + typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; + typedef typename _Allocator::template rebind<_Node>::other + _Node_allocator_type; + typedef typename _Allocator::template rebind<_Node*>::other + _Bucket_allocator_type; + + _Node_allocator_type _M_node_allocator; + _Node** _M_buckets; + size_type _M_bucket_count; + size_type _M_element_count; + _RehashPolicy _M_rehash_policy; - node* - m_allocate_node(const value_type& v); + _Node* + _M_allocate_node(const value_type& __v); void - m_deallocate_node(node* n); + _M_deallocate_node(_Node* __n); void - m_deallocate_nodes(node**, size_type); + _M_deallocate_nodes(_Node**, size_type); - node** - m_allocate_buckets(size_type n); + _Node** + _M_allocate_buckets(size_type __n); void - m_deallocate_buckets(node**, size_type n); + _M_deallocate_buckets(_Node**, size_type __n); public: // Constructor, destructor, assignment, swap - hashtable(size_type bucket_hint, - const H1&, const H2&, const H&, - const Equal&, const ExtractKey&, - const allocator_type&); + _Hashtable(size_type __bucket_hint, + const _H1&, const _H2&, const _Hash&, + const _Equal&, const _ExtractKey&, + const allocator_type&); - template - hashtable(InIter first, InIter last, - size_type bucket_hint, - const H1&, const H2&, const H&, - const Equal&, const ExtractKey&, - const allocator_type&); + template + _Hashtable(_InputIterator __first, _InputIterator __last, + size_type __bucket_hint, + const _H1&, const _H2&, const _Hash&, + const _Equal&, const _ExtractKey&, + const allocator_type&); - hashtable(const hashtable&); + _Hashtable(const _Hashtable&); - hashtable& - operator=(const hashtable&); + _Hashtable& + operator=(const _Hashtable&); - ~hashtable(); + ~_Hashtable(); - void swap(hashtable&); + void swap(_Hashtable&); // Basic container operations iterator begin() { - iterator i(m_buckets); - if (!i.m_cur_node) - i.m_incr_bucket(); - return i; + iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; } const_iterator begin() const { - const_iterator i(m_buckets); - if (!i.m_cur_node) - i.m_incr_bucket(); - return i; + const_iterator __i(_M_buckets); + if (!__i._M_cur_node) + __i._M_incr_bucket(); + return __i; } iterator end() - { return iterator(m_buckets + m_bucket_count); } + { return iterator(_M_buckets + _M_bucket_count); } const_iterator end() const - { return const_iterator(m_buckets + m_bucket_count); } + { return const_iterator(_M_buckets + _M_bucket_count); } size_type size() const - { return m_element_count; } + { return _M_element_count; } bool empty() const @@ -260,50 +268,50 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) allocator_type get_allocator() const - { return m_node_allocator; } + { return _M_node_allocator; } size_type max_size() const - { return m_node_allocator.max_size(); } + { return _M_node_allocator.max_size(); } // Observers key_equal key_eq() const - { return this->m_eq; } + { return this->_M_eq; } - // hash_function, if present, comes from hash_code_base. + // hash_function, if present, comes from _Hash_code_base. // Bucket operations size_type bucket_count() const - { return m_bucket_count; } + { return _M_bucket_count; } size_type max_bucket_count() const { return max_size(); } size_type - bucket_size(size_type n) const - { return std::distance(begin(n), end(n)); } + bucket_size(size_type __n) const + { return std::distance(begin(__n), end(__n)); } size_type - bucket(const key_type& k) const + bucket(const key_type& __k) const { - return this->bucket_index(k, this->m_hash_code(k), - this->m_bucket_count); + return this->_M_bucket_index(__k, this->_M_hash_code(__k), + bucket_count()); } local_iterator - begin(size_type n) - { return local_iterator(m_buckets[n]); } + begin(size_type __n) + { return local_iterator(_M_buckets[__n]); } local_iterator end(size_type) { return local_iterator(0); } const_local_iterator - begin(size_type n) const - { return const_local_iterator(m_buckets[n]); } + begin(size_type __n) const + { return const_local_iterator(_M_buckets[__n]); } const_local_iterator end(size_type) const @@ -315,82 +323,83 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) return static_cast(size()) / static_cast(bucket_count()); } - // max_load_factor, if present, comes from rehash_base. + // max_load_factor, if present, comes from _Rehash_base. // Generalization of max_load_factor. Extension, not found in TR1. Only - // useful if RehashPolicy is something other than the default. - const RehashPolicy& - rehash_policy() const - { return m_rehash_policy; } + // useful if _RehashPolicy is something other than the default. + const _RehashPolicy& + __rehash_policy() const + { return _M_rehash_policy; } void - rehash_policy(const RehashPolicy&); + __rehash_policy(const _RehashPolicy&); // Lookup. iterator - find(const key_type& k); + find(const key_type& __k); const_iterator - find(const key_type& k) const; + find(const key_type& __k) const; size_type - count(const key_type& k) const; + count(const key_type& __k) const; std::pair - equal_range(const key_type& k); + equal_range(const key_type& __k); std::pair - equal_range(const key_type& k) const; + equal_range(const key_type& __k) const; private: // Find, insert and erase helper functions // ??? This dispatching is a workaround for the fact that we don't // have partial specialization of member templates; it would be - // better to just specialize insert on unique_keys. There may be a + // better to just specialize insert on __unique_keys. There may be a // cleaner workaround. - typedef typename __gnu_cxx::__conditional_type, iterator>::__type - Insert_Return_Type; + _Insert_Return_Type; - typedef typename __gnu_cxx::__conditional_type, - std::_Identity + typedef typename __gnu_cxx::__conditional_type<__unique_keys, + std::_Select1st<_Insert_Return_Type>, + std::_Identity<_Insert_Return_Type> >::__type - Insert_Conv_Type; + _Insert_Conv_Type; - node* - m_find_node(node*, const key_type&, - typename hashtable::hash_code_t) const; + _Node* + _M_find_node(_Node*, const key_type&, + typename _Hashtable::_Hash_code_type) const; iterator - m_insert_bucket(const value_type&, size_type, - typename hashtable::hash_code_t); + _M_insert_bucket(const value_type&, size_type, + typename _Hashtable::_Hash_code_type); std::pair - m_insert(const value_type&, std::tr1::true_type); + _M_insert(const value_type&, std::tr1::true_type); iterator - m_insert(const value_type&, std::tr1::false_type); + _M_insert(const value_type&, std::tr1::false_type); void - m_erase_node(node*, node**); + _M_erase_node(_Node*, _Node**); public: // Insert and erase - Insert_Return_Type - insert(const value_type& v) - { return m_insert(v, std::tr1::integral_constant()); } + _Insert_Return_Type + insert(const value_type& __v) + { return _M_insert(__v, std::tr1::integral_constant()); } iterator - insert(iterator, const value_type& v) - { return iterator(Insert_Conv_Type()(this->insert(v))); } + insert(iterator, const value_type& __v) + { return iterator(_Insert_Conv_Type()(this->insert(__v))); } const_iterator - insert(const_iterator, const value_type& v) - { return const_iterator(Insert_Conv_Type()(this->insert(v))); } + insert(const_iterator, const value_type& __v) + { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); } - template + template void - insert(InIter first, InIter last); + insert(_InputIterator __first, _InputIterator __last); iterator erase(iterator); @@ -411,365 +420,407 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) clear(); // Set number of buckets to be appropriate for container of n element. - void rehash(size_type n); + void rehash(size_type __n); private: // Unconditionally change size of bucket array to n. - void m_rehash(size_type n); + void _M_rehash(size_type __n); }; - // Definitions of class template hashtable's out-of-line member functions. - template - typename hashtable::node* - hashtable:: - m_allocate_node(const value_type& v) + // Definitions of class template _Hashtable's out-of-line member functions. + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node* + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_allocate_node(const value_type& __v) { - node* n = m_node_allocator.allocate(1); + _Node* __n = _M_node_allocator.allocate(1); try { - get_allocator().construct(&n->m_v, v); - n->m_next = 0; - return n; + get_allocator().construct(&__n->_M_v, __v); + __n->_M_next = 0; + return __n; } catch(...) { - m_node_allocator.deallocate(n, 1); + _M_node_allocator.deallocate(__n, 1); __throw_exception_again; } } - template + template void - hashtable:: - m_deallocate_node(node* n) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_node(_Node* __n) { - get_allocator().destroy(&n->m_v); - m_node_allocator.deallocate(n, 1); + get_allocator().destroy(&__n->_M_v); + _M_node_allocator.deallocate(__n, 1); } - template + template void - hashtable:: - m_deallocate_nodes(node** array, size_type n) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_nodes(_Node** __array, size_type __n) { - for (size_type i = 0; i < n; ++i) + for (size_type __i = 0; __i < __n; ++__i) { - node* p = array[i]; - while (p) + _Node* __p = __array[__i]; + while (__p) { - node* tmp = p; - p = p->m_next; - m_deallocate_node(tmp); + _Node* __tmp = __p; + __p = __p->_M_next; + _M_deallocate_node(__tmp); } - array[i] = 0; + __array[__i] = 0; } } - template - typename hashtable::node** - hashtable:: - m_allocate_buckets(size_type n) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node** + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_allocate_buckets(size_type __n) { - bucket_allocator_t alloc(m_node_allocator); + _Bucket_allocator_type __alloc(_M_node_allocator); // We allocate one extra bucket to hold a sentinel, an arbitrary // non-null pointer. Iterator increment relies on this. - node** p = alloc.allocate(n + 1); - std::fill(p, p + n, (node*) 0); - p[n] = reinterpret_cast(0x1000); - return p; + _Node** __p = __alloc.allocate(__n + 1); + std::fill(__p, __p + __n, (_Node*) 0); + __p[__n] = reinterpret_cast<_Node*>(0x1000); + return __p; } - template + template void - hashtable:: - m_deallocate_buckets(node** p, size_type n) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_deallocate_buckets(_Node** __p, size_type __n) { - bucket_allocator_t alloc(m_node_allocator); - alloc.deallocate(p, n + 1); + _Bucket_allocator_type __alloc(_M_node_allocator); + __alloc.deallocate(__p, __n + 1); } - template - hashtable:: - hashtable(size_type bucket_hint, - const H1& h1, const H2& h2, const H& h, - const Eq& eq, const Ex& exk, - const allocator_type& a) - : detail::rehash_base(), - detail::hash_code_base(exk, eq, h1, h2, h), - detail::map_base(), - m_node_allocator(a), - m_bucket_count(0), - m_element_count(0), - m_rehash_policy() + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(size_type __bucket_hint, + const _H1& __h1, const _H2& __h2, const _Hash& __h, + const _Equal& __eq, const _ExtractKey& __exk, + const allocator_type& __a) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__exk, __eq, + __h1, __h2, __h), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + _M_node_allocator(__a), + _M_bucket_count(0), + _M_element_count(0), + _M_rehash_policy() { - m_bucket_count = m_rehash_policy.next_bkt(bucket_hint); - m_buckets = m_allocate_buckets(m_bucket_count); + _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint); + _M_buckets = _M_allocate_buckets(_M_bucket_count); } - template - template - hashtable:: - hashtable(InIter f, InIter l, - size_type bucket_hint, - const H1& h1, const H2& h2, const H& h, - const Eq& eq, const Ex& exk, - const allocator_type& a) - : detail::rehash_base(), - detail::hash_code_base(exk, eq, - h1, h2, h), - detail::map_base(), - m_node_allocator(a), - m_bucket_count(0), - m_element_count(0), - m_rehash_policy() + template + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(_InputIterator __f, _InputIterator __l, + size_type __bucket_hint, + const _H1& __h1, const _H2& __h2, const _Hash& __h, + const _Equal& __eq, const _ExtractKey& __exk, + const allocator_type& __a) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__exk, __eq, + __h1, __h2, __h), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), + _M_node_allocator(__a), + _M_bucket_count(0), + _M_element_count(0), + _M_rehash_policy() { - m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint), - m_rehash_policy. - bkt_for_elements(detail:: - distance_fw(f, l))); - m_buckets = m_allocate_buckets(m_bucket_count); + _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint), + _M_rehash_policy. + _M_bkt_for_elements(__detail:: + __distance_fw(__f, + __l))); + _M_buckets = _M_allocate_buckets(_M_bucket_count); try { - for (; f != l; ++f) - this->insert(*f); + for (; __f != __l; ++__f) + this->insert(*__f); } catch(...) { clear(); - m_deallocate_buckets(m_buckets, m_bucket_count); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); __throw_exception_again; } } - template - hashtable:: - hashtable(const hashtable& ht) - : detail::rehash_base(ht), - detail::hash_code_base(ht), - detail::map_base(ht), - m_node_allocator(ht.get_allocator()), - m_bucket_count(ht.m_bucket_count), - m_element_count(ht.m_element_count), - m_rehash_policy(ht.m_rehash_policy) + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _Hashtable(const _Hashtable& __ht) + : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht), + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>(__ht), + __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht), + _M_node_allocator(__ht.get_allocator()), + _M_bucket_count(__ht._M_bucket_count), + _M_element_count(__ht._M_element_count), + _M_rehash_policy(__ht._M_rehash_policy) { - m_buckets = m_allocate_buckets(m_bucket_count); + _M_buckets = _M_allocate_buckets(_M_bucket_count); try { - for (size_type i = 0; i < ht.m_bucket_count; ++i) + for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i) { - node* n = ht.m_buckets[i]; - node** tail = m_buckets + i; - while (n) + _Node* __n = __ht._M_buckets[__i]; + _Node** __tail = _M_buckets + __i; + while (__n) { - *tail = m_allocate_node(n->m_v); - this->copy_code(*tail, n); - tail = &((*tail)->m_next); - n = n->m_next; + *__tail = _M_allocate_node(__n->_M_v); + this->_M_copy_code(*__tail, __n); + __tail = &((*__tail)->_M_next); + __n = __n->_M_next; } } } catch(...) { clear(); - m_deallocate_buckets(m_buckets, m_bucket_count); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); __throw_exception_again; } } - template - hashtable& - hashtable:: - operator=(const hashtable& ht) + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>& + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + operator=(const _Hashtable& __ht) { - hashtable tmp(ht); - this->swap(tmp); + _Hashtable __tmp(__ht); + this->swap(__tmp); return *this; } - template - hashtable:: - ~hashtable() + template + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + ~_Hashtable() { clear(); - m_deallocate_buckets(m_buckets, m_bucket_count); + _M_deallocate_buckets(_M_buckets, _M_bucket_count); } - template + template void - hashtable:: - swap(hashtable& x) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + swap(_Hashtable& __x) { // The only base class with member variables is hash_code_base. We - // define hash_code_base::m_swap because different specializations + // define _Hash_code_base::_M_swap because different specializations // have different members. - detail::hash_code_base::m_swap(x); + __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, + _H1, _H2, _Hash, __chc>::_M_swap(__x); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 431. Swapping containers with unequal allocators. - std::__alloc_swap::_S_do_it(m_node_allocator, - x.m_node_allocator); + std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator, + __x._M_node_allocator); - std::swap(m_rehash_policy, x.m_rehash_policy); - std::swap(m_buckets, x.m_buckets); - std::swap(m_bucket_count, x.m_bucket_count); - std::swap(m_element_count, x.m_element_count); + std::swap(_M_rehash_policy, __x._M_rehash_policy); + std::swap(_M_buckets, __x._M_buckets); + std::swap(_M_bucket_count, __x._M_bucket_count); + std::swap(_M_element_count, __x._M_element_count); } - template + template void - hashtable:: - rehash_policy(const RP& pol) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + __rehash_policy(const _RehashPolicy& __pol) { - m_rehash_policy = pol; - size_type n_bkt = pol.bkt_for_elements(m_element_count); - if (n_bkt > m_bucket_count) - m_rehash(n_bkt); + _M_rehash_policy = __pol; + size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count); + if (__n_bkt > _M_bucket_count) + _M_rehash(__n_bkt); } - template - typename hashtable::iterator - hashtable:: - find(const key_type& k) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + find(const key_type& __k) { - typename hashtable::hash_code_t code = this->m_hash_code(k); - std::size_t n = this->bucket_index(k, code, this->bucket_count()); - node* p = m_find_node(m_buckets[n], k, code); - return p ? iterator(p, m_buckets + n) : this->end(); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); + return __p ? iterator(__p, _M_buckets + __n) : this->end(); } - template - typename hashtable::const_iterator - hashtable:: - find(const key_type& k) const + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + find(const key_type& __k) const { - typename hashtable::hash_code_t code = this->m_hash_code(k); - std::size_t n = this->bucket_index(k, code, this->bucket_count()); - node* p = m_find_node(m_buckets[n], k, code); - return p ? const_iterator(p, m_buckets + n) : this->end(); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node* __p = _M_find_node(_M_buckets[__n], __k, __code); + return __p ? const_iterator(__p, _M_buckets + __n) : this->end(); } - template - typename hashtable::size_type - hashtable:: - count(const key_type& k) const + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::size_type + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + count(const key_type& __k) const { - typename hashtable::hash_code_t code = this->m_hash_code(k); - std::size_t n = this->bucket_index(k, code, this->bucket_count()); - std::size_t result = 0; - for (node* p = m_buckets[n]; p; p = p->m_next) - if (this->compare(k, code, p)) - ++result; - return result; + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + std::size_t __result = 0; + for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next) + if (this->_M_compare(__k, __code, __p)) + ++__result; + return __result; } - template - std::pair::iterator, - typename hashtable::iterator> - hashtable:: - equal_range(const key_type& k) + template + std::pair::iterator, + typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + equal_range(const key_type& __k) { - typename hashtable::hash_code_t code = this->m_hash_code(k); - std::size_t n = this->bucket_index(k, code, this->bucket_count()); - node** head = m_buckets + n; - node* p = m_find_node(*head, k, code); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node** __head = _M_buckets + __n; + _Node* __p = _M_find_node(*__head, __k, __code); - if (p) + if (__p) { - node* p1 = p->m_next; - for (; p1; p1 = p1->m_next) - if (!this->compare(k, code, p1)) + _Node* __p1 = __p->_M_next; + for (; __p1; __p1 = __p1->_M_next) + if (!this->_M_compare(__k, __code, __p1)) break; - iterator first(p, head); - iterator last(p1, head); - if (!p1) - last.m_incr_bucket(); - return std::make_pair(first, last); + iterator __first(__p, __head); + iterator __last(__p1, __head); + if (!__p1) + __last._M_incr_bucket(); + return std::make_pair(__first, __last); } else return std::make_pair(this->end(), this->end()); } - template - std::pair::const_iterator, - typename hashtable::const_iterator> - hashtable:: - equal_range(const key_type& k) const + template + std::pair::const_iterator, + typename _Hashtable<_Key, _Value, _Allocator, + _ExtractKey, _Equal, _H1, + _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + equal_range(const key_type& __k) const { - typename hashtable::hash_code_t code = this->m_hash_code(k); - std::size_t n = this->bucket_index(k, code, this->bucket_count()); - node** head = m_buckets + n; - node* p = m_find_node(*head, k, code); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + _Node** __head = _M_buckets + __n; + _Node* __p = _M_find_node(*__head, __k, __code); - if (p) + if (__p) { - node* p1 = p->m_next; - for (; p1; p1 = p1->m_next) - if (!this->compare(k, code, p1)) + _Node* __p1 = __p->_M_next; + for (; __p1; __p1 = __p1->_M_next) + if (!this->_M_compare(__k, __code, __p1)) break; - const_iterator first(p, head); - const_iterator last(p1, head); - if (!p1) - last.m_incr_bucket(); - return std::make_pair(first, last); + const_iterator __first(__p, __head); + const_iterator __last(__p1, __head); + if (!__p1) + __last._M_incr_bucket(); + return std::make_pair(__first, __last); } else return std::make_pair(this->end(), this->end()); @@ -777,295 +828,330 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // Find the node whose key compares equal to k, beginning the search // at p (usually the head of a bucket). Return nil if no node is found. - template - typename hashtable::node* - hashtable:: - m_find_node(node* p, const key_type& k, - typename hashtable::hash_code_t code) const + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, + _Equal, _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::_Node* + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_find_node(_Node* __p, const key_type& __k, + typename _Hashtable::_Hash_code_type __code) const { - for (; p; p = p->m_next) - if (this->compare(k, code, p)) - return p; + for (; __p; __p = __p->_M_next) + if (this->_M_compare(__k, __code, __p)) + return __p; return false; } // Insert v in bucket n (assumes no element with its key already present). - template - typename hashtable::iterator - hashtable:: - m_insert_bucket(const value_type& v, size_type n, - typename hashtable::hash_code_t code) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert_bucket(const value_type& __v, size_type __n, + typename _Hashtable::_Hash_code_type __code) { - std::pair do_rehash - = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); // Allocate the new node before doing the rehash so that we don't // do a rehash if the allocation throws. - node* new_node = m_allocate_node(v); + _Node* __new_node = _M_allocate_node(__v); try { - if (do_rehash.first) + if (__do_rehash.first) { - const key_type& k = this->m_extract(v); - n = this->bucket_index(k, code, do_rehash.second); - m_rehash(do_rehash.second); + const key_type& __k = this->_M_extract(__v); + __n = this->_M_bucket_index(__k, __code, __do_rehash.second); + _M_rehash(__do_rehash.second); } - new_node->m_next = m_buckets[n]; - this->store_code(new_node, code); - m_buckets[n] = new_node; - ++m_element_count; - return iterator(new_node, m_buckets + n); + __new_node->_M_next = _M_buckets[__n]; + this->_M_store_code(__new_node, __code); + _M_buckets[__n] = __new_node; + ++_M_element_count; + return iterator(__new_node, _M_buckets + __n); } catch(...) { - m_deallocate_node(new_node); + _M_deallocate_node(__new_node); __throw_exception_again; } } // Insert v if no element with its key is already present. - template - std::pair::iterator, bool> - hashtable:: - m_insert(const value_type& v, std::tr1::true_type) + template + std::pair::iterator, bool> + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert(const value_type& __v, std::tr1::true_type) { - const key_type& k = this->m_extract(v); - typename hashtable::hash_code_t code = this->m_hash_code(k); - size_type n = this->bucket_index(k, code, m_bucket_count); + const key_type& __k = this->_M_extract(__v); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); - if (node* p = m_find_node(m_buckets[n], k, code)) - return std::make_pair(iterator(p, m_buckets + n), false); - return std::make_pair(m_insert_bucket(v, n, code), true); + if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code)) + return std::make_pair(iterator(__p, _M_buckets + __n), false); + return std::make_pair(_M_insert_bucket(__v, __n, __code), true); } // Insert v unconditionally. - template - typename hashtable::iterator - hashtable:: - m_insert(const value_type& v, std::tr1::false_type) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_insert(const value_type& __v, std::tr1::false_type) { - std::pair do_rehash - = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); - if (do_rehash.first) - m_rehash(do_rehash.second); + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); + if (__do_rehash.first) + _M_rehash(__do_rehash.second); - const key_type& k = this->m_extract(v); - typename hashtable::hash_code_t code = this->m_hash_code(k); - size_type n = this->bucket_index(k, code, m_bucket_count); + const key_type& __k = this->_M_extract(__v); + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count); // First find the node, avoid leaking new_node if compare throws. - node* prev = m_find_node(m_buckets[n], k, code); - node* new_node = m_allocate_node(v); + _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code); + _Node* __new_node = _M_allocate_node(__v); - if (prev) + if (__prev) { - new_node->m_next = prev->m_next; - prev->m_next = new_node; + __new_node->_M_next = __prev->_M_next; + __prev->_M_next = __new_node; } else { - new_node->m_next = m_buckets[n]; - m_buckets[n] = new_node; + __new_node->_M_next = _M_buckets[__n]; + _M_buckets[__n] = __new_node; } - this->store_code(new_node, code); + this->_M_store_code(__new_node, __code); - ++m_element_count; - return iterator(new_node, m_buckets + n); + ++_M_element_count; + return iterator(__new_node, _M_buckets + __n); } // For erase(iterator) and erase(const_iterator). - template + template void - hashtable:: - m_erase_node(node* p, node** b) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_erase_node(_Node* __p, _Node** __b) { - node* cur = *b; - if (cur == p) - *b = cur->m_next; + _Node* __cur = *__b; + if (__cur == __p) + *__b = __cur->_M_next; else { - node* next = cur->m_next; - while (next != p) + _Node* __next = __cur->_M_next; + while (__next != __p) { - cur = next; - next = cur->m_next; + __cur = __next; + __next = __cur->_M_next; } - cur->m_next = next->m_next; + __cur->_M_next = __next->_M_next; } - m_deallocate_node(p); - --m_element_count; + _M_deallocate_node(__p); + --_M_element_count; } - template - template + template + template void - hashtable:: - insert(InIter first, InIter last) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + insert(_InputIterator __first, _InputIterator __last) { - size_type n_elt = detail::distance_fw(first, last); - std::pair do_rehash - = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt); - if (do_rehash.first) - m_rehash(do_rehash.second); - - for (; first != last; ++first) - this->insert(*first); + size_type __n_elt = __detail::__distance_fw(__first, __last); + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, __n_elt); + if (__do_rehash.first) + _M_rehash(__do_rehash.second); + + for (; __first != __last; ++__first) + this->insert(*__first); } - template - typename hashtable::iterator - hashtable:: - erase(iterator it) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(iterator __it) { - iterator result = it; - ++result; - m_erase_node(it.m_cur_node, it.m_cur_bucket); - return result; + iterator __result = __it; + ++__result; + _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); + return __result; } - template - typename hashtable::const_iterator - hashtable:: - erase(const_iterator it) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const_iterator __it) { - const_iterator result = it; - ++result; - m_erase_node(it.m_cur_node, it.m_cur_bucket); - return result; + const_iterator __result = __it; + ++__result; + _M_erase_node(__it._M_cur_node, __it._M_cur_bucket); + return __result; } - template - typename hashtable::size_type - hashtable:: - erase(const key_type& k) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::size_type + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const key_type& __k) { - typename hashtable::hash_code_t code = this->m_hash_code(k); - std::size_t n = this->bucket_index(k, code, m_bucket_count); - size_type result = 0; + typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k); + std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count); + size_type __result = 0; - node** slot = m_buckets + n; - while (*slot && !this->compare(k, code, *slot)) - slot = &((*slot)->m_next); + _Node** __slot = _M_buckets + __n; + while (*__slot && !this->_M_compare(__k, __code, *__slot)) + __slot = &((*__slot)->_M_next); - while (*slot && this->compare(k, code, *slot)) + while (*__slot && this->_M_compare(__k, __code, *__slot)) { - node* p = *slot; - *slot = p->m_next; - m_deallocate_node(p); - --m_element_count; - ++result; + _Node* __p = *__slot; + *__slot = __p->_M_next; + _M_deallocate_node(__p); + --_M_element_count; + ++__result; } - return result; + return __result; } // ??? This could be optimized by taking advantage of the bucket // structure, but it's not clear that it's worth doing. It probably // wouldn't even be an optimization unless the load factor is large. - template - typename hashtable::iterator - hashtable:: - erase(iterator first, iterator last) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(iterator __first, iterator __last) { - while (first != last) - first = this->erase(first); - return last; + while (__first != __last) + __first = this->erase(__first); + return __last; } - template - typename hashtable::const_iterator - hashtable:: - erase(const_iterator first, const_iterator last) + template + typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, + __chc, __cit, __uk>::const_iterator + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + erase(const_iterator __first, const_iterator __last) { - while (first != last) - first = this->erase(first); - return last; + while (__first != __last) + __first = this->erase(__first); + return __last; } - template + template void - hashtable:: + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: clear() { - m_deallocate_nodes(m_buckets, m_bucket_count); - m_element_count = 0; + _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_element_count = 0; } - template + template void - hashtable:: - rehash(size_type n) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + rehash(size_type __n) { - m_rehash(std::max(m_rehash_policy.next_bkt(n), - m_rehash_policy.bkt_for_elements(m_element_count - + 1))); + _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n), + _M_rehash_policy._M_bkt_for_elements(_M_element_count + + 1))); } - template + template void - hashtable:: - m_rehash(size_type n) + _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, + _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: + _M_rehash(size_type __n) { - node** new_array = m_allocate_buckets(n); + _Node** __new_array = _M_allocate_buckets(__n); try { - for (size_type i = 0; i < m_bucket_count; ++i) - while (node* p = m_buckets[i]) + for (size_type __i = 0; __i < _M_bucket_count; ++__i) + while (_Node* __p = _M_buckets[__i]) { - std::size_t new_index = this->bucket_index(p, n); - m_buckets[i] = p->m_next; - p->m_next = new_array[new_index]; - new_array[new_index] = p; + std::size_t __new_index = this->_M_bucket_index(__p, __n); + _M_buckets[__i] = __p->_M_next; + __p->_M_next = __new_array[__new_index]; + __new_array[__new_index] = __p; } - m_deallocate_buckets(m_buckets, m_bucket_count); - m_bucket_count = n; - m_buckets = new_array; + _M_deallocate_buckets(_M_buckets, _M_bucket_count); + _M_bucket_count = __n; + _M_buckets = __new_array; } catch(...) { @@ -1073,10 +1159,10 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // We can't restore the previous state without calling the hash // function again, so the only sensible recovery is to delete // everything. - m_deallocate_nodes(new_array, n); - m_deallocate_buckets(new_array, n); - m_deallocate_nodes(m_buckets, m_bucket_count); - m_element_count = 0; + _M_deallocate_nodes(__new_array, __n); + _M_deallocate_buckets(__new_array, __n); + _M_deallocate_nodes(_M_buckets, _M_bucket_count); + _M_element_count = 0; __throw_exception_again; } } diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h index 076bcce45bf..d9fda09f5be 100644 --- a/libstdc++-v3/include/tr1/hashtable_policy.h +++ b/libstdc++-v3/include/tr1/hashtable_policy.h @@ -41,56 +41,58 @@ namespace std { _GLIBCXX_BEGIN_NAMESPACE(tr1) -namespace detail +namespace __detail { namespace { // Helper function: return distance(first, last) for forward // iterators, or 0 for input iterators. - template - inline typename std::iterator_traits::difference_type - distance_fw(Iterator first, Iterator last, std::input_iterator_tag) + template + inline typename std::iterator_traits<_Iterator>::difference_type + __distance_fw(_Iterator __first, _Iterator __last, + std::input_iterator_tag) { return 0; } - template - inline typename std::iterator_traits::difference_type - distance_fw(Iterator first, Iterator last, std::forward_iterator_tag) - { return std::distance(first, last); } + template + inline typename std::iterator_traits<_Iterator>::difference_type + __distance_fw(_Iterator __first, _Iterator __last, + std::forward_iterator_tag) + { return std::distance(__first, __last); } - template - inline typename std::iterator_traits::difference_type - distance_fw(Iterator first, Iterator last) + template + inline typename std::iterator_traits<_Iterator>::difference_type + __distance_fw(_Iterator __first, _Iterator __last) { - typedef typename std::iterator_traits::iterator_category tag; - return distance_fw(first, last, tag()); + 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 + // 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 + // _Prime_rehash_policy's member functions to be inline, and there's + // certainly no good reason for _Primes<> to exist at all. + struct _LessThan { - template + template bool - operator()(X x, Y y) - { return x < y; } + operator()(_Tp __x, _Up __y) + { return __x < __y; } }; - template - struct X + template + struct _Primes { - static const int n_primes = ulongsize != 8 ? 256 : 256 + 48; - static const unsigned long primes[256 + 48 + 1]; + static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48; + static const unsigned long __primes[256 + 48 + 1]; }; - template - const int X::n_primes; + template + const int _Primes<__ulongsize>::__n_primes; - template - const unsigned long X::primes[256 + 48 + 1] = + template + const unsigned long _Primes<__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, @@ -135,7 +137,7 @@ namespace 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, + __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull, (unsigned long)8589934583ull, (unsigned long)12884901857ull, (unsigned long)17179869143ull, (unsigned long)25769803693ull, (unsigned long)34359738337ull, @@ -168,306 +170,315 @@ namespace }; } // anonymous namespace - // Auxiliary types used for all instantiations of hashtable: nodes + // 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 + // 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 - struct hash_node; + template + struct _Hash_node; - template - struct hash_node + template + struct _Hash_node<_Value, true> { - Value m_v; - std::size_t hash_code; - hash_node* m_next; + _Value _M_v; + std::size_t _M_hash_code; + _Hash_node* _M_next; }; - template - struct hash_node + template + struct _Hash_node<_Value, false> { - Value m_v; - hash_node* m_next; + _Value _M_v; + _Hash_node* _M_next; }; // Local iterators, used to iterate within a bucket but not between // buckets. - template - struct node_iterator_base + template + struct _Node_iterator_base { - node_iterator_base(hash_node* p) - : m_cur(p) { } + _Node_iterator_base(_Hash_node<_Value, __cache>* __p) + : _M_cur(__p) { } void - incr() - { m_cur = m_cur->m_next; } + _M_incr() + { _M_cur = _M_cur->_M_next; } - hash_node* m_cur; + _Hash_node<_Value, __cache>* _M_cur; }; - template + template inline bool - operator==(const node_iterator_base& x, - const node_iterator_base& y) - { return x.m_cur == y.m_cur; } + operator==(const _Node_iterator_base<_Value, __cache>& __x, + const _Node_iterator_base<_Value, __cache>& __y) + { return __x._M_cur == __y._M_cur; } - template + template inline bool - operator!=(const node_iterator_base& x, - const node_iterator_base& y) - { return x.m_cur != y.m_cur; } + operator!=(const _Node_iterator_base<_Value, __cache>& __x, + const _Node_iterator_base<_Value, __cache>& __y) + { return __x._M_cur != __y._M_cur; } - template - struct node_iterator - : public node_iterator_base + template + struct _Node_iterator + : public _Node_iterator_base<_Value, __cache> { - typedef Value value_type; - typedef typename __gnu_cxx::__conditional_type::__type + typedef _Value value_type; + typedef typename + __gnu_cxx::__conditional_type<__constant_iterators, + const _Value*, _Value*>::__type pointer; - typedef typename __gnu_cxx::__conditional_type::__type + typedef typename + __gnu_cxx::__conditional_type<__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(0) { } + _Node_iterator() + : _Node_iterator_base<_Value, __cache>(0) { } explicit - node_iterator(hash_node* p) - : node_iterator_base(p) { } + _Node_iterator(_Hash_node<_Value, __cache>* __p) + : _Node_iterator_base<_Value, __cache>(__p) { } reference operator*() const - { return this->m_cur->m_v; } + { return this->_M_cur->_M_v; } pointer operator->() const - { return &this->m_cur->m_v; } + { return &this->_M_cur->_M_v; } - node_iterator& + _Node_iterator& operator++() { - this->incr(); + this->_M_incr(); return *this; } - node_iterator + _Node_iterator operator++(int) { - node_iterator tmp(*this); - this->incr(); - return tmp; + _Node_iterator __tmp(*this); + this->_M_incr(); + return __tmp; } }; - template - struct node_const_iterator - : public node_iterator_base + template + struct _Node_const_iterator + : public _Node_iterator_base<_Value, __cache> { - typedef Value value_type; - typedef const Value* pointer; - typedef const Value& reference; + 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(0) { } + _Node_const_iterator() + : _Node_iterator_base<_Value, __cache>(0) { } explicit - node_const_iterator(hash_node* p) - : node_iterator_base(p) { } + _Node_const_iterator(_Hash_node<_Value, __cache>* __p) + : _Node_iterator_base<_Value, __cache>(__p) { } - node_const_iterator(const node_iterator& x) - : node_iterator_base(x.m_cur) { } + _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; } + { return this->_M_cur->_M_v; } pointer operator->() const - { return &this->m_cur->m_v; } + { return &this->_M_cur->_M_v; } - node_const_iterator& + _Node_const_iterator& operator++() { - this->incr(); + this->_M_incr(); return *this; } - node_const_iterator + _Node_const_iterator operator++(int) { - node_const_iterator tmp(*this); - this->incr(); - return tmp; + _Node_const_iterator __tmp(*this); + this->_M_incr(); + return __tmp; } }; - template - struct hashtable_iterator_base + template + struct _Hashtable_iterator_base { - hashtable_iterator_base(hash_node* node, - hash_node** bucket) - : m_cur_node(node), m_cur_bucket(bucket) { } + _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, + _Hash_node<_Value, __cache>** __bucket) + : _M_cur_node(__node), _M_cur_bucket(__bucket) { } void - incr() + _M_incr() { - m_cur_node = m_cur_node->m_next; - if (!m_cur_node) - m_incr_bucket(); + _M_cur_node = _M_cur_node->_M_next; + if (!_M_cur_node) + _M_incr_bucket(); } void - m_incr_bucket(); + _M_incr_bucket(); - hash_node* m_cur_node; - hash_node** m_cur_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 + template void - hashtable_iterator_base:: - m_incr_bucket() + _Hashtable_iterator_base<_Value, __cache>:: + _M_incr_bucket() { - ++m_cur_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; + while (!*_M_cur_bucket) + ++_M_cur_bucket; + _M_cur_node = *_M_cur_bucket; } - template + template inline bool - operator==(const hashtable_iterator_base& x, - const hashtable_iterator_base& y) - { return x.m_cur_node == y.m_cur_node; } + 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 + template inline bool - operator!=(const hashtable_iterator_base& x, - const hashtable_iterator_base& y) - { return x.m_cur_node != y.m_cur_node; } + 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 - struct hashtable_iterator - : public hashtable_iterator_base + template + struct _Hashtable_iterator + : public _Hashtable_iterator_base<_Value, __cache> { - typedef Value value_type; - typedef typename __gnu_cxx::__conditional_type::__type + typedef _Value value_type; + typedef typename + __gnu_cxx::__conditional_type<__constant_iterators, + const _Value*, _Value*>::__type pointer; - typedef typename __gnu_cxx::__conditional_type::__type + typedef typename + __gnu_cxx::__conditional_type<__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(0, 0) { } + _Hashtable_iterator() + : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } - hashtable_iterator(hash_node* p, - hash_node** b) - : hashtable_iterator_base(p, b) { } + _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, + _Hash_node<_Value, __cache>** __b) + : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } explicit - hashtable_iterator(hash_node** b) - : hashtable_iterator_base(*b, b) { } + _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) + : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } reference operator*() const - { return this->m_cur_node->m_v; } + { return this->_M_cur_node->_M_v; } pointer operator->() const - { return &this->m_cur_node->m_v; } + { return &this->_M_cur_node->_M_v; } - hashtable_iterator& + _Hashtable_iterator& operator++() { - this->incr(); + this->_M_incr(); return *this; } - hashtable_iterator + _Hashtable_iterator operator++(int) { - hashtable_iterator tmp(*this); - this->incr(); - return tmp; + _Hashtable_iterator __tmp(*this); + this->_M_incr(); + return __tmp; } }; - template - struct hashtable_const_iterator - : public hashtable_iterator_base + template + struct _Hashtable_const_iterator + : public _Hashtable_iterator_base<_Value, __cache> { - typedef Value value_type; - typedef const Value* pointer; - typedef const Value& reference; + 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(0, 0) { } + _Hashtable_const_iterator() + : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } - hashtable_const_iterator(hash_node* p, - hash_node** b) - : hashtable_iterator_base(p, b) { } + _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** b) - : hashtable_iterator_base(*b, b) { } + _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) + : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } - hashtable_const_iterator(const hashtable_iterator& x) - : hashtable_iterator_base(x.m_cur_node, x.m_cur_bucket) { } + _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; } + { return this->_M_cur_node->_M_v; } pointer operator->() const - { return &this->m_cur_node->m_v; } + { return &this->_M_cur_node->_M_v; } - hashtable_const_iterator& + _Hashtable_const_iterator& operator++() { - this->incr(); + this->_M_incr(); return *this; } - hashtable_const_iterator + _Hashtable_const_iterator operator++(int) { - hashtable_const_iterator tmp(*this); - this->incr(); - return tmp; + _Hashtable_const_iterator __tmp(*this); + this->_M_incr(); + return __tmp; } }; - // Many of class template hashtable's template parameters are policy + // Many of class template _Hashtable's template parameters are policy // classes. These are defaults for the policies. // Default range hashing function: use division to fold a large number // into the range [0, N). - struct mod_range_hashing + 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; } + operator()(first_argument_type __num, second_argument_type __den) const + { return __num % __den; } }; // Default ranged hash function H. In principle it should be a @@ -475,103 +486,114 @@ namespace // 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 { }; + 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 + struct _Prime_rehash_policy { - prime_rehash_policy(float z = 1.0); - + _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; + _M_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; + _M_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 + // __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 - need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const; + _M_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; + 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) + _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:: + _Prime_rehash_policy:: max_load_factor() const - { return m_max_load_factor; } + { 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 + _Prime_rehash_policy:: + _M_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::ceil(*p * m_max_load_factor)); - return *p; + const unsigned long* const __last = (_Primes<>::__primes + + _Primes<>::__n_primes); + const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, + __n); + _M_next_resize = static_cast(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 + _Prime_rehash_policy:: + _M_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::ceil(*p * m_max_load_factor)); - return *p; + const unsigned long* const __last = (_Primes<>::__primes + + _Primes<>::__n_primes); + const float __min_bkts = __n / _M_max_load_factor; + const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last, + __min_bkts, _LessThan()); + _M_next_resize = static_cast(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 + // 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. + // _M_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 - prime_rehash_policy:: - need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const + _Prime_rehash_policy:: + _M_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) + 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) + 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::ceil(*p * m_max_load_factor)); - return std::make_pair(true, *p); + __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); + const unsigned long* const __last = (_Primes<>::__primes + + _Primes<>::__n_primes); + const unsigned long* __p = std::lower_bound(_Primes<>::__primes, + __last, __min_bkts, + _LessThan()); + _M_next_resize = + static_cast(std::ceil(*__p * _M_max_load_factor)); + return std::make_pair(true, *__p); } else { - m_next_resize = - static_cast(std::ceil(n_bkt * m_max_load_factor)); + _M_next_resize = + static_cast(std::ceil(__n_bkt + * _M_max_load_factor)); return std::make_pair(false, 0); } } @@ -579,78 +601,82 @@ namespace return std::make_pair(false, 0); } - // Base classes for std::tr1::hashtable. We define these base + // 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 + // 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 + // class template _Map_base. If the hashtable has a value type of the // form pair 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 - struct map_base { }; + template + struct _Map_base { }; - template - struct map_base, false, Hashtable> + template + struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> { - typedef typename Pair::second_type mapped_type; + typedef typename _Pair::second_type mapped_type; }; - template - struct map_base, true, Hashtable> + template + struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> { - typedef typename Pair::second_type mapped_type; + typedef typename _Pair::second_type mapped_type; mapped_type& - operator[](const K& k); + operator[](const _Key& __k); }; - template - typename map_base, true, Hashtable>::mapped_type& - map_base, true, Hashtable>:: - operator[](const K& k) + template + typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, + true, _Hashtable>::mapped_type& + _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: + operator[](const _Key& __k) { - Hashtable* h = static_cast(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; + _Hashtable* __h = static_cast<_Hashtable*>(this); + typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); + std::size_t __n = __h->_M_bucket_index(__k, __code, + __h->_M_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 - struct rehash_base { }; + // class template _Rehash_base. Give hashtable the max_load_factor + // functions iff the rehash policy is _Prime_rehash_policy. + template + struct _Rehash_base { }; - template - struct rehash_base + template + struct _Rehash_base<_Prime_rehash_policy, _Hashtable> { float max_load_factor() const { - const Hashtable* This = static_cast(this); - return This->rehash_policy().max_load_factor(); + const _Hashtable* __this = static_cast(this); + return __this->__rehash_policy().max_load_factor(); } void - max_load_factor(float z) + max_load_factor(float __z) { - Hashtable* This = static_cast(this); - This->rehash_policy(prime_rehash_policy(z)); + _Hashtable* __this = static_cast<_Hashtable*>(this); + __this->__rehash_policy(_Prime_rehash_policy(__z)); } }; - // Class template hash_code_base. Encapsulates two policy issues that + // 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. @@ -662,62 +688,67 @@ namespace // objects here, for convenience. // Primary template: unused except as a hook for specializations. - template - struct hash_code_base; + template + 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 - struct hash_code_base + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Hash, 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) { } + _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, + const _H1&, const _H2&, const _Hash& __h) + : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } - typedef void* hash_code_t; + typedef void* _Hash_code_type; - hash_code_t - m_hash_code(const Key& k) const + _Hash_code_type + _M_hash_code(const _Key& __key) 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); } + _M_bucket_index(const _Key& __k, _Hash_code_type, + std::size_t __n) const + { return _M_ranged_hash(__k, __n); } std::size_t - bucket_index(const hash_node* p, std::size_t N) const - { return m_ranged_hash(m_extract(p->m_v), N); } + _M_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* n) const - { return m_eq(k, m_extract(n->m_v)); } + _M_compare(const _Key& __k, _Hash_code_type, + _Hash_node<_Value, false>* __n) const + { return _M_eq(__k, _M_extract(__n->_M_v)); } void - store_code(hash_node*, hash_code_t) const + _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const { } void - copy_code(hash_node*, const hash_node*) const + _M_copy_code(_Hash_node<_Value, false>*, + const _Hash_node<_Value, false>*) const { } void - m_swap(hash_code_base& x) + _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); + 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; + _ExtractKey _M_extract; + _Equal _M_eq; + _Hash _M_ranged_hash; }; @@ -728,137 +759,146 @@ namespace // Specialization: ranged hash function, cache hash codes. This // combination is meaningless, so we provide only a declaration // and no definition. - template - struct hash_code_base; - + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Hash, 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 - struct hash_code_base + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Default_ranged_hash, false> { - typedef H1 hasher; - + typedef _H1 hasher; + hasher hash_function() const - { return m_h1; } + { 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) { } + _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); } + typedef std::size_t _Hash_code_type; + + _Hash_code_type + _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); } + _M_bucket_index(const _Key&, _Hash_code_type __c, + std::size_t __n) const + { return _M_h2(__c, __n); } std::size_t - bucket_index(const hash_node* p, std::size_t N) const - { return m_h2(m_h1(m_extract(p->m_v)), N); } + _M_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* n) const - { return m_eq(k, m_extract(n->m_v)); } + _M_compare(const _Key& __k, _Hash_code_type, + _Hash_node<_Value, false>* __n) const + { return _M_eq(__k, _M_extract(__n->_M_v)); } void - store_code(hash_node*, hash_code_t) const + _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const { } void - copy_code(hash_node*, const hash_node*) const + _M_copy_code(_Hash_node<_Value, false>*, + const _Hash_node<_Value, false>*) const { } void - m_swap(hash_code_base& x) + _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); + 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; + _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 - struct hash_code_base + template + struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, + _Default_ranged_hash, true> { - typedef H1 hasher; + typedef _H1 hasher; hasher hash_function() const - { return m_h1; } + { 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) { } + _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; + typedef std::size_t _Hash_code_type; - hash_code_t - m_hash_code(const Key& k) const - { return m_h1(k); } + _Hash_code_type + _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); } + _M_bucket_index(const _Key&, _Hash_code_type __c, + std::size_t __n) const + { return _M_h2(__c, __n); } std::size_t - bucket_index(const hash_node* p, std::size_t N) const - { return m_h2(p->hash_code, N); } + _M_bucket_index(const _Hash_node<_Value, true>* __p, + std::size_t __n) const + { return _M_h2(__p->_M_hash_code, __n); } bool - compare(const Key& k, hash_code_t c, hash_node* n) const - { return c == n->hash_code && m_eq(k, m_extract(n->m_v)); } + _M_compare(const _Key& __k, _Hash_code_type __c, + _Hash_node<_Value, true>* __n) const + { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } void - store_code(hash_node* n, hash_code_t c) const - { n->hash_code = c; } + _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const + { __n->_M_hash_code = __c; } void - copy_code(hash_node* to, - const hash_node* from) const - { to->hash_code = from->hash_code; } + _M_copy_code(_Hash_node<_Value, true>* __to, + const _Hash_node<_Value, true>* __from) const + { __to->_M_hash_code = __from->_M_hash_code; } void - m_swap(hash_code_base& x) + _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); + 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; + _ExtractKey _M_extract; + _Equal _M_eq; + _H1 _M_h1; + _H2 _M_h2; }; -} // namespace detail +} // namespace __detail _GLIBCXX_END_NAMESPACE } // namespace std::tr1 diff --git a/libstdc++-v3/include/tr1/unordered_map b/libstdc++-v3/include/tr1/unordered_map index 58aaa08c093..9d0098b590b 100644 --- a/libstdc++-v3/include/tr1/unordered_map +++ b/libstdc++-v3/include/tr1/unordered_map @@ -43,120 +43,124 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // XXX When we get typedef templates these class definitions // will be unnecessary. - template, - class Pred = std::equal_to, - class Alloc = std::allocator >, - bool cache_hash_code = false> + template, + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator >, + bool __cache_hash_code = false> class unordered_map - : public hashtable, Alloc, - std::_Select1st >, Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, false, true> + : public _Hashtable<_Key, std::pair, _Alloc, + std::_Select1st >, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, false, true> { - typedef hashtable, Alloc, - std::_Select1st >, Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, false, true> - Base; + typedef _Hashtable<_Key, std::pair, _Alloc, + std::_Select1st >, _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; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; explicit - unordered_map(size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base(n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), - eql, std::_Select1st >(), a) + unordered_map(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), + __eql, std::_Select1st >(), __a) { } - template - unordered_map(InputIterator f, InputIterator l, - size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (f, l, n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), - eql, std::_Select1st >(), a) + template + unordered_map(_InputIterator __f, _InputIterator __l, + size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), + __eql, std::_Select1st >(), __a) { } }; - template, - class Pred = std::equal_to, - class Alloc = std::allocator >, - bool cache_hash_code = false> + template, + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator >, + bool __cache_hash_code = false> class unordered_multimap - : public hashtable , - Alloc, - std::_Select1st >, Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, false, false> + : public _Hashtable<_Key, std::pair, + _Alloc, + std::_Select1st >, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, false, false> { - typedef hashtable , - Alloc, - std::_Select1st >, Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, false, false> - Base; + typedef _Hashtable<_Key, std::pair, + _Alloc, + std::_Select1st >, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, false, false> + _Base; public: - typedef typename Base::size_type size_type; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; explicit - unordered_multimap(size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), - eql, std::_Select1st >(), a) + unordered_multimap(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), + __eql, std::_Select1st >(), __a) { } - template - unordered_multimap(InputIterator f, InputIterator l, - typename Base::size_type n = 0, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (f, l, n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), - eql, std::_Select1st >(), a) + template + unordered_multimap(_InputIterator __f, _InputIterator __l, + typename _Base::size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), + __eql, std::_Select1st >(), __a) { } }; - template + template inline void - swap(unordered_map& x, - unordered_map& y) - { x.swap(y); } - - template + swap(unordered_map<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __x, + unordered_map<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } + + template inline void - swap(unordered_multimap& x, - unordered_multimap& y) - { x.swap(y); } + swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __x, + unordered_multimap<_Key, _Tp, _Hash, _Pred, + _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } _GLIBCXX_END_NAMESPACE } diff --git a/libstdc++-v3/include/tr1/unordered_set b/libstdc++-v3/include/tr1/unordered_set index b537d74997e..227dae54968 100644 --- a/libstdc++-v3/include/tr1/unordered_set +++ b/libstdc++-v3/include/tr1/unordered_set @@ -43,114 +43,122 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) // XXX When we get typedef templates these class definitions // will be unnecessary. - template, - class Pred = std::equal_to, - class Alloc = std::allocator, - bool cache_hash_code = false> + template, + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value>, + bool __cache_hash_code = false> class unordered_set - : public hashtable, Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, true, true> + : public _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, true> { - typedef hashtable, Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, true, true> - Base; + typedef _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, true> + _Base; public: - typedef typename Base::size_type size_type; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; explicit - unordered_set(size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base(n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), eql, std::_Identity(), a) + unordered_set(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<_Value>(), __a) { } - template - unordered_set(InputIterator f, InputIterator l, - size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base(f, l, n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), eql, std::_Identity(), a) + template + unordered_set(_InputIterator __f, _InputIterator __l, + size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<_Value>(), __a) { } }; - template, - class Pred = std::equal_to, - class Alloc = std::allocator, - bool cache_hash_code = false> + template, + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value>, + bool __cache_hash_code = false> class unordered_multiset - : public hashtable , Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, true, false> + : public _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, false> { - typedef hashtable, Pred, - Hash, detail::mod_range_hashing, - detail::default_ranged_hash, - detail::prime_rehash_policy, - cache_hash_code, true, false> - Base; + typedef _Hashtable<_Value, _Value, _Alloc, + std::_Identity<_Value>, _Pred, + _Hash, __detail::_Mod_range_hashing, + __detail::_Default_ranged_hash, + __detail::_Prime_rehash_policy, + __cache_hash_code, true, false> + _Base; public: - typedef typename Base::size_type size_type; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; + typedef typename _Base::size_type size_type; + typedef typename _Base::hasher hasher; + typedef typename _Base::key_equal key_equal; + typedef typename _Base::allocator_type allocator_type; explicit - unordered_multiset(size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base(n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), eql, std::_Identity(), a) + unordered_multiset(size_type __n = 10, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<_Value>(), __a) { } - template - unordered_multiset(InputIterator f, InputIterator l, - typename Base::size_type n = 0, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base(f, l, n, hf, detail::mod_range_hashing(), - detail::default_ranged_hash(), eql, std::_Identity(), a) + template + unordered_multiset(_InputIterator __f, _InputIterator __l, + typename _Base::size_type __n = 0, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal(), + const allocator_type& __a = allocator_type()) + : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(), + __detail::_Default_ranged_hash(), __eql, + std::_Identity<_Value>(), __a) { } }; - template + template inline void - swap (unordered_set& x, - unordered_set& y) - { x.swap(y); } - - template + swap (unordered_set<_Value, _Hash, _Pred, + _Alloc, __cache_hash_code>& __x, + unordered_set<_Value, _Hash, _Pred, + _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } + + template inline void - swap(unordered_multiset& x, - unordered_multiset& y) - { x.swap(y); } + swap(unordered_multiset<_Value, _Hash, _Pred, + _Alloc, __cache_hash_code>& __x, + unordered_multiset<_Value, _Hash, _Pred, + _Alloc, __cache_hash_code>& __y) + { __x.swap(__y); } _GLIBCXX_END_NAMESPACE } -- 2.11.0