File Coverage

/usr/local/lib/perl5/site_perl/5.26.1/x86_64-linux/XS/libpanda.x/i/panda/basic_string.h
Criterion Covered Total %
statement 20 139 14.3
branch 2 46 4.3
condition n/a
subroutine n/a
pod n/a
total 22 185 11.8


line stmt bran cond sub pod time code
1             #pragma once
2             #include "hash.h"
3             #include "from_chars.h"
4             #include "string_view.h"
5             #include
6             #include
7             #include
8             #include
9             #include // swap
10             #include
11             #include
12             #include
13             #include
14             #include
15             #include
16              
17             namespace panda {
18              
19             /*
20             * panda::string is an std::string drop-in replacement which has the same API but is much more flexible and allows for behaviors that in other case
21             * would lead to a lot of unnecessary allocations/copying.
22             *
23             * Most important features are:
24             *
25             * - Copy-On-Write support (COW).
26             * Not only when assigning the whole string but also when any form of substr() is applied.
27             * If any of the COW copies is trying to change, it detaches from the original string, copying the content it needs.
28             * - External static string support.
29             * Can be created from external static(immortal) data without allocating memory and copying it.
30             * String will be allocated and copied when you first try to change it.
31             * For example if a function accepts string, you may pass it just a string literal "hello" and nothing is allocated or copied and even the length
32             * is counted in compile time.
33             * - External dynamic string support.
34             * Can be created from external dynamic(mortal) data without allocating memory and copying it.
35             * External data will be deallocated via custom destructor when the last string that references to the external data is lost.
36             * As for any other subtype of panda::string copying/substr/etc of such string does not copy anything
37             * - SSO support (small string optimization). Up to 23 bytes for 64bit / 11 bytes for 32bit.
38             * It does not mean that all strings <= MAX_SSO_CHARS are in SSO mode. SSO mode is used only when otherwise panda::string would have to allocate
39             * and copy something. For example if you call "otherstr = mystr.substr(offset, len)", then otherstr will not use SSO even if len <= MAX_SSO_CHARS,
40             * because it prefers to do nothing (COW-mode) instead of copying content to SSO location.
41             * - Support for getting r/w internal data buffer to manually fill it.
42             * The content of other strings which shares the data with current string will not be affected.
43             * - Reallocate instead of deallocate/allocate when possible, which in many cases is much faster
44             * - Supports auto convertations between basic_strings with different Allocator template parameter without copying and allocating anything.
45             * For example any basic_string<...> can be assigned to/from string as if they were of the same class.
46             *
47             * All these features covers almost all generic use cases, including creating zero-copy cascade parsers which in other case would lead to a lot of
48             * pain.
49             *
50             * c_str() is not supported, because strings are not null-terminated
51             */
52              
53             namespace string_detail {
54             template
55             struct mutable_charref {
56             using value_type = typename S::value_type;
57             using size_type = typename S::size_type;
58              
59             mutable_charref (S& string, size_type pos): _string(string), _pos(pos) {}
60              
61             template ::value>>
62             mutable_charref& operator= (Arg&& value) {
63             _string._detach();
64             _string._str[_pos] = std::forward(value);
65             return *this;
66             }
67              
68             operator value_type() const { return _string._str[_pos]; }
69              
70             private:
71             S& _string;
72             size_type _pos;
73             };
74              
75             enum class State : uint8_t {
76             LITERAL, // shares external data, no Buffer, no _storage.dtor (literal data is immortal)
77             SSO, // owns small string, no Buffer, no _storage.dtor
78             INTERNAL, // has InternalBuffer, may have _storage.dtor in case of basic_string <-> basic_string convertations
79             EXTERNAL, // has ExternalShared, shares external data, _storage.dtor present, _storage.external->dtor present
80             };
81              
82             template
83             struct Buffer {
84             size_t capacity;
85             uint32_t refcnt;
86 0           CharT* start() {return (CharT*)(&refcnt + 1);}
87             };
88              
89             static_assert(sizeof(Buffer) % 8 == 0, "Alignment problem, sizeof(Buffer) should be 8 on 32-bit platforms and 16 on 64");
90              
91             template
92             struct ExternalShared : Buffer {
93             using dtor_fn = void (*)(CharT*, size_t);
94             dtor_fn dtor; // deallocator for ExternalShared, may differ from Alloc::deallocate !
95             CharT* ptr; // pointer to external data originally passed to string's constructor
96             };
97             }
98              
99             template
100             struct DefaultStaticAllocator {
101             typedef T value_type;
102              
103 0           static T* allocate (size_t n) {
104 0           void* mem = malloc(n * sizeof(T));
105 0 0         if (!mem) throw std::bad_alloc();
106 0           return (T*)mem;
107             }
108              
109 0           static void deallocate (T* mem, size_t) {
110 0           free(mem);
111 0           }
112              
113 0           static T* reallocate (T* mem, size_t need, size_t /*old*/) {
114 0           void* new_mem = realloc(mem, need * sizeof(T));
115             //if (new_mem != mem) { call move constructors if applicable }
116 0           return (T*)new_mem;
117             }
118             };
119              
120             // GCC fails to determine maybe-uninitialized cases correctly for this code
121             #pragma GCC diagnostic push
122             #pragma GCC diagnostic ignored "-Wpragmas"
123             #pragma GCC diagnostic ignored "-Wunknown-warning-option"
124             #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
125              
126             template , class Alloc = DefaultStaticAllocator>
127             struct basic_string {
128             struct iterator;
129             typedef Traits traits_type;
130             typedef Alloc allocator_type;
131             typedef std::allocator_traits allocator_traits;
132             typedef typename Traits::char_type value_type;
133             typedef value_type& reference;
134             typedef const value_type& const_reference;
135             typedef typename allocator_traits::pointer pointer;
136             typedef typename allocator_traits::const_pointer const_pointer;
137             typedef const CharT* const_iterator;
138             typedef std::reverse_iterator reverse_iterator;
139             typedef std::reverse_iterator const_reverse_iterator;
140             typedef typename allocator_traits::difference_type difference_type;
141             typedef typename allocator_traits::size_type size_type;
142              
143             using ExternalShared = string_detail::ExternalShared;
144              
145             private:
146             using dtor_fn = typename ExternalShared::dtor_fn;
147             using State = string_detail::State;
148             using Buffer = string_detail::Buffer;
149             using mutable_charref = string_detail::mutable_charref;
150              
151             template friend struct basic_string;
152             friend mutable_charref;
153              
154             static constexpr const size_type BUF_FILLER = sizeof(void*) - 4;
155             static constexpr const size_type BUF_CHARS = (sizeof(Buffer) - BUF_FILLER) / sizeof(CharT);
156             static constexpr const size_type EBUF_CHARS = sizeof(ExternalShared) / sizeof(CharT);
157             static constexpr const size_type MAX_SSO_BYTES = 3 * sizeof(void*) - 1; // last byte for _state
158             static constexpr const float GROW_RATE = 1.6;
159             static const CharT TERMINAL;
160              
161             union {
162             CharT* _str;
163             const CharT* _str_literal;
164             };
165              
166             size_type _length;
167              
168             #pragma pack(push, 1)
169             union { // the size of this union is MAX_SSO_BYTES. Last byte is kept for _state which is following this union (and thus packing is needed)
170             char __fill[MAX_SSO_BYTES];
171             CharT _sso[MAX_SSO_BYTES/sizeof(CharT)];
172             struct {
173             union {
174             Buffer* any; // when code doesn't matter if we in internal or external state
175             Buffer* internal;
176             ExternalShared* external;
177             };
178             dtor_fn dtor;
179             } _storage;
180             };
181             State _state;
182             #pragma pack(pop)
183              
184             public:
185             static const size_type npos = std::numeric_limits::max();
186             static const size_type MAX_SSO_CHARS = (MAX_SSO_BYTES / sizeof(CharT));
187             static const size_type MAX_SIZE = npos / sizeof(CharT) - BUF_CHARS;
188              
189             basic_string () noexcept : _str_literal(&TERMINAL), _length(0), _state(State::LITERAL) {}
190              
191             template // implicit constructor for literals, literals are expected to be null-terminated
192 2           basic_string (const CharT (&str)[SIZE]) noexcept : _str_literal(str), _length(SIZE-1), _state(State::LITERAL) {}
193              
194             template // implicit constructor for char arrays, array must be null-trminated, behaviour is similar to std::string
195             constexpr basic_string (CharT (&str)[SIZE]) noexcept : basic_string(str, traits_type::length(str)) {}
196              
197             template::value>::type>
198             // GCC < 6 has a bug determining return value type for literals, so this ctor must be implicitly available
199             #if !defined(__GNUC__) || defined(__clang__) || __GNUC__ >= 6
200             explicit
201             #endif
202             basic_string (const _CharT* const& str) noexcept : basic_string(str, traits_type::length(str)) {}
203              
204             explicit
205             basic_string (size_type capacity) : _length(0) {
206             _new_auto(capacity);
207             }
208              
209             basic_string (const CharT* str, size_type len) : _length(len) {
210             _new_auto(len);
211             traits_type::copy(_str, str, len);
212             }
213              
214             basic_string (CharT* str, size_type len, size_type capacity, dtor_fn dtor) {
215             _new_external(str, len, capacity, dtor, (ExternalShared*)Alloc::allocate(EBUF_CHARS), &Alloc::deallocate);
216             }
217              
218             basic_string (CharT* str, size_type len, size_type capacity, dtor_fn dtor, ExternalShared* ebuf, dtor_fn ebuf_dtor) {
219             _new_external(str, len, capacity, dtor, ebuf, ebuf_dtor);
220             }
221              
222             basic_string (size_type len, CharT c) : _length(len) {
223             _new_auto(len);
224             traits_type::assign(_str, len, c);
225             }
226              
227             basic_string (const basic_string& oth) {
228             _cow(oth, 0, oth._length);
229             }
230              
231             template
232             basic_string (const basic_string& oth) {
233             _cow(oth, 0, oth._length);
234             }
235              
236             template
237             basic_string (const basic_string& oth, size_type pos) {
238             _cow_offset(oth, pos, oth._length);
239             }
240              
241             template
242             basic_string (const basic_string& oth, size_type pos, size_type len) {
243             _cow_offset(oth, pos, len);
244             }
245              
246 8           basic_string (basic_string&& oth) {
247 8           _move_from(std::move(oth));
248 8           }
249              
250             template
251             basic_string (basic_string&& oth) {
252             _move_from(std::move(oth));
253             }
254              
255             basic_string (std::initializer_list ilist) : basic_string(ilist.begin(), ilist.size()) {}
256              
257             explicit
258             basic_string (basic_string_view sv) : basic_string(sv.data(), sv.length()) {}
259              
260             explicit
261             basic_string (const std::basic_string& ss) : basic_string(ss.data(), ss.length()) {}
262              
263             template
264             basic_string& assign (const CharT (&str)[SIZE]) {
265             _release();
266             _state = State::LITERAL;
267             _str_literal = str;
268             _length = SIZE - 1;
269             return *this;
270             }
271              
272             struct iterator {
273             using size_type = typename basic_string::size_type;
274             using value_type = typename basic_string::value_type;
275             using reference = mutable_charref;
276             using pointer = mutable_charref;
277             using difference_type = std::ptrdiff_t;
278             using iterator_category = std::random_access_iterator_tag;
279             using const_iterator = typename basic_string::const_iterator;
280              
281             iterator (basic_string& string, size_type pos): _string(&string), _pos(pos) {}
282              
283             iterator () = default;
284             iterator (const iterator&) = default;
285             iterator (iterator&&) = default;
286              
287             iterator& operator=(const iterator&) = default;
288             iterator& operator=(iterator&&) = default;
289              
290             iterator& operator++ () { ++_pos; return *this; }
291             iterator operator++ (int) { iterator copy{*_string, _pos }; ++_pos; return copy; }
292             iterator& operator-- () { --_pos; return *this; }
293             iterator operator-- (int) { iterator copy{*_string, _pos }; --_pos; return copy; }
294             iterator& operator+= (int delta) { _pos += delta; return *this; }
295             iterator& operator-= (int delta) { _pos -= delta; return *this; }
296             reference operator* () { return reference{*_string, _pos}; }
297             reference operator-> () { return reference{*_string, _pos}; }
298             reference operator[] (size_type i) { return reference{*_string, i + _pos}; }
299              
300             difference_type operator- (const iterator& rhs) const { return static_cast(_pos - rhs._pos); }
301              
302             bool operator== (const iterator& rhs) const { return _pos == rhs._pos; }
303             bool operator!= (const iterator& rhs) const { return _pos != rhs._pos; }
304             bool operator< (const iterator& rhs) const { return rhs._pos - _pos > 0; }
305             bool operator> (const iterator& rhs) const { return _pos - rhs._pos > 0; }
306             bool operator<= (const iterator& rhs) const { return rhs._pos - _pos >= 0; }
307             bool operator>= (const iterator& rhs) const { return _pos - rhs._pos >= 0; }
308              
309             operator const_iterator () { return _string->data() + _pos; }
310              
311             friend inline iterator operator+ (int delta, const iterator& it) { return iterator{*it._string, it._pos + delta}; }
312             friend inline iterator operator+ (const iterator& it, int delta) { return iterator{*it._string, it._pos + delta}; }
313             friend inline iterator operator- (int delta, const iterator& it) { return iterator{*it._string, it._pos - delta}; }
314             friend inline iterator operator- (const iterator& it, int delta) { return iterator{*it._string, it._pos - delta}; }
315              
316             private:
317             basic_string* _string;
318             size_type _pos;
319             };
320              
321              
322             template::value>::type>
323             basic_string& assign (const _CharT* const& str) {
324             return assign(str, traits_type::length(str));
325             }
326              
327             basic_string& assign (const CharT* str, size_type len) {
328             _reserve_drop(len);
329             traits_type::copy(_str, str, len);
330             _length = len;
331             return *this;
332             }
333              
334             basic_string& assign (CharT* str, size_type len, size_type capacity, dtor_fn dtor) {
335             if (_state != State::EXTERNAL || _storage.external->refcnt != 1) {
336             _release();
337             _new_external(str, len, capacity, dtor, (ExternalShared*)Alloc::allocate(EBUF_CHARS), &Alloc::deallocate);
338             }
339             else _replace_external(str, len, capacity, dtor);
340             return *this;
341             }
342              
343             basic_string& assign (CharT* str, size_type len, size_type capacity, dtor_fn dtor, ExternalShared* ebuf, dtor_fn ebuf_dtor) {
344             // EXTERNAL refcnt==1 optimizations do not apply because user already allocated ebuf and in either case we would need to deallocate one ebuf
345             _release();
346             _new_external(str, len, capacity, dtor, ebuf, ebuf_dtor);
347             return *this;
348             }
349              
350             basic_string& assign (size_type len, CharT c) {
351             _reserve_drop(len);
352             traits_type::assign(_str, len, c);
353             _length = len;
354             return *this;
355             }
356              
357             template
358             basic_string& assign (const basic_string& source) {
359             if (std::is_same::value && this == (void*)&source) return *this;
360             _release();
361             _cow(source, 0, source._length);
362             return *this;
363             }
364              
365             template
366             basic_string& assign (const basic_string& source, size_type pos, size_type length = npos) {
367             if (std::is_same::value && this == (void*)&source)
368             offset(pos, length);
369             else {
370             _release();
371             _cow_offset(source, pos, length);
372             }
373             return *this;
374             }
375              
376             template
377             basic_string& assign (basic_string&& source) {
378             if (std::is_same::value && this == (void*)&source) return *this;
379             _release();
380             _move_from(std::move(source));
381             return *this;
382             }
383              
384             basic_string& assign (std::initializer_list ilist) {
385             return assign(ilist.begin(), ilist.size());
386             }
387              
388             basic_string& assign (basic_string_view sv) {
389             return assign(sv.data(), sv.length());
390             }
391              
392             template
393             basic_string& operator= (const CharT (&str)[SIZE]) { return assign(str); }
394             template::value>::type>
395             basic_string& operator= (const _CharT* const& str) { return assign(str); }
396             basic_string& operator= (CharT c) { return assign(1, c); }
397             basic_string& operator= (const basic_string& source) { return assign(source); }
398             template
399             basic_string& operator= (const basic_string& source) { return assign(source); }
400             basic_string& operator= (basic_string&& source) { return assign(std::move(source)); }
401             template
402             basic_string& operator= (basic_string&& source) { return assign(std::move(source)); }
403             basic_string& operator= (std::initializer_list ilist) { return assign(ilist); }
404             basic_string& operator= (basic_string_view sv) { return assign(sv); }
405              
406             constexpr size_type length () const { return _length; }
407             constexpr size_type size () const { return _length; }
408             constexpr const CharT* data () const { return _str; }
409             constexpr bool empty () const { return _length == 0; }
410             constexpr size_type max_size () const { return MAX_SIZE; }
411              
412             CharT* buf () { _detach(); return _str; }
413             CharT* shared_buf () { _shared_detach(); return _str; }
414              
415             CharT* reserve (size_type capacity) {
416             _reserve_save(capacity);
417             return _str;
418             }
419              
420             iterator begin () { return iterator(*this, 0); }
421             iterator end () { return iterator(*this, _length); }
422             reverse_iterator rbegin () { return reverse_iterator(end()); }
423             reverse_iterator rend () { return reverse_iterator(begin()); }
424              
425             constexpr const_iterator cbegin () const { return data(); }
426             constexpr const_iterator begin () const { return cbegin(); }
427             constexpr const_iterator cend () const { return data() + _length; }
428             constexpr const_iterator end () const { return cend(); }
429             constexpr const_reverse_iterator crbegin () const { return const_reverse_iterator(cend()); }
430             constexpr const_reverse_iterator rbegin () const { return crbegin(); }
431             constexpr const_reverse_iterator crend () const { return const_reverse_iterator(cbegin()); }
432             constexpr const_reverse_iterator rend () const { return crend(); }
433              
434             explicit
435             constexpr operator bool () const { return _length; }
436              
437 2 50         operator std::basic_string () const { return std::basic_string(_str, _length); }
438             operator basic_string_view () const { return basic_string_view(_str, _length); }
439              
440             const CharT& at (size_type pos) const {
441             if (pos >= _length) throw std::out_of_range("basic_string::at");
442             return _str[pos];
443             }
444              
445             mutable_charref at (size_type pos) {
446             if (pos >= _length) throw std::out_of_range("basic_string::at");
447             return mutable_charref{ *this, pos };
448             }
449              
450             constexpr const CharT& operator[] (size_type pos) const { return _str[pos]; }
451             mutable_charref operator[] (size_type pos) { return mutable_charref{ *this, pos }; }
452              
453             constexpr const CharT& front () const { return _str[0]; }
454             constexpr const CharT& back () const { return _str[_length-1]; }
455             mutable_charref front () { return mutable_charref{ *this, 0 }; }
456             mutable_charref back () { return mutable_charref{ *this, _length-1 }; }
457              
458             size_type capacity () const {
459             switch (_state) {
460             case State::INTERNAL: return _storage.internal->refcnt == 1 ? _capacity_internal() : 0;
461             case State::EXTERNAL: return _storage.external->refcnt == 1 ? _capacity_external() : 0;
462             case State::LITERAL: return 0;
463             case State::SSO: return _capacity_sso();
464             }
465             return 0;
466             }
467              
468             size_type shared_capacity () const {
469             switch (_state) {
470             case State::INTERNAL: return _capacity_internal();
471             case State::EXTERNAL: return _capacity_external();
472             case State::LITERAL: return 0;
473             case State::SSO: return _capacity_sso();
474             }
475             return 0;
476             }
477              
478             uint32_t use_count () const {
479             switch (_state) {
480             case State::INTERNAL:
481             case State::EXTERNAL:
482             return _storage.any->refcnt;
483             default: return 1;
484             }
485             }
486              
487             void length (size_type newlen) { _length = newlen; }
488              
489             void offset (size_type offset, size_type length = npos) {
490             if (offset > _length) throw std::out_of_range("basic_string::offset");
491             if (length > _length - offset) _length = _length - offset;
492             else _length = length;
493             _str += offset;
494             }
495              
496             basic_string substr (size_type offset = 0, size_type length = npos) const {
497             return basic_string(*this, offset, length);
498             }
499              
500             void resize (size_type count) { resize(count, CharT()); }
501              
502             void resize (size_type count, CharT ch) {
503             if (count > _length) {
504             _reserve_save(count);
505             traits_type::assign(_str + _length, count - _length, ch);
506             }
507             _length = count;
508             }
509              
510             void pop_back () { --_length; }
511             void clear () { _length = 0; }
512              
513             void shrink_to_fit () {
514             switch (_state) {
515             case State::INTERNAL:
516             if (_length <= MAX_SSO_CHARS) {
517             auto old_buf = _storage.internal;
518             auto old_dtor = _storage.dtor;
519             _detach_str(_length);
520             _release_internal(old_buf, old_dtor);
521             }
522             else if (_storage.internal->capacity > _length) {
523             if (_storage.internal->refcnt == 1) _internal_realloc(_length);
524             // else _detach_cow(_length); // NOTE: it's a very hard question should or should not we do it, NOT FOR NOW
525             }
526             break;
527             case State::EXTERNAL:
528             if (_length <= MAX_SSO_CHARS) {
529             auto old_buf = _storage.external;
530             auto old_dtor = _storage.dtor;
531             _detach_str(_length);
532             _release_external(old_buf, old_dtor);
533             }
534             else if (_storage.external->capacity > _length) {
535             if (_storage.external->refcnt == 1) _external_realloc(_length);
536             // else _detach_cow(_length); // NOTE: it's a very hard question should or should not we do it, NOT FOR NOW
537             }
538             break;
539             case State::LITERAL:
540             case State::SSO:
541             break;
542             }
543             }
544              
545             template
546             void swap (basic_string& oth) {
547             std::swap(_str, oth._str);
548             std::swap(_length, oth._length);
549             if (_state == State::SSO) oth._str = oth._sso + (oth._str - _sso);
550             if (oth._state == State::SSO) _str = _sso + (_str - oth._sso);
551             // swap union & state after it
552             std::swap(((void**)__fill)[0], ((void**)oth.__fill)[0]);
553             std::swap(((void**)__fill)[1], ((void**)oth.__fill)[1]);
554             std::swap(((void**)__fill)[2], ((void**)oth.__fill)[2]);
555             }
556              
557             size_type copy (CharT* dest, size_type count, size_type pos = 0) const {
558             if (pos > _length) throw std::out_of_range("basic_string::copy");
559             if (count > _length - pos) count = _length - pos;
560             traits_type::copy(dest, _str + pos, count);
561             return count;
562             }
563              
564             basic_string& erase (size_type pos = 0, size_type count = npos) {
565             if (pos > _length) throw std::out_of_range("basic_string::erase");
566              
567             if (count > _length - pos) { // remove trail
568             _length = pos;
569             return *this;
570             }
571              
572             _length -= count;
573              
574             if (pos == 0) { // remove head
575             _str += count;
576             return *this;
577             }
578              
579             switch (_state) {
580             case State::INTERNAL:
581             case State::EXTERNAL:
582             if (_storage.any->refcnt == 1) {
583             case State::SSO:
584             // move tail or head depending on what is shorter
585             if (pos >= _length - pos) traits_type::move(_str + pos, _str + pos + count, _length - pos); // tail is shorter
586             else { // head is shorter
587             traits_type::move(_str + count, _str, pos);
588             _str += count;
589             }
590             break;
591             }
592             else --_storage.any->refcnt; // fallthrough
593             case State::LITERAL:
594             auto old_str = _str;
595             _new_auto(_length);
596             traits_type::copy(_str, old_str, pos);
597             traits_type::copy(_str + pos, old_str + pos + count, _length - pos);
598             break;
599             }
600             return *this;
601             }
602              
603             const_iterator erase (const_iterator it) {
604             size_type pos = it - cbegin();
605             erase(pos, 1);
606             return cbegin() + pos;
607             }
608              
609             const_iterator erase (const_iterator first, const_iterator last) {
610             size_type pos = first - cbegin();
611             erase(pos, last - first);
612             return cbegin() + pos;
613             }
614              
615             template
616             int compare (const basic_string& str) const {
617             return _compare(_str, _length, str._str, str._length);
618             }
619              
620             template
621             int compare (size_type pos1, size_type count1, const basic_string& str) const {
622             if (pos1 > _length) throw std::out_of_range("basic_string::compare");
623             if (count1 > _length - pos1) count1 = _length - pos1;
624             return _compare(_str + pos1, count1, str._str, str._length);
625             }
626              
627             template
628             int compare (size_type pos1, size_type count1, const basic_string& str, size_type pos2, size_type count2 = npos) const {
629             if (pos1 > _length || pos2 > str._length) throw std::out_of_range("basic_string::compare");
630             if (count1 > _length - pos1) count1 = _length - pos1;
631             if (count2 > str._length - pos2) count2 = str._length - pos2;
632             return _compare(_str + pos1, count1, str._str + pos2, count2);
633             }
634              
635             template::value>::type>
636             int compare (const _CharT* const& s) const {
637             return _compare(_str, _length, s, traits_type::length(s));
638             }
639              
640             template
641             int compare (const CharT (&s)[SIZE]) const {
642             return _compare(_str, _length, s, SIZE-1);
643             }
644              
645             template::value>::type>
646             int compare (size_type pos1, size_type count1, const _CharT* const& s) const {
647             return compare(pos1, count1, s, traits_type::length(s));
648             }
649              
650             template
651             int compare (size_type pos1, size_type count1, const CharT (&s)[SIZE]) const {
652             return compare(pos1, count1, s, SIZE-1);
653             }
654              
655             int compare (size_type pos1, size_type count1, const CharT* ptr, size_type count2) const {
656             if (pos1 > _length) throw std::out_of_range("basic_string::compare");
657             if (count1 > _length - pos1) count1 = _length - pos1;
658             return _compare(_str + pos1, count1, ptr, count2);
659             }
660              
661             int compare (basic_string_view sv) const {
662             return _compare(_str, _length, sv.data(), sv.length());
663             }
664              
665             int compare (size_type pos1, size_type count1, basic_string_view sv) const {
666             return compare(pos1, count1, sv.data(), sv.length());
667             }
668              
669             template
670             size_type find (const basic_string& str, size_type pos = 0) const {
671             return find(str._str, pos, str._length);
672             }
673              
674             size_type find (const CharT* s, size_type pos, size_type count) const {
675             if (pos > _length) return npos;
676             if (count == 0) return pos;
677              
678             const CharT* ptr = traits_type::find(_str + pos, _length - pos, *s);
679             const CharT* end = _str + _length;
680             while (ptr && end >= ptr + count) {
681             if (traits_type::compare(ptr, s, count) == 0) return ptr - _str;
682             ptr = traits_type::find(ptr+1, end - ptr - 1, *s);
683             }
684              
685             return npos;
686             }
687              
688             template::value>::type>
689             size_type find (const _CharT* const& s, size_type pos = 0) const {
690             return find(s, pos, traits_type::length(s));
691             }
692              
693             template
694             size_type find (const CharT (&s)[SIZE], size_type pos = 0) const {
695             return find(s, pos, SIZE-1);
696             }
697              
698             size_type find (CharT ch, size_type pos = 0) const {
699             if (pos >= _length) return npos;
700             const CharT* ptr = traits_type::find(_str + pos, _length - pos, ch);
701             if (ptr) return ptr - _str;
702             return npos;
703             }
704              
705             size_type find (basic_string_view sv, size_type pos = 0) const {
706             return find(sv.data(), pos, sv.length());
707             }
708              
709             template
710             size_type rfind (const basic_string& str, size_type pos = npos) const {
711             return rfind(str._str, pos, str._length);
712             }
713              
714             size_type rfind (const CharT* s, size_type pos, size_type count) const {
715             for (const CharT* ptr = _str + ((pos >= _length - count) ? (_length - count) : pos); ptr >= _str; --ptr)
716             if (traits_type::compare(ptr, s, count) == 0) return ptr - _str;
717             return npos;
718             }
719              
720             template::value>::type>
721             size_type rfind (const _CharT* const& s, size_type pos = npos) const {
722             return rfind(s, pos, traits_type::length(s));
723             }
724              
725             template
726             size_type rfind (const CharT (&s)[SIZE], size_type pos = npos) const {
727             return rfind(s, pos, SIZE-1);
728             }
729              
730             size_type rfind (CharT ch, size_type pos = npos) const {
731             const CharT* ptr = _str + (pos >= _length ? _length : (pos+1));
732             while (--ptr >= _str) if (traits_type::eq(*ptr, ch)) return ptr - _str;
733             return npos;
734             }
735              
736             size_type rfind (basic_string_view sv, size_type pos = npos) const {
737             return rfind(sv.data(), pos, sv.length());
738             }
739              
740             template
741             size_type find_first_of (const basic_string& str, size_type pos = 0) const {
742             return find_first_of(str._str, pos, str._length);
743             }
744              
745             size_type find_first_of (const CharT* s, size_type pos, size_type count) const {
746             if (count == 0) return npos;
747             const CharT* end = _str + _length;
748             for (const CharT* ptr = _str + pos; ptr < end; ++ptr) if (traits_type::find(s, count, *ptr)) return ptr - _str;
749             return npos;
750             }
751              
752             template::value>::type>
753             size_type find_first_of (const _CharT* const& s, size_type pos = 0) const {
754             return find_first_of(s, pos, traits_type::length(s));
755             }
756              
757             template
758             size_type find_first_of (const CharT (&s)[SIZE], size_type pos = 0) const {
759             return find_first_of(s, pos, SIZE-1);
760             }
761              
762             size_type find_first_of (CharT ch, size_type pos = 0) const {
763             return find(ch, pos);
764             }
765              
766             size_type find_first_of (basic_string_view sv, size_type pos = 0) const {
767             return find_first_of(sv.data(), pos, sv.length());
768             }
769              
770             template
771             size_type find_first_not_of (const basic_string& str, size_type pos = 0) const {
772             return find_first_not_of(str._str, pos, str._length);
773             }
774              
775             size_type find_first_not_of (const CharT* s, size_type pos, size_type count) const {
776             if (count == 0) return pos >= _length ? npos : pos;
777             const CharT* end = _str + _length;
778             for (const CharT* ptr = _str + pos; ptr < end; ++ptr) if (!traits_type::find(s, count, *ptr)) return ptr - _str;
779             return npos;
780             }
781              
782             template::value>::type>
783             size_type find_first_not_of (const _CharT* const& s, size_type pos = 0) const {
784             return find_first_not_of(s, pos, traits_type::length(s));
785             }
786              
787             template
788             size_type find_first_not_of (const CharT (&s)[SIZE], size_type pos = 0) const {
789             return find_first_not_of(s, pos, SIZE-1);
790             }
791              
792             size_type find_first_not_of (CharT ch, size_type pos = 0) const {
793             const CharT* end = _str + _length;
794             for (const CharT* ptr = _str + pos; ptr < end; ++ptr) if (!traits_type::eq(*ptr, ch)) return ptr - _str;
795             return npos;
796             }
797              
798             size_type find_first_not_of (basic_string_view sv, size_type pos = 0) const {
799             return find_first_not_of(sv.data(), pos, sv.length());
800             }
801              
802             template
803             size_type find_last_of (const basic_string& str, size_type pos = npos) const {
804             return find_last_of(str._str, pos, str._length);
805             }
806              
807             size_type find_last_of (const CharT* s, size_type pos, size_type count) const {
808             if (count == 0) return npos;
809             for (const CharT* ptr = _str + (pos >= _length ? (_length - 1) : pos); ptr >= _str; --ptr)
810             if (traits_type::find(s, count, *ptr)) return ptr - _str;
811             return npos;
812             }
813              
814             template::value>::type>
815             size_type find_last_of (const _CharT* const& s, size_type pos = npos) const {
816             return find_last_of(s, pos, traits_type::length(s));
817             }
818              
819             template
820             size_type find_last_of (const CharT (&s)[SIZE], size_type pos = npos) const {
821             return find_last_of(s, pos, SIZE-1);
822             }
823              
824             size_type find_last_of (CharT ch, size_type pos = npos) const {
825             return rfind(ch, pos);
826             }
827              
828             size_type find_last_of (basic_string_view sv, size_type pos = npos) const {
829             return find_last_of(sv.data(), pos, sv.length());
830             }
831              
832             template
833             size_type find_last_not_of (const basic_string& str, size_type pos = npos) const {
834             return find_last_not_of(str._str, pos, str._length);
835             }
836              
837             size_type find_last_not_of (const CharT* s, size_type pos, size_type count) const {
838             if (count == 0) return pos >= _length ? (_length-1) : pos;
839             for (const CharT* ptr = _str + (pos >= _length ? (_length - 1) : pos); ptr >= _str; --ptr)
840             if (!traits_type::find(s, count, *ptr)) return ptr - _str;
841             return npos;
842             }
843              
844             template::value>::type>
845             size_type find_last_not_of (const _CharT* const& s, size_type pos = npos) const {
846             return find_last_not_of(s, pos, traits_type::length(s));
847             }
848              
849             template
850             size_type find_last_not_of (const CharT (&s)[SIZE], size_type pos = npos) const {
851             return find_last_not_of(s, pos, SIZE-1);
852             }
853              
854             size_type find_last_not_of (CharT ch, size_type pos = npos) const {
855             for (const CharT* ptr = _str + (pos >= _length ? (_length - 1) : pos); ptr >= _str; --ptr)
856             if (!traits_type::eq(*ptr, ch)) return ptr - _str;
857             return npos;
858             }
859              
860             size_type find_last_not_of (basic_string_view sv, size_type pos = npos) const {
861             return find_last_not_of(sv.data(), pos, sv.length());
862             }
863              
864             basic_string& append (size_type count, CharT ch) {
865             if (count) {
866             _reserve_save_extra(_length + count);
867             traits_type::assign(_str + _length, count, ch);
868             _length += count;
869             }
870             return *this;
871             }
872              
873             template
874             basic_string& append (const basic_string& str) {
875             if (str._length) { // can't call append(const CharT*, size_type) because otherwise if &str == this a fuckup would occur
876             _reserve_save_extra(_length + str._length);
877             traits_type::copy(_str + _length, str._str, str._length);
878             _length += str._length;
879             }
880             return *this;
881             }
882              
883             template
884             basic_string& append (const basic_string& str, size_type pos, size_type count = npos) {
885             if (pos > str._length) throw std::out_of_range("basic_string::append");
886             if (count > str._length - pos) count = str._length - pos;
887             if (count) { // can't call append(const CharT*, size_type) because otherwise if &str == this a fuckup would occur
888             _reserve_save_extra(_length + count);
889             traits_type::copy(_str + _length, str._str + pos, count);
890             _length += count;
891             }
892             return *this;
893             }
894              
895 8           basic_string& append (const CharT* s, size_type count) { // 's' MUST NOT BE any part of this->data()
896 8 50         if (count) {
897 8           _reserve_save_extra(_length + count);
898 8           traits_type::copy(_str + _length, s, count);
899 8           _length += count;
900             }
901 8           return *this;
902             }
903              
904             template::value>::type>
905 4           basic_string& append (const _CharT* const& s) {
906 4           return append(s, traits_type::length(s));
907             }
908              
909             template
910             basic_string& append (const CharT (&s)[SIZE]) {
911             return append(s, SIZE-1);
912             }
913              
914             basic_string& append (std::initializer_list ilist) {
915             return append(ilist.begin(), ilist.size());
916             }
917              
918 4           basic_string& append (basic_string_view sv) {
919 4           return append(sv.data(), sv.length());
920             }
921              
922             void push_back (CharT ch) {
923             append(1, ch);
924             }
925              
926             template
927             basic_string& operator+= (const CharT (&str)[SIZE]) { return append(str, SIZE-1); }
928             template::value>::type>
929             basic_string& operator+= (const _CharT* const& str) { return append(str); }
930             template
931             basic_string& operator+= (const basic_string& str) { return append(str); }
932             basic_string& operator+= (CharT ch) { return append(1, ch); }
933             basic_string& operator+= (std::initializer_list ilist) { return append(ilist); }
934             basic_string& operator+= (basic_string_view sv) { return append(sv); }
935              
936             basic_string& insert (size_type pos, const basic_string& str) {
937             if (this == &str) {
938             const basic_string tmp(str);
939             return insert(pos, tmp._str, tmp._length);
940             }
941             else return insert(pos, str._str, str._length);
942             }
943              
944             template
945             basic_string& insert (size_type pos, const basic_string& str) {
946             return insert(pos, str._str, str._length);
947             }
948              
949             basic_string& insert (size_type pos, const basic_string& str, size_type subpos, size_type sublen = npos) {
950             if (subpos > str._length) throw std::out_of_range("basic_string::insert");
951             if (sublen > str._length - subpos) sublen = str._length - subpos;
952             if (this == &str) {
953             const basic_string tmp(str);
954             return insert(pos, tmp._str + subpos, sublen);
955             }
956             else return insert(pos, str._str + subpos, sublen);
957             }
958              
959             template
960             basic_string& insert (size_type pos, const basic_string& str, size_type subpos, size_type sublen = npos) {
961             if (subpos > str._length) throw std::out_of_range("basic_string::insert");
962             if (sublen > str._length - subpos) sublen = str._length - subpos;
963             return insert(pos, str._str + subpos, sublen);
964             }
965              
966             template::value>::type>
967             basic_string& insert (size_type pos, const _CharT* const& s) {
968             return insert(pos, s, traits_type::length(s));
969             }
970              
971             template
972             basic_string& insert (size_type pos, const CharT (&s)[SIZE]) {
973             return insert(pos, s, SIZE-1);
974             }
975              
976             basic_string& insert (size_type pos, const CharT* s, size_type count) {
977             if (pos >= _length) {
978             if (pos == _length) return append(s, count);
979             throw std::out_of_range("basic_string::insert");
980             }
981             if (count == 0) return *this;
982             _reserve_middle(pos, 0, count);
983             traits_type::copy(_str + pos, s, count);
984             return *this;
985             }
986              
987             basic_string& insert (size_type pos, size_type count, CharT ch) {
988             if (pos >= _length) {
989             if (pos == _length) return append(count, ch);
990             throw std::out_of_range("basic_string::insert");
991             }
992             if (count == 0) return *this;
993             _reserve_middle(pos, 0, count);
994             traits_type::assign(_str + pos, count, ch);
995             return *this;
996             }
997              
998             iterator insert (const_iterator it, size_type count, CharT ch) {
999             size_type pos = it - cbegin();
1000             insert(pos, count, ch);
1001             return iterator{*this, pos};
1002             }
1003              
1004             iterator insert (const_iterator it, CharT ch) {
1005             size_type pos = it - cbegin();
1006             insert(pos, 1, ch);
1007             return iterator{*this, pos};
1008             }
1009              
1010             basic_string& insert (const_iterator it, std::initializer_list ilist) {
1011             return insert(it - cbegin(), ilist.begin(), ilist.size());
1012             }
1013              
1014             basic_string& insert (size_type pos, basic_string_view sv) {
1015             return insert(pos, sv.data(), sv.length());
1016             }
1017              
1018             // fix ambiguity between iterator(char*) and size_t
1019             basic_string& insert (int pos, size_type count, CharT ch) { return insert((size_type)pos, count, ch); }
1020              
1021             basic_string& replace (size_type pos, size_type remove_count, const basic_string& str) {
1022             if (this == &str) {
1023             const basic_string tmp(str);
1024             return replace(pos, remove_count, tmp._str, tmp._length);
1025             }
1026             return replace(pos, remove_count, str._str, str._length);
1027             }
1028              
1029             template
1030             basic_string& replace (size_type pos, size_type remove_count, const basic_string& str) {
1031             return replace(pos, remove_count, str._str, str._length);
1032             }
1033              
1034             template
1035             basic_string& replace (const_iterator first, const_iterator last, const basic_string& str) {
1036             return replace(first - cbegin(), last - first, str);
1037             }
1038              
1039             basic_string& replace (size_type pos, size_type remove_count, const basic_string& str, size_type pos2, size_type insert_count = npos) {
1040             if (pos2 > str._length) throw std::out_of_range("basic_string::replace");
1041             if (insert_count > str._length - pos2) insert_count = str._length - pos2;
1042             if (this == &str) {
1043             const basic_string tmp(str);
1044             return replace(pos, remove_count, tmp._str + pos2, insert_count);
1045             }
1046             return replace(pos, remove_count, str._str + pos2, insert_count);
1047             }
1048              
1049             template
1050             basic_string& replace (size_type pos, size_type remove_count, const basic_string& str, size_type pos2, size_type insert_count = npos) {
1051             if (pos2 > str._length) throw std::out_of_range("basic_string::replace");
1052             if (insert_count > str._length - pos2) insert_count = str._length - pos2;
1053             return replace(pos, remove_count, str._str + pos2, insert_count);
1054             }
1055              
1056             basic_string& replace (size_type pos, size_type remove_count, const CharT* s, size_type insert_count) {
1057             if (pos >= _length) {
1058             if (pos == _length) return append(s, insert_count);
1059             throw std::out_of_range("basic_string::replace");
1060             }
1061             if (remove_count >= _length - pos) {
1062             _length = pos;
1063             return append(s, insert_count);
1064             }
1065             if (insert_count == 0) {
1066             if (remove_count == 0) return *this;
1067             return erase(pos, remove_count);
1068             }
1069             _reserve_middle(pos, remove_count, insert_count);
1070             traits_type::copy(_str + pos, s, insert_count);
1071             return *this;
1072             }
1073              
1074             basic_string& replace (const_iterator first, const_iterator last, const CharT* s, size_type insert_count) {
1075             return replace(first - cbegin(), last - first, s, insert_count);
1076             }
1077              
1078             template::value>::type>
1079             basic_string& replace (size_type pos, size_type remove_count, const _CharT* const& s) {
1080             return replace(pos, remove_count, s, traits_type::length(s));
1081             }
1082              
1083             template
1084             basic_string& replace (size_type pos, size_type remove_count, const CharT (&s)[SIZE]) {
1085             return replace(pos, remove_count, s, SIZE-1);
1086             }
1087              
1088             template::value>::type>
1089             basic_string& replace (const_iterator first, const_iterator last, const _CharT* const& s) {
1090             return replace(first, last, s, traits_type::length(s));
1091             }
1092              
1093             template
1094             basic_string& replace (const_iterator first, const_iterator last, const CharT (&s)[SIZE]) {
1095             return replace(first, last, s, SIZE-1);
1096             }
1097              
1098             basic_string& replace (size_type pos, size_type remove_count, size_type insert_count, CharT ch) {
1099             if (pos >= _length) {
1100             if (pos == _length) return append(insert_count, ch);
1101             throw std::out_of_range("basic_string::replace");
1102             }
1103             if (remove_count >= _length - pos) {
1104             _length = pos;
1105             return append(insert_count, ch);
1106             }
1107             if (insert_count == 0) {
1108             if (remove_count == 0) return *this;
1109             return erase(pos, remove_count);
1110             }
1111             _reserve_middle(pos, remove_count, insert_count);
1112             traits_type::assign(_str + pos, insert_count, ch);
1113             return *this;
1114             }
1115              
1116             basic_string& replace (const_iterator first, const_iterator last, size_type insert_count, CharT ch) {
1117             return replace(first - cbegin(), last - first, insert_count, ch);
1118             }
1119              
1120             basic_string& replace (const_iterator first, const_iterator last, std::initializer_list ilist) {
1121             return replace(first, last, ilist.begin(), ilist.size());
1122             }
1123              
1124             basic_string& replace (size_type pos, size_type remove_count, basic_string_view sv) {
1125             return replace(pos, remove_count, sv.data(), sv.length());
1126             }
1127              
1128             basic_string& replace (const_iterator first, const_iterator last, basic_string_view sv) {
1129             return replace(first - cbegin(), last - first, sv);
1130             }
1131              
1132             template
1133             from_chars_result to_number (V& value, int base = 10) const { return from_chars(_str, _str + _length, value, base); }
1134              
1135             template
1136             from_chars_result to_number (V& value, size_type pos, size_type count = npos, int base = 10) const {
1137             if (pos > _length) throw std::out_of_range("basic_string::to_number");
1138             if (count > _length - pos) count = _length - pos;
1139             return from_chars(_str + pos, _str + pos + count, value, base);
1140             }
1141              
1142             template
1143             static basic_string from_number (V value, int base = 10) {
1144             auto maxsz = to_chars_maxsize(base);
1145             basic_string ret(maxsz);
1146             auto res = to_chars(ret._str, ret._str + maxsz, value, base);
1147             assert(!res.ec);
1148             ret.length(res.ptr - ret.data());
1149             return ret;
1150             }
1151              
1152             const CharT* c_str () const {
1153             if (_state == State::LITERAL) return _str; // LITERALs are NT
1154             // _str[_length] access to possibly uninititalized memory, UB.
1155             // if we have r/o space after string, let's see if it's already NT
1156             // if (shared_capacity() > _length && _str[_length] == 0) return _str;
1157              
1158             // string is not NT
1159             if (capacity() <= _length) const_cast(this)->_reserve_save(_length + 1); // we're in COW mode or don't have space
1160             _str[_length] = 0;
1161             return _str;
1162             }
1163              
1164 0           ~basic_string () { _release(); }
1165              
1166             private:
1167              
1168 0           constexpr size_type _capacity_internal () const { return _storage.internal->capacity - (_str - _storage.internal->start()); }
1169 0           constexpr size_type _capacity_external () const { return _storage.external->capacity - (_str - _storage.external->ptr); }
1170 0           constexpr size_type _capacity_sso () const { return MAX_SSO_CHARS - (_str - _sso); }
1171              
1172 0           void _new_auto (size_type capacity) {
1173 0 0         if (capacity <= MAX_SSO_CHARS) {
1174 0           _state = State::SSO;
1175 0           _str = _sso;
1176             } else {
1177 0 0         if (capacity > MAX_SIZE) throw std::length_error("basic_string::_new_auto");
    0          
1178 0           _state = State::INTERNAL;
1179 0           _storage.internal = (Buffer*)Alloc::allocate(capacity + BUF_CHARS);
1180 0           _storage.internal->capacity = capacity;
1181 0           _storage.internal->refcnt = 1;
1182 0           _str = _storage.internal->start();
1183 0           _storage.dtor = &Alloc::deallocate;
1184             }
1185 0           }
1186              
1187             // becomes INTERNAL for capacity, and copy _str to buffer in the way so that none of internal SSO members are written before copy is made.
1188 0           void _new_internal_from_sso (size_type capacity) {
1189 0           auto ibuf = (Buffer*)Alloc::allocate(capacity + BUF_CHARS);
1190 0           traits_type::copy(ibuf->start(), _str, _length);
1191 0           ibuf->capacity = capacity;
1192 0           ibuf->refcnt = 1;
1193 0           _state = State::INTERNAL;
1194 0           _str = ibuf->start();
1195 0           _storage.internal = ibuf;
1196 0           _storage.dtor = &Alloc::deallocate;
1197 0           }
1198              
1199             void _new_internal_from_sso (size_type capacity, size_type pos, size_type remove_count, size_type insert_count) {
1200             auto ibuf = (Buffer*)Alloc::allocate(capacity + BUF_CHARS);
1201             if (pos) traits_type::copy(ibuf->start(), _str, pos);
1202             traits_type::copy((CharT*)ibuf->start() + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
1203             ibuf->capacity = capacity;
1204             ibuf->refcnt = 1;
1205             _state = State::INTERNAL;
1206             _str = ibuf->start();
1207             _storage.internal = ibuf;
1208             _storage.dtor = &Alloc::deallocate;
1209             }
1210              
1211             void _new_external (CharT* str, size_type len, size_type capacity, dtor_fn dtor, ExternalShared* ebuf, dtor_fn ebuf_dtor) {
1212             _state = State::EXTERNAL;
1213             _str = str;
1214             _length = len;
1215             ebuf->capacity = capacity;
1216             ebuf->refcnt = 1;
1217             ebuf->dtor = ebuf_dtor;
1218             ebuf->ptr = str;
1219             _storage.dtor = dtor;
1220             _storage.external = ebuf;
1221             }
1222              
1223             // releases currently held external string and reuses current ExternalShared for the new external string
1224             void _replace_external (CharT* str, size_type len, size_type capacity, dtor_fn dtor) {
1225             _free_external_str();
1226             _str = str;
1227             _length = len;
1228             _storage.dtor = dtor;
1229             _storage.external->capacity = capacity;
1230             _storage.external->ptr = str;
1231             }
1232              
1233             template
1234             void _cow (const basic_string& oth, size_type offset, size_type length) {
1235             _length = length;
1236             switch (oth._state) {
1237             case State::INTERNAL:
1238             case State::EXTERNAL:
1239             _state = oth._state;
1240             _str = oth._str + offset;
1241             _storage.any = oth._storage.any;
1242             _storage.dtor = oth._storage.dtor;
1243             ++_storage.any->refcnt;
1244             break;
1245             case State::LITERAL:
1246             _state = State::LITERAL;
1247             _str_literal = oth._str_literal + offset;
1248             break;
1249             case State::SSO:
1250             memcpy(__fill, oth.__fill, MAX_SSO_BYTES+1); // also sets _state to SSO
1251             _str = _sso + (oth._str - oth._sso) + offset;
1252             break;
1253             }
1254             }
1255              
1256             template
1257             void _cow_offset (const basic_string& oth, size_type offset, size_type length) {
1258             if (offset > oth._length) throw std::out_of_range("basic_string::assign");
1259             if (length > oth._length - offset) length = oth._length - offset;
1260             _cow(oth, offset, length);
1261             }
1262              
1263             template
1264 0           void _move_from (basic_string&& oth) {
1265 0           _length = oth._length;
1266 0           memcpy(__fill, oth.__fill, MAX_SSO_BYTES+1); // also sets _state
1267 0 0         if (oth._state == State::SSO) _str = _sso + (oth._str - oth._sso);
1268 0           else _str = oth._str;
1269 0           oth._state = State::LITERAL;
1270 0           oth._str_literal = &TERMINAL;
1271 0           oth._length = 0;
1272 0           }
1273              
1274             // loses content, may change state, after call _str is guaranteed to be writable (detaches from COW and statics)
1275             void _reserve_drop (size_type capacity) {
1276             switch (_state) {
1277             case State::INTERNAL: _reserve_drop_internal(capacity); break;
1278             case State::EXTERNAL: _reserve_drop_external(capacity); break;
1279             case State::LITERAL:
1280             case State::SSO: _new_auto(capacity);
1281             }
1282             }
1283              
1284             void _reserve_drop_internal (size_type capacity) {
1285             if (_storage.internal->refcnt > 1) {
1286             --_storage.internal->refcnt;
1287             _new_auto(capacity);
1288             }
1289             else if (_storage.internal->capacity < capacity) { // could realloc save anything?
1290             _free_internal();
1291             _new_auto(capacity);
1292             }
1293             else _str = _storage.internal->start();
1294             }
1295              
1296             void _reserve_drop_external (size_type capacity) {
1297             if (_storage.external->refcnt > 1) {
1298             --_storage.external->refcnt;
1299             _new_auto(capacity);
1300             }
1301             else if (_storage.external->capacity < capacity) {
1302             _free_external();
1303             _new_auto(capacity);
1304             }
1305             else _str = _storage.external->ptr;
1306             }
1307              
1308             void _detach () {
1309             switch (_state) {
1310             case State::INTERNAL:
1311             case State::EXTERNAL:
1312             // suppress false-positive uninitialized warning for "_storage.any" for GCC
1313             if (_storage.any->refcnt > 1) _detach_cow(_length);
1314             break;
1315             case State::LITERAL:
1316             _detach_str(_length);
1317             break;
1318             case State::SSO: break;
1319             }
1320             }
1321              
1322 0           void _detach_cow (size_type capacity) {
1323 0           --_storage.any->refcnt;
1324 0           _detach_str(capacity);
1325 0           }
1326              
1327 0           void _detach_str (size_type capacity) {
1328             assert(capacity >= _length);
1329 0           auto old_str = _str;
1330 0           _new_auto(capacity);
1331 0           traits_type::copy(_str, old_str, _length);
1332 0           }
1333              
1334             void _shared_detach () {
1335             if (_state == State::LITERAL) _detach_str(_length);
1336             }
1337              
1338 16           void _reserve_save_extra (size_type capacity) { _reserve_save(capacity, GROW_RATE); }
1339              
1340 0           void _reserve_save (size_type capacity, float extra = 1) {
1341 0 0         if (capacity < _length) capacity = _length;
1342 0           switch (_state) {
1343 0           case State::INTERNAL: _reserve_save_internal(capacity, extra); break;
1344 0           case State::EXTERNAL: _reserve_save_external(capacity, extra); break;
1345 0           case State::LITERAL: _detach_str(capacity * extra); break;
1346 0           case State::SSO: _reserve_save_sso(capacity, extra); break;
1347             }
1348 0           }
1349              
1350 0           void _reserve_save_internal (size_type capacity, float extra) {
1351 0 0         if (_storage.internal->refcnt > 1) _detach_cow(capacity * extra);
1352 0 0         else if (_storage.internal->capacity < capacity) _internal_realloc(capacity * extra); // need to grow storage
1353 0 0         else if (_capacity_internal() < capacity) { // may not to grow storage if str is moved to the beginning
1354 0           traits_type::move(_storage.internal->start(), _str, _length);
1355 0           _str = _storage.internal->start();
1356             }
1357 0           }
1358              
1359 0           void _internal_realloc (size_type capacity) {
1360             // see if we can reallocate. if _str != start we should not reallocate because we would need
1361             // either allocate more space than needed or move everything to the beginning before reallocation
1362 0 0         if (_storage.dtor == &Alloc::deallocate && _str == _storage.internal->start()) {
    0          
    0          
1363 0 0         if (capacity > MAX_SIZE) throw std::length_error("basic_string::_internal_realloc");
    0          
1364 0           _storage.internal = (Buffer*)Alloc::reallocate((CharT*)_storage.internal, capacity + BUF_CHARS, _storage.internal->capacity + BUF_CHARS);
1365 0           _str = _storage.internal->start();
1366 0           _storage.internal->capacity = capacity;
1367             } else { // need to allocate/deallocate
1368 0           auto old_buf = _storage.internal;
1369 0           auto old_str = _str;
1370 0           auto old_dtor = _storage.dtor;
1371 0           _new_auto(capacity);
1372 0           traits_type::copy(_str, old_str, _length);
1373 0           _free_internal(old_buf, old_dtor);
1374             }
1375 0           }
1376              
1377 0           void _reserve_save_external (size_type capacity, float extra) {
1378 0 0         if (_storage.external->refcnt > 1) _detach_cow(capacity * extra);
1379 0 0         else if (_storage.external->capacity < capacity) _external_realloc(capacity * extra); // need to grow storage, switch to INTERNAL/SSO
1380 0 0         else if (_capacity_external() < capacity) { // may not to grow storage if str is moved to the beginning
1381 0           traits_type::move(_storage.external->ptr, _str, _length);
1382 0           _str = _storage.external->ptr;
1383             }
1384 0           }
1385              
1386 0           void _external_realloc (size_type capacity) {
1387 0           auto old_buf = _storage.external;
1388 0           auto old_str = _str;
1389 0           auto old_dtor = _storage.dtor;
1390 0           _new_auto(capacity);
1391 0           traits_type::copy(_str, old_str, _length);
1392 0           _free_external(old_buf, old_dtor);
1393 0           }
1394              
1395 0           void _reserve_save_sso (size_type capacity, float extra) {
1396 0 0         if (MAX_SSO_CHARS < capacity) {
1397 0           _new_internal_from_sso(capacity * extra);
1398 0           return;
1399             }
1400 0 0         else if (_capacity_sso() < capacity) {
1401 0           traits_type::move(_sso, _str, _length);
1402 0           _str = _sso;
1403             }
1404             }
1405              
1406             // splits string into pwo pieces at position 'pos' with insert_count distance between them replacing remove_count chars after pos.
1407             // Tries its best not to allocate memory. set the length of string to old length + insert_count - remove_count.
1408             // The content of part [pos, pos+insert_count) is undefined after operation
1409             void _reserve_middle (size_type pos, size_type remove_count, size_type insert_count) {
1410             size_type newlen = _length + insert_count - remove_count;
1411              
1412             switch (_state) {
1413             case State::INTERNAL:
1414             if (_storage.internal->refcnt > 1) {
1415             --_storage.internal->refcnt;
1416             _reserve_middle_new(pos, remove_count, insert_count);
1417             }
1418             else if (newlen > _storage.internal->capacity) {
1419             auto old_buf = _storage.internal;
1420             auto old_dtor = _storage.dtor;
1421             _reserve_middle_new(pos, remove_count, insert_count);
1422             _release_internal(old_buf, old_dtor);
1423             }
1424             else _reserve_middle_move(pos, remove_count, insert_count, _storage.internal->start(), _capacity_internal());
1425             break;
1426             case State::EXTERNAL:
1427             if (_storage.external->refcnt > 1) {
1428             --_storage.external->refcnt;
1429             _reserve_middle_new(pos, remove_count, insert_count);
1430             }
1431             else if (newlen > _storage.external->capacity) {
1432             auto old_buf = _storage.external;
1433             auto old_dtor = _storage.dtor;
1434             _reserve_middle_new(pos, remove_count, insert_count);
1435             _release_external(old_buf, old_dtor);
1436             }
1437             else _reserve_middle_move(pos, remove_count, insert_count, _storage.external->ptr, _capacity_external());
1438             break;
1439             case State::LITERAL:
1440             _reserve_middle_new(pos, remove_count, insert_count);
1441             break;
1442             case State::SSO:
1443             if (newlen > MAX_SSO_CHARS) _new_internal_from_sso(newlen, pos, remove_count, insert_count);
1444             else _reserve_middle_move(pos, remove_count, insert_count, _sso, _capacity_sso());
1445             break;
1446             }
1447              
1448             _length = newlen;
1449             }
1450              
1451             void _reserve_middle_new (size_type pos, size_type remove_count, size_type insert_count) {
1452             auto old_str = _str;
1453             _new_auto(_length + insert_count - remove_count);
1454             if (pos) traits_type::copy(_str, old_str, pos);
1455             traits_type::copy(_str + pos + insert_count, old_str + pos + remove_count, _length - pos - remove_count);
1456             }
1457              
1458             void _reserve_middle_move (size_type pos, size_type remove_count, size_type insert_count, CharT* ptr_start, size_type capacity_tail) {
1459             if (remove_count >= insert_count) {
1460             traits_type::move(_str + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
1461             return;
1462             }
1463              
1464             auto extra_count = insert_count - remove_count;
1465             bool has_head_space = _str >= ptr_start + extra_count;
1466             bool has_tail_space = (capacity_tail - _length) >= extra_count;
1467             if (has_head_space && has_tail_space) { // move what is shorter
1468             if (pos > _length - pos - remove_count) { // tail is shorter
1469             traits_type::move(_str + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
1470             } else { // head is shorter
1471             if (pos) traits_type::move(_str - extra_count, _str, pos);
1472             _str -= extra_count;
1473             }
1474             }
1475             else if (has_head_space) {
1476             if (pos) traits_type::move(_str - extra_count, _str, pos);
1477             _str -= extra_count;
1478             }
1479             else if (has_tail_space) {
1480             traits_type::move(_str + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
1481             }
1482             else {
1483             if (pos) traits_type::move(ptr_start, _str, pos);
1484             traits_type::move(ptr_start + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
1485             _str = ptr_start;
1486             }
1487             }
1488              
1489             // leaves object in invalid state
1490 0           void _release () {
1491             // suppress false-positive GCC warning: ‘*((void*)& +16)’ may be used uninitialized in this function
1492 0           switch (_state) {
1493             case State::LITERAL :
1494 0           case State::SSO : break;
1495 0           case State::INTERNAL : _release_internal(); break;
1496 0           case State::EXTERNAL : _release_external(); break;
1497             }
1498 0           }
1499              
1500 0           void _release_internal () { _release_internal(_storage.internal, _storage.dtor); }
1501 0           void _release_external () { _release_external(_storage.external, _storage.dtor); }
1502              
1503             void _free_internal () { _free_internal(_storage.internal, _storage.dtor); }
1504             void _free_external () { _free_external_str(); _free_external_buf(); }
1505             void _free_external_str () { _free_external_str(_storage.external, _storage.dtor); }
1506             void _free_external_buf () { _free_external_buf(_storage.external); }
1507              
1508 0 0         static void _release_internal (Buffer* buf, dtor_fn dtor) { if (!--buf->refcnt) _free_internal(buf, dtor); }
1509 0 0         static void _release_external (ExternalShared* ebuf, dtor_fn dtor) { if (!--ebuf->refcnt) _free_external(ebuf, dtor); }
1510              
1511 0           static void _free_internal (Buffer* buf, dtor_fn dtor) { dtor((CharT*)buf, buf->capacity + BUF_CHARS); }
1512 0           static void _free_external (ExternalShared* ebuf, dtor_fn dtor) { _free_external_str(ebuf, dtor); _free_external_buf(ebuf); }
1513 0           static void _free_external_str (ExternalShared* ebuf, dtor_fn dtor) { dtor(ebuf->ptr, ebuf->capacity); }
1514 0           static void _free_external_buf (ExternalShared* ebuf) { ebuf->dtor((CharT*)ebuf, EBUF_CHARS); }
1515              
1516             static size_type min(size_type a, size_type b) { // std::min is in header, it is too heavy to include for one function
1517             return a < b ? a : b;
1518             }
1519              
1520             static int _compare (const CharT* ptr1, size_type len1, const CharT* ptr2, size_type len2) {
1521             int r = traits_type::compare(ptr1, ptr2, min(len1, len2));
1522             if (!r) r = (len1 < len2) ? -1 : (len1 > len2 ? 1 : 0);
1523             return r;
1524             }
1525              
1526             };
1527              
1528             #pragma GCC diagnostic pop
1529              
1530             template const C basic_string::TERMINAL = C();
1531              
1532             template const typename basic_string::size_type basic_string::npos;
1533             template const typename basic_string::size_type basic_string::MAX_SSO_CHARS;
1534             template const typename basic_string::size_type basic_string::MAX_SIZE;
1535              
1536             template inline bool operator== (const basic_string& lhs, const basic_string& rhs) { return lhs.compare(rhs) == 0; }
1537             template inline bool operator== (const C* lhs, const basic_string& rhs) { return rhs.compare(lhs) == 0; }
1538             template inline bool operator== (const basic_string& lhs, const C* rhs) { return lhs.compare(rhs) == 0; }
1539             template inline bool operator== (basic_string_view lhs, const basic_string& rhs) { return rhs.compare(lhs) == 0; }
1540             template inline bool operator== (const basic_string& lhs, basic_string_view rhs) { return lhs.compare(rhs) == 0; }
1541              
1542             template inline bool operator!= (const basic_string& lhs, const basic_string& rhs) { return lhs.compare(rhs) != 0; }
1543             template inline bool operator!= (const C* lhs, const basic_string& rhs) { return rhs.compare(lhs) != 0; }
1544             template inline bool operator!= (const basic_string& lhs, const C* rhs) { return lhs.compare(rhs) != 0; }
1545             template inline bool operator!= (basic_string_view lhs, const basic_string& rhs) { return rhs.compare(lhs) != 0; }
1546             template inline bool operator!= (const basic_string& lhs, basic_string_view rhs) { return lhs.compare(rhs) != 0; }
1547              
1548             template inline bool operator< (const basic_string& lhs, const basic_string& rhs) { return lhs.compare(rhs) < 0; }
1549             template inline bool operator< (const C* lhs, const basic_string& rhs) { return rhs.compare(lhs) > 0; }
1550             template inline bool operator< (const basic_string& lhs, const C* rhs) { return lhs.compare(rhs) < 0; }
1551             template inline bool operator< (basic_string_view lhs, const basic_string& rhs) { return rhs.compare(lhs) > 0; }
1552             template inline bool operator< (const basic_string& lhs, basic_string_view rhs) { return lhs.compare(rhs) < 0; }
1553              
1554             template inline bool operator<= (const basic_string& lhs, const basic_string& rhs) { return lhs.compare(rhs) <= 0; }
1555             template inline bool operator<= (const C* lhs, const basic_string& rhs) { return rhs.compare(lhs) >= 0; }
1556             template inline bool operator<= (const basic_string& lhs, const C* rhs) { return lhs.compare(rhs) <= 0; }
1557             template inline bool operator<= (basic_string_view lhs, const basic_string& rhs) { return rhs.compare(lhs) >= 0; }
1558             template inline bool operator<= (const basic_string& lhs, basic_string_view rhs) { return lhs.compare(rhs) <= 0; }
1559              
1560             template inline bool operator> (const basic_string& lhs, const basic_string& rhs) { return lhs.compare(rhs) > 0; }
1561             template inline bool operator> (const C* lhs, const basic_string& rhs) { return rhs.compare(lhs) < 0; }
1562             template inline bool operator> (const basic_string& lhs, const C* rhs) { return lhs.compare(rhs) > 0; }
1563             template inline bool operator> (basic_string_view lhs, const basic_string& rhs) { return rhs.compare(lhs) < 0; }
1564             template inline bool operator> (const basic_string& lhs, basic_string_view rhs) { return lhs.compare(rhs) > 0; }
1565              
1566             template inline bool operator>= (const basic_string& lhs, const basic_string& rhs) { return lhs.compare(rhs) >= 0; }
1567             template inline bool operator>= (const C* lhs, const basic_string& rhs) { return rhs.compare(lhs) <= 0; }
1568             template inline bool operator>= (const basic_string& lhs, const C* rhs) { return lhs.compare(rhs) >= 0; }
1569             template inline bool operator>= (basic_string_view lhs, const basic_string& rhs) { return rhs.compare(lhs) <= 0; }
1570             template inline bool operator>= (const basic_string& lhs, basic_string_view rhs) { return lhs.compare(rhs) >= 0; }
1571              
1572             namespace {
1573             template
1574             inline basic_string _operator_plus (const C* lhs, size_t llen, const C* rhs, size_t rlen) {
1575             basic_string ret(llen + rlen);
1576             auto buf = const_cast(ret.data()); // avoid checks for detach
1577             T::copy(buf, lhs, llen);
1578             T::copy(buf + llen, rhs, rlen);
1579             ret.length(llen + rlen);
1580             return ret;
1581             }
1582             }
1583              
1584             template
1585             inline basic_string operator+ (const basic_string& lhs, const basic_string& rhs) {
1586             if (lhs.length() == 0) return rhs;
1587             if (rhs.length() == 0) return lhs;
1588             return _operator_plus(lhs.data(), lhs.length(), rhs.data(), rhs.length());
1589             }
1590              
1591             template
1592             inline basic_string operator+ (const C* lhs, const basic_string& rhs) {
1593             size_t llen = T::length(lhs);
1594             if (llen == 0) return rhs;
1595             if (rhs.length() == 0) return basic_string(lhs, llen);
1596             return _operator_plus(lhs, llen, rhs.data(), rhs.length());
1597             }
1598              
1599             template
1600             inline basic_string operator+ (basic_string_view lhs, const basic_string& rhs) {
1601             if (lhs.length() == 0) return rhs;
1602             if (rhs.length() == 0) return basic_string(lhs);
1603             return _operator_plus(lhs.data(), lhs.length(), rhs.data(), rhs.length());
1604             }
1605              
1606             template
1607             inline basic_string operator+ (C lhs, const basic_string& rhs) {
1608             if (rhs.length() == 0) return basic_string(1, lhs);
1609             return _operator_plus(&lhs, 1, rhs.data(), rhs.length());
1610             }
1611              
1612             template
1613             inline basic_string operator+ (const basic_string& lhs, const C* rhs) {
1614             size_t rlen = T::length(rhs);
1615             if (rlen == 0) return lhs;
1616             if (lhs.length() == 0) return basic_string(rhs, rlen);
1617             return _operator_plus(lhs.data(), lhs.length(), rhs, rlen);
1618             }
1619              
1620             template
1621             inline basic_string operator+ (const basic_string& lhs, basic_string_view rhs) {
1622             if (rhs.length() == 0) return lhs;
1623             if (lhs.length() == 0) return basic_string(rhs);
1624             return _operator_plus(lhs.data(), lhs.length(), rhs.data(), rhs.length());
1625             }
1626              
1627             template
1628             inline basic_string operator+ (const basic_string& lhs, C rhs) {
1629             if (lhs.length() == 0) return basic_string(1, rhs);
1630             return _operator_plus(lhs.data(), lhs.length(), &rhs, 1);
1631             }
1632              
1633             template
1634             inline basic_string operator+ (basic_string&& lhs, const basic_string& rhs) {
1635             return std::move(lhs.append(rhs));
1636             }
1637              
1638             template
1639             inline basic_string operator+ (const basic_string& lhs, basic_string&& rhs) {
1640             return std::move(rhs.insert(0, lhs));
1641             }
1642              
1643             template
1644             inline basic_string operator+ (basic_string&& lhs, basic_string&& rhs) {
1645             return std::move(lhs.append(std::move(rhs))); // NOTE: there is cases when inserting into second is faster. But we'll need some heuristics to determine that
1646             }
1647              
1648             template
1649             inline basic_string operator+ (const C* lhs, basic_string&& rhs) {
1650             return std::move(rhs.insert(0, lhs));
1651             }
1652              
1653             template
1654             inline basic_string operator+ (basic_string_view lhs, basic_string&& rhs) {
1655             return std::move(rhs.insert(0, lhs));
1656             }
1657              
1658             template
1659             inline basic_string operator+ (C lhs, basic_string&& rhs) {
1660             return std::move(rhs.insert(0, 1, lhs));
1661             }
1662              
1663             template
1664 4           inline basic_string operator+ (basic_string&& lhs, const C* rhs) {
1665 4           return std::move(lhs.append(rhs));
1666             }
1667              
1668             template
1669 4           inline basic_string operator+ (basic_string&& lhs, basic_string_view rhs) {
1670 4           return std::move(lhs.append(rhs));
1671             }
1672              
1673             template
1674             inline basic_string operator+ (basic_string&& lhs, C rhs) {
1675             return std::move(lhs.append(1, rhs));
1676             }
1677              
1678             template
1679             inline std::basic_ostream& operator<< (std::basic_ostream& os, const basic_string& str) {
1680             return os.write(str.data(), str.length());
1681             }
1682              
1683             template
1684             inline void swap (basic_string& lhs, basic_string& rhs) {
1685             lhs.swap(rhs);
1686             }
1687              
1688             }
1689              
1690             namespace std {
1691             template
1692             struct hash> {
1693             size_t operator() (const panda::basic_string& s) const {
1694             return panda::hash::hashXX(panda::string_view((const char*)s.data(), s.length() * sizeof(C)));
1695             }
1696             };
1697              
1698             template
1699             struct hash> {
1700             size_t operator() (const panda::basic_string& s) const {
1701             return panda::hash::hashXX(panda::string_view((const char*)s.data(), s.length() * sizeof(C)));
1702             }
1703             };
1704             }