diff options
| author | (no author) <(no author)@138bc75d-0d04-0410-961f-82ee72b054a4> | 1998-09-02 12:33:39 +0000 |
|---|---|---|
| committer | (no author) <(no author)@138bc75d-0d04-0410-961f-82ee72b054a4> | 1998-09-02 12:33:39 +0000 |
| commit | ff379a7312800e8366544ae4f0ef42a408768a37 (patch) | |
| tree | 39c7dd96eee00a735a3928b1fac916c0e6cc3ad0 | |
| parent | 09c212a5211c0f93b5b4edd6875d08f9e3cc36a1 (diff) | |
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/SGI@22183 138bc75d-0d04-0410-961f-82ee72b054a4
| -rw-r--r-- | libstdc++/stl/bitset | 1064 | ||||
| -rw-r--r-- | libstdc++/stl/char_traits.h | 135 | ||||
| -rw-r--r-- | libstdc++/stl/stdexcept | 92 | ||||
| -rw-r--r-- | libstdc++/stl/stl_exception.h | 57 | ||||
| -rw-r--r-- | libstdc++/stl/stl_string_fwd.h | 51 | ||||
| -rw-r--r-- | libstdc++/stl/string | 1960 |
6 files changed, 3359 insertions, 0 deletions
diff --git a/libstdc++/stl/bitset b/libstdc++/stl/bitset new file mode 100644 index 00000000000..5660855b059 --- /dev/null +++ b/libstdc++/stl/bitset @@ -0,0 +1,1064 @@ +/* + * Copyright (c) 1998 + * 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. + */ + +#ifndef __SGI_STL_BITSET +#define __SGI_STL_BITSET + +// This implementation of bitset<> has a second template parameter, +// _WordT, which defaults to unsigned long. *YOU SHOULD NOT USE +// THIS FEATURE*. It is experimental, and it may be removed in +// future releases. + +// A bitset of size N, using words of type _WordT, will have +// N % (sizeof(_WordT) * CHAR_BIT) unused bits. (They are the high- +// order bits in the highest word.) It is a class invariant +// of class bitset<> that those unused bits are always zero. + +// Most of the actual code isn't contained in bitset<> itself, but in the +// base class _Base_bitset. The base class works with whole words, not with +// individual bits. This allows us to specialize _Base_bitset for the +// important special case where the bitset is only a single word. + +// The C++ standard does not define the precise semantics of operator[]. +// In this implementation the const version of operator[] is equivalent +// to test(), except that it does no range checking. The non-const version +// returns a reference to a bit, again without doing any range checking. + + +#include <stddef.h> // for size_t +#include <string> +#include <stdexcept> // for invalid_argument, out_of_range, overflow_error +#include <iostream.h> // for istream, ostream + +#define __BITS_PER_WORDT(__wt) (CHAR_BIT*sizeof(__wt)) +#define __BITSET_WORDS(__n,__wt) \ + ((__n) < 1 ? 1 : ((__n) + __BITS_PER_WORDT(__wt) - 1)/__BITS_PER_WORDT(__wt)) + +__STL_BEGIN_NAMESPACE + +#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) +#pragma set woff 1209 +#endif + +// structure to aid in counting bits +template<bool __dummy> +struct _Bit_count { + static unsigned char _S_bit_count[256]; +}; + +// Mapping from 8 bit unsigned integers to the index of the first one +// bit: +template<bool __dummy> +struct _First_one { + static unsigned char _S_first_one[256]; +}; + +// +// Base class: general case. +// + +template<size_t _Nw, class _WordT> +struct _Base_bitset { + _WordT _M_w[_Nw]; // 0 is the least significant word. + + _Base_bitset( void ) { _M_do_reset(); } + + _Base_bitset(unsigned long __val); + + static size_t _S_whichword( size_t __pos ) { + return __pos / __BITS_PER_WORDT(_WordT); + } + static size_t _S_whichbyte( size_t __pos ) { + return (__pos % __BITS_PER_WORDT(_WordT)) / CHAR_BIT; + } + static size_t _S_whichbit( size_t __pos ) { + return __pos % __BITS_PER_WORDT(_WordT); + } + static _WordT _S_maskbit( size_t __pos ) { + return (static_cast<_WordT>(1)) << _S_whichbit(__pos); + } + + _WordT& _M_getword(size_t __pos) { return _M_w[_S_whichword(__pos)]; } + _WordT _M_getword(size_t __pos) const { return _M_w[_S_whichword(__pos)]; } + + _WordT& _M_hiword() { return _M_w[_Nw - 1]; } + _WordT _M_hiword() const { return _M_w[_Nw - 1]; } + + void _M_do_and(const _Base_bitset<_Nw,_WordT>& __x) { + for ( size_t __i = 0; __i < _Nw; __i++ ) { + _M_w[__i] &= __x._M_w[__i]; + } + } + + void _M_do_or(const _Base_bitset<_Nw,_WordT>& __x) { + for ( size_t __i = 0; __i < _Nw; __i++ ) { + _M_w[__i] |= __x._M_w[__i]; + } + } + + void _M_do_xor(const _Base_bitset<_Nw,_WordT>& __x) { + for ( size_t __i = 0; __i < _Nw; __i++ ) { + _M_w[__i] ^= __x._M_w[__i]; + } + } + + void _M_do_left_shift(size_t __shift); + + void _M_do_right_shift(size_t __shift); + + void _M_do_flip() { + for ( size_t __i = 0; __i < _Nw; __i++ ) { + _M_w[__i] = ~_M_w[__i]; + } + } + + void _M_do_set() { + for ( size_t __i = 0; __i < _Nw; __i++ ) { + _M_w[__i] = ~static_cast<_WordT>(0); + } + } + + void _M_do_reset() { + for ( size_t __i = 0; __i < _Nw; __i++ ) { + _M_w[__i] = 0; + } + } + + bool _M_is_equal(const _Base_bitset<_Nw,_WordT>& __x) const { + for (size_t __i = 0; __i < _Nw; ++__i) { + if (_M_w[__i] != __x._M_w[__i]) + return false; + } + return true; + } + + bool _M_is_any() const { + for ( size_t __i = 0; __i < __BITSET_WORDS(_Nw,_WordT); __i++ ) { + if ( _M_w[__i] != static_cast<_WordT>(0) ) + return true; + } + return false; + } + + size_t _M_do_count() const { + size_t __result = 0; + const unsigned char* __byte_ptr = (const unsigned char*)_M_w; + const unsigned char* __end_ptr = (const unsigned char*)(_M_w+_Nw); + + while ( __byte_ptr < __end_ptr ) { + __result += _Bit_count<true>::_S_bit_count[*__byte_ptr]; + __byte_ptr++; + } + return __result; + } + + unsigned long _M_do_to_ulong() const; + + // find first "on" bit + size_t _M_do_find_first(size_t __not_found) const; + + // find the next "on" bit that follows "prev" + size_t _M_do_find_next(size_t __prev, size_t __not_found) const; +}; + +// +// Definitions of non-inline functions from _Base_bitset. +// + +template<size_t _Nw, class _WordT> +_Base_bitset<_Nw, _WordT>::_Base_bitset(unsigned long __val) +{ + _M_do_reset(); + const size_t __n = min(sizeof(unsigned long)*CHAR_BIT, + __BITS_PER_WORDT(_WordT)*_Nw); + for(size_t __i = 0; __i < __n; ++__i, __val >>= 1) + if ( __val & 0x1 ) + _M_getword(__i) |= _S_maskbit(__i); +} + +template<size_t _Nw, class _WordT> +void _Base_bitset<_Nw, _WordT>::_M_do_left_shift(size_t __shift) +{ + if (__shift != 0) { + const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT); + const size_t __offset = __shift % __BITS_PER_WORDT(_WordT); + const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset; + size_t __n = _Nw - 1; + for ( ; __n > __wshift; --__n) + _M_w[__n] = (_M_w[__n - __wshift] << __offset) | + (_M_w[__n - __wshift - 1] >> __sub_offset); + if (__n == __wshift) + _M_w[__n] = _M_w[0] << __offset; + for (size_t __n1 = 0; __n1 < __n; ++__n1) + _M_w[__n1] = static_cast<_WordT>(0); + } +} + +template<size_t _Nw, class _WordT> +void _Base_bitset<_Nw, _WordT>::_M_do_right_shift(size_t __shift) +{ + if (__shift != 0) { + const size_t __wshift = __shift / __BITS_PER_WORDT(_WordT); + const size_t __offset = __shift % __BITS_PER_WORDT(_WordT); + const size_t __sub_offset = __BITS_PER_WORDT(_WordT) - __offset; + const size_t __limit = _Nw - __wshift - 1; + size_t __n = 0; + for ( ; __n < __limit; ++__n) + _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | + (_M_w[__n + __wshift + 1] << __sub_offset); + _M_w[__limit] = _M_w[_Nw-1] >> __offset; + for (size_t __n1 = __limit + 1; __n1 < _Nw; ++__n1) + _M_w[__n1] = static_cast<_WordT>(0); + } +} + +template<size_t _Nw, class _WordT> +unsigned long _Base_bitset<_Nw, _WordT>::_M_do_to_ulong() const +{ + const overflow_error __overflow("bitset"); + + if (sizeof(_WordT) >= sizeof(unsigned long)) { + for (size_t __i = 1; __i < _Nw; ++__i) + if (_M_w[__i]) + __STL_THROW(__overflow); + + const _WordT __mask = static_cast<_WordT>(static_cast<unsigned long>(-1)); + if (_M_w[0] & ~__mask) + __STL_THROW(__overflow); + + return static_cast<unsigned long>(_M_w[0] & __mask); + } + else { // sizeof(_WordT) < sizeof(unsigned long). + const size_t __nwords = + (sizeof(unsigned long) + sizeof(_WordT) - 1) / sizeof(_WordT); + + size_t __min_nwords = __nwords; + if (_Nw > __nwords) { + for (size_t __i = __nwords; __i < _Nw; ++__i) + if (_M_w[__i]) + __STL_THROW(__overflow); + } + else + __min_nwords = _Nw; + + // If unsigned long is 8 bytes and _WordT is 6 bytes, then an unsigned + // long consists of all of one word plus 2 bytes from another word. + const size_t __part = sizeof(unsigned long) % sizeof(_WordT); + + if (__part != 0 && __nwords <= _Nw && + (_M_w[__min_nwords - 1] >> ((sizeof(_WordT) - __part) * CHAR_BIT)) != 0) + __STL_THROW(__overflow); + + unsigned long __result = 0; + for (size_t __i = 0; __i < __min_nwords; ++__i) { + __result |= static_cast<unsigned long>( + _M_w[__i]) << (__i * sizeof(_WordT) * CHAR_BIT); + } + return __result; + } +} // End _M_do_to_ulong + +template<size_t _Nw, class _WordT> +size_t _Base_bitset<_Nw, _WordT>::_M_do_find_first(size_t __not_found) const +{ + for ( size_t __i = 0; __i < _Nw; __i++ ) { + _WordT __thisword = _M_w[__i]; + if ( __thisword != static_cast<_WordT>(0) ) { + // find byte within word + for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { + unsigned char __this_byte + = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); + if ( __this_byte ) + return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + + _First_one<true>::_S_first_one[__this_byte]; + + __thisword >>= CHAR_BIT; + } + } + } + // not found, so return an indication of failure. + return __not_found; +} + +template<size_t _Nw, class _WordT> +size_t +_Base_bitset<_Nw, _WordT>::_M_do_find_next(size_t __prev, + size_t __not_found) const +{ + // make bound inclusive + ++__prev; + + // check out of bounds + if ( __prev >= _Nw * __BITS_PER_WORDT(_WordT) ) + return __not_found; + + // search first word + size_t __i = _S_whichword(__prev); + _WordT __thisword = _M_w[__i]; + + // mask off bits below bound + __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); + + if ( __thisword != static_cast<_WordT>(0) ) { + // find byte within word + // get first byte into place + __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; + for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) { + unsigned char __this_byte + = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); + if ( __this_byte ) + return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + + _First_one<true>::_S_first_one[__this_byte]; + + __thisword >>= CHAR_BIT; + } + } + + // check subsequent words + __i++; + for ( ; __i < _Nw; __i++ ) { + _WordT __thisword = _M_w[__i]; + if ( __thisword != static_cast<_WordT>(0) ) { + // find byte within word + for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { + unsigned char __this_byte + = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); + if ( __this_byte ) + return __i*__BITS_PER_WORDT(_WordT) + __j*CHAR_BIT + + _First_one<true>::_S_first_one[__this_byte]; + + __thisword >>= CHAR_BIT; + } + } + } + + // not found, so return an indication of failure. + return __not_found; +} // end _M_do_find_next + + +// ------------------------------------------------------------ + +// +// Base class: specialization for a single word. +// + +template<class _WordT> +struct _Base_bitset<1, _WordT> { + _WordT _M_w; + + _Base_bitset( void ) { _M_do_reset(); } + + _Base_bitset(unsigned long __val); + + static size_t _S_whichword( size_t __pos ) { + return __pos / __BITS_PER_WORDT(_WordT); + } + static size_t _S_whichbyte( size_t __pos ) { + return (__pos % __BITS_PER_WORDT(_WordT)) / CHAR_BIT; + } + static size_t _S_whichbit( size_t __pos ) { + return __pos % __BITS_PER_WORDT(_WordT); + } + static _WordT _S_maskbit( size_t __pos ) { + return (static_cast<_WordT>(1)) << _S_whichbit(__pos); + } + + _WordT& _M_getword(size_t) { return _M_w; } + _WordT _M_getword(size_t) const { return _M_w; } + + _WordT& _M_hiword() { return _M_w; } + _WordT _M_hiword() const { return _M_w; } + + void _M_do_and(const _Base_bitset<1,_WordT>& __x) { _M_w &= __x._M_w; } + void _M_do_or(const _Base_bitset<1,_WordT>& __x) { _M_w |= __x._M_w; } + void _M_do_xor(const _Base_bitset<1,_WordT>& __x) { _M_w ^= __x._M_w; } + void _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } + void _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } + void _M_do_flip() { _M_w = ~_M_w; } + void _M_do_set() { _M_w = ~static_cast<_WordT>(0); } + void _M_do_reset() { _M_w = 0; } + + bool _M_is_equal(const _Base_bitset<1,_WordT>& __x) const { + return _M_w == __x._M_w; + } + bool _M_is_any() const { + return _M_w != 0; + } + + size_t _M_do_count() const { + size_t __result = 0; + const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; + const unsigned char* __end_ptr = ((const unsigned char*)&_M_w)+sizeof(_M_w); + while ( __byte_ptr < __end_ptr ) { + __result += _Bit_count<true>::_S_bit_count[*__byte_ptr]; + __byte_ptr++; + } + return __result; + } + + unsigned long _M_do_to_ulong() const { + if (sizeof(_WordT) <= sizeof(unsigned long)) + return static_cast<unsigned long>(_M_w); + else { + const _WordT __mask = static_cast<_WordT>(static_cast<unsigned long>(-1)); + if (_M_w & ~__mask) + __STL_THROW(overflow_error("bitset")); + return static_cast<unsigned long>(_M_w); + } + } + + size_t _M_do_find_first(size_t __not_found) const; + + // find the next "on" bit that follows "prev" + size_t _M_do_find_next(size_t __prev, size_t __not_found) const; + +}; + +// +// Definitions of non-inline functions from the single-word version of +// _Base_bitset. +// + +template <class _WordT> +_Base_bitset<1, _WordT>::_Base_bitset(unsigned long __val) +{ + _M_do_reset(); + const size_t __n = min(sizeof(unsigned long)*CHAR_BIT, + __BITS_PER_WORDT(_WordT)*_Nw); + for(size_t __i = 0; __i < __n; ++__i, __val >>= 1) + if ( __val & 0x1 ) + _M_w |= _S_maskbit(__i); +} + +template <class _WordT> +size_t _Base_bitset<1, _WordT>::_M_do_find_first(size_t __not_found) const +{ + _WordT __thisword = _M_w; + + if ( __thisword != static_cast<_WordT>(0) ) { + // find byte within word + for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { + unsigned char __this_byte + = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); + if ( __this_byte ) + return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte]; + + __thisword >>= CHAR_BIT; + } + } + // not found, so return a value that indicates failure. + return __not_found; +} + +template <class _WordT> +size_t +_Base_bitset<1, _WordT>::_M_do_find_next(size_t __prev, + size_t __not_found ) const +{ + // make bound inclusive + ++__prev; + + // check out of bounds + if ( __prev >= __BITS_PER_WORDT(_WordT) ) + return __not_found; + + // search first (and only) word + _WordT __thisword = _M_w; + + // mask off bits below bound + __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); + + if ( __thisword != static_cast<_WordT>(0) ) { + // find byte within word + // get first byte into place + __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; + for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) { + unsigned char __this_byte + = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); + if ( __this_byte ) + return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte]; + + __thisword >>= CHAR_BIT; + } + } + + // not found, so return a value that indicates failure. + return __not_found; +} // end _M_do_find_next + +// +// One last specialization: _M_do_to_ulong() and the constructor from +// unsigned long are very simple if the bitset consists of a single +// word of type unsigned long. +// + +template<> +inline unsigned long +_Base_bitset<1, unsigned long>::_M_do_to_ulong() const { return _M_w; } + +template<> +inline _Base_bitset<1, unsigned long>::_Base_bitset(unsigned long __val) { + _M_w = __val; +} + + +// ------------------------------------------------------------ +// Helper class to zero out the unused high-order bits in the highest word. + +template <class _WordT, size_t _Extrabits> struct _Sanitize { + static void _M_do_sanitize(_WordT& __val) + { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); } +}; + +template <class _WordT> struct _Sanitize<_WordT, 0> { + static void _M_do_sanitize(_WordT) {} +}; + +// ------------------------------------------------------------ +// Class bitset. +// _Nb may be any nonzero number of type size_t. +// Type _WordT may be any unsigned integral type. + +template<size_t _Nb, class _WordT = unsigned long> +class bitset : private _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT> +{ +private: + typedef _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT> _Base; + + // Import base's protected interface. Necessary because of new template + // name resolution rules. + using _Base::_S_whichword; + using _Base::_S_whichbyte; + using _Base::_S_whichbit; + using _Base::_S_maskbit; + using _Base::_M_getword; + using _Base::_M_hiword; + using _Base::_M_do_and; + using _Base::_M_do_or; + using _Base::_M_do_xor; + using _Base::_M_do_left_shift; + using _Base::_M_do_right_shift; + using _Base::_M_do_flip; + using _Base::_M_do_set; + using _Base::_M_do_reset; + using _Base::_M_is_equal; + using _Base::_M_is_any; + using _Base::_M_do_count; + using _Base::_M_do_to_ulong; + using _Base::_M_do_find_first; + using _Base::_M_do_find_next; + +private: + void _M_do_sanitize() { + _Sanitize<_WordT,_Nb%__BITS_PER_WORDT(_WordT) > + ::_M_do_sanitize(_M_hiword()); + } + +public: + + // bit reference: + class reference { + friend class bitset; + + _WordT *_M_wp; + size_t _M_bpos; + + // left undefined + reference(); + + reference( bitset& __b, size_t __pos ) { + _M_wp = &__b._M_getword(__pos); + _M_bpos = _S_whichbit(__pos); + } + + public: + ~reference() {} + + // for b[i] = __x; + reference& operator=(bool __x) { + if ( __x ) + *_M_wp |= _S_maskbit(_M_bpos); + else + *_M_wp &= ~_S_maskbit(_M_bpos); + + return *this; + } + + // for b[i] = b[__j]; + reference& operator=(const reference& __j) { + if ( (*(__j._M_wp) & _S_maskbit(__j._M_bpos)) ) + *_M_wp |= _S_maskbit(_M_bpos); + else + *_M_wp &= ~_S_maskbit(_M_bpos); + + return *this; + } + + // flips the bit + bool operator~() const { return (*(_M_wp) & _S_maskbit(_M_bpos)) == 0; } + + // for __x = b[i]; + operator bool() const { return (*(_M_wp) & _S_maskbit(_M_bpos)) != 0; } + + // for b[i].flip(); + reference& flip() { + *_M_wp ^= _S_maskbit(_M_bpos); + return *this; + } + }; + + // 23.3.5.1 constructors: + bitset() {} + bitset(unsigned long __val) : + _Base_bitset<__BITSET_WORDS(_Nb,_WordT), _WordT>(__val) {} + + template<class _CharT, class _Traits, class _Alloc> + explicit bitset(const basic_string<_CharT,_Traits,_Alloc>& __s, + size_t __pos = 0, + size_t __n = basic_string<_CharT,_Traits,_Alloc>::npos) + : _Base() + { + if (__pos > __s.size()) + __STL_THROW(out_of_range("bitset")); + _M_copy_from_string(__s, __pos, __n); + } + + // 23.3.5.2 bitset operations: + bitset<_Nb,_WordT>& operator&=(const bitset<_Nb,_WordT>& __rhs) { + _M_do_and(__rhs); + return *this; + } + + bitset<_Nb,_WordT>& operator|=(const bitset<_Nb,_WordT>& __rhs) { + _M_do_or(__rhs); + return *this; + } + + bitset<_Nb,_WordT>& operator^=(const bitset<_Nb,_WordT>& __rhs) { + _M_do_xor(__rhs); + return *this; + } + + bitset<_Nb,_WordT>& operator<<=(size_t __pos) { + _M_do_left_shift(__pos); + _M_do_sanitize(); + return *this; + } + + bitset<_Nb,_WordT>& operator>>=(size_t __pos) { + _M_do_right_shift(__pos); + _M_do_sanitize(); + return *this; + } + + // + // Extension: + // Versions of single-bit set, reset, flip, test with no range checking. + // + + bitset<_Nb,_WordT>& _Unchecked_set(size_t __pos) { + _M_getword(__pos) |= _S_maskbit(__pos); + return *this; + } + + bitset<_Nb,_WordT>& _Unchecked_set(size_t __pos, int __val) { + if (__val) + _M_getword(__pos) |= _S_maskbit(__pos); + else + _M_getword(__pos) &= ~_S_maskbit(__pos); + + return *this; + } + + bitset<_Nb,_WordT>& _Unchecked_reset(size_t __pos) { + _M_getword(__pos) &= ~_S_maskbit(__pos); + return *this; + } + + bitset<_Nb,_WordT>& _Unchecked_flip(size_t __pos) { + _M_getword(__pos) ^= _S_maskbit(__pos); + return *this; + } + + bool _Unchecked_test(size_t __pos) const { + return (_M_getword(__pos) & _S_maskbit(__pos)) != static_cast<_WordT>(0); + } + + // Set, reset, and flip. + + bitset<_Nb,_WordT>& set() { + _M_do_set(); + _M_do_sanitize(); + return *this; + } + + bitset<_Nb,_WordT>& set(size_t __pos) { + if (__pos >= _Nb) + __STL_THROW(out_of_range("bitset")); + + return _Unchecked_set(__pos); + } + + bitset<_Nb,_WordT>& set(size_t __pos, int __val) { + if (__pos >= _Nb) + __STL_THROW(out_of_range("bitset")); + + return _Unchecked_set(__pos, __val); + } + + bitset<_Nb,_WordT>& reset() { + _M_do_reset(); + return *this; + } + + bitset<_Nb,_WordT>& reset(size_t __pos) { + if (__pos >= _Nb) + __STL_THROW(out_of_range("bitset")); + + return _Unchecked_reset(__pos); + } + + bitset<_Nb,_WordT>& flip() { + _M_do_flip(); + _M_do_sanitize(); + return *this; + } + + bitset<_Nb,_WordT>& flip(size_t __pos) { + if (__pos >= _Nb) + __STL_THROW(out_of_range("bitset")); + + return _Unchecked_flip(__pos); + } + + bitset<_Nb,_WordT> operator~() const { + return bitset<_Nb,_WordT>(*this).flip(); + } + + // element access: + //for b[i]; + reference operator[](size_t __pos) { return reference(*this,__pos); } + bool operator[](size_t __pos) const { return _Unchecked_test(__pos); } + + unsigned long to_ulong() const { return _M_do_to_ulong(); } + +#if __STL_EXPLICIT_FUNCTION_TMPL_ARGS + template <class _CharT, class _Traits, class _Alloc> + basic_string<_CharT, _Traits, _Alloc> to_string() const { + basic_string<_CharT, _Traits, _Alloc> __result; + _M_copy_to_string(__result); + return __result; + } +#endif /* __STL_EXPLICIT_FUNCTION_TMPL_ARGS */ + + // Helper functions for string operations. + template<class _CharT, class _Traits, class _Alloc> + void _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, + size_t, + size_t); + + // Helper functions for string operations. + template<class _CharT, class _Traits, class _Alloc> + void _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; + + size_t count() const { return _M_do_count(); } + + size_t size() const { return _Nb; } + + bool operator==(const bitset<_Nb,_WordT>& __rhs) const { + return _M_is_equal(__rhs); + } + bool operator!=(const bitset<_Nb,_WordT>& __rhs) const { + return !_M_is_equal(__rhs); + } + + bool test(size_t __pos) const { + if (__pos > _Nb) + __STL_THROW(out_of_range("bitset")); + + return _Unchecked_test(__pos); + } + + bool any() const { return _M_is_any(); } + bool none() const { return !_M_is_any(); } + + bitset<_Nb,_WordT> operator<<(size_t __pos) const + { return bitset<_Nb,_WordT>(*this) <<= __pos; } + bitset<_Nb,_WordT> operator>>(size_t __pos) const + { return bitset<_Nb,_WordT>(*this) >>= __pos; } + + // + // EXTENSIONS: bit-find operations. These operations are + // experimental, and are subject to change or removal in future + // versions. + // + + // find the index of the first "on" bit + size_t _Find_first() const + { return _M_do_find_first(_Nb); } + + // find the index of the next "on" bit after prev + size_t _Find_next( size_t __prev ) const + { return _M_do_find_next(__prev, _Nb); } + +}; + +// +// Definitions of non-inline member functions. +// + +template <size_t _Nb, class _WordT> +template<class _CharT, class _Traits, class _Alloc> +void bitset<_Nb, _WordT> + ::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, + size_t __pos, + size_t __n) +{ + reset(); + const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); + for (size_t __i = 0; __i < __nbits; ++__i) { + switch(__s[__pos + __nbits - __i - 1]) { + case '0': + break; + case '1': + set(__i); + break; + default: + __STL_THROW(invalid_argument("bitset")); + } + } +} + +template <size_t _Nb, class _WordT> +template <class _CharT, class _Traits, class _Alloc> +void bitset<_Nb, _WordT> + ::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const +{ + __s.assign(_Nb, '0'); + + for (size_t __i = 0; __i < _Nb; ++__i) + if (_Unchecked_test(__i)) + __s[_Nb - 1 - __i] = '1'; +} + +// ------------------------------------------------------------ + +// +// 23.3.5.3 bitset operations: +// + +template <size_t _Nb, class _WordT> +inline bitset<_Nb,_WordT> operator&(const bitset<_Nb,_WordT>& __x, + const bitset<_Nb,_WordT>& __y) { + bitset<_Nb,_WordT> __result(__x); + __result &= __y; + return __result; +} + + +template <size_t _Nb, class _WordT> +inline bitset<_Nb,_WordT> operator|(const bitset<_Nb,_WordT>& __x, + const bitset<_Nb,_WordT>& __y) { + bitset<_Nb,_WordT> __result(__x); + __result |= __y; + return __result; +} + +template <size_t _Nb, class _WordT> +inline bitset<_Nb,_WordT> operator^(const bitset<_Nb,_WordT>& __x, + const bitset<_Nb,_WordT>& __y) { + bitset<_Nb,_WordT> __result(__x); + __result ^= __y; + return __result; +} + +// NOTE: these must be rewritten once we have templatized iostreams. + +template <size_t _Nb, class _WordT> +istream& +operator>>(istream& __is, bitset<_Nb,_WordT>& __x) { + string __tmp; + __tmp.reserve(_Nb); + + // In new templatized iostreams, use istream::sentry + if (__is.flags() & ios::skipws) { + char __c; + do + __is.get(__c); + while (__is && isspace(__c)); + if (__is) + __is.putback(__c); + } + + for (size_t __i = 0; __i < _Nb; ++__i) { + char __c; + __is.get(__c); + + if (!__is) + break; + else if (__c != '0' && __c != '1') { + __is.putback(__c); + break; + } + else + __tmp.push_back(__c); + } + + if (__tmp.empty()) + __is.clear(__is.rdstate() | ios::failbit); + else + __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); + + return __is; +} + +template <size_t _Nb, class _WordT> +ostream& operator<<(ostream& __os, const bitset<_Nb,_WordT>& __x) { + string __tmp; + __x._M_copy_to_string(__tmp); + return __os << __tmp; +} + +// ------------------------------------------------------------ +// Lookup tables for find and count operations. + +template<bool __dummy> +unsigned char _Bit_count<__dummy>::_S_bit_count[] = { + 0, /* 0 */ 1, /* 1 */ 1, /* 2 */ 2, /* 3 */ 1, /* 4 */ + 2, /* 5 */ 2, /* 6 */ 3, /* 7 */ 1, /* 8 */ 2, /* 9 */ + 2, /* 10 */ 3, /* 11 */ 2, /* 12 */ 3, /* 13 */ 3, /* 14 */ + 4, /* 15 */ 1, /* 16 */ 2, /* 17 */ 2, /* 18 */ 3, /* 19 */ + 2, /* 20 */ 3, /* 21 */ 3, /* 22 */ 4, /* 23 */ 2, /* 24 */ + 3, /* 25 */ 3, /* 26 */ 4, /* 27 */ 3, /* 28 */ 4, /* 29 */ + 4, /* 30 */ 5, /* 31 */ 1, /* 32 */ 2, /* 33 */ 2, /* 34 */ + 3, /* 35 */ 2, /* 36 */ 3, /* 37 */ 3, /* 38 */ 4, /* 39 */ + 2, /* 40 */ 3, /* 41 */ 3, /* 42 */ 4, /* 43 */ 3, /* 44 */ + 4, /* 45 */ 4, /* 46 */ 5, /* 47 */ 2, /* 48 */ 3, /* 49 */ + 3, /* 50 */ 4, /* 51 */ 3, /* 52 */ 4, /* 53 */ 4, /* 54 */ + 5, /* 55 */ 3, /* 56 */ 4, /* 57 */ 4, /* 58 */ 5, /* 59 */ + 4, /* 60 */ 5, /* 61 */ 5, /* 62 */ 6, /* 63 */ 1, /* 64 */ + 2, /* 65 */ 2, /* 66 */ 3, /* 67 */ 2, /* 68 */ 3, /* 69 */ + 3, /* 70 */ 4, /* 71 */ 2, /* 72 */ 3, /* 73 */ 3, /* 74 */ + 4, /* 75 */ 3, /* 76 */ 4, /* 77 */ 4, /* 78 */ 5, /* 79 */ + 2, /* 80 */ 3, /* 81 */ 3, /* 82 */ 4, /* 83 */ 3, /* 84 */ + 4, /* 85 */ 4, /* 86 */ 5, /* 87 */ 3, /* 88 */ 4, /* 89 */ + 4, /* 90 */ 5, /* 91 */ 4, /* 92 */ 5, /* 93 */ 5, /* 94 */ + 6, /* 95 */ 2, /* 96 */ 3, /* 97 */ 3, /* 98 */ 4, /* 99 */ + 3, /* 100 */ 4, /* 101 */ 4, /* 102 */ 5, /* 103 */ 3, /* 104 */ + 4, /* 105 */ 4, /* 106 */ 5, /* 107 */ 4, /* 108 */ 5, /* 109 */ + 5, /* 110 */ 6, /* 111 */ 3, /* 112 */ 4, /* 113 */ 4, /* 114 */ + 5, /* 115 */ 4, /* 116 */ 5, /* 117 */ 5, /* 118 */ 6, /* 119 */ + 4, /* 120 */ 5, /* 121 */ 5, /* 122 */ 6, /* 123 */ 5, /* 124 */ + 6, /* 125 */ 6, /* 126 */ 7, /* 127 */ 1, /* 128 */ 2, /* 129 */ + 2, /* 130 */ 3, /* 131 */ 2, /* 132 */ 3, /* 133 */ 3, /* 134 */ + 4, /* 135 */ 2, /* 136 */ 3, /* 137 */ 3, /* 138 */ 4, /* 139 */ + 3, /* 140 */ 4, /* 141 */ 4, /* 142 */ 5, /* 143 */ 2, /* 144 */ + 3, /* 145 */ 3, /* 146 */ 4, /* 147 */ 3, /* 148 */ 4, /* 149 */ + 4, /* 150 */ 5, /* 151 */ 3, /* 152 */ 4, /* 153 */ 4, /* 154 */ + 5, /* 155 */ 4, /* 156 */ 5, /* 157 */ 5, /* 158 */ 6, /* 159 */ + 2, /* 160 */ 3, /* 161 */ 3, /* 162 */ 4, /* 163 */ 3, /* 164 */ + 4, /* 165 */ 4, /* 166 */ 5, /* 167 */ 3, /* 168 */ 4, /* 169 */ + 4, /* 170 */ 5, /* 171 */ 4, /* 172 */ 5, /* 173 */ 5, /* 174 */ + 6, /* 175 */ 3, /* 176 */ 4, /* 177 */ 4, /* 178 */ 5, /* 179 */ + 4, /* 180 */ 5, /* 181 */ 5, /* 182 */ 6, /* 183 */ 4, /* 184 */ + 5, /* 185 */ 5, /* 186 */ 6, /* 187 */ 5, /* 188 */ 6, /* 189 */ + 6, /* 190 */ 7, /* 191 */ 2, /* 192 */ 3, /* 193 */ 3, /* 194 */ + 4, /* 195 */ 3, /* 196 */ 4, /* 197 */ 4, /* 198 */ 5, /* 199 */ + 3, /* 200 */ 4, /* 201 */ 4, /* 202 */ 5, /* 203 */ 4, /* 204 */ + 5, /* 205 */ 5, /* 206 */ 6, /* 207 */ 3, /* 208 */ 4, /* 209 */ + 4, /* 210 */ 5, /* 211 */ 4, /* 212 */ 5, /* 213 */ 5, /* 214 */ + 6, /* 215 */ 4, /* 216 */ 5, /* 217 */ 5, /* 218 */ 6, /* 219 */ + 5, /* 220 */ 6, /* 221 */ 6, /* 222 */ 7, /* 223 */ 3, /* 224 */ + 4, /* 225 */ 4, /* 226 */ 5, /* 227 */ 4, /* 228 */ 5, /* 229 */ + 5, /* 230 */ 6, /* 231 */ 4, /* 232 */ 5, /* 233 */ 5, /* 234 */ + 6, /* 235 */ 5, /* 236 */ 6, /* 237 */ 6, /* 238 */ 7, /* 239 */ + 4, /* 240 */ 5, /* 241 */ 5, /* 242 */ 6, /* 243 */ 5, /* 244 */ + 6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */ + 6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */ + 8 /* 255 */ +}; // end _Bit_count + +template<bool __dummy> +unsigned char _First_one<__dummy>::_S_first_one[] = { + 0, /* 0 */ 0, /* 1 */ 1, /* 2 */ 0, /* 3 */ 2, /* 4 */ + 0, /* 5 */ 1, /* 6 */ 0, /* 7 */ 3, /* 8 */ 0, /* 9 */ + 1, /* 10 */ 0, /* 11 */ 2, /* 12 */ 0, /* 13 */ 1, /* 14 */ + 0, /* 15 */ 4, /* 16 */ 0, /* 17 */ 1, /* 18 */ 0, /* 19 */ + 2, /* 20 */ 0, /* 21 */ 1, /* 22 */ 0, /* 23 */ 3, /* 24 */ + 0, /* 25 */ 1, /* 26 */ 0, /* 27 */ 2, /* 28 */ 0, /* 29 */ + 1, /* 30 */ 0, /* 31 */ 5, /* 32 */ 0, /* 33 */ 1, /* 34 */ + 0, /* 35 */ 2, /* 36 */ 0, /* 37 */ 1, /* 38 */ 0, /* 39 */ + 3, /* 40 */ 0, /* 41 */ 1, /* 42 */ 0, /* 43 */ 2, /* 44 */ + 0, /* 45 */ 1, /* 46 */ 0, /* 47 */ 4, /* 48 */ 0, /* 49 */ + 1, /* 50 */ 0, /* 51 */ 2, /* 52 */ 0, /* 53 */ 1, /* 54 */ + 0, /* 55 */ 3, /* 56 */ 0, /* 57 */ 1, /* 58 */ 0, /* 59 */ + 2, /* 60 */ 0, /* 61 */ 1, /* 62 */ 0, /* 63 */ 6, /* 64 */ + 0, /* 65 */ 1, /* 66 */ 0, /* 67 */ 2, /* 68 */ 0, /* 69 */ + 1, /* 70 */ 0, /* 71 */ 3, /* 72 */ 0, /* 73 */ 1, /* 74 */ + 0, /* 75 */ 2, /* 76 */ 0, /* 77 */ 1, /* 78 */ 0, /* 79 */ + 4, /* 80 */ 0, /* 81 */ 1, /* 82 */ 0, /* 83 */ 2, /* 84 */ + 0, /* 85 */ 1, /* 86 */ 0, /* 87 */ 3, /* 88 */ 0, /* 89 */ + 1, /* 90 */ 0, /* 91 */ 2, /* 92 */ 0, /* 93 */ 1, /* 94 */ + 0, /* 95 */ 5, /* 96 */ 0, /* 97 */ 1, /* 98 */ 0, /* 99 */ + 2, /* 100 */ 0, /* 101 */ 1, /* 102 */ 0, /* 103 */ 3, /* 104 */ + 0, /* 105 */ 1, /* 106 */ 0, /* 107 */ 2, /* 108 */ 0, /* 109 */ + 1, /* 110 */ 0, /* 111 */ 4, /* 112 */ 0, /* 113 */ 1, /* 114 */ + 0, /* 115 */ 2, /* 116 */ 0, /* 117 */ 1, /* 118 */ 0, /* 119 */ + 3, /* 120 */ 0, /* 121 */ 1, /* 122 */ 0, /* 123 */ 2, /* 124 */ + 0, /* 125 */ 1, /* 126 */ 0, /* 127 */ 7, /* 128 */ 0, /* 129 */ + 1, /* 130 */ 0, /* 131 */ 2, /* 132 */ 0, /* 133 */ 1, /* 134 */ + 0, /* 135 */ 3, /* 136 */ 0, /* 137 */ 1, /* 138 */ 0, /* 139 */ + 2, /* 140 */ 0, /* 141 */ 1, /* 142 */ 0, /* 143 */ 4, /* 144 */ + 0, /* 145 */ 1, /* 146 */ 0, /* 147 */ 2, /* 148 */ 0, /* 149 */ + 1, /* 150 */ 0, /* 151 */ 3, /* 152 */ 0, /* 153 */ 1, /* 154 */ + 0, /* 155 */ 2, /* 156 */ 0, /* 157 */ 1, /* 158 */ 0, /* 159 */ + 5, /* 160 */ 0, /* 161 */ 1, /* 162 */ 0, /* 163 */ 2, /* 164 */ + 0, /* 165 */ 1, /* 166 */ 0, /* 167 */ 3, /* 168 */ 0, /* 169 */ + 1, /* 170 */ 0, /* 171 */ 2, /* 172 */ 0, /* 173 */ 1, /* 174 */ + 0, /* 175 */ 4, /* 176 */ 0, /* 177 */ 1, /* 178 */ 0, /* 179 */ + 2, /* 180 */ 0, /* 181 */ 1, /* 182 */ 0, /* 183 */ 3, /* 184 */ + 0, /* 185 */ 1, /* 186 */ 0, /* 187 */ 2, /* 188 */ 0, /* 189 */ + 1, /* 190 */ 0, /* 191 */ 6, /* 192 */ 0, /* 193 */ 1, /* 194 */ + 0, /* 195 */ 2, /* 196 */ 0, /* 197 */ 1, /* 198 */ 0, /* 199 */ + 3, /* 200 */ 0, /* 201 */ 1, /* 202 */ 0, /* 203 */ 2, /* 204 */ + 0, /* 205 */ 1, /* 206 */ 0, /* 207 */ 4, /* 208 */ 0, /* 209 */ + 1, /* 210 */ 0, /* 211 */ 2, /* 212 */ 0, /* 213 */ 1, /* 214 */ + 0, /* 215 */ 3, /* 216 */ 0, /* 217 */ 1, /* 218 */ 0, /* 219 */ + 2, /* 220 */ 0, /* 221 */ 1, /* 222 */ 0, /* 223 */ 5, /* 224 */ + 0, /* 225 */ 1, /* 226 */ 0, /* 227 */ 2, /* 228 */ 0, /* 229 */ + 1, /* 230 */ 0, /* 231 */ 3, /* 232 */ 0, /* 233 */ 1, /* 234 */ + 0, /* 235 */ 2, /* 236 */ 0, /* 237 */ 1, /* 238 */ 0, /* 239 */ + 4, /* 240 */ 0, /* 241 */ 1, /* 242 */ 0, /* 243 */ 2, /* 244 */ + 0, /* 245 */ 1, /* 246 */ 0, /* 247 */ 3, /* 248 */ 0, /* 249 */ + 1, /* 250 */ 0, /* 251 */ 2, /* 252 */ 0, /* 253 */ 1, /* 254 */ + 0, /* 255 */ +}; // end _First_one + +#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) +#pragma reset woff 1209 +#endif + +__STL_END_NAMESPACE + + +#undef __BITS_PER_WORDT +#undef __BITSET_WORDS + +#endif /* __SGI_STL_BITSET */ + + +// Local Variables: +// mode:C++ +// End: + diff --git a/libstdc++/stl/char_traits.h b/libstdc++/stl/char_traits.h new file mode 100644 index 00000000000..44ec2fb60e4 --- /dev/null +++ b/libstdc++/stl/char_traits.h @@ -0,0 +1,135 @@ +/* + * Copyright (c) 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. + */ + +#ifndef __SGI_STL_CHAR_TRAITS_H +#define __SGI_STL_CHAR_TRAITS_H + +#include <string.h> +#include <wchar.h> + +__STL_BEGIN_NAMESPACE + +// Class __char_traits_base. + +template <class _CharT, class _IntT> struct __char_traits_base { + typedef _CharT char_type; + typedef _IntT int_type; + // typedef streamoff off_type; + // typedef streampos pos_type; + // typedef mbstate_t state_type; + + static void assign(char_type& __c1, const char_type& __c2) { __c1 = __c2; } + static bool eq(const _CharT& __c1, const _CharT& __c2) + { return __c1 == __c2; } + static bool lt(const _CharT& __c1, const _CharT& __c2) + { return __c1 < __c2; } + + static int compare(const _CharT* __s1, const _CharT* __s2, size_t __n) { + for (size_t __i = 0; __i < __n; ++__i) + if (!eq(__s1[__i], __s2[__i])) + return __s1[__i] < __s2[__i] ? -1 : 1; + return 0; + } + + static size_t length(const _CharT* __s) { + const _CharT __null = _CharT(); + size_t __i; + for (__i = 0; !eq(__s[__i], __null); ++__i) + {} + return __i; + } + + static const _CharT* find(const _CharT* __s, size_t __n, const _CharT& __c) + { + for ( ; __n > 0 ; ++__s, --__n) + if (eq(*__s, __c)) + return __s; + return 0; + } + + static _CharT* move(_CharT* __s1, const _CharT* __s2, size_t __n) { + memmove(__s1, __s2, __n * sizeof(_CharT)); + return __s1; + } + + static _CharT* copy(_CharT* __s1, const _CharT* __s2, size_t __n) { + memcpy(__s1, __s2, __n * sizeof(_CharT)); + return __s1; + } + + static _CharT* assign(_CharT* __s, size_t __n, _CharT __c) { + for (size_t __i = 0; __i < __n; ++__i) + __s[__i] = __c; + return __s; + } + + static int_type not_eof(const int_type& __c) { + return !eq(__c, eof()) ? __c : 0; + } + + static char_type to_char_type(const int_type& __c) { + return static_cast<char_type>(__c); + } + + static int_type to_int_type(const char_type& __c) { + return static_cast<int_type>(__c); + } + + static bool eq_int_type(const int_type& __c1, const int_type& __c2) { + return __c1 == __c2; + } + + static int_type eof() { + return static_cast<int_type>(-1); + } +}; + +// Generic char_traits class. Note that this class is provided only +// as a base for explicit specialization; it is unlikely to be useful +// as is for any particular user-defined type. In particular, it +// *will not work* for a non-POD type. + +template <class _CharT> struct char_traits + : public __char_traits_base<_CharT, _CharT> +{}; + +// Specialization for char. + +template<> struct char_traits<char> + : public __char_traits_base<char, int> +{ + static int compare(const char* __s1, const char* __s2, size_t __n) + { return memcmp(__s1, __s2, __n); } + + static size_t length(const char* __s) { return strlen(__s); } + + static void assign(char& __c1, const char& __c2) { __c1 = __c2; } + + static char* assign(char* __s, size_t __n, char __c) + { memset(__s, __c, __n); return __s; } +}; + +// Specialization for wchar_t. + +template<> struct char_traits<wchar_t> + : public __char_traits_base<wchar_t, wint_t> +{}; + +__STL_END_NAMESPACE + +#endif /* __SGI_STL_CHAR_TRAITS_H */ + +// Local Variables: +// mode:C++ +// End: + diff --git a/libstdc++/stl/stdexcept b/libstdc++/stl/stdexcept new file mode 100644 index 00000000000..f66143da837 --- /dev/null +++ b/libstdc++/stl/stdexcept @@ -0,0 +1,92 @@ +/* + * Copyright (c) 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. + */ + +#ifndef __SGI_STDEXCEPT +#define __SGI_STDEXCEPT + +#include <stl_exception.h> + +#if !(defined(_MIPS_SIM) && defined(_ABIO32) && _MIPS_SIM == _ABIO32) + +#include <stl_string_fwd.h> + +__STL_BEGIN_NAMESPACE + +class logic_error : public __STL_EXCEPTION_BASE { +public: + logic_error(const string& __s) + { _S_string_copy(__s, _M_name, _S_bufsize); } + virtual const char* what() const __STL_NOTHROW { return _M_name; } +private: + enum { _S_bufsize = 256 }; + char _M_name[_S_bufsize]; +}; + +class runtime_error : public __STL_EXCEPTION_BASE { +public: + runtime_error(const string& __s) + { _S_string_copy(__s, _M_name, _S_bufsize); } + virtual const char* what() const __STL_NOTHROW { return _M_name; } +private: + enum { _S_bufsize = 256 }; + char _M_name[_S_bufsize]; +}; + +class domain_error : public logic_error { +public: + domain_error(const string& __arg) : logic_error(__arg) {} +}; + +class invalid_argument : public logic_error { +public: + invalid_argument(const string& __arg) : logic_error(__arg) {} +}; + +class length_error : public logic_error { +public: + length_error(const string& __arg) : logic_error(__arg) {} +}; + +class out_of_range : public logic_error { +public: + out_of_range(const string& __arg) : logic_error(__arg) {} +}; + +class range_error : public runtime_error { +public: + range_error(const string& __arg) : runtime_error(__arg) {} +}; + +class overflow_error : public runtime_error { +public: + overflow_error(const string& __arg) : runtime_error(__arg) {} +}; + +class underflow_error : public runtime_error { +public: + underflow_error(const string& __arg) : runtime_error(__arg) {} +}; + +__STL_END_NAMESPACE + +#ifndef __SGI_STL_STRING +#include <string> +#endif + +#endif /* Not o32 */ + +#endif /* __SGI_STDEXCEPT */ + +// Local Variables: +// mode:C++ +// End: diff --git a/libstdc++/stl/stl_exception.h b/libstdc++/stl/stl_exception.h new file mode 100644 index 00000000000..37b54d74442 --- /dev/null +++ b/libstdc++/stl/stl_exception.h @@ -0,0 +1,57 @@ +/* + * Copyright (c) 1998 + * 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. + */ + +#ifndef __SGI_STL_EXCEPTION_H +#define __SGI_STL_EXCEPTION_H + +// This header exists solely for portability. Normally it just includes +// the header <exception>. + +// The header <exception> contains low-level functions that interact +// with a compiler's exception-handling mechanism. It is assumed to +// be supplied with the compiler, rather than with the library, because +// it is inherently tied very closely to the compiler itself. + +// On platforms where <exception> does not exist, this header defines +// an exception base class. This is *not* a substitute for everything +// in <exception>, but it suffices to support a bare minimum of STL +// functionality. + +#include <stl_config.h> + +#ifndef __STL_NO_EXCEPTION_HEADER + +#include <exception> +#define __STL_EXCEPTION_BASE exception + +#else /* __STL_NO_EXCEPTION_HEADER */ + +__STL_BEGIN_NAMESPACE + +class _Exception { +public: + virtual ~_Exception() __STL_NOTHROW {} + virtual const char* what() const __STL_NOTHROW { return ""; } +}; + +#define __STL_EXCEPTION_BASE _Exception + +__STL_END_NAMESPACE + +#endif /* __STL_NO_EXCEPTION_HEADER */ + +#endif /* __SGI_STL_EXCEPTION_H */ + +// Local Variables: +// mode:C++ +// End: diff --git a/libstdc++/stl/stl_string_fwd.h b/libstdc++/stl/stl_string_fwd.h new file mode 100644 index 00000000000..d2af9e19f01 --- /dev/null +++ b/libstdc++/stl/stl_string_fwd.h @@ -0,0 +1,51 @@ +/* + * Copyright (c) 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. + */ + +#ifndef __SGI_STL_STRING_FWD_H +#define __SGI_STL_STRING_FWD_H + +#include <stddef.h> + +__STL_BEGIN_NAMESPACE + +#ifdef __STL_USE_STD_ALLOCATORS + +template <class _Tp> class allocator; + +#else /* __STL_USE_STD_ALLOCATORS */ + +template <bool __threads, int __inst> class _Default_alloc_template; +typedef _Default_alloc_template<true, 0> _Alloc; + +#endif /* __STL_USE_STD_ALLOCATORS */ + +template <class _CharT> struct char_traits; +template <class _CharT, + class _Traits = char_traits<_CharT>, + class _Alloc = __STL_DEFAULT_ALLOCATOR(_CharT) > +class basic_string; + +typedef basic_string<char> string; +typedef basic_string<wchar_t> wstring; + +template <class _CharT, class _Traits, class _Alloc> +void _S_string_copy(const basic_string<_CharT,_Traits,_Alloc>&, _CharT*, + size_t); + +__STL_END_NAMESPACE + +#endif /* __SGI_STL_STRING_FWD_H */ + +// Local Variables: +// mode:C++ +// End: diff --git a/libstdc++/stl/string b/libstdc++/stl/string new file mode 100644 index 00000000000..24cfc20940f --- /dev/null +++ b/libstdc++/stl/string @@ -0,0 +1,1960 @@ +/* + * Copyright (c) 1997,1998 + * 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. + */ + +#ifndef __SGI_STL_STRING +#define __SGI_STL_STRING + +#include <ctype.h> +#include <stdexcept> // Includes stl_string_fwd.h and stl_config.h +#include <char_traits.h> // This header name is an extension. +#include <iterator> +#include <functional> +#include <memory> +#include <algorithm> + +// Standard C++ string class. This class has performance +// characteristics very much like vector<>, meaning, for example, that +// it does not perform reference-count or copy-on-write, and that +// concatenation of two strings is an O(N) operation. + +// There are three reasons why basic_string is not identical to +// vector. First, basic_string always stores a null character at the +// end; this makes it possible for c_str to be a fast operation. +// Second, the C++ standard requires basic_string to copy elements +// using char_traits<>::assign, char_traits<>::copy, and +// char_traits<>::move. This means that all of vector<>'s low-level +// operations must be rewritten. Third, basic_string<> has a lot of +// extra functions in its interface that are convenient but, strictly +// speaking, redundant. + +// Additionally, the C++ standard imposes a major restriction: according +// to the standard, the character type _CharT must be a POD type. This +// implementation weakens that restriction, and allows _CharT to be a +// a user-defined non-POD type. However, _CharT must still have a +// default constructor. + +__STL_BEGIN_NAMESPACE + +#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) +#pragma set woff 1174 +#pragma set woff 1375 +#endif + +// Helper classes that turn char_traits into function objects. + +template <class _Traits> +struct _Eq_traits + : public binary_function<typename _Traits::char_type, + typename _Traits::char_type, + bool> +{ + bool operator()(const typename _Traits::char_type& __x, + const typename _Traits::char_type& __y) const + { return _Traits::eq(__x, __y); } +}; + +template <class _Traits> +struct _Lt_traits + : public binary_function<typename _Traits::char_type, + typename _Traits::char_type, + bool> +{ + bool operator()(const typename _Traits::char_type& __x, + const typename _Traits::char_type& __y) const + { return _Traits::lt(__x, __y); } +}; + +template <class _Traits> +struct _Not_within_traits + : public unary_function<typename _Traits::char_type, bool> +{ + typedef const typename _Traits::char_type* _Pointer; + const _Pointer _M_first; + const _Pointer _M_last; + + _Not_within_traits(_Pointer __f, _Pointer __l) + : _M_first(__f), _M_last(__l) {} + + bool operator()(const typename _Traits::char_type& __x) const { + return find_if(_M_first, _M_last, + bind1st(_Eq_traits<_Traits>(), __x)) == _M_last; + } +}; + +// ------------------------------------------------------------ +// Class _String_base. + +// _String_base is a helper class that makes it it easier to write an +// exception-safe version of basic_string. The constructor allocates, +// but does not initialize, a block of memory. The destructor +// deallocates, but does not destroy elements within, a block of +// memory. The destructor assumes that _M_start either is null, or else +// points to a block of memory that was allocated using _String_base's +// allocator and whose size is _M_end_of_storage - _M_start. + +// Additionally, _String_base encapsulates the difference between +// old SGI-style allocators and standard-conforming allocators. + +#ifdef __STL_USE_STD_ALLOCATORS + +// General base class. +template <class _Tp, class _Alloc, bool _S_instanceless> +class _String_alloc_base { +public: + typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; + allocator_type get_allocator() const { return _M_data_allocator; } + + _String_alloc_base(const allocator_type& __a) + : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) + {} + +protected: + _Tp* _M_allocate(size_t __n) + { return _M_data_allocator.allocate(__n); } + void _M_deallocate(_Tp* __p, size_t __n) { + if (__p) + _M_data_allocator.deallocate(__p, __n); + } + +protected: + allocator_type _M_data_allocator; + + _Tp* _M_start; + _Tp* _M_finish; + _Tp* _M_end_of_storage; +}; + +// Specialization for instanceless allocators. +template <class _Tp, class _Alloc> +class _String_alloc_base<_Tp,_Alloc,true> { +public: + typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; + allocator_type get_allocator() const { return allocator_type(); } + + _String_alloc_base(const allocator_type&) + : _M_start(0), _M_finish(0), _M_end_of_storage(0) {} + +protected: + typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Alloc_type; + _Tp* _M_allocate(size_t __n) + { return _Alloc_type::allocate(__n); } + void _M_deallocate(_Tp* __p, size_t __n) + { _Alloc_type::deallocate(__p, __n); } + +protected: + _Tp* _M_start; + _Tp* _M_finish; + _Tp* _M_end_of_storage; +}; + +template <class _Tp, class _Alloc> +class _String_base + : public _String_alloc_base<_Tp, _Alloc, + _Alloc_traits<_Tp, _Alloc>::_S_instanceless> +{ +protected: + typedef _String_alloc_base<_Tp, _Alloc, + _Alloc_traits<_Tp, _Alloc>::_S_instanceless> + _Base; + typedef typename _Base::allocator_type allocator_type; + + void _M_allocate_block(size_t __n) { + if (__n <= max_size()) { + _M_start = _M_allocate(__n); + _M_finish = _M_start; + _M_end_of_storage = _M_start + __n; + } + else + _M_throw_length_error(); + } + + void _M_deallocate_block() + { _M_deallocate(_M_start, _M_end_of_storage - _M_start); } + + size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; } + + _String_base(const allocator_type& __a) : _Base(__a) { } + + _String_base(const allocator_type& __a, size_t __n) : _Base(__a) + { _M_allocate_block(__n); } + + ~_String_base() { _M_deallocate_block(); } + + void _M_throw_length_error() const; + void _M_throw_out_of_range() const; +}; + +#else /* __STL_USE_STD_ALLOCATORS */ + +template <class _Tp, class _Alloc> class _String_base { +protected: + typedef simple_alloc<_Tp, _Alloc> _Alloc_type; + typedef _Alloc allocator_type; + allocator_type get_allocator() const { return allocator_type(); } + + _Tp* _M_start; + _Tp* _M_finish; + _Tp* _M_end_of_storage; + // Precondition: 0 < __n <= max_size(). + + _Tp* _M_allocate(size_t __n) { return _Alloc_type::allocate(__n); } + void _M_deallocate(_Tp* __p, size_t __n) { + if (__p) + _Alloc_type::deallocate(__p, __n); + } + + void _M_allocate_block(size_t __n) { + if (__n <= max_size()) { + _M_start = _M_allocate(__n); + _M_finish = _M_start; + _M_end_of_storage = _M_start + __n; + } + else + _M_throw_length_error(); + } + + void _M_deallocate_block() + { _M_deallocate(_M_start, _M_end_of_storage - _M_start); } + + size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; } + + _String_base(const allocator_type&) + : _M_start(0), _M_finish(0), _M_end_of_storage(0) { } + + _String_base(const allocator_type&, size_t __n) + : _M_start(0), _M_finish(0), _M_end_of_storage(0) + { _M_allocate_block(__n); } + + ~_String_base() { _M_deallocate_block(); } + + void _M_throw_length_error() const; + void _M_throw_out_of_range() const; +}; + +#endif /* __STL_USE_STD_ALLOCATORS */ + +template <class _Tp, class _Alloc> +void _String_base<_Tp,_Alloc>::_M_throw_length_error() const { + __STL_THROW(length_error("basic_string")); +} + +template <class _Tp, class _Alloc> +void _String_base<_Tp, _Alloc>::_M_throw_out_of_range() const { + __STL_THROW(out_of_range("basic_string")); +} + +// ------------------------------------------------------------ +// Class basic_string. + +// Class invariants: +// (1) [start, finish) is a valid range. +// (2) Each iterator in [start, finish) points to a valid object +// of type value_type. +// (3) *finish is a valid object of type value_type; in particular, +// it is value_type(). +// (4) [finish + 1, end_of_storage) is a valid range. +// (5) Each iterator in [finish + 1, end_of_storage) points to +// unininitialized memory. + +// Note one important consequence: a string of length n must manage +// a block of memory whose size is at least n + 1. + + +template <class _CharT, class _Traits, class _Alloc> +class basic_string : private _String_base<_CharT,_Alloc> { +public: + typedef _CharT value_type; + typedef _Traits traits_type; + + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef size_t size_type; + typedef ptrdiff_t difference_type; + + typedef const value_type* const_iterator; + typedef value_type* iterator; + typedef reverse_iterator<const_iterator> const_reverse_iterator; + typedef reverse_iterator<iterator> reverse_iterator; + + static const size_type npos = -1; + + typedef _String_base<_CharT,_Alloc> _Base; + +public: // Constructor, destructor, assignment. + typedef typename _Base::allocator_type allocator_type; +#ifdef __STL_USE_NAMESPACES + using _Base::get_allocator; +#endif /* __STL_USE_NAMESPACES */ + + explicit basic_string(const allocator_type& __a = allocator_type()) + : _Base(__a, 8) { construct(_M_finish); } + + struct _Reserve_t {}; + basic_string(_Reserve_t, size_t __n, + const allocator_type& __a = allocator_type()) + : _Base(__a, __n + 1) { construct(_M_finish); } + + basic_string(const basic_string& __s) : _Base(__s.get_allocator()) + { _M_range_initialize(__s.begin(), __s.end()); } + + basic_string(const basic_string& __s, size_type __pos, size_type __n = npos, + const allocator_type& __a = allocator_type()) + : _Base(__a) { + if (__pos > __s.size()) + _M_throw_out_of_range(); + else + _M_range_initialize(__s.begin() + __pos, + __s.begin() + __pos + min(__n, __s.size() - __pos)); + } + + basic_string(const _CharT* __s, size_type __n, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { _M_range_initialize(__s, __s + __n); } + + basic_string(const _CharT* __s, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { _M_range_initialize(__s, __s + _Traits::length(__s)); } + + basic_string(size_type __n, _CharT __c, + const allocator_type& __a = allocator_type()) + : _Base(__a, __n + 1) + { + _M_finish = uninitialized_fill_n(_M_start, __n, __c); + _M_terminate_string(); + } + + // Check to see if _InputIterator is an integer type. If so, then + // it can't be an iterator. + template <class _InputIterator> + basic_string(_InputIterator __f, _InputIterator __l, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { + typedef typename _Is_integer<_InputIterator>::_Integral _Integral; + _M_initialize_dispatch(__f, __l, _Integral()); + } + + ~basic_string() { destroy(_M_start, _M_finish + 1); } + + basic_string& operator=(const basic_string& __s) { + if (&__s != this) + assign(__s.begin(), __s.end()); + return *this; + } + + basic_string& operator=(const _CharT* __s) + { return assign(__s, __s + _Traits::length(__s)); } + + basic_string& operator=(_CharT __c) + { return assign(static_cast<size_type>(1), __c); } + +private: // Protected members inherited from base. +#ifdef __STL_HAS_NAMESPACES + using _Base::_M_allocate; + using _Base::_M_deallocate; + using _Base::_M_allocate_block; + using _Base::_M_deallocate_block; + using _Base::_M_throw_length_error; + using _Base::_M_throw_out_of_range; + + using _Base::_M_start; + using _Base::_M_finish; + using _Base::_M_end_of_storage; +#endif /* __STL_HAS_NAMESPACES */ + +private: + // Helper functions used by constructors. It is a severe error for + // any of them to be called anywhere except from within constructors. + + void _M_terminate_string() { + __STL_TRY { + construct(_M_finish); + } + __STL_UNWIND(destroy(_M_start, _M_finish)); + } + + template <class _InputIter> + void _M_range_initialize(_InputIter __f, _InputIter __l, + input_iterator_tag) { + _M_allocate_block(8); + construct(_M_finish); + __STL_TRY { + append(__f, __l); + } + __STL_UNWIND(destroy(_M_start, _M_finish + 1)); + } + + template <class _ForwardIter> + void _M_range_initialize(_ForwardIter __f, _ForwardIter __l, + forward_iterator_tag) { + typename iterator_traits<_ForwardIter>::difference_type __n + = distance(__f, __l); + _M_allocate_block(__n + 1); + _M_finish = uninitialized_copy(__f, __l, _M_start); + _M_terminate_string(); + } + + template <class _InputIter> + void _M_range_initialize(_InputIter __f, _InputIter __l) { + typedef typename iterator_traits<_InputIter>::iterator_category _Category; + _M_range_initialize(__f, __l, _Category()); + } + + template <class _Integer> + void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) { + _M_allocate_block(__n + 1); + _M_finish = uninitialized_fill_n(_M_start, __n, __x); + _M_terminate_string(); + } + + template <class _InputIter> + void _M_initialize_dispatch(_InputIter __f, _InputIter __l, __false_type) { + _M_range_initialize(__f, __l); + } + + +public: // Iterators. + iterator begin() { return _M_start; } + iterator end() { return _M_finish; } + const_iterator begin() const { return _M_start; } + const_iterator end() const { return _M_finish; } + + reverse_iterator rbegin() + { return reverse_iterator(_M_finish); } + reverse_iterator rend() + { return reverse_iterator(_M_start); } + const_reverse_iterator rbegin() const + { return const_reverse_iterator(_M_finish); } + const_reverse_iterator rend() const + { return const_reverse_iterator(_M_start); } + +public: // Size, capacity, etc. + size_type size() const { return _M_finish - _M_start; } + size_type length() const { return size(); } +#ifdef __STL_USE_NAMESPACES + using _Base::max_size; +#endif /* __STL_USE_NAMESPACES */ + + void resize(size_type __n, _CharT __c = _CharT()) { + if (__n <= size()) + erase(begin() + __n, end()); + else + append(__n - size(), __c); + } + + void reserve(size_type = 0); + + size_type capacity() const { return (_M_end_of_storage - _M_start) - 1; } + + void clear() { + if (!empty()) { + _Traits::assign(*_M_start, _CharT()); + destroy(_M_start+1, _M_finish+1); + _M_finish = _M_start; + } + } + + bool empty() const { return _M_start == _M_finish; } + +public: // Element access. + + const_reference operator[](size_type __n) const + { return *(_M_start + __n); } + reference operator[](size_type __n) + { return *(_M_start + __n); } + + const_reference at(size_type __n) const { + if (__n >= size()) + _M_throw_out_of_range(); + return *(_M_start + __n); + } + + reference at(size_type __n) { + if (__n >= size()) + _M_throw_out_of_range(); + return *(_M_start + __n); + } + +public: // Append, operator+=, push_back. + + basic_string& operator+=(const basic_string& __s) { return append(__s); } + basic_string& operator+=(const _CharT* __s) { return append(__s); } + basic_string& operator+=(_CharT __c) { push_back(__c); return *this; } + + basic_string& append(const basic_string& __s) + { return append(__s.begin(), __s.end()); } + + basic_string& append(const basic_string& __s, + size_type __pos, size_type __n) + { + if (__pos > __s.size()) + _M_throw_out_of_range(); + return append(__s.begin() + __pos, + __s.begin() + __pos + min(__n, __s.size() - __pos)); + } + + basic_string& append(const _CharT* __s, size_type __n) + { return append(__s, __s+__n); } + + basic_string& append(const _CharT* __s) + { return append(__s, __s + _Traits::length(__s)); } + + basic_string& append(size_type __n, _CharT __c); + + // Check to see if _InputIterator is an integer type. If so, then + // it can't be an iterator. + template <class _InputIter> + basic_string& append(_InputIter __first, _InputIter __last) { + typedef typename _Is_integer<_InputIter>::_Integral _Integral; + return _M_append_dispatch(__first, __last, _Integral()); + } + + void push_back(_CharT __c) { + if (_M_finish + 1 == _M_end_of_storage) + reserve(size() + max(size(), static_cast<size_type>(1))); + construct(_M_finish + 1); + _Traits::assign(*_M_finish, __c); + ++_M_finish; + } + + void pop_back() { + _Traits::assign(*(_M_finish - 1), _CharT()); + destroy(_M_finish); + --_M_finish; + } + +private: // Helper functions for append. + + template <class _InputIter> + basic_string& append(_InputIter __f, _InputIter __l, input_iterator_tag); + + template <class _ForwardIter> + basic_string& append(_ForwardIter __f, _ForwardIter __l, + forward_iterator_tag); + + template <class _Integer> + basic_string& _M_append_dispatch(_Integer __n, _Integer __x, __true_type) { + return append((size_type) __n, (_CharT) __x); + } + + template <class _InputIter> + basic_string& _M_append_dispatch(_InputIter __f, _InputIter __l, + __false_type) { + typedef typename iterator_traits<_InputIter>::iterator_category _Category; + return append(__f, __l, _Category()); + } + +public: // Assign + + basic_string& assign(const basic_string& __s) + { return assign(__s.begin(), __s.end()); } + + basic_string& assign(const basic_string& __s, + size_type __pos, size_type __n) { + if (__pos > __s.size()) + _M_throw_out_of_range(); + return assign(__s.begin() + __pos, + __s.begin() + __pos + min(__n, __s.size() - __pos)); + } + + basic_string& assign(const _CharT* __s, size_type __n) + { return assign(__s, __s + __n); } + + basic_string& assign(const _CharT* __s) + { return assign(__s, __s + _Traits::length(__s)); } + + basic_string& assign(size_type __n, _CharT __c); + + // Check to see if _InputIterator is an integer type. If so, then + // it can't be an iterator. + template <class _InputIter> + basic_string& assign(_InputIter __first, _InputIter __last) { + typedef typename _Is_integer<_InputIter>::_Integral _Integral; + return _M_assign_dispatch(__first, __last, _Integral()); + } + + basic_string& assign(const _CharT* __f, const _CharT* __l); + +private: // Helper functions for assign. + + template <class _Integer> + basic_string& _M_assign_dispatch(_Integer __n, _Integer __x, __true_type) { + return assign((size_type) __n, (_CharT) __x); + } + + template <class _InputIter> + basic_string& _M_assign_dispatch(_InputIter __f, _InputIter __l, + __false_type); + +public: // Insert + + basic_string& insert(size_type __pos, const basic_string& __s) { + if (__pos > size()) + _M_throw_out_of_range(); + if (size() > max_size() - __s.size()) + _M_throw_length_error(); + insert(_M_start + __pos, __s.begin(), __s.end()); + return *this; + } + + basic_string& insert(size_type __pos, const basic_string& __s, + size_type __beg, size_type __n) { + if (__pos > size() || __beg > __s.size()) + _M_throw_out_of_range(); + size_type __len = min(__n, __s.size() - __beg); + if (size() > max_size() - __len) + _M_throw_length_error(); + insert(_M_start + __pos, + __s.begin() + __beg, __s.begin() + __beg + __len); + return *this; + } + + basic_string& insert(size_type __pos, const _CharT* __s, size_type __n) { + if (__pos > size()) + _M_throw_out_of_range(); + if (size() > max_size() - __n) + _M_throw_length_error(); + insert(_M_start + __pos, __s, __s + __n); + return *this; + } + + basic_string& insert(size_type __pos, const _CharT* __s) { + if (__pos > size()) + _M_throw_out_of_range(); + size_type __len = _Traits::length(__s); + if (size() > max_size() - __len) + _M_throw_length_error(); + insert(_M_start + __pos, __s, __s + __len); + return *this; + } + + basic_string& insert(size_type __pos, size_type __n, _CharT __c) { + if (__pos > size()) + _M_throw_out_of_range(); + if (size() > max_size() - __n) + _M_throw_length_error(); + insert(_M_start + __pos, __n, __c); + return *this; + } + + iterator insert(iterator __p, _CharT __c) { + if (__p == _M_finish) { + push_back(__c); + return _M_finish - 1; + } + else + return _M_insert_aux(__p, __c); + } + + void insert(iterator __p, size_t __n, _CharT __c); + + // Check to see if _InputIterator is an integer type. If so, then + // it can't be an iterator. + template <class _InputIter> + void insert(iterator __p, _InputIter __first, _InputIter __last) { + typedef typename _Is_integer<_InputIter>::_Integral _Integral; + _M_insert_dispatch(__p, __first, __last, _Integral()); + } + +private: // Helper functions for insert. + template <class _InputIter> + void insert(iterator __p, _InputIter, _InputIter, input_iterator_tag); + + template <class _ForwardIter> + void insert(iterator __p, _ForwardIter, _ForwardIter, forward_iterator_tag); + + + template <class _Integer> + void _M_insert_dispatch(iterator __p, _Integer __n, _Integer __x, + __true_type) { + insert(__p, (size_type) __n, (_CharT) __x); + } + + template <class _InputIter> + void _M_insert_dispatch(iterator __p, _InputIter __first, _InputIter __last, + __false_type) { + typedef typename iterator_traits<_InputIter>::iterator_category _Category; + insert(__p, __first, __last, _Category()); + } + + iterator _M_insert_aux(iterator, _CharT); + + template <class _InputIterator> + void + _M_copy(_InputIterator __first, _InputIterator __last, iterator __result) { + for ( ; __first != __last; ++__first, ++__result) + _Traits::assign(*__result, *__first); + } + + void + _M_copy(const _CharT* __first, const _CharT* __last, _CharT* __result) { + _Traits::copy(__result, __first, __last - __first); + } + +public: // Erase. + + basic_string& erase(size_type __pos = 0, size_type __n = npos) { + if (__pos > size()) + _M_throw_out_of_range(); + erase(_M_start + __pos, _M_start + __pos + min(__n, size() - __pos)); + return *this; + } + + iterator erase(iterator __position) { + // The move includes the terminating _CharT(). + _Traits::move(__position, __position + 1, _M_finish - __position); + destroy(_M_finish); + --_M_finish; + return __position; + } + + iterator erase(iterator __first, iterator __last) { + if (__first != __last) { + // The move includes the terminating _CharT(). + _Traits::move(__first, __last, (_M_finish - __last) + 1); + const iterator __new_finish = _M_finish - (__last - __first); + destroy(__new_finish + 1, _M_finish + 1); + _M_finish = __new_finish; + } + return __first; + } + +public: // Replace. (Conceptually equivalent + // to erase followed by insert.) + basic_string& replace(size_type __pos, size_type __n, + const basic_string& __s) { + if (__pos > size()) + _M_throw_out_of_range(); + const size_type __len = min(__n, size() - __pos); + if (size() - __len >= max_size() - __s.size()) + _M_throw_length_error(); + return replace(_M_start + __pos, _M_start + __pos + __len, + __s.begin(), __s.end()); + } + + basic_string& replace(size_type __pos1, size_type __n1, + const basic_string& __s, + size_type __pos2, size_type __n2) { + if (__pos1 > size() || __pos2 > __s.size()) + _M_throw_out_of_range(); + const size_type __len1 = min(__n1, size() - __pos1); + const size_type __len2 = min(__n2, __s.size() - __pos2); + if (size() - __len1 >= max_size() - __len2) + _M_throw_length_error(); + return replace(_M_start + __pos1, _M_start + __pos1 + __len1, + __s._M_start + __pos2, __s._M_start + __pos2 + __len2); + } + + basic_string& replace(size_type __pos, size_type __n1, + const _CharT* __s, size_type __n2) { + if (__pos > size()) + _M_throw_out_of_range(); + const size_type __len = min(__n1, size() - __pos); + if (__n2 > max_size() || size() - __len >= max_size() - __n2) + _M_throw_length_error(); + return replace(_M_start + __pos, _M_start + __pos + __len, + __s, __s + __n2); + } + + basic_string& replace(size_type __pos, size_type __n1, + const _CharT* __s) { + if (__pos > size()) + _M_throw_out_of_range(); + const size_type __len = min(__n1, size() - __pos); + const size_type __n2 = _Traits::length(__s); + if (__n2 > max_size() || size() - __len >= max_size() - __n2) + _M_throw_length_error(); + return replace(_M_start + __pos, _M_start + __pos + __len, + __s, __s + _Traits::length(__s)); + } + + basic_string& replace(size_type __pos, size_type __n1, + size_type __n2, _CharT __c) { + if (__pos > size()) + _M_throw_out_of_range(); + const size_type __len = min(__n1, size() - __pos); + if (__n2 > max_size() || size() - __len >= max_size() - __n2) + _M_throw_length_error(); + return replace(_M_start + __pos, _M_start + __pos + __len, __n2, __c); + } + + basic_string& replace(iterator __first, iterator __last, + const basic_string& __s) + { return replace(__first, __last, __s.begin(), __s.end()); } + + basic_string& replace(iterator __first, iterator __last, + const _CharT* __s, size_type __n) + { return replace(__first, __last, __s, __s + __n); } + + basic_string& replace(iterator __first, iterator __last, + const _CharT* __s) { + return replace(__first, __last, __s, __s + _Traits::length(__s)); + } + + basic_string& replace(iterator __first, iterator __last, + size_type __n, _CharT __c); + + // Check to see if _InputIterator is an integer type. If so, then + // it can't be an iterator. + template <class _InputIter> + basic_string& replace(iterator __first, iterator __last, + _InputIter __f, _InputIter __l) { + typedef typename _Is_integer<_InputIter>::_Integral _Integral; + return _M_replace_dispatch(__first, __last, __f, __l, _Integral()); + } + +private: // Helper functions for replace. + + template <class _Integer> + basic_string& _M_replace_dispatch(iterator __first, iterator __last, + _Integer __n, _Integer __x, + __true_type) { + return replace(__first, __last, (size_type) __n, (_CharT) __x); + } + + template <class _InputIter> + basic_string& _M_replace_dispatch(iterator __first, iterator __last, + _InputIter __f, _InputIter __l, + __false_type) { + typedef typename iterator_traits<_InputIter>::iterator_category _Category; + return replace(__first, __last, __f, __l, _Category()); + } + + template <class _InputIter> + basic_string& replace(iterator __first, iterator __last, + _InputIter __f, _InputIter __l, input_iterator_tag); + + template <class _ForwardIter> + basic_string& replace(iterator __first, iterator __last, + _ForwardIter __f, _ForwardIter __l, + forward_iterator_tag); + +public: // Other modifier member functions. + + size_type copy(_CharT* __s, size_type __n, size_type __pos = 0) const { + if (__pos > size()) + _M_throw_out_of_range(); + const size_type __len = min(__n, size() - __pos); + _Traits::copy(__s, _M_start + __pos, __len); + return __len; + } + + void swap(basic_string& __s) { + __STD::swap(_M_start, __s._M_start); + __STD::swap(_M_finish, __s._M_finish); + __STD::swap(_M_end_of_storage, __s._M_end_of_storage); + } + +public: // Conversion to C string. + + const _CharT* c_str() const { return _M_start; } + const _CharT* data() const { return _M_start; } + +public: // find. + + size_type find(const basic_string& __s, size_type __pos = 0) const + { return find(__s.begin(), __pos, __s.size()); } + + size_type find(const _CharT* __s, size_type __pos = 0) const + { return find(__s, __pos, _Traits::length(__s)); } + + size_type find(const _CharT* __s, size_type __pos, size_type __n) const; + size_type find(_CharT __c, size_type __pos = 0) const; + +public: // rfind. + + size_type rfind(const basic_string& __s, size_type __pos = npos) const + { return rfind(__s.begin(), __pos, __s.size()); } + + size_type rfind(const _CharT* __s, size_type __pos = npos) const + { return rfind(__s, __pos, _Traits::length(__s)); } + + size_type rfind(const _CharT* __s, size_type __pos, size_type __n) const; + size_type rfind(_CharT __c, size_type __pos = npos) const; + +public: // find_first_of + + size_type find_first_of(const basic_string& __s, size_type __pos = 0) const + { return find_first_of(__s.begin(), __pos, __s.size()); } + + size_type find_first_of(const _CharT* __s, size_type __pos = 0) const + { return find_first_of(__s, __pos, _Traits::length(__s)); } + + size_type find_first_of(const _CharT* __s, size_type __pos, + size_type __n) const; + + size_type find_first_of(_CharT __c, size_type __pos = 0) const + { return find(__c, __pos); } + +public: // find_last_of + + size_type find_last_of(const basic_string& __s, + size_type __pos = npos) const + { return find_last_of(__s.begin(), __pos, __s.size()); } + + size_type find_last_of(const _CharT* __s, size_type __pos = npos) const + { return find_last_of(__s, __pos, _Traits::length(__s)); } + + size_type find_last_of(const _CharT* __s, size_type __pos, + size_type __n) const; + + size_type find_last_of(_CharT __c, size_type __pos = npos) const { + return rfind(__c, __pos); + } + +public: // find_first_not_of + + size_type find_first_not_of(const basic_string& __s, + size_type __pos = 0) const + { return find_first_not_of(__s.begin(), __pos, __s.size()); } + + size_type find_first_not_of(const _CharT* __s, size_type __pos = 0) const + { return find_first_not_of(__s, __pos, _Traits::length(__s)); } + + size_type find_first_not_of(const _CharT* __s, size_type __pos, + size_type __n) const; + + size_type find_first_not_of(_CharT __c, size_type __pos = 0) const; + +public: // find_last_not_of + + size_type find_last_not_of(const basic_string& __s, + size_type __pos = npos) const + { return find_last_not_of(__s.begin(), __pos, __s.size()); } + + size_type find_last_not_of(const _CharT* __s, size_type __pos = npos) const + { return find_last_not_of(__s, __pos, _Traits::length(__s)); } + + size_type find_last_not_of(const _CharT* __s, size_type __pos, + size_type __n) const; + + size_type find_last_not_of(_CharT __c, size_type __pos = npos) const; + +public: // Substring. + + basic_string substr(size_type __pos = 0, size_type __n = npos) const { + if (__pos > size()) + _M_throw_out_of_range(); + return basic_string(_M_start + __pos, + _M_start + __pos + min(__n, size() - __pos)); + } + +public: // Compare + + int compare(const basic_string& __s) const + { return _M_compare(_M_start, _M_finish, __s._M_start, __s._M_finish); } + + int compare(size_type __pos1, size_type __n1, + const basic_string& __s) const { + if (__pos1 > size()) + _M_throw_out_of_range(); + return _M_compare(_M_start + __pos1, + _M_start + __pos1 + min(__n1, size() - __pos1), + __s._M_start, __s._M_finish); + } + + int compare(size_type __pos1, size_type __n1, + const basic_string& __s, + size_type __pos2, size_type __n2) const { + if (__pos1 > size() || __pos2 > __s.size()) + _M_throw_out_of_range(); + return _M_compare(_M_start + __pos1, + _M_start + __pos1 + min(__n1, size() - __pos1), + __s._M_start + __pos2, + __s._M_start + __pos2 + min(__n2, size() - __pos2)); + } + + int compare(const _CharT* __s) const { + return _M_compare(_M_start, _M_finish, __s, __s + _Traits::length(__s)); + } + + int compare(size_type __pos1, size_type __n1, const _CharT* __s) const { + if (__pos1 > size()) + _M_throw_out_of_range(); + return _M_compare(_M_start + __pos1, + _M_start + __pos1 + min(__n1, size() - __pos1), + __s, __s + _Traits::length(__s)); + } + + int compare(size_type __pos1, size_type __n1, const _CharT* __s, + size_type __n2) const { + if (__pos1 > size()) + _M_throw_out_of_range(); + return _M_compare(_M_start + __pos1, + _M_start + __pos1 + min(__n1, size() - __pos1), + __s, __s + __n2); + } + +private: // Helper functions for compare. + + static int _M_compare(const _CharT* __f1, const _CharT* __l1, + const _CharT* __f2, const _CharT* __l2) { + const ptrdiff_t __n1 = __l1 - __f1; + const ptrdiff_t __n2 = __l2 - __f2; + const int cmp = _Traits::compare(__f1, __f2, min(__n1, __n2)); + return cmp != 0 ? cmp : (__n1 < __n2 ? -1 : (__n1 > __n2 ? 1 : 0)); + } + + friend bool operator< __STL_NULL_TMPL_ARGS (const basic_string&, + const basic_string&); + friend bool operator< __STL_NULL_TMPL_ARGS (const _CharT*, + const basic_string&); + friend bool operator< __STL_NULL_TMPL_ARGS (const basic_string&, + const _CharT*); +}; + + + +// ------------------------------------------------------------ +// Non-inline declarations. + +template <class _CharT, class _Traits, class _Alloc> +const basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc>::npos; + +// Change the string's capacity so that it is large enough to hold +// at least __res_arg elements, plus the terminating _CharT(). Note that, +// if __res_arg < capacity(), this member function may actually decrease +// the string's capacity. +template <class _CharT, class _Traits, class _Alloc> +void basic_string<_CharT,_Traits,_Alloc>::reserve(size_type __res_arg) { + if (__res_arg > max_size()) + _M_throw_length_error(); + + size_type __n = max(__res_arg, size()) + 1; + pointer __new_start = _M_allocate(__n); + pointer __new_finish = __new_start; + + __STL_TRY { + __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start); + construct(__new_finish); + } + __STL_UNWIND((destroy(__new_start, __new_finish), + _M_deallocate(__new_start, __n))); + + destroy(_M_start, _M_finish + 1); + _M_deallocate_block(); + _M_start = __new_start; + _M_finish = __new_finish; + _M_end_of_storage = __new_start + __n; +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>& +basic_string<_CharT,_Traits,_Alloc>::append(size_type __n, _CharT __c) { + if (__n > max_size() || size() > max_size() - __n) + _M_throw_length_error(); + if (size() + __n > capacity()) + reserve(size() + max(size(), __n)); + if (__n > 0) { + uninitialized_fill_n(_M_finish + 1, __n - 1, __c); + __STL_TRY { + construct(_M_finish + __n); + } + __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n)); + _Traits::assign(*_M_finish, __c); + _M_finish += __n; + } + return *this; +} + +template <class _Tp, class _Traits, class _Alloc> +template <class _InputIterator> +basic_string<_Tp, _Traits, _Alloc>& +basic_string<_Tp, _Traits, _Alloc>::append(_InputIterator __first, + _InputIterator __last, + input_iterator_tag) { + for ( ; __first != __last ; ++__first) + push_back(*__first); + return *this; +} + +template <class _Tp, class _Traits, class _Alloc> +template <class _ForwardIter> +basic_string<_Tp, _Traits, _Alloc>& +basic_string<_Tp, _Traits, _Alloc>::append(_ForwardIter __first, + _ForwardIter __last, + forward_iterator_tag) { + if (__first != __last) { + const size_type __old_size = size(); + typename iterator_traits<_ForwardIter>::difference_type __n + = distance(__first, __last); + if (__n > max_size() || __old_size > max_size() - __n) + _M_throw_length_error(); + if (__old_size + __n > capacity()) { + const size_type __len = __old_size + + max(__old_size, static_cast<size_type>(__n)) + 1; + pointer __new_start = _M_allocate(__len); + pointer __new_finish = __new_start; + __STL_TRY { + __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start); + __new_finish = uninitialized_copy(__first, __last, __new_finish); + construct(__new_finish); + } + __STL_UNWIND((destroy(__new_start,__new_finish), + _M_deallocate(__new_start,__len))); + destroy(_M_start, _M_finish + 1); + _M_deallocate_block(); + _M_start = __new_start; + _M_finish = __new_finish; + _M_end_of_storage = __new_start + __len; + } + else { + _ForwardIter __f1 = __first; + ++__f1; + uninitialized_copy(__f1, __last, _M_finish + 1); + __STL_TRY { + construct(_M_finish + __n); + } + __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n)); + _Traits::assign(*_M_finish, *__first); + _M_finish += __n; + } + } + return *this; +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>& +basic_string<_CharT,_Traits,_Alloc>::assign(size_type __n, _CharT __c) { + if (__n <= size()) { + _Traits::assign(_M_start, __n, __c); + erase(_M_start + __n, _M_finish); + } + else { + _Traits::assign(_M_start, size(), __c); + append(__n - size(), __c); + } + return *this; +} + +template <class _CharT, class _Traits, class _Alloc> +template <class _InputIter> +basic_string<_CharT,_Traits,_Alloc>& basic_string<_CharT,_Traits,_Alloc> + ::_M_assign_dispatch(_InputIter __f, _InputIter __l, __false_type) +{ + pointer __cur = _M_start; + while (__f != __l && __cur != _M_finish) { + _Traits::assign(*__cur, *__f); + ++__f; + ++__cur; + } + if (__f == __l) + erase(__cur, _M_finish); + else + append(__f, __l); + return *this; +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>& +basic_string<_CharT,_Traits,_Alloc>::assign(const _CharT* __f, + const _CharT* __l) +{ + const ptrdiff_t __n = __l - __f; + if (__n <= size()) { + _Traits::copy(_M_start, __f, __n); + erase(_M_start + __n, _M_finish); + } + else { + _Traits::copy(_M_start, __f, size()); + append(__f + size(), __l); + } + return *this; +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::iterator +basic_string<_CharT,_Traits,_Alloc> + ::_M_insert_aux(basic_string<_CharT,_Traits,_Alloc>::iterator __p, + _CharT __c) +{ + iterator __new_pos = __p; + if (_M_finish + 1 < _M_end_of_storage) { + construct(_M_finish + 1); + _Traits::move(__p + 1, __p, _M_finish - __p); + _Traits::assign(*__p, __c); + ++_M_finish; + } + else { + const size_type __old_len = size(); + const size_type __len = __old_len + + max(__old_len, static_cast<size_type>(1)) + 1; + iterator __new_start = _M_allocate(__len); + iterator __new_finish = __new_start; + __STL_TRY { + __new_pos = uninitialized_copy(_M_start, __p, __new_start); + construct(__new_pos, __c); + __new_finish = __new_pos + 1; + __new_finish = uninitialized_copy(__p, _M_finish, __new_finish); + construct(__new_finish); + } + __STL_UNWIND((destroy(__new_start,__new_finish), + _M_deallocate(__new_start,__len))); + destroy(_M_start, _M_finish + 1); + _M_deallocate_block(); + _M_start = __new_start; + _M_finish = __new_finish; + _M_end_of_storage = __new_start + __len; + } + return __new_pos; +} + +template <class _CharT, class _Traits, class _Alloc> +void basic_string<_CharT,_Traits,_Alloc> + ::insert(basic_string<_CharT,_Traits,_Alloc>::iterator __position, + size_t __n, _CharT __c) +{ + if (__n != 0) { + if (size_type(_M_end_of_storage - _M_finish) >= __n + 1) { + const size_type __elems_after = _M_finish - __position; + iterator __old_finish = _M_finish; + if (__elems_after >= __n) { + uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1, + _M_finish + 1); + _M_finish += __n; + _Traits::move(__position + __n, + __position, (__elems_after - __n) + 1); + _Traits::assign(__position, __n, __c); + } + else { + uninitialized_fill_n(_M_finish + 1, __n - __elems_after - 1, __c); + _M_finish += __n - __elems_after; + __STL_TRY { + uninitialized_copy(__position, __old_finish + 1, _M_finish); + _M_finish += __elems_after; + } + __STL_UNWIND((destroy(__old_finish + 1, _M_finish), + _M_finish = __old_finish)); + _Traits::assign(__position, __elems_after + 1, __c); + } + } + else { + const size_type __old_size = size(); + const size_type __len = __old_size + max(__old_size, __n) + 1; + iterator __new_start = _M_allocate(__len); + iterator __new_finish = __new_start; + __STL_TRY { + __new_finish = uninitialized_copy(_M_start, __position, __new_start); + __new_finish = uninitialized_fill_n(__new_finish, __n, __c); + __new_finish = uninitialized_copy(__position, _M_finish, + __new_finish); + construct(__new_finish); + } + __STL_UNWIND((destroy(__new_start,__new_finish), + _M_deallocate(__new_start,__len))); + destroy(_M_start, _M_finish + 1); + _M_deallocate_block(); + _M_start = __new_start; + _M_finish = __new_finish; + _M_end_of_storage = __new_start + __len; + } + } +} + +template <class _Tp, class _Traits, class _Alloc> +template <class _InputIter> +void basic_string<_Tp, _Traits, _Alloc>::insert(iterator __p, + _InputIter __first, + _InputIter __last, + input_iterator_tag) +{ + for ( ; __first != __last; ++__first) { + __p = insert(__p, *__first); + ++__p; + } +} + +template <class _CharT, class _Traits, class _Alloc> +template <class _ForwardIter> +void +basic_string<_CharT,_Traits,_Alloc>::insert(iterator __position, + _ForwardIter __first, + _ForwardIter __last, + forward_iterator_tag) +{ + if (__first != __last) { + const difference_type __n = distance(__first, __last); + if (_M_end_of_storage - _M_finish >= __n + 1) { + const difference_type __elems_after = _M_finish - __position; + iterator __old_finish = _M_finish; + if (__elems_after >= __n) { + uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1, + _M_finish + 1); + _M_finish += __n; + _Traits::move(__position + __n, + __position, (__elems_after - __n) + 1); + _M_copy(__first, __last, __position); + } + else { + _ForwardIter __mid = __first; + advance(__mid, __elems_after + 1); + uninitialized_copy(__mid, __last, _M_finish + 1); + _M_finish += __n - __elems_after; + __STL_TRY { + uninitialized_copy(__position, __old_finish + 1, _M_finish); + _M_finish += __elems_after; + } + __STL_UNWIND((destroy(__old_finish + 1, _M_finish), + _M_finish = __old_finish)); + _M_copy(__first, __mid, __position); + } + } + else { + const size_type __old_size = size(); + const size_type __len + = __old_size + max(__old_size, static_cast<size_type>(__n)) + 1; + pointer __new_start = _M_allocate(__len); + pointer __new_finish = __new_start; + __STL_TRY { + __new_finish = uninitialized_copy(_M_start, __position, __new_start); + __new_finish = uninitialized_copy(__first, __last, __new_finish); + __new_finish + = uninitialized_copy(__position, _M_finish, __new_finish); + construct(__new_finish); + } + __STL_UNWIND((destroy(__new_start,__new_finish), + _M_deallocate(__new_start,__len))); + destroy(_M_start, _M_finish + 1); + _M_deallocate_block(); + _M_start = __new_start; + _M_finish = __new_finish; + _M_end_of_storage = __new_start + __len; + } + } +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>& +basic_string<_CharT,_Traits,_Alloc> + ::replace(iterator __first, iterator __last, size_type __n, _CharT __c) +{ + const size_type __len = static_cast<size_type>(__last - __first); + if (__len >= __n) { + _Traits::assign(__first, __n, __c); + erase(__first + __n, __last); + } + else { + _Traits::assign(__first, __len, __c); + insert(__last, __n - __len, __c); + } + return *this; +} + +template <class _CharT, class _Traits, class _Alloc> +template <class _InputIter> +basic_string<_CharT,_Traits,_Alloc>& +basic_string<_CharT,_Traits,_Alloc> + ::replace(iterator __first, iterator __last, _InputIter __f, _InputIter __l, + input_iterator_tag) +{ + for ( ; __first != __last && __f != __l; ++__first, ++__f) + _Traits::assign(*__first, *__f); + + if (__f == __l) + erase(__first, __last); + else + insert(__last, __f, __l); + return *this; +} + +template <class _CharT, class _Traits, class _Alloc> +template <class _ForwardIter> +basic_string<_CharT,_Traits,_Alloc>& +basic_string<_CharT,_Traits,_Alloc> + ::replace(iterator __first, iterator __last, + _ForwardIter __f, _ForwardIter __l, + forward_iterator_tag) +{ + const typename iterator_traits<_ForwardIter>::difference_type __n = + distance(__f, __l); + const difference_type __len = __last - __first; + if (__len >= __n) { + _M_copy(__f, __l, __first); + erase(__first + __n, __last); + } + else { + _ForwardIter m = __f; + advance(m, __len); + _M_copy(__f, m, __first); + insert(__last, m, __l); + } + return *this; +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::find(const _CharT* __s, size_type __pos, size_type __n) const +{ + if (__pos >= size()) + return npos; + else { + const const_iterator __result = + search(_M_start + __pos, _M_finish, + __s, __s + __n, _Eq_traits<_Traits>()); + return __result != _M_finish ? __result - begin() : npos; + } +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::find(_CharT __c, size_type __pos) const +{ + if (__pos >= size()) + return npos; + else { + const const_iterator __result = + find_if(_M_start + __pos, _M_finish, + bind2nd(_Eq_traits<_Traits>(), __c)); + return __result != _M_finish ? __result - begin() : npos; + } +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::rfind(const _CharT* __s, size_type __pos, size_type __n) const +{ + const size_t __len = size(); + + if (__n > __len) + return npos; + else if (__n == 0) + return min(__len, __pos); + else { + const const_iterator __last = begin() + min(__len - __n, __pos) + __n; + const const_iterator __result = find_end(begin(), __last, + __s, __s + __n, + _Eq_traits<_Traits>()); + return __result != __last ? __result - begin() : npos; + } +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::rfind(_CharT __c, size_type __pos) const +{ + const size_type __len = size(); + + if (__len < 1) + return npos; + else { + const const_iterator __last = begin() + min(__len - 1, __pos) + 1; + const_reverse_iterator __rresult = + find_if(const_reverse_iterator(__last), rend(), + bind2nd(_Eq_traits<_Traits>(), __c)); + return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos; + } +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::find_first_of(const _CharT* __s, size_type __pos, size_type __n) const +{ + if (__pos >= size()) + return npos; + else { + const const_iterator __result = std::find_first_of(begin() + __pos, end(), + __s, __s + __n, + _Eq_traits<_Traits>()); + return __result != _M_finish ? __result - begin() : npos; + } +} + + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::find_last_of(const _CharT* __s, size_type __pos, size_type __n) const +{ + const size_type __len = size(); + + if (__len < 1) + return npos; + else { + const const_iterator __last = _M_start + min(__len - 1, __pos) + 1; + const const_reverse_iterator __rresult = + std::find_first_of(const_reverse_iterator(__last), rend(), + __s, __s + __n, + _Eq_traits<_Traits>()); + return __rresult != rend() ? (__rresult.base() - 1) - _M_start : npos; + } +} + + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const +{ + if (__pos > size()) + return npos; + else { + const_iterator __result = find_if(_M_start + __pos, _M_finish, + _Not_within_traits<_Traits>(__s, __s + __n)); + return __result != _M_finish ? __result - _M_start : npos; + } +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::find_first_not_of(_CharT __c, size_type __pos) const +{ + if (__pos > size()) + return npos; + else { + const_iterator __result + = find_if(begin() + __pos, end(), + not1(bind2nd(_Eq_traits<_Traits>(), __c))); + return __result != _M_finish ? __result - begin() : npos; + } +} + +template <class _CharT, class _Traits, class _Alloc> +basic_string<_CharT,_Traits,_Alloc>::size_type +basic_string<_CharT,_Traits,_Alloc> + ::find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const +{ + + const size_type __len = size(); + + if (__len < 1) + return npos; + else { + const const_iterator __last = begin() + min(__len - 1, __pos) + 1; + const const_reverse_iterator __rresult = + find_if(const_reverse_iterator(__last), rend(), + _Not_within_traits<_Traits>(__s, __s + __n)); + return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos; + } +} + +template <class _Tp, class _Traits, class _Alloc> +basic_string<_Tp, _Traits, _Alloc>::size_type +basic_string<_Tp, _Traits, _Alloc> + ::find_last_not_of(_Tp __c, size_type __pos) const +{ + const size_type __len = size(); + + if (__len < 1) + return npos; + else { + const const_iterator __last = begin() + min(__len - 1, __pos) + 1; + const_reverse_iterator __rresult = + find_if(const_reverse_iterator(__last), rend(), + not1(bind2nd(_Eq_traits<_Traits>(), __c))); + return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos; + } +} + +// ------------------------------------------------------------ +// Non-member functions. + +// Operator+ + +template <class _CharT, class _Traits, class _Alloc> +inline basic_string<_CharT,_Traits,_Alloc> +operator+(const basic_string<_CharT,_Traits,_Alloc>& __x, + const basic_string<_CharT,_Traits,_Alloc>& __y) +{ + typedef basic_string<_CharT,_Traits,_Alloc> _Str; + typedef typename _Str::_Reserve_t _Reserve_t; + _Str __result(_Reserve_t(), __x.size() + __y.size(), __x.get_allocator()); + __result.append(__x); + __result.append(__y); + return __result; +} + +template <class _CharT, class _Traits, class _Alloc> +inline basic_string<_CharT,_Traits,_Alloc> +operator+(const _CharT* __s, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + typedef basic_string<_CharT,_Traits,_Alloc> _Str; + typedef typename _Str::_Reserve_t _Reserve_t; + const size_t __n = _Traits::length(__s); + _Str __result(_Reserve_t(), __n + __y.size()); + __result.append(__s, __s + __n); + __result.append(__y); + return __result; +} + +template <class _CharT, class _Traits, class _Alloc> +inline basic_string<_CharT,_Traits,_Alloc> +operator+(_CharT __c, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + typedef basic_string<_CharT,_Traits,_Alloc> _Str; + typedef typename _Str::_Reserve_t _Reserve_t; + _Str __result(_Reserve_t(), 1 + __y.size()); + __result.push_back(__c); + __result.append(__y); + return __result; +} + +template <class _CharT, class _Traits, class _Alloc> +inline basic_string<_CharT,_Traits,_Alloc> +operator+(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT* __s) { + typedef basic_string<_CharT,_Traits,_Alloc> _Str; + typedef typename _Str::_Reserve_t _Reserve_t; + const size_t __n = _Traits::length(__s); + _Str __result(_Reserve_t(), __x.size() + __n, __x.get_allocator()); + __result.append(__x); + __result.append(__s, __s + __n); + return __result; +} + +template <class _CharT, class _Traits, class _Alloc> +inline basic_string<_CharT,_Traits,_Alloc> +operator+(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT __c) { + typedef basic_string<_CharT,_Traits,_Alloc> _Str; + typedef typename _Str::_Reserve_t _Reserve_t; + _Str __result(_Reserve_t(), __x.size() + 1, __x.get_allocator()); + __result.append(__x); + __result.push_back(__c); + return __result; +} + +// Operator== and operator!= + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator==(const basic_string<_CharT,_Traits,_Alloc>& __x, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return __x.size() == __y.size() && + _Traits::compare(__x.data(), __y.data(), __x.size()) == 0; +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator==(const _CharT* __s, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + size_t __n = _Traits::length(__s); + return __n == __y.size() && _Traits::compare(__s, __y.data(), __n) == 0; +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator==(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT* __s) { + size_t __n = _Traits::length(__s); + return __x.size() == __n && _Traits::compare(__x.data(), __s, __n) == 0; +} + +#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return !(__x == __y); +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator!=(const _CharT* __s, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return !(__s == __y); +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT* __s) { + return !(__x == __s); +} + +#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ + +// Operator< (and also >, <=, and >=). + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator<(const basic_string<_CharT,_Traits,_Alloc>& __x, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return basic_string<_CharT,_Traits,_Alloc> + ::_M_compare(__x.begin(), __x.end(), __y.begin(), __y.end()) < 0; +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator<(const _CharT* __s, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + size_t __n = _Traits::length(__s); + return basic_string<_CharT,_Traits,_Alloc> + ::_M_compare(__s, __s + __n, __y.begin(), __y.end()) < 0; +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator<(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT* __s) { + size_t __n = _Traits::length(__s); + return basic_string<_CharT,_Traits,_Alloc> + ::_M_compare(__x.begin(), __x.end(), __s, __s + __n) < 0; +} + +#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator>(const basic_string<_CharT,_Traits,_Alloc>& __x, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return __y < __x; +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator>(const _CharT* __s, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return __y < __s; +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator>(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT* __s) { + return __s < __x; +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return !(__y < __x); +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator<=(const _CharT* __s, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return !(__y < __s); +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT* __s) { + return !(__s < __x); +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return !(__x < __y); +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator>=(const _CharT* __s, + const basic_string<_CharT,_Traits,_Alloc>& __y) { + return !(__s < __y); +} + +template <class _CharT, class _Traits, class _Alloc> +inline bool +operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x, + const _CharT* __s) { + return !(__x < __s); +} + +#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ + +// Swap. + +#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER + +template <class _CharT, class _Traits, class _Alloc> +inline void swap(basic_string<_CharT,_Traits,_Alloc>& __x, + basic_string<_CharT,_Traits,_Alloc>& __y) { + __x.swap(__y); +} + +#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ + +// I/O. (Using istream and ostream only, as opposed to the +// basic_istream and basic_ostream templates. The result is that +// these functions really don't make all that much sense except +// for basic_string<char>.) + +inline void __sgi_string_fill(ostream& __o, size_t __n) +{ + char __f = __o.fill(); + size_t __i; + + for (__i = 0; __i < __n; __i++) __o.put(__f); +} + +template <class _CharT, class _Traits, class _Alloc> +ostream& operator<<(ostream& __os, + const basic_string<_CharT,_Traits,_Alloc>& __s) +{ + size_t __n = __s.size(); + size_t __pad_len = 0; + const bool __left = bool(__os.flags() & ios::left); + const size_t __w = __os.width(); + + if (__w > 0) { + __n = min(__w, __n); + __pad_len = __w - __n; + } + + if (!__left) + __sgi_string_fill(__os, __pad_len); + + const size_t __nwritten = __os.rdbuf()->sputn(__s.data(), __n); + + if (__left) + __sgi_string_fill(__os, __pad_len); + + if (__nwritten != __n) + __os.clear(__os.rdstate() | ios::failbit); + + __os.width(0); + return __os; +} + +template <class _CharT, class _Traits, class _Alloc> +istream& operator>>(istream& __is, basic_string<_CharT,_Traits,_Alloc>& __s) +{ + + if (__is.flags() & ios::skipws) { + _CharT __c; + do + __is.get(__c); + while (__is && isspace(__c)); + if (__is) + __is.putback(__c); + } + + // If we arrive at end of file (or fail for some other reason) while + // still discarding whitespace, then we don't try to read the string. + if (__is) { + __s.clear(); + + size_t __n = __is.width(); + if (__n == 0) + __n = static_cast<size_t>(-1); + else + __s.reserve(__n); + + while (__n-- > 0) { + _CharT __c; + __is.get(__c); + if (!__is) + break; + else if (isspace(__c)) { + __is.putback(__c); + break; + } + else + __s.push_back(__c); + } + + // If we have successfully read some characters, and then arrive + // at end of file, the stream should still be marked good. Note + // that we only clear errors that are due to EOF, not other kinds + // of errors. + if (__s.size() != 0 && __is.eof()) + __is.clear((~ios::eofbit & ~ios::failbit) & __is.rdstate()); + } + + __is.width(0); + return __is; +} + +template <class _CharT, class _Traits, class _Alloc> +istream& getline(istream& __is, + basic_string<_CharT,_Traits,_Alloc>& __s, + _CharT __delim = '\n') { + size_t __nread = 0; + if (__is) { + __s.clear(); + + _CharT __c; + while (__nread < __s.max_size() && __is.get(__c)) { + ++__nread; + if (!_Traits::eq(__c, __delim)) + __s.push_back(__c); + else + break; // Character is extracted but not appended. + } + } + + if (__nread == 0 || __nread >= __s.max_size()) + __is.clear(__is.rdstate() | ios::failbit); + return __is; +} + +template <class _CharT, class _Traits, class _Alloc> +void _S_string_copy(const basic_string<_CharT,_Traits,_Alloc>& __s, + _CharT* __buf, + size_t __n) +{ + if (__n > 0) { + const size_t __n = min(__n - 1, __s.size()); + copy(__s.begin(), __s.begin() + __n, __buf); + __buf[__n] = _CharT(); + } +} + +// ------------------------------------------------------------ +// Typedefs + +typedef basic_string<char> string; +typedef basic_string<wchar_t> wstring; + + +#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) +#pragma reset woff 1174 +#pragma reset woff 1375 +#endif + +__STL_END_NAMESPACE + +#include <stl_hash_fun.h> + +__STL_BEGIN_NAMESPACE + +template <class _CharT, class _Traits, class _Alloc> +struct hash<basic_string<_CharT,_Traits,_Alloc> > { + size_t operator()(const basic_string<_CharT,_Traits,_Alloc>& __s) const { + unsigned long __h = 0; + for (basic_string<_CharT,_Traits,_Alloc>::const_iterator __i + = __s.begin(); + __i != __s.end(); + ++__i) + __h = 5*__h + *__i; + return size_t(__h); + } +}; + +__STL_END_NAMESPACE + +#endif /* __SGI_STL_STRING */ + + +// Local Variables: +// mode:C++ +// End: + |