File Coverage

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