1 // Short-string-optimized versatile string base -*- C++ -*-
2
3 // Copyright (C) 2005-2020 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
_GLIBCXX_VISIBILITY(default)33 namespace __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