diff options
Diffstat (limited to 'tests/libcxx/include/__hash_table')
| -rw-r--r-- | tests/libcxx/include/__hash_table | 1819 |
1 files changed, 0 insertions, 1819 deletions
diff --git a/tests/libcxx/include/__hash_table b/tests/libcxx/include/__hash_table deleted file mode 100644 index ae9ee1c5..00000000 --- a/tests/libcxx/include/__hash_table +++ /dev/null @@ -1,1819 +0,0 @@ -// -*- C++ -*- -//===----------------------------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is dual licensed under the MIT and the University of Illinois Open -// Source Licenses. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP__HASH_TABLE -#define _LIBCPP__HASH_TABLE - -#include <__config> -#include <initializer_list> -#include <memory> -#include <iterator> -#include <algorithm> -#include <cmath> - -#pragma GCC system_header - -_LIBCPP_BEGIN_NAMESPACE_STD - -_LIBCPP_VISIBLE -size_t __next_prime(size_t); - -template <class _NodePtr> -struct __hash_node_base -{ - typedef __hash_node_base __first_node; - typedef _NodePtr pointer; - - pointer __next_; - - _LIBCPP_INLINE_VISIBILITY __hash_node_base() : __next_(nullptr) {} -}; - -template <class _Tp, class _VoidPtr> -struct __hash_node - : public __hash_node_base - < - typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__hash_node<_Tp, _VoidPtr> > -#else - rebind<__hash_node<_Tp, _VoidPtr> >::other -#endif - > -{ - typedef _Tp value_type; - - size_t __hash_; - value_type __value_; -}; - -template <class, class, class, class> class __hash_table; -template <class> class __hash_const_iterator; -template <class> class __hash_map_iterator; -template <class> class __hash_map_const_iterator; -template <class, class, class, class, class> class _LIBCPP_VISIBLE unordered_map; - -template <class _NodePtr> -class _LIBCPP_VISIBLE __hash_iterator -{ - typedef _NodePtr __node_pointer; - - __node_pointer __node_; - -public: - typedef forward_iterator_tag iterator_category; - typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; - typedef typename pointer_traits<__node_pointer>::difference_type difference_type; - typedef value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<value_type> -#else - rebind<value_type>::other -#endif - pointer; - - _LIBCPP_INLINE_VISIBILITY __hash_iterator() {} - - _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __node_->__value_;} - _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return addressof(__node_->__value_);} - - _LIBCPP_INLINE_VISIBILITY - __hash_iterator& operator++() - { - __node_ = __node_->__next_; - return *this; - } - - _LIBCPP_INLINE_VISIBILITY - __hash_iterator operator++(int) - { - __hash_iterator __t(*this); - ++(*this); - return __t; - } - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) - {return __x.__node_ == __y.__node_;} - friend _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) - {return __x.__node_ != __y.__node_;} - -private: - _LIBCPP_INLINE_VISIBILITY - __hash_iterator(__node_pointer __node) - : __node_(__node) - {} - - template <class, class, class, class> friend class __hash_table; - template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; - template <class> friend class _LIBCPP_VISIBLE __hash_map_iterator; - template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; - template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; -}; - -template <class _ConstNodePtr> -class _LIBCPP_VISIBLE __hash_const_iterator -{ - typedef _ConstNodePtr __node_pointer; - - __node_pointer __node_; - - typedef typename remove_const< - typename pointer_traits<__node_pointer>::element_type - >::type __node; - -public: - typedef forward_iterator_tag iterator_category; - typedef typename __node::value_type value_type; - typedef typename pointer_traits<__node_pointer>::difference_type difference_type; - typedef const value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const value_type> -#else - rebind<const value_type>::other -#endif - pointer; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__node> -#else - rebind<__node>::other -#endif - __non_const_node_pointer; - typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; - - _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() {} - _LIBCPP_INLINE_VISIBILITY - __hash_const_iterator(const __non_const_iterator& __x) - : __node_(__x.__node_) - {} - - _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __node_->__value_;} - _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return addressof(__node_->__value_);} - - _LIBCPP_INLINE_VISIBILITY - __hash_const_iterator& operator++() - { - __node_ = __node_->__next_; - return *this; - } - - _LIBCPP_INLINE_VISIBILITY - __hash_const_iterator operator++(int) - { - __hash_const_iterator __t(*this); - ++(*this); - return __t; - } - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) - {return __x.__node_ == __y.__node_;} - friend _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) - {return __x.__node_ != __y.__node_;} - -private: - _LIBCPP_INLINE_VISIBILITY - __hash_const_iterator(__node_pointer __node) - : __node_(__node) - {} - - template <class, class, class, class> friend class __hash_table; - template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; - template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; - template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; -}; - -template <class> class _LIBCPP_VISIBLE __hash_const_local_iterator; - -template <class _NodePtr> -class _LIBCPP_VISIBLE __hash_local_iterator -{ - typedef _NodePtr __node_pointer; - - __node_pointer __node_; - size_t __bucket_; - size_t __bucket_count_; - - typedef pointer_traits<__node_pointer> __pointer_traits; -public: - typedef forward_iterator_tag iterator_category; - typedef typename __pointer_traits::element_type::value_type value_type; - typedef typename __pointer_traits::difference_type difference_type; - typedef value_type& reference; - typedef typename __pointer_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<value_type> -#else - rebind<value_type>::other -#endif - pointer; - - _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() {} - - _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __node_->__value_;} - _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return &__node_->__value_;} - - _LIBCPP_INLINE_VISIBILITY - __hash_local_iterator& operator++() - { - __node_ = __node_->__next_; - if (__node_ != nullptr && __node_->__hash_ % __bucket_count_ != __bucket_) - __node_ = nullptr; - return *this; - } - - _LIBCPP_INLINE_VISIBILITY - __hash_local_iterator operator++(int) - { - __hash_local_iterator __t(*this); - ++(*this); - return __t; - } - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) - {return __x.__node_ == __y.__node_;} - friend _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) - {return __x.__node_ != __y.__node_;} - -private: - _LIBCPP_INLINE_VISIBILITY - __hash_local_iterator(__node_pointer __node, size_t __bucket, - size_t __bucket_count) - : __node_(__node), - __bucket_(__bucket), - __bucket_count_(__bucket_count) - { - if (__node_ != nullptr) - __node_ = __node_->__next_; - } - - template <class, class, class, class> friend class __hash_table; - template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; - template <class> friend class _LIBCPP_VISIBLE __hash_map_iterator; -}; - -template <class _ConstNodePtr> -class _LIBCPP_VISIBLE __hash_const_local_iterator -{ - typedef _ConstNodePtr __node_pointer; - - __node_pointer __node_; - size_t __bucket_; - size_t __bucket_count_; - - typedef pointer_traits<__node_pointer> __pointer_traits; - typedef typename __pointer_traits::element_type __node; - typedef typename remove_const<__node>::type __non_const_node; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__non_const_node> -#else - rebind<__non_const_node>::other -#endif - __non_const_node_pointer; - typedef __hash_local_iterator<__non_const_node_pointer> - __non_const_iterator; -public: - typedef forward_iterator_tag iterator_category; - typedef typename remove_const< - typename __pointer_traits::element_type::value_type - >::type value_type; - typedef typename __pointer_traits::difference_type difference_type; - typedef const value_type& reference; - typedef typename __pointer_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const value_type> -#else - rebind<const value_type>::other -#endif - pointer; - - _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() {} - _LIBCPP_INLINE_VISIBILITY - __hash_const_local_iterator(const __non_const_iterator& __x) - : __node_(__x.__node_), - __bucket_(__x.__bucket_), - __bucket_count_(__x.__bucket_count_) - {} - - _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return __node_->__value_;} - _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return &__node_->__value_;} - - _LIBCPP_INLINE_VISIBILITY - __hash_const_local_iterator& operator++() - { - __node_ = __node_->__next_; - if (__node_ != nullptr && __node_->__hash_ % __bucket_count_ != __bucket_) - __node_ = nullptr; - return *this; - } - - _LIBCPP_INLINE_VISIBILITY - __hash_const_local_iterator operator++(int) - { - __hash_const_local_iterator __t(*this); - ++(*this); - return __t; - } - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) - {return __x.__node_ == __y.__node_;} - friend _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) - {return __x.__node_ != __y.__node_;} - -private: - _LIBCPP_INLINE_VISIBILITY - __hash_const_local_iterator(__node_pointer __node, size_t __bucket, - size_t __bucket_count) - : __node_(__node), - __bucket_(__bucket), - __bucket_count_(__bucket_count) - { - if (__node_ != nullptr) - __node_ = __node_->__next_; - } - - template <class, class, class, class> friend class __hash_table; - template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; -}; - -template <class _Alloc> -class __bucket_list_deallocator -{ - typedef _Alloc allocator_type; - typedef allocator_traits<allocator_type> __alloc_traits; - typedef typename __alloc_traits::size_type size_type; - - __compressed_pair<size_type, allocator_type> __data_; -public: - typedef typename __alloc_traits::pointer pointer; - - _LIBCPP_INLINE_VISIBILITY - __bucket_list_deallocator() - : __data_(0) {} - - _LIBCPP_INLINE_VISIBILITY - __bucket_list_deallocator(const allocator_type& __a, size_type __size) - : __data_(__size, __a) {} - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - - _LIBCPP_INLINE_VISIBILITY - __bucket_list_deallocator(__bucket_list_deallocator&& __x) - : __data_(_STD::move(__x.__data_)) - { - __x.size() = 0; - } - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - _LIBCPP_INLINE_VISIBILITY size_type& size() {return __data_.first();} - _LIBCPP_INLINE_VISIBILITY size_type size() const {return __data_.first();} - - _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __data_.second();} - _LIBCPP_INLINE_VISIBILITY const allocator_type& __alloc() const {return __data_.second();} - - _LIBCPP_INLINE_VISIBILITY - void operator()(pointer __p) - { - __alloc_traits::deallocate(__alloc(), __p, size()); - } -}; - -template <class> class __hash_map_node_destructor; - -template <class _Alloc> -class __hash_node_destructor -{ - typedef _Alloc allocator_type; - typedef allocator_traits<allocator_type> __alloc_traits; - typedef typename __alloc_traits::value_type::value_type value_type; -public: - typedef typename __alloc_traits::pointer pointer; -private: - - allocator_type& __na_; - - __hash_node_destructor& operator=(const __hash_node_destructor&); - -public: - bool __value_constructed; - - _LIBCPP_INLINE_VISIBILITY - explicit __hash_node_destructor(allocator_type& __na) - : __na_(__na), - __value_constructed(false) - {} - - _LIBCPP_INLINE_VISIBILITY - void operator()(pointer __p) - { - if (__value_constructed) - __alloc_traits::destroy(__na_, addressof(__p->__value_)); - if (__p) - __alloc_traits::deallocate(__na_, __p, 1); - } - - template <class> friend class __hash_map_node_destructor; -}; - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -class __hash_table -{ -public: - typedef _Tp value_type; - typedef _Hash hasher; - typedef _Equal key_equal; - typedef _Alloc allocator_type; - -private: - typedef allocator_traits<allocator_type> __alloc_traits; -public: - typedef value_type& reference; - typedef const value_type& const_reference; - typedef typename __alloc_traits::pointer pointer; - typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; -public: - // Create __node - typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; - typedef typename __node::__first_node __first_node; - typedef typename __alloc_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind_alloc<__node> -#else - rebind_alloc<__node>::other -#endif - __node_allocator; - typedef allocator_traits<__node_allocator> __node_traits; - typedef typename __node_traits::pointer __node_pointer; - typedef typename __node_traits::const_pointer __node_const_pointer; - -private: - - typedef typename __node_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind_alloc<__node_pointer> -#else - rebind_alloc<__node_pointer>::other -#endif - __pointer_allocator; - typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; - typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; - typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; - typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; - - // --- Member data begin --- - __bucket_list __bucket_list_; - __compressed_pair<__first_node, __node_allocator> __p1_; - __compressed_pair<size_type, hasher> __p2_; - __compressed_pair<float, key_equal> __p3_; - // --- Member data end --- - - _LIBCPP_INLINE_VISIBILITY size_type& size() {return __p2_.first();} -public: - _LIBCPP_INLINE_VISIBILITY size_type size() const {return __p2_.first();} - - _LIBCPP_INLINE_VISIBILITY hasher& hash_function() {return __p2_.second();} - _LIBCPP_INLINE_VISIBILITY const hasher& hash_function() const {return __p2_.second();} - - _LIBCPP_INLINE_VISIBILITY float& max_load_factor() {return __p3_.first();} - _LIBCPP_INLINE_VISIBILITY float max_load_factor() const {return __p3_.first();} - - _LIBCPP_INLINE_VISIBILITY key_equal& key_eq() {return __p3_.second();} - _LIBCPP_INLINE_VISIBILITY const key_equal& key_eq() const {return __p3_.second();} - - _LIBCPP_INLINE_VISIBILITY __node_allocator& __node_alloc() {return __p1_.second();} - _LIBCPP_INLINE_VISIBILITY const __node_allocator& __node_alloc() const {return __p1_.second();} - -public: - typedef __hash_iterator<__node_pointer> iterator; - typedef __hash_const_iterator<__node_const_pointer> const_iterator; - typedef __hash_local_iterator<__node_pointer> local_iterator; - typedef __hash_const_local_iterator<__node_const_pointer> const_local_iterator; - - __hash_table(); - __hash_table(const hasher& __hf, const key_equal& __eql); - __hash_table(const hasher& __hf, const key_equal& __eql, - const allocator_type& __a); - explicit __hash_table(const allocator_type& __a); - __hash_table(const __hash_table& __u); - __hash_table(const __hash_table& __u, const allocator_type& __a); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __hash_table(__hash_table&& __u); - __hash_table(__hash_table&& __u, const allocator_type& __a); -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - ~__hash_table(); - - __hash_table& operator=(const __hash_table& __u); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __hash_table& operator=(__hash_table&& __u); -#endif - template <class _InputIterator> - void __assign_unique(_InputIterator __first, _InputIterator __last); - template <class _InputIterator> - void __assign_multi(_InputIterator __first, _InputIterator __last); - - _LIBCPP_INLINE_VISIBILITY - size_type max_size() const - { - return allocator_traits<__pointer_allocator>::max_size( - __bucket_list_.get_deleter().__alloc()); - } - - pair<iterator, bool> __node_insert_unique(__node_pointer __nd); - iterator __node_insert_multi(__node_pointer __nd); - iterator __node_insert_multi(const_iterator __p, - __node_pointer __nd); - -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - template <class... _Args> - pair<iterator, bool> __emplace_unique(_Args&&... __args); - template <class... _Args> - iterator __emplace_multi(_Args&&... __args); - template <class... _Args> - iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - - pair<iterator, bool> __insert_unique(const value_type& __x); - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - template <class _P> - pair<iterator, bool> __insert_unique(_P&& __x); -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - template <class _P> - iterator __insert_multi(_P&& __x); - template <class _P> - iterator __insert_multi(const_iterator __p, _P&& __x); -#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES - iterator __insert_multi(const value_type& __x); - iterator __insert_multi(const_iterator __p, const value_type& __x); -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - void clear(); - void rehash(size_type __n); - _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) - {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} - - _LIBCPP_INLINE_VISIBILITY - size_type bucket_count() const - { - return __bucket_list_.get_deleter().size(); - } - - iterator begin(); - iterator end(); - const_iterator begin() const; - const_iterator end() const; - - template <class _Key> - _LIBCPP_INLINE_VISIBILITY - size_type bucket(const _Key& __k) const - {return hash_function()(__k) % bucket_count();} - - template <class _Key> - iterator find(const _Key& __x); - template <class _Key> - const_iterator find(const _Key& __x) const; - - typedef __hash_node_destructor<__node_allocator> _D; - typedef unique_ptr<__node, _D> __node_holder; - - iterator erase(const_iterator __p); - iterator erase(const_iterator __first, const_iterator __last); - template <class _Key> - size_type __erase_unique(const _Key& __k); - template <class _Key> - size_type __erase_multi(const _Key& __k); - __node_holder remove(const_iterator __p); - - template <class _Key> - size_type __count_unique(const _Key& __k) const; - template <class _Key> - size_type __count_multi(const _Key& __k) const; - - template <class _Key> - pair<iterator, iterator> - __equal_range_unique(const _Key& __k); - template <class _Key> - pair<const_iterator, const_iterator> - __equal_range_unique(const _Key& __k) const; - - template <class _Key> - pair<iterator, iterator> - __equal_range_multi(const _Key& __k); - template <class _Key> - pair<const_iterator, const_iterator> - __equal_range_multi(const _Key& __k) const; - - void swap(__hash_table& __u); - - _LIBCPP_INLINE_VISIBILITY - size_type max_bucket_count() const - {return __bucket_list_.get_deleter().__alloc().max_size();} - size_type bucket_size(size_type __n) const; - _LIBCPP_INLINE_VISIBILITY float load_factor() const - { - size_type __bc = bucket_count(); - return __bc != 0 ? (float)size() / __bc : 0.f; - } - _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) - {max_load_factor() = _STD::max(__mlf, load_factor());} - - _LIBCPP_INLINE_VISIBILITY local_iterator begin(size_type __n) - {return local_iterator(__bucket_list_[__n], __n, bucket_count());} - _LIBCPP_INLINE_VISIBILITY local_iterator end(size_type __n) - {return local_iterator(nullptr, __n, bucket_count());} - _LIBCPP_INLINE_VISIBILITY const_local_iterator cbegin(size_type __n) const - {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());} - _LIBCPP_INLINE_VISIBILITY const_local_iterator cend(size_type __n) const - {return const_local_iterator(nullptr, __n, bucket_count());} -private: - void __rehash(size_type __n); - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS - template <class ..._Args> - __node_holder __construct_node(_Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS - __node_holder __construct_node(value_type&& __v, size_t __hash); -#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(const value_type& __v); -#endif - __node_holder __construct_node(const value_type& __v, size_t __hash); - - _LIBCPP_INLINE_VISIBILITY - void __copy_assign_alloc(const __hash_table& __u) - {__copy_assign_alloc(__u, integral_constant<bool, - __node_traits::propagate_on_container_copy_assignment::value>());} - void __copy_assign_alloc(const __hash_table& __u, true_type); - _LIBCPP_INLINE_VISIBILITY - void __copy_assign_alloc(const __hash_table& __u, false_type) {} - - void __move_assign(__hash_table& __u, false_type); - void __move_assign(__hash_table& __u, true_type); - _LIBCPP_INLINE_VISIBILITY void __move_assign_alloc(__hash_table& __u) - {__move_assign_alloc(__u, integral_constant<bool, - __node_traits::propagate_on_container_move_assignment::value>());} - _LIBCPP_INLINE_VISIBILITY - void __move_assign_alloc(__hash_table& __u, true_type) - { - __bucket_list_.get_deleter().__alloc() = - _STD::move(__u.__bucket_list_.get_deleter().__alloc()); - __node_alloc() = _STD::move(__u.__node_alloc()); - } - _LIBCPP_INLINE_VISIBILITY - void __move_assign_alloc(__hash_table&, false_type) {} - - template <class _A> - _LIBCPP_INLINE_VISIBILITY - static - void - __swap_alloc(_A& __x, _A& __y) - { - __swap_alloc(__x, __y, - integral_constant<bool, - allocator_traits<_A>::propagate_on_container_swap::value - >()); - } - - template <class _A> - _LIBCPP_INLINE_VISIBILITY - static - void - __swap_alloc(_A& __x, _A& __y, true_type) - { - using _STD::swap; - swap(__x, __y); - } - - template <class _A> - _LIBCPP_INLINE_VISIBILITY - static - void - __swap_alloc(_A& __x, _A& __y, false_type) {} - - void __deallocate(__node_pointer __np); - __node_pointer __detach(); -}; - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() - : __p2_(0), - __p3_(1.0f) -{ -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, - const key_equal& __eql) - : __bucket_list_(nullptr, __bucket_list_deleter()), - __p1_(), - __p2_(0, __hf), - __p3_(1.0f, __eql) -{ -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, - const key_equal& __eql, - const allocator_type& __a) - : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), - __p1_(__node_allocator(__a)), - __p2_(0, __hf), - __p3_(1.0f, __eql) -{ -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) - : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), - __p1_(__node_allocator(__a)), - __p2_(0), - __p3_(1.0f) -{ -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) - : __bucket_list_(nullptr, - __bucket_list_deleter(allocator_traits<__pointer_allocator>:: - select_on_container_copy_construction( - __u.__bucket_list_.get_deleter().__alloc()), 0)), - __p1_(allocator_traits<__node_allocator>:: - select_on_container_copy_construction(__u.__node_alloc())), - __p2_(0, __u.hash_function()), - __p3_(__u.__p3_) -{ -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, - const allocator_type& __a) - : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), - __p1_(__node_allocator(__a)), - __p2_(0, __u.hash_function()), - __p3_(__u.__p3_) -{ -} - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) - : __bucket_list_(_STD::move(__u.__bucket_list_)), - __p1_(_STD::move(__u.__p1_)), - __p2_(_STD::move(__u.__p2_)), - __p3_(_STD::move(__u.__p3_)) -{ - if (size() > 0) - { - __bucket_list_[__p1_.first().__next_->__hash_ % bucket_count()] = - static_cast<__node_pointer>(addressof(__p1_.first())); - __u.__p1_.first().__next_ = nullptr; - __u.size() = 0; - } -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, - const allocator_type& __a) - : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), - __p1_(__node_allocator(__a)), - __p2_(0, _STD::move(__u.hash_function())), - __p3_(_STD::move(__u.__p3_)) -{ - if (__a == allocator_type(__u.__node_alloc())) - { - __bucket_list_.reset(__u.__bucket_list_.release()); - __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); - __u.__bucket_list_.get_deleter().size() = 0; - if (__u.size() > 0) - { - __p1_.first().__next_ = __u.__p1_.first().__next_; - __u.__p1_.first().__next_ = nullptr; - __bucket_list_[__p1_.first().__next_->__hash_ % bucket_count()] = - static_cast<__node_pointer>(addressof(__p1_.first())); - size() = __u.size(); - __u.size() = 0; - } - } -} - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() -{ - __deallocate(__p1_.first().__next_); -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( - const __hash_table& __u, true_type) -{ - if (__node_alloc() != __u.__node_alloc()) - { - clear(); - __bucket_list_.reset(); - __bucket_list_.get_deleter().size() = 0; - } - __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); - __node_alloc() = __u.__node_alloc(); -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -__hash_table<_Tp, _Hash, _Equal, _Alloc>& -__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) -{ - if (this != &__u) - { - __copy_assign_alloc(__u); - hash_function() = __u.hash_function(); - key_eq() = __u.key_eq(); - max_load_factor() = __u.max_load_factor(); - __assign_multi(__u.begin(), __u.end()); - } - return *this; -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) -{ - __node_allocator& __na = __node_alloc(); - while (__np != nullptr) - { - __node_pointer __next = __np->__next_; - __node_traits::destroy(__na, addressof(__np->__value_)); - __node_traits::deallocate(__na, __np, 1); - __np = __next; - } -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() -{ - size_type __bc = bucket_count(); - for (size_type __i = 0; __i < __bc; ++__i) - __bucket_list_[__i] = nullptr; - size() = 0; - __node_pointer __cache = __p1_.first().__next_; - __p1_.first().__next_ = nullptr; - return __cache; -} - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( - __hash_table& __u, true_type) -{ - clear(); - __bucket_list_.reset(__u.__bucket_list_.release()); - __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); - __u.__bucket_list_.get_deleter().size() = 0; - __move_assign_alloc(__u); - size() = __u.size(); - hash_function() = _STD::move(__u.hash_function()); - max_load_factor() = __u.max_load_factor(); - key_eq() = _STD::move(__u.key_eq()); - __p1_.first().__next_ = __u.__p1_.first().__next_; - if (size() > 0) - { - __bucket_list_[__p1_.first().__next_->__hash_ % bucket_count()] = - static_cast<__node_pointer>(addressof(__p1_.first())); - __u.__p1_.first().__next_ = nullptr; - __u.size() = 0; - } -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( - __hash_table& __u, false_type) -{ - if (__node_alloc() == __u.__node_alloc()) - __move_assign(__u, true_type()); - else - { - hash_function() = _STD::move(__u.hash_function()); - key_eq() = _STD::move(__u.key_eq()); - max_load_factor() = __u.max_load_factor(); - if (bucket_count() != 0) - { - __node_pointer __cache = __detach(); -#ifndef _LIBCPP_NO_EXCEPTIONS - try - { -#endif // _LIBCPP_NO_EXCEPTIONS - const_iterator __i = __u.begin(); - while (__cache != nullptr && __u.size() != 0) - { - __cache->__value_ = _STD::move(__u.remove(__i++)->__value_); - __node_pointer __next = __cache->__next_; - __node_insert_multi(__cache); - __cache = __next; - } -#ifndef _LIBCPP_NO_EXCEPTIONS - } - catch (...) - { - __deallocate(__cache); - throw; - } -#endif // _LIBCPP_NO_EXCEPTIONS - __deallocate(__cache); - } - const_iterator __i = __u.begin(); - while (__u.size() != 0) - { - __node_holder __h = - __construct_node(_STD::move(__u.remove(__i++)->__value_)); - __node_insert_multi(__h.get()); - __h.release(); - } - } -} - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -inline _LIBCPP_INLINE_VISIBILITY -__hash_table<_Tp, _Hash, _Equal, _Alloc>& -__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) -{ - __move_assign(__u, integral_constant<bool, - __node_traits::propagate_on_container_move_assignment::value>()); - return *this; -} - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - -template <class _Tp, class _Hash, class _Equal, class _Alloc> -template <class _InputIterator> -void -__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, - _InputIterator __last) -{ - if (bucket_count() != 0) - { - __node_pointer __cache = __detach(); -#ifndef _LIBCPP_NO_EXCEPTIONS - try |