libstdc++-v3/include/ext/sso_string_base.h

   1 // Short-string-optimized versatile string base -*- C++ -*-
   2
   3 // Copyright (C) 2005 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file ext/sso_string_base.h
  31  *  This file is a GNU extension to the Standard C++ Library.
  32  *  This is an internal header file, included by other library headers.
  33  *  You should not attempt to use it directly.
  34  */
  35
  36 #ifndef _SSO_STRING_BASE_H
  37 #define _SSO_STRING_BASE_H 1
  38
  39 namespace __gnu_cxx
  40 {
  41   template<typename _CharT, typename _Traits, typename _Alloc>
  42     class __sso_string_base
  43     : protected __vstring_utility<_CharT, _Traits, _Alloc>
  44     {
  45     public:
  46       typedef _Traits                                       traits_type;
  47       typedef typename _Traits::char_type                   value_type;
  48       typedef _Alloc                                        allocator_type;
  49
  50       typedef __vstring_utility<_CharT, _Traits, _Alloc>    _Util_Base;
  51       typedef typename _Util_Base::_CharT_alloc_type        _CharT_alloc_type;
  52       typedef typename _CharT_alloc_type::size_type         size_type;
  53
  54     private:
  55       // The maximum number of individual char_type elements of an
  56       // individual string is determined by _S_max_size. This is the
  57       // value that will be returned by max_size().  (Whereas npos
  58       // is the maximum number of bytes the allocator can allocate.)
  59       // If one was to divvy up the theoretical largest size string,
  60       // with a terminating character and m _CharT elements, it'd
  61       // look like this:
  62       // npos = m * sizeof(_CharT) + sizeof(_CharT)
  63       // Solving for m:
  64       // m = npos / sizeof(_CharT) - 1
  65       // In addition, this implementation quarters this amount.
  66       enum { _S_max_size = (((static_cast<size_type>(-1)
  67                               / sizeof(_CharT)) - 1) / 4) };
  68
  69       // Data Members (private):
  70       typename _Util_Base::template _Alloc_hider<_Alloc>    _M_dataplus;
  71       size_type                                             _M_string_length;
  72
  73       enum { _S_local_capacity = 15 };
  74
  75       union
  76       {
  77         _CharT           _M_local_data[_S_local_capacity + 1];
  78         size_type        _M_allocated_capacity;
  79       };
  80
  81       void
  82       _M_data(_CharT* __p)
  83       { _M_dataplus._M_p = __p; }
  84
  85       void
  86       _M_length(size_type __length)
  87       { _M_string_length = __length; }
  88
  89       void
  90       _M_capacity(size_type __capacity)
  91       { _M_allocated_capacity = __capacity; }
  92
  93       bool
  94       _M_is_local() const
  95       { return _M_data() == _M_local_data; }
  96
  97       // Create & Destroy
  98       _CharT*
  99       _M_create(size_type&, size_type);
 100
 101       void
 102       _M_dispose()
 103       {
 104         if (!_M_is_local())
 105           _M_destroy(_M_allocated_capacity);
 106       }
 107
 108       void
 109       _M_destroy(size_type) throw();
 110
 111       // _M_construct_aux is used to implement the 21.3.1 para 15 which
 112       // requires special behaviour if _InIterator is an integral type
 113       template<typename _InIterator>
 114         void
 115         _M_construct_aux(_InIterator __beg, _InIterator __end, __false_type)
 116         {
 117           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
 118           _M_construct(__beg, __end, _Tag());
 119         }
 120
 121       template<typename _InIterator>
 122         void
 123         _M_construct_aux(_InIterator __beg, _InIterator __end, __true_type)
 124         { _M_construct(static_cast<size_type>(__beg),
 125                        static_cast<value_type>(__end)); }
 126
 127       template<typename _InIterator>
 128         void
 129         _M_construct(_InIterator __beg, _InIterator __end)
 130         {
 131           typedef typename std::__is_integer<_InIterator>::__type _Integral;
 132           _M_construct_aux(__beg, __end, _Integral());
 133         }
 134
 135       // For Input Iterators, used in istreambuf_iterators, etc.
 136       template<typename _InIterator>
 137         void
 138         _M_construct(_InIterator __beg, _InIterator __end,
 139                      std::input_iterator_tag);
 140
 141       // For forward_iterators up to random_access_iterators, used for
 142       // string::iterator, _CharT*, etc.
 143       template<typename _FwdIterator>
 144         void
 145         _M_construct(_FwdIterator __beg, _FwdIterator __end,
 146                      std::forward_iterator_tag);
 147
 148       void
 149       _M_construct(size_type __req, _CharT __c);
 150
 151     public:
 152       size_type
 153       _M_max_size() const
 154       { return size_type(_S_max_size); }
 155
 156       _CharT*
 157       _M_data() const
 158       { return _M_dataplus._M_p; }
 159
 160       size_type
 161       _M_length() const
 162       { return _M_string_length; }
 163
 164       size_type
 165       _M_capacity() const
 166       {
 167         return _M_is_local() ? size_type(_S_local_capacity)
 168                              : _M_allocated_capacity;
 169       }
 170
 171       bool
 172       _M_is_shared() const
 173       { return false; }
 174
 175       void
 176       _M_set_leaked() { }
 177
 178       void
 179       _M_leak() { }
 180
 181       void
 182       _M_set_length(size_type __n)
 183       {
 184         _M_length(__n);
 185         traits_type::assign(_M_data()[__n], _CharT());
 186       }
 187
 188       __sso_string_base()
 189       : _M_dataplus(_Alloc(), _M_local_data)
 190       { _M_set_length(0); }
 191
 192       __sso_string_base(const _Alloc& __a);
 193
 194       __sso_string_base(const __sso_string_base& __rcs);
 195
 196       __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
 197
 198       template<typename _InputIterator>
 199         __sso_string_base(_InputIterator __beg, _InputIterator __end,
 200                           const _Alloc& __a);
 201
 202       ~__sso_string_base()
 203       { _M_dispose(); }
 204
 205       allocator_type&
 206       _M_get_allocator()
 207       { return _M_dataplus; }
 208
 209       const allocator_type&
 210       _M_get_allocator() const
 211       { return _M_dataplus; }
 212
 213       void
 214       _M_swap(__sso_string_base& __rcs);
 215
 216       void
 217       _M_assign(const __sso_string_base& __rcs);
 218
 219       void
 220       _M_reserve(size_type __res);
 221
 222       void
 223       _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
 224                 size_type __len2);
 225
 226       void
 227       _M_erase(size_type __pos, size_type __n);
 228
 229       bool
 230       _M_compare(const __sso_string_base&) const
 231       { return false; }
 232     };
 233
 234   template<typename _CharT, typename _Traits, typename _Alloc>
 235     void
 236     __sso_string_base<_CharT, _Traits, _Alloc>::
 237     _M_destroy(size_type __size) throw()
 238     { _CharT_alloc_type(_M_get_allocator()).deallocate(_M_data(), __size + 1); }
 239
 240   template<typename _CharT, typename _Traits, typename _Alloc>
 241     void
 242     __sso_string_base<_CharT, _Traits, _Alloc>::
 243     _M_swap(__sso_string_base& __rcs)
 244     {
 245       // NB: Implement Option 3 of DR 431 (see N1599).
 246       _M_dataplus._M_alloc_swap(__rcs._M_dataplus);
 247
 248       if (_M_is_local())
 249         if (__rcs._M_is_local())
 250           {
 251             if (_M_length() && __rcs._M_length())
 252               {
 253                 _CharT __tmp_data[_S_local_capacity + 1];
 254                 traits_type::copy(__tmp_data, __rcs._M_local_data,
 255                                   _S_local_capacity + 1);
 256                 traits_type::copy(__rcs._M_local_data, _M_local_data,
 257                                   _S_local_capacity + 1);
 258                 traits_type::copy(_M_local_data, __tmp_data,
 259                                   _S_local_capacity + 1);
 260               }
 261             else if (__rcs._M_length())
 262               {
 263                 traits_type::copy(_M_local_data, __rcs._M_local_data,
 264                                   _S_local_capacity + 1);
 265                 _M_length(__rcs._M_length());
 266                 __rcs._M_set_length(0);
 267                 return;
 268               }
 269             else if (_M_length())
 270               {
 271                 traits_type::copy(__rcs._M_local_data, _M_local_data,
 272                                   _S_local_capacity + 1);
 273                 __rcs._M_length(_M_length());
 274                 _M_set_length(0);
 275                 return;
 276               }
 277           }
 278         else
 279           {
 280             const size_type __tmp_capacity = __rcs._M_allocated_capacity;
 281             traits_type::copy(__rcs._M_local_data, _M_local_data,
 282                               _S_local_capacity + 1);
 283             _M_data(__rcs._M_data());
 284             __rcs._M_data(__rcs._M_local_data);
 285             _M_capacity(__tmp_capacity);
 286           }
 287       else
 288         {
 289           const size_type __tmp_capacity = _M_allocated_capacity;
 290           if (__rcs._M_is_local())
 291             {
 292               traits_type::copy(_M_local_data, __rcs._M_local_data,
 293                                 _S_local_capacity + 1);
 294               __rcs._M_data(_M_data());
 295               _M_data(_M_local_data);
 296             }
 297           else
 298             {
 299               _CharT* __tmp_ptr = _M_data();
 300               _M_data(__rcs._M_data());
 301               __rcs._M_data(__tmp_ptr);
 302               _M_capacity(__rcs._M_allocated_capacity);
 303             }
 304           __rcs._M_capacity(__tmp_capacity);
 305         }
 306
 307       const size_type __tmp_length = _M_length();
 308       _M_length(__rcs._M_length());
 309       __rcs._M_length(__tmp_length);
 310     }
 311
 312   template<typename _CharT, typename _Traits, typename _Alloc>
 313     _CharT*
 314     __sso_string_base<_CharT, _Traits, _Alloc>::
 315     _M_create(size_type& __capacity, size_type __old_capacity)
 316     {
 317       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 318       // 83.  String::npos vs. string::max_size()
 319       if (__capacity > size_type(_S_max_size))
 320         std::__throw_length_error(__N("__sso_string_base::_M_create"));
 321
 322       // The below implements an exponential growth policy, necessary to
 323       // meet amortized linear time requirements of the library: see
 324       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 325       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
 326         __capacity = 2 * __old_capacity;
 327
 328       // NB: Need an array of char_type[__capacity], plus a terminating
 329       // null char_type() element.
 330       return _CharT_alloc_type(_M_get_allocator()).allocate(__capacity + 1);
 331     }
 332
 333   template<typename _CharT, typename _Traits, typename _Alloc>
 334     __sso_string_base<_CharT, _Traits, _Alloc>::
 335     __sso_string_base(const _Alloc& __a)
 336     : _M_dataplus(__a, _M_local_data)
 337     { _M_set_length(0); }
 338
 339   template<typename _CharT, typename _Traits, typename _Alloc>
 340     __sso_string_base<_CharT, _Traits, _Alloc>::
 341     __sso_string_base(const __sso_string_base& __rcs)
 342     : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
 343     { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
 344
 345   template<typename _CharT, typename _Traits, typename _Alloc>
 346     __sso_string_base<_CharT, _Traits, _Alloc>::
 347     __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
 348     : _M_dataplus(__a, _M_local_data)
 349     { _M_construct(__n, __c); }
 350
 351   template<typename _CharT, typename _Traits, typename _Alloc>
 352     template<typename _InputIterator>
 353     __sso_string_base<_CharT, _Traits, _Alloc>::
 354     __sso_string_base(_InputIterator __beg, _InputIterator __end,
 355                       const _Alloc& __a)
 356     : _M_dataplus(__a, _M_local_data)
 357     { _M_construct(__beg, __end); }
 358
 359   // NB: This is the special case for Input Iterators, used in
 360   // istreambuf_iterators, etc.
 361   // Input Iterators have a cost structure very different from
 362   // pointers, calling for a different coding style.
 363   template<typename _CharT, typename _Traits, typename _Alloc>
 364     template<typename _InIterator>
 365       void
 366       __sso_string_base<_CharT, _Traits, _Alloc>::
 367       _M_construct(_InIterator __beg, _InIterator __end,
 368                    std::input_iterator_tag)
 369       {
 370         size_type __len = 0;
 371         size_type __capacity = size_type(_S_local_capacity);
 372
 373         while (__beg != __end && __len < __capacity)
 374           {
 375             _M_data()[__len++] = *__beg;
 376             ++__beg;
 377           }
 378
 379         try
 380           {
 381             while (__beg != __end)
 382               {
 383                 if (__len == __capacity)
 384                   {
 385                     // Allocate more space.
 386                     __capacity = __len + 1;
 387                     _CharT* __another = _M_create(__capacity, __len);
 388                     _S_copy(__another, _M_data(), __len);
 389                     _M_dispose();
 390                     _M_data(__another);
 391                     _M_capacity(__capacity);
 392                   }
 393                 _M_data()[__len++] = *__beg;
 394                 ++__beg;
 395               }
 396           }
 397         catch(...)
 398           {
 399             _M_dispose();
 400             __throw_exception_again;
 401           }
 402
 403         _M_set_length(__len);
 404       }
 405
 406   template<typename _CharT, typename _Traits, typename _Alloc>
 407     template<typename _InIterator>
 408       void
 409       __sso_string_base<_CharT, _Traits, _Alloc>::
 410       _M_construct(_InIterator __beg, _InIterator __end,
 411                    std::forward_iterator_tag)
 412       {
 413         // NB: Not required, but considered best practice.
 414         if (__builtin_expect(_S_is_null_pointer(__beg) && __beg != __end, 0))
 415           std::__throw_logic_error(__N("__sso_string_base::"
 416                                        "_M_construct NULL not valid"));
 417
 418         size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
 419
 420         if (__dnew > size_type(_S_local_capacity))
 421           {
 422             _M_data(_M_create(__dnew, size_type(0)));
 423             _M_capacity(__dnew);
 424           }
 425
 426         // Check for out_of_range and length_error exceptions.
 427         try
 428           { _S_copy_chars(_M_data(), __beg, __end); }
 429         catch(...)
 430           {
 431             _M_dispose();
 432             __throw_exception_again;
 433           }
 434
 435         _M_set_length(__dnew);
 436       }
 437
 438   template<typename _CharT, typename _Traits, typename _Alloc>
 439     void
 440     __sso_string_base<_CharT, _Traits, _Alloc>::
 441     _M_construct(size_type __n, _CharT __c)
 442     {
 443       if (__n > size_type(_S_local_capacity))
 444         {
 445           _M_data(_M_create(__n, size_type(0)));
 446           _M_capacity(__n);
 447         }
 448
 449       if (__n)
 450         _S_assign(_M_data(), __n, __c);
 451
 452       _M_set_length(__n);
 453     }
 454
 455   template<typename _CharT, typename _Traits, typename _Alloc>
 456     void
 457     __sso_string_base<_CharT, _Traits, _Alloc>::
 458     _M_assign(const __sso_string_base& __rcs)
 459     {
 460       if (this != &__rcs)
 461         {
 462           const size_type __rsize = __rcs._M_length();
 463           const size_type __capacity = _M_capacity();
 464
 465           if (__rsize > __capacity)
 466             {
 467               size_type __new_capacity = __rsize;
 468               _CharT* __tmp = _M_create(__new_capacity, __capacity);
 469               _M_dispose();
 470               _M_data(__tmp);
 471               _M_capacity(__new_capacity);
 472             }
 473
 474           if (__rsize)
 475             _S_copy(_M_data(), __rcs._M_data(), __rsize);
 476
 477           _M_set_length(__rsize);
 478         }
 479     }
 480
 481   template<typename _CharT, typename _Traits, typename _Alloc>
 482     void
 483     __sso_string_base<_CharT, _Traits, _Alloc>::
 484     _M_reserve(size_type __res)
 485     {
 486       // Make sure we don't shrink below the current size.
 487       if (__res < _M_length())
 488         __res = _M_length();
 489
 490       const size_type __capacity = _M_capacity();
 491       if (__res != __capacity)
 492         {
 493           if (__res > __capacity
 494               || __res > size_type(_S_local_capacity))
 495             {
 496               _CharT* __tmp = _M_create(__res, __capacity);
 497               _S_copy(__tmp, _M_data(), _M_length() + 1);
 498               _M_dispose();
 499               _M_data(__tmp);
 500               _M_capacity(__res);
 501             }
 502           else if (!_M_is_local())
 503             {
 504               _S_copy(_M_local_data, _M_data(), _M_length() + 1);
 505               _M_destroy(__capacity);
 506               _M_data(_M_local_data);
 507             }
 508         }
 509     }
 510
 511   template<typename _CharT, typename _Traits, typename _Alloc>
 512     void
 513     __sso_string_base<_CharT, _Traits, _Alloc>::
 514     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
 515               const size_type __len2)
 516     {
 517       const size_type __how_much = _M_length() - __pos - __len1;
 518
 519       size_type __new_capacity = _M_length() + __len2 - __len1;
 520       _CharT* __r = _M_create(__new_capacity, _M_capacity());
 521
 522       if (__pos)
 523         _S_copy(__r, _M_data(), __pos);
 524       if (__s && __len2)
 525         _S_copy(__r + __pos, __s, __len2);
 526       if (__how_much)
 527         _S_copy(__r + __pos + __len2,
 528                 _M_data() + __pos + __len1, __how_much);
 529
 530       _M_dispose();
 531       _M_data(__r);
 532       _M_capacity(__new_capacity);
 533     }
 534
 535   template<typename _CharT, typename _Traits, typename _Alloc>
 536     void
 537     __sso_string_base<_CharT, _Traits, _Alloc>::
 538     _M_erase(size_type __pos, size_type __n)
 539     {
 540       const size_type __how_much = _M_length() - __pos - __n;
 541
 542       if (__how_much && __n)
 543         _S_move(_M_data() + __pos, _M_data() + __pos + __n,
 544                 __how_much);
 545
 546       _M_set_length(_M_length() - __n);
 547     }
 548
 549   template<>
 550     inline bool
 551     __sso_string_base<char, std::char_traits<char>,
 552                       std::allocator<char> >::
 553     _M_compare(const __sso_string_base& __rcs) const
 554     {
 555       if (this == &__rcs)
 556         return true;
 557       return false;
 558     }
 559
 560   template<>
 561     inline bool
 562     __sso_string_base<wchar_t, std::char_traits<wchar_t>,
 563                       std::allocator<wchar_t> >::
 564     _M_compare(const __sso_string_base& __rcs) const
 565     {
 566       if (this == &__rcs)
 567         return true;
 568       return false;
 569     }
 570 } // namespace __gnu_cxx
 571
 572 #endif /* _SSO_STRING_BASE_H */