1// Short-string-optimized versatile string base -*- C++ -*-
2
3// Copyright (C) 2005-2022 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 3, 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// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file ext/sso_string_base.h
26 *  This is an internal header file, included by other library headers.
27 *  Do not attempt to use it directly. @headername{ext/vstring.h}
28 */
29
30#ifndef _SSO_STRING_BASE_H
31#define _SSO_STRING_BASE_H 1
32
33namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
34{
35_GLIBCXX_BEGIN_NAMESPACE_VERSION
36
37  template<typename _CharT, typename _Traits, typename _Alloc>
38    class __sso_string_base
39    : protected __vstring_utility<_CharT, _Traits, _Alloc>
40    {
41    public:
42      typedef _Traits					    traits_type;
43      typedef typename _Traits::char_type		    value_type;
44
45      typedef __vstring_utility<_CharT, _Traits, _Alloc>    _Util_Base;
46      typedef typename _Util_Base::_CharT_alloc_type        _CharT_alloc_type;
47      typedef typename _CharT_alloc_type::size_type	    size_type;
48
49    private:
50      // Data Members:
51      typename _Util_Base::template _Alloc_hider<_CharT_alloc_type>
52                                                            _M_dataplus;
53      size_type                                             _M_string_length;
54
55      enum { _S_local_capacity = 15 };
56
57      union
58      {
59	_CharT           _M_local_data[_S_local_capacity + 1];
60	size_type        _M_allocated_capacity;
61      };
62
63      void
64      _M_data(_CharT* __p)
65      { _M_dataplus._M_p = __p; }
66
67      void
68      _M_length(size_type __length)
69      { _M_string_length = __length; }
70
71      void
72      _M_capacity(size_type __capacity)
73      { _M_allocated_capacity = __capacity; }
74
75      bool
76      _M_is_local() const
77      { return _M_data() == _M_local_data; }
78
79      // Create & Destroy
80      _CharT*
81      _M_create(size_type&, size_type);
82
83      void
84      _M_dispose()
85      {
86	if (!_M_is_local())
87	  _M_destroy(_M_allocated_capacity);
88      }
89
90      void
91      _M_destroy(size_type __size) throw()
92      { _M_get_allocator().deallocate(_M_data(), __size + 1); }
93
94      // _M_construct_aux is used to implement the 21.3.1 para 15 which
95      // requires special behaviour if _InIterator is an integral type
96      template<typename _InIterator>
97        void
98        _M_construct_aux(_InIterator __beg, _InIterator __end,
99			 std::__false_type)
100	{
101          typedef typename std::iterator_traits<_InIterator>::iterator_category
102	    _Tag;
103          _M_construct(__beg, __end, _Tag());
104	}
105
106      // _GLIBCXX_RESOLVE_LIB_DEFECTS
107      // 438. Ambiguity in the "do the right thing" clause
108      template<typename _Integer>
109        void
110        _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
111	{ _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
112
113      void
114      _M_construct_aux_2(size_type __req, _CharT __c)
115      { _M_construct(__req, __c); }
116
117      template<typename _InIterator>
118        void
119        _M_construct(_InIterator __beg, _InIterator __end)
120	{
121	  typedef typename std::__is_integer<_InIterator>::__type _Integral;
122	  _M_construct_aux(__beg, __end, _Integral());
123        }
124
125      // For Input Iterators, used in istreambuf_iterators, etc.
126      template<typename _InIterator>
127        void
128        _M_construct(_InIterator __beg, _InIterator __end,
129		     std::input_iterator_tag);
130
131      // For forward_iterators up to random_access_iterators, used for
132      // string::iterator, _CharT*, etc.
133      template<typename _FwdIterator>
134        void
135        _M_construct(_FwdIterator __beg, _FwdIterator __end,
136		     std::forward_iterator_tag);
137
138      void
139      _M_construct(size_type __req, _CharT __c);
140
141    public:
142      size_type
143      _M_max_size() const
144      {
145	typedef __alloc_traits<_CharT_alloc_type> _ATraits;
146	return (_ATraits::max_size(_M_get_allocator()) - 1) / 2;
147      }
148
149      _CharT*
150      _M_data() const
151      { return _M_dataplus._M_p; }
152
153      size_type
154      _M_length() const
155      { return _M_string_length; }
156
157      size_type
158      _M_capacity() const
159      {
160	return _M_is_local() ? size_type(_S_local_capacity)
161	                     : _M_allocated_capacity;
162      }
163
164      bool
165      _M_is_shared() const
166      { return false; }
167
168      void
169      _M_set_leaked() { }
170
171      void
172      _M_leak() { }
173
174      void
175      _M_set_length(size_type __n)
176      {
177	_M_length(__n);
178	traits_type::assign(_M_data()[__n], _CharT());
179      }
180
181      __sso_string_base()
182      : _M_dataplus(_M_local_data)
183      { _M_set_length(0); }
184
185      __sso_string_base(const _Alloc& __a);
186
187      __sso_string_base(const __sso_string_base& __rcs);
188
189#if __cplusplus >= 201103L
190      __sso_string_base(__sso_string_base&& __rcs);
191#endif
192
193      __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a);
194
195      template<typename _InputIterator>
196        __sso_string_base(_InputIterator __beg, _InputIterator __end,
197			  const _Alloc& __a);
198
199      ~__sso_string_base()
200      { _M_dispose(); }
201
202      _CharT_alloc_type&
203      _M_get_allocator()
204      { return _M_dataplus; }
205
206      const _CharT_alloc_type&
207      _M_get_allocator() const
208      { return _M_dataplus; }
209
210      void
211      _M_swap(__sso_string_base& __rcs);
212
213      void
214      _M_assign(const __sso_string_base& __rcs);
215
216      void
217      _M_reserve(size_type __res);
218
219      void
220      _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
221		size_type __len2);
222
223      void
224      _M_erase(size_type __pos, size_type __n);
225
226      void
227      _M_clear()
228      { _M_set_length(0); }
229
230      bool
231      _M_compare(const __sso_string_base&) const
232      { return false; }
233    };
234
235  template<typename _CharT, typename _Traits, typename _Alloc>
236    void
237    __sso_string_base<_CharT, _Traits, _Alloc>::
238    _M_swap(__sso_string_base& __rcs)
239    {
240      if (this == &__rcs)
241	return;
242
243      // _GLIBCXX_RESOLVE_LIB_DEFECTS
244      // 431. Swapping containers with unequal allocators.
245      std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(),
246						     __rcs._M_get_allocator());
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 > _M_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	{
327	  __capacity = 2 * __old_capacity;
328	  // Never allocate a string bigger than max_size.
329	  if (__capacity > _M_max_size())
330	    __capacity = _M_max_size();
331	}
332
333      // NB: Need an array of char_type[__capacity], plus a terminating
334      // null char_type() element.
335      return _M_get_allocator().allocate(__capacity + 1);
336    }
337
338  template<typename _CharT, typename _Traits, typename _Alloc>
339    __sso_string_base<_CharT, _Traits, _Alloc>::
340    __sso_string_base(const _Alloc& __a)
341    : _M_dataplus(__a, _M_local_data)
342    { _M_set_length(0); }
343
344  template<typename _CharT, typename _Traits, typename _Alloc>
345    __sso_string_base<_CharT, _Traits, _Alloc>::
346    __sso_string_base(const __sso_string_base& __rcs)
347    : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
348    { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); }
349
350#if __cplusplus >= 201103L
351  template<typename _CharT, typename _Traits, typename _Alloc>
352    __sso_string_base<_CharT, _Traits, _Alloc>::
353    __sso_string_base(__sso_string_base&& __rcs)
354    : _M_dataplus(__rcs._M_get_allocator(), _M_local_data)
355    {
356      if (__rcs._M_is_local())
357	{
358	  if (__rcs._M_length())
359	    traits_type::copy(_M_local_data, __rcs._M_local_data,
360			      _S_local_capacity + 1);
361	}
362      else
363	{
364	  _M_data(__rcs._M_data());
365	  _M_capacity(__rcs._M_allocated_capacity);
366	}
367
368      _M_set_length(__rcs._M_length());
369      __rcs._M_data(__rcs._M_local_data);
370      __rcs._M_set_length(0);
371    }
372#endif
373
374  template<typename _CharT, typename _Traits, typename _Alloc>
375    __sso_string_base<_CharT, _Traits, _Alloc>::
376    __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a)
377    : _M_dataplus(__a, _M_local_data)
378    { _M_construct(__n, __c); }
379
380  template<typename _CharT, typename _Traits, typename _Alloc>
381    template<typename _InputIterator>
382    __sso_string_base<_CharT, _Traits, _Alloc>::
383    __sso_string_base(_InputIterator __beg, _InputIterator __end,
384		      const _Alloc& __a)
385    : _M_dataplus(__a, _M_local_data)
386    { _M_construct(__beg, __end); }
387
388  // NB: This is the special case for Input Iterators, used in
389  // istreambuf_iterators, etc.
390  // Input Iterators have a cost structure very different from
391  // pointers, calling for a different coding style.
392  template<typename _CharT, typename _Traits, typename _Alloc>
393    template<typename _InIterator>
394      void
395      __sso_string_base<_CharT, _Traits, _Alloc>::
396      _M_construct(_InIterator __beg, _InIterator __end,
397		   std::input_iterator_tag)
398      {
399	size_type __len = 0;
400	size_type __capacity = size_type(_S_local_capacity);
401
402	while (__beg != __end && __len < __capacity)
403	  {
404	    _M_data()[__len++] = *__beg;
405	    ++__beg;
406	  }
407
408	__try
409	  {
410	    while (__beg != __end)
411	      {
412		if (__len == __capacity)
413		  {
414		    // Allocate more space.
415		    __capacity = __len + 1;
416		    _CharT* __another = _M_create(__capacity, __len);
417		    this->_S_copy(__another, _M_data(), __len);
418		    _M_dispose();
419		    _M_data(__another);
420		    _M_capacity(__capacity);
421		  }
422		_M_data()[__len++] = *__beg;
423		++__beg;
424	      }
425	  }
426	__catch(...)
427	  {
428	    _M_dispose();
429	    __throw_exception_again;
430	  }
431
432	_M_set_length(__len);
433      }
434
435  template<typename _CharT, typename _Traits, typename _Alloc>
436    template<typename _InIterator>
437      void
438      __sso_string_base<_CharT, _Traits, _Alloc>::
439      _M_construct(_InIterator __beg, _InIterator __end,
440		   std::forward_iterator_tag)
441      {
442	// NB: Not required, but considered best practice.
443	if (__is_null_pointer(__beg) && __beg != __end)
444	  std::__throw_logic_error(__N("__sso_string_base::"
445				       "_M_construct null not valid"));
446
447	size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
448
449	if (__dnew > size_type(_S_local_capacity))
450	  {
451	    _M_data(_M_create(__dnew, size_type(0)));
452	    _M_capacity(__dnew);
453	  }
454
455	// Check for out_of_range and length_error exceptions.
456	__try
457	  { this->_S_copy_chars(_M_data(), __beg, __end); }
458	__catch(...)
459	  {
460	    _M_dispose();
461	    __throw_exception_again;
462	  }
463
464	_M_set_length(__dnew);
465      }
466
467  template<typename _CharT, typename _Traits, typename _Alloc>
468    void
469    __sso_string_base<_CharT, _Traits, _Alloc>::
470    _M_construct(size_type __n, _CharT __c)
471    {
472      if (__n > size_type(_S_local_capacity))
473	{
474	  _M_data(_M_create(__n, size_type(0)));
475	  _M_capacity(__n);
476	}
477
478      if (__n)
479	this->_S_assign(_M_data(), __n, __c);
480
481      _M_set_length(__n);
482    }
483
484  template<typename _CharT, typename _Traits, typename _Alloc>
485    void
486    __sso_string_base<_CharT, _Traits, _Alloc>::
487    _M_assign(const __sso_string_base& __rcs)
488    {
489      if (this != &__rcs)
490	{
491	  const size_type __rsize = __rcs._M_length();
492	  const size_type __capacity = _M_capacity();
493
494	  if (__rsize > __capacity)
495	    {
496	      size_type __new_capacity = __rsize;
497	      _CharT* __tmp = _M_create(__new_capacity, __capacity);
498	      _M_dispose();
499	      _M_data(__tmp);
500	      _M_capacity(__new_capacity);
501	    }
502
503	  if (__rsize)
504	    this->_S_copy(_M_data(), __rcs._M_data(), __rsize);
505
506	  _M_set_length(__rsize);
507	}
508    }
509
510  template<typename _CharT, typename _Traits, typename _Alloc>
511    void
512    __sso_string_base<_CharT, _Traits, _Alloc>::
513    _M_reserve(size_type __res)
514    {
515      // Make sure we don't shrink below the current size.
516      if (__res < _M_length())
517	__res = _M_length();
518
519      const size_type __capacity = _M_capacity();
520      if (__res != __capacity)
521	{
522	  if (__res > __capacity
523	      || __res > size_type(_S_local_capacity))
524	    {
525	      _CharT* __tmp = _M_create(__res, __capacity);
526	      this->_S_copy(__tmp, _M_data(), _M_length() + 1);
527	      _M_dispose();
528	      _M_data(__tmp);
529	      _M_capacity(__res);
530	    }
531	  else if (!_M_is_local())
532	    {
533	      this->_S_copy(_M_local_data, _M_data(), _M_length() + 1);
534	      _M_destroy(__capacity);
535	      _M_data(_M_local_data);
536	    }
537	}
538    }
539
540  template<typename _CharT, typename _Traits, typename _Alloc>
541    void
542    __sso_string_base<_CharT, _Traits, _Alloc>::
543    _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
544	      size_type __len2)
545    {
546      const size_type __how_much = _M_length() - __pos - __len1;
547
548      size_type __new_capacity = _M_length() + __len2 - __len1;
549      _CharT* __r = _M_create(__new_capacity, _M_capacity());
550
551      if (__pos)
552	this->_S_copy(__r, _M_data(), __pos);
553      if (__s && __len2)
554	this->_S_copy(__r + __pos, __s, __len2);
555      if (__how_much)
556	this->_S_copy(__r + __pos + __len2,
557		      _M_data() + __pos + __len1, __how_much);
558
559      _M_dispose();
560      _M_data(__r);
561      _M_capacity(__new_capacity);
562    }
563
564  template<typename _CharT, typename _Traits, typename _Alloc>
565    void
566    __sso_string_base<_CharT, _Traits, _Alloc>::
567    _M_erase(size_type __pos, size_type __n)
568    {
569      const size_type __how_much = _M_length() - __pos - __n;
570
571      if (__how_much && __n)
572	this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
573
574      _M_set_length(_M_length() - __n);
575    }
576
577_GLIBCXX_END_NAMESPACE_VERSION
578} // namespace
579
580#endif /* _SSO_STRING_BASE_H */
581