diff options
Diffstat (limited to 'system/include/libcxx/unordered_map')
| -rw-r--r-- | system/include/libcxx/unordered_map | 475 |
1 files changed, 314 insertions, 161 deletions
diff --git a/system/include/libcxx/unordered_map b/system/include/libcxx/unordered_map index 235b2eab..eebf2f5e 100644 --- a/system/include/libcxx/unordered_map +++ b/system/include/libcxx/unordered_map @@ -325,7 +325,7 @@ template <class Key, class T, class Hash, class Pred, class Alloc> _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value +template <class _Key, class _Cp, class _Hash, bool = is_empty<_Hash>::value #if __has_feature(is_final) && !__is_final(_Hash) #endif @@ -333,8 +333,6 @@ template <class _Key, class _Tp, class _Hash, bool = is_empty<_Hash>::value class __unordered_map_hasher : private _Hash { - typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; - typedef pair<const _Key, _Tp> _Cp; public: _LIBCPP_INLINE_VISIBILITY __unordered_map_hasher() @@ -347,23 +345,18 @@ public: _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const _NOEXCEPT {return *this;} _LIBCPP_INLINE_VISIBILITY - size_t operator()(const _Pp& __x) const - {return static_cast<const _Hash&>(*this)(__x.first);} - _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Cp& __x) const - {return static_cast<const _Hash&>(*this)(__x.first);} + {return static_cast<const _Hash&>(*this)(__x.__cc.first);} _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Key& __x) const {return static_cast<const _Hash&>(*this)(__x);} }; -template <class _Key, class _Tp, class _Hash> -class __unordered_map_hasher<_Key, _Tp, _Hash, false> +template <class _Key, class _Cp, class _Hash> +class __unordered_map_hasher<_Key, _Cp, _Hash, false> { _Hash __hash_; - typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; - typedef pair<const _Key, _Tp> _Cp; public: _LIBCPP_INLINE_VISIBILITY __unordered_map_hasher() @@ -376,17 +369,14 @@ public: _LIBCPP_INLINE_VISIBILITY const _Hash& hash_function() const _NOEXCEPT {return __hash_;} _LIBCPP_INLINE_VISIBILITY - size_t operator()(const _Pp& __x) const - {return __hash_(__x.first);} - _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Cp& __x) const - {return __hash_(__x.first);} + {return __hash_(__x.__cc.first);} _LIBCPP_INLINE_VISIBILITY size_t operator()(const _Key& __x) const {return __hash_(__x);} }; -template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value +template <class _Key, class _Cp, class _Pred, bool = is_empty<_Pred>::value #if __has_feature(is_final) && !__is_final(_Pred) #endif @@ -394,8 +384,6 @@ template <class _Key, class _Tp, class _Pred, bool = is_empty<_Pred>::value class __unordered_map_equal : private _Pred { - typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; - typedef pair<const _Key, _Tp> _Cp; public: _LIBCPP_INLINE_VISIBILITY __unordered_map_equal() @@ -408,41 +396,21 @@ public: _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const _NOEXCEPT {return *this;} _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Pp& __x, const _Pp& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Pp& __x, const _Cp& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Pp& __x, const _Key& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Cp& __x, const _Pp& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Cp& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y.first);} + {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y.__cc.first);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Key& __y) const - {return static_cast<const _Pred&>(*this)(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _Pp& __y) const - {return static_cast<const _Pred&>(*this)(__x, __y.first);} + {return static_cast<const _Pred&>(*this)(__x.__cc.first, __y);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Key& __x, const _Cp& __y) const - {return static_cast<const _Pred&>(*this)(__x, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _Key& __y) const - {return static_cast<const _Pred&>(*this)(__x, __y);} + {return static_cast<const _Pred&>(*this)(__x, __y.__cc.first);} }; -template <class _Key, class _Tp, class _Pred> -class __unordered_map_equal<_Key, _Tp, _Pred, false> +template <class _Key, class _Cp, class _Pred> +class __unordered_map_equal<_Key, _Cp, _Pred, false> { _Pred __pred_; - typedef pair<typename remove_const<_Key>::type, _Tp> _Pp; - typedef pair<const _Key, _Tp> _Cp; public: _LIBCPP_INLINE_VISIBILITY __unordered_map_equal() @@ -455,32 +423,14 @@ public: _LIBCPP_INLINE_VISIBILITY const _Pred& key_eq() const _NOEXCEPT {return __pred_;} _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Pp& __x, const _Pp& __y) const - {return __pred_(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Pp& __x, const _Cp& __y) const - {return __pred_(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Pp& __x, const _Key& __y) const - {return __pred_(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Cp& __x, const _Pp& __y) const - {return __pred_(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Cp& __y) const - {return __pred_(__x.first, __y.first);} + {return __pred_(__x.__cc.first, __y.__cc.first);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Cp& __x, const _Key& __y) const - {return __pred_(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _Pp& __y) const - {return __pred_(__x, __y.first);} + {return __pred_(__x.__cc.first, __y);} _LIBCPP_INLINE_VISIBILITY bool operator()(const _Key& __x, const _Cp& __y) const - {return __pred_(__x, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _Key& __y) const - {return __pred_(__x, __y);} + {return __pred_(__x, __y.__cc.first);} }; template <class _Alloc> @@ -492,8 +442,8 @@ class __hash_map_node_destructor public: typedef typename __alloc_traits::pointer pointer; private: - typedef typename value_type::first_type first_type; - typedef typename value_type::second_type second_type; + typedef typename value_type::value_type::first_type first_type; + typedef typename value_type::value_type::second_type second_type; allocator_type& __na_; @@ -535,9 +485,9 @@ public: void operator()(pointer __p) _NOEXCEPT { if (__second_constructed) - __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second)); + __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second)); if (__first_constructed) - __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first)); + __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first)); if (__p) __alloc_traits::deallocate(__na_, __p, 1); } @@ -549,8 +499,8 @@ class _LIBCPP_TYPE_VIS __hash_map_iterator _HashIterator __i_; typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; - typedef const typename _HashIterator::value_type::first_type key_type; - typedef typename _HashIterator::value_type::second_type mapped_type; + typedef const typename _HashIterator::value_type::value_type::first_type key_type; + typedef typename _HashIterator::value_type::value_type::second_type mapped_type; public: typedef forward_iterator_tag iterator_category; typedef pair<key_type, mapped_type> value_type; @@ -571,9 +521,9 @@ public: __hash_map_iterator(_HashIterator __i) _NOEXCEPT : __i_(__i) {} _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return *operator->();} + reference operator*() const {return __i_->__cc;} _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return (pointer)__i_.operator->();} + pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} _LIBCPP_INLINE_VISIBILITY __hash_map_iterator& operator++() {++__i_; return *this;} @@ -605,8 +555,8 @@ class _LIBCPP_TYPE_VIS __hash_map_const_iterator _HashIterator __i_; typedef pointer_traits<typename _HashIterator::pointer> __pointer_traits; - typedef const typename _HashIterator::value_type::first_type key_type; - typedef typename _HashIterator::value_type::second_type mapped_type; + typedef const typename _HashIterator::value_type::value_type::first_type key_type; + typedef typename _HashIterator::value_type::value_type::second_type mapped_type; public: typedef forward_iterator_tag iterator_category; typedef pair<key_type, mapped_type> value_type; @@ -632,9 +582,9 @@ public: : __i_(__i.__i_) {} _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return *operator->();} + reference operator*() const {return __i_->__cc;} _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return (pointer)__i_.operator->();} + pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);} _LIBCPP_INLINE_VISIBILITY __hash_map_const_iterator& operator++() {++__i_; return *this;} @@ -671,13 +621,58 @@ public: typedef _Pred key_equal; typedef _Alloc allocator_type; typedef pair<const key_type, mapped_type> value_type; + typedef pair<key_type, mapped_type> __nc_value_type; typedef value_type& reference; typedef const value_type& const_reference; + static_assert((is_same<value_type, typename allocator_type::value_type>::value), + "Invalid allocator::value_type"); private: - typedef pair<key_type, mapped_type> __value_type; - typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher; - typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal; +#if __cplusplus >= 201103L + union __value_type + { + typedef typename unordered_map::value_type value_type; + typedef typename unordered_map::__nc_value_type __nc_value_type; + value_type __cc; + __nc_value_type __nc; + + template <class ..._Args> + __value_type(_Args&& ...__args) + : __cc(std::forward<_Args>(__args)...) {} + + __value_type(const __value_type& __v) + : __cc(std::move(__v.__cc)) {} + + __value_type(__value_type&& __v) + : __nc(std::move(__v.__nc)) {} + + __value_type& operator=(const __value_type& __v) + {__nc = __v.__cc; return *this;} + + __value_type& operator=(__value_type&& __v) + {__nc = std::move(__v.__nc); return *this;} + + ~__value_type() {__cc.~value_type();} + }; +#else + struct __value_type + { + typedef typename unordered_map::value_type value_type; + value_type __cc; + + __value_type() {} + + template <class _A0> + __value_type(const _A0& __a0) + : __cc(__a0) {} + + template <class _A0, class _A1> + __value_type(const _A0& __a0, const _A1& __a1) + : __cc(__a0, __a1) {} + }; +#endif + typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; + typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; typedef typename allocator_traits<allocator_type>::template #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES rebind_alloc<__value_type> @@ -713,7 +708,11 @@ public: _LIBCPP_INLINE_VISIBILITY unordered_map() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) - {} // = default; + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif + } explicit unordered_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); unordered_map(size_type __n, const hasher& __hf, @@ -750,7 +749,16 @@ public: _LIBCPP_INLINE_VISIBILITY unordered_map& operator=(const unordered_map& __u) { +#if __cplusplus >= 201103L __table_ = __u.__table_; +#else + __table_.clear(); + __table_.hash_function() = __u.__table_.hash_function(); + __table_.key_eq() = __u.__table_.key_eq(); + __table_.max_load_factor() = __u.__table_.max_load_factor(); + __table_.__copy_assign_alloc(__u.__table_); + insert(__u.begin(), __u.end()); +#endif return *this; } #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES @@ -793,8 +801,18 @@ public: template <class... _Args> _LIBCPP_INLINE_VISIBILITY +#if _LIBCPP_DEBUG_LEVEL >= 2 + iterator emplace_hint(const_iterator __p, _Args&&... __args) + { + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::emplace_hint(const_iterator, args...) called with an iterator not" + " referring to this unordered_map"); + return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; + } +#else iterator emplace_hint(const_iterator, _Args&&... __args) {return emplace(_VSTD::forward<_Args>(__args)...).first;} +#endif #endif // _LIBCPP_HAS_NO_VARIADICS #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES _LIBCPP_INLINE_VISIBILITY @@ -808,14 +826,34 @@ public: {return __table_.__insert_unique(_VSTD::forward<_Pp>(__x));} #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES _LIBCPP_INLINE_VISIBILITY +#if _LIBCPP_DEBUG_LEVEL >= 2 + iterator insert(const_iterator __p, const value_type& __x) + { + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::insert(const_iterator, const value_type&) called with an iterator not" + " referring to this unordered_map"); + return insert(__x).first; + } +#else iterator insert(const_iterator, const value_type& __x) {return insert(__x).first;} +#endif #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Pp, class = typename enable_if<is_constructible<value_type, _Pp>::value>::type> _LIBCPP_INLINE_VISIBILITY +#if _LIBCPP_DEBUG_LEVEL >= 2 + iterator insert(const_iterator __p, _Pp&& __x) + { + _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, + "unordered_map::insert(const_iterator, value_type&&) called with an iterator not" + " referring to this unordered_map"); + return insert(_VSTD::forward<_Pp>(__x)).first; + } +#else iterator insert(const_iterator, _Pp&& __x) {return insert(_VSTD::forward<_Pp>(__x)).first;} +#endif #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _InputIterator> void insert(_InputIterator __first, _InputIterator __last); @@ -903,30 +941,32 @@ public: _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) {__table_.reserve(__n);} +#if _LIBCPP_DEBUG_LEVEL >= 2 + + bool __dereferenceable(const const_iterator* __i) const + {return __table_.__dereferenceable(&__i->__i_);} + bool __decrementable(const const_iterator* __i) const + {return __table_.__decrementable(&__i->__i_);} + bool __addable(const const_iterator* __i, ptrdiff_t __n) const + {return __table_.__addable(&__i->__i_, __n);} + bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const + {return __table_.__addable(&__i->__i_, __n);} + +#endif // _LIBCPP_DEBUG_LEVEL >= 2 + private: #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES __node_holder __construct_node(); template <class _A0> - typename enable_if - < - is_constructible<value_type, _A0>::value, - __node_holder - >::type - __construct_node(_A0&& __a0); - template <class _A0> - typename enable_if - < - is_constructible<key_type, _A0>::value, - __node_holder - >::type + __node_holder __construct_node(_A0&& __a0); + __node_holder __construct_node_with_key(key_type&& __k); #ifndef _LIBCPP_HAS_NO_VARIADICS template <class _A0, class _A1, class ..._Args> __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args); #endif // _LIBCPP_HAS_NO_VARIADICS -#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(const key_type& __k); -#endif +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + __node_holder __construct_node_with_key(const key_type& __k); }; template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -934,6 +974,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( size_type __n, const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); } @@ -943,6 +986,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const allocator_type& __a) : __table_(__hf, __eql, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); } @@ -952,6 +998,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const allocator_type& __a) : __table_(__a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -959,6 +1008,9 @@ template <class _InputIterator> unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( _InputIterator __first, _InputIterator __last) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif insert(__first, __last); } @@ -969,6 +1021,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__first, __last); } @@ -980,6 +1035,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const hasher& __hf, const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__first, __last); } @@ -989,6 +1047,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const unordered_map& __u) : __table_(__u.__table_) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -998,6 +1059,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const unordered_map& __u, const allocator_type& __a) : __table_(__u.__table_, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -1011,6 +1075,10 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) : __table_(_VSTD::move(__u.__table_)) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); + __get_db()->swap(this, &__u); +#endif } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1018,6 +1086,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( unordered_map&& __u, const allocator_type& __a) : __table_(_VSTD::move(__u.__table_), __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif if (__a != __u.get_allocator()) { iterator __i = __u.begin(); @@ -1026,6 +1097,10 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) ); } +#if _LIBCPP_DEBUG_LEVEL >= 2 + else + __get_db()->swap(this, &__u); +#endif } #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES @@ -1036,6 +1111,9 @@ template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( initializer_list<value_type> __il) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif insert(__il.begin(), __il.end()); } @@ -1045,6 +1123,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const key_equal& __eql) : __table_(__hf, __eql) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__il.begin(), __il.end()); } @@ -1055,6 +1136,9 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_map( const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__il.begin(), __il.end()); } @@ -1105,11 +1189,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _A0> -typename enable_if -< - is_constructible<pair<const _Key, _Tp>, _A0>::value, - typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder ->::type +typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) { __node_allocator& __na = __table_.__node_alloc(); @@ -1122,22 +1202,16 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class _A0> -typename enable_if -< - is_constructible<_Key, _A0>::value, - typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder ->::type -unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) +typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder +unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(key_type&& __k) { __node_allocator& __na = __table_.__node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), - _VSTD::forward<_A0>(__a0)); + __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k)); __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); + __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); __h.get_deleter().__second_constructed = true; - return __h; + return _VSTD::move(__h); } #ifndef _LIBCPP_HAS_NO_VARIADICS @@ -1172,23 +1246,21 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::emplace(_Args&&... __args) } #endif // _LIBCPP_HAS_NO_VARIADICS -#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> typename unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder -unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) +unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node_with_key(const key_type& __k) { __node_allocator& __na = __table_.__node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k); + __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k); __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); + __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second)); __h.get_deleter().__second_constructed = true; return _VSTD::move(__h); } -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _InputIterator> inline _LIBCPP_INLINE_VISIBILITY @@ -1207,7 +1279,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](const key_type& __k) iterator __i = find(__k); if (__i != end()) return __i->second; - __node_holder __h = __construct_node(__k); + __node_holder __h = __construct_node_with_key(__k); pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); __h.release(); return __r.first->second; @@ -1222,7 +1294,7 @@ unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](key_type&& __k) iterator __i = find(__k); if (__i != end()) return __i->second; - __node_holder __h = __construct_node(_VSTD::move(__k)); + __node_holder __h = __construct_node_with_key(_VSTD::move(__k)); pair<iterator, bool> __r = __table_.__node_insert_unique(__h.get()); __h.release(); return __r.first->second; @@ -1304,13 +1376,58 @@ public: typedef _Pred key_equal; typedef _Alloc allocator_type; typedef pair<const key_type, mapped_type> value_type; + typedef pair<key_type, mapped_type> __nc_value_type; typedef value_type& reference; typedef const value_type& const_reference; + static_assert((is_same<value_type, typename allocator_type::value_type>::value), + "Invalid allocator::value_type"); private: - typedef pair<key_type, mapped_type> __value_type; - typedef __unordered_map_hasher<key_type, mapped_type, hasher> __hasher; - typedef __unordered_map_equal<key_type, mapped_type, key_equal> __key_equal; +#if __cplusplus >= 201103L + union __value_type + { + typedef typename unordered_multimap::value_type value_type; + typedef typename unordered_multimap::__nc_value_type __nc_value_type; + value_type __cc; + __nc_value_type __nc; + + template <class ..._Args> + __value_type(_Args&& ...__args) + : __cc(std::forward<_Args>(__args)...) {} + + __value_type(const __value_type& __v) + : __cc(std::move(__v.__cc)) {} + + __value_type(__value_type&& __v) + : __nc(std::move(__v.__nc)) {} + + __value_type& operator=(const __value_type& __v) + {__nc = __v.__cc; return *this;} + + __value_type& operator=(__value_type&& __v) + {__nc = std::move(__v.__nc); return *this;} + + ~__value_type() {__cc.~value_type();} + }; +#else + struct __value_type + { + typedef typename unordered_multimap::value_type value_type; + value_type __cc; + + __value_type() {} + + template <class _A0> + __value_type(const _A0& __a0) + : __cc(__a0) {} + + template <class _A0, class _A1> + __value_type(const _A0& __a0, const _A1& __a1) + : __cc(__a0, __a1) {} + }; +#endif + typedef __unordered_map_hasher<key_type, __value_type, hasher> __hasher; + typedef __unordered_map_equal<key_type, __value_type, key_equal> __key_equal; typedef typename allocator_traits<allocator_type>::template #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES rebind_alloc<__value_type> @@ -1344,7 +1461,11 @@ public: _LIBCPP_INLINE_VISIBILITY unordered_multimap() _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) - {} // = default; + { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif + } explicit unordered_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); unordered_multimap(size_type __n, const hasher& __hf, @@ -1382,7 +1503,16 @@ public: _LIBCPP_INLINE_VISIBILITY unordered_multimap& operator=(const unordered_multimap& __u) { +#if __cplusplus >= 201103L __table_ = __u.__table_; +#else + __table_.clear(); + __table_.hash_function() = __u.__table_.hash_function(); + __table_.key_eq() = __u.__table_.key_eq(); + __table_.max_load_factor() = __u.__table_.max_load_factor(); + __table_.__copy_assign_alloc(__u.__table_); + insert(__u.begin(), __u.end()); +#endif return *this; } #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES @@ -1525,22 +1655,24 @@ public: _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) {__table_.reserve(__n);} +#if _LIBCPP_DEBUG_LEVEL >= 2 + + bool __dereferenceable(const const_iterator* __i) const + {return __table_.__dereferenceable(&__i->__i_);} + bool __decrementable(const const_iterator* __i) const + {return __table_.__decrementable(&__i->__i_);} + bool __addable(const const_iterator* __i, ptrdiff_t __n) const + {return __table_.__addable(&__i->__i_, __n);} + bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const + {return __table_.__addable(&__i->__i_, __n);} + +#endif // _LIBCPP_DEBUG_LEVEL >= 2 + private: #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES __node_holder __construct_node(); template <class _A0> - typename enable_if - < - is_constructible<value_type, _A0>::value, - __node_holder - >::type - __construct_node(_A0&& __a0); - template <class _A0> - typename enable_if - < - is_constructible<key_type, _A0>::value, - __node_holder - >::type + __node_holder __construct_node(_A0&& __a0); #ifndef _LIBCPP_HAS_NO_VARIADICS template <class _A0, class _A1, class ..._Args> @@ -1554,6 +1686,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( size_type __n, const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); } @@ -1563,6 +1698,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const allocator_type& __a) : __table_(__hf, __eql, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); } @@ -1571,6 +1709,9 @@ template <class _InputIterator> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( _InputIterator __first, _InputIterator __last) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif insert(__first, __last); } @@ -1581,6 +1722,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const hasher& __hf, const key_equal& __eql) : __table_(__hf, __eql) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__first, __last); } @@ -1592,6 +1736,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const hasher& __hf, const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__first, __last); } @@ -1602,6 +1749,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const allocator_type& __a) : __table_(__a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1609,6 +1759,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const unordered_multimap& __u) : __table_(__u.__table_) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -1618,6 +1771,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const unordered_multimap& __u, const allocator_type& __a) : __table_(__u.__table_, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__u.bucket_count()); insert(__u.begin(), __u.end()); } @@ -1631,6 +1787,10 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) : __table_(_VSTD::move(__u.__table_)) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); + __get_db()->swap(this, &__u); +#endif } template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> @@ -1638,16 +1798,23 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( unordered_multimap&& __u, const allocator_type& __a) : __table_(_VSTD::move(__u.__table_), __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif if (__a != __u.get_allocator()) { iterator __i = __u.begin(); while (__u.size() != 0) -{ + { __table_.__insert_multi( _VSTD::move(__u.__table_.remove((__i++).__i_)->__value_) ); -} + } } +#if _LIBCPP_DEBUG_LEVEL >= 2 + else + __get_db()->swap(this, &__u); +#endif } #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES @@ -1658,6 +1825,9 @@ template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( initializer_list<value_type> __il) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif insert(__il.begin(), __il.end()); } @@ -1667,6 +1837,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const key_equal& __eql) : __table_(__hf, __eql) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__il.begin(), __il.end()); } @@ -1677,6 +1850,9 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::unordered_multimap( const key_equal& __eql, const allocator_type& __a) : __table_(__hf, __eql, __a) { +#if _LIBCPP_DEBUG_LEVEL >= 2 + __get_db()->__insert_c(this); +#endif __table_.rehash(__n); insert(__il.begin(), __il.end()); } @@ -1727,11 +1903,7 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node() template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> template <class _A0> -typename enable_if -< - is_constructible<pair<const _Key, _Tp>, _A0>::value, - typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder ->::type +typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) { __node_allocator& __na = __table_.__node_alloc(); @@ -1743,25 +1915,6 @@ unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0 return __h; } -template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> -template <class _A0> -typename enable_if -< - is_constructible<_Key, _A0>::value, - typename unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder ->::type -unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(_A0&& __a0) -{ - __node_allocator& __na = __table_.__node_alloc(); - __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), - _VSTD::forward<_A0>(__a0)); - __h.get_deleter().__first_constructed = true; - __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second)); - __h.get_deleter().__second_constructed = true; - return __h; -} - #ifndef _LIBCPP_HAS_NO_VARIADICS template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> |