libstdc++
sso_string_base.h
Go to the documentation of this file.
00001 // Short-string-optimized versatile string base -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file ext/sso_string_base.h
00027  *  This is an internal header file, included by other library headers.
00028  *  Do not attempt to use it directly. @headername{ext/vstring.h}
00029  */
00030 
00031 #ifndef _SSO_STRING_BASE_H
00032 #define _SSO_STRING_BASE_H 1
00033 
00034 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00035 {
00036 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00037 
00038   template<typename _CharT, typename _Traits, typename _Alloc>
00039     class __sso_string_base
00040     : protected __vstring_utility<_CharT, _Traits, _Alloc>
00041     {
00042     public:
00043       typedef _Traits                       traits_type;
00044       typedef typename _Traits::char_type           value_type;
00045 
00046       typedef __vstring_utility<_CharT, _Traits, _Alloc>    _Util_Base;
00047       typedef typename _Util_Base::_CharT_alloc_type        _CharT_alloc_type;
00048       typedef typename _CharT_alloc_type::size_type     size_type;
00049       
00050     private:
00051       // Data Members:
00052       typename _Util_Base::template _Alloc_hider<_CharT_alloc_type>
00053                                                             _M_dataplus;
00054       size_type                                             _M_string_length;
00055 
00056       enum { _S_local_capacity = 15 };
00057       
00058       union
00059       {
00060     _CharT           _M_local_data[_S_local_capacity + 1];
00061     size_type        _M_allocated_capacity;
00062       };
00063 
00064       void
00065       _M_data(_CharT* __p)
00066       { _M_dataplus._M_p = __p; }
00067 
00068       void
00069       _M_length(size_type __length)
00070       { _M_string_length = __length; }
00071 
00072       void
00073       _M_capacity(size_type __capacity)
00074       { _M_allocated_capacity = __capacity; }
00075 
00076       bool
00077       _M_is_local() const
00078       { return _M_data() == _M_local_data; }
00079 
00080       // Create & Destroy
00081       _CharT*
00082       _M_create(size_type&, size_type);
00083       
00084       void
00085       _M_dispose()
00086       {
00087     if (!_M_is_local())
00088       _M_destroy(_M_allocated_capacity);
00089       }
00090 
00091       void
00092       _M_destroy(size_type __size) throw()
00093       { _M_get_allocator().deallocate(_M_data(), __size + 1); }
00094 
00095       // _M_construct_aux is used to implement the 21.3.1 para 15 which
00096       // requires special behaviour if _InIterator is an integral type
00097       template<typename _InIterator>
00098         void
00099         _M_construct_aux(_InIterator __beg, _InIterator __end, 
00100              std::__false_type)
00101     {
00102           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
00103           _M_construct(__beg, __end, _Tag());
00104     }
00105 
00106       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00107       // 438. Ambiguity in the "do the right thing" clause
00108       template<typename _Integer>
00109         void
00110         _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
00111     { _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
00112 
00113       void
00114       _M_construct_aux_2(size_type __req, _CharT __c)
00115       { _M_construct(__req, __c); }
00116 
00117       template<typename _InIterator>
00118         void
00119         _M_construct(_InIterator __beg, _InIterator __end)
00120     {
00121       typedef typename std::__is_integer<_InIterator>::__type _Integral;
00122       _M_construct_aux(__beg, __end, _Integral());
00123         }
00124 
00125       // For Input Iterators, used in istreambuf_iterators, etc.
00126       template<typename _InIterator>
00127         void
00128         _M_construct(_InIterator __beg, _InIterator __end,
00129              std::input_iterator_tag);
00130       
00131       // For forward_iterators up to random_access_iterators, used for
00132       // string::iterator, _CharT*, etc.
00133       template<typename _FwdIterator>
00134         void
00135         _M_construct(_FwdIterator __beg, _FwdIterator __end,
00136              std::forward_iterator_tag);
00137 
00138       void
00139       _M_construct(size_type __req, _CharT __c);
00140 
00141     public:
00142       size_type
00143       _M_max_size() const
00144       { return (_M_get_allocator().max_size() - 1) / 2; }
00145 
00146       _CharT*
00147       _M_data() const
00148       { return _M_dataplus._M_p; }
00149 
00150       size_type
00151       _M_length() const
00152       { return _M_string_length; }
00153 
00154       size_type
00155       _M_capacity() const
00156       {
00157     return _M_is_local() ? size_type(_S_local_capacity)
00158                          : _M_allocated_capacity; 
00159       }
00160 
00161       bool
00162       _M_is_shared() const
00163       { return false; }
00164 
00165       void
00166       _M_set_leaked() { }
00167 
00168       void
00169       _M_leak() { }
00170 
00171       void
00172       _M_set_length(size_type __n)
00173       {
00174     _M_length(__n);
00175     traits_type::assign(_M_data()[__n], _CharT());
00176       }
00177 
00178       __sso_string_base()
00179       : _M_dataplus(_M_local_data)
00180       { _M_set_length(0); }
00181 
00182       __sso_string_base(const _Alloc& __a);
00183 
00184       __sso_string_base(const __sso_string_base& __rcs);
00185 
00186 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00187       __sso_string_base(__sso_string_base&& __rcs);
00188 #endif
00189 
00190       __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
00191 
00192       template<typename _InputIterator>
00193         __sso_string_base(_InputIterator __beg, _InputIterator __end,
00194               const _Alloc& __a);
00195 
00196       ~__sso_string_base()
00197       { _M_dispose(); }
00198 
00199       _CharT_alloc_type&
00200       _M_get_allocator()
00201       { return _M_dataplus; }
00202 
00203       const _CharT_alloc_type&
00204       _M_get_allocator() const
00205       { return _M_dataplus; }
00206 
00207       void
00208       _M_swap(__sso_string_base& __rcs);
00209 
00210       void
00211       _M_assign(const __sso_string_base& __rcs);
00212 
00213       void
00214       _M_reserve(size_type __res);
00215 
00216       void
00217       _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00218         size_type __len2);
00219 
00220       void
00221       _M_erase(size_type __pos, size_type __n);
00222 
00223       void
00224       _M_clear()
00225       { _M_set_length(0); }
00226 
00227       bool
00228       _M_compare(const __sso_string_base&) const
00229       { return false; }
00230     };
00231 
00232   template<typename _CharT, typename _Traits, typename _Alloc>
00233     void
00234     __sso_string_base<_CharT, _Traits, _Alloc>::
00235     _M_swap(__sso_string_base& __rcs)
00236     {
00237       if (this == &__rcs)
00238     return;
00239 
00240       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00241       // 431. Swapping containers with unequal allocators.
00242       std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(),
00243                              __rcs._M_get_allocator());
00244 
00245       if (_M_is_local())
00246     if (__rcs._M_is_local())
00247       {
00248         if (_M_length() && __rcs._M_length())
00249           {
00250         _CharT __tmp_data[_S_local_capacity + 1];
00251         traits_type::copy(__tmp_data, __rcs._M_local_data,
00252                   _S_local_capacity + 1);
00253         traits_type::copy(__rcs._M_local_data, _M_local_data,
00254                   _S_local_capacity + 1);
00255         traits_type::copy(_M_local_data, __tmp_data,
00256                   _S_local_capacity + 1);
00257           }
00258         else if (__rcs._M_length())
00259           {
00260         traits_type::copy(_M_local_data, __rcs._M_local_data,
00261                   _S_local_capacity + 1);
00262         _M_length(__rcs._M_length());
00263         __rcs._M_set_length(0);
00264         return;
00265           }
00266         else if (_M_length())
00267           {
00268         traits_type::copy(__rcs._M_local_data, _M_local_data,
00269                   _S_local_capacity + 1);
00270         __rcs._M_length(_M_length());
00271         _M_set_length(0);
00272         return;
00273           }
00274       }
00275     else
00276       {
00277         const size_type __tmp_capacity = __rcs._M_allocated_capacity;
00278         traits_type::copy(__rcs._M_local_data, _M_local_data,
00279                   _S_local_capacity + 1);
00280         _M_data(__rcs._M_data());
00281         __rcs._M_data(__rcs._M_local_data);
00282         _M_capacity(__tmp_capacity);
00283       }
00284       else
00285     {
00286       const size_type __tmp_capacity = _M_allocated_capacity;
00287       if (__rcs._M_is_local())
00288         {
00289           traits_type::copy(_M_local_data, __rcs._M_local_data,
00290                 _S_local_capacity + 1);
00291           __rcs._M_data(_M_data());
00292           _M_data(_M_local_data);
00293         }
00294       else
00295         {
00296           _CharT* __tmp_ptr = _M_data();
00297           _M_data(__rcs._M_data());
00298           __rcs._M_data(__tmp_ptr);
00299           _M_capacity(__rcs._M_allocated_capacity);
00300         }
00301       __rcs._M_capacity(__tmp_capacity);
00302     }
00303 
00304       const size_type __tmp_length = _M_length();
00305       _M_length(__rcs._M_length());
00306       __rcs._M_length(__tmp_length);
00307     }
00308 
00309   template<typename _CharT, typename _Traits, typename _Alloc>
00310     _CharT*
00311     __sso_string_base<_CharT, _Traits, _Alloc>::
00312     _M_create(size_type& __capacity, size_type __old_capacity)
00313     {
00314       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00315       // 83.  String::npos vs. string::max_size()
00316       if (__capacity > _M_max_size())
00317     std::__throw_length_error(__N("__sso_string_base::_M_create"));
00318 
00319       // The below implements an exponential growth policy, necessary to
00320       // meet amortized linear time requirements of the library: see
00321       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
00322       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
00323     {
00324       __capacity = 2 * __old_capacity;
00325       // Never allocate a string bigger than max_size.
00326       if (__capacity > _M_max_size())
00327         __capacity = _M_max_size();
00328     }
00329 
00330       // NB: Need an array of char_type[__capacity], plus a terminating
00331       // null char_type() element.
00332       return _M_get_allocator().allocate(__capacity + 1);
00333     }
00334 
00335   template<typename _CharT, typename _Traits, typename _Alloc>
00336     __sso_string_base<_CharT, _Traits, _Alloc>::
00337     __sso_string_base(const _Alloc& __a)
00338     : _M_dataplus(__a, _M_local_data)
00339     { _M_set_length(0); }
00340 
00341   template<typename _CharT, typename _Traits, typename _Alloc>
00342     __sso_string_base<_CharT, _Traits, _Alloc>::
00343     __sso_string_base(const __sso_string_base& __rcs)
00344     : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
00345     { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
00346 
00347 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00348   template<typename _CharT, typename _Traits, typename _Alloc>
00349     __sso_string_base<_CharT, _Traits, _Alloc>::
00350     __sso_string_base(__sso_string_base&& __rcs)
00351     : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
00352     {
00353       if (__rcs._M_is_local())
00354     {
00355       if (__rcs._M_length())
00356         traits_type::copy(_M_local_data, __rcs._M_local_data,
00357                   _S_local_capacity + 1);
00358     }
00359       else
00360     {
00361       _M_data(__rcs._M_data());
00362       _M_capacity(__rcs._M_allocated_capacity);
00363     }
00364 
00365       _M_length(__rcs._M_length());
00366       __rcs._M_length(0);
00367       __rcs._M_data(__rcs._M_local_data);
00368     }
00369 #endif
00370 
00371   template<typename _CharT, typename _Traits, typename _Alloc>
00372     __sso_string_base<_CharT, _Traits, _Alloc>::
00373     __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
00374     : _M_dataplus(__a, _M_local_data)
00375     { _M_construct(__n, __c); }
00376 
00377   template<typename _CharT, typename _Traits, typename _Alloc>
00378     template<typename _InputIterator>
00379     __sso_string_base<_CharT, _Traits, _Alloc>::
00380     __sso_string_base(_InputIterator __beg, _InputIterator __end,
00381               const _Alloc& __a)
00382     : _M_dataplus(__a, _M_local_data)
00383     { _M_construct(__beg, __end); }
00384 
00385   // NB: This is the special case for Input Iterators, used in
00386   // istreambuf_iterators, etc.
00387   // Input Iterators have a cost structure very different from
00388   // pointers, calling for a different coding style.
00389   template<typename _CharT, typename _Traits, typename _Alloc>
00390     template<typename _InIterator>
00391       void
00392       __sso_string_base<_CharT, _Traits, _Alloc>::
00393       _M_construct(_InIterator __beg, _InIterator __end,
00394            std::input_iterator_tag)
00395       {
00396     size_type __len = 0;
00397     size_type __capacity = size_type(_S_local_capacity);
00398 
00399     while (__beg != __end && __len < __capacity)
00400       {
00401         _M_data()[__len++] = *__beg;
00402         ++__beg;
00403       }
00404     
00405     __try
00406       {
00407         while (__beg != __end)
00408           {
00409         if (__len == __capacity)
00410           {
00411             // Allocate more space.
00412             __capacity = __len + 1;
00413             _CharT* __another = _M_create(__capacity, __len);
00414             this->_S_copy(__another, _M_data(), __len);
00415             _M_dispose();
00416             _M_data(__another);
00417             _M_capacity(__capacity);
00418           }
00419         _M_data()[__len++] = *__beg;
00420         ++__beg;
00421           }
00422       }
00423     __catch(...)
00424       {
00425         _M_dispose();
00426         __throw_exception_again;
00427       }
00428 
00429     _M_set_length(__len);
00430       }
00431 
00432   template<typename _CharT, typename _Traits, typename _Alloc>
00433     template<typename _InIterator>
00434       void
00435       __sso_string_base<_CharT, _Traits, _Alloc>::
00436       _M_construct(_InIterator __beg, _InIterator __end,
00437            std::forward_iterator_tag)
00438       {
00439     // NB: Not required, but considered best practice.
00440     if (__is_null_pointer(__beg) && __beg != __end)
00441       std::__throw_logic_error(__N("__sso_string_base::"
00442                        "_M_construct null not valid"));
00443 
00444     size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
00445 
00446     if (__dnew > size_type(_S_local_capacity))
00447       {
00448         _M_data(_M_create(__dnew, size_type(0)));
00449         _M_capacity(__dnew);
00450       }
00451 
00452     // Check for out_of_range and length_error exceptions.
00453     __try
00454       { this->_S_copy_chars(_M_data(), __beg, __end); }
00455     __catch(...)
00456       {
00457         _M_dispose();
00458         __throw_exception_again;
00459       }
00460 
00461     _M_set_length(__dnew);
00462       }
00463 
00464   template<typename _CharT, typename _Traits, typename _Alloc>
00465     void
00466     __sso_string_base<_CharT, _Traits, _Alloc>::
00467     _M_construct(size_type __n, _CharT __c)
00468     {
00469       if (__n > size_type(_S_local_capacity))
00470     {
00471       _M_data(_M_create(__n, size_type(0)));
00472       _M_capacity(__n);
00473     }
00474 
00475       if (__n)
00476     this->_S_assign(_M_data(), __n, __c);
00477 
00478       _M_set_length(__n);
00479     }
00480 
00481   template<typename _CharT, typename _Traits, typename _Alloc>
00482     void
00483     __sso_string_base<_CharT, _Traits, _Alloc>::
00484     _M_assign(const __sso_string_base& __rcs)
00485     {
00486       if (this != &__rcs)
00487     {
00488       const size_type __rsize = __rcs._M_length();
00489       const size_type __capacity = _M_capacity();
00490 
00491       if (__rsize > __capacity)
00492         {
00493           size_type __new_capacity = __rsize;
00494           _CharT* __tmp = _M_create(__new_capacity, __capacity);
00495           _M_dispose();
00496           _M_data(__tmp);
00497           _M_capacity(__new_capacity);
00498         }
00499 
00500       if (__rsize)
00501         this->_S_copy(_M_data(), __rcs._M_data(), __rsize);
00502 
00503       _M_set_length(__rsize);
00504     }
00505     }
00506 
00507   template<typename _CharT, typename _Traits, typename _Alloc>
00508     void
00509     __sso_string_base<_CharT, _Traits, _Alloc>::
00510     _M_reserve(size_type __res)
00511     {
00512       // Make sure we don't shrink below the current size.
00513       if (__res < _M_length())
00514     __res = _M_length();
00515 
00516       const size_type __capacity = _M_capacity();
00517       if (__res != __capacity)
00518     {
00519       if (__res > __capacity
00520           || __res > size_type(_S_local_capacity))
00521         {
00522           _CharT* __tmp = _M_create(__res, __capacity);
00523           this->_S_copy(__tmp, _M_data(), _M_length() + 1);
00524           _M_dispose();
00525           _M_data(__tmp);
00526           _M_capacity(__res);
00527         }
00528       else if (!_M_is_local())
00529         {
00530           this->_S_copy(_M_local_data, _M_data(), _M_length() + 1);
00531           _M_destroy(__capacity);
00532           _M_data(_M_local_data);
00533         }
00534     }
00535     }
00536 
00537   template<typename _CharT, typename _Traits, typename _Alloc>
00538     void
00539     __sso_string_base<_CharT, _Traits, _Alloc>::
00540     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00541           size_type __len2)
00542     {
00543       const size_type __how_much = _M_length() - __pos - __len1;
00544       
00545       size_type __new_capacity = _M_length() + __len2 - __len1;
00546       _CharT* __r = _M_create(__new_capacity, _M_capacity());
00547 
00548       if (__pos)
00549     this->_S_copy(__r, _M_data(), __pos);
00550       if (__s && __len2)
00551     this->_S_copy(__r + __pos, __s, __len2);
00552       if (__how_much)
00553     this->_S_copy(__r + __pos + __len2,
00554               _M_data() + __pos + __len1, __how_much);
00555       
00556       _M_dispose();
00557       _M_data(__r);
00558       _M_capacity(__new_capacity);
00559     }
00560 
00561   template<typename _CharT, typename _Traits, typename _Alloc>
00562     void
00563     __sso_string_base<_CharT, _Traits, _Alloc>::
00564     _M_erase(size_type __pos, size_type __n)
00565     {
00566       const size_type __how_much = _M_length() - __pos - __n;
00567 
00568       if (__how_much && __n)
00569     this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
00570 
00571       _M_set_length(_M_length() - __n);
00572     }
00573 
00574 _GLIBCXX_END_NAMESPACE_VERSION
00575 } // namespace
00576 
00577 #endif /* _SSO_STRING_BASE_H */