From 3ad39e9878310e5317ee73c9b353c1e2c1c5c4ee Mon Sep 17 00:00:00 2001 From: Richard Qin Date: Sat, 11 Jul 2026 22:48:30 +0800 Subject: lib: establish Zircon libc++ and KTL foundation --- third_party/libcxx/include/c++/v1/ext/__hash | 85 +++ third_party/libcxx/include/c++/v1/ext/hash_map | 835 +++++++++++++++++++++++++ third_party/libcxx/include/c++/v1/ext/hash_set | 582 +++++++++++++++++ 3 files changed, 1502 insertions(+) create mode 100644 third_party/libcxx/include/c++/v1/ext/__hash create mode 100644 third_party/libcxx/include/c++/v1/ext/hash_map create mode 100644 third_party/libcxx/include/c++/v1/ext/hash_set (limited to 'third_party/libcxx/include/c++/v1/ext') diff --git a/third_party/libcxx/include/c++/v1/ext/__hash b/third_party/libcxx/include/c++/v1/ext/__hash new file mode 100644 index 0000000..e523d0d --- /dev/null +++ b/third_party/libcxx/include/c++/v1/ext/__hash @@ -0,0 +1,85 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_EXT_HASH +#define _LIBCPP_EXT_HASH + +#pragma GCC system_header + +#include <__config> +#include +#include +#include + +namespace __gnu_cxx { + +template +struct hash {}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(const char* __c) const _NOEXCEPT { + return std::__do_string_hash(__c, __c + strlen(__c)); + } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(char* __c) const _NOEXCEPT { + return std::__do_string_hash(__c, __c + strlen(__c)); + } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(char __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(signed char __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned char __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(short __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned short __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(int __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned int __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(long __c) const _NOEXCEPT { return __c; } +}; + +template <> +struct hash : public std::__unary_function { + _LIBCPP_HIDE_FROM_ABI size_t operator()(unsigned long __c) const _NOEXCEPT { return __c; } +}; +} // namespace __gnu_cxx + +#endif // _LIBCPP_EXT_HASH diff --git a/third_party/libcxx/include/c++/v1/ext/hash_map b/third_party/libcxx/include/c++/v1/ext/hash_map new file mode 100644 index 0000000..09c9811 --- /dev/null +++ b/third_party/libcxx/include/c++/v1/ext/hash_map @@ -0,0 +1,835 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_HASH_MAP +#define _LIBCPP_HASH_MAP + +/* + + hash_map synopsis + +namespace __gnu_cxx +{ + +template , class Pred = equal_to, + class Alloc = allocator>> +class hash_map +{ +public: + // types + typedef Key key_type; + typedef T mapped_type; + typedef Hash hasher; + typedef Pred key_equal; + typedef Alloc allocator_type; + typedef pair value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef typename allocator_traits::pointer pointer; + typedef typename allocator_traits::const_pointer const_pointer; + typedef typename allocator_traits::size_type size_type; + typedef typename allocator_traits::difference_type difference_type; + + typedef /unspecified/ iterator; + typedef /unspecified/ const_iterator; + + hash_map(); + explicit hash_map(size_type n, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + template + hash_map(InputIterator f, InputIterator l); + template + hash_map(InputIterator f, InputIterator l, + size_type n, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + hash_map(const hash_map&); + ~hash_map(); + hash_map& operator=(const hash_map&); + + allocator_type get_allocator() const; + + bool empty() const; + size_type size() const; + size_type max_size() const; + + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + + pair insert(const value_type& obj); + template + void insert(InputIterator first, InputIterator last); + + void erase(const_iterator position); + size_type erase(const key_type& k); + void erase(const_iterator first, const_iterator last); + void clear(); + + void swap(hash_map&); + + hasher hash_funct() const; + key_equal key_eq() const; + + iterator find(const key_type& k); + const_iterator find(const key_type& k) const; + size_type count(const key_type& k) const; + pair equal_range(const key_type& k); + pair equal_range(const key_type& k) const; + + mapped_type& operator[](const key_type& k); + + size_type bucket_count() const; + size_type max_bucket_count() const; + + size_type elems_in_bucket(size_type n) const; + + void resize(size_type n); +}; + +template + void swap(hash_map& x, + hash_map& y); + +template + bool + operator==(const hash_map& x, + const hash_map& y); + +template + bool + operator!=(const hash_map& x, + const hash_map& y); + +template , class Pred = equal_to, + class Alloc = allocator>> +class hash_multimap +{ +public: + // types + typedef Key key_type; + typedef T mapped_type; + typedef Hash hasher; + typedef Pred key_equal; + typedef Alloc allocator_type; + typedef pair value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef typename allocator_traits::pointer pointer; + typedef typename allocator_traits::const_pointer const_pointer; + typedef typename allocator_traits::size_type size_type; + typedef typename allocator_traits::difference_type difference_type; + + typedef /unspecified/ iterator; + typedef /unspecified/ const_iterator; + + explicit hash_multimap(size_type n = 193, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + template + hash_multimap(InputIterator f, InputIterator l, + size_type n = 193, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + explicit hash_multimap(const allocator_type&); + hash_multimap(const hash_multimap&); + ~hash_multimap(); + hash_multimap& operator=(const hash_multimap&); + + allocator_type get_allocator() const; + + bool empty() const; + size_type size() const; + size_type max_size() const; + + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + + iterator insert(const value_type& obj); + template + void insert(InputIterator first, InputIterator last); + + void erase(const_iterator position); + size_type erase(const key_type& k); + void erase(const_iterator first, const_iterator last); + void clear(); + + void swap(hash_multimap&); + + hasher hash_funct() const; + key_equal key_eq() const; + + iterator find(const key_type& k); + const_iterator find(const key_type& k) const; + size_type count(const key_type& k) const; + pair equal_range(const key_type& k); + pair equal_range(const key_type& k) const; + + size_type bucket_count() const; + size_type max_bucket_count() const; + + size_type elems_in_bucket(size_type n) const; + + void resize(size_type n); +}; + +template + void swap(hash_multimap& x, + hash_multimap& y); + +template + bool + operator==(const hash_multimap& x, + const hash_multimap& y); + +template + bool + operator!=(const hash_multimap& x, + const hash_multimap& y); + +} // __gnu_cxx + +*/ + +#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) +# include <__cxx03/ext/hash_map> +#else +# include <__config> +# include <__hash_table> +# include <__memory/compressed_pair.h> +# include +# include +# include + +# if defined(__DEPRECATED) && __DEPRECATED +# if defined(_LIBCPP_WARNING) +_LIBCPP_WARNING("Use of the header is deprecated. Migrate to ") +# else +# warning Use of the header is deprecated. Migrate to +# endif +# endif + +# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +# endif + +namespace __gnu_cxx { + +template +class __hash_map_hasher { + _LIBCPP_COMPRESSED_ELEMENT(_Hash, __hash_); + +public: + _LIBCPP_HIDE_FROM_ABI __hash_map_hasher() : __hash_() {} + _LIBCPP_HIDE_FROM_ABI __hash_map_hasher(const _Hash& __h) : __hash_(__h) {} + _LIBCPP_HIDE_FROM_ABI const _Hash& hash_function() const { return __hash_; } + _LIBCPP_HIDE_FROM_ABI size_t operator()(const _Tp& __x) const { return __hash_(__x.first); } + _LIBCPP_HIDE_FROM_ABI size_t operator()(const typename _Tp::first_type& __x) const { return __hash_(__x); } +}; + +template +class __hash_map_equal { + _LIBCPP_COMPRESSED_ELEMENT(_Pred, __pred_); + +public: + _LIBCPP_HIDE_FROM_ABI __hash_map_equal() : __pred_() {} + _LIBCPP_HIDE_FROM_ABI __hash_map_equal(const _Pred& __p) : __pred_(__p) {} + _LIBCPP_HIDE_FROM_ABI const _Pred& key_eq() const { return __pred_; } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const _Tp& __y) const { return __pred_(__x.first, __y.first); } + _LIBCPP_HIDE_FROM_ABI bool operator()(const typename _Tp::first_type& __x, const _Tp& __y) const { + return __pred_(__x, __y.first); + } + _LIBCPP_HIDE_FROM_ABI bool operator()(const _Tp& __x, const typename _Tp::first_type& __y) const { + return __pred_(__x.first, __y); + } + _LIBCPP_HIDE_FROM_ABI bool + operator()(const typename _Tp::first_type& __x, const typename _Tp::first_type& __y) const { + return __pred_(__x, __y); + } +}; + +template +class __hash_map_node_destructor { + typedef _Alloc allocator_type; + typedef std::allocator_traits __alloc_traits; + typedef typename __alloc_traits::value_type::__node_value_type value_type; + +public: + typedef typename __alloc_traits::pointer pointer; + +private: + typedef typename value_type::first_type first_type; + typedef typename value_type::second_type second_type; + + allocator_type& __na_; + +public: + bool __first_constructed; + bool __second_constructed; + + _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(__hash_map_node_destructor const&) = default; + __hash_map_node_destructor& operator=(const __hash_map_node_destructor&) = delete; + + _LIBCPP_HIDE_FROM_ABI explicit __hash_map_node_destructor(allocator_type& __na) + : __na_(__na), __first_constructed(false), __second_constructed(false) {} + +# ifndef _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(std::__hash_node_destructor&& __x) + : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { + __x.__value_constructed = false; + } +# else // _LIBCPP_CXX03_LANG + _LIBCPP_HIDE_FROM_ABI __hash_map_node_destructor(const std::__hash_node_destructor& __x) + : __na_(__x.__na_), __first_constructed(__x.__value_constructed), __second_constructed(__x.__value_constructed) { + const_cast(__x.__value_constructed) = false; + } +# endif // _LIBCPP_CXX03_LANG + + _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) { + if (__second_constructed) + __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().second)); + if (__first_constructed) + __alloc_traits::destroy(__na_, std::addressof(__p->__get_value().first)); + if (__p) + __alloc_traits::deallocate(__na_, __p, 1); + } +}; + +template +class __hash_map_iterator { + _HashIterator __i_; + + typedef const typename _HashIterator::value_type::first_type key_type; + typedef typename _HashIterator::value_type::second_type mapped_type; + +public: + typedef std::forward_iterator_tag iterator_category; + typedef std::pair value_type; + typedef typename _HashIterator::difference_type difference_type; + typedef value_type& reference; + typedef std::__rebind_pointer_t pointer; + + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator() {} + + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator(_HashIterator __i) : __i_(__i) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); } + + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator& operator++() { + ++__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __hash_map_iterator operator++(int) { + __hash_map_iterator __t(*this); + ++(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { + return __x.__i_ == __y.__i_; + } + friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_map_iterator& __x, const __hash_map_iterator& __y) { + return __x.__i_ != __y.__i_; + } + + template + friend class hash_map; + template + friend class hash_multimap; + template + friend class __hash_const_iterator; + template + friend class __hash_const_local_iterator; + template + friend class __hash_map_const_iterator; +}; + +template +class __hash_map_const_iterator { + _HashIterator __i_; + + typedef const typename _HashIterator::value_type::first_type key_type; + typedef typename _HashIterator::value_type::second_type mapped_type; + +public: + typedef std::forward_iterator_tag iterator_category; + typedef std::pair value_type; + typedef typename _HashIterator::difference_type difference_type; + typedef const value_type& reference; + typedef std::__rebind_pointer_t pointer; + + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator() {} + + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(_HashIterator __i) : __i_(__i) {} + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator(__hash_map_iterator __i) + : __i_(__i.__i_) {} + + _LIBCPP_HIDE_FROM_ABI reference operator*() const { return *operator->(); } + _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return (pointer)__i_.operator->(); } + + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator& operator++() { + ++__i_; + return *this; + } + _LIBCPP_HIDE_FROM_ABI __hash_map_const_iterator operator++(int) { + __hash_map_const_iterator __t(*this); + ++(*this); + return __t; + } + + friend _LIBCPP_HIDE_FROM_ABI bool + operator==(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { + return __x.__i_ == __y.__i_; + } + friend _LIBCPP_HIDE_FROM_ABI bool + operator!=(const __hash_map_const_iterator& __x, const __hash_map_const_iterator& __y) { + return __x.__i_ != __y.__i_; + } + + template + friend class hash_map; + template + friend class hash_multimap; + template + friend class __hash_const_iterator; + template + friend class __hash_const_local_iterator; +}; + +template , + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator > > +class hash_map { +public: + // types + typedef _Key key_type; + typedef _Tp mapped_type; + typedef _Tp data_type; + typedef _Hash hasher; + typedef _Pred key_equal; + typedef _Alloc allocator_type; + typedef std::pair value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + +private: + typedef std::pair __value_type; + typedef __hash_map_hasher<__value_type, hasher> __hasher; + typedef __hash_map_equal<__value_type, key_equal> __key_equal; + typedef std::__rebind_alloc, __value_type> __allocator_type; + + typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; + + __table __table_; + + typedef typename __table::__node_traits __node_traits; + typedef typename __table::__node_allocator __node_allocator; + typedef typename __table::__node __node; + typedef __hash_map_node_destructor<__node_allocator> _Dp; + typedef std::unique_ptr<__node, _Dp> __node_holder; + typedef std::allocator_traits __alloc_traits; + +public: + 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; + + typedef __hash_map_iterator iterator; + typedef __hash_map_const_iterator const_iterator; + + _LIBCPP_HIDE_FROM_ABI hash_map() {} + explicit _LIBCPP_HIDE_FROM_ABI + hash_map(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); + _LIBCPP_HIDE_FROM_ABI hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + template + _LIBCPP_HIDE_FROM_ABI hash_map(_InputIterator __first, _InputIterator __last); + template + _LIBCPP_HIDE_FROM_ABI + hash_map(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal()); + template + _LIBCPP_HIDE_FROM_ABI + hash_map(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI hash_map(const hash_map& __u); + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } + + _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } + + _LIBCPP_HIDE_FROM_ABI std::pair insert(const value_type& __x) { + return __table_.__emplace_unique(__x); + } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } + template + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); + + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { + __table_.erase(__first.__i_, __last.__i_); + } + _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } + + _LIBCPP_HIDE_FROM_ABI void swap(hash_map& __u) { __table_.swap(__u.__table_); } + + _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); } + _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } + + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) { + return __table_.__equal_range_unique(__k); + } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) const { + return __table_.__equal_range_unique(__k); + } + + _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k); + + _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } + _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } + + _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } + + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); } + +private: + _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(const key_type& __k); +}; + +template +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_unique(__n); +} + +template +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( + size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_unique(__n); +} + +template +template +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(_InputIterator __first, _InputIterator __last) { + insert(__first, __last); +} + +template +template +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( + _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_unique(__n); + insert(__first, __last); +} + +template +template +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map( + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_unique(__n); + insert(__first, __last); +} + +template +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_map(const hash_map& __u) : __table_(__u.__table_) {} + +template +typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__node_holder +hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::__construct_node(const key_type& __k) { + __node_allocator& __na = __table_.__node_alloc(); + __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); + __node_traits::construct(__na, std::addressof(__h->__get_value().first), __k); + __h.get_deleter().__first_constructed = true; + __node_traits::construct(__na, std::addressof(__h->__get_value().second)); + __h.get_deleter().__second_constructed = true; + return __h; +} + +template +template +inline void hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { + for (; __first != __last; ++__first) + __table_.__emplace_unique(*__first); +} + +template +_Tp& hash_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); + std::pair __r = __table_.__node_insert_unique(__h.get()); + __h.release(); + return __r.first->second; +} + +template +inline _LIBCPP_HIDE_FROM_ABI void +swap(hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + __x.swap(__y); +} + +template +_LIBCPP_HIDE_FROM_ABI bool +operator==(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + if (__x.size() != __y.size()) + return false; + typedef typename hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { + const_iterator __j = __y.find(__i->first); + if (__j == __ey || !(*__i == *__j)) + return false; + } + return true; +} + +template +inline _LIBCPP_HIDE_FROM_ABI bool +operator!=(const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, const hash_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + return !(__x == __y); +} + +template , + class _Pred = std::equal_to<_Key>, + class _Alloc = std::allocator > > +class hash_multimap { +public: + // types + typedef _Key key_type; + typedef _Tp mapped_type; + typedef _Tp data_type; + typedef _Hash hasher; + typedef _Pred key_equal; + typedef _Alloc allocator_type; + typedef std::pair value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + +private: + typedef std::pair __value_type; + typedef __hash_map_hasher<__value_type, hasher> __hasher; + typedef __hash_map_equal<__value_type, key_equal> __key_equal; + typedef std::__rebind_alloc, __value_type> __allocator_type; + + typedef std::__hash_table<__value_type, __hasher, __key_equal, __allocator_type> __table; + + __table __table_; + + typedef typename __table::__node_allocator __node_allocator; + typedef typename __table::__node __node; + typedef __hash_map_node_destructor<__node_allocator> _Dp; + typedef std::unique_ptr<__node, _Dp> __node_holder; + typedef std::allocator_traits __alloc_traits; + +public: + 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; + + typedef __hash_map_iterator iterator; + typedef __hash_map_const_iterator const_iterator; + + _LIBCPP_HIDE_FROM_ABI hash_multimap() {} + explicit _LIBCPP_HIDE_FROM_ABI + hash_multimap(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); + _LIBCPP_HIDE_FROM_ABI + hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + template + _LIBCPP_HIDE_FROM_ABI hash_multimap(_InputIterator __first, _InputIterator __last); + template + _LIBCPP_HIDE_FROM_ABI + hash_multimap(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal()); + template + _LIBCPP_HIDE_FROM_ABI hash_multimap( + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI hash_multimap(const hash_multimap& __u); + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } + + _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } + + _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__emplace_multi(__x); } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); } + template + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); + + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p.__i_); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { + __table_.erase(__first.__i_, __last.__i_); + } + _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } + + _LIBCPP_HIDE_FROM_ABI void swap(hash_multimap& __u) { __table_.swap(__u.__table_); } + + _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function().hash_function(); } + _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq().key_eq(); } + + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) { + return __table_.__equal_range_multi(__k); + } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) const { + return __table_.__equal_range_multi(__k); + } + + _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } + _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } + + _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } + + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); } +}; + +template +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_multi(__n); +} + +template +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( + size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_multi(__n); +} + +template +template +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(_InputIterator __first, _InputIterator __last) { + insert(__first, __last); +} + +template +template +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( + _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_multi(__n); + insert(__first, __last); +} + +template +template +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap( + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_multi(__n); + insert(__first, __last); +} + +template +hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::hash_multimap(const hash_multimap& __u) : __table_(__u.__table_) {} + +template +template +inline void hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { + for (; __first != __last; ++__first) + __table_.__emplace_multi(*__first); +} + +template +inline _LIBCPP_HIDE_FROM_ABI void +swap(hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + __x.swap(__y); +} + +template +_LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, + const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + if (__x.size() != __y.size()) + return false; + typedef typename hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + typedef std::pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { + _EqRng __xeq = __x.equal_range(__i->first); + _EqRng __yeq = __y.equal_range(__i->first); + if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || + !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + return false; + __i = __xeq.second; + } + return true; +} + +template +inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, + const hash_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) { + return !(__x == __y); +} + +} // namespace __gnu_cxx + +# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 +# include +# include +# include +# endif +#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) + +#endif // _LIBCPP_HASH_MAP diff --git a/third_party/libcxx/include/c++/v1/ext/hash_set b/third_party/libcxx/include/c++/v1/ext/hash_set new file mode 100644 index 0000000..56aa4d8 --- /dev/null +++ b/third_party/libcxx/include/c++/v1/ext/hash_set @@ -0,0 +1,582 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP_HASH_SET +#define _LIBCPP_HASH_SET + +/* + + hash_set synopsis + +namespace __gnu_cxx +{ + +template , class Pred = equal_to, + class Alloc = allocator> +class hash_set +{ +public: + // types + typedef Value key_type; + typedef key_type value_type; + typedef Hash hasher; + typedef Pred key_equal; + typedef Alloc allocator_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef typename allocator_traits::pointer pointer; + typedef typename allocator_traits::const_pointer const_pointer; + typedef typename allocator_traits::size_type size_type; + typedef typename allocator_traits::difference_type difference_type; + + typedef /unspecified/ iterator; + typedef /unspecified/ const_iterator; + + explicit hash_set(size_type n = 193, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + template + hash_set(InputIterator f, InputIterator l, + size_type n = 193, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + hash_set(const hash_set&); + ~hash_set(); + hash_set& operator=(const hash_set&); + + allocator_type get_allocator() const; + + bool empty() const; + size_type size() const; + size_type max_size() const; + + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + + pair insert(const value_type& obj); + template + void insert(InputIterator first, InputIterator last); + + void erase(const_iterator position); + size_type erase(const key_type& k); + void erase(const_iterator first, const_iterator last); + void clear(); + + void swap(hash_set&); + + hasher hash_funct() const; + key_equal key_eq() const; + + iterator find(const key_type& k); + const_iterator find(const key_type& k) const; + size_type count(const key_type& k) const; + pair equal_range(const key_type& k); + pair equal_range(const key_type& k) const; + + size_type bucket_count() const; + size_type max_bucket_count() const; + + size_type elems_in_bucket(size_type n) const; + + void resize(size_type n); +}; + +template + void swap(hash_set& x, + hash_set& y); + +template + bool + operator==(const hash_set& x, + const hash_set& y); + +template + bool + operator!=(const hash_set& x, + const hash_set& y); + +template , class Pred = equal_to, + class Alloc = allocator> +class hash_multiset +{ +public: + // types + typedef Value key_type; + typedef key_type value_type; + typedef Hash hasher; + typedef Pred key_equal; + typedef Alloc allocator_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef typename allocator_traits::pointer pointer; + typedef typename allocator_traits::const_pointer const_pointer; + typedef typename allocator_traits::size_type size_type; + typedef typename allocator_traits::difference_type difference_type; + + typedef /unspecified/ iterator; + typedef /unspecified/ const_iterator; + + explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + template + hash_multiset(InputIterator f, InputIterator l, + size_type n = 193, const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()); + hash_multiset(const hash_multiset&); + ~hash_multiset(); + hash_multiset& operator=(const hash_multiset&); + + allocator_type get_allocator() const; + + bool empty() const; + size_type size() const; + size_type max_size() const; + + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + + iterator insert(const value_type& obj); + template + void insert(InputIterator first, InputIterator last); + + void erase(const_iterator position); + size_type erase(const key_type& k); + void erase(const_iterator first, const_iterator last); + void clear(); + + void swap(hash_multiset&); + + hasher hash_funct() const; + key_equal key_eq() const; + + iterator find(const key_type& k); + const_iterator find(const key_type& k) const; + size_type count(const key_type& k) const; + pair equal_range(const key_type& k); + pair equal_range(const key_type& k) const; + + size_type bucket_count() const; + size_type max_bucket_count() const; + + size_type elems_in_bucket(size_type n) const; + + void resize(size_type n); +}; + +template + void swap(hash_multiset& x, + hash_multiset& y); + +template + bool + operator==(const hash_multiset& x, + const hash_multiset& y); + +template + bool + operator!=(const hash_multiset& x, + const hash_multiset& y); +} // __gnu_cxx + +*/ + +#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) +# include <__cxx03/ext/hash_set> +#else +# include <__config> +# include <__hash_table> +# include +# include +# include + +# if defined(__DEPRECATED) && __DEPRECATED +# if defined(_LIBCPP_WARNING) +_LIBCPP_WARNING("Use of the header is deprecated. Migrate to ") +# else +# warning Use of the header is deprecated. Migrate to +# endif +# endif + +# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +# endif + +namespace __gnu_cxx { + +template , + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value> > +class hash_set { +public: + // types + typedef _Value key_type; + typedef key_type value_type; + typedef _Hash hasher; + typedef _Pred key_equal; + typedef _Alloc allocator_type; + typedef value_type& reference; + typedef const value_type& const_reference; + +private: + typedef std::__hash_table __table; + + __table __table_; + +public: + typedef typename __table::pointer pointer; + typedef typename __table::const_pointer const_pointer; + typedef typename __table::size_type size_type; + typedef typename __table::difference_type difference_type; + + typedef typename __table::const_iterator iterator; + typedef typename __table::const_iterator const_iterator; + + _LIBCPP_HIDE_FROM_ABI hash_set() {} + _LIBCPP_HIDE_FROM_ABI explicit hash_set( + size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); + _LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + template + _LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last); + template + _LIBCPP_HIDE_FROM_ABI + hash_set(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal()); + template + _LIBCPP_HIDE_FROM_ABI + hash_set(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u); + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } + + _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } + + _LIBCPP_HIDE_FROM_ABI std::pair insert(const value_type& __x) { + return __table_.__emplace_unique(__x); + } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; } + template + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); + + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); } + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); } + _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } + + _LIBCPP_HIDE_FROM_ABI void swap(hash_set& __u) { __table_.swap(__u.__table_); } + + _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); } + _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } + + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) { + return __table_.__equal_range_unique(__k); + } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) const { + return __table_.__equal_range_unique(__k); + } + + _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } + _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } + + _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } + + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); } +}; + +template +hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_unique(__n); +} + +template +hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( + size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_unique(__n); +} + +template +template +hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(_InputIterator __first, _InputIterator __last) { + insert(__first, __last); +} + +template +template +hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( + _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_unique(__n); + insert(__first, __last); +} + +template +template +hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set( + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_unique(__n); + insert(__first, __last); +} + +template +hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(const hash_set& __u) : __table_(__u.__table_) {} + +template +template +inline void hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { + for (; __first != __last; ++__first) + __table_.__emplace_unique(*__first); +} + +template +inline _LIBCPP_HIDE_FROM_ABI void +swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, hash_set<_Value, _Hash, _Pred, _Alloc>& __y) { + __x.swap(__y); +} + +template +_LIBCPP_HIDE_FROM_ABI bool +operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) { + if (__x.size() != __y.size()) + return false; + typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) { + const_iterator __j = __y.find(*__i); + if (__j == __ey || !(*__i == *__j)) + return false; + } + return true; +} + +template +inline _LIBCPP_HIDE_FROM_ABI bool +operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) { + return !(__x == __y); +} + +template , + class _Pred = std::equal_to<_Value>, + class _Alloc = std::allocator<_Value> > +class hash_multiset { +public: + // types + typedef _Value key_type; + typedef key_type value_type; + typedef _Hash hasher; + typedef _Pred key_equal; + typedef _Alloc allocator_type; + typedef value_type& reference; + typedef const value_type& const_reference; + +private: + typedef std::__hash_table __table; + + __table __table_; + +public: + typedef typename __table::pointer pointer; + typedef typename __table::const_pointer const_pointer; + typedef typename __table::size_type size_type; + typedef typename __table::difference_type difference_type; + + typedef typename __table::const_iterator iterator; + typedef typename __table::const_iterator const_iterator; + + _LIBCPP_HIDE_FROM_ABI hash_multiset() {} + explicit _LIBCPP_HIDE_FROM_ABI + hash_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal()); + _LIBCPP_HIDE_FROM_ABI + hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a); + template + _LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last); + template + _LIBCPP_HIDE_FROM_ABI + hash_multiset(_InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf = hasher(), + const key_equal& __eql = key_equal()); + template + _LIBCPP_HIDE_FROM_ABI hash_multiset( + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a); + _LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u); + + _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); } + + _LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; } + _LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); } + _LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); } + + _LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); } + _LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); } + _LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); } + + _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__emplace_multi(__x); } + _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); } + template + _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last); + + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); } + _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); } + _LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); } + _LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); } + + _LIBCPP_HIDE_FROM_ABI void swap(hash_multiset& __u) { __table_.swap(__u.__table_); } + + _LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); } + _LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); } + + _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); } + _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) { + return __table_.__equal_range_multi(__k); + } + _LIBCPP_HIDE_FROM_ABI std::pair equal_range(const key_type& __k) const { + return __table_.__equal_range_multi(__k); + } + + _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); } + _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); } + + _LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); } + + _LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); } +}; + +template +hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_multi(__n); +} + +template +hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( + size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_multi(__n); +} + +template +template +hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(_InputIterator __first, _InputIterator __last) { + insert(__first, __last); +} + +template +template +hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( + _InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql) + : __table_(__hf, __eql) { + __table_.__rehash_multi(__n); + insert(__first, __last); +} + +template +template +hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset( + _InputIterator __first, + _InputIterator __last, + size_type __n, + const hasher& __hf, + const key_equal& __eql, + const allocator_type& __a) + : __table_(__hf, __eql, __a) { + __table_.__rehash_multi(__n); + insert(__first, __last); +} + +template +hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(const hash_multiset& __u) : __table_(__u.__table_) {} + +template +template +inline void hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) { + for (; __first != __last; ++__first) + __table_.__emplace_multi(*__first); +} + +template +inline _LIBCPP_HIDE_FROM_ABI void +swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { + __x.swap(__y); +} + +template +_LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, + const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { + if (__x.size() != __y.size()) + return false; + typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator; + typedef std::pair _EqRng; + for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) { + _EqRng __xeq = __x.equal_range(*__i); + _EqRng __yeq = __y.equal_range(*__i); + if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) || + !std::is_permutation(__xeq.first, __xeq.second, __yeq.first)) + return false; + __i = __xeq.second; + } + return true; +} + +template +inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, + const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) { + return !(__x == __y); +} + +} // namespace __gnu_cxx + +# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 +# include +# include +# include +# endif +#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS) + +#endif // _LIBCPP_HASH_SET -- cgit v1.2.3