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 9 33 27.2
branch 1 8 12.5
condition n/a
subroutine n/a
pod n/a
total 10 41 24.3


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