opy()) { } __rc_string_base(const _Alloc& __a); __rc_string_base(const __rc_string_base& __rcs); #ifdef __GXX_EXPERIMENTAL_CXX0X__ __rc_string_base(__rc_string_base&& __rcs) : _M_dataplus(__rcs._M_get_allocator(), __rcs._M_data()) { __rcs._M_data(_S_empty_rep._M_refcopy()); } #endif __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a); template __rc_string_base(_InputIterator __beg, _InputIterator __end, const _Alloc& __a); ~__rc_string_base() { _M_dispose(); } allocator_type& _M_get_allocator() { return _M_dataplus; } const allocator_type& _M_get_allocator() const { return _M_dataplus; } void _M_swap(__rc_string_base& __rcs); void _M_assign(const __rc_string_base& __rcs); void _M_reserve(size_type __res); void _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, size_type __len2); void _M_erase(size_type __pos, size_type __n); void _M_clear() { _M_erase(size_type(0), _M_length()); } bool _M_compare(const __rc_string_base&) const { return false; } }; template typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep_empty __rc_string_base<_CharT, _Traits, _Alloc>::_S_empty_rep; template typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep* __rc_string_base<_CharT, _Traits, _Alloc>::_Rep:: _S_create(size_type __capacity, size_type __old_capacity, const _Alloc& __alloc) { // _GLIBCXX_RESOLVE_LIB_DEFECTS // 83. String::npos vs. string::max_size() if (__capacity > size_type(_S_max_size)) std::__throw_length_error(__N("__rc_string_base::_Rep::_S_create")); // The standard places no restriction on allocating more memory // than is strictly needed within this layer at C8D8E8F8G8H8I8J8K8L8M8N8the moment or as // requested by an explicit application call to reserve(). // Many malloc implementations perform quite poorly when an // application attempts to allocate memory in a stepwise fashion // growing each allocation size by only 1 char. Additionally, // it makes little sense to allocate less linear memory than the // natural blocking size of the malloc implementation. // Unfortunately, we would need a somewhat low-level calculation // with tuned parameters to get this perfect for any particular // malloc implementation. Fortunately, generalizations about // common features seen among implementations seems to suffice. // __pagesize need not match the actual VM page size for good // results in practice, thus we pick a common value on the low // side. __malloc_header_size is an estimate of the amount of // overhead per memory allocation (in practice seen N * sizeof // (void*) where N is 0, 2 or 4). According to folklore, // picking this value on the high side is better than // low-balling it (especially when this algorithm is used with // malloc implementations that allocate memory blocks rounded up // to a size which is a power of 2). const size_type __pagesize = 4096; const size_type __malloc_header_size = 4 * sizeof(void*); // The below implements an exponential growth policy, necessary to // meet amortized linear time requirements of the library: see // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) { __capacity = 2 * __old_capacity; // Never allocate a string bigger than _S_max_size. if (__capacity > size_type(_S_max_size)) __capacity = size_type(_S_max_size); } // NB: Need an array of char_type[__capacity], plus a terminating // null char_type() element, plus enough for the _Rep data structure, // plus sizeof(_Rep) - 1 to upper round to a size multiple of // sizeof(_Rep). // Whew. Seemingly so needy, yet so elemental. size_type __size = ((__capacity + 1) * sizeof(_CharT) + 2 * sizeof(_Rep) - 1); const size_type __adj_size = __size + __malloc_header_size; if (__adj_size > __pagesize && __capacity > __old_capacity) { const size_type __extra = __pagesize - __adj_size % __pagesize; __capacity += __extra / sizeof(_CharT); if (__capacity > size_type(_S_max_size)) __capacity = size_type(_S_max_size); __size = (__capacity + 1) * sizeof(_CharT) + 2 * sizeof(_Rep) - 1; } // NB: Might throw, but no worries about a leak, mate: _Rep() // does not throw. _Rep* __place = _Rep_alloc_type(__alloc).allocate(__size / sizeof(_Rep)); _Rep* __p = new (__place) _Rep; __p->_M_info._M_capacity = __capacity; return __p; } template void __rc_string_base<_CharT, _Traits, _Alloc>::_Rep:: _M_destroy(const _Alloc& __a) throw () { const size_type __size = ((_M_info._M_capacity + 1) * sizeof(_CharT) + 2 * sizeof(_Rep) - 1); _Rep_alloc_type(__a).deallocate(this, __size / sizeof(_Rep)); } template _CharT* __rc_string_base<_CharT, _Traits, _Alloc>::_Rep:: _M_clone(const _Alloc& __alloc, size_type __res) { // Requested capacity of the clone. const size_type __requested_cap = _M_info._M_length + __res; _Rep* __r = _Rep::_S_create(__requested_cap, _M_info._M_capacity, __alloc); if (_M_info._M_length) _S_copy(__r->_M_refdata(), _M_refdata(), _M_info._M_length); __r->_M_set_length(_M_info._M_length); return __r->_M_refdata(); } template __rc_string_base<_CharT, _Traits, _Alloc>:: __rc_string_base(const _Alloc& __a) : _M_dataplus(__a, _S_construct(size_type(), _CharT(), __a)) { } template __rc_string_base<_CharT, _Traits, _Alloc>:: __rc_string_base(const __rc_string_base& __rcs) : _M_dataplus(__rcs._M_get_allocator(), __rcs._M_grab(__rcs._M_get_allocator())) { } template __rc_string_base<_CharT, _Traits, _Alloc>:: __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a) : _M_dataplus(__a, _S_construct(__n, __c, __a)) { } template template __rc_string_base<_CharT, _Traits, _Alloc>:: __rc_string_base(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) : _M_dataplus(__a, _S_construct(__beg, __end, __a)) { } template void __rc_string_base<_CharT, _Traits, _Alloc>:: _M_leak_hard() { if (_M_is_shared()) _M_erase(0, 0); _M_set_leaked(); } // NB: This is the special case for Input Iterators, used in // istreambuf_iterators, etc. // Input Iterators have a cost structure very different from // pointers, calling for a different coding style. template template _CharT* __rc_string_base<_CharT, _Traits, _Alloc>:: _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, std::input_iterator_tag) { if (__beg == __end && __a == _Alloc()) return _S_empty_rep._M_refcopy(); // Avoid reallocation for common case. _CharT __buf[128]; size_type __len = 0; while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) { __buf[__len++] = *__beg; ++__beg; } _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); _S_copy(__r->_M_refdata(), __buf, __len); try { while (__beg != __end) { if (__len == __r->_M_info._M_capacity) { // Allocate more space. _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); _S_copy(__another->_M_refdata(), __r->_M_refdata(), __len); __r->_M_destroy(__a); __r = __another; } __r->_M_refdata()[__len++] = *__beg; ++__beg; } } catch(...) { __r->_M_destroy(__a); __throw_exception_again; } __r->_M_set_length(__len); return __r->_M_refdata(); } template template _CharT* __rc_string_base<_CharT, _Traits, _Alloc>:: _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, std::forward_iterator_tag) { if (__beg == __end && __a == _Alloc()) return _S_empty_rep._M_refcopy(); // NB: Not required, but considered best practice. if (__builtin_expect(__is_null_pointer(__beg) && __beg != __end, 0)) std::__throw_logic_error(__N("__rc_string_base::" "_S_construct NULL not valid")); const size_type __dnew = static_cast(std::distance(__beg, __end)); // Check for out_of_range and length_error exceptions. _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); try { _S_copy_chars(__r->_M_refdata(), __beg, __end); } catch(...) { __r->_M_destroy(__a); __throw_exception_again; } __r->_M_set_length(__dnew); return __r->_M_refdata(); } template _CharT* __rc_string_base<_CharT, _Traits, _Alloc>:: _S_construct(size_type __n, _CharT __c, const _Alloc& __a) { if (__n == 0 && __a == _Alloc()) return _S_empty_rep._M_refcopy(); // Check for out_of_range and length_error exceptions. _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); if (__n) _S_assign(__r->_M_refdata(), __n, __c); __r->_M_set_length(__n); return __r->_M_refdata(); } template void __rc_string_base<_CharT, _Traits, _Alloc>:: _M_swap(__rc_string_base& __rcs) { if (_M_is_leaked()) _M_set_sharable(); if (__rcs._M_is_leaked()) __rcs._M_set_sharable(); _CharT* __tmp = _M_data(); _M_data(__rcs._M_data()); __rcs._M_data(__tmp); // _GLIBCXX_RESOLVE_LIB_DEFECTS // 431. Swapping containers with unequal allocators. std::__alloc_swap::_S_do_it(_M_get_allocator(), __rcs._M_get_allocator()); } template void __rc_string_base<_CharT, _Traits, _Alloc>:: _M_assign(const __rc_string_base& __rcs) { if (_M_rep() != __rcs._M_rep()) { _CharT* __tmp = __rcs._M_grab(_M_get_allocator()); _M_dispose(); _M_data(__tmp); } } template void __rc_string_base<_CharT, _Traits, _Alloc>:: _M_reserve(size_type __res) { // Make sure we don't shrink below the current size. if (__res < _M_length()) __res = _M_length(); if (__res != _M_capacity() || _M_is_shared()) { _CharT* __tmp = _M_rep()->_M_clone(_M_get_allocator(), __res - _M_length()); _M_dispose(); _M_data(__tmp); } } template void __rc_string_base<_CharT, _Traits, _Alloc>:: _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, size_type __len2) { const size_type __how_much = _M_length() - __pos - __len1; _Rep* __r = _Rep::_S_create(_M_length() + __len2 - __len1, _M_capacity(), _M_get_allocator()); if (__pos) _S_copy(__r->_M_refdata(), _M_data(), __pos); if (__s && __len2) _S_copy(__r->_M_refdata() + __pos, __s, __len2); if (__how_much) _S_copy(__r->_M_refdata() + __pos + __len2, _M_data() + __pos + __len1, __how_much); _M_dispose(); _M_data(__r->_M_refdata()); } template void __rc_string_base<_CharT, _Traits, _Alloc>:: _M_erase(size_type __pos, size_type __n) { const size_type __new_size = _M_length() - __n; const size_type __how_much = _M_length() - __pos - __n; if (_M_is_shared()) { // Must reallocate. _Rep* __r = _Rep::_S_create(__new_size, _M_capacity(), _M_get_allocator()); if (__pos) _S_copy(__r->_M_refdata(), _M_data(), __pos); if (__how_much) _S_copy(__r->_M_refdata() + __pos, _M_data() + __pos + __n, __how_much); _M_dispose(); _M_data(__r->_M_refdata()); } else if (__how_much && __n) { // Work in-place. _S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much); } _M_rep()->_M_set_length(__new_size); } template<> inline bool __rc_string_base, std::allocator >:: _M_compare(const __rc_string_base& __rcs) const { if (_M_rep() == __rcs._M_rep()) return true; return false; } #ifdef _GLIBCXX_USE_WCHAR_T template<> inline bool __rc_string_base, std::allocator >:: _M_compare(const __rc_string_base& __rcs) const { if (_M_rep() == __rcs._M_rep()) return true; return false; } #endif _GLIBCXX_END_NAMESPACE #endif /* _RC_STRING_BASE_H */ // Allocator that wraps operator new -*- C++ -*- // 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 // 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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. /** @file ext/new_allocator.h * This file is a GNU extension to the Standard C++ Library. */ #ifndef _NEW_ALLOCATOR_H #define _NEW_ALLOCATOR_H 1 #include #include #include _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) using std::size_t; using std::ptrdiff_t; /** * @brief An allocator that uses global new, as per [20.4]. * * This is precisely the allocator defined in the C++ Standard. * - all allocation calls operator new * - all deallocation calls operator delete */ template class new_allocator { public: typedef size_t size_type; typedef ptrdiff_t difference_type; typedef _Tp* pointer; typedef const _Tp* const_pointer; typedef _Tp& reference; typedef const _Tp& const_reference; typedef _Tp value_type; template struct rebind { typedef new_allocator<_Tp1> other; }; new_allocator() throw() { } new_allocator(const new_allocator&) throw() { } template new_allocator(const new_allocator<_Tp1>&) throw() { } ~new_allocator() throw() { } pointer address(reference __x) const { return &__x; } const_pointer address(const_reference __x) const { return &__x; } // NB: __n is permitted to be 0. The C++ standard says nothing // about what the return value is when __n == 0. pointer allocate(size_type __n, const void* = 0) { if (__builtin_expect(__n > this->max_size(), false)) std::__throw_bad_alloc(); return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp))); } // __p is not permitted to be a null pointer. void deallocate(pointer __p, size_type) { ::operator delete(__p); } size_type max_size() const throw() { return size_t(-1) / sizeof(_Tp); } // _GLIBCXX_RESOLVE_LIB_DEFECTS // 402. wrong new expression in [some_] allocator::construct void construct(pointer __p, const _Tp& __val) { ::new((void *)__p) _Tp(__val); } #ifdef __GXX_EXPERIMENTAL_CXX0X__ template void construct(pointer __p, _Args&&... __args) { ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); } #endif void destroy(pointer __p) { __p->~_Tp(); } }; template inline bool operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&) { return true; } template inline bool operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&) { return false; } _GLIBCXX_END_NAMESPACE #endif // Functional extensions -*- C++ -*- // Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 // 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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. /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /** @file ext/functional * This file is a GNU extension to the Standard C++ Library (possibly * containing extensions from the HP/SGI STL subset). */ #ifndef _EXT_FUNCTIONAL #define _EXT_FUNCTIONAL 1 #pragma GCC system_header #include #include _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) using std::size_t; using std::unary_function; using std::binary_function; using std::mem_fun1_t; using std::const_mem_fun1_t; using std::mem_fun1_ref_t; using std::const_mem_fun1_ref_t; /** The @c identity_element functions are not part of the C++ * standard; SGI provided them as an extension. Its argument is an * operation, and its return value is the identity element for that * operation. It is overloaded for addition and multiplication, * and you can overload it for your own nefarious operations. * * @addtogroup SGIextensions * @{ */ /// An \link SGIextensions SGI extension \endlink. template inline _Tp identity_element(std::plus<_Tp>) { return _Tp(0); } /// An \link SGIextensions SGI extension \endlink. template inline _Tp identity_element(std::multiplies<_Tp>) { return _Tp(1); } /** @} */ /** As an extension to the binders, SGI provided composition functors and * wrapper functions to aid in their creation. The @c unary_compose * functor is constructed from two functions/functors, @c f and @c g. * Calling @c operator() with a single argument @c x returns @c f(g(x)). * The function @c compose1 takes the two functions and constructs a * @c unary_compose variable for you. * * @c binary_compose is constructed from three functors, @c f, @c g1, * and @c g2. Its @c operator() returns @c f(g1(x),g2(x)). The function * @compose2 takes f, g1, and g2, and constructs the @c binary_compose * instance for you. For example, if @c f returns an int, then * \code * int answer = (compose2(f,g1,g2))(x); * \endcode * is equivalent to * \code * int temp1 = g1(x); * int temp2 = g2(x); * int answer = f(temp1,temp2); * \endcode * But the first form is more compact, and can be passed around as a * functor to other algorithms. * * @addtogroup SGIextensions * @{ */ /// An \link SGIextensions SGI extension \endlink. template class unary_compose : public unary_function { protected: _Operation1 _M_fn1; _Operation2 _M_fn2; public: unary_compose(const _Operation1& __x, const _Operation2& __y) : _M_fn1(__x), _M_fn2(__y) {} typename _Operation1::result_type operator()(const typename _Operation2::argument_type& __x) const { return _M_fn1(_M_fn2(__x)); } }; /// An \link SGIextensions SGI extension \endlink. template inline unary_compose<_Operation1, _Operation2> compose1(const _Operation1& __fn1, const _Operation2& __fn2) { return unary_compose<_Operation1,_Operation2>(__fn1, __fn2); } /// An \link SGIextensions SGI extension \endlink. template class binary_compose : public unary_function { protected: _Operation1 _M_fn1; _Operation2 _M_fn2; _Operation3 _M_fn3; public: binary_compose(const _Operation1& __x, const _Operation2& __y, const _Operation3& __z) : _M_fn1(__x), _M_fn2(__y), _M_fn3(__z) { } typename _Operation1::result_type operator()(const typename _Operation2::argument_type& __x) const { return _M_fn1(_M_fn2(__x), _M_fn3(__x)); } }; /// An \link SGIextensions SGI extension \endlink. template inline binary_compose<_Operation1, _Operation2, _Operation3> compose2(const _Operation1& __fn1, const _Operation2& __fn2, const _Operation3& __fn3) { return binary_compose<_Operation1, _Operation2, _Operation3> (__fn1, __fn2, __fn3); } /** @} */ /** As an extension, SGI provided a functor called @c identity. When a * functor is required but no operations are desired, this can be used as a * pass-through. Its @c operator() returns its argument unchanged. * * @addtogroup SGIextensions */ template struct identity : public std::_Identity<_Tp> {}; /** @c select1st and @c select2nd are extensions provided by SGI. Their * @c operator()s * take a @c std::pair as an argument, and return either the first member * or the second member, respectively. They can be used (especially with * the composition functors) to "strip" data from a sequence before * performing the remainder of an algorithm. * * @addtogroup SGIextensions * @{ */ /// An \link SGIextensions SGI extension \endlink. template struct select1st : public std::_Select1st<_Pair> {}; /// An \link SGIextensions SGI extension \endlink. template struct select2nd : public std::_Select2nd<_Pair> {}; /** @} */ // extension documented next template struct _Project1st : public binary_function<_Arg1, _Arg2, _Arg1> { _Arg1 operator()(const _Arg1& __x, const _Arg2&) const { return __x; } }; template struct _Project2nd : public binary_function<_Arg1, _Arg2, _Arg2> { _Arg2 operator()(const _Arg1&, const _Arg2& __y) const { return __y; } }; /** The @c operator() of the @c project1st functor takes two arbitrary * arguments and returns the first one, while @c project2nd returns the * second one. They are extensions provided by SGI. * * @addtogroup SGIextensions * @{ */ /// An \link SGIextensions SGI extension \endlink. template struct project1st : public _Project1st<_Arg1, _Arg2> {}; /// An \link SGIextensions SGI extension \endlink. template struct project2nd : public _Project2nd<_Arg1, _Arg2> {}; /** @} */ // extension documented next template struct _Constant_void_fun { typedef _Result result_type; result_type _M_val; _Constant_void_fun(const result_type& __v) : _M_val(__v) {} const result_type& operator()() const { return _M_val; } }; template struct _Constant_unary_fun { typedef _Argument argument_type; typedef _Result result_type; result_type _M_val; _Constant_unary_fun(const result_type& __v) : _M_val(__v) {} const result_type& operator()(const _Argument&) const { return _M_val; } }; template struct _Constant_binary_fun { typedef _Arg1 first_argument_type; typedef _Arg2 second_argument_type; typedef _Result result_type; _Result _M_val; _Constant_binary_fun(const _Result& __v) : _M_val(__v) {} const result_type& operator()(const _Arg1&, const _Arg2&) const { return _M_val; } }; /** These three functors are each constructed from a single arbitrary * variable/value. Later, their @c operator()s completely ignore any * arguments passed, and return the stored value. * - @c constant_void_fun's @c operator() takes no arguments * - @c constant_unary_fun's @c operator() takes one argument (ignored) * - @c constant_binary_fun's @c operator() takes two arguments (ignored) * * The helper creator functions @c constant0, @c constant1, and * @c constant2 each take a "result" argument and construct variables of * the appropriate functor type. * * @addtogroup SGIextensions * @{ */ /// An \link SGIextensions SGI extension \endlink. template struct constant_void_fun : public _Constant_void_fun<_Result> { constant_void_fun(const _Result& __v) : _Constant_void_fun<_Result>(__v) {} }; /// An \link SGIextensions SGI extension \endlink. template struct constant_unary_fun : public _Constant_unary_fun<_Result, _Argument> { constant_unary_fun(const _Result& __v) : _Constant_unary_fun<_Result, _Argument>(__v) {} }; /// An \link SGIextensions SGI extension \endlink. template struct constant_binary_fun : public _Constant_binary_fun<_Result, _Arg1, _Arg2> { constant_binary_fun(const _Result& __v) : _Constant_binary_fun<_Result, _Arg1, _Arg2>(__v) {} }; /// An \link SGIextensions SGI extension \endlink. template inline constant_void_fun<_Result> constant0(const _Result& __val) { return constant_void_fun<_Result>(__val); } /// An \link SGIextensions SGI extension \endlink. template inline constant_unary_fun<_Result, _Result> constant1(const _Result& __val) { return constant_unary_fun<_Result, _Result>(__val); } /// An \link SGIextensions SGI extension \endlink. template inline constant_binary_fun<_Result,_Result,_Result> constant2(const _Result& __val) { return constant_binary_fun<_Result, _Result, _Result>(__val); } /** @} */ /** The @c subtractive_rng class is documented on * SGIa8b8c8's site. * Note that this code assumes that @c int is 32 bits. * * @ingroup SGIextensions */ class subtractive_rng : public unary_function { private: unsigned int _M_table[55]; size_t _M_index1; size_t _M_index2; public: /// Returns a number less than the argument. unsigned int operator()(unsigned int __limit) { _M_index1 = (_M_index1 + 1) % 55; _M_index2 = (_M_index2 + 1) % 55; _M_table[_M_index1] = _M_table[_M_index1] - _M_table[_M_index2]; return _M_table[_M_index1] % __limit; } void _M_initialize(unsigned int __seed) { unsigned int __k = 1; _M_table[54] = __seed; size_t __i; for (__i = 0; __i < 54; __i++) { size_t __ii = (21 * (__i + 1) % 55) - 1; _M_table[__ii] = __k; __k = __seed - __k; __seed = _M_table[__ii]; } for (int __loop = 0; __loop < 4; __loop++) { for (__i = 0; __i < 55; __i++) _M_table[__i] = _M_table[__i] - _M_table[(1 + __i + 30) % 55]; } _M_index1 = 0; _M_index2 = 31; } /// Ctor allowing you to initialize the seed. subtractive_rng(unsigned int __seed) { _M_initialize(__seed); } /// Default ctor; initializes its state with some number you don't see. subtractive_rng() { _M_initialize(161803398u); } }; // Mem_fun adaptor helper functions mem_fun1 and mem_fun1_ref, // provided for backward compatibility, they are no longer part of // the C++ standard. template inline mem_fun1_t<_Ret, _Tp, _Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg)) { return mem_fun1_t<_Ret, _Tp, _Arg>(__f); } template inline const_mem_fun1_t<_Ret, _Tp, _Arg> mem_fun1(_Ret (_Tp::*__f)(_Arg) const) { return const_mem_fun1_t<_Ret, _Tp, _Arg>(__f); } template inline mem_fun1_ref_t<_Ret, _Tp, _Arg> mem_fun1_ref(_Ret (_Tp::*__f)(_Arg)) { return mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); } template inline const_mem_fun1_ref_t<_Ret, _Tp, _Arg> mem_fun1_ref(_Ret (_Tp::*__f)(_Arg) const) { return const_mem_fun1_ref_t<_Ret, _Tp, _Arg>(__f); } _GLIBCXX_END_NAMESPACE #endif // File descriptor layer for filebuf -*- C++ -*- // Copyright (C) 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 // 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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. /** @file ext/stdio_filebuf.h * This file is a GNU extension to the Standard C++ Library. */ #ifndef _STDIO_FILEBUF_H #define _STDIO_FILEBUF_H 1 #pragma GCC system_header #include _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) /** * @brief Provides a layer of compatibility for C/POSIX. * * This GNU extension provides extensions for working with standard C * FILE*'s and POSIX file descriptors. It must be instantiated by the * user with the type of character used in the file stream, e.g., * stdio_filebuf. */ template > class stdio_filebuf : public std::basic_filebuf<_CharT, _Traits> { public: // Types: typedef _CharT char_type; typedef _Traits traits_type; typedef typename traits_type::int_type int_type; typedef typename traits_type::pos_type pos_type; typedef typename traits_type::off_type off_type; typedef std::size_t size_t; public: /** * deferred initialization */ stdio_filebuf() : std::basic_filebuf<_CharT, _Traits>() {} /** * @param fd An open file descriptor. * @param mode Same meaning as in a standard filebuf. * @param size Optimal or preferred size of internal buffer, in chars. * * This constructor associates a file stream buffer with an open * POSIX file descriptor. The file descriptor will be automatically * closed when the stdio_filebuf is closed/destroyed. */ stdio_filebuf(int __fd, std::ios_base::openmode __mode, size_t __size = static_cast(BUFSIZ)); /** * @param f An open @c FILE*. * @param mode Same meaning as in a standard filebuf. * @param size Optimal or preferred size of internal buffer, in chars. * Defaults to system's @c BUFSIZ. * * This constructor associates a file stream buffer with an open * C @c FILE*. The @c FILE* will not be automatically closed when the * stdio_filebuf is closed/destroyed. */ stdio_filebuf(std::__c_file* __f, std::ios_base::openmode __mode, size_t __size = static_cast(BUFSIZ)); /** * Closes the external data stream if the file descriptor constructor * was used. */ virtual ~stdio_filebuf(); /** * @return The underlying file descriptor. * * Once associated with an external data stream, this function can be * used to access the underlying POSIX file descriptor. Note that * there is no way for the library to track what you do with the * descriptor, so be careful. */ int fd() { return this->_M_file.fd(); } /** * @return The underlying FILE*. * * This function can be used to access the underlying "C" file pointer. * Note that there is no way for the library to track what you do * with the file, so be careful. */ std::__c_file* file() { return this->_M_file.file(); } }; template stdio_filebuf<_CharT, _Traits>::~stdio_filebuf() { } template stdio_filebuf<_CharT, _Traits>:: stdio_filebuf(int __fd, std::ios_base::openmode __mode, size_t __size) { this->_M_file.sys_open(__fd, __mode); if (this->is_open()) { this->_M_mode = __mode; this->_M_buf_size = __size; this->_M_allocate_internal_buffer(); this->_M_reading = false; this->_M_writing = false; this->_M_set_buffer(-1); } } template stdio_filebuf<_CharT, _Traits>:: stdio_filebuf(std::__c_file* __f, std::ios_base::openmode __mode, size_t __size) { this->_M_file.sys_open(__f, __mode); if (this->is_open()) { this->_M_mode = __mode; this->_M_buf_size = __size; this->_M_allocate_internal_buffer(); this->_M_reading = false; this->_M_writing = false; this->_M_set_buffer(-1); } } _GLIBCXX_END_NAMESPACE #endif // -*- C++ -*- forwarding header. // 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 // 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, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, 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. /** @file ciso646 * This is a Standard C++ Library file. You should @c #include this file * in your programs, rather than any of the "*.h" implementation files. * * This is the C++ version of the Standard C Library header @c iso646.h, * and its contents are (mostly) the same as that header, but are all * contained in the namespace @c std (except for names which are defined * as macros in C). */ // -*- C++ -*- // Copyright (C) 2007, 2008 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, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, 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. /** @file include/unordered_map * This is a Standard C++ Library header. */ #ifndef _GLIBCXX_UNORDERED_MAP #define _GLIBCXX_UNORDERED_MAP 1 #pragma GCC system_header #ifndef __GXX_EXPERIMENTAL_CXX0X__ # include #endif #if defined(_GLIBCXX_INCLUDE_AS_TR1) # error C++0x header cannot be included from TR1 header #endif #include #include #include #include #include // equal_to, _Identity, _Select1st #include #include #include #if defined(_GLIBCXX_INCLUDE_AS_CXX0X) # include #else # define _GLIBCXX_INCLUDE_AS_CXX0X #if defined(_GLIBCXX_DEBUG) || defined(_GLIBCXX_PARALLEL) # define _GLIBCXX_BEGIN_NAMESPACE_TR1 namespace _GLIBCXX_STD_D { # define _GLIBCXX_END_NAMESPACE_TR1 } # define _GLIBCXX_TR1 _GLIBCXX_STD_D #else # define _GLIBCXX_BEGIN_NAMESPACE_TR1 # define _GLIBCXX_END_NAMESPACE_TR1 # define _GLIBCXX_TR1 #endif # include # undef _GLIBCXX_TR1 # undef _GLIBCXX_END_NAMESPACE_TR1 # undef _GLIBCXX_BEGIN_NAMESPACE_TR1 # undef _GLIBCXX_INCLUDE_AS_CXX0X #endif #ifdef _GLIBCXX_DEBUG # include #endif #endif // _GLIBCXX_UNORDERED_MAP // -*- C++ -*- // Copyright (C) 2001, 2002 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, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, 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. /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /** @file include/map * This is a Standard C++ Library header. */ #ifndef _GLIBCXX_MAP #define _GLIBCXX_MAP 1 #pragma GCC system_header #include #include #include #ifdef _GLIBCXX_DEBUG # include #endif #endif /* _GLIBCXX_MAP */ // -*- C++ -*- // Copyright (C) 2007 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, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, 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. /** @file include/regex * This is a Standard C++ Library header. */ #ifndef _GLIBCXX_CXX0X_REGEX #define _GLIBCXX_CXX0X_REGEX 1 #pragma GCC system_header #ifndef __GXX_EXPERIMENTAL_CXX0X__ # include #endif #if defined(_GLIBCXX_INCLUDE_AS_TR1) # error C++0x header cannot be included from TR1 header #endif #include #include #include #include #include #include #include #include #if defined(_GLIBCXX_INCLUDE_AS_CXX0X) # include #else # define _GLIBCXX_INCLUDE_AS_CXX0X # define _GLIBCXX_BEGIN_NAMESPACE_TR1 # define _GLIBCXX_END_NAMESPACE_TR1 # define _GLIBCXX_TR1 # include # undef _GLIBCXX_TR1 # undef _GLIBCXX_END_NAMESPACE_TR1 # undef _GLIBCXX_BEGIN_NAMESPACE_TR1 # undef _GLIBCXX_INCLUDE_AS_CXX0X #endif #endif // _GLIBCXX_CXX0X_REGEX // Standard exception classes -*- C++ -*- // Copyright (C) 2001, 2002, 2005, 2007 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, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, 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. /** @file stdexcept * This is a Standard C++ Library header. */ // // ISO C++ 19.1 Exception classes // #ifndef _GLIBCXX_STDEXCEPT #define _GLIBCXX_STDEXCEPT 1 #pragma GCC system_header #include #include _GLIBCXX_BEGIN_NAMESPACE(std) /** Logic errors represent problems in the internal logic of a program; * in theory, these are preventable, and even detectable before the * program runs (e.g., violations of class invariants). * @brief One of two subclasses of exception. */ class logic_error : public exception { string _M_msg; public: /** Takes a character string describing the error. */ explicit logic_error(const string& __arg); virtual ~logic_error() throw(); /** Returns a C-style character string describing the general cause of * the current error (the same string passed to the ctor). */ virtual const char* what() const throw(); }; /** Thrown by the library, or by you, to report domain errors (domain in * the mathematical sense). */ class domain_error : public logic_error { public: explicit domain_error(const string& __arg); }; /** Thrown to report invalid arguments to functions. */ class invalid_argument : public logic_error { public: explicit invalid_argument(const string& __arg); }; /** Thrown when an object is constructed that would exceed its maximum * permitted size (e.g., a basic_string instance). */ class length_error : public logic_error { public: explicit length_error(const string& __arg); }; /** This represents an argument whose value is not within the expected * range (e.g., boundary checks in basic_string). */ class out_of_range : public logic_error { public: explicit out_of_range(const string& __arg); }; /** Runtime errors represent problems outside the scope of a program; * they cannot be easily predicted and can generally only be caught as * the program executes. * @brief One of two subclasses of exception. */ class runtime_error : public exception { string _M_msg; public: /** Takes a character string describing the error. */ explicit runtime_error(const string& __arg); virtual ~runtime_error() throw(); /** Returns a C-style character string describing the general cause of * the current error (the same string passed to the ctor). */ virtual const char* what() const throw(); }; /** Thrown to indicate range errors in internal computations. */ class range_error : public runtime_error { public: explicit range_error(const string& __arg); }; /** Thrown to indicate arithmetic overflow. */ class overflow_error : public runtime_error { public: explicit overflow_error(const string& __arg); }; /** Thrown to indicate arithmetic underflow. */ class underflow_error : public runtime_error { public: explicit underflow_error(const string& __arg); }; _GLIBCXX_END_NAMESPACE #endif /* _GLIBCXX_STDEXCEPT */ // -*- C++ -*- // Copyright (C) 2001, 2002 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, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, 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. /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /** @file include/set * This is a Standard C++ Library header. */ #ifndef _GLIBCXX_SET #define _GLIBCXX_SET 1 #pragma GCC system_header #include #include #include #ifdef _GLIBCXX_DEBUG # include #endif #endif /* _GLIBCXX_SET */ Ž . .. hashtable.h strstream‘backward_warning.h’ hash_fun.h“ auto_ptr.h”hash_set•hash_map–\ binders.h// Hashtable implementation used by containers -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 // 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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. /* * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copy