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