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 138 14.4
branch 2 44 4.5
condition n/a
subroutine n/a
pod n/a
total 22 182 12.0


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