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