diff options
Diffstat (limited to 'libstdc++-v3/include')
44 files changed, 2822 insertions, 2431 deletions
diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index abd9abf4e70..797afb619c8 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -321,6 +321,7 @@ debug_headers = \ ${debug_srcdir}/debug.h \ ${debug_srcdir}/deque \ ${debug_srcdir}/formatter.h \ + ${debug_srcdir}/functions.h \ ${debug_srcdir}/hash_map \ ${debug_srcdir}/hash_map.h \ ${debug_srcdir}/hash_multimap.h \ @@ -329,6 +330,7 @@ debug_headers = \ ${debug_srcdir}/hash_set.h \ ${debug_srcdir}/list \ ${debug_srcdir}/map \ + ${debug_srcdir}/macros.h \ ${debug_srcdir}/map.h \ ${debug_srcdir}/multimap.h \ ${debug_srcdir}/multiset.h \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index 60bf72bf3c4..ef6f242f0d5 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -40,7 +40,8 @@ DIST_COMMON = $(srcdir)/Makefile.am $(srcdir)/Makefile.in \ $(top_srcdir)/fragment.am subdir = include ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 -am__aclocal_m4_deps = $(top_srcdir)/../config/no-executables.m4 \ +am__aclocal_m4_deps = $(top_srcdir)/../config/lead-dot.m4 \ + $(top_srcdir)/../config/no-executables.m4 \ $(top_srcdir)/../libtool.m4 $(top_srcdir)/crossconfig.m4 \ $(top_srcdir)/linkage.m4 $(top_srcdir)/acinclude.m4 \ $(top_srcdir)/configure.ac @@ -538,6 +539,7 @@ debug_headers = \ ${debug_srcdir}/debug.h \ ${debug_srcdir}/deque \ ${debug_srcdir}/formatter.h \ + ${debug_srcdir}/functions.h \ ${debug_srcdir}/hash_map \ ${debug_srcdir}/hash_map.h \ ${debug_srcdir}/hash_multimap.h \ @@ -546,6 +548,7 @@ debug_headers = \ ${debug_srcdir}/hash_set.h \ ${debug_srcdir}/list \ ${debug_srcdir}/map \ + ${debug_srcdir}/macros.h \ ${debug_srcdir}/map.h \ ${debug_srcdir}/multimap.h \ ${debug_srcdir}/multiset.h \ diff --git a/libstdc++-v3/include/bits/allocator.h b/libstdc++-v3/include/bits/allocator.h index c28442fc6fa..598048d0df3 100644 --- a/libstdc++-v3/include/bits/allocator.h +++ b/libstdc++-v3/include/bits/allocator.h @@ -1,6 +1,6 @@ // Allocators -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -79,7 +79,7 @@ namespace std * http://gcc.gnu.org/onlinedocs/libstdc++/20_util/allocator.html */ template<typename _Tp> - class allocator: public ___glibcxx_base_allocator<_Tp> + class allocator: public __glibcxx_base_allocator<_Tp> { public: typedef size_t size_type; @@ -97,7 +97,7 @@ namespace std allocator() throw() { } allocator(const allocator& __a) throw() - : ___glibcxx_base_allocator<_Tp>(__a) { } + : __glibcxx_base_allocator<_Tp>(__a) { } template<typename _Tp1> allocator(const allocator<_Tp1>&) throw() { } @@ -126,7 +126,7 @@ namespace std #endif // Undefine. -#undef ___glibcxx_base_allocator +#undef __glibcxx_base_allocator } // namespace std #endif diff --git a/libstdc++-v3/include/bits/basic_string.h b/libstdc++-v3/include/bits/basic_string.h index 35dd364d969..07b66d6d615 100644 --- a/libstdc++-v3/include/bits/basic_string.h +++ b/libstdc++-v3/include/bits/basic_string.h @@ -109,17 +109,19 @@ namespace std template<typename _CharT, typename _Traits, typename _Alloc> class basic_string { + typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type; + // Types: public: typedef _Traits traits_type; typedef typename _Traits::char_type value_type; typedef _Alloc allocator_type; - typedef typename _Alloc::size_type size_type; - typedef typename _Alloc::difference_type difference_type; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; + typedef typename _CharT_alloc_type::size_type size_type; + typedef typename _CharT_alloc_type::difference_type difference_type; + typedef typename _CharT_alloc_type::reference reference; + typedef typename _CharT_alloc_type::const_reference const_reference; + typedef typename _CharT_alloc_type::pointer pointer; + typedef typename _CharT_alloc_type::const_pointer const_pointer; typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator; typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string> const_iterator; @@ -151,7 +153,7 @@ namespace std struct _Rep : _Rep_base { // Types: - typedef typename _Alloc::template rebind<size_type>::other _Raw_alloc; + typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc; // (Public) Data members: @@ -198,7 +200,8 @@ namespace std { this->_M_set_sharable(); // One reference. this->_M_length = __n; - this->_M_refdata()[__n] = _S_terminal; // grrr. (per 21.3.4) + traits_type::assign(this->_M_refdata()[__n], _S_terminal); + // grrr. (per 21.3.4) // You cannot leave those LWG people alone for a second. } diff --git a/libstdc++-v3/include/bits/basic_string.tcc b/libstdc++-v3/include/bits/basic_string.tcc index 672457f9be9..41db0dff438 100644 --- a/libstdc++-v3/include/bits/basic_string.tcc +++ b/libstdc++-v3/include/bits/basic_string.tcc @@ -425,10 +425,9 @@ namespace std basic_string<_CharT, _Traits, _Alloc>::_Rep:: _M_destroy(const _Alloc& __a) throw () { - const size_type __size = ((this->_M_capacity + 1) * sizeof(_CharT) - + sizeof(_Rep_base) + sizeof(size_type) - 1); - _Raw_alloc(__a).deallocate(reinterpret_cast<size_type*>(this), __size - / sizeof(size_type)); + const size_type __size = sizeof(_Rep_base) + + (this->_M_capacity + 1) * sizeof(_CharT); + _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); } template<typename _CharT, typename _Traits, typename _Alloc> @@ -569,12 +568,9 @@ namespace std __capacity = 2 * __old_capacity; // NB: Need an array of char_type[__capacity], plus a terminating - // null char_type() element, plus enough for the _Rep data structure, - // plus sizeof(size_type) - 1 to upper round to a size multiple - // of sizeof(size_type). + // null char_type() element, plus enough for the _Rep data structure. // Whew. Seemingly so needy, yet so elemental. - size_type __size = ((__capacity + 1) * sizeof(_CharT) + sizeof(_Rep) - + sizeof(size_type) - 1); + size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); const size_type __adj_size = __size + __malloc_header_size; if (__adj_size > __pagesize && __capacity > __old_capacity) @@ -584,14 +580,12 @@ namespace std // Never allocate a string bigger than _S_max_size. if (__capacity > _S_max_size) __capacity = _S_max_size; - __size = ((__capacity + 1) * sizeof(_CharT) + sizeof(_Rep) - + sizeof(size_type) - 1); + __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); } // NB: Might throw, but no worries about a leak, mate: _Rep() // does not throw. - void* __place = _Raw_alloc(__alloc).allocate(__size - / sizeof(size_type)); + void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); _Rep *__p = new (__place) _Rep; __p->_M_capacity = __capacity; return __p; diff --git a/libstdc++-v3/include/bits/c++config b/libstdc++-v3/include/bits/c++config index 526ab8c7355..16c3194ba67 100644 --- a/libstdc++-v3/include/bits/c++config +++ b/libstdc++-v3/include/bits/c++config @@ -1,6 +1,6 @@ // Predefined symbols and macros -*- C++ -*- -// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 +// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -34,27 +34,6 @@ // Pick up any OS-specific definitions. #include <bits/os_defines.h> -// Allow use of "export template." This is currently not a feature -// that g++ supports. -// #define _GLIBCXX_EXPORT_TEMPLATE 1 - -// Allow use of the GNU syntax extension, "extern template." This -// extension is fully documented in the g++ manual, but in a nutshell, -// it inhibits all implicit instantiations and is used throughout the -// library to avoid multiple weak definitions for required types that -// are already explicitly instantiated in the library binary. This -// substantially reduces the binary size of resulting executables. -#ifndef _GLIBCXX_EXTERN_TEMPLATE -# define _GLIBCXX_EXTERN_TEMPLATE 1 -#endif - -// Certain function definitions that are meant to be overridable from -// user code are decorated with this macro. For some targets, this -// macro causes these definitions to be weak. -#ifndef _GLIBCXX_WEAK_DEFINITION -# define _GLIBCXX_WEAK_DEFINITION -#endif - // Debug mode support. Debug mode basic_string is not allowed to be // associated with std, because of locale and exception link // dependence. @@ -66,7 +45,10 @@ namespace __gnu_debug } #ifdef _GLIBCXX_DEBUG -# define _GLIBCXX_STD __gnu_norm +# if __GXX_WEAK__ +# define _GLIBCXX_STD __gnu_norm +# define _GLIBCXX_EXTERN_TEMPLATE 0 + namespace __gnu_norm { using namespace std; @@ -75,10 +57,33 @@ namespace std { using namespace __gnu_debug_def __attribute__ ((strong)); } +# else +# warning debug mode disabled due to lack of weak symbol support +# endif #else # define _GLIBCXX_STD std #endif +// Allow use of "export template." This is currently not a feature +// that g++ supports. +// #define _GLIBCXX_EXPORT_TEMPLATE 1 + +// Allow use of the GNU syntax extension, "extern template." This +// extension is fully documented in the g++ manual, but in a nutshell, +// it inhibits all implicit instantiations and is used throughout the +// library to avoid multiple weak definitions for required types that +// are already explicitly instantiated in the library binary. This +// substantially reduces the binary size of resulting executables. +#ifndef _GLIBCXX_EXTERN_TEMPLATE +# define _GLIBCXX_EXTERN_TEMPLATE 1 +#endif + +// Certain function definitions that are meant to be overridable from +// user code are decorated with this macro. For some targets, this +// macro causes these definitions to be weak. +#ifndef _GLIBCXX_WEAK_DEFINITION +# define _GLIBCXX_WEAK_DEFINITION +#endif // The remainder of the prewritten config is automatic; all the // user hooks are listed above. diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc index c5440b22419..e69c79a4f34 100644 --- a/libstdc++-v3/include/bits/deque.tcc +++ b/libstdc++-v3/include/bits/deque.tcc @@ -147,7 +147,7 @@ namespace _GLIBCXX_STD std::copy_backward(this->_M_impl._M_start, __first, __last); iterator __new_start = this->_M_impl._M_start + __n; std::_Destroy(this->_M_impl._M_start, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); _M_destroy_nodes(this->_M_impl._M_start._M_node, __new_start._M_node); this->_M_impl._M_start = __new_start; @@ -157,7 +157,7 @@ namespace _GLIBCXX_STD std::copy(__last, this->_M_impl._M_finish, __first); iterator __new_finish = this->_M_impl._M_finish - __n; std::_Destroy(__new_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_destroy_nodes(__new_finish._M_node + 1, this->_M_impl._M_finish._M_node + 1); this->_M_impl._M_finish = __new_finish; @@ -176,7 +176,7 @@ namespace _GLIBCXX_STD ++__node) { std::_Destroy(*__node, *__node + _S_buffer_size(), - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate_node(*__node); } @@ -184,16 +184,16 @@ namespace _GLIBCXX_STD { std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_start._M_last, - this->get_allocator()); + _M_get_Tp_allocator()); std::_Destroy(this->_M_impl._M_finish._M_first, this->_M_impl._M_finish._M_cur, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate_node(this->_M_impl._M_finish._M_first); } else std::_Destroy(this->_M_impl._M_start._M_cur, this->_M_impl._M_finish._M_cur, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = this->_M_impl._M_start; } @@ -201,9 +201,9 @@ namespace _GLIBCXX_STD template <typename _Tp, class _Alloc> template <typename _InputIterator> void - deque<_Tp, _Alloc> - ::_M_assign_aux(_InputIterator __first, _InputIterator __last, - std::input_iterator_tag) + deque<_Tp, _Alloc>:: + _M_assign_aux(_InputIterator __first, _InputIterator __last, + std::input_iterator_tag) { iterator __cur = begin(); for (; __first != __last && __cur != end(); ++__cur, ++__first) @@ -226,7 +226,7 @@ namespace _GLIBCXX_STD { std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, __x, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_start = __new_start; } catch(...) @@ -243,7 +243,7 @@ namespace _GLIBCXX_STD { std::__uninitialized_fill_a(this->_M_impl._M_finish, __new_finish, __x, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = __new_finish; } catch(...) @@ -269,15 +269,15 @@ namespace _GLIBCXX_STD __cur < this->_M_impl._M_finish._M_node; ++__cur) std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), - __value, this->get_allocator()); + __value, _M_get_Tp_allocator()); std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, this->_M_impl._M_finish._M_cur, - __value, this->get_allocator()); + __value, _M_get_Tp_allocator()); } catch(...) { std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), - this->get_allocator()); + _M_get_Tp_allocator()); __throw_exception_again; } } @@ -322,18 +322,18 @@ namespace _GLIBCXX_STD _ForwardIterator __mid = __first; std::advance(__mid, _S_buffer_size()); std::__uninitialized_copy_a(__first, __mid, *__cur_node, - this->get_allocator()); + _M_get_Tp_allocator()); __first = __mid; } std::__uninitialized_copy_a(__first, __last, this->_M_impl._M_finish._M_first, - this->get_allocator()); + _M_get_Tp_allocator()); } catch(...) { std::_Destroy(this->_M_impl._M_start, iterator(*__cur_node, __cur_node), - this->get_allocator()); + _M_get_Tp_allocator()); __throw_exception_again; } } @@ -435,7 +435,7 @@ namespace _GLIBCXX_STD try { std::__uninitialized_copy_a(__first, __last, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_start = __new_start; } catch(...) @@ -452,7 +452,7 @@ namespace _GLIBCXX_STD { std::__uninitialized_copy_a(__first, __last, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = __new_finish; } catch(...) @@ -520,7 +520,7 @@ namespace _GLIBCXX_STD + difference_type(__n)); std::__uninitialized_copy_a(this->_M_impl._M_start, __start_n, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_start = __new_start; std::copy(__start_n, __pos, __old_start); fill(__pos - difference_type(__n), __pos, __x_copy); @@ -531,7 +531,7 @@ namespace _GLIBCXX_STD __pos, __new_start, this->_M_impl._M_start, __x_copy, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_start = __new_start; std::fill(__old_start, __pos, __x_copy); } @@ -559,7 +559,7 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_a(__finish_n, this->_M_impl._M_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = __new_finish; std::copy_backward(__pos, __finish_n, __old_finish); std::fill(__pos, __pos + difference_type(__n), __x_copy); @@ -570,7 +570,7 @@ namespace _GLIBCXX_STD __pos + difference_type(__n), __x_copy, __pos, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = __new_finish; std::fill(__pos, __old_finish, __x_copy); } @@ -607,7 +607,7 @@ namespace _GLIBCXX_STD + difference_type(__n)); std::__uninitialized_copy_a(this->_M_impl._M_start, __start_n, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_start = __new_start; std::copy(__start_n, __pos, __old_start); std::copy(__first, __last, __pos - difference_type(__n)); @@ -619,7 +619,7 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_copy(this->_M_impl._M_start, __pos, __first, __mid, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_start = __new_start; std::copy(__mid, __last, __old_start); } @@ -647,7 +647,7 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_a(__finish_n, this->_M_impl._M_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = __new_finish; std::copy_backward(__pos, __finish_n, __old_finish); std::copy(__first, __last, __pos); @@ -659,7 +659,7 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_copy(__mid, __last, __pos, this->_M_impl._M_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = __new_finish; std::copy(__first, __mid, __pos); } diff --git a/libstdc++-v3/include/bits/fstream.tcc b/libstdc++-v3/include/bits/fstream.tcc index 40bf428e2c1..0228322f2ea 100644 --- a/libstdc++-v3/include/bits/fstream.tcc +++ b/libstdc++-v3/include/bits/fstream.tcc @@ -203,8 +203,7 @@ namespace std return traits_type::to_int_type(*this->gptr()); // Get and convert input sequence. - const size_t __buflen = _M_buf_size > 1 - ? _M_buf_size - 1 : 1; + const size_t __buflen = _M_buf_size > 1 ? _M_buf_size - 1 : 1; // Will be set to true if ::read() returns 0 indicating EOF. bool __got_eof = false; diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc index 59f9d1ad703..d65f73c0bee 100644 --- a/libstdc++-v3/include/bits/list.tcc +++ b/libstdc++-v3/include/bits/list.tcc @@ -1,6 +1,6 @@ // List implementation (out of line) -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -74,7 +74,7 @@ namespace _GLIBCXX_STD { _Node* __tmp = __cur; __cur = static_cast<_Node*>(__cur->_M_next); - this->get_allocator().destroy(&__tmp->_M_data); + _M_get_Tp_allocator().destroy(&__tmp->_M_data); _M_put_node(__tmp); } } @@ -102,7 +102,7 @@ namespace _GLIBCXX_STD template<typename _Tp, typename _Alloc> void list<_Tp, _Alloc>:: - resize(size_type __new_size, const value_type& __x) + resize(size_type __new_size, value_type __x) { iterator __i = begin(); size_type __len = 0; diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index c0eaf5cd516..ee73321f6e2 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -1,6 +1,6 @@ // Algorithm implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -413,9 +413,8 @@ namespace std { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_EqualityComparableConcept< - typename iterator_traits<_InputIterator>::value_type >) - __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); typename iterator_traits<_InputIterator>::difference_type __n = 0; for ( ; __first != __last; ++__first) @@ -627,9 +626,8 @@ namespace std { // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_EqualityComparableConcept< - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_ForwardIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); if (__count <= 0) @@ -918,7 +916,10 @@ namespace std __glibcxx_requires_valid_range(__first, __last); for ( ; __first != __last; ++__first, ++__result) - *__result = *__first == __old_value ? __new_value : *__first; + if (*__first == __old_value) + *__result = __new_value; + else + *__result = *__first; return __result; } @@ -952,7 +953,10 @@ namespace std __glibcxx_requires_valid_range(__first, __last); for ( ; __first != __last; ++__first, ++__result) - *__result = __pred(*__first) ? __new_value : *__first; + if (__pred(*__first)) + *__result = __new_value; + else + *__result = *__first; return __result; } @@ -1637,7 +1641,7 @@ namespace std for (_Distance __i = 0; __i < __d; __i++) { - const _ValueType __tmp = *__first; + _ValueType __tmp = *__first; _RandomAccessIterator __p = __first; if (__k < __l) diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 426fcba0298..a0f7c5041c3 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -94,7 +94,7 @@ namespace std // concept requirements __glibcxx_function_requires(_SGIAssignableConcept<_Tp>) - const _Tp __tmp = __a; + _Tp __tmp = __a; __a = __b; __b = __tmp; } @@ -111,7 +111,7 @@ namespace std { typedef typename iterator_traits<_ForwardIterator1>::value_type _ValueType1; - const _ValueType1 __tmp = *__a; + _ValueType1 __tmp = *__a; *__a = *__b; *__b = __tmp; } diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h index fdee3d5aedf..5a20b657a5f 100644 --- a/libstdc++-v3/include/bits/stl_deque.h +++ b/libstdc++-v3/include/bits/stl_deque.h @@ -358,7 +358,7 @@ namespace _GLIBCXX_STD allocator_type get_allocator() const - { return *static_cast<const _Alloc*>(&this->_M_impl); } + { return _M_get_Tp_allocator(); } typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator; typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; @@ -377,30 +377,43 @@ namespace _GLIBCXX_STD //This struct encapsulates the implementation of the std::deque //standard container and at the same time makes use of the EBO //for empty allocators. + typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type; + + typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; + struct _Deque_impl - : public _Alloc + : public _Tp_alloc_type { _Tp** _M_map; size_t _M_map_size; iterator _M_start; iterator _M_finish; - _Deque_impl(const _Alloc& __a) - : _Alloc(__a), _M_map(0), _M_map_size(0), _M_start(), _M_finish() + _Deque_impl(const _Tp_alloc_type& __a) + : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0), + _M_start(), _M_finish() { } }; - typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type; - _Map_alloc_type _M_get_map_allocator() const - { return _Map_alloc_type(this->get_allocator()); } + _Tp_alloc_type + _M_get_Tp_allocator() const + { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } + + _Map_alloc_type + _M_get_map_allocator() const + { return _M_get_Tp_allocator(); } _Tp* _M_allocate_node() - { return _M_impl._Alloc::allocate(__deque_buf_size(sizeof(_Tp))); } + { + return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); + } void _M_deallocate_node(_Tp* __p) - { _M_impl._Alloc::deallocate(__p, __deque_buf_size(sizeof(_Tp))); } + { + _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); + } _Tp** _M_allocate_map(size_t __n) @@ -595,23 +608,26 @@ namespace _GLIBCXX_STD class deque : protected _Deque_base<_Tp, _Alloc> { // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Tp, _SGIAssignableConcept) + __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) typedef _Deque_base<_Tp, _Alloc> _Base; + typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; public: - typedef _Tp value_type; - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; - typedef typename _Base::iterator iterator; - typedef typename _Base::const_iterator const_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; + typedef _Tp value_type; + typedef typename _Tp_alloc_type::pointer pointer; + typedef typename _Tp_alloc_type::const_pointer const_pointer; + typedef typename _Tp_alloc_type::reference reference; + typedef typename _Tp_alloc_type::const_reference const_reference; + typedef typename _Base::iterator iterator; + typedef typename _Base::const_iterator const_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; - typedef typename _Base::allocator_type allocator_type; + typedef _Alloc allocator_type; protected: typedef pointer* _Map_pointer; @@ -627,6 +643,7 @@ namespace _GLIBCXX_STD using _Base::_M_deallocate_node; using _Base::_M_allocate_map; using _Base::_M_deallocate_map; + using _Base::_M_get_Tp_allocator; /** @if maint * A total of four data members accumulated down the heirarchy. @@ -652,24 +669,13 @@ namespace _GLIBCXX_STD * * This constructor fills the %deque with @a n copies of @a value. */ - deque(size_type __n, const value_type& __value, + explicit + deque(size_type __n, const value_type& __value = value_type(), const allocator_type& __a = allocator_type()) : _Base(__a, __n) { _M_fill_initialize(__value); } /** - * @brief Create a %deque with default elements. - * @param n The number of elements to initially create. - * - * This constructor fills the %deque with @a n copies of a - * default-constructed element. - */ - explicit - deque(size_type __n) - : _Base(allocator_type(), __n) - { _M_fill_initialize(value_type()); } - - /** * @brief %Deque copy constructor. * @param x A %deque of identical element and allocator types. * @@ -680,7 +686,7 @@ namespace _GLIBCXX_STD : _Base(__x.get_allocator(), __x.size()) { std::__uninitialized_copy_a(__x.begin(), __x.end(), this->_M_impl._M_start, - this->get_allocator()); } + _M_get_Tp_allocator()); } /** * @brief Builds a %deque from a range. @@ -713,7 +719,7 @@ namespace _GLIBCXX_STD */ ~deque() { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, - this->get_allocator()); } + _M_get_Tp_allocator()); } /** * @brief %Deque assignment operator. @@ -857,7 +863,7 @@ namespace _GLIBCXX_STD * data. */ void - resize(size_type __new_size, const value_type& __x) + resize(size_type __new_size, value_type __x = value_type()) { const size_type __len = size(); if (__new_size < __len) @@ -867,19 +873,6 @@ namespace _GLIBCXX_STD } /** - * @brief Resizes the %deque to the specified number of elements. - * @param new_size Number of elements the %deque should contain. - * - * This function will resize the %deque to the specified number - * of elements. If the number is smaller than the %deque's - * current size the %deque is truncated, otherwise the %deque - * is extended and new elements are default-constructed. - */ - void - resize(size_type new_size) - { resize(new_size, value_type()); } - - /** * Returns true if the %deque is empty. (Thus begin() would * equal end().) */ diff --git a/libstdc++-v3/include/bits/stl_function.h b/libstdc++-v3/include/bits/stl_function.h index 74ddcce9d8b..fbd22c3c8b5 100644 --- a/libstdc++-v3/include/bits/stl_function.h +++ b/libstdc++-v3/include/bits/stl_function.h @@ -1,6 +1,6 @@ // Functor implementations -*- C++ -*- -// Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -88,7 +88,7 @@ namespace std * \endcode * The addition and negation functions will be inlined directly. * - * The standard functiors are derived from structs named @c unary_function + * The standard functors are derived from structs named @c unary_function * and @c binary_function. These two classes contain nothing but typedefs, * to aid in generic (template) programming. If you write your own * functors, you might consider doing the same. @@ -360,7 +360,7 @@ namespace std /** @defgroup s20_3_6_binder Binder Classes * Binders turn functions/functors with two arguments into functors with * a single argument, storing an argument to be applied later. For - * example, an variable @c B of type @c binder1st is constructed from a + * example, a variable @c B of type @c binder1st is constructed from a * functor @c f and an argument @c x. Later, B's @c operator() is called * with a single argument @c y. The return value is the value of @c f(x,y). * @c B can be "called" with various arguments (y1, y2, ...) and will in diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h index ce167ef80e4..e17ec2b4606 100644 --- a/libstdc++-v3/include/bits/stl_list.h +++ b/libstdc++-v3/include/bits/stl_list.h @@ -290,18 +290,19 @@ namespace _GLIBCXX_STD // // We put this to the test in the constructors and in // get_allocator, where we use conversions between - // allocator_type and _Node_Alloc_type. The conversion is + // allocator_type and _Node_alloc_type. The conversion is // required by table 32 in [20.1.5]. typedef typename _Alloc::template rebind<_List_node<_Tp> >::other + _Node_alloc_type; - _Node_Alloc_type; + typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; struct _List_impl - : public _Node_Alloc_type + : public _Node_alloc_type { _List_node_base _M_node; - _List_impl (const _Node_Alloc_type& __a) - : _Node_Alloc_type(__a) + _List_impl(const _Node_alloc_type& __a) + : _Node_alloc_type(__a) { } }; @@ -309,19 +310,22 @@ namespace _GLIBCXX_STD _List_node<_Tp>* _M_get_node() - { return _M_impl._Node_Alloc_type::allocate(1); } + { return _M_impl._Node_alloc_type::allocate(1); } void _M_put_node(_List_node<_Tp>* __p) - { _M_impl._Node_Alloc_type::deallocate(__p, 1); } + { _M_impl._Node_alloc_type::deallocate(__p, 1); } public: typedef _Alloc allocator_type; + _Tp_alloc_type + _M_get_Tp_allocator() const + { return *static_cast<const _Node_alloc_type*>(&this->_M_impl); } + allocator_type get_allocator() const - { return allocator_type(*static_cast< - const _Node_Alloc_type*>(&this->_M_impl)); } + { return _M_get_Tp_allocator(); } _List_base(const allocator_type& __a) : _M_impl(__a) @@ -391,28 +395,31 @@ namespace _GLIBCXX_STD class list : protected _List_base<_Tp, _Alloc> { // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Tp, _SGIAssignableConcept) + __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) - typedef _List_base<_Tp, _Alloc> _Base; + typedef _List_base<_Tp, _Alloc> _Base; + typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; public: typedef _Tp value_type; - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; + typedef typename _Tp_alloc_type::pointer pointer; + typedef typename _Tp_alloc_type::const_pointer const_pointer; + typedef typename _Tp_alloc_type::reference reference; + typedef typename _Tp_alloc_type::const_reference const_reference; typedef _List_iterator<_Tp> iterator; typedef _List_const_iterator<_Tp> const_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; - typedef typename _Base::allocator_type allocator_type; + typedef _Alloc allocator_type; protected: // Note that pointers-to-_Node's can be ctor-converted to // iterator types. - typedef _List_node<_Tp> _Node; + typedef _List_node<_Tp> _Node; /** @if maint * One data member plus two memory-handling functions. If the @@ -423,6 +430,7 @@ namespace _GLIBCXX_STD using _Base::_M_impl; using _Base::_M_put_node; using _Base::_M_get_node; + using _Base::_M_get_Tp_allocator; /** * @if maint @@ -437,7 +445,7 @@ namespace _GLIBCXX_STD _Node* __p = this->_M_get_node(); try { - this->get_allocator().construct(&__p->_M_data, __x); + _M_get_Tp_allocator().construct(&__p->_M_data, __x); } catch(...) { @@ -464,24 +472,13 @@ namespace _GLIBCXX_STD * * This constructor fills the %list with @a n copies of @a value. */ - list(size_type __n, const value_type& __value, + explicit + list(size_type __n, const value_type& __value = value_type(), const allocator_type& __a = allocator_type()) : _Base(__a) { this->insert(begin(), __n, __value); } /** - * @brief Create a %list with default elements. - * @param n The number of elements to initially create. - * - * This constructor fills the %list with @a n copies of a - * default-constructed element. - */ - explicit - list(size_type __n) - : _Base(allocator_type()) - { this->insert(begin(), __n, value_type()); } - - /** * @brief %List copy constructor. * @param x A %list of identical element and allocator types. * @@ -671,20 +668,7 @@ namespace _GLIBCXX_STD * extended and new elements are populated with given data. */ void - resize(size_type __new_size, const value_type& __x); - - /** - * @brief Resizes the %list to the specified number of elements. - * @param new_size Number of elements the %list should contain. - * - * This function will resize the %list to the specified number of - * elements. If the number is smaller than the %list's current - * size the %list is truncated, otherwise the %list is extended - * and new elements are default-constructed. - */ - void - resize(size_type __new_size) - { this->resize(__new_size, value_type()); } + resize(size_type __new_size, value_type __x = value_type()); // element access /** @@ -1158,7 +1142,7 @@ namespace _GLIBCXX_STD { __position._M_node->unhook(); _Node* __n = static_cast<_Node*>(__position._M_node); - this->get_allocator().destroy(&__n->_M_data); + _M_get_Tp_allocator().destroy(&__n->_M_data); _M_put_node(__n); } }; diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h index a0834a763bc..5f4be568a69 100644 --- a/libstdc++-v3/include/bits/stl_map.h +++ b/libstdc++-v3/include/bits/stl_map.h @@ -90,21 +90,26 @@ namespace _GLIBCXX_STD typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > > class map { - // concept requirements - __glibcxx_class_requires(_Tp, _SGIAssignableConcept) - __glibcxx_class_requires4(_Compare, bool, _Key, _Key, - _BinaryFunctionConcept) - public: typedef _Key key_type; typedef _Tp mapped_type; typedef std::pair<const _Key, _Tp> value_type; typedef _Compare key_compare; + typedef _Alloc allocator_type; + + private: + // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; + __glibcxx_class_requires(_Tp, _SGIAssignableConcept) + __glibcxx_class_requires4(_Compare, bool, _Key, _Key, + _BinaryFunctionConcept) + __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) + public: class value_compare : public std::binary_function<value_type, value_type, bool> { - friend class map<_Key,_Tp,_Compare,_Alloc>; + friend class map<_Key, _Tp, _Compare, _Alloc>; protected: _Compare comp; @@ -118,19 +123,22 @@ namespace _GLIBCXX_STD private: /// @if maint This turns a red-black tree into a [multi]map. @endif - typedef _Rb_tree<key_type, value_type, - _Select1st<value_type>, key_compare, _Alloc> _Rep_type; + typedef typename _Alloc::template rebind<value_type>::other + _Pair_alloc_type; + + typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, + key_compare, _Pair_alloc_type> _Rep_type; + /// @if maint The actual tree structure. @endif _Rep_type _M_t; public: // many of these are specified differently in ISO, but the following are // "functionally equivalent" - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; - typedef typename _Rep_type::allocator_type allocator_type; + typedef typename _Pair_alloc_type::pointer pointer; + typedef typename _Pair_alloc_type::const_pointer const_pointer; + typedef typename _Pair_alloc_type::reference reference; + typedef typename _Pair_alloc_type::const_reference const_reference; typedef typename _Rep_type::iterator iterator; typedef typename _Rep_type::const_iterator const_iterator; typedef typename _Rep_type::size_type size_type; @@ -589,7 +597,7 @@ namespace _GLIBCXX_STD * * This function probably only makes sense for multimaps. */ - std::pair<iterator,iterator> + std::pair<iterator, iterator> equal_range(const key_type& __x) { return _M_t.equal_range(__x); } @@ -608,19 +616,19 @@ namespace _GLIBCXX_STD * * This function probably only makes sense for multimaps. */ - std::pair<const_iterator,const_iterator> + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } template <typename _K1, typename _T1, typename _C1, typename _A1> friend bool - operator== (const map<_K1,_T1,_C1,_A1>&, - const map<_K1,_T1,_C1,_A1>&); + operator== (const map<_K1, _T1, _C1, _A1>&, + const map<_K1, _T1, _C1, _A1>&); template <typename _K1, typename _T1, typename _C1, typename _A1> friend bool - operator< (const map<_K1,_T1,_C1,_A1>&, - const map<_K1,_T1,_C1,_A1>&); + operator< (const map<_K1, _T1, _C1, _A1>&, + const map<_K1, _T1, _C1, _A1>&); }; /** @@ -635,8 +643,8 @@ namespace _GLIBCXX_STD */ template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator==(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return __x._M_t == __y._M_t; } /** @@ -652,42 +660,43 @@ namespace _GLIBCXX_STD */ template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator<(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator<(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return __x._M_t < __y._M_t; } /// Based on operator== template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator!=(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator!=(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__x == __y); } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator>(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator>(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return __y < __x; } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator<=(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator<=(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__y < __x); } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator>=(const map<_Key,_Tp,_Compare,_Alloc>& __x, - const map<_Key,_Tp,_Compare,_Alloc>& __y) + operator>=(const map<_Key, _Tp, _Compare, _Alloc>& __x, + const map<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__x < __y); } /// See std::map::swap(). template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline void - swap(map<_Key,_Tp,_Compare,_Alloc>& __x, map<_Key,_Tp,_Compare,_Alloc>& __y) + swap(map<_Key, _Tp, _Compare, _Alloc>& __x, + map<_Key, _Tp, _Compare, _Alloc>& __y) { __x.swap(__y); } } // namespace std diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h index 524b2366813..dca95563343 100644 --- a/libstdc++-v3/include/bits/stl_multimap.h +++ b/libstdc++-v3/include/bits/stl_multimap.h @@ -74,13 +74,13 @@ namespace _GLIBCXX_STD template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y); + operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y); template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y); + operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y); /** * @brief A standard container made up of (key,value) pairs, which can be @@ -106,21 +106,26 @@ namespace _GLIBCXX_STD template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> class multimap { - // concept requirements - __glibcxx_class_requires(_Tp, _SGIAssignableConcept) - __glibcxx_class_requires4(_Compare, bool, _Key, _Key, - _BinaryFunctionConcept) - public: typedef _Key key_type; typedef _Tp mapped_type; typedef std::pair<const _Key, _Tp> value_type; typedef _Compare key_compare; + typedef _Alloc allocator_type; + private: + // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; + __glibcxx_class_requires(_Tp, _SGIAssignableConcept) + __glibcxx_class_requires4(_Compare, bool, _Key, _Key, + _BinaryFunctionConcept) + __glibcxx_class_requires2(value_type, _Alloc_value_type, _SameTypeConcept) + + public: class value_compare : public std::binary_function<value_type, value_type, bool> { - friend class multimap<_Key,_Tp,_Compare,_Alloc>; + friend class multimap<_Key, _Tp, _Compare, _Alloc>; protected: _Compare comp; @@ -134,19 +139,21 @@ namespace _GLIBCXX_STD private: /// @if maint This turns a red-black tree into a [multi]map. @endif - typedef _Rb_tree<key_type, value_type, - _Select1st<value_type>, key_compare, _Alloc> _Rep_type; + typedef typename _Alloc::template rebind<value_type>::other + _Pair_alloc_type; + + typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, + key_compare, _Pair_alloc_type> _Rep_type; /// @if maint The actual tree structure. @endif _Rep_type _M_t; public: // many of these are specified differently in ISO, but the following are // "functionally equivalent" - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; - typedef typename _Rep_type::allocator_type allocator_type; + typedef typename _Pair_alloc_type::pointer pointer; + typedef typename _Pair_alloc_type::const_pointer const_pointer; + typedef typename _Pair_alloc_type::reference reference; + typedef typename _Pair_alloc_type::const_reference const_reference; typedef typename _Rep_type::iterator iterator; typedef typename _Rep_type::const_iterator const_iterator; typedef typename _Rep_type::size_type size_type; @@ -573,7 +580,7 @@ namespace _GLIBCXX_STD * @endcode * (but is faster than making the calls separately). */ - std::pair<iterator,iterator> + std::pair<iterator, iterator> equal_range(const key_type& __x) { return _M_t.equal_range(__x); } @@ -590,19 +597,19 @@ namespace _GLIBCXX_STD * @endcode * (but is faster than making the calls separately). */ - std::pair<const_iterator,const_iterator> + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } template <typename _K1, typename _T1, typename _C1, typename _A1> friend bool - operator== (const multimap<_K1,_T1,_C1,_A1>&, - const multimap<_K1,_T1,_C1,_A1>&); + operator== (const multimap<_K1, _T1, _C1, _A1>&, + const multimap<_K1, _T1, _C1, _A1>&); template <typename _K1, typename _T1, typename _C1, typename _A1> friend bool - operator< (const multimap<_K1,_T1,_C1,_A1>&, - const multimap<_K1,_T1,_C1,_A1>&); + operator< (const multimap<_K1, _T1, _C1, _A1>&, + const multimap<_K1, _T1, _C1, _A1>&); }; /** @@ -617,8 +624,8 @@ namespace _GLIBCXX_STD */ template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator==(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y) + operator==(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y) { return __x._M_t == __y._M_t; } /** @@ -634,43 +641,43 @@ namespace _GLIBCXX_STD */ template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator<(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y) + operator<(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y) { return __x._M_t < __y._M_t; } /// Based on operator== template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator!=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y) + operator!=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__x == __y); } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator>(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y) + operator>(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y) { return __y < __x; } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator<=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y) + operator<=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__y < __x); } /// Based on operator< template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline bool - operator>=(const multimap<_Key,_Tp,_Compare,_Alloc>& __x, - const multimap<_Key,_Tp,_Compare,_Alloc>& __y) + operator>=(const multimap<_Key, _Tp, _Compare, _Alloc>& __x, + const multimap<_Key, _Tp, _Compare, _Alloc>& __y) { return !(__x < __y); } /// See std::multimap::swap(). template <typename _Key, typename _Tp, typename _Compare, typename _Alloc> inline void - swap(multimap<_Key,_Tp,_Compare,_Alloc>& __x, - multimap<_Key,_Tp,_Compare,_Alloc>& __y) + swap(multimap<_Key, _Tp, _Compare, _Alloc>& __x, + multimap<_Key, _Tp, _Compare, _Alloc>& __y) { __x.swap(__y); } } // namespace std diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h index 3f42ef4c38d..f401db76fd5 100644 --- a/libstdc++-v3/include/bits/stl_multiset.h +++ b/libstdc++-v3/include/bits/stl_multiset.h @@ -73,13 +73,13 @@ namespace _GLIBCXX_STD template <class _Key, class _Compare, class _Alloc> inline bool - operator==(const multiset<_Key,_Compare,_Alloc>& __x, - const multiset<_Key,_Compare,_Alloc>& __y); + operator==(const multiset<_Key, _Compare, _Alloc>& __x, + const multiset<_Key, _Compare, _Alloc>& __y); template <class _Key, class _Compare, class _Alloc> inline bool - operator<(const multiset<_Key,_Compare,_Alloc>& __x, - const multiset<_Key,_Compare,_Alloc>& __y); + operator<(const multiset<_Key, _Compare, _Alloc>& __x, + const multiset<_Key, _Compare, _Alloc>& __y); /** * @brief A standard container made up of elements, which can be retrieved @@ -105,9 +105,11 @@ namespace _GLIBCXX_STD class multiset { // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Key, _SGIAssignableConcept) __glibcxx_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept) + __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) public: // typedefs: @@ -115,35 +117,37 @@ namespace _GLIBCXX_STD typedef _Key value_type; typedef _Compare key_compare; typedef _Compare value_compare; + typedef _Alloc allocator_type; private: /// @if maint This turns a red-black tree into a [multi]set. @endif - typedef _Rb_tree<key_type, value_type, - _Identity<value_type>, key_compare, _Alloc> _Rep_type; + typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type; + + typedef _Rb_tree<key_type, value_type, _Identity<value_type>, + key_compare, _Key_alloc_type> _Rep_type; /// @if maint The actual tree structure. @endif _Rep_type _M_t; public: - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; + typedef typename _Key_alloc_type::pointer pointer; + typedef typename _Key_alloc_type::const_pointer const_pointer; + typedef typename _Key_alloc_type::reference reference; + typedef typename _Key_alloc_type::const_reference const_reference; // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 103. set::iterator is required to be modifiable, // but this allows modification of keys. - typedef typename _Rep_type::const_iterator iterator; - typedef typename _Rep_type::const_iterator const_iterator; - typedef typename _Rep_type::const_reverse_iterator reverse_iterator; - typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; - typedef typename _Rep_type::size_type size_type; - typedef typename _Rep_type::difference_type difference_type; - typedef typename _Rep_type::allocator_type allocator_type; - - // allocation/deallocation - - /** - * @brief Default constructor creates no elements. - */ + typedef typename _Rep_type::const_iterator iterator; + typedef typename _Rep_type::const_iterator const_iterator; + typedef typename _Rep_type::const_reverse_iterator reverse_iterator; + typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; + typedef typename _Rep_type::size_type size_type; + typedef typename _Rep_type::difference_type difference_type; + + // allocation/deallocation + + /** + * @brief Default constructor creates no elements. + */ multiset() : _M_t(_Compare(), allocator_type()) { } @@ -286,7 +290,7 @@ namespace _GLIBCXX_STD * std::swap(s1,s2) will feed to this function. */ void - swap(multiset<_Key,_Compare,_Alloc>& __x) + swap(multiset<_Key, _Compare, _Alloc>& __x) { _M_t.swap(__x._M_t); } // insert/erase @@ -492,23 +496,23 @@ namespace _GLIBCXX_STD * * This function probably only makes sense for multisets. */ - std::pair<iterator,iterator> + std::pair<iterator, iterator> equal_range(const key_type& __x) { return _M_t.equal_range(__x); } - std::pair<const_iterator,const_iterator> + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } template <class _K1, class _C1, class _A1> friend bool - operator== (const multiset<_K1,_C1,_A1>&, - const multiset<_K1,_C1,_A1>&); + operator== (const multiset<_K1, _C1, _A1>&, + const multiset<_K1, _C1, _A1>&); template <class _K1, class _C1, class _A1> friend bool - operator< (const multiset<_K1,_C1,_A1>&, - const multiset<_K1,_C1,_A1>&); + operator< (const multiset<_K1, _C1, _A1>&, + const multiset<_K1, _C1, _A1>&); }; /** @@ -524,8 +528,8 @@ namespace _GLIBCXX_STD */ template <class _Key, class _Compare, class _Alloc> inline bool - operator==(const multiset<_Key,_Compare,_Alloc>& __x, - const multiset<_Key,_Compare,_Alloc>& __y) + operator==(const multiset<_Key, _Compare, _Alloc>& __x, + const multiset<_Key, _Compare, _Alloc>& __y) { return __x._M_t == __y._M_t; } /** @@ -541,15 +545,15 @@ namespace _GLIBCXX_STD */ template <class _Key, class _Compare, class _Alloc> inline bool - operator<(const multiset<_Key,_Compare,_Alloc>& __x, - const multiset<_Key,_Compare,_Alloc>& __y) + operator<(const multiset<_Key, _Compare, _Alloc>& __x, + const multiset<_Key, _Compare, _Alloc>& __y) { return __x._M_t < __y._M_t; } /// Returns !(x == y). template <class _Key, class _Compare, class _Alloc> inline bool - operator!=(const multiset<_Key,_Compare,_Alloc>& __x, - const multiset<_Key,_Compare,_Alloc>& __y) + operator!=(const multiset<_Key, _Compare, _Alloc>& __x, + const multiset<_Key, _Compare, _Alloc>& __y) { return !(__x == __y); } /// Returns y < x. @@ -562,22 +566,22 @@ namespace _GLIBCXX_STD /// Returns !(y < x) template <class _Key, class _Compare, class _Alloc> inline bool - operator<=(const multiset<_Key,_Compare,_Alloc>& __x, - const multiset<_Key,_Compare,_Alloc>& __y) + operator<=(const multiset<_Key, _Compare, _Alloc>& __x, + const multiset<_Key, _Compare, _Alloc>& __y) { return !(__y < __x); } /// Returns !(x < y) template <class _Key, class _Compare, class _Alloc> inline bool - operator>=(const multiset<_Key,_Compare,_Alloc>& __x, - const multiset<_Key,_Compare,_Alloc>& __y) + operator>=(const multiset<_Key, _Compare, _Alloc>& __x, + const multiset<_Key, _Compare, _Alloc>& __y) { return !(__x < __y); } /// See std::multiset::swap(). template <class _Key, class _Compare, class _Alloc> inline void - swap(multiset<_Key,_Compare,_Alloc>& __x, - multiset<_Key,_Compare,_Alloc>& __y) + swap(multiset<_Key, _Compare, _Alloc>& __x, + multiset<_Key, _Compare, _Alloc>& __y) { __x.swap(__y); } } // namespace std diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h index 1a15d1172c8..c76e55475c6 100644 --- a/libstdc++-v3/include/bits/stl_set.h +++ b/libstdc++-v3/include/bits/stl_set.h @@ -72,13 +72,13 @@ namespace _GLIBCXX_STD template<class _Key, class _Compare, class _Alloc> inline bool - operator==(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y); + operator==(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y); template<class _Key, class _Compare, class _Alloc> inline bool - operator<(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y); + operator<(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y); /** * @brief A standard container made up of unique keys, which can be @@ -107,9 +107,11 @@ namespace _GLIBCXX_STD class set { // concept requirements + typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Key, _SGIAssignableConcept) __glibcxx_class_requires4(_Compare, bool, _Key, _Key, _BinaryFunctionConcept) + __glibcxx_class_requires2(_Key, _Alloc_value_type, _SameTypeConcept) public: // typedefs: @@ -119,29 +121,32 @@ namespace _GLIBCXX_STD typedef _Key value_type; typedef _Compare key_compare; typedef _Compare value_compare; + typedef _Alloc allocator_type; //@} private: - typedef _Rb_tree<key_type, value_type, - _Identity<value_type>, key_compare, _Alloc> _Rep_type; + typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type; + + typedef _Rb_tree<key_type, value_type, _Identity<value_type>, + key_compare, _Key_alloc_type> _Rep_type; _Rep_type _M_t; // red-black tree representing set + public: //@{ /// Iterator-related typedefs. - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; + typedef typename _Key_alloc_type::pointer pointer; + typedef typename _Key_alloc_type::const_pointer const_pointer; + typedef typename _Key_alloc_type::reference reference; + typedef typename _Key_alloc_type::const_reference const_reference; // _GLIBCXX_RESOLVE_LIB_DEFECTS // DR 103. set::iterator is required to be modifiable, // but this allows modification of keys. - typedef typename _Rep_type::const_iterator iterator; - typedef typename _Rep_type::const_iterator const_iterator; - typedef typename _Rep_type::const_reverse_iterator reverse_iterator; - typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; - typedef typename _Rep_type::size_type size_type; - typedef typename _Rep_type::difference_type difference_type; - typedef typename _Rep_type::allocator_type allocator_type; + typedef typename _Rep_type::const_iterator iterator; + typedef typename _Rep_type::const_iterator const_iterator; + typedef typename _Rep_type::const_reverse_iterator reverse_iterator; + typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator; + typedef typename _Rep_type::size_type size_type; + typedef typename _Rep_type::difference_type difference_type; //@} // allocation/deallocation @@ -155,8 +160,9 @@ namespace _GLIBCXX_STD * @param comp Comparator to use. * @param a Allocator to use. */ - explicit set(const _Compare& __comp, - const allocator_type& __a = allocator_type()) + explicit + set(const _Compare& __comp, + const allocator_type& __a = allocator_type()) : _M_t(__comp, __a) {} /** @@ -503,22 +509,22 @@ namespace _GLIBCXX_STD * * This function probably only makes sense for multisets. */ - std::pair<iterator,iterator> + std::pair<iterator, iterator> equal_range(const key_type& __x) { return _M_t.equal_range(__x); } - std::pair<const_iterator,const_iterator> + std::pair<const_iterator, const_iterator> equal_range(const key_type& __x) const { return _M_t.equal_range(__x); } //@} template<class _K1, class _C1, class _A1> friend bool - operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); + operator== (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); template<class _K1, class _C1, class _A1> friend bool - operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&); + operator< (const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); }; @@ -534,8 +540,8 @@ namespace _GLIBCXX_STD */ template<class _Key, class _Compare, class _Alloc> inline bool - operator==(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator==(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return __x._M_t == __y._M_t; } /** @@ -551,42 +557,42 @@ namespace _GLIBCXX_STD */ template<class _Key, class _Compare, class _Alloc> inline bool - operator<(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator<(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return __x._M_t < __y._M_t; } /// Returns !(x == y). template<class _Key, class _Compare, class _Alloc> inline bool - operator!=(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator!=(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return !(__x == __y); } /// Returns y < x. template<class _Key, class _Compare, class _Alloc> inline bool - operator>(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator>(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return __y < __x; } /// Returns !(y < x) template<class _Key, class _Compare, class _Alloc> inline bool - operator<=(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator<=(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return !(__y < __x); } /// Returns !(x < y) template<class _Key, class _Compare, class _Alloc> inline bool - operator>=(const set<_Key,_Compare,_Alloc>& __x, - const set<_Key,_Compare,_Alloc>& __y) + operator>=(const set<_Key, _Compare, _Alloc>& __x, + const set<_Key, _Compare, _Alloc>& __y) { return !(__x < __y); } /// See std::set::swap(). template<class _Key, class _Compare, class _Alloc> inline void - swap(set<_Key,_Compare,_Alloc>& __x, set<_Key,_Compare,_Alloc>& __y) + swap(set<_Key, _Compare, _Alloc>& __x, set<_Key, _Compare, _Alloc>& __y) { __x.swap(__y); } } // namespace std diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h index d532c2dc910..06b94017c01 100644 --- a/libstdc++-v3/include/bits/stl_vector.h +++ b/libstdc++-v3/include/bits/stl_vector.h @@ -75,23 +75,29 @@ namespace _GLIBCXX_STD template<typename _Tp, typename _Alloc> struct _Vector_base { + typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; + struct _Vector_impl - : public _Alloc + : public _Tp_alloc_type { _Tp* _M_start; _Tp* _M_finish; _Tp* _M_end_of_storage; - _Vector_impl(_Alloc const& __a) - : _Alloc(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) + _Vector_impl(_Tp_alloc_type const& __a) + : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) { } }; public: typedef _Alloc allocator_type; + _Tp_alloc_type + _M_get_Tp_allocator() const + { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); } + allocator_type get_allocator() const - { return *static_cast<const _Alloc*>(&this->_M_impl); } + { return _M_get_Tp_allocator(); } _Vector_base(const allocator_type& __a) : _M_impl(__a) @@ -148,17 +154,20 @@ namespace _GLIBCXX_STD class vector : protected _Vector_base<_Tp, _Alloc> { // Concept requirements. + typedef typename _Alloc::value_type _Alloc_value_type; __glibcxx_class_requires(_Tp, _SGIAssignableConcept) - - typedef _Vector_base<_Tp, _Alloc> _Base; - typedef vector<_Tp, _Alloc> vector_type; + __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) + + typedef _Vector_base<_Tp, _Alloc> _Base; + typedef vector<_Tp, _Alloc> vector_type; + typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; public: typedef _Tp value_type; - typedef typename _Alloc::pointer pointer; - typedef typename _Alloc::const_pointer const_pointer; - typedef typename _Alloc::reference reference; - typedef typename _Alloc::const_reference const_reference; + typedef typename _Tp_alloc_type::pointer pointer; + typedef typename _Tp_alloc_type::const_pointer const_pointer; + typedef typename _Tp_alloc_type::reference reference; + typedef typename _Tp_alloc_type::const_reference const_reference; typedef __gnu_cxx::__normal_iterator<pointer, vector_type> iterator; typedef __gnu_cxx::__normal_iterator<const_pointer, vector_type> const_iterator; @@ -166,7 +175,7 @@ namespace _GLIBCXX_STD typedef std::reverse_iterator<iterator> reverse_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; - typedef typename _Base::allocator_type allocator_type; + typedef _Alloc allocator_type; protected: /** @if maint @@ -177,6 +186,7 @@ namespace _GLIBCXX_STD using _Base::_M_allocate; using _Base::_M_deallocate; using _Base::_M_impl; + using _Base::_M_get_Tp_allocator; public: // [23.2.4.1] construct/copy/destroy @@ -196,32 +206,17 @@ namespace _GLIBCXX_STD * * This constructor fills the %vector with @a n copies of @a value. */ - vector(size_type __n, const value_type& __value, + explicit + vector(size_type __n, const value_type& __value = value_type(), const allocator_type& __a = allocator_type()) : _Base(__n, __a) { std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = this->_M_impl._M_start + __n; } /** - * @brief Create a %vector with default elements. - * @param n The number of elements to initially create. - * - * This constructor fills the %vector with @a n copies of a - * default-constructed element. - */ - explicit - vector(size_type __n) - : _Base(__n, allocator_type()) - { - std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, value_type(), - this->get_allocator()); - this->_M_impl._M_finish = this->_M_impl._M_start + __n; - } - - /** * @brief %Vector copy constructor. * @param x A %vector of identical element and allocator types. * @@ -235,7 +230,7 @@ namespace _GLIBCXX_STD { this->_M_impl._M_finish = std::__uninitialized_copy_a(__x.begin(), __x.end(), this->_M_impl._M_start, - this->get_allocator()); + _M_get_Tp_allocator()); } /** @@ -271,7 +266,7 @@ namespace _GLIBCXX_STD */ ~vector() { std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); } /** @@ -419,7 +414,7 @@ namespace _GLIBCXX_STD * given data. */ void - resize(size_type __new_size, const value_type& __x) + resize(size_type __new_size, value_type __x = value_type()) { if (__new_size < size()) erase(begin() + __new_size, end()); @@ -428,20 +423,6 @@ namespace _GLIBCXX_STD } /** - * @brief Resizes the %vector to the specified number of elements. - * @param new_size Number of elements the %vector should contain. - * - * This function will resize the %vector to the specified - * number of elements. If the number is smaller than the - * %vector's current size the %vector is truncated, otherwise - * the %vector is extended and new elements are - * default-constructed. - */ - void - resize(size_type __new_size) - { resize(__new_size, value_type()); } - - /** * Returns the total number of elements that the %vector can * hold before needing to allocate more memory. */ @@ -764,7 +745,7 @@ namespace _GLIBCXX_STD try { std::__uninitialized_copy_a(__first, __last, __result, - this->get_allocator()); + _M_get_Tp_allocator()); return __result; } catch(...) @@ -785,7 +766,7 @@ namespace _GLIBCXX_STD this->_M_impl._M_start = _M_allocate(__n); this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish = this->_M_impl._M_end_of_storage; } @@ -822,7 +803,7 @@ namespace _GLIBCXX_STD this->_M_impl._M_finish = std::__uninitialized_copy_a(__first, __last, this->_M_impl._M_start, - this->get_allocator()); + _M_get_Tp_allocator()); } diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc index f9f5e5ac8a7..aa1634bbc5e 100644 --- a/libstdc++-v3/include/bits/vector.tcc +++ b/libstdc++-v3/include/bits/vector.tcc @@ -77,7 +77,7 @@ namespace _GLIBCXX_STD this->_M_impl._M_start, this->_M_impl._M_finish); std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); @@ -122,7 +122,7 @@ namespace _GLIBCXX_STD erase(iterator __first, iterator __last) { iterator __i(std::copy(__last, end(), __first)); - std::_Destroy(__i, end(), this->get_allocator()); + std::_Destroy(__i, end(), _M_get_Tp_allocator()); this->_M_impl._M_finish = this->_M_impl._M_finish - (__last - __first); return __first; } @@ -140,7 +140,7 @@ namespace _GLIBCXX_STD pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end()); std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); @@ -150,7 +150,7 @@ namespace _GLIBCXX_STD else if (size() >= __xlen) { iterator __i(std::copy(__x.begin(), __x.end(), begin())); - std::_Destroy(__i, end(), this->get_allocator()); + std::_Destroy(__i, end(), _M_get_Tp_allocator()); } else { @@ -158,7 +158,7 @@ namespace _GLIBCXX_STD this->_M_impl._M_start); std::__uninitialized_copy_a(__x.begin() + size(), __x.end(), this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); } this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; } @@ -172,7 +172,7 @@ namespace _GLIBCXX_STD { if (__n > capacity()) { - vector __tmp(__n, __val, get_allocator()); + vector __tmp(__n, __val, _M_get_Tp_allocator()); __tmp.swap(*this); } else if (__n > size()) @@ -180,7 +180,7 @@ namespace _GLIBCXX_STD std::fill(begin(), end(), __val); std::__uninitialized_fill_n_a(this->_M_impl._M_finish, __n - size(), __val, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish += __n - size(); } else @@ -216,7 +216,7 @@ namespace _GLIBCXX_STD { pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); @@ -228,7 +228,7 @@ namespace _GLIBCXX_STD { iterator __new_finish(std::copy(__first, __last, this->_M_impl._M_start)); - std::_Destroy(__new_finish, end(), this->get_allocator()); + std::_Destroy(__new_finish, end(), _M_get_Tp_allocator()); this->_M_impl._M_finish = __new_finish.base(); } else @@ -239,7 +239,7 @@ namespace _GLIBCXX_STD this->_M_impl._M_finish = std::__uninitialized_copy_a(__mid, __last, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); } } @@ -280,22 +280,22 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_a(iterator(this->_M_impl._M_start), __position, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl.construct(__new_finish.base(), __x); ++__new_finish; __new_finish = std::__uninitialized_copy_a(__position, iterator(this->_M_impl._M_finish), __new_finish, - this->get_allocator()); + _M_get_Tp_allocator()); } catch(...) { - std::_Destroy(__new_start, __new_finish, this->get_allocator()); + std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); _M_deallocate(__new_start.base(),__len); __throw_exception_again; } - std::_Destroy(begin(), end(), this->get_allocator()); + std::_Destroy(begin(), end(), _M_get_Tp_allocator()); _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); @@ -323,7 +323,7 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_a(this->_M_impl._M_finish - __n, this->_M_impl._M_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish += __n; std::copy_backward(__position, __old_finish - __n, __old_finish); @@ -334,11 +334,11 @@ namespace _GLIBCXX_STD std::__uninitialized_fill_n_a(this->_M_impl._M_finish, __n - __elems_after, __x_copy, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish += __n - __elems_after; std::__uninitialized_copy_a(__position, __old_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish += __elems_after; std::fill(__position, __old_finish, __x_copy); } @@ -361,23 +361,23 @@ namespace _GLIBCXX_STD __new_finish = std::__uninitialized_copy_a(begin(), __position, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); std::__uninitialized_fill_n_a(__new_finish, __n, __x, - this->get_allocator()); + _M_get_Tp_allocator()); __new_finish += __n; __new_finish = std::__uninitialized_copy_a(__position, end(), __new_finish, - this->get_allocator()); + _M_get_Tp_allocator()); } catch(...) { std::_Destroy(__new_start, __new_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate(__new_start.base(), __len); __throw_exception_again; } std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); @@ -421,7 +421,7 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_a(this->_M_impl._M_finish - __n, this->_M_impl._M_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish += __n; std::copy_backward(__position, __old_finish - __n, __old_finish); @@ -433,11 +433,11 @@ namespace _GLIBCXX_STD std::advance(__mid, __elems_after); std::__uninitialized_copy_a(__mid, __last, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish += __n - __elems_after; std::__uninitialized_copy_a(__position, __old_finish, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); this->_M_impl._M_finish += __elems_after; std::copy(__first, __mid, __position); } @@ -461,25 +461,25 @@ namespace _GLIBCXX_STD std::__uninitialized_copy_a(iterator(this->_M_impl._M_start), __position, __new_start, - this->get_allocator()); + _M_get_Tp_allocator()); __new_finish = std::__uninitialized_copy_a(__first, __last, __new_finish, - this->get_allocator()); + _M_get_Tp_allocator()); __new_finish = std::__uninitialized_copy_a(__position, iterator(this->_M_impl._M_finish), __new_finish, - this->get_allocator()); + _M_get_Tp_allocator()); } catch(...) { std::_Destroy(__new_start,__new_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate(__new_start.base(), __len); __throw_exception_again; } std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, - this->get_allocator()); + _M_get_Tp_allocator()); _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); diff --git a/libstdc++-v3/include/c_std/std_cstdlib.h b/libstdc++-v3/include/c_std/std_cstdlib.h index 3fde655621a..cf91f27b2d3 100644 --- a/libstdc++-v3/include/c_std/std_cstdlib.h +++ b/libstdc++-v3/include/c_std/std_cstdlib.h @@ -1,6 +1,6 @@ // -*- C++ -*- forwarding header. -// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 +// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -168,17 +168,14 @@ namespace __gnu_cxx inline long long abs(long long __x) { return __x >= 0 ? __x : -__x; } - inline long long - llabs(long long __x) { return __x >= 0 ? __x : -__x; } - #if !_GLIBCXX_USE_C99_LONG_LONG_DYNAMIC + using ::llabs; + inline lldiv_t div(long long __n, long long __d) { lldiv_t __q; __q.quot = __n / __d; __q.rem = __n % __d; return __q; } - inline lldiv_t - lldiv(long long __n, long long __d) - { lldiv_t __q; __q.quot = __n / __d; __q.rem = __n % __d; return __q; } + using ::lldiv; #endif #if _GLIBCXX_USE_C99_LONG_LONG_CHECK || _GLIBCXX_USE_C99_LONG_LONG_DYNAMIC @@ -204,8 +201,8 @@ namespace std #endif using __gnu_cxx::_Exit; using __gnu_cxx::abs; - using __gnu_cxx::llabs; #if !_GLIBCXX_USE_C99_LONG_LONG_DYNAMIC + using __gnu_cxx::llabs; using __gnu_cxx::div; using __gnu_cxx::lldiv; #endif diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h index f371a6a47ca..7cd08cdeca0 100644 --- a/libstdc++-v3/include/debug/debug.h +++ b/libstdc++-v3/include/debug/debug.h @@ -31,191 +31,6 @@ #ifndef _GLIBCXX_DEBUG_DEBUG_H #define _GLIBCXX_DEBUG_DEBUG_H 1 -/** - * Macros used by the implementation to verify certain - * properties. These macros may only be used directly by the debug - * wrappers. Note that these are macros (instead of the more obviously - * "correct" choice of making them functions) because we need line and - * file information at the call site, to minimize the distance between - * the user error and where the error is reported. - * - */ -#define _GLIBCXX_DEBUG_VERIFY(_Condition,_ErrorMessage) \ - do { \ - if (! (_Condition)) \ - ::__gnu_debug::_Error_formatter::_M_at(__FILE__, __LINE__) \ - ._ErrorMessage._M_error(); \ - } while (false) - -// Verify that [_First, _Last) forms a valid iterator range. -#define __glibcxx_check_valid_range(_First,_Last) \ -_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__valid_range(_First, _Last), \ - _M_message(::__gnu_debug::__msg_valid_range) \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last)) - -/** Verify that we can insert into *this with the iterator _Position. - * Insertion into a container at a specific position requires that - * the iterator be nonsingular (i.e., either dereferenceable or - * past-the-end) and that it reference the sequence we are inserting - * into. Note that this macro is only valid when the container is a - * _Safe_sequence and the iterator is a _Safe_iterator. -*/ -#define __glibcxx_check_insert(_Position) \ -_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(), \ - _M_message(::__gnu_debug::__msg_insert_singular) \ - ._M_sequence(*this, "this") \ - ._M_iterator(_Position, #_Position)); \ -_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ - _M_message(::__gnu_debug::__msg_insert_different) \ - ._M_sequence(*this, "this") \ - ._M_iterator(_Position, #_Position)) - -/** Verify that we can insert the values in the iterator range - * [_First, _Last) into *this with the iterator _Position. Insertion - * into a container at a specific position requires that the iterator - * be nonsingular (i.e., either dereferenceable or past-the-end), - * that it reference the sequence we are inserting into, and that the - * iterator range [_First, Last) is a valid (possibly empty) - * range. Note that this macro is only valid when the container is a - * _Safe_sequence and the iterator is a _Safe_iterator. - * - * @tbd We would like to be able to check for noninterference of - * _Position and the range [_First, _Last), but that can't (in - * general) be done. -*/ -#define __glibcxx_check_insert_range(_Position,_First,_Last) \ -__glibcxx_check_valid_range(_First,_Last); \ -_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(), \ - _M_message(::__gnu_debug::__msg_insert_singular) \ - ._M_sequence(*this, "this") \ - ._M_iterator(_Position, #_Position)); \ -_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ - _M_message(::__gnu_debug::__msg_insert_different) \ - ._M_sequence(*this, "this") \ - ._M_iterator(_Position, #_Position)) - -/** Verify that we can erase the element referenced by the iterator - * _Position. We can erase the element if the _Position iterator is - * dereferenceable and references this sequence. -*/ -#define __glibcxx_check_erase(_Position) \ -_GLIBCXX_DEBUG_VERIFY(_Position._M_dereferenceable(), \ - _M_message(::__gnu_debug::__msg_erase_bad) \ - ._M_sequence(*this, "this") \ - ._M_iterator(_Position, #_Position)); \ -_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ - _M_message(::__gnu_debug::__msg_erase_different) \ - ._M_sequence(*this, "this") \ - ._M_iterator(_Position, #_Position)) - -/** Verify that we can erase the elements in the iterator range - * [_First, _Last). We can erase the elements if [_First, _Last) is a - * valid iterator range within this sequence. -*/ -#define __glibcxx_check_erase_range(_First,_Last) \ -__glibcxx_check_valid_range(_First,_Last); \ -_GLIBCXX_DEBUG_VERIFY(_First._M_attached_to(this), \ - _M_message(::__gnu_debug::__msg_erase_different) \ - ._M_sequence(*this, "this") \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last)) - -// Verify that the subscript _N is less than the container's size. -#define __glibcxx_check_subscript(_N) \ -_GLIBCXX_DEBUG_VERIFY(_N < this->size(), \ - _M_message(::__gnu_debug::__msg_subscript_oob) \ - ._M_sequence(*this, "this") \ - ._M_integer(_N, #_N) \ - ._M_integer(this->size(), "size")) - -// Verify that the container is nonempty -#define __glibcxx_check_nonempty() \ -_GLIBCXX_DEBUG_VERIFY(! this->empty(), \ - _M_message(::__gnu_debug::__msg_empty) \ - ._M_sequence(*this, "this")) - -// Verify that the < operator for elements in the sequence is a -// StrictWeakOrdering by checking that it is irreflexive. -#define __glibcxx_check_strict_weak_ordering(_First,_Last) \ -_GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First)) - -// Verify that the predicate is StrictWeakOrdering by checking that it -// is irreflexive. -#define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred) \ -_GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First)) - - -// Verify that the iterator range [_First, _Last) is sorted -#define __glibcxx_check_sorted(_First,_Last) \ -__glibcxx_check_valid_range(_First,_Last); \ -__glibcxx_check_strict_weak_ordering(_First,_Last); \ -_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last), \ - _M_message(::__gnu_debug::__msg_unsorted) \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last)) - -/** Verify that the iterator range [_First, _Last) is sorted by the - predicate _Pred. */ -#define __glibcxx_check_sorted_pred(_First,_Last,_Pred) \ -__glibcxx_check_valid_range(_First,_Last); \ -__glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred); \ -_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last, _Pred), \ - _M_message(::__gnu_debug::__msg_unsorted_pred) \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last) \ - ._M_string(#_Pred)) - -/** Verify that the iterator range [_First, _Last) is partitioned - w.r.t. the value _Value. */ -#define __glibcxx_check_partitioned(_First,_Last,_Value) \ -__glibcxx_check_valid_range(_First,_Last); \ -_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last, \ - _Value), \ - _M_message(::__gnu_debug::__msg_unpartitioned) \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last) \ - ._M_string(#_Value)) - -/** Verify that the iterator range [_First, _Last) is partitioned - w.r.t. the value _Value and predicate _Pred. */ -#define __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred) \ -__glibcxx_check_valid_range(_First,_Last); \ -_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last, \ - _Value, _Pred), \ - _M_message(::__gnu_debug::__msg_unpartitioned_pred) \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last) \ - ._M_string(#_Pred) \ - ._M_string(#_Value)) - -// Verify that the iterator range [_First, _Last) is a heap -#define __glibcxx_check_heap(_First,_Last) \ -__glibcxx_check_valid_range(_First,_Last); \ -_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last), \ - _M_message(::__gnu_debug::__msg_not_heap) \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last)) - -/** Verify that the iterator range [_First, _Last) is a heap - w.r.t. the predicate _Pred. */ -#define __glibcxx_check_heap_pred(_First,_Last,_Pred) \ -__glibcxx_check_valid_range(_First,_Last); \ -_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred), \ - _M_message(::__gnu_debug::__msg_not_heap_pred) \ - ._M_iterator(_First, #_First) \ - ._M_iterator(_Last, #_Last) \ - ._M_string(#_Pred)) - -#ifdef _GLIBCXX_DEBUG_PEDANTIC -# define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_ASSERT(_String != 0) -# define __glibcxx_check_string_len(_String,_Len) \ - _GLIBCXX_DEBUG_ASSERT(_String != 0 || _Len == 0) -#else -# define __glibcxx_check_string(_String) -# define __glibcxx_check_string_len(_String,_Len) -#endif - /** Macros used by the implementation outside of debug wrappers to * verify certain properties. The __glibcxx_requires_xxx macros are * merely wrappers around the __glibcxx_check_xxx wrappers when we @@ -223,11 +38,13 @@ _GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred), \ * release mode so that there is no checking performed in, e.g., the * standard library algorithms. */ + #ifdef _GLIBCXX_DEBUG -# define _GLIBCXX_DEBUG_ASSERT(_Condition) assert(_Condition) +# include <debug/macros.h> +# define _GLIBCXX_DEBUG_ASSERT(_Condition) _GLIBCXX_DEBUG_ABORT(_Condition) # ifdef _GLIBCXX_DEBUG_PEDANTIC -# define _GLIBCXX_DEBUG_PEDASSERT(_Condition) assert(_Condition) +# define _GLIBCXX_DEBUG_PEDASSERT(_Condition) _GLIBCXX_DEBUG_ABORT(_Condition) # else # define _GLIBCXX_DEBUG_PEDASSERT(_Condition) # endif @@ -252,6 +69,9 @@ _GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred), \ # define __glibcxx_requires_string_len(_String,_Len) \ __glibcxx_check_string_len(_String,_Len) # define __glibcxx_requires_subscript(_N) __glibcxx_check_subscript(_N) + +# include <debug/functions.h> +# include <debug/formatter.h> #else # define _GLIBCXX_DEBUG_ASSERT(_Condition) # define _GLIBCXX_DEBUG_PEDASSERT(_Condition) @@ -269,263 +89,4 @@ _GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred), \ # define __glibcxx_requires_subscript(_N) #endif -#include <cassert> // TBD: temporary - -#include <stddef.h> // for ptrdiff_t -#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories -#include <bits/cpp_type_traits.h> // for __is_integer - -namespace __gnu_debug -{ - template<typename _Iterator, typename _Sequence> - class _Safe_iterator; - - // An arbitrary iterator pointer is not singular. - inline bool - __check_singular_aux(const void*) { return false; } - - // We may have an iterator that derives from _Safe_iterator_base but isn't - // a _Safe_iterator. - template<typename _Iterator> - inline bool - __check_singular(_Iterator& __x) - { return __gnu_debug::__check_singular_aux(&__x); } - - /** Non-NULL pointers are nonsingular. */ - template<typename _Tp> - inline bool - __check_singular(const _Tp* __ptr) - { return __ptr == 0; } - - /** Safe iterators know if they are singular. */ - template<typename _Iterator, typename _Sequence> - inline bool - __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x) - { return __x._M_singular(); } - - /** Assume that some arbitrary iterator is dereferenceable, because we - can't prove that it isn't. */ - template<typename _Iterator> - inline bool - __check_dereferenceable(_Iterator&) - { return true; } - - /** Non-NULL pointers are dereferenceable. */ - template<typename _Tp> - inline bool - __check_dereferenceable(const _Tp* __ptr) - { return __ptr; } - - /** Safe iterators know if they are singular. */ - template<typename _Iterator, typename _Sequence> - inline bool - __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x) - { return __x._M_dereferenceable(); } - - /** If the distance between two random access iterators is - * nonnegative, assume the range is valid. - */ - template<typename _RandomAccessIterator> - inline bool - __valid_range_aux2(const _RandomAccessIterator& __first, - const _RandomAccessIterator& __last, - std::random_access_iterator_tag) - { return __last - __first >= 0; } - - /** Can't test for a valid range with input iterators, because - * iteration may be destructive. So we just assume that the range - * is valid. - */ - template<typename _InputIterator> - inline bool - __valid_range_aux2(const _InputIterator&, const _InputIterator&, - std::input_iterator_tag) - { return true; } - - /** We say that integral types for a valid range, and defer to other - * routines to realize what to do with integral types instead of - * iterators. - */ - template<typename _Integral> - inline bool - __valid_range_aux(const _Integral&, const _Integral&, __true_type) - { return true; } - - /** We have iterators, so figure out what kind of iterators that are - * to see if we can check the range ahead of time. - */ - template<typename _InputIterator> - inline bool - __valid_range_aux(const _InputIterator& __first, - const _InputIterator& __last, __false_type) - { - typedef typename std::iterator_traits<_InputIterator>::iterator_category - _Category; - return __gnu_debug::__valid_range_aux2(__first, __last, _Category()); - } - - /** Don't know what these iterators are, or if they are even - * iterators (we may get an integral type for InputIterator), so - * see if they are integral and pass them on to the next phase - * otherwise. - */ - template<typename _InputIterator> - inline bool - __valid_range(const _InputIterator& __first, const _InputIterator& __last) - { - typedef typename std::__is_integer<_InputIterator>::__type _Integral; - return __gnu_debug::__valid_range_aux(__first, __last, _Integral()); - } - - /** Safe iterators know how to check if they form a valid range. */ - template<typename _Iterator, typename _Sequence> - inline bool - __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, - const _Safe_iterator<_Iterator, _Sequence>& __last) - { return __first._M_valid_range(__last); } - - /* Checks that [first, last) is a valid range, and then returns - * __first. This routine is useful when we can't use a separate - * assertion statement because, e.g., we are in a constructor. - */ - template<typename _InputIterator> - inline _InputIterator - __check_valid_range(const _InputIterator& __first, - const _InputIterator& __last) - { - _GLIBCXX_DEBUG_ASSERT(__gnu_debug::__valid_range(__first, __last)); - return __first; - } - - /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ - template<typename _CharT, typename _Integer> - inline const _CharT* - __check_string(const _CharT* __s, const _Integer& __n) - { -#ifdef _GLIBCXX_DEBUG_PEDANTIC - _GLIBCXX_DEBUG_ASSERT(__s != 0 || __n == 0); -#endif - return __s; - } - - /** Checks that __s is non-NULL and then returns __s. */ - template<typename _CharT> - inline const _CharT* - __check_string(const _CharT* __s) - { -#ifdef _GLIBCXX_DEBUG_PEDANTIC - _GLIBCXX_DEBUG_ASSERT(__s != 0); -#endif - return __s; - } - - // Can't check if an input iterator sequence is sorted, because we - // can't step through the sequence. - template<typename _InputIterator> - inline bool - __check_sorted_aux(const _InputIterator&, const _InputIterator&, - std::input_iterator_tag) - { return true; } - - // Can verify if a forward iterator sequence is in fact sorted using - // std::__is_sorted - template<typename _ForwardIterator> - inline bool - __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, - std::forward_iterator_tag) - { - if (__first == __last) - return true; - - _ForwardIterator __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) { - if (*__next < *__first) - return false; - } - - return true; - } - - // Can't check if an input iterator sequence is sorted, because we can't step - // through the sequence. - template<typename _InputIterator, typename _Predicate> - inline bool - __check_sorted_aux(const _InputIterator&, const _InputIterator&, - _Predicate, std::input_iterator_tag) - { return true; } - - // Can verify if a forward iterator sequence is in fact sorted using - // std::__is_sorted - template<typename _ForwardIterator, typename _Predicate> - inline bool - __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, - _Predicate __pred, std::forward_iterator_tag) - { - if (__first == __last) - return true; - - _ForwardIterator __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) { - if (__pred(*__next, *__first)) - return false; - } - - return true; - } - - // Determine if a sequence is sorted. - template<typename _InputIterator> - inline bool - __check_sorted(const _InputIterator& __first, const _InputIterator& __last) - { - typedef typename std::iterator_traits<_InputIterator>::iterator_category - _Category; - return __gnu_debug::__check_sorted_aux(__first, __last, _Category()); - } - - template<typename _InputIterator, typename _Predicate> - inline bool - __check_sorted(const _InputIterator& __first, const _InputIterator& __last, - _Predicate __pred) - { - typedef typename std::iterator_traits<_InputIterator>::iterator_category - _Category; - return __gnu_debug::__check_sorted_aux(__first, __last, __pred, - _Category()); - } - - // _GLIBCXX_RESOLVE_LIB_DEFECTS - // 270. Binary search requirements overly strict - // Determine if a sequence is partitioned w.r.t. this element. - template<typename _ForwardIterator, typename _Tp> - inline bool - __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __value) - { - while (__first != __last && *__first < __value) - ++__first; - while (__first != __last && !(*__first < __value)) - ++__first; - return __first == __last; - } - - // Determine if a sequence is partitioned w.r.t. this element. - template<typename _ForwardIterator, typename _Tp, typename _Pred> - inline bool - __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __value, _Pred __pred) - { - while (__first != __last && __pred(*__first, __value)) - ++__first; - while (__first != __last && !__pred(*__first, __value)) - ++__first; - return __first == __last; - } -} // namespace __gnu_debug - -#ifdef _GLIBCXX_DEBUG -// We need the error formatter -# include <debug/formatter.h> -#endif - #endif diff --git a/libstdc++-v3/include/debug/deque b/libstdc++-v3/include/debug/deque index c39a49c0461..5d87cdaeb34 100644 --- a/libstdc++-v3/include/debug/deque +++ b/libstdc++-v3/include/debug/deque @@ -1,6 +1,6 @@ // Debugging deque implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -46,8 +46,8 @@ namespace __gnu_debug_def typedef __gnu_debug::_Safe_sequence<deque> _Safe_base; public: - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque> iterator; @@ -59,8 +59,8 @@ namespace __gnu_debug_def typedef _Tp value_type; typedef _Allocator allocator_type; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h new file mode 100644 index 00000000000..28834d4786e --- /dev/null +++ b/libstdc++-v3/include/debug/functions.h @@ -0,0 +1,286 @@ +// Debugging support implementation -*- C++ -*- + +// Copyright (C) 2003, 2005 +// Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +#ifndef _GLIBCXX_DEBUG_FUNCTIONS_H +#define _GLIBCXX_DEBUG_FUNCTIONS_H 1 + +#include <stddef.h> // for ptrdiff_t +#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories +#include <bits/cpp_type_traits.h> // for __is_integer + +namespace __gnu_debug +{ + template<typename _Iterator, typename _Sequence> + class _Safe_iterator; + + // An arbitrary iterator pointer is not singular. + inline bool + __check_singular_aux(const void*) { return false; } + + // We may have an iterator that derives from _Safe_iterator_base but isn't + // a _Safe_iterator. + template<typename _Iterator> + inline bool + __check_singular(_Iterator& __x) + { return __gnu_debug::__check_singular_aux(&__x); } + + /** Non-NULL pointers are nonsingular. */ + template<typename _Tp> + inline bool + __check_singular(const _Tp* __ptr) + { return __ptr == 0; } + + /** Safe iterators know if they are singular. */ + template<typename _Iterator, typename _Sequence> + inline bool + __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x) + { return __x._M_singular(); } + + /** Assume that some arbitrary iterator is dereferenceable, because we + can't prove that it isn't. */ + template<typename _Iterator> + inline bool + __check_dereferenceable(_Iterator&) + { return true; } + + /** Non-NULL pointers are dereferenceable. */ + template<typename _Tp> + inline bool + __check_dereferenceable(const _Tp* __ptr) + { return __ptr; } + + /** Safe iterators know if they are singular. */ + template<typename _Iterator, typename _Sequence> + inline bool + __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x) + { return __x._M_dereferenceable(); } + + /** If the distance between two random access iterators is + * nonnegative, assume the range is valid. + */ + template<typename _RandomAccessIterator> + inline bool + __valid_range_aux2(const _RandomAccessIterator& __first, + const _RandomAccessIterator& __last, + std::random_access_iterator_tag) + { return __last - __first >= 0; } + + /** Can't test for a valid range with input iterators, because + * iteration may be destructive. So we just assume that the range + * is valid. + */ + template<typename _InputIterator> + inline bool + __valid_range_aux2(const _InputIterator&, const _InputIterator&, + std::input_iterator_tag) + { return true; } + + /** We say that integral types for a valid range, and defer to other + * routines to realize what to do with integral types instead of + * iterators. + */ + template<typename _Integral> + inline bool + __valid_range_aux(const _Integral&, const _Integral&, __true_type) + { return true; } + + /** We have iterators, so figure out what kind of iterators that are + * to see if we can check the range ahead of time. + */ + template<typename _InputIterator> + inline bool + __valid_range_aux(const _InputIterator& __first, + const _InputIterator& __last, __false_type) + { + typedef typename std::iterator_traits<_InputIterator>::iterator_category + _Category; + return __gnu_debug::__valid_range_aux2(__first, __last, _Category()); + } + + /** Don't know what these iterators are, or if they are even + * iterators (we may get an integral type for InputIterator), so + * see if they are integral and pass them on to the next phase + * otherwise. + */ + template<typename _InputIterator> + inline bool + __valid_range(const _InputIterator& __first, const _InputIterator& __last) + { + typedef typename std::__is_integer<_InputIterator>::__type _Integral; + return __gnu_debug::__valid_range_aux(__first, __last, _Integral()); + } + + /** Safe iterators know how to check if they form a valid range. */ + template<typename _Iterator, typename _Sequence> + inline bool + __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, + const _Safe_iterator<_Iterator, _Sequence>& __last) + { return __first._M_valid_range(__last); } + + /* Checks that [first, last) is a valid range, and then returns + * __first. This routine is useful when we can't use a separate + * assertion statement because, e.g., we are in a constructor. + */ + template<typename _InputIterator> + inline _InputIterator + __check_valid_range(const _InputIterator& __first, + const _InputIterator& __last) + { + _GLIBCXX_DEBUG_ASSERT(__gnu_debug::__valid_range(__first, __last)); + return __first; + } + + /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ + template<typename _CharT, typename _Integer> + inline const _CharT* + __check_string(const _CharT* __s, const _Integer& __n) + { +#ifdef _GLIBCXX_DEBUG_PEDANTIC + _GLIBCXX_DEBUG_ASSERT(__s != 0 || __n == 0); +#endif + return __s; + } + + /** Checks that __s is non-NULL and then returns __s. */ + template<typename _CharT> + inline const _CharT* + __check_string(const _CharT* __s) + { +#ifdef _GLIBCXX_DEBUG_PEDANTIC + _GLIBCXX_DEBUG_ASSERT(__s != 0); +#endif + return __s; + } + + // Can't check if an input iterator sequence is sorted, because we + // can't step through the sequence. + template<typename _InputIterator> + inline bool + __check_sorted_aux(const _InputIterator&, const _InputIterator&, + std::input_iterator_tag) + { return true; } + + // Can verify if a forward iterator sequence is in fact sorted using + // std::__is_sorted + template<typename _ForwardIterator> + inline bool + __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, + std::forward_iterator_tag) + { + if (__first == __last) + return true; + + _ForwardIterator __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) { + if (*__next < *__first) + return false; + } + + return true; + } + + // Can't check if an input iterator sequence is sorted, because we can't step + // through the sequence. + template<typename _InputIterator, typename _Predicate> + inline bool + __check_sorted_aux(const _InputIterator&, const _InputIterator&, + _Predicate, std::input_iterator_tag) + { return true; } + + // Can verify if a forward iterator sequence is in fact sorted using + // std::__is_sorted + template<typename _ForwardIterator, typename _Predicate> + inline bool + __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, + _Predicate __pred, std::forward_iterator_tag) + { + if (__first == __last) + return true; + + _ForwardIterator __next = __first; + for (++__next; __next != __last; __first = __next, ++__next) { + if (__pred(*__next, *__first)) + return false; + } + + return true; + } + + // Determine if a sequence is sorted. + template<typename _InputIterator> + inline bool + __check_sorted(const _InputIterator& __first, const _InputIterator& __last) + { + typedef typename std::iterator_traits<_InputIterator>::iterator_category + _Category; + return __gnu_debug::__check_sorted_aux(__first, __last, _Category()); + } + + template<typename _InputIterator, typename _Predicate> + inline bool + __check_sorted(const _InputIterator& __first, const _InputIterator& __last, + _Predicate __pred) + { + typedef typename std::iterator_traits<_InputIterator>::iterator_category + _Category; + return __gnu_debug::__check_sorted_aux(__first, __last, __pred, + _Category()); + } + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // 270. Binary search requirements overly strict + // Determine if a sequence is partitioned w.r.t. this element. + template<typename _ForwardIterator, typename _Tp> + inline bool + __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) + { + while (__first != __last && *__first < __value) + ++__first; + while (__first != __last && !(*__first < __value)) + ++__first; + return __first == __last; + } + + // Determine if a sequence is partitioned w.r.t. this element. + template<typename _ForwardIterator, typename _Tp, typename _Pred> + inline bool + __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value, _Pred __pred) + { + while (__first != __last && __pred(*__first, __value)) + ++__first; + while (__first != __last && !__pred(*__first, __value)) + ++__first; + return __first == __last; + } +} // namespace __gnu_debug + +#endif diff --git a/libstdc++-v3/include/debug/hash_map b/libstdc++-v3/include/debug/hash_map index 570a9af6b69..d4d149756cd 100644 --- a/libstdc++-v3/include/debug/hash_map +++ b/libstdc++-v3/include/debug/hash_map @@ -1,6 +1,6 @@ // Debugging hash_map/hash_multimap implementation -*- C++ -*- -// Copyright (C) 2003 +// Copyright (C) 2003, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -31,8 +31,8 @@ #ifndef _GLIBCXX_DEBUG_HASH_MAP #define _GLIBCXX_DEBUG_HASH_MAP 1 -#include <hash_map> -#include <debug/dbg_hash_map.h> -#include <debug/dbg_hash_multimap.h> +#include <ext/hash_map> +#include <debug/hash_map.h> +#include <debug/hash_multimap.h> #endif diff --git a/libstdc++-v3/include/debug/hash_set b/libstdc++-v3/include/debug/hash_set index 282cba27613..c600f07c160 100644 --- a/libstdc++-v3/include/debug/hash_set +++ b/libstdc++-v3/include/debug/hash_set @@ -1,6 +1,6 @@ // Debugging hash_set/hash_multiset implementation -*- C++ -*- -// Copyright (C) 2003 +// Copyright (C) 2003, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -31,8 +31,8 @@ #ifndef _GLIBCXX_DEBUG_HASH_SET #define _GLIBCXX_DEBUG_HASH_SET 1 -#include <hash_set> -#include <debug/dbg_hash_set.h> -#include <debug/dbg_hash_multiset.h> +#include <ext/hash_set> +#include <debug/hash_set.h> +#include <debug/hash_multiset.h> #endif diff --git a/libstdc++-v3/include/debug/list b/libstdc++-v3/include/debug/list index 556c9d9acff..745f14ea7b7 100644 --- a/libstdc++-v3/include/debug/list +++ b/libstdc++-v3/include/debug/list @@ -1,6 +1,6 @@ // Debugging list implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -47,8 +47,8 @@ namespace __gnu_debug_def typedef __gnu_debug::_Safe_sequence<list> _Safe_base; public: - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, list> iterator; @@ -60,8 +60,8 @@ namespace __gnu_debug_def typedef _Tp value_type; typedef _Allocator allocator_type; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h new file mode 100644 index 00000000000..3fe60c9df9a --- /dev/null +++ b/libstdc++-v3/include/debug/macros.h @@ -0,0 +1,229 @@ +// Debugging support implementation -*- C++ -*- + +// Copyright (C) 2003, 2005 +// Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +#ifndef _GLIBCXX_DEBUG_MACROS_H +#define _GLIBCXX_DEBUG_MACROS_H 1 + +/** + * Macros used by the implementation to verify certain + * properties. These macros may only be used directly by the debug + * wrappers. Note that these are macros (instead of the more obviously + * "correct" choice of making them functions) because we need line and + * file information at the call site, to minimize the distance between + * the user error and where the error is reported. + * + */ +namespace __gnu_debug +{ void __fancy_abort(const char*, int, const char*, const char*); } +#define _GLIBCXX_DEBUG_ABORT(_Condition) \ + do { \ + if (! (_Condition)) \ + ::__gnu_debug::__fancy_abort(__FILE__, __LINE__, \ + __PRETTY_FUNCTION__, \ + #_Condition); \ + } while (false) + +#define _GLIBCXX_DEBUG_VERIFY(_Condition,_ErrorMessage) \ + do { \ + if (! (_Condition)) \ + ::__gnu_debug::_Error_formatter::_M_at(__FILE__, __LINE__) \ + ._ErrorMessage._M_error(); \ + } while (false) + +// Verify that [_First, _Last) forms a valid iterator range. +#define __glibcxx_check_valid_range(_First,_Last) \ +_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__valid_range(_First, _Last), \ + _M_message(::__gnu_debug::__msg_valid_range) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last)) + +/** Verify that we can insert into *this with the iterator _Position. + * Insertion into a container at a specific position requires that + * the iterator be nonsingular (i.e., either dereferenceable or + * past-the-end) and that it reference the sequence we are inserting + * into. Note that this macro is only valid when the container is a + * _Safe_sequence and the iterator is a _Safe_iterator. +*/ +#define __glibcxx_check_insert(_Position) \ +_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(), \ + _M_message(::__gnu_debug::__msg_insert_singular) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_Position, #_Position)); \ +_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ + _M_message(::__gnu_debug::__msg_insert_different) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_Position, #_Position)) + +/** Verify that we can insert the values in the iterator range + * [_First, _Last) into *this with the iterator _Position. Insertion + * into a container at a specific position requires that the iterator + * be nonsingular (i.e., either dereferenceable or past-the-end), + * that it reference the sequence we are inserting into, and that the + * iterator range [_First, Last) is a valid (possibly empty) + * range. Note that this macro is only valid when the container is a + * _Safe_sequence and the iterator is a _Safe_iterator. + * + * @tbd We would like to be able to check for noninterference of + * _Position and the range [_First, _Last), but that can't (in + * general) be done. +*/ +#define __glibcxx_check_insert_range(_Position,_First,_Last) \ +__glibcxx_check_valid_range(_First,_Last); \ +_GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(), \ + _M_message(::__gnu_debug::__msg_insert_singular) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_Position, #_Position)); \ +_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ + _M_message(::__gnu_debug::__msg_insert_different) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_Position, #_Position)) + +/** Verify that we can erase the element referenced by the iterator + * _Position. We can erase the element if the _Position iterator is + * dereferenceable and references this sequence. +*/ +#define __glibcxx_check_erase(_Position) \ +_GLIBCXX_DEBUG_VERIFY(_Position._M_dereferenceable(), \ + _M_message(::__gnu_debug::__msg_erase_bad) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_Position, #_Position)); \ +_GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ + _M_message(::__gnu_debug::__msg_erase_different) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_Position, #_Position)) + +/** Verify that we can erase the elements in the iterator range + * [_First, _Last). We can erase the elements if [_First, _Last) is a + * valid iterator range within this sequence. +*/ +#define __glibcxx_check_erase_range(_First,_Last) \ +__glibcxx_check_valid_range(_First,_Last); \ +_GLIBCXX_DEBUG_VERIFY(_First._M_attached_to(this), \ + _M_message(::__gnu_debug::__msg_erase_different) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last)) + +// Verify that the subscript _N is less than the container's size. +#define __glibcxx_check_subscript(_N) \ +_GLIBCXX_DEBUG_VERIFY(_N < this->size(), \ + _M_message(::__gnu_debug::__msg_subscript_oob) \ + ._M_sequence(*this, "this") \ + ._M_integer(_N, #_N) \ + ._M_integer(this->size(), "size")) + +// Verify that the container is nonempty +#define __glibcxx_check_nonempty() \ +_GLIBCXX_DEBUG_VERIFY(! this->empty(), \ + _M_message(::__gnu_debug::__msg_empty) \ + ._M_sequence(*this, "this")) + +// Verify that the < operator for elements in the sequence is a +// StrictWeakOrdering by checking that it is irreflexive. +#define __glibcxx_check_strict_weak_ordering(_First,_Last) \ +_GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First)) + +// Verify that the predicate is StrictWeakOrdering by checking that it +// is irreflexive. +#define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred) \ +_GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First)) + + +// Verify that the iterator range [_First, _Last) is sorted +#define __glibcxx_check_sorted(_First,_Last) \ +__glibcxx_check_valid_range(_First,_Last); \ +__glibcxx_check_strict_weak_ordering(_First,_Last); \ +_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last), \ + _M_message(::__gnu_debug::__msg_unsorted) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last)) + +/** Verify that the iterator range [_First, _Last) is sorted by the + predicate _Pred. */ +#define __glibcxx_check_sorted_pred(_First,_Last,_Pred) \ +__glibcxx_check_valid_range(_First,_Last); \ +__glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred); \ +_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last, _Pred), \ + _M_message(::__gnu_debug::__msg_unsorted_pred) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last) \ + ._M_string(#_Pred)) + +/** Verify that the iterator range [_First, _Last) is partitioned + w.r.t. the value _Value. */ +#define __glibcxx_check_partitioned(_First,_Last,_Value) \ +__glibcxx_check_valid_range(_First,_Last); \ +_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last, \ + _Value), \ + _M_message(::__gnu_debug::__msg_unpartitioned) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last) \ + ._M_string(#_Value)) + +/** Verify that the iterator range [_First, _Last) is partitioned + w.r.t. the value _Value and predicate _Pred. */ +#define __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred) \ +__glibcxx_check_valid_range(_First,_Last); \ +_GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last, \ + _Value, _Pred), \ + _M_message(::__gnu_debug::__msg_unpartitioned_pred) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last) \ + ._M_string(#_Pred) \ + ._M_string(#_Value)) + +// Verify that the iterator range [_First, _Last) is a heap +#define __glibcxx_check_heap(_First,_Last) \ +__glibcxx_check_valid_range(_First,_Last); \ +_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last), \ + _M_message(::__gnu_debug::__msg_not_heap) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last)) + +/** Verify that the iterator range [_First, _Last) is a heap + w.r.t. the predicate _Pred. */ +#define __glibcxx_check_heap_pred(_First,_Last,_Pred) \ +__glibcxx_check_valid_range(_First,_Last); \ +_GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred), \ + _M_message(::__gnu_debug::__msg_not_heap_pred) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last) \ + ._M_string(#_Pred)) + +#ifdef _GLIBCXX_DEBUG_PEDANTIC +# define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_ASSERT(_String != 0) +# define __glibcxx_check_string_len(_String,_Len) \ + _GLIBCXX_DEBUG_ASSERT(_String != 0 || _Len == 0) +#else +# define __glibcxx_check_string(_String) +# define __glibcxx_check_string_len(_String,_Len) +#endif + +#endif diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h index 017158479d1..75ae2f4bcf3 100644 --- a/libstdc++-v3/include/debug/map.h +++ b/libstdc++-v3/include/debug/map.h @@ -1,6 +1,6 @@ // Debugging map implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -53,8 +53,8 @@ namespace __gnu_debug_def typedef std::pair<const _Key, _Tp> value_type; typedef _Compare key_compare; typedef _Allocator allocator_type; - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, map> iterator; @@ -63,8 +63,8 @@ namespace __gnu_debug_def typedef typename _Base::size_type size_type; typedef typename _Base::difference_type difference_type; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h index 4de1e3b58f4..d5dbe5c2f71 100644 --- a/libstdc++-v3/include/debug/multimap.h +++ b/libstdc++-v3/include/debug/multimap.h @@ -1,6 +1,6 @@ // Debugging multimap implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -53,8 +53,8 @@ namespace __gnu_debug_def typedef std::pair<const _Key, _Tp> value_type; typedef _Compare key_compare; typedef _Allocator allocator_type; - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multimap> iterator; @@ -63,8 +63,8 @@ namespace __gnu_debug_def typedef typename _Base::size_type size_type; typedef typename _Base::difference_type difference_type; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h index 92042fef68c..879e2feb59a 100644 --- a/libstdc++-v3/include/debug/multiset.h +++ b/libstdc++-v3/include/debug/multiset.h @@ -1,6 +1,6 @@ // Debugging multiset implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -53,8 +53,8 @@ namespace __gnu_debug_def typedef _Compare key_compare; typedef _Compare value_compare; typedef _Allocator allocator_type; - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset> iterator; @@ -63,8 +63,8 @@ namespace __gnu_debug_def typedef typename _Base::size_type size_type; typedef typename _Base::difference_type difference_type; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h index 1f5b0f65e45..8d96f397c85 100644 --- a/libstdc++-v3/include/debug/safe_iterator.h +++ b/libstdc++-v3/include/debug/safe_iterator.h @@ -31,10 +31,12 @@ #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1 -#include <bits/stl_pair.h> #include <debug/debug.h> +#include <debug/macros.h> +#include <debug/functions.h> #include <debug/formatter.h> #include <debug/safe_base.h> +#include <bits/stl_pair.h> #include <bits/cpp_type_traits.h> namespace __gnu_debug @@ -46,7 +48,8 @@ namespace __gnu_debug * _Safe_iterators can be determined singular or non-singular via * _Safe_iterator_base. */ - inline bool __check_singular_aux(const _Safe_iterator_base* __x) + inline bool + __check_singular_aux(const _Safe_iterator_base* __x) { return __x->_M_singular(); } /** \brief Safe iterator wrapper. diff --git a/libstdc++-v3/include/debug/safe_sequence.h b/libstdc++-v3/include/debug/safe_sequence.h index f050530a997..a1577b4b4ee 100644 --- a/libstdc++-v3/include/debug/safe_sequence.h +++ b/libstdc++-v3/include/debug/safe_sequence.h @@ -1,6 +1,6 @@ // Safe sequence implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -32,6 +32,8 @@ #define _GLIBCXX_DEBUG_SAFE_SEQUENCE_H 1 #include <debug/debug.h> +#include <debug/macros.h> +#include <debug/functions.h> #include <debug/safe_base.h> namespace __gnu_debug diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h index 8656cb0aff6..f6fd451e1b9 100644 --- a/libstdc++-v3/include/debug/set.h +++ b/libstdc++-v3/include/debug/set.h @@ -1,6 +1,6 @@ // Debugging set implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -53,8 +53,8 @@ namespace __gnu_debug_def typedef _Compare key_compare; typedef _Compare value_compare; typedef _Allocator allocator_type; - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set> iterator; @@ -63,8 +63,8 @@ namespace __gnu_debug_def typedef typename _Base::size_type size_type; typedef typename _Base::difference_type difference_type; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/libstdc++-v3/include/debug/string b/libstdc++-v3/include/debug/string index a91c004e937..26a1582d3d8 100644 --- a/libstdc++-v3/include/debug/string +++ b/libstdc++-v3/include/debug/string @@ -1,6 +1,6 @@ // Debugging string implementation -*- C++ -*- -// Copyright (C) 2003 +// Copyright (C) 2003, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -37,7 +37,8 @@ namespace __gnu_debug { - template<typename _CharT, typename _Traits, typename _Allocator> +template<typename _CharT, typename _Traits = std::char_traits<_CharT>, + typename _Allocator = std::allocator<_CharT> > class basic_string : public std::basic_string<_CharT, _Traits, _Allocator>, public __gnu_debug::_Safe_sequence<basic_string<_CharT, _Traits, @@ -51,12 +52,12 @@ namespace __gnu_debug typedef _Traits traits_type; typedef typename _Traits::char_type value_type; typedef _Allocator allocator_type; - typedef typename _Allocator::size_type size_type; - typedef typename _Allocator::difference_type difference_type; - typedef typename _Allocator::reference reference; - typedef typename _Allocator::const_reference const_reference; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::size_type size_type; + typedef typename _Base::difference_type difference_type; + typedef typename _Base::reference reference; + typedef typename _Base::const_reference const_reference; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, basic_string> iterator; @@ -213,7 +214,16 @@ namespace __gnu_debug reference operator[](size_type __pos) { +#ifdef _GLIBCXX_DEBUG_PEDANTIC __glibcxx_check_subscript(__pos); +#else + // as an extension v3 allows s[s.size()] when s is non-const. + _GLIBCXX_DEBUG_VERIFY(__pos <= this->size(), + _M_message(::__gnu_debug::__msg_subscript_oob) + ._M_sequence(*this, "this") + ._M_integer(__pos, "__pos") + ._M_integer(this->size(), "size")); +#endif return _M_base()[__pos]; } @@ -996,6 +1006,13 @@ namespace __gnu_debug __str._M_invalidate_all(); return __res; } + + typedef basic_string<char> string; + +#ifdef _GLIBCXX_USE_WCHAR_T + typedef basic_string<wchar_t> wstring; +#endif + } // namespace __gnu_debug #endif diff --git a/libstdc++-v3/include/debug/vector b/libstdc++-v3/include/debug/vector index 0cc2997b975..05c15ec18d3 100644 --- a/libstdc++-v3/include/debug/vector +++ b/libstdc++-v3/include/debug/vector @@ -1,6 +1,6 @@ // Debugging vector implementation -*- C++ -*- -// Copyright (C) 2003, 2004 +// Copyright (C) 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -32,9 +32,9 @@ #define _GLIBCXX_DEBUG_VECTOR 1 #include <vector> +#include <utility> #include <debug/safe_sequence.h> #include <debug/safe_iterator.h> -#include <utility> namespace __gnu_debug_def { @@ -64,8 +64,8 @@ namespace __gnu_debug_def typedef _Tp value_type; typedef _Allocator allocator_type; - typedef typename _Allocator::pointer pointer; - typedef typename _Allocator::const_pointer const_pointer; + typedef typename _Base::pointer pointer; + typedef typename _Base::const_pointer const_pointer; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; diff --git a/libstdc++-v3/include/ext/array_allocator.h b/libstdc++-v3/include/ext/array_allocator.h index 27169193306..8689d9da26a 100644 --- a/libstdc++-v3/include/ext/array_allocator.h +++ b/libstdc++-v3/include/ext/array_allocator.h @@ -121,10 +121,9 @@ namespace __gnu_cxx allocate(size_type __n, const void* = 0) { static size_type __array_used; - if (_M_array == 0 - || __array_used + __n > sizeof(*_M_array) / sizeof(_Tp)) + if (_M_array == 0 || __array_used + __n > _M_array->size()) std::__throw_bad_alloc(); - pointer __ret = reinterpret_cast<_Tp*>(_M_array) + __array_used; + pointer __ret = _M_array->begin() + __array_used; __array_used += __n; return __ret; } diff --git a/libstdc++-v3/include/ext/hash_map b/libstdc++-v3/include/ext/hash_map index eff10e0272b..20eebeb29a2 100644 --- a/libstdc++-v3/include/ext/hash_map +++ b/libstdc++-v3/include/ext/hash_map @@ -1,6 +1,6 @@ // Hashing map implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -617,4 +617,9 @@ namespace std { return *this; } }; } // namespace std + +#ifdef _GLIBCXX_DEBUG +# include <debug/hash_map> +#endif + #endif diff --git a/libstdc++-v3/include/ext/hash_set b/libstdc++-v3/include/ext/hash_set index f6e791a500f..120bfc5ae4b 100644 --- a/libstdc++-v3/include/ext/hash_set +++ b/libstdc++-v3/include/ext/hash_set @@ -1,6 +1,6 @@ // Hashing set implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -583,4 +583,9 @@ namespace std operator++(int) { return *this; } }; } // namespace std + +#ifdef _GLIBCXX_DEBUG +# include <debug/hash_set> +#endif + #endif diff --git a/libstdc++-v3/include/std/std_complex.h b/libstdc++-v3/include/std/std_complex.h index 6c1e0033730..80020756789 100644 --- a/libstdc++-v3/include/std/std_complex.h +++ b/libstdc++-v3/include/std/std_complex.h @@ -749,7 +749,7 @@ namespace std __complex_log(const complex<_Tp>& __z) { return complex<_Tp>(log(std::abs(__z)), std::arg(__z)); } - /* +#if _GLIBCXX_USE_C99_COMPLEX inline __complex__ float __complex_log(__complex__ float __z) { return __builtin_clogf(__z); } @@ -758,14 +758,16 @@ namespace std inline __complex__ long double __complex_log(const __complex__ long double& __z) - { return __builtin_clogl(__z); } */ + { return __builtin_clogl(__z); } - // FIXME: Currently we don't use built-ins for log() because of some - // obscure user name-space issues. So, we use the generic version - // which is why we don't use __z.__rep() in the call below. + template<typename _Tp> + inline complex<_Tp> + log(const complex<_Tp>& __z) { return __complex_log(__z.__rep()); } +#else template<typename _Tp> inline complex<_Tp> log(const complex<_Tp>& __z) { return __complex_log(__z); } +#endif template<typename _Tp> inline complex<_Tp> diff --git a/libstdc++-v3/include/std/std_sstream.h b/libstdc++-v3/include/std/std_sstream.h index 66215b2f730..52c416f85b9 100644 --- a/libstdc++-v3/include/std/std_sstream.h +++ b/libstdc++-v3/include/std/std_sstream.h @@ -1,6 +1,6 @@ // String based streams -*- C++ -*- -// Copyright (C) 1997, 1998, 1999, 2002, 2003, 2004 +// Copyright (C) 1997, 1998, 1999, 2002, 2003, 2004, 2005 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -127,16 +127,18 @@ namespace std __string_type str() const { + __string_type __ret; if (this->pptr()) { // The current egptr() may not be the actual string end. if (this->pptr() > this->egptr()) - return __string_type(this->pbase(), this->pptr()); + __ret = __string_type(this->pbase(), this->pptr()); else - return __string_type(this->pbase(), this->egptr()); + __ret = __string_type(this->pbase(), this->egptr()); } else - return _M_string; + __ret = _M_string; + return __ret; } /** @@ -151,7 +153,7 @@ namespace std { // Cannot use _M_string = __s, since v3 strings are COW. _M_string.assign(__s.data(), __s.size()); - _M_stringbuf_init(this->_M_mode); + _M_stringbuf_init(_M_mode); } protected: @@ -159,14 +161,25 @@ namespace std void _M_stringbuf_init(ios_base::openmode __mode) { - this->_M_mode = __mode; - + _M_mode = __mode; __size_type __len = 0; - if (this->_M_mode & (ios_base::ate | ios_base::app)) + if (_M_mode & (ios_base::ate | ios_base::app)) __len = _M_string.size(); _M_sync(const_cast<char_type*>(_M_string.data()), 0, __len); } + virtual streamsize + showmanyc() + { + streamsize __ret = -1; + if (_M_mode & ios_base::in) + { + _M_update_egptr(); + __ret = this->egptr() - this->gptr(); + } + return __ret; + } + virtual int_type underflow(); @@ -223,8 +236,8 @@ namespace std void _M_sync(char_type* __base, __size_type __i, __size_type __o) { - const bool __testin = this->_M_mode & ios_base::in; - const bool __testout = this->_M_mode & ios_base::out; + const bool __testin = _M_mode & ios_base::in; + const bool __testout = _M_mode & ios_base::out; char_type* __end = __base + _M_string.size(); if (__testin) @@ -252,8 +265,7 @@ namespace std void _M_update_egptr() { - const bool __testin = this->_M_mode & ios_base::in; - + const bool __testin = _M_mode & ios_base::in; if (this->pptr() && this->pptr() > this->egptr()) if (__testin) this->setg(this->eback(), this->gptr(), this->pptr()); diff --git a/libstdc++-v3/include/tr1/hashtable b/libstdc++-v3/include/tr1/hashtable index c015e9edf69..add5f5bde15 100644 --- a/libstdc++-v3/include/tr1/hashtable +++ b/libstdc++-v3/include/tr1/hashtable @@ -64,40 +64,39 @@ //---------------------------------------------------------------------- // General utilities -namespace Internal { -template <bool Flag, typename IfTrue, typename IfFalse> struct IF; - -template <typename IfTrue, typename IfFalse> -struct IF <true, IfTrue, IfFalse> { typedef IfTrue type; }; - -template <typename IfTrue, typename IfFalse> -struct IF <false, IfTrue, IfFalse> { typedef IfFalse type; }; - -// Helper function: return distance(first, last) for forward -// iterators, or 0 for input iterators. - -template <class Iterator> -inline typename std::iterator_traits<Iterator>::difference_type -distance_fw (Iterator first, Iterator last, std::input_iterator_tag) -{ - return 0; -} - -template <class Iterator> -inline typename std::iterator_traits<Iterator>::difference_type -distance_fw (Iterator first, Iterator last, std::forward_iterator_tag) -{ - return std::distance(first, last); -} - -template <class Iterator> -inline typename std::iterator_traits<Iterator>::difference_type -distance_fw (Iterator first, Iterator last) +namespace Internal { - typedef typename std::iterator_traits<Iterator>::iterator_category tag; - return distance_fw(first, last, tag()); -} + template<bool Flag, typename IfTrue, typename IfFalse> + struct IF; + template<typename IfTrue, typename IfFalse> + struct IF<true, IfTrue, IfFalse> + { typedef IfTrue type; }; + + template <typename IfTrue, typename IfFalse> + struct IF<false, IfTrue, IfFalse> + { typedef IfFalse type; }; + + // Helper function: return distance(first, last) for forward + // iterators, or 0 for input iterators. + template<class Iterator> + inline typename std::iterator_traits<Iterator>::difference_type + distance_fw(Iterator first, Iterator last, std::input_iterator_tag) + { return 0; } + + template<class Iterator> + inline typename std::iterator_traits<Iterator>::difference_type + distance_fw(Iterator first, Iterator last, std::forward_iterator_tag) + { return std::distance(first, last); } + + template<class Iterator> + inline typename std::iterator_traits<Iterator>::difference_type + distance_fw(Iterator first, Iterator last) + { + typedef typename std::iterator_traits<Iterator>::iterator_category tag; + return distance_fw(first, last, tag()); + } + } // namespace Internal //---------------------------------------------------------------------- @@ -109,140 +108,187 @@ distance_fw (Iterator first, Iterator last) // nodes also store a hash code. In some cases (e.g. strings) this may // be a performance win. -namespace Internal { - -template <typename Value, bool cache_hash_code> struct hash_node; - -template <typename Value> -struct hash_node<Value, true> { - Value m_v; - std::size_t hash_code; - hash_node* m_next; -}; - -template <typename Value> -struct hash_node<Value, false> { - Value m_v; - hash_node* m_next; -}; - -// Local iterators, used to iterate within a bucket but not between -// buckets. - -template <typename Value, bool cache> -struct node_iterator_base { - node_iterator_base(hash_node<Value, cache>* p) : m_cur(p) { } - void incr() { m_cur = m_cur->m_next; } - - hash_node<Value, cache>* m_cur; -}; - -template <typename Value, bool cache> -inline bool operator== (const node_iterator_base<Value, cache>& x, - const node_iterator_base<Value, cache>& y) +namespace Internal { - return x.m_cur == y.m_cur; -} - -template <typename Value, bool cache> -inline bool operator!= (const node_iterator_base<Value, cache>& x, - const node_iterator_base<Value, cache>& y) -{ - return x.m_cur != y.m_cur; -} - -template <typename Value, bool is_const, bool cache> -struct node_iterator : public node_iterator_base<Value, cache> { - typedef Value value_type; - typedef typename IF<is_const, const Value*, Value*>::type pointer; - typedef typename IF<is_const, const Value&, Value&>::type reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - explicit node_iterator (hash_node<Value, cache>* p = 0) - : node_iterator_base<Value, cache>(p) { } - node_iterator (const node_iterator<Value, true, cache>& x) - : node_iterator_base<Value, cache>(x.m_cur) { } - - reference operator*() const { return this->m_cur->m_v; } - pointer operator->() const { return &this->m_cur->m_v; } - - node_iterator& operator++() { this->incr(); return *this; } - node_iterator operator++(int) - { node_iterator tmp(*this); this->incr(); return tmp; } -}; - -template <typename Value, bool cache> -struct hashtable_iterator_base { - hashtable_iterator_base(hash_node<Value, cache>* node, - hash_node<Value, cache>** bucket) - : m_cur_node (node), m_cur_bucket (bucket) - { } + template<typename Value, bool cache_hash_code> + struct hash_node; + + template<typename Value> + struct hash_node<Value, true> + { + Value m_v; + std::size_t hash_code; + hash_node* m_next; + }; + + template<typename Value> + struct hash_node<Value, false> + { + Value m_v; + hash_node* m_next; + }; + + // Local iterators, used to iterate within a bucket but not between + // buckets. + + template<typename Value, bool cache> + struct node_iterator_base + { + node_iterator_base(hash_node<Value, cache>* p) + : m_cur(p) { } + + void + incr() + { m_cur = m_cur->m_next; } + + hash_node<Value, cache>* m_cur; + }; + + template<typename Value, bool cache> + inline bool + operator==(const node_iterator_base<Value, cache>& x, + const node_iterator_base<Value, cache>& y) + { return x.m_cur == y.m_cur; } + + template<typename Value, bool cache> + inline bool + operator!=(const node_iterator_base<Value, cache>& x, + const node_iterator_base<Value, cache>& y) + { return x.m_cur != y.m_cur; } + + template<typename Value, bool is_const, bool cache> + struct node_iterator + : public node_iterator_base<Value, cache> + { + typedef Value value_type; + typedef typename IF<is_const, const Value*, Value*>::type pointer; + typedef typename IF<is_const, const Value&, Value&>::type reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + explicit + node_iterator(hash_node<Value, cache>* p = 0) + : node_iterator_base<Value, cache>(p) { } + + node_iterator(const node_iterator<Value, true, cache>& x) + : node_iterator_base<Value, cache>(x.m_cur) { } + + reference + operator*() const + { return this->m_cur->m_v; } + + pointer + operator->() const + { return &this->m_cur->m_v; } + + node_iterator& + operator++() + { + this->incr(); + return *this; + } + + node_iterator + operator++(int) + { + node_iterator tmp(*this); + this->incr(); + return tmp; + } + }; + + template<typename Value, bool cache> + struct hashtable_iterator_base + { + hashtable_iterator_base(hash_node<Value, cache>* node, + hash_node<Value, cache>** bucket) + : m_cur_node(node), m_cur_bucket(bucket) + { } + + void + incr() + { + m_cur_node = m_cur_node->m_next; + if (!m_cur_node) + m_incr_bucket(); + } - void incr() { - m_cur_node = m_cur_node->m_next; - if (!m_cur_node) + void m_incr_bucket(); - } - - void m_incr_bucket(); - - hash_node<Value, cache>* m_cur_node; - hash_node<Value, cache>** m_cur_bucket; -}; - -// Global iterators, used for arbitrary iteration within a hash -// table. Larger and more expensive than local iterators. - -template <typename Value, bool cache> -void hashtable_iterator_base<Value, cache>::m_incr_bucket() -{ - ++m_cur_bucket; - - // This loop requires the bucket array to have a non-null sentinel - while (!*m_cur_bucket) - ++m_cur_bucket; - m_cur_node = *m_cur_bucket; -} - -template <typename Value, bool cache> -inline bool operator== (const hashtable_iterator_base<Value, cache>& x, - const hashtable_iterator_base<Value, cache>& y) -{ - return x.m_cur_node == y.m_cur_node; -} + hash_node<Value, cache>* m_cur_node; + hash_node<Value, cache>** m_cur_bucket; + }; + + // Global iterators, used for arbitrary iteration within a hash + // table. Larger and more expensive than local iterators. + template<typename Value, bool cache> + void + hashtable_iterator_base<Value, cache>:: + m_incr_bucket() + { + ++m_cur_bucket; + + // This loop requires the bucket array to have a non-null sentinel. + while (!*m_cur_bucket) + ++m_cur_bucket; + m_cur_node = *m_cur_bucket; + } -template <typename Value, bool cache> -inline bool operator!= (const hashtable_iterator_base<Value, cache>& x, - const hashtable_iterator_base<Value, cache>& y) -{ - return x.m_cur_node != y.m_cur_node; -} + template<typename Value, bool cache> + inline bool + operator==(const hashtable_iterator_base<Value, cache>& x, + const hashtable_iterator_base<Value, cache>& y) + { return x.m_cur_node == y.m_cur_node; } + + template<typename Value, bool cache> + inline bool + operator!=(const hashtable_iterator_base<Value, cache>& x, + const hashtable_iterator_base<Value, cache>& y) + { return x.m_cur_node != y.m_cur_node; } + + template<typename Value, bool is_const, bool cache> + struct hashtable_iterator + : public hashtable_iterator_base<Value, cache> + { + typedef Value value_type; + typedef typename IF<is_const, const Value*, Value*>::type pointer; + typedef typename IF<is_const, const Value&, Value&>::type reference; + typedef std::ptrdiff_t difference_type; + typedef std::forward_iterator_tag iterator_category; + + hashtable_iterator(hash_node<Value, cache>* p, + hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(p, b) { } + + hashtable_iterator(hash_node<Value, cache>** b) + : hashtable_iterator_base<Value, cache>(*b, b) { } + + hashtable_iterator(const hashtable_iterator<Value, true, cache>& x) + : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { } -template <typename Value, bool is_const, bool cache> -struct hashtable_iterator : public hashtable_iterator_base<Value, cache> -{ - typedef Value value_type; - typedef typename IF<is_const, const Value*, Value*>::type pointer; - typedef typename IF<is_const, const Value&, Value&>::type reference; - typedef std::ptrdiff_t difference_type; - typedef std::forward_iterator_tag iterator_category; - - hashtable_iterator (hash_node<Value, cache>* p, hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(p, b) { } - hashtable_iterator (hash_node<Value, cache>** b) - : hashtable_iterator_base<Value, cache>(*b, b) { } - hashtable_iterator (const hashtable_iterator<Value, true, cache>& x) - : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { } - - reference operator*() const { return this->m_cur_node->m_v; } - pointer operator->() const { return &this->m_cur_node->m_v; } - - hashtable_iterator& operator++() { this->incr(); return *this; } - hashtable_iterator operator++(int) - { hashtable_iterator tmp(*this); this->incr(); return tmp; } -}; + reference + operator*() const + { return this->m_cur_node->m_v; } + + pointer + operator->() const + { return &this->m_cur_node->m_v; } + + hashtable_iterator& + operator++() + { + this->incr(); + return *this; + } + + hashtable_iterator + operator++(int) + { + hashtable_iterator tmp(*this); + this->incr(); + return tmp; } + }; } // namespace Internal @@ -250,193 +296,218 @@ struct hashtable_iterator : public hashtable_iterator_base<Value, cache> // Many of class template hashtable's template parameters are policy // classes. These are defaults for the policies. -namespace Internal { - -// The two key extraction policies used by the *set and *map variants. -template <typename T> -struct identity { - T operator()(const T& t) const { return t; } -}; - -template <typename Pair> -struct extract1st { - typename Pair::first_type operator()(const Pair& p) const { return p.first; } -}; - -// Default range hashing function: use division to fold a large number -// into the range [0, N). -struct mod_range_hashing +namespace Internal { - typedef std::size_t first_argument_type; - typedef std::size_t second_argument_type; - typedef std::size_t result_type; + // The two key extraction policies used by the *set and *map variants. + template<typename T> + struct identity + { + T + operator()(const T& t) const + { return t; } + }; + + template<typename Pair> + struct extract1st + { + typename Pair::first_type + operator()(const Pair& p) const + { return p.first; } + }; + + // Default range hashing function: use division to fold a large number + // into the range [0, N). + struct mod_range_hashing + { + typedef std::size_t first_argument_type; + typedef std::size_t second_argument_type; + typedef std::size_t result_type; - result_type operator() (first_argument_type r, second_argument_type N) const + result_type + operator() (first_argument_type r, second_argument_type N) const { return r % N; } -}; - -// Default ranged hash function H. In principle it should be a -// function object composed from objects of type H1 and H2 such that -// h(k, N) = h2(h1(k), N), but that would mean making extra copies of -// h1 and h2. So instead we'll just use a tag to tell class template -// hashtable to do that composition. -struct default_ranged_hash { }; + }; -// Default value for rehash policy. Bucket size is (usually) the -// smallest prime that keeps the load factor small enough. + // Default ranged hash function H. In principle it should be a + // function object composed from objects of type H1 and H2 such that + // h(k, N) = h2(h1(k), N), but that would mean making extra copies of + // h1 and h2. So instead we'll just use a tag to tell class template + // hashtable to do that composition. + struct default_ranged_hash { }; -struct prime_rehash_policy -{ - prime_rehash_policy (float z = 1.0); - - float max_load_factor() const; - - // Return a bucket size no smaller than n. - std::size_t next_bkt (std::size_t n) const; - - // Return a bucket count appropriate for n elements - std::size_t bkt_for_elements (std::size_t n) const; - - // n_bkt is current bucket count, n_elt is current element count, - // and n_ins is number of elements to be inserted. Do we need to - // increase bucket count? If so, return make_pair(true, n), where n - // is the new bucket count. If not, return make_pair(false, 0). - std::pair<bool, std::size_t> - need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const; - - float m_max_load_factor; - float m_growth_factor; - mutable std::size_t m_next_resize; -}; - -// XXX This is a hack. prime_rehash_policy's member functions, and -// certainly the list of primes, should be defined in a .cc file. -// We're temporarily putting them in a header because we don't have a -// place to put TR1 .cc files yet. There's no good reason for any of -// prime_rehash_policy's member functions to be inline, and there's -// certainly no good reason for X<> to exist at all. - -struct lt { - template <typename X, typename Y> bool operator()(X x, Y y) { return x < y; } -}; - -template <int dummy> -struct X { - static const int n_primes = 256; - static const unsigned long primes[n_primes + 1]; -}; - -template <int dummy> -const int X<dummy>::n_primes; - -template <int dummy> -const unsigned long X<dummy>::primes[n_primes + 1] = + // Default value for rehash policy. Bucket size is (usually) the + // smallest prime that keeps the load factor small enough. + struct prime_rehash_policy { - 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, - 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, - 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, - 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, - 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, - 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, - 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, - 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, - 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, - 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, - 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, - 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, - 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, - 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, - 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, - 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, - 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, - 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, - 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, - 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, - 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, - 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, - 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, - 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, - 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, - 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, - 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, - 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, - 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, - 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, - 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, - 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, - 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, - 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, - 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, - 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, - 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, - 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, - 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, - 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, - 4294967291ul, - 4294967291ul // sentinel so we don't have to test result of lower_bound + prime_rehash_policy(float z = 1.0); + + float + max_load_factor() const; + + // Return a bucket size no smaller than n. + std::size_t + next_bkt(std::size_t n) const; + + // Return a bucket count appropriate for n elements + std::size_t + bkt_for_elements(std::size_t n) const; + + // n_bkt is current bucket count, n_elt is current element count, + // and n_ins is number of elements to be inserted. Do we need to + // increase bucket count? If so, return make_pair(true, n), where n + // is the new bucket count. If not, return make_pair(false, 0). + std::pair<bool, std::size_t> + need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const; + + float m_max_load_factor; + float m_growth_factor; + mutable std::size_t m_next_resize; }; -inline prime_rehash_policy::prime_rehash_policy (float z) - : m_max_load_factor(z), - m_growth_factor (2.f), - m_next_resize (0) -{ } - -inline float prime_rehash_policy::max_load_factor() const -{ - return m_max_load_factor; -} + // XXX This is a hack. prime_rehash_policy's member functions, and + // certainly the list of primes, should be defined in a .cc file. + // We're temporarily putting them in a header because we don't have a + // place to put TR1 .cc files yet. There's no good reason for any of + // prime_rehash_policy's member functions to be inline, and there's + // certainly no good reason for X<> to exist at all. + + struct lt + { + template<typename X, typename Y> + bool + operator()(X x, Y y) + { return x < y; } + }; -// Return a prime no smaller than n. -inline std::size_t prime_rehash_policy::next_bkt (std::size_t n) const -{ - const unsigned long* const last = X<0>::primes + X<0>::n_primes; - const unsigned long* p = std::lower_bound (X<0>::primes, last, n); - m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return *p; -} + template<int dummy> + struct X + { + static const int n_primes = 256; + static const unsigned long primes[n_primes + 1]; + }; + + template<int dummy> + const int X<dummy>::n_primes; + + template<int dummy> + const unsigned long X<dummy>::primes[n_primes + 1] = + { + 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul, + 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul, + 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul, + 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul, + 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul, + 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul, + 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul, + 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul, + 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul, + 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul, + 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul, + 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul, + 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul, + 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul, + 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul, + 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul, + 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul, + 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul, + 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul, + 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul, + 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul, + 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul, + 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul, + 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul, + 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul, + 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul, + 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul, + 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul, + 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul, + 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul, + 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul, + 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul, + 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul, + 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul, + 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul, + 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul, + 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul, + 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul, + 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul, + 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul, + 4294967291ul, + 4294967291ul // sentinel so we don't have to test result of lower_bound + }; + + inline + prime_rehash_policy:: + prime_rehash_policy(float z) + : m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0) + { } -// Return the smallest prime p such that alpha p >= n, where alpha -// is the load factor. -inline std::size_t prime_rehash_policy::bkt_for_elements (std::size_t n) const -{ - const unsigned long* const last = X<0>::primes + X<0>::n_primes; - const float min_bkts = n / m_max_load_factor; - const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt()); - m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return *p; -} + inline float + prime_rehash_policy:: + max_load_factor() const + { return m_max_load_factor; } -// Finds the smallest prime p such that alpha p > n_elt + n_ins. -// If p > n_bkt, return make_pair(true, p); otherwise return -// make_pair(false, 0). In principle this isn't very different from -// bkt_for_elements. + // Return a prime no smaller than n. + inline std::size_t + prime_rehash_policy:: + next_bkt(std::size_t n) const + { + const unsigned long* const last = X<0>::primes + X<0>::n_primes; + const unsigned long* p = std::lower_bound (X<0>::primes, last, n); + m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); + return *p; + } -// The only tricky part is that we're caching the element count at -// which we need to rehash, so we don't have to do a floating-point -// multiply for every insertion. + // Return the smallest prime p such that alpha p >= n, where alpha + // is the load factor. + inline std::size_t + prime_rehash_policy:: + bkt_for_elements(std::size_t n) const + { + const unsigned long* const last = X<0>::primes + X<0>::n_primes; + const float min_bkts = n / m_max_load_factor; + const unsigned long* p = std::lower_bound (X<0>::primes, last, + min_bkts, lt()); + m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); + return *p; + } -inline std::pair<bool, std::size_t> -prime_rehash_policy -::need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const -{ - if (n_elt + n_ins > m_next_resize) { - float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor; - if (min_bkts > n_bkt) { - min_bkts = std::max (min_bkts, m_growth_factor * n_bkt); - const unsigned long* const last = X<0>::primes + X<0>::n_primes; - const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt()); - m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); - return std::make_pair(true, *p); - } - else { - m_next_resize = static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor)); + // Finds the smallest prime p such that alpha p > n_elt + n_ins. + // If p > n_bkt, return make_pair(true, p); otherwise return + // make_pair(false, 0). In principle this isn't very different from + // bkt_for_elements. + + // The only tricky part is that we're caching the element count at + // which we need to rehash, so we don't have to do a floating-point + // multiply for every insertion. + + inline std::pair<bool, std::size_t> + prime_rehash_policy:: + need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const + { + if (n_elt + n_ins > m_next_resize) + { + float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor; + if (min_bkts > n_bkt) + { + min_bkts = std::max (min_bkts, m_growth_factor * n_bkt); + const unsigned long* const last = X<0>::primes + X<0>::n_primes; + const unsigned long* p = std::lower_bound (X<0>::primes, last, + min_bkts, lt()); + m_next_resize = + static_cast<std::size_t>(std::ceil(*p * m_max_load_factor)); + return std::make_pair(true, *p); + } + else + { + m_next_resize = + static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor)); + return std::make_pair(false, 0); + } + } + else return std::make_pair(false, 0); - } } - else - return std::make_pair(false, 0); -} } // namespace Internal @@ -449,983 +520,1182 @@ prime_rehash_policy // need to access other members of class template hashtable, so we use // the "curiously recurring template pattern" for them. -namespace Internal { - -// class template map_base. If the hashtable has a value type of the -// form pair<T1, T2> and a key extraction policy that returns the -// first part of the pair, the hashtable gets a mapped_type typedef. -// If it satisfies those criteria and also has unique keys, then it -// also gets an operator[]. - -template <typename K, typename V, typename Ex, bool unique, typename Hashtable> -struct map_base { }; - -template <typename K, typename Pair, typename Hashtable> -struct map_base<K, Pair, extract1st<Pair>, false, Hashtable> -{ - typedef typename Pair::second_type mapped_type; -}; - -template <typename K, typename Pair, typename Hashtable> -struct map_base<K, Pair, extract1st<Pair>, true, Hashtable> -{ - typedef typename Pair::second_type mapped_type; - mapped_type& operator[](const K& k) { - Hashtable* h = static_cast<Hashtable*>(this); - typename Hashtable::iterator it = h->insert(std::make_pair(k, mapped_type())).first; - return it->second; - } -}; - -// class template rehash_base. Give hashtable the max_load_factor -// functions iff the rehash policy is prime_rehash_policy. -template <typename RehashPolicy, typename Hashtable> -struct rehash_base { }; - -template <typename Hashtable> -struct rehash_base<prime_rehash_policy, Hashtable> +namespace Internal { - float max_load_factor() const { - const Hashtable* This = static_cast<const Hashtable*>(this); - return This->rehash_policy()->max_load_factor(); - } - - void max_load_factor(float z) { - Hashtable* This = static_cast<Hashtable*>(this); - This->rehash_policy(prime_rehash_policy(z)); - } -}; - -// Class template hash_code_base. Encapsulates two policy issues that -// aren't quite orthogonal. -// (1) the difference between using a ranged hash function and using -// the combination of a hash function and a range-hashing function. -// In the former case we don't have such things as hash codes, so -// we have a dummy type as placeholder. -// (2) Whether or not we cache hash codes. Caching hash codes is -// meaningless if we have a ranged hash function. -// We also put the key extraction and equality comparison function -// objects here, for convenience. - -// Primary template: unused except as a hook for specializations. - -template <typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H, - bool cache_hash_code> -struct hash_code_base; - -// Specialization: ranged hash function, no caching hash codes. H1 -// and H2 are provided but ignored. We define a dummy hash code type. -template <typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H> -struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, false> -{ -protected: - hash_code_base (const ExtractKey& ex, const Equal& eq, - const H1&, const H2&, const H& h) - : m_extract(ex), m_eq(eq), m_ranged_hash(h) { } - - typedef void* hash_code_t; - hash_code_t m_hash_code (const Key& k) const { return 0; } - std::size_t bucket_index (const Key& k, hash_code_t, std::size_t N) const - { return m_ranged_hash (k, N); } - std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const { - return m_ranged_hash (m_extract (p->m_v), N); - } + // class template map_base. If the hashtable has a value type of the + // form pair<T1, T2> and a key extraction policy that returns the + // first part of the pair, the hashtable gets a mapped_type typedef. + // If it satisfies those criteria and also has unique keys, then it + // also gets an operator[]. - bool compare (const Key& k, hash_code_t, hash_node<Value, false>* n) const - { return m_eq (k, m_extract(n->m_v)); } - - void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { } - - void m_swap(hash_code_base& x) { - m_extract.m_swap(x); - m_eq.m_swap(x); - m_ranged_hash.m_swap(x); - } - -protected: - ExtractKey m_extract; - Equal m_eq; - H m_ranged_hash; -}; - - -// No specialization for ranged hash function while caching hash codes. -// That combination is meaningless, and trying to do it is an error. + template<typename K, typename V, typename Ex, bool unique, typename Hashtable> + struct map_base { }; + + template<typename K, typename Pair, typename Hashtable> + struct map_base<K, Pair, extract1st<Pair>, false, Hashtable> + { + typedef typename Pair::second_type mapped_type; + }; + + template<typename K, typename Pair, typename Hashtable> + struct map_base<K, Pair, extract1st<Pair>, true, Hashtable> + { + typedef typename Pair::second_type mapped_type; + + mapped_type& + operator[](const K& k) + { + Hashtable* h = static_cast<Hashtable*>(this); + typename Hashtable::iterator it = + h->insert(std::make_pair(k, mapped_type())).first; + return it->second; + } + }; + + // class template rehash_base. Give hashtable the max_load_factor + // functions iff the rehash policy is prime_rehash_policy. + template<typename RehashPolicy, typename Hashtable> + struct rehash_base { }; + + template<typename Hashtable> + struct rehash_base<prime_rehash_policy, Hashtable> + { + float + max_load_factor() const + { + const Hashtable* This = static_cast<const Hashtable*>(this); + return This->rehash_policy()->max_load_factor(); + } + void + max_load_factor(float z) + { + Hashtable* This = static_cast<Hashtable*>(this); + This->rehash_policy(prime_rehash_policy(z)); + } + }; + + // Class template hash_code_base. Encapsulates two policy issues that + // aren't quite orthogonal. + // (1) the difference between using a ranged hash function and using + // the combination of a hash function and a range-hashing function. + // In the former case we don't have such things as hash codes, so + // we have a dummy type as placeholder. + // (2) Whether or not we cache hash codes. Caching hash codes is + // meaningless if we have a ranged hash function. + // We also put the key extraction and equality comparison function + // objects here, for convenience. + + // Primary template: unused except as a hook for specializations. + + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2, typename H, + bool cache_hash_code> + struct hash_code_base; + + // Specialization: ranged hash function, no caching hash codes. H1 + // and H2 are provided but ignored. We define a dummy hash code type. + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2, typename H> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false> + { + protected: + hash_code_base(const ExtractKey& ex, const Equal& eq, + const H1&, const H2&, const H& h) + : m_extract(ex), m_eq(eq), m_ranged_hash(h) { } + + typedef void* hash_code_t; + + hash_code_t + m_hash_code(const Key& k) const + { return 0; } + + std::size_t + bucket_index(const Key& k, hash_code_t, std::size_t N) const + { return m_ranged_hash (k, N); } -// Specialization: ranged hash function, cache hash codes. This -// combination is meaningless, so we provide only a declaration -// and no definition. + std::size_t + bucket_index(const hash_node<Value, false>* p, std::size_t N) const + { return m_ranged_hash (m_extract (p->m_v), N); } + + bool + compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const + { return m_eq (k, m_extract(n->m_v)); } + + void + copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const + { } + + void + m_swap(hash_code_base& x) + { + m_extract.m_swap(x); + m_eq.m_swap(x); + m_ranged_hash.m_swap(x); + } -template <typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2, typename H> -struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, true>; + protected: + ExtractKey m_extract; + Equal m_eq; + H m_ranged_hash; + }; -// Specialization: hash function and range-hashing function, no -// caching of hash codes. H is provided but ignored. Provides -// typedef and accessor required by TR1. + // No specialization for ranged hash function while caching hash codes. + // That combination is meaningless, and trying to do it is an error. + + + // Specialization: ranged hash function, cache hash codes. This + // combination is meaningless, so we provide only a declaration + // and no definition. + + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2, typename H> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>; -template <typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2> -struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, false> -{ - typedef H1 hasher; - hasher hash_function() const { return m_h1; } - -protected: - hash_code_base (const ExtractKey& ex, const Equal& eq, - const H1& h1, const H2& h2, const default_ranged_hash&) - : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } - - typedef std::size_t hash_code_t; - hash_code_t m_hash_code (const Key& k) const { return m_h1(k); } - std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const - { return m_h2 (c, N); } - std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const { - return m_h2 (m_h1 (m_extract (p->m_v)), N); - } - bool compare (const Key& k, hash_code_t, hash_node<Value, false>* n) const - { return m_eq (k, m_extract(n->m_v)); } + // Specialization: hash function and range-hashing function, no + // caching of hash codes. H is provided but ignored. Provides + // typedef and accessor required by TR1. + + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, + default_ranged_hash, false> + { + typedef H1 hasher; + + hasher + hash_function() const + { return m_h1; } + + protected: + hash_code_base(const ExtractKey& ex, const Equal& eq, + const H1& h1, const H2& h2, const default_ranged_hash&) + : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } + + typedef std::size_t hash_code_t; + + hash_code_t + m_hash_code(const Key& k) const + { return m_h1(k); } + + std::size_t + bucket_index(const Key&, hash_code_t c, std::size_t N) const + { return m_h2 (c, N); } + + std::size_t + bucket_index(const hash_node<Value, false>* p, std::size_t N) const + { return m_h2 (m_h1 (m_extract (p->m_v)), N); } + + bool + compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const + { return m_eq (k, m_extract(n->m_v)); } + + void + copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const + { } + + void + m_swap(hash_code_base& x) + { + m_extract.m_swap(x); + m_eq.m_swap(x); + m_h1.m_swap(x); + m_h2.m_swap(x); + } - void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { } + protected: + ExtractKey m_extract; + Equal m_eq; + H1 m_h1; + H2 m_h2; + }; + + // Specialization: hash function and range-hashing function, + // caching hash codes. H is provided but ignored. Provides + // typedef and accessor required by TR1. + template<typename Key, typename Value, + typename ExtractKey, typename Equal, + typename H1, typename H2> + struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, + default_ranged_hash, true> + { + typedef H1 hasher; + + hasher + hash_function() const + { return m_h1; } + + protected: + hash_code_base(const ExtractKey& ex, const Equal& eq, + const H1& h1, const H2& h2, const default_ranged_hash&) + : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } + + typedef std::size_t hash_code_t; + + hash_code_t + m_hash_code (const Key& k) const + { return m_h1(k); } + + std::size_t + bucket_index(const Key&, hash_code_t c, std::size_t N) const + { return m_h2 (c, N); } + + std::size_t + bucket_index(const hash_node<Value, true>* p, std::size_t N) const + { return m_h2 (p->hash_code, N); } + + bool + compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const + { return c == n->hash_code && m_eq(k, m_extract(n->m_v)); } + + void + copy_code(hash_node<Value, true>* to, + const hash_node<Value, true>* from) const + { to->hash_code = from->hash_code; } + + void + m_swap(hash_code_base& x) + { + m_extract.m_swap(x); + m_eq.m_swap(x); + m_h1.m_swap(x); + m_h2.m_swap(x); + } + + protected: + ExtractKey m_extract; + Equal m_eq; + H1 m_h1; + H2 m_h2; + }; - void m_swap(hash_code_base& x) { - m_extract.m_swap(x); - m_eq.m_swap(x); - m_h1.m_swap(x); - m_h2.m_swap(x); - } +} // namespace internal -protected: - ExtractKey m_extract; - Equal m_eq; - H1 m_h1; - H2 m_h2; -}; - -// Specialization: hash function and range-hashing function, -// caching hash codes. H is provided but ignored. Provides -// typedef and accessor required by TR1. -template <typename Key, typename Value, - typename ExtractKey, typename Equal, - typename H1, typename H2> -struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, true> +namespace std +{ +namespace tr1 { - typedef H1 hasher; - hasher hash_function() const { return m_h1; } - -protected: - hash_code_base (const ExtractKey& ex, const Equal& eq, - const H1& h1, const H2& h2, const default_ranged_hash&) - : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { } - - typedef std::size_t hash_code_t; - hash_code_t m_hash_code (const Key& k) const { return m_h1(k); } - std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const - { return m_h2 (c, N); } - - std::size_t bucket_index (const hash_node<Value, true>* p, std::size_t N) const { - return m_h2 (p->hash_code, N); - } - - bool compare (const Key& k, hash_code_t c, hash_node<Value, true>* n) const - { return c == n->hash_code && m_eq (k, m_extract(n->m_v)); } + //---------------------------------------------------------------------- + // Class template hashtable, class definition. + + // Meaning of class template hashtable's template parameters + + // Key and Value: arbitrary CopyConstructible types. + + // Allocator: an allocator type ([lib.allocator.requirements]) whose + // value type is Value. + + // ExtractKey: function object that takes a object of type Value + // and returns a value of type Key. + + // Equal: function object that takes two objects of type k and returns + // a bool-like value that is true if the two objects are considered equal. + + // H1: the hash function. A unary function object with argument type + // Key and result type size_t. Return values should be distributed + // over the entire range [0, numeric_limits<size_t>:::max()]. + + // H2: the range-hashing function (in the terminology of Tavori and + // Dreizin). A binary function object whose argument types and result + // type are all size_t. Given arguments r and N, the return value is + // in the range [0, N). + + // H: the ranged hash function (Tavori and Dreizin). A binary function + // whose argument types are Key and size_t and whose result type is + // size_t. Given arguments k and N, the return value is in the range + // [0, N). Default: h(k, N) = h2(h1(k), N). If H is anything other + // than the default, H1 and H2 are ignored. + + // RehashPolicy: Policy class with three members, all of which govern + // the bucket count. n_bkt(n) returns a bucket count no smaller + // than n. bkt_for_elements(n) returns a bucket count appropriate + // for an element count of n. need_rehash(n_bkt, n_elt, n_ins) + // determines whether, if the current bucket count is n_bkt and the + // current element count is n_elt, we need to increase the bucket + // count. If so, returns make_pair(true, n), where n is the new + // bucket count. If not, returns make_pair(false, <anything>). + + // ??? Right now it is hard-wired that the number of buckets never + // shrinks. Should we allow RehashPolicy to change that? + + // cache_hash_code: bool. true if we store the value of the hash + // function along with the value. This is a time-space tradeoff. + // Storing it may improve lookup speed by reducing the number of times + // we need to call the Equal function. + + // mutable_iterators: bool. true if hashtable::iterator is a mutable + // iterator, false if iterator and const_iterator are both const + // iterators. This is true for unordered_map and unordered_multimap, + // false for unordered_set and unordered_multiset. + + // unique_keys: bool. true if the return value of hashtable::count(k) + // is always at most one, false if it may be an arbitrary number. This + // true for unordered_set and unordered_map, false for unordered_multiset + // and unordered_multimap. + + template<typename Key, typename Value, + typename Allocator, + typename ExtractKey, typename Equal, + typename H1, typename H2, + typename H, typename RehashPolicy, + bool cache_hash_code, + bool mutable_iterators, + bool unique_keys> + class hashtable + : public Internal::rehash_base<RehashPolicy, + hashtable<Key, Value, Allocator, ExtractKey, + Equal, H1, H2, H, RehashPolicy, + cache_hash_code, mutable_iterators, + unique_keys> >, + public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, + cache_hash_code>, + public Internal::map_base<Key, Value, ExtractKey, unique_keys, + hashtable<Key, Value, Allocator, ExtractKey, + Equal, H1, H2, H, RehashPolicy, + cache_hash_code, mutable_iterators, + unique_keys> > + { + public: + typedef Allocator allocator_type; + typedef Value value_type; + typedef Key key_type; + typedef Equal key_equal; + // mapped_type, if present, comes from map_base. + // hasher, if present, comes from hash_code_base. + typedef typename Allocator::difference_type difference_type; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::reference reference; + typedef typename Allocator::const_reference const_reference; + + typedef Internal::node_iterator<value_type, !mutable_iterators, + cache_hash_code> + local_iterator; + typedef Internal::node_iterator<value_type, false, cache_hash_code> + const_local_iterator; + + typedef Internal::hashtable_iterator<value_type, !mutable_iterators, + cache_hash_code> + iterator; + typedef Internal::hashtable_iterator<value_type, false, cache_hash_code> + const_iterator; + + private: + typedef Internal::hash_node<Value, cache_hash_code> node; + typedef typename Allocator::template rebind<node>::other + node_allocator_t; + typedef typename Allocator::template rebind<node*>::other + bucket_allocator_t; + + private: + node_allocator_t m_node_allocator; + node** m_buckets; + size_type m_bucket_count; + size_type m_element_count; + RehashPolicy m_rehash_policy; + + node* + m_allocate_node(const value_type& v); + + void + m_deallocate_node(node* n); + + void + m_deallocate_nodes(node**, size_type); - void copy_code (hash_node<Value, true>* to, const hash_node<Value, true>* from) const - { to->hash_code = from->hash_code; } + node** + m_allocate_buckets(size_type n); + + void + m_deallocate_buckets(node**, size_type n); + + public: // Constructor, destructor, assignment, swap + hashtable(size_type bucket_hint, + const H1&, const H2&, const H&, + const Equal&, const ExtractKey&, + const allocator_type&); + + template<typename InIter> + hashtable(InIter first, InIter last, + size_type bucket_hint, + const H1&, const H2&, const H&, + const Equal&, const ExtractKey&, + const allocator_type&); + + hashtable(const hashtable&); + + hashtable& + operator=(const hashtable&); + + ~hashtable(); + + void swap(hashtable&); + + public: // Basic container operations + iterator + begin() + { + iterator i(m_buckets); + if (!i.m_cur_node) + i.m_incr_bucket(); + return i; + } - void m_swap(hash_code_base& x) { - m_extract.m_swap(x); - m_eq.m_swap(x); - m_h1.m_swap(x); - m_h2.m_swap(x); - } + const_iterator + begin() const + { + const_iterator i(m_buckets); + if (!i.m_cur_node) + i.m_incr_bucket(); + return i; + } -protected: - ExtractKey m_extract; - Equal m_eq; - H1 m_h1; - H2 m_h2; -}; + iterator + end() + { return iterator(m_buckets + m_bucket_count); } -} // namespace internal + const_iterator + end() const + { return const_iterator(m_buckets + m_bucket_count); } -namespace std { namespace tr1 { + size_type + size() const + { return m_element_count; } + + bool + empty() const + { return size() == 0; } -//---------------------------------------------------------------------- -// Class template hashtable, class definition. - -// Meaning of class template hashtable's template parameters - -// Key and Value: arbitrary CopyConstructible types. - -// Allocator: an allocator type ([lib.allocator.requirements]) whose -// value type is Value. - -// ExtractKey: function object that takes a object of type Value -// and returns a value of type Key. - -// Equal: function object that takes two objects of type k and returns -// a bool-like value that is true if the two objects are considered equal. - -// H1: the hash function. A unary function object with argument type -// Key and result type size_t. Return values should be distributed -// over the entire range [0, numeric_limits<size_t>:::max()]. - -// H2: the range-hashing function (in the terminology of Tavori and -// Dreizin). A binary function object whose argument types and result -// type are all size_t. Given arguments r and N, the return value is -// in the range [0, N). - -// H: the ranged hash function (Tavori and Dreizin). A binary function -// whose argument types are Key and size_t and whose result type is -// size_t. Given arguments k and N, the return value is in the range -// [0, N). Default: h(k, N) = h2(h1(k), N). If H is anything other -// than the default, H1 and H2 are ignored. - -// RehashPolicy: Policy class with three members, all of which govern -// the bucket count. n_bkt(n) returns a bucket count no smaller -// than n. bkt_for_elements(n) returns a bucket count appropriate -// for an element count of n. need_rehash(n_bkt, n_elt, n_ins) -// determines whether, if the current bucket count is n_bkt and the -// current element count is n_elt, we need to increase the bucket -// count. If so, returns make_pair(true, n), where n is the new -// bucket count. If not, returns make_pair(false, <anything>). - -// ??? Right now it is hard-wired that the number of buckets never -// shrinks. Should we allow RehashPolicy to change that? - -// cache_hash_code: bool. true if we store the value of the hash -// function along with the value. This is a time-space tradeoff. -// Storing it may improve lookup speed by reducing the number of times -// we need to call the Equal function. - -// mutable_iterators: bool. true if hashtable::iterator is a mutable -// iterator, false if iterator and const_iterator are both const -// iterators. This is true for unordered_map and unordered_multimap, -// false for unordered_set and unordered_multiset. - -// unique_keys: bool. true if the return value of hashtable::count(k) -// is always at most one, false if it may be an arbitrary number. This -// true for unordered_set and unordered_map, false for unordered_multiset -// and unordered_multimap. - -template <typename Key, typename Value, - typename Allocator, - typename ExtractKey, typename Equal, - typename H1, typename H2, - typename H, typename RehashPolicy, - bool cache_hash_code, - bool mutable_iterators, - bool unique_keys> -class hashtable - : public Internal::rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> >, - public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, cache_hash_code>, - public Internal::map_base<Key, Value, ExtractKey, unique_keys, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> > -{ -public: - typedef Allocator allocator_type; - typedef Value value_type; - typedef Key key_type; - typedef Equal key_equal; - // mapped_type, if present, comes from map_base. - // hasher, if present, comes from hash_code_base. - typedef typename Allocator::difference_type difference_type; - typedef typename Allocator::size_type size_type; - typedef typename Allocator::reference reference; - typedef typename Allocator::const_reference const_reference; - - typedef Internal::node_iterator<value_type, !mutable_iterators, cache_hash_code> - local_iterator; - typedef Internal::node_iterator<value_type, false, cache_hash_code> - const_local_iterator; - - typedef Internal::hashtable_iterator<value_type, !mutable_iterators, cache_hash_code> - iterator; - typedef Internal::hashtable_iterator<value_type, false, cache_hash_code> - const_iterator; - -private: - typedef Internal::hash_node<Value, cache_hash_code> node; - typedef typename Allocator::template rebind<node>::other node_allocator_t; - typedef typename Allocator::template rebind<node*>::other bucket_allocator_t; - -private: - node_allocator_t m_node_allocator; - node** m_buckets; - size_type m_bucket_count; - size_type m_element_count; - RehashPolicy m_rehash_policy; - - node* m_allocate_node (const value_type& v); - void m_deallocate_node (node* n); - void m_deallocate_nodes (node**, size_type); - - node** m_allocate_buckets (size_type n); - void m_deallocate_buckets (node**, size_type n); - -public: // Constructor, destructor, assignment, swap - hashtable(size_type bucket_hint, - const H1&, const H2&, const H&, - const Equal&, const ExtractKey&, - const allocator_type&); + allocator_type + get_allocator() const + { return m_node_allocator; } - template <typename InIter> - hashtable(InIter first, InIter last, - size_type bucket_hint, - const H1&, const H2&, const H&, - const Equal&, const ExtractKey&, - const allocator_type&); + size_type + max_size() const + { return m_node_allocator.max_size(); } + + public: // Bucket operations + size_type + bucket_count() const + { return m_bucket_count; } - hashtable(const hashtable&); - hashtable& operator=(const hashtable&); - ~hashtable(); - - void swap(hashtable&); - -public: // Basic container operations - iterator begin() { - iterator i(m_buckets); - if (!i.m_cur_node) - i.m_incr_bucket(); - return i; - } - - const_iterator begin() const { - const_iterator i(m_buckets); - if (!i.m_cur_node) - i.m_incr_bucket(); - return i; - } + size_type + max_bucket_count() const + { return max_size(); } + + size_type + bucket_size(size_type n) const + { return std::distance(begin(n), end(n)); } + + size_type bucket(const key_type& k) const + { + return this->bucket_index(k, this->m_hash_code, this->m_bucket_count); + } - iterator end() - { return iterator(m_buckets + m_bucket_count); } - const_iterator end() const - { return const_iterator(m_buckets + m_bucket_count); } - - size_type size() const { return m_element_count; } - bool empty() const { return size() == 0; } - - allocator_type get_allocator() const { return m_node_allocator; } - size_type max_size() const { return m_node_allocator.max_size(); } - -public: // Bucket operations - size_type bucket_count() const - { return m_bucket_count; } - size_type max_bucket_count() const - { return max_size(); } - size_type bucket_size (size_type n) const - { return std::distance(begin(n), end(n)); } - size_type bucket (const key_type& k) const - { return this->bucket_index (k, this->m_hash_code, this->m_bucket_count); } - - local_iterator begin(size_type n) - { return local_iterator(m_buckets[n]); } - local_iterator end(size_type n) - { return local_iterator(0); } - const_local_iterator begin(size_type n) const - { return const_local_iterator(m_buckets[n]); } - const_local_iterator end(size_type n) const - { return const_local_iterator(0); } - - float load_factor() const - { return static_cast<float>(size()) / static_cast<float>(bucket_count()); } - // max_load_factor, if present, comes from rehash_base. - - // Generalization of max_load_factor. Extension, not found in TR1. Only - // useful if RehashPolicy is something other than the default. - const RehashPolicy& rehash_policy() const { return m_rehash_policy; } - void rehash_policy (const RehashPolicy&); - -public: // lookup - iterator find(const key_type&); - const_iterator find(const key_type& k) const; - size_type count(const key_type& k) const; - std::pair<iterator, iterator> equal_range(const key_type& k); - std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const; - -private: // Insert and erase helper functions - // ??? This dispatching is a workaround for the fact that we don't - // have partial specialization of member templates; it would be - // better to just specialize insert on unique_keys. There may be a - // cleaner workaround. - typedef typename Internal::IF<unique_keys, std::pair<iterator, bool>, iterator>::type - Insert_Return_Type; - - node* find_node (node* p, const key_type& k, typename hashtable::hash_code_t c); - - std::pair<iterator, bool> insert (const value_type&, std::tr1::true_type); - iterator insert (const value_type&, std::tr1::false_type); - -public: // Insert and erase - Insert_Return_Type insert (const value_type& v) - { return this->insert (v, std::tr1::integral_constant<bool, unique_keys>()); } - Insert_Return_Type insert (const_iterator, const value_type& v) - { return this->insert(v); } - - template <typename InIter> void insert(InIter first, InIter last); - - void erase(const_iterator); - size_type erase(const key_type&); - void erase(const_iterator, const_iterator); - void clear(); - -public: - // Set number of buckets to be apropriate for container of n element. - void rehash (size_type n); - -private: - // Unconditionally change size of bucket array to n. - void m_rehash (size_type n); -}; + local_iterator + begin(size_type n) + { return local_iterator(m_buckets[n]); } + + local_iterator + end(size_type n) + { return local_iterator(0); } + + const_local_iterator + begin(size_type n) const + { return const_local_iterator(m_buckets[n]); } + + const_local_iterator + end(size_type n) const + { return const_local_iterator(0); } + + float + load_factor() const + { + return static_cast<float>(size()) / static_cast<float>(bucket_count()); + } + // max_load_factor, if present, comes from rehash_base. + + // Generalization of max_load_factor. Extension, not found in TR1. Only + // useful if RehashPolicy is something other than the default. + const RehashPolicy& + rehash_policy() const + { return m_rehash_policy; } + + void + rehash_policy(const RehashPolicy&); + + public: // lookup + iterator + find(const key_type&); + + const_iterator + find(const key_type& k) const; + + size_type + count(const key_type& k) const; + + std::pair<iterator, iterator> + equal_range(const key_type& k); + + std::pair<const_iterator, const_iterator> + equal_range(const key_type& k) const; + + private: // Insert and erase helper functions + // ??? This dispatching is a workaround for the fact that we don't + // have partial specialization of member templates; it would be + // better to just specialize insert on unique_keys. There may be a + // cleaner workaround. + typedef typename Internal::IF<unique_keys, + std::pair<iterator, bool>, iterator>::type + Insert_Return_Type; + + node* + find_node(node* p, const key_type& k, typename hashtable::hash_code_t c); + + std::pair<iterator, bool> + insert(const value_type&, std::tr1::true_type); + + iterator + insert + (const value_type&, std::tr1::false_type); + + public: // Insert and erase + Insert_Return_Type + insert(const value_type& v) + { + return this->insert(v, std::tr1::integral_constant<bool, + unique_keys>()); + } + + Insert_Return_Type + insert(const_iterator, const value_type& v) + { return this->insert(v); } -//---------------------------------------------------------------------- -// Definitions of class template hashtable's out-of-line member functions. - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node* -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_node (const value_type& v) -{ - node* n = m_node_allocator.allocate(1); - try { - get_allocator().construct(&n->m_v, v); - n->m_next = 0; - return n; - } - catch(...) { - m_node_allocator.deallocate(n, 1); - throw; - } -} + template<typename InIter> + void + insert(InIter first, InIter last); -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_deallocate_node (node* n) -{ - get_allocator().destroy(&n->m_v); - m_node_allocator.deallocate(n, 1); -} + void + erase(const_iterator); + + size_type + erase(const key_type&); + + void + erase(const_iterator, const_iterator); + + void + clear(); + + public: + // Set number of buckets to be apropriate for container of n element. + void rehash (size_type n); + + private: + // Unconditionally change size of bucket array to n. + void m_rehash (size_type n); + }; + + //---------------------------------------------------------------------- + // Definitions of class template hashtable's out-of-line member functions. + + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::node* + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + m_allocate_node(const value_type& v) + { + node* n = m_node_allocator.allocate(1); + try + { + get_allocator().construct(&n->m_v, v); + n->m_next = 0; + return n; + } + catch(...) + { + m_node_allocator.deallocate(n, 1); + throw; + } + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::m_deallocate_nodes (node** array, size_type n) -{ - for (size_type i = 0; i < n; ++i) { - node* p = array[i]; - while (p) { - node* tmp = p; - p = p->m_next; - m_deallocate_node (tmp); + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + m_deallocate_node(node* n) + { + get_allocator().destroy(&n->m_v); + m_node_allocator.deallocate(n, 1); } - array[i] = 0; - } -} -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node** -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_buckets (size_type n) -{ - bucket_allocator_t alloc(m_node_allocator); - - // We allocate one extra bucket to hold a sentinel, an arbitrary - // non-null pointer. Iterator increment relies on this. - node** p = alloc.allocate(n+1); - std::fill(p, p+n, (node*) 0); - p[n] = reinterpret_cast<node*>(0x1000); - return p; -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + m_deallocate_nodes(node** array, size_type n) + { + for (size_type i = 0; i < n; ++i) + { + node* p = array[i]; + while (p) + { + node* tmp = p; + p = p->m_next; + m_deallocate_node (tmp); + } + array[i] = 0; + } + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::m_deallocate_buckets (node** p, size_type n) -{ - bucket_allocator_t alloc(m_node_allocator); - alloc.deallocate(p, n+1); -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::node** + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + m_allocate_buckets(size_type n) + { + bucket_allocator_t alloc(m_node_allocator); + + // We allocate one extra bucket to hold a sentinel, an arbitrary + // non-null pointer. Iterator increment relies on this. + node** p = alloc.allocate(n+1); + std::fill(p, p+n, (node*) 0); + p[n] = reinterpret_cast<node*>(0x1000); + return p; + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::hashtable(size_type bucket_hint, - const H1& h1, const H2& h2, const H& h, - const Eq& eq, const Ex& exk, - const allocator_type& a) - : Internal::rehash_base<RP,hashtable> (), - Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h), - Internal::map_base<K,V,Ex,u,hashtable> (), - m_node_allocator(a), - m_bucket_count (0), - m_element_count (0), - m_rehash_policy () -{ - m_bucket_count = m_rehash_policy.next_bkt(bucket_hint); - m_buckets = m_allocate_buckets (m_bucket_count); -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + m_deallocate_buckets(node** p, size_type n) + { + bucket_allocator_t alloc(m_node_allocator); + alloc.deallocate(p, n+1); + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -template <typename InIter> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::hashtable(InIter f, InIter l, - size_type bucket_hint, - const H1& h1, const H2& h2, const H& h, - const Eq& eq, const Ex& exk, - const allocator_type& a) - : Internal::rehash_base<RP,hashtable> (), - Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h), - Internal::map_base<K,V,Ex,u,hashtable> (), - m_node_allocator(a), - m_bucket_count (0), - m_element_count (0), - m_rehash_policy () -{ - m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint), - m_rehash_policy.bkt_for_elements(Internal::distance_fw(f, l))); - m_buckets = m_allocate_buckets (m_bucket_count); - try { - for (; f != l; ++f) - this->insert (*f); - } - catch(...) { - clear(); - m_deallocate_buckets (m_buckets, m_bucket_count); - throw; - } -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + hashtable(size_type bucket_hint, + const H1& h1, const H2& h2, const H& h, + const Eq& eq, const Ex& exk, + const allocator_type& a) + : Internal::rehash_base<RP,hashtable>(), + Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h), + Internal::map_base<K, V, Ex, u, hashtable>(), + m_node_allocator(a), + m_bucket_count(0), + m_element_count(0), + m_rehash_policy() + { + m_bucket_count = m_rehash_policy.next_bkt(bucket_hint); + m_buckets = m_allocate_buckets(m_bucket_count); + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::hashtable(const hashtable& ht) - : Internal::rehash_base<RP,hashtable> (ht), - Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (ht), - Internal::map_base<K,V,Ex,u,hashtable> (ht), - m_node_allocator(ht.get_allocator()), - m_bucket_count (ht.m_bucket_count), - m_element_count (ht.m_element_count), - m_rehash_policy (ht.m_rehash_policy) -{ - m_buckets = m_allocate_buckets (m_bucket_count); - try { - for (size_t i = 0; i < ht.m_bucket_count; ++i) { - node* n = ht.m_buckets[i]; - node** tail = m_buckets + i; - while (n) { - *tail = m_allocate_node (n); - (*tail).copy_code_from (n); - tail = &((*tail)->m_next); - n = n->m_next; + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + template<typename InIter> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + hashtable(InIter f, InIter l, + size_type bucket_hint, + const H1& h1, const H2& h2, const H& h, + const Eq& eq, const Ex& exk, + const allocator_type& a) + : Internal::rehash_base<RP,hashtable>(), + Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c> (exk, eq, + h1, h2, h), + Internal::map_base<K,V,Ex,u,hashtable>(), + m_node_allocator(a), + m_bucket_count (0), + m_element_count(0), + m_rehash_policy() + { + m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint), + m_rehash_policy. + bkt_for_elements(Internal:: + distance_fw(f, l))); + m_buckets = m_allocate_buckets(m_bucket_count); + try + { + for (; f != l; ++f) + this->insert(*f); + } + catch(...) + { + clear(); + m_deallocate_buckets(m_buckets, m_bucket_count); + throw; + } } + + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + hashtable(const hashtable& ht) + : Internal::rehash_base<RP, hashtable>(ht), + Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht), + Internal::map_base<K, V, Ex, u, hashtable>(ht), + m_node_allocator(ht.get_allocator()), + m_bucket_count(ht.m_bucket_count), + m_element_count(ht.m_element_count), + m_rehash_policy(ht.m_rehash_policy) + { + m_buckets = m_allocate_buckets (m_bucket_count); + try + { + for (size_t i = 0; i < ht.m_bucket_count; ++i) + { + node* n = ht.m_buckets[i]; + node** tail = m_buckets + i; + while (n) + { + *tail = m_allocate_node(n); + (*tail).copy_code_from(n); + tail = &((*tail)->m_next); + n = n->m_next; + } + } + } + catch (...) + { + clear(); + m_deallocate_buckets (m_buckets, m_bucket_count); + throw; + } } - } - catch (...) { - clear(); - m_deallocate_buckets (m_buckets, m_bucket_count); - throw; - } -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>& -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::operator= (const hashtable& ht) -{ - hashtable tmp(ht); - this->swap(tmp); - return *this; -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::~hashtable() -{ - clear(); - m_deallocate_buckets(m_buckets, m_bucket_count); -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::swap (hashtable& x) -{ - // The only base class with member variables is hash_code_base. We - // define hash_code_base::m_swap because different specializations - // have different members. - Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x); - - // open LWG issue 431 - // std::swap(m_node_allocator, x.m_node_allocator); - std::swap (m_rehash_policy, x.m_rehash_policy); - std::swap (m_buckets, x.m_buckets); - std::swap (m_bucket_count, x.m_bucket_count); - std::swap (m_element_count, x.m_element_count); -} -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::rehash_policy (const RP& pol) -{ - m_rehash_policy = pol; - size_type n_bkt = pol.bkt_for_elements(m_element_count); - if (n_bkt > m_bucket_count) - m_rehash (n_bkt); -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k) -{ - typename hashtable::hash_code_t code = this->m_hash_code (k); - std::size_t n = this->bucket_index (k, code, this->bucket_count()); - node* p = find_node (m_buckets[n], k, code); - return p ? iterator(p, m_buckets + n) : this->end(); -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k) const -{ - typename hashtable::hash_code_t code = this->m_hash_code (k); - std::size_t n = this->bucket_index (k, code, this->bucket_count()); - node* p = find_node (m_buckets[n], k, code); - return p ? const_iterator(p, m_buckets + n) : this->end(); -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::count (const key_type& k) const -{ - typename hashtable::hash_code_t code = this->m_hash_code (k); - std::size_t n = this->bucket_index (k, code, this->bucket_count()); - size_t result = 0; - for (node* p = m_buckets[n]; p ; p = p->m_next) - if (this->compare (k, code, p)) - ++result; - return result; -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator, - typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k) -{ - typename hashtable::hash_code_t code = this->m_hash_code (k); - std::size_t n = this->bucket_index (k, code, this->bucket_count()); - node** head = m_buckets + n; - node* p = find_node (*head, k, code); - - if (p) { - node* p1 = p->m_next; - for (; p1 ; p1 = p1->m_next) - if (!this->compare (k, code, p1)) - break; - iterator first(p, head); - iterator last(p1, head); - if (!p1) - last.m_incr_bucket(); - return std::make_pair(first, last); - } - else - return std::make_pair (this->end(), this->end()); -} - -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator, - typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k) const -{ - typename hashtable::hash_code_t code = this->m_hash_code (k); - std::size_t n = this->bucket_index (k, code, this->bucket_count()); - node** head = m_buckets + n; - node* p = find_node (*head, k, code); - - if (p) { - node* p1 = p->m_next; - for (; p1 ; p1 = p1->m_next) - if (!this->compare (k, code, p1)) - break; - const_iterator first(p, head); - const_iterator last(p1, head); - if (!p1) - last.m_incr_bucket(); - return std::make_pair(first, last); - } - else - return std::make_pair (this->end(), this->end()); -} - -// Find the node whose key compares equal to k, beginning the search -// at p (usually the head of a bucket). Return nil if no node is found. -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node* -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::find_node (node* p, const key_type& k, typename hashtable::hash_code_t code) -{ - for ( ; p ; p = p->m_next) - if (this->compare (k, code, p)) - return p; - return false; -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>& + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + operator=(const hashtable& ht) + { + hashtable tmp(ht); + this->swap(tmp); + return *this; + } -// Insert v if no element with its key is already present. -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator, bool> -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::insert (const value_type& v, std::tr1::true_type) -{ - const key_type& k = this->m_extract(v); - typename hashtable::hash_code_t code = this->m_hash_code (k); - size_type n = this->bucket_index (k, code, m_bucket_count); + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + ~hashtable() + { + clear(); + m_deallocate_buckets(m_buckets, m_bucket_count); + } - if (node* p = find_node (m_buckets[n], k, code)) - return std::make_pair(iterator(p, m_buckets + n), false); + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + swap(hashtable& x) + { + // The only base class with member variables is hash_code_base. We + // define hash_code_base::m_swap because different specializations + // have different members. + Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x); + + // open LWG issue 431 + // std::swap(m_node_allocator, x.m_node_allocator); + std::swap(m_rehash_policy, x.m_rehash_policy); + std::swap(m_buckets, x.m_buckets); + std::swap(m_bucket_count, x.m_bucket_count); + std::swap(m_element_count, x.m_element_count); + } - std::pair<bool, size_t> do_rehash - = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + rehash_policy(const RP& pol) + { + m_rehash_policy = pol; + size_type n_bkt = pol.bkt_for_elements(m_element_count); + if (n_bkt > m_bucket_count) + m_rehash (n_bkt); + } - // Allocate the new node before doing the rehash so that we don't - // do a rehash if the allocation throws. - node* new_node = m_allocate_node (v); + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::iterator + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + find(const key_type& k) + { + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index(k, code, this->bucket_count()); + node* p = find_node (m_buckets[n], k, code); + return p ? iterator(p, m_buckets + n) : this->end(); + } + + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::const_iterator + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + find(const key_type& k) const + { + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index(k, code, this->bucket_count()); + node* p = find_node (m_buckets[n], k, code); + return p ? const_iterator(p, m_buckets + n) : this->end(); + } + + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::size_type + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + count(const key_type& k) const + { + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index (k, code, this->bucket_count()); + size_t result = 0; + for (node* p = m_buckets[n]; p ; p = p->m_next) + if (this->compare (k, code, p)) + ++result; + return result; + } - try { - if (do_rehash.first) { - n = this->bucket_index (k, code, do_rehash.second); - m_rehash(do_rehash.second); + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + std::pair<typename hashtable<K, V, A, Ex, Eq, H1, + H2, H, RP, c, m, u>::iterator, + typename hashtable<K, V, A, Ex, Eq, H1, + H2, H, RP, c, m, u>::iterator> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + equal_range(const key_type& k) + { + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index(k, code, this->bucket_count()); + node** head = m_buckets + n; + node* p = find_node (*head, k, code); + + if (p) + { + node* p1 = p->m_next; + for (; p1 ; p1 = p1->m_next) + if (!this->compare (k, code, p1)) + break; + + iterator first(p, head); + iterator last(p1, head); + if (!p1) + last.m_incr_bucket(); + return std::make_pair(first, last); + } + else + return std::make_pair(this->end(), this->end()); } - new_node->m_next = m_buckets[n]; - m_buckets[n] = new_node; - ++m_element_count; - return std::make_pair(iterator (new_node, m_buckets + n), true); - } - catch (...) { - m_deallocate_node (new_node); - throw; - } -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + std::pair<typename hashtable<K, V, A, Ex, Eq, H1, + H2, H, RP, c, m, u>::const_iterator, + typename hashtable<K, V, A, Ex, Eq, H1, + H2, H, RP, c, m, u>::const_iterator> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + equal_range(const key_type& k) const + { + typename hashtable::hash_code_t code = this->m_hash_code (k); + std::size_t n = this->bucket_index(k, code, this->bucket_count()); + node** head = m_buckets + n; + node* p = find_node (*head, k, code); + + if (p) + { + node* p1 = p->m_next; + for (; p1 ; p1 = p1->m_next) + if (!this->compare (k, code, p1)) + break; + + const_iterator first(p, head); + const_iterator last(p1, head); + if (!p1) + last.m_incr_bucket(); + return std::make_pair(first, last); + } + else + return std::make_pair(this->end(), this->end()); + } -// Insert v unconditionally. -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::insert (const value_type& v, std::tr1::false_type) -{ - std::pair<bool, std::size_t> do_rehash - = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); - if (do_rehash.first) - m_rehash(do_rehash.second); - - const key_type& k = this->m_extract(v); - typename hashtable::hash_code_t code = this->m_hash_code (k); - size_type n = this->bucket_index (k, code, m_bucket_count); - - node* new_node = m_allocate_node (v); - node* prev = find_node (m_buckets[n], k, code); - if (prev) { - new_node->m_next = prev->m_next; - prev->m_next = new_node; - } - else { - new_node->m_next = m_buckets[n]; - m_buckets[n] = new_node; - } + // Find the node whose key compares equal to k, beginning the search + // at p (usually the head of a bucket). Return nil if no node is found. + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::node* + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + find_node(node* p, const key_type& k, typename hashtable::hash_code_t code) + { + for ( ; p ; p = p->m_next) + if (this->compare (k, code, p)) + return p; + return false; + } - ++m_element_count; - return iterator (new_node, m_buckets + n); -} + // Insert v if no element with its key is already present. + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + std::pair<typename hashtable<K, V, A, Ex, Eq, H1, + H2, H, RP, c, m, u>::iterator, bool> + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + insert(const value_type& v, std::tr1::true_type) + { + const key_type& k = this->m_extract(v); + typename hashtable::hash_code_t code = this->m_hash_code (k); + size_type n = this->bucket_index(k, code, m_bucket_count); + + if (node* p = find_node(m_buckets[n], k, code)) + return std::make_pair(iterator(p, m_buckets + n), false); + + std::pair<bool, size_t> do_rehash + = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); + + // Allocate the new node before doing the rehash so that we don't + // do a rehash if the allocation throws. + node* new_node = m_allocate_node (v); + + try + { + if (do_rehash.first) + { + n = this->bucket_index(k, code, do_rehash.second); + m_rehash(do_rehash.second); + } + + new_node->m_next = m_buckets[n]; + m_buckets[n] = new_node; + ++m_element_count; + return std::make_pair(iterator(new_node, m_buckets + n), true); + } + catch (...) + { + m_deallocate_node (new_node); + throw; + } + } + + // Insert v unconditionally. + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::iterator + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + insert(const value_type& v, std::tr1::false_type) + { + std::pair<bool, std::size_t> do_rehash + = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1); + if (do_rehash.first) + m_rehash(do_rehash.second); + + const key_type& k = this->m_extract(v); + typename hashtable::hash_code_t code = this->m_hash_code (k); + size_type n = this->bucket_index(k, code, m_bucket_count); + + node* new_node = m_allocate_node (v); + node* prev = find_node(m_buckets[n], k, code); + if (prev) + { + new_node->m_next = prev->m_next; + prev->m_next = new_node; + } + else + { + new_node->m_next = m_buckets[n]; + m_buckets[n] = new_node; + } + + ++m_element_count; + return iterator(new_node, m_buckets + n); + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -template <typename InIter> -void -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::insert(InIter first, InIter last) -{ - size_type n_elt = Internal::distance_fw (first, last); - std::pair<bool, std::size_t> do_rehash - = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt); - if (do_rehash.first) - m_rehash(do_rehash.second); - - for (; first != last; ++first) - this->insert (*first); -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + template<typename InIter> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + insert(InIter first, InIter last) + { + size_type n_elt = Internal::distance_fw (first, last); + std::pair<bool, std::size_t> do_rehash + = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt); + if (do_rehash.first) + m_rehash(do_rehash.second); + + for (; first != last; ++first) + this->insert (*first); + } -// XXX We're following the TR in giving this a return type of void, -// but that ought to change. The return type should be const_iterator, -// and it should return the iterator following the one we've erased. -// That would simplify range erase. -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase (const_iterator i) -{ - node* p = i.m_cur_node; - node* cur = *i.m_cur_bucket; - if (cur == p) - *i.m_cur_bucket = cur->m_next; - else { - node* next = cur->m_next; - while (next != p) { - cur = next; - next = cur->m_next; + // XXX We're following the TR in giving this a return type of void, + // but that ought to change. The return type should be const_iterator, + // and it should return the iterator following the one we've erased. + // That would simplify range erase. + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + erase(const_iterator i) + { + node* p = i.m_cur_node; + node* cur = *i.m_cur_bucket; + if (cur == p) + *i.m_cur_bucket = cur->m_next; + else + { + node* next = cur->m_next; + while (next != p) + { + cur = next; + next = cur->m_next; + } + cur->m_next = next->m_next; + } + + m_deallocate_node (p); + --m_element_count; } - cur->m_next = next->m_next; - } - - m_deallocate_node (p); - --m_element_count; -} -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase(const key_type& k) -{ - typename hashtable::hash_code_t code = this->m_hash_code (k); - size_type n = this->bucket_index (k, code, m_bucket_count); - - node** slot = m_buckets + n; - while (*slot && ! this->compare (k, code, *slot)) - slot = &((*slot)->m_next); - - while (*slot && this->compare (k, code, *slot)) { - node* n = *slot; - *slot = n->m_next; - m_deallocate_node (n); - --m_element_count; - } -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>::size_type + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + erase(const key_type& k) + { + typename hashtable::hash_code_t code = this->m_hash_code (k); + size_type n = this->bucket_index(k, code, m_bucket_count); + + node** slot = m_buckets + n; + while (*slot && ! this->compare (k, code, *slot)) + slot = &((*slot)->m_next); + + while (*slot && this->compare (k, code, *slot)) + { + node* n = *slot; + *slot = n->m_next; + m_deallocate_node (n); + --m_element_count; + } + } -// ??? This could be optimized by taking advantage of the bucket -// structure, but it's not clear that it's worth doing. It probably -// wouldn't even be an optimization unless the load factor is large. -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u> -::erase(const_iterator first, const_iterator last) -{ - while (first != last) { - const_iterator next = first; - ++next; - this->erase(first); - first = next; - } -} + // ??? This could be optimized by taking advantage of the bucket + // structure, but it's not clear that it's worth doing. It probably + // wouldn't even be an optimization unless the load factor is large. + template <typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + erase(const_iterator first, const_iterator last) + { + while (first != last) + { + const_iterator next = first; + ++next; + this->erase(first); + first = next; + } + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::clear() -{ - m_deallocate_nodes (m_buckets, m_bucket_count); - m_element_count = 0; -} + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + clear() + { + m_deallocate_nodes(m_buckets, m_bucket_count); + m_element_count = 0; + } -template <typename K, typename V, - typename A, typename Ex, typename Eq, - typename H1, typename H2, typename H, typename RP, - bool c, bool m, bool u> -void -hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_rehash (size_type N) -{ - node** new_array = m_allocate_buckets (N); - try { - for (size_type i = 0; i < m_bucket_count; ++i) - while (node* p = m_buckets[i]) { - size_type new_index = this->bucket_index (p, N); - m_buckets[i] = p->m_next; - p->m_next = new_array[new_index]; - new_array[new_index] = p; - } - m_deallocate_buckets (m_buckets, m_bucket_count); - m_bucket_count = N; - m_buckets = new_array; - } - catch (...) { - // A failure here means that a hash function threw an exception. - // We can't restore the previous state without calling the hash - // function again, so the only sensible recovery is to delete - // everything. - m_deallocate_nodes (new_array, N); - m_deallocate_buckets (new_array, N); - m_deallocate_nodes (m_buckets, m_bucket_count); - m_element_count = 0; - throw; - } + template<typename K, typename V, + typename A, typename Ex, typename Eq, + typename H1, typename H2, typename H, typename RP, + bool c, bool m, bool u> + void + hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, m, u>:: + m_rehash(size_type N) + { + node** new_array = m_allocate_buckets (N); + try + { + for (size_type i = 0; i < m_bucket_count; ++i) + while (node* p = m_buckets[i]) + { + size_type new_index = this->bucket_index (p, N); + m_buckets[i] = p->m_next; + p->m_next = new_array[new_index]; + new_array[new_index] = p; + } + m_deallocate_buckets(m_buckets, m_bucket_count); + m_bucket_count = N; + m_buckets = new_array; + } + catch (...) + { + // A failure here means that a hash function threw an exception. + // We can't restore the previous state without calling the hash + // function again, so the only sensible recovery is to delete + // everything. + m_deallocate_nodes(new_array, N); + m_deallocate_buckets(new_array, N); + m_deallocate_nodes(m_buckets, m_bucket_count); + m_element_count = 0; + throw; + } + } + } - -} } // Namespace std::tr1 +} // Namespace std::tr1 #endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */ diff --git a/libstdc++-v3/include/tr1/unordered_map b/libstdc++-v3/include/tr1/unordered_map index e35683d36aa..4750c2aaf90 100644 --- a/libstdc++-v3/include/tr1/unordered_map +++ b/libstdc++-v3/include/tr1/unordered_map @@ -40,127 +40,131 @@ #include <utility> #include <memory> -namespace std { namespace tr1 { - -// XXX When we get typedef templates these class definitions will be unnecessary. - -template <class Key, class T, - class Hash = hash<Key>, - class Pred = std::equal_to<Key>, - class Alloc = std::allocator<std::pair<const Key, T> >, - bool cache_hash_code = false> -class unordered_map - : public hashtable <Key, std::pair<const Key, T>, - Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, true, true> +namespace std { - typedef hashtable <Key, std::pair<const Key, T>, - Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, true, true> - Base; - -public: - typedef typename Base::size_type size_type; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; - - explicit unordered_map(size_type n = 10, +namespace tr1 +{ + // XXX When we get typedef templates these class definitions + // will be unnecessary. + + template<class Key, class T, + class Hash = hash<Key>, + class Pred = std::equal_to<Key>, + class Alloc = std::allocator<std::pair<const Key, T> >, + bool cache_hash_code = false> + class unordered_map + : public hashtable <Key, std::pair<const Key, T>, + Alloc, + Internal::extract1st<std::pair<const Key, T> >, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, true> + { + typedef hashtable <Key, std::pair<const Key, T>, + Alloc, + Internal::extract1st<std::pair<const Key, T> >, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, true> + Base; + + public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit + unordered_map(size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base(n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), + eql, Internal::extract1st<std::pair<const Key, T> >(), a) + { } + + template<typename InputIterator> + unordered_map(InputIterator f, InputIterator l, + size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), + eql, Internal::extract1st<std::pair<const Key, T> >(), a) + { } + }; + + template<class Key, class T, + class Hash = hash<Key>, + class Pred = std::equal_to<Key>, + class Alloc = std::allocator<std::pair<const Key, T> >, + bool cache_hash_code = false> + class unordered_multimap + : public hashtable <Key, std::pair<const Key, T>, + Alloc, + Internal::extract1st<std::pair<const Key, T> >, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, false> + { + typedef hashtable <Key, std::pair<const Key, T>, + Alloc, + Internal::extract1st<std::pair<const Key, T> >, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, true, false> + Base; + + public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit + unordered_multimap(size_type n = 10, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), - a) - { } - - template <typename InputIterator> - unordered_map(InputIterator f, InputIterator l, - size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (f, l, - n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), - a) - { } -}; - -template <class Key, class T, - class Hash = hash<Key>, - class Pred = std::equal_to<Key>, - class Alloc = std::allocator<std::pair<const Key, T> >, - bool cache_hash_code = false> -class unordered_multimap - : public hashtable <Key, std::pair<const Key, T>, - Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, true, false> -{ - typedef hashtable <Key, std::pair<const Key, T>, - Alloc, - Internal::extract1st<std::pair<const Key, T> >, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, true, false> - Base; - -public: - typedef typename Base::size_type size_type; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; - - explicit unordered_multimap(size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), - a) - { } - - - template <typename InputIterator> - unordered_multimap(InputIterator f, InputIterator l, - typename Base::size_type n = 0, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (f, l, - n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::extract1st<std::pair<const Key, T> >(), - a) - { } -}; - -template <class Key, class T, class Hash, class Pred, class Alloc, bool cache_hash_code> -inline void swap (unordered_map<Key, T, Hash, Pred, Alloc, cache_hash_code>& x, - unordered_map<Key, T, Hash, Pred, Alloc, cache_hash_code>& y) -{ - x.swap(y); -} + : Base (n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), + eql, Internal::extract1st<std::pair<const Key, T> >(), a) + { } + + + template<typename InputIterator> + unordered_multimap(InputIterator f, InputIterator l, + typename Base::size_type n = 0, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), + eql, Internal::extract1st<std::pair<const Key, T> >(), a) + { } + }; + + template<class Key, class T, class Hash, class Pred, class Alloc, + bool cache_hash_code> + inline void + swap(unordered_map<Key, T, Hash, Pred, Alloc, cache_hash_code>& x, + unordered_map<Key, T, Hash, Pred, Alloc, cache_hash_code>& y) + { x.swap(y); } + + template<class Key, class T, class Hash, class Pred, class Alloc, + bool cache_hash_code> + inline void + swap(unordered_multimap<Key, T, Hash, Pred, Alloc, cache_hash_code>& x, + unordered_multimap<Key, T, Hash, Pred, Alloc, cache_hash_code>& y) + { x.swap(y); } -template <class Key, class T, class Hash, class Pred, class Alloc, bool cache_hash_code> -inline void swap (unordered_multimap<Key, T, Hash, Pred, Alloc, cache_hash_code>& x, - unordered_multimap<Key, T, Hash, Pred, Alloc, cache_hash_code>& y) -{ - x.swap(y); } - -} } +} #endif /* GNU_LIBSTDCXX_TR1_UNORDERED_MAP_ */ diff --git a/libstdc++-v3/include/tr1/unordered_set b/libstdc++-v3/include/tr1/unordered_set index e0f75f05c13..ecf8e7a968a 100644 --- a/libstdc++-v3/include/tr1/unordered_set +++ b/libstdc++-v3/include/tr1/unordered_set @@ -38,123 +38,128 @@ #include <tr1/functional> #include <memory> -namespace std { namespace tr1 { - -// XXX When we get typedef templates these class definitions will be unnecessary. - -template <class Value, - class Hash = hash<Value>, - class Pred = std::equal_to<Value>, - class Alloc = std::allocator<Value>, - bool cache_hash_code = false> -class unordered_set - : public hashtable <Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, false, true> +namespace std +{ +namespace tr1 { - typedef hashtable <Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, false, true> - Base; - -public: - typedef typename Base::size_type size_type; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; - - explicit unordered_set(size_type n = 10, + + // XXX When we get typedef templates these class definitions + // will be unnecessary. + + template<class Value, + class Hash = hash<Value>, + class Pred = std::equal_to<Value>, + class Alloc = std::allocator<Value>, + bool cache_hash_code = false> + class unordered_set + : public hashtable<Value, Value, Alloc, + Internal::identity<Value>, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, true> + { + typedef hashtable<Value, Value, Alloc, + Internal::identity<Value>, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, true> + Base; + + public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit + unordered_set(size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), + eql, Internal::identity<Value>(), a) + { } + + template<typename InputIterator> + unordered_set(InputIterator f, InputIterator l, + size_type n = 10, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), + eql, Internal::identity<Value>(), a) + { } + }; + + template<class Value, + class Hash = hash<Value>, + class Pred = std::equal_to<Value>, + class Alloc = std::allocator<Value>, + bool cache_hash_code = false> + class unordered_multiset + : public hashtable <Value, Value, Alloc, + Internal::identity<Value>, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, false> + { + typedef hashtable<Value, Value, Alloc, + Internal::identity<Value>, Pred, + Hash, Internal::mod_range_hashing, + Internal::default_ranged_hash, + Internal::prime_rehash_policy, + cache_hash_code, false, false> + Base; + + public: + typedef typename Base::size_type size_type; + typedef typename Base::hasher hasher; + typedef typename Base::key_equal key_equal; + typedef typename Base::allocator_type allocator_type; + + explicit + unordered_multiset(size_type n = 10, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& a = allocator_type()) - : Base (n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::identity<Value>(), - a) - { } - - template <typename InputIterator> - unordered_set(InputIterator f, InputIterator l, - size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (f, l, - n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::identity<Value>(), - a) - { } -}; - -template <class Value, - class Hash = hash<Value>, - class Pred = std::equal_to<Value>, - class Alloc = std::allocator<Value>, - bool cache_hash_code = false> -class unordered_multiset - : public hashtable <Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, false, false> -{ - typedef hashtable <Value, Value, Alloc, - Internal::identity<Value>, Pred, - Hash, Internal::mod_range_hashing, Internal::default_ranged_hash, - Internal::prime_rehash_policy, - cache_hash_code, false, false> - Base; - -public: - typedef typename Base::size_type size_type; - typedef typename Base::hasher hasher; - typedef typename Base::key_equal key_equal; - typedef typename Base::allocator_type allocator_type; - - explicit unordered_multiset(size_type n = 10, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::identity<Value>(), - a) - { } - - - template <typename InputIterator> - unordered_multiset(InputIterator f, InputIterator l, - typename Base::size_type n = 0, - const hasher& hf = hasher(), - const key_equal& eql = key_equal(), - const allocator_type& a = allocator_type()) - : Base (f, l, - n, - hf, Internal::mod_range_hashing(), Internal::default_ranged_hash(), - eql, Internal::identity<Value>(), - a) - { } -}; - -template <class Value, class Hash, class Pred, class Alloc, bool cache_hash_code> -inline void swap (unordered_set<Value, Hash, Pred, Alloc, cache_hash_code>& x, - unordered_set<Value, Hash, Pred, Alloc, cache_hash_code>& y) -{ - x.swap(y); -} + : Base (n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), + eql, Internal::identity<Value>(), a) + { } + + + template<typename InputIterator> + unordered_multiset(InputIterator f, InputIterator l, + typename Base::size_type n = 0, + const hasher& hf = hasher(), + const key_equal& eql = key_equal(), + const allocator_type& a = allocator_type()) + : Base (f, l, n, hf, Internal::mod_range_hashing(), + Internal::default_ranged_hash(), eql, + Internal::identity<Value>(), a) + { } + }; + + template<class Value, class Hash, class Pred, class Alloc, + bool cache_hash_code> + inline void + swap (unordered_set<Value, Hash, Pred, Alloc, cache_hash_code>& x, + unordered_set<Value, Hash, Pred, Alloc, cache_hash_code>& y) + { x.swap(y); } + + template<class Value, class Hash, class Pred, class Alloc, + bool cache_hash_code> + inline void + swap(unordered_multiset<Value, Hash, Pred, Alloc, cache_hash_code>& x, + unordered_multiset<Value, Hash, Pred, Alloc, cache_hash_code>& y) + { x.swap(y); } -template <class Value, class Hash, class Pred, class Alloc, bool cache_hash_code> -inline void swap (unordered_multiset<Value, Hash, Pred, Alloc, cache_hash_code>& x, - unordered_multiset<Value, Hash, Pred, Alloc, cache_hash_code>& y) -{ - x.swap(y); } - -} } +} #endif /* GNU_LIBSTDCXX_TR1_UNORDERED_SET_ */ |