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