#pragma once
#include "hash.h"
#include "from_chars.h"
#include "string_view.h"
#include <string>
#include <limits>
#include <memory>
#include <iosfwd>
#include <utility> // swap
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <iterator>
#include <stdexcept>
#include <initializer_list>
namespace panda {
/*
* 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
* would lead to a lot of unnecessary allocations/copying.
*
* Most important features are:
*
* - Copy-On-Write support (COW).
* Not only when assigning the whole string but also when any form of substr() is applied.
* If any of the COW copies is trying to change, it detaches from the original string, copying the content it needs.
* - External static string support.
* Can be created from external static(immortal) data without allocating memory and copying it.
* String will be allocated and copied when you first try to change it.
* 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
* is counted in compile time.
* - External dynamic string support.
* Can be created from external dynamic(mortal) data without allocating memory and copying it.
* External data will be deallocated via custom destructor when the last string that references to the external data is lost.
* As for any other subtype of panda::string copying/substr/etc of such string does not copy anything
* - SSO support (small string optimization). Up to 23 bytes for 64bit / 11 bytes for 32bit.
* 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
* 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,
* because it prefers to do nothing (COW-mode) instead of copying content to SSO location.
* - Support for getting r/w internal data buffer to manually fill it.
* The content of other strings which shares the data with current string will not be affected.
* - Reallocate instead of deallocate/allocate when possible, which in many cases is much faster
* - Supports auto convertations between basic_strings with different Allocator template parameter without copying and allocating anything.
* For example any basic_string<...> can be assigned to/from string as if they were of the same class.
*
* 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
* pain.
*
* c_str() is not supported, because strings are not null-terminated
*/
namespace string_detail {
template <typename S>
struct mutable_charref {
using value_type = typename S::value_type;
using size_type = typename S::size_type;
mutable_charref (S& string, size_type pos): _string(string), _pos(pos) {}
template <typename Arg, typename = std::enable_if_t<std::is_convertible<Arg, value_type>::value>>
mutable_charref& operator= (Arg&& value) {
_string._detach();
_string._str[_pos] = std::forward<Arg>(value);
return *this;
}
operator value_type() const { return _string._str[_pos]; }
private:
S& _string;
size_type _pos;
};
enum class State : uint8_t {
LITERAL, // shares external data, no Buffer, no _storage.dtor (literal data is immortal)
SSO, // owns small string, no Buffer, no _storage.dtor
INTERNAL, // has InternalBuffer, may have _storage.dtor in case of basic_string<A,B,X> <-> basic_string<A,B,Y> convertations
EXTERNAL, // has ExternalShared, shares external data, _storage.dtor present, _storage.external->dtor present
};
template <class CharT>
struct Buffer {
size_t capacity;
uint32_t refcnt;
CharT* start() {return (CharT*)(&refcnt + 1);}
};
static_assert(sizeof(Buffer<char>) % 8 == 0, "Alignment problem, sizeof(Buffer<char>) should be 8 on 32-bit platforms and 16 on 64");
template <class CharT>
struct ExternalShared : Buffer<CharT> {
using dtor_fn = void (*)(CharT*, size_t);
dtor_fn dtor; // deallocator for ExternalShared, may differ from Alloc::deallocate !
CharT* ptr; // pointer to external data originally passed to string's constructor
};
}
template <class T>
struct DefaultStaticAllocator {
typedef T value_type;
static T* allocate (size_t n) {
void* mem = malloc(n * sizeof(T));
if (!mem) throw std::bad_alloc();
return (T*)mem;
}
static void deallocate (T* mem, size_t) {
free(mem);
}
static T* reallocate (T* mem, size_t need, size_t /*old*/) {
void* new_mem = realloc(mem, need * sizeof(T));
//if (new_mem != mem) { call move constructors if applicable }
return (T*)new_mem;
}
};
// GCC fails to determine maybe-uninitialized cases correctly for this code
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
template <class CharT, class Traits = std::char_traits<CharT>, class Alloc = DefaultStaticAllocator<CharT>>
struct basic_string {
struct iterator;
typedef Traits traits_type;
typedef Alloc allocator_type;
typedef std::allocator_traits<allocator_type> allocator_traits;
typedef typename Traits::char_type value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef typename allocator_traits::pointer pointer;
typedef typename allocator_traits::const_pointer const_pointer;
typedef const CharT* const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
typedef typename allocator_traits::difference_type difference_type;
typedef typename allocator_traits::size_type size_type;
using ExternalShared = string_detail::ExternalShared<CharT>;
private:
using dtor_fn = typename ExternalShared::dtor_fn;
using State = string_detail::State;
using Buffer = string_detail::Buffer<CharT>;
using mutable_charref = string_detail::mutable_charref<basic_string>;
template <class C, class T, class A> friend struct basic_string;
friend mutable_charref;
static constexpr const size_type BUF_FILLER = sizeof(void*) - 4;
static constexpr const size_type BUF_CHARS = (sizeof(Buffer) - BUF_FILLER) / sizeof(CharT);
static constexpr const size_type EBUF_CHARS = sizeof(ExternalShared) / sizeof(CharT);
static constexpr const size_type MAX_SSO_BYTES = 3 * sizeof(void*) - 1; // last byte for _state
static constexpr const float GROW_RATE = 1.6;
static const CharT TERMINAL;
union {
CharT* _str;
const CharT* _str_literal;
};
size_type _length;
#pragma pack(push, 1)
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)
char __fill[MAX_SSO_BYTES];
CharT _sso[MAX_SSO_BYTES/sizeof(CharT)];
struct {
union {
Buffer* any; // when code doesn't matter if we in internal or external state
Buffer* internal;
ExternalShared* external;
};
dtor_fn dtor;
} _storage;
};
State _state;
#pragma pack(pop)
public:
static const size_type npos = std::numeric_limits<size_type>::max();
static const size_type MAX_SSO_CHARS = (MAX_SSO_BYTES / sizeof(CharT));
static const size_type MAX_SIZE = npos / sizeof(CharT) - BUF_CHARS;
basic_string () noexcept : _str_literal(&TERMINAL), _length(0), _state(State::LITERAL) {}
template <size_type SIZE> // implicit constructor for literals, literals are expected to be null-terminated
basic_string (const CharT (&str)[SIZE]) noexcept : _str_literal(str), _length(SIZE-1), _state(State::LITERAL) {}
template <size_type SIZE> // implicit constructor for char arrays, array must be null-trminated, behaviour is similar to std::string
constexpr basic_string (CharT (&str)[SIZE]) noexcept : basic_string(str, traits_type::length(str)) {}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
// GCC < 6 has a bug determining return value type for literals, so this ctor must be implicitly available
#if !defined(__GNUC__) || defined(__clang__) || __GNUC__ >= 6
explicit
#endif
basic_string (const _CharT* const& str) noexcept : basic_string(str, traits_type::length(str)) {}
explicit
basic_string (size_type capacity) : _length(0) {
_new_auto(capacity);
}
basic_string (const CharT* str, size_type len) : _length(len) {
_new_auto(len);
traits_type::copy(_str, str, len);
}
basic_string (CharT* str, size_type len, size_type capacity, dtor_fn dtor) {
_new_external(str, len, capacity, dtor, (ExternalShared*)Alloc::allocate(EBUF_CHARS), &Alloc::deallocate);
}
basic_string (CharT* str, size_type len, size_type capacity, dtor_fn dtor, ExternalShared* ebuf, dtor_fn ebuf_dtor) {
_new_external(str, len, capacity, dtor, ebuf, ebuf_dtor);
}
basic_string (size_type len, CharT c) : _length(len) {
_new_auto(len);
traits_type::assign(_str, len, c);
}
basic_string (const basic_string& oth) {
_cow(oth, 0, oth._length);
}
template <class Alloc2>
basic_string (const basic_string<CharT, Traits, Alloc2>& oth) {
_cow(oth, 0, oth._length);
}
template <class Alloc2>
basic_string (const basic_string<CharT, Traits, Alloc2>& oth, size_type pos) {
_cow_offset(oth, pos, oth._length);
}
template <class Alloc2>
basic_string (const basic_string<CharT, Traits, Alloc2>& oth, size_type pos, size_type len) {
_cow_offset(oth, pos, len);
}
basic_string (basic_string&& oth) {
_move_from(std::move(oth));
}
template <class Alloc2>
basic_string (basic_string<CharT, Traits, Alloc2>&& oth) {
_move_from(std::move(oth));
}
basic_string (std::initializer_list<CharT> ilist) : basic_string(ilist.begin(), ilist.size()) {}
explicit
basic_string (basic_string_view<CharT, Traits> sv) : basic_string(sv.data(), sv.length()) {}
explicit
basic_string (const std::basic_string<CharT,Traits>& ss) : basic_string(ss.data(), ss.length()) {}
template <size_type SIZE>
basic_string& assign (const CharT (&str)[SIZE]) {
_release();
_state = State::LITERAL;
_str_literal = str;
_length = SIZE - 1;
return *this;
}
struct iterator {
using size_type = typename basic_string::size_type;
using value_type = typename basic_string::value_type;
using reference = mutable_charref;
using pointer = mutable_charref;
using difference_type = std::ptrdiff_t;
using iterator_category = std::random_access_iterator_tag;
using const_iterator = typename basic_string::const_iterator;
iterator (basic_string& string, size_type pos): _string(&string), _pos(pos) {}
iterator () = default;
iterator (const iterator&) = default;
iterator (iterator&&) = default;
iterator& operator=(const iterator&) = default;
iterator& operator=(iterator&&) = default;
iterator& operator++ () { ++_pos; return *this; }
iterator operator++ (int) { iterator copy{*_string, _pos }; ++_pos; return copy; }
iterator& operator-- () { --_pos; return *this; }
iterator operator-- (int) { iterator copy{*_string, _pos }; --_pos; return copy; }
iterator& operator+= (int delta) { _pos += delta; return *this; }
iterator& operator-= (int delta) { _pos -= delta; return *this; }
reference operator* () { return reference{*_string, _pos}; }
reference operator-> () { return reference{*_string, _pos}; }
reference operator[] (size_type i) { return reference{*_string, i + _pos}; }
difference_type operator- (const iterator& rhs) const { return static_cast<difference_type>(_pos - rhs._pos); }
bool operator== (const iterator& rhs) const { return _pos == rhs._pos; }
bool operator!= (const iterator& rhs) const { return _pos != rhs._pos; }
bool operator< (const iterator& rhs) const { return rhs._pos - _pos > 0; }
bool operator> (const iterator& rhs) const { return _pos - rhs._pos > 0; }
bool operator<= (const iterator& rhs) const { return rhs._pos - _pos >= 0; }
bool operator>= (const iterator& rhs) const { return _pos - rhs._pos >= 0; }
operator const_iterator () { return _string->data() + _pos; }
friend inline iterator operator+ (int delta, const iterator& it) { return iterator{*it._string, it._pos + delta}; }
friend inline iterator operator+ (const iterator& it, int delta) { return iterator{*it._string, it._pos + delta}; }
friend inline iterator operator- (int delta, const iterator& it) { return iterator{*it._string, it._pos - delta}; }
friend inline iterator operator- (const iterator& it, int delta) { return iterator{*it._string, it._pos - delta}; }
private:
basic_string* _string;
size_type _pos;
};
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
basic_string& assign (const _CharT* const& str) {
return assign(str, traits_type::length(str));
}
basic_string& assign (const CharT* str, size_type len) {
_reserve_drop(len);
traits_type::copy(_str, str, len);
_length = len;
return *this;
}
basic_string& assign (CharT* str, size_type len, size_type capacity, dtor_fn dtor) {
if (_state != State::EXTERNAL || _storage.external->refcnt != 1) {
_release();
_new_external(str, len, capacity, dtor, (ExternalShared*)Alloc::allocate(EBUF_CHARS), &Alloc::deallocate);
}
else _replace_external(str, len, capacity, dtor);
return *this;
}
basic_string& assign (CharT* str, size_type len, size_type capacity, dtor_fn dtor, ExternalShared* ebuf, dtor_fn ebuf_dtor) {
// EXTERNAL refcnt==1 optimizations do not apply because user already allocated ebuf and in either case we would need to deallocate one ebuf
_release();
_new_external(str, len, capacity, dtor, ebuf, ebuf_dtor);
return *this;
}
basic_string& assign (size_type len, CharT c) {
_reserve_drop(len);
traits_type::assign(_str, len, c);
_length = len;
return *this;
}
template <class Alloc2>
basic_string& assign (const basic_string<CharT, Traits, Alloc2>& source) {
if (std::is_same<Alloc, Alloc2>::value && this == (void*)&source) return *this;
_release();
_cow(source, 0, source._length);
return *this;
}
template <class Alloc2>
basic_string& assign (const basic_string<CharT, Traits, Alloc2>& source, size_type pos, size_type length = npos) {
if (std::is_same<Alloc, Alloc2>::value && this == (void*)&source)
offset(pos, length);
else {
_release();
_cow_offset(source, pos, length);
}
return *this;
}
template <class Alloc2>
basic_string& assign (basic_string<CharT, Traits, Alloc2>&& source) {
if (std::is_same<Alloc, Alloc2>::value && this == (void*)&source) return *this;
_release();
_move_from(std::move(source));
return *this;
}
basic_string& assign (std::initializer_list<CharT> ilist) {
return assign(ilist.begin(), ilist.size());
}
basic_string& assign (basic_string_view<CharT, Traits> sv) {
return assign(sv.data(), sv.length());
}
template <size_type SIZE>
basic_string& operator= (const CharT (&str)[SIZE]) { return assign(str); }
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
basic_string& operator= (const _CharT* const& str) { return assign(str); }
basic_string& operator= (CharT c) { return assign(1, c); }
basic_string& operator= (const basic_string& source) { return assign(source); }
template <class Alloc2>
basic_string& operator= (const basic_string<CharT, Traits, Alloc2>& source) { return assign(source); }
basic_string& operator= (basic_string&& source) { return assign(std::move(source)); }
template <class Alloc2>
basic_string& operator= (basic_string<CharT, Traits, Alloc2>&& source) { return assign(std::move(source)); }
basic_string& operator= (std::initializer_list<CharT> ilist) { return assign(ilist); }
basic_string& operator= (basic_string_view<CharT, Traits> sv) { return assign(sv); }
constexpr size_type length () const { return _length; }
constexpr size_type size () const { return _length; }
constexpr const CharT* data () const { return _str; }
constexpr bool empty () const { return _length == 0; }
constexpr size_type max_size () const { return MAX_SIZE; }
CharT* buf () { _detach(); return _str; }
CharT* shared_buf () { _shared_detach(); return _str; }
CharT* reserve (size_type capacity) {
_reserve_save(capacity);
return _str;
}
iterator begin () { return iterator(*this, 0); }
iterator end () { return iterator(*this, _length); }
reverse_iterator rbegin () { return reverse_iterator(end()); }
reverse_iterator rend () { return reverse_iterator(begin()); }
constexpr const_iterator cbegin () const { return data(); }
constexpr const_iterator begin () const { return cbegin(); }
constexpr const_iterator cend () const { return data() + _length; }
constexpr const_iterator end () const { return cend(); }
constexpr const_reverse_iterator crbegin () const { return const_reverse_iterator(cend()); }
constexpr const_reverse_iterator rbegin () const { return crbegin(); }
constexpr const_reverse_iterator crend () const { return const_reverse_iterator(cbegin()); }
constexpr const_reverse_iterator rend () const { return crend(); }
explicit
constexpr operator bool () const { return _length; }
operator std::basic_string<CharT,Traits> () const { return std::basic_string<CharT,Traits>(_str, _length); }
operator basic_string_view<CharT,Traits> () const { return basic_string_view<CharT,Traits>(_str, _length); }
const CharT& at (size_type pos) const {
if (pos >= _length) throw std::out_of_range("basic_string::at");
return _str[pos];
}
mutable_charref at (size_type pos) {
if (pos >= _length) throw std::out_of_range("basic_string::at");
return mutable_charref{ *this, pos };
}
constexpr const CharT& operator[] (size_type pos) const { return _str[pos]; }
mutable_charref operator[] (size_type pos) { return mutable_charref{ *this, pos }; }
constexpr const CharT& front () const { return _str[0]; }
constexpr const CharT& back () const { return _str[_length-1]; }
mutable_charref front () { return mutable_charref{ *this, 0 }; }
mutable_charref back () { return mutable_charref{ *this, _length-1 }; }
size_type capacity () const {
switch (_state) {
case State::INTERNAL: return _storage.internal->refcnt == 1 ? _capacity_internal() : 0;
case State::EXTERNAL: return _storage.external->refcnt == 1 ? _capacity_external() : 0;
case State::LITERAL: return 0;
case State::SSO: return _capacity_sso();
}
return 0;
}
size_type shared_capacity () const {
switch (_state) {
case State::INTERNAL: return _capacity_internal();
case State::EXTERNAL: return _capacity_external();
case State::LITERAL: return 0;
case State::SSO: return _capacity_sso();
}
return 0;
}
uint32_t use_count () const {
switch (_state) {
case State::INTERNAL:
case State::EXTERNAL:
return _storage.any->refcnt;
default: return 1;
}
}
void length (size_type newlen) { _length = newlen; }
void offset (size_type offset, size_type length = npos) {
if (offset > _length) throw std::out_of_range("basic_string::offset");
if (length > _length - offset) _length = _length - offset;
else _length = length;
_str += offset;
}
basic_string substr (size_type offset = 0, size_type length = npos) const {
return basic_string(*this, offset, length);
}
void resize (size_type count) { resize(count, CharT()); }
void resize (size_type count, CharT ch) {
if (count > _length) {
_reserve_save(count);
traits_type::assign(_str + _length, count - _length, ch);
}
_length = count;
}
void pop_back () { --_length; }
void clear () { _length = 0; }
void shrink_to_fit () {
switch (_state) {
case State::INTERNAL:
if (_length <= MAX_SSO_CHARS) {
auto old_buf = _storage.internal;
auto old_dtor = _storage.dtor;
_detach_str(_length);
_release_internal(old_buf, old_dtor);
}
else if (_storage.internal->capacity > _length) {
if (_storage.internal->refcnt == 1) _internal_realloc(_length);
// else _detach_cow(_length); // NOTE: it's a very hard question should or should not we do it, NOT FOR NOW
}
break;
case State::EXTERNAL:
if (_length <= MAX_SSO_CHARS) {
auto old_buf = _storage.external;
auto old_dtor = _storage.dtor;
_detach_str(_length);
_release_external(old_buf, old_dtor);
}
else if (_storage.external->capacity > _length) {
if (_storage.external->refcnt == 1) _external_realloc(_length);
// else _detach_cow(_length); // NOTE: it's a very hard question should or should not we do it, NOT FOR NOW
}
break;
case State::LITERAL:
case State::SSO:
break;
}
}
template <class Alloc2>
void swap (basic_string<CharT, Traits, Alloc2>& oth) {
std::swap(_str, oth._str);
std::swap(_length, oth._length);
if (_state == State::SSO) oth._str = oth._sso + (oth._str - _sso);
if (oth._state == State::SSO) _str = _sso + (_str - oth._sso);
// swap union & state after it
std::swap(((void**)__fill)[0], ((void**)oth.__fill)[0]);
std::swap(((void**)__fill)[1], ((void**)oth.__fill)[1]);
std::swap(((void**)__fill)[2], ((void**)oth.__fill)[2]);
}
size_type copy (CharT* dest, size_type count, size_type pos = 0) const {
if (pos > _length) throw std::out_of_range("basic_string::copy");
if (count > _length - pos) count = _length - pos;
traits_type::copy(dest, _str + pos, count);
return count;
}
basic_string& erase (size_type pos = 0, size_type count = npos) {
if (pos > _length) throw std::out_of_range("basic_string::erase");
if (count > _length - pos) { // remove trail
_length = pos;
return *this;
}
_length -= count;
if (pos == 0) { // remove head
_str += count;
return *this;
}
switch (_state) {
case State::INTERNAL:
case State::EXTERNAL:
if (_storage.any->refcnt == 1) {
case State::SSO:
// move tail or head depending on what is shorter
if (pos >= _length - pos) traits_type::move(_str + pos, _str + pos + count, _length - pos); // tail is shorter
else { // head is shorter
traits_type::move(_str + count, _str, pos);
_str += count;
}
break;
}
else --_storage.any->refcnt; // fallthrough
case State::LITERAL:
auto old_str = _str;
_new_auto(_length);
traits_type::copy(_str, old_str, pos);
traits_type::copy(_str + pos, old_str + pos + count, _length - pos);
break;
}
return *this;
}
const_iterator erase (const_iterator it) {
size_type pos = it - cbegin();
erase(pos, 1);
return cbegin() + pos;
}
const_iterator erase (const_iterator first, const_iterator last) {
size_type pos = first - cbegin();
erase(pos, last - first);
return cbegin() + pos;
}
template <class Alloc2>
int compare (const basic_string<CharT, Traits, Alloc2>& str) const {
return _compare(_str, _length, str._str, str._length);
}
template <class Alloc2>
int compare (size_type pos1, size_type count1, const basic_string<CharT, Traits, Alloc2>& str) const {
if (pos1 > _length) throw std::out_of_range("basic_string::compare");
if (count1 > _length - pos1) count1 = _length - pos1;
return _compare(_str + pos1, count1, str._str, str._length);
}
template <class Alloc2>
int compare (size_type pos1, size_type count1, const basic_string<CharT, Traits, Alloc2>& str, size_type pos2, size_type count2 = npos) const {
if (pos1 > _length || pos2 > str._length) throw std::out_of_range("basic_string::compare");
if (count1 > _length - pos1) count1 = _length - pos1;
if (count2 > str._length - pos2) count2 = str._length - pos2;
return _compare(_str + pos1, count1, str._str + pos2, count2);
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
int compare (const _CharT* const& s) const {
return _compare(_str, _length, s, traits_type::length(s));
}
template <size_type SIZE>
int compare (const CharT (&s)[SIZE]) const {
return _compare(_str, _length, s, SIZE-1);
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
int compare (size_type pos1, size_type count1, const _CharT* const& s) const {
return compare(pos1, count1, s, traits_type::length(s));
}
template <size_type SIZE>
int compare (size_type pos1, size_type count1, const CharT (&s)[SIZE]) const {
return compare(pos1, count1, s, SIZE-1);
}
int compare (size_type pos1, size_type count1, const CharT* ptr, size_type count2) const {
if (pos1 > _length) throw std::out_of_range("basic_string::compare");
if (count1 > _length - pos1) count1 = _length - pos1;
return _compare(_str + pos1, count1, ptr, count2);
}
int compare (basic_string_view<CharT, Traits> sv) const {
return _compare(_str, _length, sv.data(), sv.length());
}
int compare (size_type pos1, size_type count1, basic_string_view<CharT, Traits> sv) const {
return compare(pos1, count1, sv.data(), sv.length());
}
template <class Alloc2>
size_type find (const basic_string<CharT, Traits, Alloc2>& str, size_type pos = 0) const {
return find(str._str, pos, str._length);
}
size_type find (const CharT* s, size_type pos, size_type count) const {
if (pos > _length) return npos;
if (count == 0) return pos;
const CharT* ptr = traits_type::find(_str + pos, _length - pos, *s);
const CharT* end = _str + _length;
while (ptr && end >= ptr + count) {
if (traits_type::compare(ptr, s, count) == 0) return ptr - _str;
ptr = traits_type::find(ptr+1, end - ptr - 1, *s);
}
return npos;
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
size_type find (const _CharT* const& s, size_type pos = 0) const {
return find(s, pos, traits_type::length(s));
}
template <size_type SIZE>
size_type find (const CharT (&s)[SIZE], size_type pos = 0) const {
return find(s, pos, SIZE-1);
}
size_type find (CharT ch, size_type pos = 0) const {
if (pos >= _length) return npos;
const CharT* ptr = traits_type::find(_str + pos, _length - pos, ch);
if (ptr) return ptr - _str;
return npos;
}
size_type find (basic_string_view<CharT, Traits> sv, size_type pos = 0) const {
return find(sv.data(), pos, sv.length());
}
template <class Alloc2>
size_type rfind (const basic_string<CharT, Traits, Alloc2>& str, size_type pos = npos) const {
return rfind(str._str, pos, str._length);
}
size_type rfind (const CharT* s, size_type pos, size_type count) const {
for (const CharT* ptr = _str + ((pos >= _length - count) ? (_length - count) : pos); ptr >= _str; --ptr)
if (traits_type::compare(ptr, s, count) == 0) return ptr - _str;
return npos;
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
size_type rfind (const _CharT* const& s, size_type pos = npos) const {
return rfind(s, pos, traits_type::length(s));
}
template <size_type SIZE>
size_type rfind (const CharT (&s)[SIZE], size_type pos = npos) const {
return rfind(s, pos, SIZE-1);
}
size_type rfind (CharT ch, size_type pos = npos) const {
const CharT* ptr = _str + (pos >= _length ? _length : (pos+1));
while (--ptr >= _str) if (traits_type::eq(*ptr, ch)) return ptr - _str;
return npos;
}
size_type rfind (basic_string_view<CharT, Traits> sv, size_type pos = npos) const {
return rfind(sv.data(), pos, sv.length());
}
template <class Alloc2>
size_type find_first_of (const basic_string<CharT, Traits, Alloc2>& str, size_type pos = 0) const {
return find_first_of(str._str, pos, str._length);
}
size_type find_first_of (const CharT* s, size_type pos, size_type count) const {
if (count == 0) return npos;
const CharT* end = _str + _length;
for (const CharT* ptr = _str + pos; ptr < end; ++ptr) if (traits_type::find(s, count, *ptr)) return ptr - _str;
return npos;
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
size_type find_first_of (const _CharT* const& s, size_type pos = 0) const {
return find_first_of(s, pos, traits_type::length(s));
}
template <size_type SIZE>
size_type find_first_of (const CharT (&s)[SIZE], size_type pos = 0) const {
return find_first_of(s, pos, SIZE-1);
}
size_type find_first_of (CharT ch, size_type pos = 0) const {
return find(ch, pos);
}
size_type find_first_of (basic_string_view<CharT, Traits> sv, size_type pos = 0) const {
return find_first_of(sv.data(), pos, sv.length());
}
template <class Alloc2>
size_type find_first_not_of (const basic_string<CharT, Traits, Alloc2>& str, size_type pos = 0) const {
return find_first_not_of(str._str, pos, str._length);
}
size_type find_first_not_of (const CharT* s, size_type pos, size_type count) const {
if (count == 0) return pos >= _length ? npos : pos;
const CharT* end = _str + _length;
for (const CharT* ptr = _str + pos; ptr < end; ++ptr) if (!traits_type::find(s, count, *ptr)) return ptr - _str;
return npos;
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
size_type find_first_not_of (const _CharT* const& s, size_type pos = 0) const {
return find_first_not_of(s, pos, traits_type::length(s));
}
template <size_type SIZE>
size_type find_first_not_of (const CharT (&s)[SIZE], size_type pos = 0) const {
return find_first_not_of(s, pos, SIZE-1);
}
size_type find_first_not_of (CharT ch, size_type pos = 0) const {
const CharT* end = _str + _length;
for (const CharT* ptr = _str + pos; ptr < end; ++ptr) if (!traits_type::eq(*ptr, ch)) return ptr - _str;
return npos;
}
size_type find_first_not_of (basic_string_view<CharT, Traits> sv, size_type pos = 0) const {
return find_first_not_of(sv.data(), pos, sv.length());
}
template <class Alloc2>
size_type find_last_of (const basic_string<CharT, Traits, Alloc2>& str, size_type pos = npos) const {
return find_last_of(str._str, pos, str._length);
}
size_type find_last_of (const CharT* s, size_type pos, size_type count) const {
if (count == 0) return npos;
for (const CharT* ptr = _str + (pos >= _length ? (_length - 1) : pos); ptr >= _str; --ptr)
if (traits_type::find(s, count, *ptr)) return ptr - _str;
return npos;
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
size_type find_last_of (const _CharT* const& s, size_type pos = npos) const {
return find_last_of(s, pos, traits_type::length(s));
}
template <size_type SIZE>
size_type find_last_of (const CharT (&s)[SIZE], size_type pos = npos) const {
return find_last_of(s, pos, SIZE-1);
}
size_type find_last_of (CharT ch, size_type pos = npos) const {
return rfind(ch, pos);
}
size_type find_last_of (basic_string_view<CharT, Traits> sv, size_type pos = npos) const {
return find_last_of(sv.data(), pos, sv.length());
}
template <class Alloc2>
size_type find_last_not_of (const basic_string<CharT, Traits, Alloc2>& str, size_type pos = npos) const {
return find_last_not_of(str._str, pos, str._length);
}
size_type find_last_not_of (const CharT* s, size_type pos, size_type count) const {
if (count == 0) return pos >= _length ? (_length-1) : pos;
for (const CharT* ptr = _str + (pos >= _length ? (_length - 1) : pos); ptr >= _str; --ptr)
if (!traits_type::find(s, count, *ptr)) return ptr - _str;
return npos;
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
size_type find_last_not_of (const _CharT* const& s, size_type pos = npos) const {
return find_last_not_of(s, pos, traits_type::length(s));
}
template <size_type SIZE>
size_type find_last_not_of (const CharT (&s)[SIZE], size_type pos = npos) const {
return find_last_not_of(s, pos, SIZE-1);
}
size_type find_last_not_of (CharT ch, size_type pos = npos) const {
for (const CharT* ptr = _str + (pos >= _length ? (_length - 1) : pos); ptr >= _str; --ptr)
if (!traits_type::eq(*ptr, ch)) return ptr - _str;
return npos;
}
size_type find_last_not_of (basic_string_view<CharT, Traits> sv, size_type pos = npos) const {
return find_last_not_of(sv.data(), pos, sv.length());
}
basic_string& append (size_type count, CharT ch) {
if (count) {
_reserve_save_extra(_length + count);
traits_type::assign(_str + _length, count, ch);
_length += count;
}
return *this;
}
template <class Alloc2>
basic_string& append (const basic_string<CharT, Traits, Alloc2>& str) {
if (str._length) { // can't call append(const CharT*, size_type) because otherwise if &str == this a fuckup would occur
_reserve_save_extra(_length + str._length);
traits_type::copy(_str + _length, str._str, str._length);
_length += str._length;
}
return *this;
}
template <class Alloc2>
basic_string& append (const basic_string<CharT, Traits, Alloc2>& str, size_type pos, size_type count = npos) {
if (pos > str._length) throw std::out_of_range("basic_string::append");
if (count > str._length - pos) count = str._length - pos;
if (count) { // can't call append(const CharT*, size_type) because otherwise if &str == this a fuckup would occur
_reserve_save_extra(_length + count);
traits_type::copy(_str + _length, str._str + pos, count);
_length += count;
}
return *this;
}
basic_string& append (const CharT* s, size_type count) { // 's' MUST NOT BE any part of this->data()
if (count) {
_reserve_save_extra(_length + count);
traits_type::copy(_str + _length, s, count);
_length += count;
}
return *this;
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
basic_string& append (const _CharT* const& s) {
return append(s, traits_type::length(s));
}
template <size_type SIZE>
basic_string& append (const CharT (&s)[SIZE]) {
return append(s, SIZE-1);
}
basic_string& append (std::initializer_list<CharT> ilist) {
return append(ilist.begin(), ilist.size());
}
basic_string& append (basic_string_view<CharT, Traits> sv) {
return append(sv.data(), sv.length());
}
void push_back (CharT ch) {
append(1, ch);
}
template <size_type SIZE>
basic_string& operator+= (const CharT (&str)[SIZE]) { return append(str, SIZE-1); }
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
basic_string& operator+= (const _CharT* const& str) { return append(str); }
template <class Alloc2>
basic_string& operator+= (const basic_string<CharT, Traits, Alloc2>& str) { return append(str); }
basic_string& operator+= (CharT ch) { return append(1, ch); }
basic_string& operator+= (std::initializer_list<CharT> ilist) { return append(ilist); }
basic_string& operator+= (basic_string_view<CharT, Traits> sv) { return append(sv); }
basic_string& insert (size_type pos, const basic_string& str) {
if (this == &str) {
const basic_string tmp(str);
return insert(pos, tmp._str, tmp._length);
}
else return insert(pos, str._str, str._length);
}
template <class Alloc2>
basic_string& insert (size_type pos, const basic_string<CharT, Traits, Alloc2>& str) {
return insert(pos, str._str, str._length);
}
basic_string& insert (size_type pos, const basic_string& str, size_type subpos, size_type sublen = npos) {
if (subpos > str._length) throw std::out_of_range("basic_string::insert");
if (sublen > str._length - subpos) sublen = str._length - subpos;
if (this == &str) {
const basic_string tmp(str);
return insert(pos, tmp._str + subpos, sublen);
}
else return insert(pos, str._str + subpos, sublen);
}
template <class Alloc2>
basic_string& insert (size_type pos, const basic_string<CharT, Traits, Alloc2>& str, size_type subpos, size_type sublen = npos) {
if (subpos > str._length) throw std::out_of_range("basic_string::insert");
if (sublen > str._length - subpos) sublen = str._length - subpos;
return insert(pos, str._str + subpos, sublen);
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
basic_string& insert (size_type pos, const _CharT* const& s) {
return insert(pos, s, traits_type::length(s));
}
template <size_type SIZE>
basic_string& insert (size_type pos, const CharT (&s)[SIZE]) {
return insert(pos, s, SIZE-1);
}
basic_string& insert (size_type pos, const CharT* s, size_type count) {
if (pos >= _length) {
if (pos == _length) return append(s, count);
throw std::out_of_range("basic_string::insert");
}
if (count == 0) return *this;
_reserve_middle(pos, 0, count);
traits_type::copy(_str + pos, s, count);
return *this;
}
basic_string& insert (size_type pos, size_type count, CharT ch) {
if (pos >= _length) {
if (pos == _length) return append(count, ch);
throw std::out_of_range("basic_string::insert");
}
if (count == 0) return *this;
_reserve_middle(pos, 0, count);
traits_type::assign(_str + pos, count, ch);
return *this;
}
iterator insert (const_iterator it, size_type count, CharT ch) {
size_type pos = it - cbegin();
insert(pos, count, ch);
return iterator{*this, pos};
}
iterator insert (const_iterator it, CharT ch) {
size_type pos = it - cbegin();
insert(pos, 1, ch);
return iterator{*this, pos};
}
basic_string& insert (const_iterator it, std::initializer_list<CharT> ilist) {
return insert(it - cbegin(), ilist.begin(), ilist.size());
}
basic_string& insert (size_type pos, basic_string_view<CharT, Traits> sv) {
return insert(pos, sv.data(), sv.length());
}
// fix ambiguity between iterator(char*) and size_t
basic_string& insert (int pos, size_type count, CharT ch) { return insert((size_type)pos, count, ch); }
basic_string& replace (size_type pos, size_type remove_count, const basic_string& str) {
if (this == &str) {
const basic_string tmp(str);
return replace(pos, remove_count, tmp._str, tmp._length);
}
return replace(pos, remove_count, str._str, str._length);
}
template <class Alloc2>
basic_string& replace (size_type pos, size_type remove_count, const basic_string<CharT, Traits, Alloc2>& str) {
return replace(pos, remove_count, str._str, str._length);
}
template <class Alloc2>
basic_string& replace (const_iterator first, const_iterator last, const basic_string<CharT, Traits, Alloc2>& str) {
return replace(first - cbegin(), last - first, str);
}
basic_string& replace (size_type pos, size_type remove_count, const basic_string& str, size_type pos2, size_type insert_count = npos) {
if (pos2 > str._length) throw std::out_of_range("basic_string::replace");
if (insert_count > str._length - pos2) insert_count = str._length - pos2;
if (this == &str) {
const basic_string tmp(str);
return replace(pos, remove_count, tmp._str + pos2, insert_count);
}
return replace(pos, remove_count, str._str + pos2, insert_count);
}
template <class Alloc2>
basic_string& replace (size_type pos, size_type remove_count, const basic_string<CharT, Traits, Alloc2>& str, size_type pos2, size_type insert_count = npos) {
if (pos2 > str._length) throw std::out_of_range("basic_string::replace");
if (insert_count > str._length - pos2) insert_count = str._length - pos2;
return replace(pos, remove_count, str._str + pos2, insert_count);
}
basic_string& replace (size_type pos, size_type remove_count, const CharT* s, size_type insert_count) {
if (pos >= _length) {
if (pos == _length) return append(s, insert_count);
throw std::out_of_range("basic_string::replace");
}
if (remove_count >= _length - pos) {
_length = pos;
return append(s, insert_count);
}
if (insert_count == 0) {
if (remove_count == 0) return *this;
return erase(pos, remove_count);
}
_reserve_middle(pos, remove_count, insert_count);
traits_type::copy(_str + pos, s, insert_count);
return *this;
}
basic_string& replace (const_iterator first, const_iterator last, const CharT* s, size_type insert_count) {
return replace(first - cbegin(), last - first, s, insert_count);
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
basic_string& replace (size_type pos, size_type remove_count, const _CharT* const& s) {
return replace(pos, remove_count, s, traits_type::length(s));
}
template <size_type SIZE>
basic_string& replace (size_type pos, size_type remove_count, const CharT (&s)[SIZE]) {
return replace(pos, remove_count, s, SIZE-1);
}
template<class _CharT, typename = typename std::enable_if<std::is_same<_CharT, CharT>::value>::type>
basic_string& replace (const_iterator first, const_iterator last, const _CharT* const& s) {
return replace(first, last, s, traits_type::length(s));
}
template <size_type SIZE>
basic_string& replace (const_iterator first, const_iterator last, const CharT (&s)[SIZE]) {
return replace(first, last, s, SIZE-1);
}
basic_string& replace (size_type pos, size_type remove_count, size_type insert_count, CharT ch) {
if (pos >= _length) {
if (pos == _length) return append(insert_count, ch);
throw std::out_of_range("basic_string::replace");
}
if (remove_count >= _length - pos) {
_length = pos;
return append(insert_count, ch);
}
if (insert_count == 0) {
if (remove_count == 0) return *this;
return erase(pos, remove_count);
}
_reserve_middle(pos, remove_count, insert_count);
traits_type::assign(_str + pos, insert_count, ch);
return *this;
}
basic_string& replace (const_iterator first, const_iterator last, size_type insert_count, CharT ch) {
return replace(first - cbegin(), last - first, insert_count, ch);
}
basic_string& replace (const_iterator first, const_iterator last, std::initializer_list<CharT> ilist) {
return replace(first, last, ilist.begin(), ilist.size());
}
basic_string& replace (size_type pos, size_type remove_count, basic_string_view<CharT, Traits> sv) {
return replace(pos, remove_count, sv.data(), sv.length());
}
basic_string& replace (const_iterator first, const_iterator last, basic_string_view<CharT, Traits> sv) {
return replace(first - cbegin(), last - first, sv);
}
template <typename V>
from_chars_result to_number (V& value, int base = 10) const { return from_chars(_str, _str + _length, value, base); }
template <typename V>
from_chars_result to_number (V& value, size_type pos, size_type count = npos, int base = 10) const {
if (pos > _length) throw std::out_of_range("basic_string::to_number");
if (count > _length - pos) count = _length - pos;
return from_chars(_str + pos, _str + pos + count, value, base);
}
template <typename V>
static basic_string from_number (V value, int base = 10) {
auto maxsz = to_chars_maxsize<V>(base);
basic_string ret(maxsz);
auto res = to_chars(ret._str, ret._str + maxsz, value, base);
assert(!res.ec);
ret.length(res.ptr - ret.data());
return ret;
}
const CharT* c_str () const {
if (_state == State::LITERAL) return _str; // LITERALs are NT
// _str[_length] access to possibly uninititalized memory, UB.
// if we have r/o space after string, let's see if it's already NT
// if (shared_capacity() > _length && _str[_length] == 0) return _str;
// string is not NT
if (capacity() <= _length) const_cast<basic_string*>(this)->_reserve_save(_length + 1); // we're in COW mode or don't have space
_str[_length] = 0;
return _str;
}
~basic_string () { _release(); }
private:
constexpr size_type _capacity_internal () const { return _storage.internal->capacity - (_str - _storage.internal->start()); }
constexpr size_type _capacity_external () const { return _storage.external->capacity - (_str - _storage.external->ptr); }
constexpr size_type _capacity_sso () const { return MAX_SSO_CHARS - (_str - _sso); }
void _new_auto (size_type capacity) {
if (capacity <= MAX_SSO_CHARS) {
_state = State::SSO;
_str = _sso;
} else {
if (capacity > MAX_SIZE) throw std::length_error("basic_string::_new_auto");
_state = State::INTERNAL;
_storage.internal = (Buffer*)Alloc::allocate(capacity + BUF_CHARS);
_storage.internal->capacity = capacity;
_storage.internal->refcnt = 1;
_str = _storage.internal->start();
_storage.dtor = &Alloc::deallocate;
}
}
// 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.
void _new_internal_from_sso (size_type capacity) {
auto ibuf = (Buffer*)Alloc::allocate(capacity + BUF_CHARS);
traits_type::copy(ibuf->start(), _str, _length);
ibuf->capacity = capacity;
ibuf->refcnt = 1;
_state = State::INTERNAL;
_str = ibuf->start();
_storage.internal = ibuf;
_storage.dtor = &Alloc::deallocate;
}
void _new_internal_from_sso (size_type capacity, size_type pos, size_type remove_count, size_type insert_count) {
auto ibuf = (Buffer*)Alloc::allocate(capacity + BUF_CHARS);
if (pos) traits_type::copy(ibuf->start(), _str, pos);
traits_type::copy((CharT*)ibuf->start() + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
ibuf->capacity = capacity;
ibuf->refcnt = 1;
_state = State::INTERNAL;
_str = ibuf->start();
_storage.internal = ibuf;
_storage.dtor = &Alloc::deallocate;
}
void _new_external (CharT* str, size_type len, size_type capacity, dtor_fn dtor, ExternalShared* ebuf, dtor_fn ebuf_dtor) {
_state = State::EXTERNAL;
_str = str;
_length = len;
ebuf->capacity = capacity;
ebuf->refcnt = 1;
ebuf->dtor = ebuf_dtor;
ebuf->ptr = str;
_storage.dtor = dtor;
_storage.external = ebuf;
}
// releases currently held external string and reuses current ExternalShared for the new external string
void _replace_external (CharT* str, size_type len, size_type capacity, dtor_fn dtor) {
_free_external_str();
_str = str;
_length = len;
_storage.dtor = dtor;
_storage.external->capacity = capacity;
_storage.external->ptr = str;
}
template <class Alloc2>
void _cow (const basic_string<CharT, Traits, Alloc2>& oth, size_type offset, size_type length) {
_length = length;
switch (oth._state) {
case State::INTERNAL:
case State::EXTERNAL:
_state = oth._state;
_str = oth._str + offset;
_storage.any = oth._storage.any;
_storage.dtor = oth._storage.dtor;
++_storage.any->refcnt;
break;
case State::LITERAL:
_state = State::LITERAL;
_str_literal = oth._str_literal + offset;
break;
case State::SSO:
memcpy(__fill, oth.__fill, MAX_SSO_BYTES+1); // also sets _state to SSO
_str = _sso + (oth._str - oth._sso) + offset;
break;
}
}
template <class Alloc2>
void _cow_offset (const basic_string<CharT, Traits, Alloc2>& oth, size_type offset, size_type length) {
if (offset > oth._length) throw std::out_of_range("basic_string::assign");
if (length > oth._length - offset) length = oth._length - offset;
_cow(oth, offset, length);
}
template <class Alloc2>
void _move_from (basic_string<CharT, Traits, Alloc2>&& oth) {
_length = oth._length;
memcpy(__fill, oth.__fill, MAX_SSO_BYTES+1); // also sets _state
if (oth._state == State::SSO) _str = _sso + (oth._str - oth._sso);
else _str = oth._str;
oth._state = State::LITERAL;
oth._str_literal = &TERMINAL;
oth._length = 0;
}
// loses content, may change state, after call _str is guaranteed to be writable (detaches from COW and statics)
void _reserve_drop (size_type capacity) {
switch (_state) {
case State::INTERNAL: _reserve_drop_internal(capacity); break;
case State::EXTERNAL: _reserve_drop_external(capacity); break;
case State::LITERAL:
case State::SSO: _new_auto(capacity);
}
}
void _reserve_drop_internal (size_type capacity) {
if (_storage.internal->refcnt > 1) {
--_storage.internal->refcnt;
_new_auto(capacity);
}
else if (_storage.internal->capacity < capacity) { // could realloc save anything?
_free_internal();
_new_auto(capacity);
}
else _str = _storage.internal->start();
}
void _reserve_drop_external (size_type capacity) {
if (_storage.external->refcnt > 1) {
--_storage.external->refcnt;
_new_auto(capacity);
}
else if (_storage.external->capacity < capacity) {
_free_external();
_new_auto(capacity);
}
else _str = _storage.external->ptr;
}
void _detach () {
switch (_state) {
case State::INTERNAL:
case State::EXTERNAL:
// suppress false-positive uninitialized warning for "_storage.any" for GCC
if (_storage.any->refcnt > 1) _detach_cow(_length);
break;
case State::LITERAL:
_detach_str(_length);
break;
case State::SSO: break;
}
}
void _detach_cow (size_type capacity) {
--_storage.any->refcnt;
_detach_str(capacity);
}
void _detach_str (size_type capacity) {
assert(capacity >= _length);
auto old_str = _str;
_new_auto(capacity);
traits_type::copy(_str, old_str, _length);
}
void _shared_detach () {
if (_state == State::LITERAL) _detach_str(_length);
}
void _reserve_save_extra (size_type capacity) { _reserve_save(capacity, GROW_RATE); }
void _reserve_save (size_type capacity, float extra = 1) {
if (capacity < _length) capacity = _length;
switch (_state) {
case State::INTERNAL: _reserve_save_internal(capacity, extra); break;
case State::EXTERNAL: _reserve_save_external(capacity, extra); break;
case State::LITERAL: _detach_str(capacity * extra); break;
case State::SSO: _reserve_save_sso(capacity, extra); break;
}
}
void _reserve_save_internal (size_type capacity, float extra) {
if (_storage.internal->refcnt > 1) _detach_cow(capacity * extra);
else if (_storage.internal->capacity < capacity) _internal_realloc(capacity * extra); // need to grow storage
else if (_capacity_internal() < capacity) { // may not to grow storage if str is moved to the beginning
traits_type::move(_storage.internal->start(), _str, _length);
_str = _storage.internal->start();
}
}
void _internal_realloc (size_type capacity) {
// see if we can reallocate. if _str != start we should not reallocate because we would need
// either allocate more space than needed or move everything to the beginning before reallocation
if (_storage.dtor == &Alloc::deallocate && _str == _storage.internal->start()) {
if (capacity > MAX_SIZE) throw std::length_error("basic_string::_internal_realloc");
_storage.internal = (Buffer*)Alloc::reallocate((CharT*)_storage.internal, capacity + BUF_CHARS, _storage.internal->capacity + BUF_CHARS);
_str = _storage.internal->start();
_storage.internal->capacity = capacity;
} else { // need to allocate/deallocate
auto old_buf = _storage.internal;
auto old_str = _str;
auto old_dtor = _storage.dtor;
_new_auto(capacity);
traits_type::copy(_str, old_str, _length);
_free_internal(old_buf, old_dtor);
}
}
void _reserve_save_external (size_type capacity, float extra) {
if (_storage.external->refcnt > 1) _detach_cow(capacity * extra);
else if (_storage.external->capacity < capacity) _external_realloc(capacity * extra); // need to grow storage, switch to INTERNAL/SSO
else if (_capacity_external() < capacity) { // may not to grow storage if str is moved to the beginning
traits_type::move(_storage.external->ptr, _str, _length);
_str = _storage.external->ptr;
}
}
void _external_realloc (size_type capacity) {
auto old_buf = _storage.external;
auto old_str = _str;
auto old_dtor = _storage.dtor;
_new_auto(capacity);
traits_type::copy(_str, old_str, _length);
_free_external(old_buf, old_dtor);
}
void _reserve_save_sso (size_type capacity, float extra) {
if (MAX_SSO_CHARS < capacity) {
_new_internal_from_sso(capacity * extra);
return;
}
else if (_capacity_sso() < capacity) {
traits_type::move(_sso, _str, _length);
_str = _sso;
}
}
// splits string into pwo pieces at position 'pos' with insert_count distance between them replacing remove_count chars after pos.
// Tries its best not to allocate memory. set the length of string to old length + insert_count - remove_count.
// The content of part [pos, pos+insert_count) is undefined after operation
void _reserve_middle (size_type pos, size_type remove_count, size_type insert_count) {
size_type newlen = _length + insert_count - remove_count;
switch (_state) {
case State::INTERNAL:
if (_storage.internal->refcnt > 1) {
--_storage.internal->refcnt;
_reserve_middle_new(pos, remove_count, insert_count);
}
else if (newlen > _storage.internal->capacity) {
auto old_buf = _storage.internal;
auto old_dtor = _storage.dtor;
_reserve_middle_new(pos, remove_count, insert_count);
_release_internal(old_buf, old_dtor);
}
else _reserve_middle_move(pos, remove_count, insert_count, _storage.internal->start(), _capacity_internal());
break;
case State::EXTERNAL:
if (_storage.external->refcnt > 1) {
--_storage.external->refcnt;
_reserve_middle_new(pos, remove_count, insert_count);
}
else if (newlen > _storage.external->capacity) {
auto old_buf = _storage.external;
auto old_dtor = _storage.dtor;
_reserve_middle_new(pos, remove_count, insert_count);
_release_external(old_buf, old_dtor);
}
else _reserve_middle_move(pos, remove_count, insert_count, _storage.external->ptr, _capacity_external());
break;
case State::LITERAL:
_reserve_middle_new(pos, remove_count, insert_count);
break;
case State::SSO:
if (newlen > MAX_SSO_CHARS) _new_internal_from_sso(newlen, pos, remove_count, insert_count);
else _reserve_middle_move(pos, remove_count, insert_count, _sso, _capacity_sso());
break;
}
_length = newlen;
}
void _reserve_middle_new (size_type pos, size_type remove_count, size_type insert_count) {
auto old_str = _str;
_new_auto(_length + insert_count - remove_count);
if (pos) traits_type::copy(_str, old_str, pos);
traits_type::copy(_str + pos + insert_count, old_str + pos + remove_count, _length - pos - remove_count);
}
void _reserve_middle_move (size_type pos, size_type remove_count, size_type insert_count, CharT* ptr_start, size_type capacity_tail) {
if (remove_count >= insert_count) {
traits_type::move(_str + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
return;
}
auto extra_count = insert_count - remove_count;
bool has_head_space = _str >= ptr_start + extra_count;
bool has_tail_space = (capacity_tail - _length) >= extra_count;
if (has_head_space && has_tail_space) { // move what is shorter
if (pos > _length - pos - remove_count) { // tail is shorter
traits_type::move(_str + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
} else { // head is shorter
if (pos) traits_type::move(_str - extra_count, _str, pos);
_str -= extra_count;
}
}
else if (has_head_space) {
if (pos) traits_type::move(_str - extra_count, _str, pos);
_str -= extra_count;
}
else if (has_tail_space) {
traits_type::move(_str + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
}
else {
if (pos) traits_type::move(ptr_start, _str, pos);
traits_type::move(ptr_start + pos + insert_count, _str + pos + remove_count, _length - pos - remove_count);
_str = ptr_start;
}
}
// leaves object in invalid state
void _release () {
// suppress false-positive GCC warning: ‘*((void*)&<anonymous> +16)’ may be used uninitialized in this function
switch (_state) {
case State::LITERAL :
case State::SSO : break;
case State::INTERNAL : _release_internal(); break;
case State::EXTERNAL : _release_external(); break;
}
}
void _release_internal () { _release_internal(_storage.internal, _storage.dtor); }
void _release_external () { _release_external(_storage.external, _storage.dtor); }
void _free_internal () { _free_internal(_storage.internal, _storage.dtor); }
void _free_external () { _free_external_str(); _free_external_buf(); }
void _free_external_str () { _free_external_str(_storage.external, _storage.dtor); }
void _free_external_buf () { _free_external_buf(_storage.external); }
static void _release_internal (Buffer* buf, dtor_fn dtor) { if (!--buf->refcnt) _free_internal(buf, dtor); }
static void _release_external (ExternalShared* ebuf, dtor_fn dtor) { if (!--ebuf->refcnt) _free_external(ebuf, dtor); }
static void _free_internal (Buffer* buf, dtor_fn dtor) { dtor((CharT*)buf, buf->capacity + BUF_CHARS); }
static void _free_external (ExternalShared* ebuf, dtor_fn dtor) { _free_external_str(ebuf, dtor); _free_external_buf(ebuf); }
static void _free_external_str (ExternalShared* ebuf, dtor_fn dtor) { dtor(ebuf->ptr, ebuf->capacity); }
static void _free_external_buf (ExternalShared* ebuf) { ebuf->dtor((CharT*)ebuf, EBUF_CHARS); }
static size_type min(size_type a, size_type b) { // std::min is in <algorithm> header, it is too heavy to include for one function
return a < b ? a : b;
}
static int _compare (const CharT* ptr1, size_type len1, const CharT* ptr2, size_type len2) {
int r = traits_type::compare(ptr1, ptr2, min(len1, len2));
if (!r) r = (len1 < len2) ? -1 : (len1 > len2 ? 1 : 0);
return r;
}
};
#pragma GCC diagnostic pop
template <class C, class T, class A> const C basic_string<C,T,A>::TERMINAL = C();
template <class C, class T, class A> const typename basic_string<C,T,A>::size_type basic_string<C,T,A>::npos;
template <class C, class T, class A> const typename basic_string<C,T,A>::size_type basic_string<C,T,A>::MAX_SSO_CHARS;
template <class C, class T, class A> const typename basic_string<C,T,A>::size_type basic_string<C,T,A>::MAX_SIZE;
template <class C, class T, class A1, class A2> inline bool operator== (const basic_string<C,T,A1>& lhs, const basic_string<C,T,A2>& rhs) { return lhs.compare(rhs) == 0; }
template <class C, class T, class A> inline bool operator== (const C* lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) == 0; }
template <class C, class T, class A> inline bool operator== (const basic_string<C,T,A>& lhs, const C* rhs) { return lhs.compare(rhs) == 0; }
template <class C, class T, class A> inline bool operator== (basic_string_view<C,T> lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) == 0; }
template <class C, class T, class A> inline bool operator== (const basic_string<C,T,A>& lhs, basic_string_view<C,T> rhs) { return lhs.compare(rhs) == 0; }
template <class C, class T, class A1, class A2> inline bool operator!= (const basic_string<C,T,A1>& lhs, const basic_string<C,T,A2>& rhs) { return lhs.compare(rhs) != 0; }
template <class C, class T, class A> inline bool operator!= (const C* lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) != 0; }
template <class C, class T, class A> inline bool operator!= (const basic_string<C,T,A>& lhs, const C* rhs) { return lhs.compare(rhs) != 0; }
template <class C, class T, class A> inline bool operator!= (basic_string_view<C,T> lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) != 0; }
template <class C, class T, class A> inline bool operator!= (const basic_string<C,T,A>& lhs, basic_string_view<C,T> rhs) { return lhs.compare(rhs) != 0; }
template <class C, class T, class A1, class A2> inline bool operator< (const basic_string<C,T,A1>& lhs, const basic_string<C,T,A2>& rhs) { return lhs.compare(rhs) < 0; }
template <class C, class T, class A> inline bool operator< (const C* lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) > 0; }
template <class C, class T, class A> inline bool operator< (const basic_string<C,T,A>& lhs, const C* rhs) { return lhs.compare(rhs) < 0; }
template <class C, class T, class A> inline bool operator< (basic_string_view<C,T> lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) > 0; }
template <class C, class T, class A> inline bool operator< (const basic_string<C,T,A>& lhs, basic_string_view<C,T> rhs) { return lhs.compare(rhs) < 0; }
template <class C, class T, class A1, class A2> inline bool operator<= (const basic_string<C,T,A1>& lhs, const basic_string<C,T,A2>& rhs) { return lhs.compare(rhs) <= 0; }
template <class C, class T, class A> inline bool operator<= (const C* lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) >= 0; }
template <class C, class T, class A> inline bool operator<= (const basic_string<C,T,A>& lhs, const C* rhs) { return lhs.compare(rhs) <= 0; }
template <class C, class T, class A> inline bool operator<= (basic_string_view<C,T> lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) >= 0; }
template <class C, class T, class A> inline bool operator<= (const basic_string<C,T,A>& lhs, basic_string_view<C,T> rhs) { return lhs.compare(rhs) <= 0; }
template <class C, class T, class A1, class A2> inline bool operator> (const basic_string<C,T,A1>& lhs, const basic_string<C,T,A2>& rhs) { return lhs.compare(rhs) > 0; }
template <class C, class T, class A> inline bool operator> (const C* lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) < 0; }
template <class C, class T, class A> inline bool operator> (const basic_string<C,T,A>& lhs, const C* rhs) { return lhs.compare(rhs) > 0; }
template <class C, class T, class A> inline bool operator> (basic_string_view<C,T> lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) < 0; }
template <class C, class T, class A> inline bool operator> (const basic_string<C,T,A>& lhs, basic_string_view<C,T> rhs) { return lhs.compare(rhs) > 0; }
template <class C, class T, class A1, class A2> inline bool operator>= (const basic_string<C,T,A1>& lhs, const basic_string<C,T,A2>& rhs) { return lhs.compare(rhs) >= 0; }
template <class C, class T, class A> inline bool operator>= (const C* lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) <= 0; }
template <class C, class T, class A> inline bool operator>= (const basic_string<C,T,A>& lhs, const C* rhs) { return lhs.compare(rhs) >= 0; }
template <class C, class T, class A> inline bool operator>= (basic_string_view<C,T> lhs, const basic_string<C,T,A>& rhs) { return rhs.compare(lhs) <= 0; }
template <class C, class T, class A> inline bool operator>= (const basic_string<C,T,A>& lhs, basic_string_view<C,T> rhs) { return lhs.compare(rhs) >= 0; }
namespace {
template <class C, class T, class A>
inline basic_string<C,T,A> _operator_plus (const C* lhs, size_t llen, const C* rhs, size_t rlen) {
basic_string<C,T,A> ret(llen + rlen);
auto buf = const_cast<C*>(ret.data()); // avoid checks for detach
T::copy(buf, lhs, llen);
T::copy(buf + llen, rhs, rlen);
ret.length(llen + rlen);
return ret;
}
}
template <class C, class T, class A1, class A2>
inline basic_string<C,T,A1> operator+ (const basic_string<C,T,A1>& lhs, const basic_string<C,T,A2>& rhs) {
if (lhs.length() == 0) return rhs;
if (rhs.length() == 0) return lhs;
return _operator_plus<C,T,A1>(lhs.data(), lhs.length(), rhs.data(), rhs.length());
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (const C* lhs, const basic_string<C,T,A>& rhs) {
size_t llen = T::length(lhs);
if (llen == 0) return rhs;
if (rhs.length() == 0) return basic_string<C,T,A>(lhs, llen);
return _operator_plus<C,T,A>(lhs, llen, rhs.data(), rhs.length());
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (basic_string_view<C,T> lhs, const basic_string<C,T,A>& rhs) {
if (lhs.length() == 0) return rhs;
if (rhs.length() == 0) return basic_string<C,T,A>(lhs);
return _operator_plus<C,T,A>(lhs.data(), lhs.length(), rhs.data(), rhs.length());
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (C lhs, const basic_string<C,T,A>& rhs) {
if (rhs.length() == 0) return basic_string<C,T,A>(1, lhs);
return _operator_plus<C,T,A>(&lhs, 1, rhs.data(), rhs.length());
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (const basic_string<C,T,A>& lhs, const C* rhs) {
size_t rlen = T::length(rhs);
if (rlen == 0) return lhs;
if (lhs.length() == 0) return basic_string<C,T,A>(rhs, rlen);
return _operator_plus<C,T,A>(lhs.data(), lhs.length(), rhs, rlen);
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (const basic_string<C,T,A>& lhs, basic_string_view<C,T> rhs) {
if (rhs.length() == 0) return lhs;
if (lhs.length() == 0) return basic_string<C,T,A>(rhs);
return _operator_plus<C,T,A>(lhs.data(), lhs.length(), rhs.data(), rhs.length());
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (const basic_string<C,T,A>& lhs, C rhs) {
if (lhs.length() == 0) return basic_string<C,T,A>(1, rhs);
return _operator_plus<C,T,A>(lhs.data(), lhs.length(), &rhs, 1);
}
template <class C, class T, class A1, class A2>
inline basic_string<C,T,A1> operator+ (basic_string<C,T,A1>&& lhs, const basic_string<C,T,A2>& rhs) {
return std::move(lhs.append(rhs));
}
template <class C, class T, class A1, class A2>
inline basic_string<C,T,A1> operator+ (const basic_string<C,T,A1>& lhs, basic_string<C,T,A2>&& rhs) {
return std::move(rhs.insert(0, lhs));
}
template <class C, class T, class A1, class A2>
inline basic_string<C,T,A1> operator+ (basic_string<C,T,A1>&& lhs, basic_string<C,T,A2>&& rhs) {
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
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (const C* lhs, basic_string<C,T,A>&& rhs) {
return std::move(rhs.insert(0, lhs));
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (basic_string_view<C,T> lhs, basic_string<C,T,A>&& rhs) {
return std::move(rhs.insert(0, lhs));
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (C lhs, basic_string<C,T,A>&& rhs) {
return std::move(rhs.insert(0, 1, lhs));
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (basic_string<C,T,A>&& lhs, const C* rhs) {
return std::move(lhs.append(rhs));
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (basic_string<C,T,A>&& lhs, basic_string_view<C,T> rhs) {
return std::move(lhs.append(rhs));
}
template <class C, class T, class A>
inline basic_string<C,T,A> operator+ (basic_string<C,T,A>&& lhs, C rhs) {
return std::move(lhs.append(1, rhs));
}
template <class C, class T, class A>
inline std::basic_ostream<C,T>& operator<< (std::basic_ostream<C,T>& os, const basic_string<C,T,A>& str) {
return os.write(str.data(), str.length());
}
template <class C, class T, class A>
inline void swap (basic_string<C,T,A>& lhs, basic_string<C,T,A>& rhs) {
lhs.swap(rhs);
}
}
namespace std {
template<class C, class T, class A>
struct hash<panda::basic_string<C,T,A>> {
size_t operator() (const panda::basic_string<C,T,A>& s) const {
return panda::hash::hashXX<size_t>(panda::string_view((const char*)s.data(), s.length() * sizeof(C)));
}
};
template<class C, class T, class A>
struct hash<const panda::basic_string<C,T,A>> {
size_t operator() (const panda::basic_string<C,T,A>& s) const {
return panda::hash::hashXX<size_t>(panda::string_view((const char*)s.data(), s.length() * sizeof(C)));
}
};
}