| /* |
| * Copyright 2013 Facebook, Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| // @author: Andrei Alexandrescu (aalexandre) |
| // String type. |
| |
| #ifndef FOLLY_BASE_FBSTRING_H_ |
| #define FOLLY_BASE_FBSTRING_H_ |
| |
| /** |
| fbstring's behavior can be configured via two macro definitions, as |
| follows. Normally, fbstring does not write a '\0' at the end of |
| each string whenever it changes the underlying characters. Instead, |
| it lazily writes the '\0' whenever either c_str() or data() |
| called. |
| |
| This is standard-compliant behavior and may save costs in some |
| circumstances. However, it may be surprising to some client code |
| because c_str() and data() are const member functions (fbstring |
| uses the "mutable" storage class for its own state). |
| |
| In order to appease client code that expects fbstring to be |
| zero-terminated at all times, if the preprocessor symbol |
| FBSTRING_CONSERVATIVE is defined, fbstring does exactly that, |
| i.e. it goes the extra mile to guarantee a '\0' is always planted |
| at the end of its data. |
| |
| On the contrary, if the desire is to debug faulty client code that |
| unduly assumes the '\0' is present, fbstring plants a '^' (i.e., |
| emphatically NOT a zero) at the end of each string if |
| FBSTRING_PERVERSE is defined. (Calling c_str() or data() still |
| writes the '\0', of course.) |
| |
| The preprocessor symbols FBSTRING_PERVERSE and |
| FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is |
| enforced during preprocessing. |
| */ |
| |
| //#define FBSTRING_PERVERSE |
| //#define FBSTRING_CONSERVATIVE |
| |
| #ifdef FBSTRING_PERVERSE |
| #ifdef FBSTRING_CONSERVATIVE |
| #error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE. |
| #endif |
| #endif |
| |
| // This file appears in two locations: inside fbcode and in the |
| // libstdc++ source code (when embedding fbstring as std::string). |
| // To aid in this schizophrenic use, two macros are defined in |
| // c++config.h: |
| // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to |
| // gate use inside fbcode v. libstdc++ |
| #include <bits/c++config.h> |
| |
| #ifdef _LIBSTDCXX_FBSTRING |
| |
| //#pragma GCC system_header |
| |
| // Handle the cases where the fbcode version (folly/Malloc.h) is included |
| // either before or after this inclusion. |
| #ifdef FOLLY_MALLOC_H_ |
| #undef FOLLY_MALLOC_H_ |
| #include "basic_fbstring_malloc.h" |
| #else |
| #include "basic_fbstring_malloc.h" |
| #undef FOLLY_MALLOC_H_ |
| #endif |
| |
| #else // !_LIBSTDCXX_FBSTRING |
| |
| #include <string> |
| #include <cstring> |
| #include <cassert> |
| |
| #include "NAMemory.h" |
| |
| #endif |
| |
| // We defined these here rather than including Likely.h to avoid |
| // redefinition errors when fbstring is imported into libstdc++. |
| #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1)) |
| #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0)) |
| |
| //#include <atomic> |
| #include <limits> |
| #include <type_traits> |
| |
| // Ignore shadowing warnings within this file, so includers can use -Wshadow. |
| //#pragma GCC diagnostic push |
| //#pragma GCC diagnostic ignored "-Wshadow" |
| |
| #ifdef _LIBSTDCXX_FBSTRING |
| namespace std _GLIBCXX_VISIBILITY(default) { |
| _GLIBCXX_BEGIN_NAMESPACE_VERSION |
| #else |
| namespace folly { |
| #endif |
| |
| namespace fbstring_detail { |
| |
| template <class InIt, class OutIt> |
| inline |
| OutIt copy_n(InIt b, |
| typename std::iterator_traits<InIt>::difference_type n, |
| OutIt d) { |
| for (; n != 0; --n, ++b, ++d) { |
| assert((const void*)&*d != &*b); |
| *d = *b; |
| } |
| return d; |
| } |
| |
| template <class Pod, class T> |
| inline void pod_fill(Pod* b, Pod* e, T c) { |
| assert(b && e && b <= e); |
| /*static*/ if (sizeof(T) == 1) { |
| memset(b, c, e - b); |
| } else { |
| auto const ee = b + ((e - b) & ~7u); |
| for (; b != ee; b += 8) { |
| b[0] = c; |
| b[1] = c; |
| b[2] = c; |
| b[3] = c; |
| b[4] = c; |
| b[5] = c; |
| b[6] = c; |
| b[7] = c; |
| } |
| // Leftovers |
| for (; b != e; ++b) { |
| *b = c; |
| } |
| } |
| } |
| |
| /* |
| * Lightly structured memcpy, simplifies copying PODs and introduces |
| * some asserts. Unfortunately using this function may cause |
| * measurable overhead (presumably because it adjusts from a begin/end |
| * convention to a pointer/size convention, so it does some extra |
| * arithmetic even though the caller might have done the inverse |
| * adaptation outside). |
| */ |
| template <class Pod> |
| inline void pod_copy(const Pod* b, const Pod* e, Pod* d) { |
| assert(e >= b); |
| assert(d >= e || d + (e - b) <= b); |
| memcpy(d, b, (e - b) * sizeof(Pod)); |
| } |
| |
| /* |
| * Lightly structured memmove, simplifies copying PODs and introduces |
| * some asserts |
| */ |
| template <class Pod> |
| inline void pod_move(const Pod* b, const Pod* e, Pod* d) { |
| assert(e >= b); |
| memmove(d, b, (e - b) * sizeof(*b)); |
| } |
| |
| } // namespace fbstring_detail |
| |
| /** |
| * Defines a special acquisition method for constructing fbstring |
| * objects. AcquireMallocatedString means that the user passes a |
| * pointer to a malloc-allocated string that the fbstring object will |
| * take into custody. |
| */ |
| //enum class AcquireMallocatedString {}; |
| |
| /* |
| * fbstring_core_model is a mock-up type that defines all required |
| * signatures of a fbstring core. The fbstring class itself uses such |
| * a core object to implement all of the numerous member functions |
| * required by the standard. |
| * |
| * If you want to define a new core, copy the definition below and |
| * implement the primitives. Then plug the core into basic_fbstring as |
| * a template argument. |
| |
| template <class Char> |
| class fbstring_core_model { |
| public: |
| fbstring_core_model(); |
| fbstring_core_model(const fbstring_core_model &); |
| ~fbstring_core_model(); |
| // Returns a pointer to string's buffer (currently only contiguous |
| // strings are supported). The pointer is guaranteed to be valid |
| // until the next call to a non-const member function. |
| const Char * data() const; |
| // Much like data(), except the string is prepared to support |
| // character-level changes. This call is a signal for |
| // e.g. reference-counted implementation to fork the data. The |
| // pointer is guaranteed to be valid until the next call to a |
| // non-const member function. |
| Char * mutable_data(); |
| // Returns a pointer to string's buffer and guarantees that a |
| // readable '\0' lies right after the buffer. The pointer is |
| // guaranteed to be valid until the next call to a non-const member |
| // function. |
| const Char * c_str() const; |
| // Shrinks the string by delta characters. Asserts that delta <= |
| // size(). |
| void shrink(size_t delta); |
| // Expands the string by delta characters (i.e. after this call |
| // size() will report the old size() plus delta) but without |
| // initializing the expanded region. Returns a pointer to the memory |
| // to be initialized (the beginning of the expanded portion). The |
| // caller is expected to fill the expanded area appropriately. |
| Char* expand_noinit(size_t delta); |
| // Expands the string by one character and sets the last character |
| // to c. |
| void push_back(Char c); |
| // Returns the string's size. |
| size_t size() const; |
| // Returns the string's capacity, i.e. maximum size that the string |
| // can grow to without reallocation. Note that for reference counted |
| // strings that's technically a lie - even assigning characters |
| // within the existing size would cause a reallocation. |
| size_t capacity() const; |
| // Returns true if the data underlying the string is actually shared |
| // across multiple strings (in a refcounted fashion). |
| bool isShared() const; |
| // Makes sure that at least minCapacity characters are available for |
| // the string without reallocation. For reference-counted strings, |
| // it should fork the data even if minCapacity < size(). |
| void reserve(size_t minCapacity); |
| private: |
| // Do not implement |
| fbstring_core_model& operator=(const fbstring_core_model &); |
| }; |
| */ |
| |
| /** |
| * gcc-4.7 throws what appears to be some false positive uninitialized |
| * warnings for the members of the MediumLarge struct. So, mute them here. |
| */ |
| #if defined(__GNUC__) && !defined(__clang__) |
| //# pragma GCC diagnostic push |
| //# pragma GCC diagnostic ignored "-Wuninitialized" |
| #endif |
| |
| inline static size_t goodMallocSize(size_t minSize) { |
| if (minSize <= 64) { |
| // Choose smallest allocation to be 64 bytes - no tripping over |
| // cache line boundaries, and small string optimization takes care |
| // of short strings anyway. |
| return 64; |
| } |
| if (minSize <= 512) { |
| // Round up to the next multiple of 64; we don't want to trip over |
| // cache line boundaries. |
| return (minSize + 63) & ~size_t(63); |
| } |
| if (minSize <= 3840) { |
| // Round up to the next multiple of 256 |
| return (minSize + 255) & ~size_t(255); |
| } |
| if (minSize <= 4072 * 1024) { |
| // Round up to the next multiple of 4KB |
| return (minSize + 4095) & ~size_t(4095); |
| } |
| // Holy Moly |
| // Round up to the next multiple of 4MB |
| return (minSize + 4194303) & ~size_t(4194303); |
| } |
| |
| /** |
| * Allocate/reallocate memory from heap_ and check for allocation |
| * failure and throw std::bad_alloc in that case. |
| */ |
| inline static void* checkedMalloc(size_t size, NAMemory* h = NULL) { |
| void* p = NULL; |
| if(NULL == h) |
| p = malloc(size); |
| else |
| p = h->allocateMemory(size); |
| //if (!p) std::__throw_bad_alloc(); |
| return p; |
| } |
| |
| inline static void* checkedRealloc(void* ptr, size_t dataSize, size_t newSize, NAMemory* h = NULL) { |
| assert(dataSize <= newSize); |
| void* p = NULL; |
| if(NULL == h) |
| p = realloc(ptr, newSize); |
| else |
| { |
| p = h->allocateMemory(newSize); |
| //auto frgSz = NAHeapFragment::memToFragment(ptr)->fragmentSize(); |
| if(ptr!=NULL && dataSize>0) |
| { |
| std::memcpy(p, ptr, dataSize); |
| h->deallocateMemory(ptr); |
| } |
| } |
| //if (!p) std::__throw_bad_alloc(); |
| return p; |
| } |
| |
| /** |
| * This function tries to reallocate a buffer of which only the first |
| * currentSize bytes are used. The problem with using realloc is that |
| * if currentSize is relatively small _and_ if realloc decides it |
| * needs to move the memory chunk to a new buffer, then realloc ends |
| * up copying data that is not used. It's impossible to hook into |
| * GNU's malloc to figure whether expansion will occur in-place or as |
| * a malloc-copy-free troika. (If an expand_in_place primitive would |
| * be available, smartRealloc would use it.) As things stand, this |
| * routine just tries to call realloc() (thus benefitting of potential |
| * copy-free coalescing) unless there's too much slack memory. |
| */ |
| inline static void* smartRealloc(void* p, |
| const size_t currentSize, |
| const size_t currentCapacity, |
| const size_t newCapacity, NAMemory* h = NULL) { |
| assert(p); |
| assert(currentSize <= currentCapacity && |
| currentCapacity < newCapacity); |
| |
| auto const slack = currentCapacity - currentSize; |
| if (slack * 2 > currentSize) { |
| // Too much slack, malloc-copy-free cycle: |
| auto const result = checkedMalloc(newCapacity, h); |
| std::memcpy(result, p, currentSize); |
| if(NULL == h) |
| free(p); |
| else |
| h->deallocateMemory(p); |
| return result; |
| } |
| // If there's not too much slack, we realloc in hope of coalescing |
| return checkedRealloc(p, currentSize ,newCapacity, h); |
| } |
| |
| /** |
| * This is the core of the string. The code should work on 32- and |
| * 64-bit architectures and with any Char size. Porting to big endian |
| * architectures would require some changes. |
| * |
| * The storage is selected as follows (assuming we store one-byte |
| * characters on a 64-bit machine): (a) "small" strings between 0 and |
| * 23 chars are stored in-situ without allocation (the rightmost byte |
| * stores the size); (b) "medium" strings from 24 through 254 chars |
| * are stored in malloc-allocated memory that is copied eagerly; (c) |
| * "large" strings of 255 chars and above are stored in a similar |
| * structure as medium arrays, except that the string is |
| * reference-counted and copied lazily. the reference count is |
| * allocated right before the character array. |
| * |
| * The discriminator between these three strategies sits in the two |
| * most significant bits of the rightmost char of the storage. If |
| * neither is set, then the string is small (and its length sits in |
| * the lower-order bits of that rightmost character). If the MSb is |
| * set, the string is medium width. If the second MSb is set, then the |
| * string is large. |
| */ |
| template <class Char> class fbstring_core { |
| public: |
| fbstring_core(NAMemory* h) : heap_(h) { |
| ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char))); |
| // or: setSmallSize(0); |
| writeTerminator(); |
| assert(category() == isSmall && size() == 0); |
| } |
| |
| /* |
| * large strings in different heaps are not shared. |
| * if rhs is a small string, just copy the ml/small member part. |
| * if rhs is a large string, if dest str in a same heap as src str, just refcounted, |
| * if not same, allocate a refcount + data in this heap. |
| * if rhs is medium string, allocate data in this heap, and set other field. |
| */ |
| fbstring_core(const fbstring_core & rhs, NAMemory *h) : heap_(h) { |
| assert(&rhs != this); |
| // Simplest case first: small strings are bitblitted |
| if (rhs.category() == isSmall) { |
| assert(offsetof(MediumLarge, data_) == 0); |
| assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_)); |
| assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_)); |
| const size_t size = rhs.smallSize(); |
| if (size == 0) { |
| ml_.capacity_ = rhs.ml_.capacity_; |
| writeTerminator(); |
| } else { |
| // Just write the whole thing, don't look at details. In |
| // particular we need to copy capacity anyway because we want |
| // to set the size (don't forget that the last character, |
| // which stores a short string's length, is shared with the |
| // ml_.capacity field). |
| ml_ = rhs.ml_; |
| } |
| assert(category() == isSmall && this->size() == rhs.size()); |
| } else /*if (rhs.category() == isLarge)*/ { |
| if(rhs.heap() == heap_)//belong to same heap |
| { |
| // Large strings are just refcounted |
| ml_ = rhs.ml_; |
| RefCounted::incrementRefs(ml_.data_); |
| assert(category() == isLarge && size() == rhs.size()); |
| } |
| else //do not share large string in different heap |
| { |
| size_t effectiveCapacity = rhs.size(); |
| auto const newRC = RefCounted::create(rhs.data(), & effectiveCapacity, heap_); |
| ml_.data_ = newRC->data_; |
| ml_.size_ = rhs.size(); |
| ml_.capacity_ = effectiveCapacity | isLarge; |
| writeTerminator(); |
| } |
| } /*else { |
| // Medium strings are copied eagerly. Don't forget to allocate |
| // one extra Char for the null terminator. |
| auto const allocSize = |
| goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char)); |
| ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize, heap_)); |
| fbstring_detail::pod_copy(rhs.ml_.data_, |
| // 1 for terminator |
| rhs.ml_.data_ + rhs.ml_.size_ + 1, |
| ml_.data_); |
| // No need for writeTerminator() here, we copied one extra |
| // element just above. |
| ml_.size_ = rhs.ml_.size_; |
| ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium; |
| assert(category() == isMedium); |
| }*/ |
| assert(size() == rhs.size()); |
| assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0); |
| } // fbstring_core ctor |
| |
| |
| /* |
| //Move constructor |
| fbstring_core(fbstring_core&& goner, NAMemory *h) : heap_(h) { |
| //assert(heap_); |
| // if h is uninitialized, then use the (derived) string class's default heap instead |
| //NAMemory * heap_ = (h == NASTRING_UNINIT_HEAP_PTR) ? this->defaultHeapPtr() : h ; |
| if (goner.category() == isSmall) { |
| // Just copy, leave the goner in peace |
| new(this) fbstring_core(goner.small_, goner.smallSize(), h); |
| } else { |
| // Take goner's guts |
| ml_ = goner.ml_; |
| // Clean goner's carcass |
| goner.setSmallSize(0); |
| } |
| } |
| */ |
| |
| /*construct three kinds of fbstring_core depending on size,*/ |
| fbstring_core(const Char *const data, const size_t size, NAMemory *h) : heap_(h) { |
| assert(data); |
| // Simplest case first: small strings are bitblitted |
| if (size <= maxSmallSize) { |
| // Layout is: Char* data_, size_t size_, size_t capacity_ |
| /*static_*/assert(sizeof(*this) == sizeof(NAMemory*) + sizeof(Char*) + 2 * sizeof(size_t)); |
| /*static_*/assert(sizeof(Char*) == sizeof(size_t)); |
| // sizeof(size_t) must be a power of 2 |
| /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0); |
| |
| // If data is aligned, use fast word-wise copying. Otherwise, |
| // use conservative memcpy. |
| if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) { |
| fbstring_detail::pod_copy(data, data + size, small_); |
| } else { |
| // Copy one word (64 bits) at a time |
| const size_t byteSize = size * sizeof(Char); |
| if (byteSize > 2 * sizeof(size_t)) { |
| // Copy three words |
| ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2]; |
| copyTwo: |
| ml_.size_ = reinterpret_cast<const size_t*>(data)[1]; |
| copyOne: |
| ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data)); |
| } else if (byteSize > sizeof(size_t)) { |
| // Copy two words |
| goto copyTwo; |
| } else if (size > 0) { |
| // Copy one word |
| goto copyOne; |
| } |
| } |
| setSmallSize(size); |
| }/* else if (size <= maxMediumSize) { |
| // Medium strings are allocated normally. Don't forget to |
| // allocate one extra Char for the terminating null. |
| auto const allocSize = goodMallocSize((1 + size) * sizeof(Char)); |
| ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize, heap_)); |
| fbstring_detail::pod_copy(data, data + size, ml_.data_); |
| ml_.size_ = size; |
| ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium; |
| }*/ else { |
| // Large strings are allocated differently |
| size_t effectiveCapacity = size; |
| auto const newRC = RefCounted::create(data, & effectiveCapacity, heap_); |
| ml_.data_ = newRC->data_; |
| ml_.size_ = size; |
| ml_.capacity_ = effectiveCapacity | isLarge; |
| } |
| writeTerminator(); |
| assert(this->size() == size); |
| assert(memcmp(this->data(), data, size * sizeof(Char)) == 0); |
| } |
| |
| ~fbstring_core() { |
| auto const c = category(); |
| if (c == isSmall) { |
| return; |
| } |
| /* |
| if (c == isMedium) { |
| if(0 == heap_) |
| free(ml_.data_); |
| else |
| heap_->deallocateMemory(ml_.data_); |
| return; |
| } |
| */ |
| RefCounted::decrementRefs(ml_.data_, heap_); |
| } |
| |
| |
| // In C++11 data() and c_str() are 100% equivalent. |
| const Char * data() const { |
| return c_str(); |
| } |
| |
| //return data buffer which can be changed |
| //will make unique for large string |
| Char * mutable_data() { |
| auto const c = category(); |
| if (c == isSmall) { |
| //make sure '\0' is presented at end |
| small_[smallSize()] = '\0'; |
| return small_; |
| } |
| assert(/*c == isMedium || */c == isLarge); |
| if (c == isLarge && RefCounted::refs(ml_.data_) > 1) { |
| // Ensure unique. |
| size_t effectiveCapacity = ml_.capacity(); |
| auto const newRC = RefCounted::create(& effectiveCapacity, heap_); |
| // If this fails, someone placed the wrong capacity in an |
| // fbstring. |
| assert(effectiveCapacity >= ml_.capacity()); |
| fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1, |
| newRC->data_); |
| RefCounted::decrementRefs(ml_.data_, heap_); |
| ml_.data_ = newRC->data_; |
| // No need to call writeTerminator(), we have + 1 above. |
| } |
| //make sure '\0' is presented at end |
| ml_.data_[ml_.size_] = '\0'; |
| return ml_.data_; |
| } |
| |
| const Char * c_str() const { |
| auto const c = category(); |
| #ifdef FBSTRING_PERVERSE |
| if (c == isSmall) { |
| assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize |
| || small_[smallSize()] == '\0'); |
| small_[smallSize()] = '\0'; |
| return small_; |
| } |
| assert(/*c == isMedium ||*/ c == isLarge); |
| assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0'); |
| ml_.data_[ml_.size_] = '\0'; |
| #elif defined(FBSTRING_CONSERVATIVE) |
| if (c == isSmall) { |
| assert(small_[smallSize()] == '\0'); |
| return small_; |
| } |
| assert(/*c == isMedium || */c == isLarge); |
| assert(ml_.data_[ml_.size_] == '\0'); |
| #else |
| if (c == isSmall) { |
| small_[smallSize()] = '\0'; |
| return small_; |
| } |
| assert(/*c == isMedium || */c == isLarge); |
| ml_.data_[ml_.size_] = '\0'; |
| #endif |
| return ml_.data_; |
| } |
| |
| //shrink size |
| void shrink(const size_t delta) { |
| if (category() == isSmall) { |
| // Check for underflow |
| assert(delta <= smallSize()); |
| setSmallSize(smallSize() - delta); |
| } else if (/*category() == isMedium || */RefCounted::refs(ml_.data_) == 1) { |
| // Medium strings and unique large strings need no special |
| // handling. |
| assert(ml_.size_ >= delta); |
| ml_.size_ -= delta; |
| } else { |
| assert(ml_.size_ >= delta); |
| // Shared large string, must make unique. This is because of the |
| // durn terminator must be written, which may trample the shared |
| // data. |
| if (delta) { |
| fbstring_core(ml_.data_, ml_.size_ - delta, heap_).swap(*this); |
| } |
| // No need to write the terminator. |
| return; |
| } |
| writeTerminator(); |
| } |
| |
| //key function to enlarge capacity, |
| //for large string make new allocation and detach from shared string, |
| //regardless minCapacity larger or smaller than current, |
| //for medium string only reallocate when minCapacity is larger. |
| void reserve(size_t minCapacity) { |
| if (category() == isLarge) { |
| // Ensure unique |
| if (RefCounted::refs(ml_.data_) > 1) { |
| // We must make it unique regardless; in-place reallocation is |
| // useless if the string is shared. In order to not surprise |
| // people, reserve the new block at current capacity or |
| // more. That way, a string's capacity never shrinks after a |
| // call to reserve. |
| minCapacity = std::max(minCapacity, ml_.capacity()); |
| auto const newRC = RefCounted::create(& minCapacity, heap_); |
| fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1, |
| newRC->data_); |
| // Done with the old data. No need to call writeTerminator(), |
| // we have + 1 above. |
| RefCounted::decrementRefs(ml_.data_, heap_); |
| ml_.data_ = newRC->data_; |
| ml_.capacity_ = minCapacity | isLarge; |
| // size remains unchanged |
| } else { |
| // String is not shared, so let's try to realloc (if needed) |
| if (minCapacity > ml_.capacity()) { |
| // Asking for more memory |
| auto const newRC = |
| RefCounted::reallocate(ml_.data_, ml_.size_, |
| ml_.capacity(), minCapacity, heap_); |
| ml_.data_ = newRC->data_; |
| ml_.capacity_ = minCapacity | isLarge; |
| writeTerminator(); |
| } |
| assert(capacity() >= minCapacity); |
| } |
| }/* else if (category() == isMedium) { |
| // String is not shared |
| if (minCapacity <= ml_.capacity()) { |
| return; // nothing to do, there's enough room |
| } |
| if (minCapacity <= maxMediumSize) { |
| // Keep the string at medium size. Don't forget to allocate |
| // one extra Char for the terminating null. |
| size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char)); |
| ml_.data_ = static_cast<Char *>( |
| smartRealloc( |
| ml_.data_, |
| ml_.size_ * sizeof(Char), |
| ml_.capacity() * sizeof(Char), |
| capacityBytes, heap_)); |
| writeTerminator(); |
| ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium; |
| } else { |
| // Conversion from medium to large string |
| fbstring_core nascent(heap_); |
| // Will recurse to another branch of this function |
| nascent.reserve(minCapacity); |
| nascent.ml_.size_ = ml_.size_; |
| fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_, |
| nascent.ml_.data_); |
| nascent.swap(*this); |
| writeTerminator(); |
| assert(capacity() >= minCapacity); |
| } |
| } */else { |
| assert(category() == isSmall); |
| if (minCapacity > maxSmallSize/*maxMediumSize*/) { |
| // large |
| auto const newRC = RefCounted::create(& minCapacity, heap_); |
| auto const size = smallSize(); |
| fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_); |
| // No need for writeTerminator(), we wrote it above with + 1. |
| ml_.data_ = newRC->data_; |
| ml_.size_ = size; |
| ml_.capacity_ = minCapacity | isLarge; |
| assert(capacity() >= minCapacity); |
| } /*else if (minCapacity > maxSmallSize) { |
| // medium |
| // Don't forget to allocate one extra Char for the terminating null |
| auto const allocSizeBytes = |
| goodMallocSize((1 + minCapacity) * sizeof(Char)); |
| auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes, heap_)); |
| auto const size = smallSize(); |
| fbstring_detail::pod_copy(small_, small_ + size + 1, data); |
| // No need for writeTerminator(), we wrote it above with + 1. |
| ml_.data_ = data; |
| ml_.size_ = size; |
| ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium; |
| } */else { |
| // small |
| // Nothing to do, everything stays put |
| } |
| } |
| assert(capacity() >= minCapacity); |
| } |
| |
| //expand size by delta , enlarge capacity if needed, |
| //return start of newly expanded memory |
| Char * expand_noinit(const size_t delta) { |
| // Strategy is simple: make room, then change size |
| assert(capacity() >= size()); |
| size_t sz, newSz; |
| if (category() == isSmall) { |
| sz = smallSize(); |
| newSz = sz + delta; |
| if (newSz <= maxSmallSize) { |
| setSmallSize(newSz); |
| writeTerminator(); |
| return small_ + sz; |
| } |
| reserve(newSz); |
| } else { |
| sz = ml_.size_; |
| newSz = ml_.size_ + delta; |
| if (newSz > capacity()) { |
| reserve(newSz); |
| } |
| } |
| assert(capacity() >= newSz); |
| // Category can't be small - we took care of that above |
| assert(/*category() == isMedium || */category() == isLarge); |
| ml_.size_ = newSz; |
| writeTerminator(); |
| assert(size() == newSz); |
| return ml_.data_ + sz; |
| } |
| |
| // swap below doesn't test whether &rhs == this (and instead |
| // potentially does extra work) on the premise that the rarity of |
| // that situation actually makes the check more expensive than is |
| // worth. |
| void swap(fbstring_core & rhs) { |
| if(rhs.heap() == heap_) |
| { |
| auto const t = ml_; |
| ml_ = rhs.ml_; |
| rhs.ml_ = t; |
| } |
| else//swap strings in different heap, including small, medium, and large |
| { |
| fbstring_core temp_this_heap(rhs.data(), rhs.size(), heap_); |
| fbstring_core temp_rhs_heap(data(), size(), rhs.heap()); |
| swap(temp_this_heap); |
| rhs.swap(temp_rhs_heap); |
| } |
| } |
| |
| void push_back(Char c) { |
| assert(capacity() >= size()); |
| size_t sz; |
| if (category() == isSmall) { |
| sz = smallSize(); |
| if (sz < maxSmallSize) { |
| setSmallSize(sz + 1); |
| small_[sz] = c; |
| writeTerminator(); |
| return; |
| } |
| reserve(maxSmallSize * 2); |
| } else { |
| sz = ml_.size_; |
| if (sz == capacity()) { // always true for isShared() |
| reserve(sz * 3 / 2); // ensures not shared |
| } |
| } |
| assert(!isShared()); |
| assert(capacity() >= sz + 1); |
| // Category can't be small - we took care of that above |
| assert(/*category() == isMedium ||*/category() == isLarge); |
| ml_.size_ = sz + 1; |
| ml_.data_[sz] = c; |
| writeTerminator(); |
| } |
| |
| //size in unit of charactors not bytes. |
| size_t size() const { |
| return category() == isSmall ? smallSize() : ml_.size_; |
| } |
| |
| //capacity also in unit of charactors not bytes. |
| size_t capacity() const { |
| switch (category()) { |
| case isSmall: |
| return maxSmallSize; |
| case isLarge: |
| // For large-sized strings, a multi-referenced chunk has no |
| // available capacity. This is because any attempt to append |
| // data would trigger a new allocation. |
| if (RefCounted::refs(ml_.data_) > 1) return ml_.size_; |
| default: {} |
| } |
| return ml_.capacity(); |
| } |
| //only large string needs to be shared, and then needs RefCounted. |
| bool isShared() const { |
| return category() == isLarge && RefCounted::refs(ml_.data_) > 1; |
| } |
| //return pointer of dynamic memory heap |
| NAMemory* heap() const |
| { |
| return heap_; |
| } |
| //refs == 0 means this is a small or medium string |
| size_t refs() const |
| { |
| if (category() == isLarge) |
| return RefCounted::refs(ml_.data_); |
| else |
| return 0; |
| } |
| #ifdef FBSTRING_PERVERSE |
| enum { TERMINATOR = '^' }; |
| #else |
| enum { TERMINATOR = '\0' }; |
| #endif |
| |
| void writeTerminator() { |
| #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE) |
| if (category() == isSmall) { |
| const auto s = smallSize(); |
| if (s != maxSmallSize) { |
| small_[s] = TERMINATOR; |
| } |
| } else { |
| ml_.data_[ml_.size_] = TERMINATOR; |
| } |
| #endif |
| } |
| size_t get_alloc_size() const |
| { |
| if(category() == isLarge) |
| { |
| return (ml_.capacity()+1)*sizeof(Char) + sizeof(RefCounted); |
| } |
| /* |
| else if(category() == isMedium) |
| { |
| return (ml_.capacity()+1)*sizeof(Char); |
| } |
| */ |
| else |
| return 0; |
| } |
| private: |
| // Disabled |
| fbstring_core & operator=(const fbstring_core & rhs); |
| fbstring_core(const fbstring_core & rhs); |
| |
| NAMemory* heap_; |
| |
| struct MediumLarge { |
| Char * data_; |
| size_t size_; |
| size_t capacity_; |
| public: |
| size_t capacity() const { |
| return capacity_ & capacityExtractMask; |
| } |
| }; |
| private: |
| struct RefCounted { |
| //std::atomic<size_t> refCount_; |
| size_t refCount_; |
| Char data_[1]; |
| |
| static RefCounted * fromData(Char * p) { |
| return static_cast<RefCounted*>( |
| static_cast<void*>( |
| static_cast<unsigned char*>(static_cast<void*>(p)) |
| - sizeof(refCount_))); |
| } |
| |
| static size_t refs(Char * p) { |
| //return fromData(p)->refCount_.load(std::memory_order_acquire); |
| return fromData(p)->refCount_; |
| } |
| |
| static void incrementRefs(Char * p) { |
| //fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel); |
| fromData(p)->refCount_ += 1; |
| } |
| |
| static void decrementRefs(Char * p, NAMemory *h) { |
| auto const dis = fromData(p); |
| //size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel); |
| //save previous value to oldcnt |
| size_t oldcnt = dis->refCount_; |
| dis->refCount_ -= 1; |
| assert(oldcnt > 0); |
| if (oldcnt == 1) { |
| if(0 == h) |
| free(dis); |
| else |
| h->deallocateMemory(dis); |
| } |
| } |
| |
| static RefCounted * create(size_t * size, NAMemory* h) { |
| // Don't forget to allocate one extra Char for the terminating |
| // null. In this case, however, one Char is already part of the |
| // struct. |
| const size_t allocSize = goodMallocSize( |
| sizeof(RefCounted) + *size * sizeof(Char)); |
| auto result = static_cast<RefCounted*>(checkedMalloc(allocSize, h)); |
| //result->refCount_.store(1, std::memory_order_release); |
| result->refCount_ = 1; |
| *size = (allocSize - sizeof(RefCounted)) / sizeof(Char); |
| return result; |
| } |
| |
| static RefCounted * create(const Char * data, size_t * size, NAMemory* h) { |
| const size_t effectiveSize = *size; |
| auto result = create(size, h); |
| fbstring_detail::pod_copy(data, data + effectiveSize, result->data_); |
| return result; |
| } |
| |
| static RefCounted * reallocate(Char *const data, |
| const size_t currentSize, |
| const size_t currentCapacity, |
| const size_t newCapacity, NAMemory* h) { |
| assert(newCapacity > 0 && newCapacity > currentSize); |
| auto const dis = fromData(data); |
| //assert(dis->refCount_.load(std::memory_order_acquire) == 1); |
| assert(dis->refCount_ == 1); |
| // Don't forget to allocate one extra Char for the terminating |
| // null. In this case, however, one Char is already part of the |
| // struct. |
| auto result = static_cast<RefCounted*>( |
| smartRealloc(dis, |
| sizeof(RefCounted) + currentSize * sizeof(Char), |
| sizeof(RefCounted) + currentCapacity * sizeof(Char), |
| sizeof(RefCounted) + newCapacity * sizeof(Char), h)); |
| //assert(result->refCount_.load(std::memory_order_acquire) == 1); |
| assert(result->refCount_ == 1); |
| return result; |
| } |
| }; |
| |
| union { |
| mutable Char small_[sizeof(MediumLarge) / sizeof(Char)]; |
| mutable MediumLarge ml_; |
| }; |
| |
| public : |
| |
| enum { |
| lastChar = sizeof(MediumLarge) - 1, |
| maxSmallSize = lastChar / sizeof(Char), |
| //maxMediumSize = 254 / sizeof(Char), // coincides with the small |
| // bin size in dlmalloc |
| categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000, |
| capacityExtractMask = ~categoryExtractMask, |
| }; |
| static_assert(!(sizeof(MediumLarge) % sizeof(Char)), |
| "Corrupt memory layout for fbstring."); |
| |
| enum Category { |
| isSmall = 0, |
| //isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000, |
| isLarge = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000, |
| }; |
| /* Which categorys string belongs to not always decided by its capacity or size. |
| * It is decided when it's constructed and won't change until: |
| * 1. reserve(), expand_noinit() called, causing capacity/capacity to enlarge. |
| * 2. swap() called causing string object to another small/medium/large string. |
| * so it is possible that a large category string with a size of 16, but capacity 255 or more. |
| * the wired thing is medium string can have a max capacity of 255 which overlaps with large |
| * string, we can not decide a string category purely by size/capacity. |
| * but small string's capacity won't exceed maxSmallSize, medium string's capacity may little |
| * greater than maxMediumSize. |
| */ |
| Category category() const { |
| // Assumes little endian |
| return static_cast<Category>(ml_.capacity_ & categoryExtractMask); |
| } |
| |
| size_t smallSize() const { |
| assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize); |
| return static_cast<size_t>(maxSmallSize) |
| - static_cast<size_t>(small_[maxSmallSize]); |
| } |
| |
| void setSmallSize(size_t s) { |
| // Warning: this should work with uninitialized strings too, |
| // so don't assume anything about the previous value of |
| // small_[maxSmallSize]. |
| assert(s <= maxSmallSize); |
| small_[maxSmallSize] = maxSmallSize - s; |
| } |
| }; |
| |
| #if defined(__GNUC__) && !defined(__clang__) |
| //# pragma GCC diagnostic pop |
| #endif |
| |
| #ifndef _LIBSTDCXX_FBSTRING |
| /** |
| * Dummy fbstring core that uses an actual std::string. This doesn't |
| * make any sense - it's just for testing purposes. |
| */ |
| template <class Char> |
| class dummy_fbstring_core { |
| public: |
| dummy_fbstring_core() { |
| } |
| dummy_fbstring_core(const dummy_fbstring_core& another) |
| : backend_(another.backend_) { |
| } |
| dummy_fbstring_core(const Char * s, size_t n) |
| : backend_(s, n) { |
| } |
| void swap(dummy_fbstring_core & rhs) { |
| backend_.swap(rhs.backend_); |
| } |
| const Char * data() const { |
| return backend_.data(); |
| } |
| Char * mutable_data() { |
| //assert(!backend_.empty()); |
| return &*backend_.begin(); |
| } |
| void shrink(size_t delta) { |
| assert(delta <= size()); |
| backend_.resize(size() - delta); |
| } |
| Char * expand_noinit(size_t delta) { |
| auto const sz = size(); |
| backend_.resize(size() + delta); |
| return backend_.data() + sz; |
| } |
| void push_back(Char c) { |
| backend_.push_back(c); |
| } |
| size_t size() const { |
| return backend_.size(); |
| } |
| size_t capacity() const { |
| return backend_.capacity(); |
| } |
| bool isShared() const { |
| return false; |
| } |
| void reserve(size_t minCapacity) { |
| backend_.reserve(minCapacity); |
| } |
| |
| private: |
| std::basic_string<Char> backend_; |
| }; |
| #endif // !_LIBSTDCXX_FBSTRING |
| |
| /** |
| * This is the basic_string replacement. For conformity, |
| * basic_fbstring takes the same template parameters, plus the last |
| * one which is the core. |
| */ |
| #ifdef _LIBSTDCXX_FBSTRING |
| template <typename E, class T, class A, class Storage> |
| #else |
| template <typename E, |
| class T = std::char_traits<E>, |
| class A = std::allocator<E>, |
| class Storage = fbstring_core<E> > |
| #endif |
| class basic_fbstring { |
| static void enforce( |
| bool condition, |
| void (*throw_exc)(const char*), |
| const char* msg) { |
| if (!condition) throw_exc(msg); |
| } |
| |
| bool isSane() const { |
| return |
| begin() <= end() && |
| empty() == (size() == 0) && |
| empty() == (begin() == end()) && |
| size() <= max_size() && |
| capacity() <= max_size() && |
| size() <= capacity() && |
| (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0'); |
| } |
| |
| struct Invariant; |
| friend struct Invariant; |
| struct Invariant { |
| #ifndef NDEBUG |
| explicit Invariant(const basic_fbstring& s) : s_(s) { |
| assert(s_.isSane()); |
| } |
| ~Invariant() { |
| assert(s_.isSane()); |
| } |
| private: |
| const basic_fbstring& s_; |
| #else |
| explicit Invariant(const basic_fbstring&) {} |
| #endif |
| Invariant& operator=(const Invariant&); |
| }; |
| |
| public: |
| // types |
| typedef T traits_type; |
| typedef typename traits_type::char_type value_type; |
| typedef A allocator_type; |
| typedef typename A::size_type size_type; |
| typedef typename A::difference_type difference_type; |
| |
| typedef typename A::reference reference; |
| typedef typename A::const_reference const_reference; |
| typedef typename A::pointer pointer; |
| typedef typename A::const_pointer const_pointer; |
| |
| typedef E* iterator; |
| typedef const E* const_iterator; |
| typedef std::reverse_iterator<iterator |
| #ifdef NO_ITERATOR_TRAITS |
| , value_type |
| #endif |
| > reverse_iterator; |
| typedef std::reverse_iterator<const_iterator |
| #ifdef NO_ITERATOR_TRAITS |
| , const value_type |
| #endif |
| > const_reverse_iterator; |
| |
| static const size_type npos; // = size_type(-1) |
| |
| private: |
| //equal to smaller one |
| static void procrustes(size_type& n, size_type nmax) { |
| if (n > nmax) n = nmax; |
| } |
| |
| public: |
| |
| // C++11 21.4.2 construct/copy/destroy |
| //explicit basic_fbstring(const A& a = A()) { |
| //} |
| explicit basic_fbstring(NAMemory* h = 0) |
| : store_(h) |
| {} |
| |
| basic_fbstring(const basic_fbstring& str, NAMemory* h = 0) |
| : store_(str.store_, h) { |
| } |
| |
| /* |
| // Move constructor |
| basic_fbstring(basic_fbstring&& goner, NAMemory* h = 0) |
| : store_(std::move(goner.store_), h) { |
| } |
| */ |
| |
| #ifndef _LIBSTDCXX_FBSTRING |
| // This is defined for compatibility with std::string |
| /* implicit */ basic_fbstring(const std::string& str, NAMemory* h = 0) |
| : store_(str.data(), str.size(), h) { |
| } |
| #endif |
| |
| basic_fbstring(const basic_fbstring& str, size_type pos, |
| size_type n = npos, NAMemory* h = 0) |
| : store_(h) |
| { |
| assign(str, pos, n); |
| } |
| |
| /* implicit */ basic_fbstring(const value_type* s, NAMemory* h = 0) |
| : store_(s, s ? traits_type::length(s) : ({ |
| basic_fbstring<char> err = __PRETTY_FUNCTION__; |
| err += ": null pointer initializer not valid"; |
| std::__throw_logic_error(err.c_str()); |
| 0; |
| }), h) { |
| } |
| |
| basic_fbstring(const value_type* s, size_type n, NAMemory* h = 0) |
| : store_(s , n, h) { |
| } |
| |
| basic_fbstring(size_type n, value_type c, NAMemory* h = 0) |
| : store_(h) |
| { |
| assert(n >=0); |
| auto const data = store_.expand_noinit(n); |
| fbstring_detail::pod_fill(data, data + n, c); |
| store_.writeTerminator(); |
| } |
| |
| template <class InIt> |
| basic_fbstring(InIt begin, InIt end, |
| NAMemory* h) |
| : store_(h) |
| { |
| assign(begin, end); |
| } |
| |
| // Specialization for const char*, const char* |
| basic_fbstring(const value_type* b, const value_type* e, NAMemory* h = 0) |
| : store_(b, e - b, h) { |
| } |
| |
| // Nonstandard constructor |
| // basic_fbstring(value_type *s, size_type n, size_type c, |
| // AcquireMallocatedString a, NAMemory* h = NASTRING_UNINIT_HEAP_PTR) |
| // : store_(s, n, c, a, (h == NASTRING_UNINIT_HEAP_PTR)?this->defaultHeapPtr():h) { |
| // }sqf/seapilot/source/regressions/run_tests |
| /* |
| // Construction from initialization list |
| basic_fbstring(std::initializer_list<value_type> il, NAMemory* h = NASTRING_UNINIT_HEAP_PTR) { |
| assign(il.begin(), il.end()); |
| } |
| */ |
| ~basic_fbstring() { |
| } |
| |
| basic_fbstring& operator=(const basic_fbstring& lhs) { |
| if (FBSTRING_UNLIKELY(&lhs == this)) { |
| return *this; |
| } |
| auto const oldSize = size(); |
| auto const srcSize = lhs.size(); |
| if (capacity() >= srcSize && !store_.isShared()) { |
| // great, just copy the contents |
| if (oldSize < srcSize) |
| store_.expand_noinit(srcSize - oldSize); |
| else |
| store_.shrink(oldSize - srcSize); |
| assert(size() == srcSize); |
| fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin()); |
| store_.writeTerminator(); |
| } else { |
| // need to reallocate, so we may as well create a brand new string |
| basic_fbstring(lhs, store_.heap()).swap(*this); |
| } |
| return *this; |
| } |
| /* |
| // Move assignment |
| basic_fbstring& operator=(basic_fbstring&& goner) { |
| if (FBSTRING_UNLIKELY(&goner == this)) { |
| // Compatibility with std::basic_string<>, |
| // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support. |
| return *this; |
| } |
| // No need of this anymore |
| this->~basic_fbstring(); |
| // Move the goner into this |
| new(&store_) fbstring_core<E>(std::move(goner.store_), store_.heap_); |
| cout << "{{" << __PRETTY_FUNCTION__ << "}}" <<endl; |
| return *this; |
| } |
| */ |
| |
| #ifndef _LIBSTDCXX_FBSTRING |
| // Compatibility with std::string |
| basic_fbstring & operator=(const std::string & rhs) { |
| return assign(rhs.data(), rhs.size()); |
| } |
| |
| // Compatibility with std::string |
| std::string toStdString() const { |
| return std::string(data(), size()); |
| } |
| #else |
| // A lot of code in fbcode still uses this method, so keep it here for now. |
| const basic_fbstring& toStdString() const { |
| return *this; |
| } |
| #endif |
| const Storage & store() const { return store_; } |
| |
| NAMemory* heap() const { return store_.heap();} |
| |
| size_t get_alloc_size() const |
| { |
| return store_.get_alloc_size(); |
| } |
| |
| basic_fbstring& operator=(const value_type* s) { |
| return assign(s); |
| } |
| |
| basic_fbstring& operator=(value_type c) { |
| if (empty()) { |
| store_.expand_noinit(1); |
| } else if (store_.isShared()) { |
| basic_fbstring(1, c, store_.heap()).swap(*this); |
| return *this; |
| } else { |
| store_.shrink(size() - 1); |
| } |
| *store_.mutable_data() = c; |
| store_.writeTerminator(); |
| return *this; |
| } |
| |
| basic_fbstring& operator=(std::initializer_list<value_type> il) { |
| return assign(il.begin(), il.end()); |
| } |
| |
| // C++11 21.4.3 iterators: |
| iterator begin() { return store_.mutable_data(); } |
| |
| const_iterator begin() const { return store_.data(); } |
| |
| const_iterator cbegin() const { return begin(); } |
| |
| iterator end() { |
| return store_.mutable_data() + store_.size(); |
| } |
| |
| const_iterator end() const { |
| return store_.data() + store_.size(); |
| } |
| |
| const_iterator cend() const { return end(); } |
| |
| reverse_iterator rbegin() { |
| return reverse_iterator(end()); |
| } |
| |
| const_reverse_iterator rbegin() const { |
| return const_reverse_iterator(end()); |
| } |
| |
| const_reverse_iterator crbegin() const { return rbegin(); } |
| |
| reverse_iterator rend() { |
| return reverse_iterator(begin()); |
| } |
| |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(begin()); |
| } |
| |
| const_reverse_iterator crend() const { return rend(); } |
| |
| // Added by C++11 |
| // C++11 21.4.5, element access: |
| const value_type& front() const { return *begin(); } |
| const value_type& back() const { |
| assert(!empty()); |
| // Should be begin()[size() - 1], but that branches twice |
| return *(end() - 1); |
| } |
| value_type& front() { return *begin(); } |
| value_type& back() { |
| assert(!empty()); |
| // Should be begin()[size() - 1], but that branches twice |
| return *(end() - 1); |
| } |
| void pop_back() { |
| assert(!empty()); |
| store_.shrink(1); |
| } |
| |
| // C++11 21.4.4 capacity: |
| size_type size() const { return store_.size(); } |
| |
| size_type length() const { return size(); } |
| |
| size_type max_size() const { |
| return std::numeric_limits<size_type>::max(); |
| } |
| |
| void resize(const size_type n, const value_type c = value_type()) { |
| auto size = this->size(); |
| if (n <= size) { |
| store_.shrink(size - n); |
| } else { |
| // Do this in two steps to minimize slack memory copied (see |
| // smartRealloc). |
| auto const capacity = this->capacity(); |
| assert(capacity >= size); |
| if (size < capacity) { |
| auto delta = std::min(n, capacity) - size; |
| store_.expand_noinit(delta); |
| fbstring_detail::pod_fill(begin() + size, end(), c); |
| size += delta; |
| if (size == n) { |
| store_.writeTerminator(); |
| return; |
| } |
| assert(size < n); |
| } |
| auto const delta = n - size; |
| store_.expand_noinit(delta); |
| fbstring_detail::pod_fill(end() - delta, end(), c); |
| store_.writeTerminator(); |
| } |
| assert(this->size() == n); |
| } |
| |
| size_type capacity() const { return store_.capacity(); } |
| |
| void reserve(size_type res_arg = 0) { |
| enforce(res_arg <= max_size(), std::__throw_length_error, ""); |
| store_.reserve(res_arg); |
| } |
| |
| void shrink_to_fit() { |
| // Shrink only if slack memory is sufficiently large |
| if (capacity() < size() * 3 / 2) { |
| return; |
| } |
| basic_fbstring(cbegin(), cend(), store_.heap()).swap(*this); |
| } |
| |
| void clear() { resize(0); } |
| |
| bool empty() const { return size() == 0; } |
| |
| // C++11 21.4.5 element access: |
| const_reference operator[](size_type pos) const { |
| return *(c_str() + pos); |
| } |
| |
| reference operator[](size_type pos) { |
| if (pos == size()) { |
| // Just call c_str() to make sure '\0' is present |
| c_str(); |
| } |
| return *(begin() + pos); |
| } |
| |
| const_reference at(size_type n) const { |
| enforce(n <= size(), std::__throw_out_of_range, ""); |
| return (*this)[n]; |
| } |
| |
| reference at(size_type n) { |
| enforce(n < size(), std::__throw_out_of_range, ""); |
| return (*this)[n]; |
| } |
| |
| // C++11 21.4.6 modifiers: |
| basic_fbstring& operator+=(const basic_fbstring& str) { |
| return append(str); |
| } |
| |
| basic_fbstring& operator+=(const value_type* s) { |
| return append(s); |
| } |
| |
| basic_fbstring& operator+=(const value_type c) { |
| push_back(c); |
| return *this; |
| } |
| |
| basic_fbstring& operator+=(std::initializer_list<value_type> il) { |
| append(il); |
| return *this; |
| } |
| |
| basic_fbstring& append(const basic_fbstring& str) { |
| #ifndef NDEBUG |
| auto desiredSize = size() + str.size(); |
| #endif |
| append(str.data(), str.size()); |
| assert(size() == desiredSize); |
| return *this; |
| } |
| |
| basic_fbstring& append(const basic_fbstring& str, const size_type pos, |
| size_type n) { |
| const size_type sz = str.size(); |
| enforce(pos <= sz, std::__throw_out_of_range, ""); |
| procrustes(n, sz - pos); |
| return append(str.data() + pos, n); |
| } |
| |
| basic_fbstring& append(const value_type* s, size_type n) { |
| #ifndef NDEBUG |
| Invariant checker(*this); |
| (void) checker; |
| #endif |
| if (FBSTRING_UNLIKELY(!n)) { |
| // Unlikely but must be done |
| return *this; |
| } |
| auto const oldSize = size(); |
| auto const oldData = data(); |
| // Check for aliasing (rare). We could use "<=" here but in theory |
| // those do not work for pointers unless the pointers point to |
| // elements in the same array. For that reason we use |
| // std::less_equal, which is guaranteed to offer a total order |
| // over pointers. See discussion at http://goo.gl/Cy2ya for more |
| // info. |
| std::less_equal<const value_type*> le; |
| if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) { |
| assert(le(s + n, oldData + oldSize)); |
| const size_type offset = s - oldData; |
| store_.reserve(oldSize + n); |
| // Restore the source |
| s = data() + offset; |
| } |
| // Warning! Repeated appends with short strings may actually incur |
| // practically quadratic performance. Avoid that by pushing back |
| // the first character (which ensures exponential growth) and then |
| // appending the rest normally. Worst case the append may incur a |
| // second allocation but that will be rare. |
| push_back(*s++); |
| --n; |
| memcpy(store_.expand_noinit(n), s, n * sizeof(value_type)); |
| assert(size() == oldSize + n + 1); |
| return *this; |
| } |
| |
| basic_fbstring& append(const value_type* s) { |
| return append(s, traits_type::length(s)); |
| } |
| |
| basic_fbstring& append(size_type n, value_type c) { |
| resize(size() + n, c); |
| return *this; |
| } |
| |
| template<class InputIterator> |
| basic_fbstring& append(InputIterator first, InputIterator last) { |
| insert(end(), first, last); |
| return *this; |
| } |
| |
| basic_fbstring& append(std::initializer_list<value_type> il) { |
| return append(il.begin(), il.end()); |
| } |
| |
| void push_back(const value_type c) { // primitive |
| store_.push_back(c); |
| } |
| |
| basic_fbstring& assign(const basic_fbstring& str) { |
| if (&str == this) return *this; |
| return assign(str.data(), str.size()); |
| } |
| |
| basic_fbstring& assign(basic_fbstring&& str) { |
| return *this = std::move(str); |
| } |
| |
| basic_fbstring& assign(const basic_fbstring& str, const size_type pos, |
| size_type n) { |
| const size_type sz = str.size(); |
| enforce(pos <= sz, std::__throw_out_of_range, ""); |
| procrustes(n, sz - pos); |
| return assign(str.data() + pos, n); |
| } |
| |
| basic_fbstring& assign(const value_type* s, const size_type n) { |
| Invariant checker(*this); |
| (void) checker; |
| if (size() >= n) { |
| std::copy(s, s + n, begin()); |
| resize(n); |
| assert(size() == n); |
| } else { |
| const value_type *const s2 = s + size(); |
| std::copy(s, s2, begin()); |
| append(s2, n - size()); |
| assert(size() == n); |
| } |
| store_.writeTerminator(); |
| assert(size() == n); |
| return *this; |
| } |
| |
| basic_fbstring& assign(const value_type* s) { |
| return assign(s, traits_type::length(s)); |
| } |
| |
| basic_fbstring& assign(std::initializer_list<value_type> il) { |
| return assign(il.begin(), il.end()); |
| } |
| |
| template <class ItOrLength, class ItOrChar> |
| basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) { |
| return replace(begin(), end(), first_or_n, last_or_c); |
| } |
| |
| basic_fbstring& insert(size_type pos1, const basic_fbstring& str) { |
| return insert(pos1, str.data(), str.size()); |
| } |
| |
| basic_fbstring& insert(size_type pos1, const basic_fbstring& str, |
| size_type pos2, size_type n) { |
| enforce(pos2 <= str.length(), std::__throw_out_of_range, ""); |
| procrustes(n, str.length() - pos2); |
| return insert(pos1, str.data() + pos2, n); |
| } |
| |
| basic_fbstring& insert(size_type pos, const value_type* s, size_type n) { |
| enforce(pos <= length(), std::__throw_out_of_range, ""); |
| insert(begin() + pos, s, s + n); |
| return *this; |
| } |
| |
| basic_fbstring& insert(size_type pos, const value_type* s) { |
| return insert(pos, s, traits_type::length(s)); |
| } |
| |
| basic_fbstring& insert(size_type pos, size_type n, value_type c) { |
| enforce(pos <= length(), std::__throw_out_of_range, ""); |
| insert(begin() + pos, n, c); |
| return *this; |
| } |
| |
| iterator insert(const_iterator p, const value_type c) { |
| const size_type pos = p - begin(); |
| insert(p, 1, c); |
| return begin() + pos; |
| } |
| |
| private: |
| template <int i> class Selector {}; |
| |
| iterator insertImplDiscr(const_iterator p, |
| size_type n, value_type c, Selector<1>) { |
| Invariant checker(*this); |
| (void) checker; |
| auto const pos = p - begin(); |
| assert(p >= begin() && p <= end()); |
| if (capacity() - size() < n) { |
| const size_type sz = p - begin(); |
| reserve(size() + n); |
| p = begin() + sz; |
| } |
| const iterator oldEnd = end(); |
| if (n < size_type(oldEnd - p)) { |
| append(oldEnd - n, oldEnd); |
| //std::copy( |
| // reverse_iterator(oldEnd - n), |
| // reverse_iterator(p), |
| // reverse_iterator(oldEnd)); |
| fbstring_detail::pod_move(&*p, &*oldEnd - n, |
| begin() + pos + n); |
| std::fill(begin() + pos, begin() + pos + n, c); |
| } else { |
| append(n - (end() - p), c); |
| append(iterator(p), oldEnd); |
| std::fill(iterator(p), oldEnd, c); |
| } |
| store_.writeTerminator(); |
| return begin() + pos; |
| } |
| |
| template<class InputIter> |
| iterator insertImplDiscr(const_iterator i, |
| InputIter b, InputIter e, Selector<0>) { |
| return insertImpl(i, b, e, |
| typename std::iterator_traits<InputIter>::iterator_category()); |
| } |
| |
| template <class FwdIterator> |
| iterator insertImpl(const_iterator i, |
| FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) { |
| Invariant checker(*this); |
| (void) checker; |
| const size_type pos = i - begin(); |
| const typename std::iterator_traits<FwdIterator>::difference_type n2 = |
| std::distance(s1, s2); |
| assert(n2 >= 0); |
| using namespace fbstring_detail; |
| assert(pos <= size()); |
| |
| const typename std::iterator_traits<FwdIterator>::difference_type maxn2 = |
| capacity() - size(); |
| if (maxn2 < n2) { |
| // realloc the string |
| reserve(size() + n2); |
| i = begin() + pos; |
| } |
| if (pos + n2 <= size()) { |
| const iterator tailBegin = end() - n2; |
| store_.expand_noinit(n2); |
| fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2); |
| std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i), |
| reverse_iterator(tailBegin + n2)); |
| std::copy(s1, s2, begin() + pos); |
| } else { |
| FwdIterator t = s1; |
| const size_type old_size = size(); |
| std::advance(t, old_size - pos); |
| const size_t newElems = std::distance(t, s2); |
| store_.expand_noinit(n2); |
| std::copy(t, s2, begin() + old_size); |
| fbstring_detail::pod_copy(data() + pos, data() + old_size, |
| begin() + old_size + newElems); |
| std::copy(s1, t, begin() + pos); |
| } |
| store_.writeTerminator(); |
| return begin() + pos; |
| } |
| |
| template <class InputIterator> |
| iterator insertImpl(const_iterator i, |
| InputIterator b, InputIterator e, |
| std::input_iterator_tag) { |
| const auto pos = i - begin(); |
| basic_fbstring temp(begin(), i, store_.heap()); |
| for (; b != e; ++b) { |
| temp.push_back(*b); |
| } |
| temp.append(i, cend()); |
| swap(temp); |
| return begin() + pos; |
| } |
| |
| public: |
| template <class ItOrLength, class ItOrChar> |
| iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) { |
| Selector<std::numeric_limits<ItOrLength>::is_specialized> sel; |
| return insertImplDiscr(p, first_or_n, last_or_c, sel); |
| } |
| |
| iterator insert(const_iterator p, std::initializer_list<value_type> il) { |
| return insert(p, il.begin(), il.end()); |
| } |
| |
| basic_fbstring& erase(size_type pos = 0, size_type n = npos) { |
| Invariant checker(*this); |
| (void) checker; |
| enforce(pos <= length(), std::__throw_out_of_range, ""); |
| procrustes(n, length() - pos); |
| std::copy(begin() + pos + n, end(), begin() + pos); |
| resize(length() - n); |
| return *this; |
| } |
| |
| iterator erase(iterator position) { |
| const size_type pos(position - begin()); |
| enforce(pos <= size(), std::__throw_out_of_range, ""); |
| erase(pos, 1); |
| return begin() + pos; |
| } |
| |
| iterator erase(iterator first, iterator last) { |
| const size_type pos(first - begin()); |
| erase(pos, last - first); |
| return begin() + pos; |
| } |
| |
| // Replaces at most n1 chars of *this, starting with pos1 with the |
| // content of str |
| basic_fbstring& replace(size_type pos1, size_type n1, |
| const basic_fbstring& str) { |
| return replace(pos1, n1, str.data(), str.size()); |
| } |
| |
| // Replaces at most n1 chars of *this, starting with pos1, |
| // with at most n2 chars of str starting with pos2 |
| basic_fbstring& replace(size_type pos1, size_type n1, |
| const basic_fbstring& str, |
| size_type pos2, size_type n2) { |
| enforce(pos2 <= str.length(), std::__throw_out_of_range, ""); |
| return replace(pos1, n1, str.data() + pos2, |
| std::min(n2, str.size() - pos2)); |
| } |
| |
| // Replaces at most n1 chars of *this, starting with pos, with chars from s |
| basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) { |
| return replace(pos, n1, s, traits_type::length(s)); |
| } |
| |
| // Replaces at most n1 chars of *this, starting with pos, with n2 |
| // occurrences of c |
| // |
| // consolidated with |
| // |
| // Replaces at most n1 chars of *this, starting with pos, with at |
| // most n2 chars of str. str must have at least n2 chars. |
| template <class StrOrLength, class NumOrChar> |
| basic_fbstring& replace(size_type pos, size_type n1, |
| StrOrLength s_or_n2, NumOrChar n_or_c) { |
| Invariant checker(*this); |
| (void) checker; |
| enforce(pos <= size(), std::__throw_out_of_range, ""); |
| procrustes(n1, length() - pos); |
| const iterator b = begin() + pos; |
| return replace(b, b + n1, s_or_n2, n_or_c); |
| } |
| |
| basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) { |
| return replace(i1, i2, str.data(), str.length()); |
| } |
| |
| basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) { |
| return replace(i1, i2, s, traits_type::length(s)); |
| } |
| |
| private: |
| basic_fbstring& replaceImplDiscr(iterator i1, iterator i2, |
| const value_type* s, size_type n, |
| Selector<2>) { |
| assert(i1 <= i2); |
| assert(begin() <= i1 && i1 <= end()); |
| assert(begin() <= i2 && i2 <= end()); |
| return replace(i1, i2, s, s + n); |
| } |
| |
| basic_fbstring& replaceImplDiscr(iterator i1, iterator i2, |
| size_type n2, value_type c, Selector<1>) { |
| const size_type n1 = i2 - i1; |
| if (n1 > n2) { |
| std::fill(i1, i1 + n2, c); |
| erase(i1 + n2, i2); |
| } else { |
| std::fill(i1, i2, c); |
| insert(i2, n2 - n1, c); |
| } |
| assert(isSane()); |
| return *this; |
| } |
| |
| template <class InputIter> |
| basic_fbstring& replaceImplDiscr(iterator i1, iterator i2, |
| InputIter b, InputIter e, |
| Selector<0>) { |
| replaceImpl(i1, i2, b, e, |
| typename std::iterator_traits<InputIter>::iterator_category()); |
| return *this; |
| } |
| |
| private: |
| template <class FwdIterator, class P> |
| bool replaceAliased(iterator i1, iterator i2, |
| FwdIterator s1, FwdIterator s2, P*) { |
| return false; |
| } |
| |
| template <class FwdIterator> |
| bool replaceAliased(iterator i1, iterator i2, |
| FwdIterator s1, FwdIterator s2, value_type*) { |
| static const std::less_equal<const value_type*> le = |
| std::less_equal<const value_type*>(); |
| const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end()); |
| if (!aliased) { |
| return false; |
| } |
| // Aliased replace, copy to new string |
| basic_fbstring temp(store_.heap()); |
| temp.reserve(size() - (i2 - i1) + std::distance(s1, s2)); |
| temp.append(begin(), i1).append(s1, s2).append(i2, end()); |
| swap(temp); |
| return true; |
| } |
| |
| public: |
| template <class FwdIterator> |
| void replaceImpl(iterator i1, iterator i2, |
| FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) { |
| Invariant checker(*this); |
| (void) checker; |
| |
| // Handle aliased replace |
| if (replaceAliased(i1, i2, s1, s2, &*s1)) { |
| return; |
| } |
| |
| auto const n1 = i2 - i1; |
| assert(n1 >= 0); |
| auto const n2 = std::distance(s1, s2); |
| assert(n2 >= 0); |
| |
| if (n1 > n2) { |
| // shrinks |
| std::copy(s1, s2, i1); |
| erase(i1 + n2, i2); |
| } else { |
| // grows |
| fbstring_detail::copy_n(s1, n1, i1); |
| std::advance(s1, n1); |
| insert(i2, s1, s2); |
| } |
| assert(isSane()); |
| } |
| |
| template <class InputIterator> |
| void replaceImpl(iterator i1, iterator i2, |
| InputIterator b, InputIterator e, std::input_iterator_tag) { |
| basic_fbstring temp(begin(), i1, store_.heap()); |
| temp.append(b, e).append(i2, end()); |
| swap(temp); |
| } |
| |
| public: |
| template <class T1, class T2> |
| basic_fbstring& replace(iterator i1, iterator i2, |
| T1 first_or_n_or_s, T2 last_or_c_or_n) { |
| const bool |
| num1 = std::numeric_limits<T1>::is_specialized, |
| num2 = std::numeric_limits<T2>::is_specialized; |
| return replaceImplDiscr( |
| i1, i2, first_or_n_or_s, last_or_c_or_n, |
| Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>()); |
| } |
| |
| size_type copy(value_type* s, size_type n, size_type pos = 0) const { |
| enforce(pos <= size(), std::__throw_out_of_range, ""); |
| procrustes(n, size() - pos); |
| |
| fbstring_detail::pod_copy( |
| data() + pos, |
| data() + pos + n, |
| s); |
| return n; |
| } |
| |
| //different heap swap should not be supported. |
| void swap(basic_fbstring& rhs) { |
| store_.swap(rhs.store_); |
| } |
| |
| const value_type* c_str() const { |
| return store_.c_str(); |
| } |
| |
| const value_type* data() const { return c_str(); } |
| |
| allocator_type get_allocator() const { |
| return allocator_type(); |
| } |
| |
| size_type find(const basic_fbstring& str, size_type pos = 0) const { |
| return find(str.data(), pos, str.length()); |
| } |
| |
| size_type find(const value_type* needle, const size_type pos, |
| const size_type nsize) const { |
| if (!nsize) return pos; |
| auto const size = this->size(); |
| if (nsize + pos > size) return npos; |
| // Don't use std::search, use a Boyer-Moore-like trick by comparing |
| // the last characters first |
| auto const haystack = data(); |
| auto const nsize_1 = nsize - 1; |
| auto const lastNeedle = needle[nsize_1]; |
| |
| // Boyer-Moore skip value for the last char in the needle. Zero is |
| // not a valid value; skip will be computed the first time it's |
| // needed. |
| size_type skip = 0; |
| |
| const E * i = haystack + pos; |
| auto iEnd = haystack + size - nsize_1; |
| |
| while (i < iEnd) { |
| // Boyer-Moore: match the last element in the needle |
| while (i[nsize_1] != lastNeedle) { |
| if (++i == iEnd) { |
| // not found |
| return npos; |
| } |
| } |
| // Here we know that the last char matches |
| // Continue in pedestrian mode |
| for (size_t j = 0; ; ) { |
| assert(j < nsize); |
| if (i[j] != needle[j]) { |
| // Not found, we can skip |
| // Compute the skip value lazily |
| if (skip == 0) { |
| skip = 1; |
| while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) { |
| ++skip; |
| } |
| } |
| i += skip; |
| break; |
| } |
| // Check if done searching |
| if (++j == nsize) { |
| // Yay |
| return i - haystack; |
| } |
| } |
| } |
| return npos; |
| } |
| |
| size_type find(const value_type* s, size_type pos = 0) const { |
| return find(s, pos, traits_type::length(s)); |
| } |
| |
| size_type find (value_type c, size_type pos = 0) const { |
| return find(&c, pos, 1); |
| } |
| |
| size_type rfind(const basic_fbstring& str, size_type pos = npos) const { |
| return rfind(str.data(), pos, str.length()); |
| } |
| |
| size_type rfind(const value_type* s, size_type pos, size_type n) const { |
| if (n > length()) return npos; |
| pos = std::min(pos, length() - n); |
| if (n == 0) return pos; |
| |
| const_iterator i(begin() + pos); |
| for (; ; --i) { |
| if (traits_type::eq(*i, *s) |
| && traits_type::compare(&*i, s, n) == 0) { |
| return i - begin(); |
| } |
| if (i == begin()) break; |
| } |
| return npos; |
| } |
| |
| size_type rfind(const value_type* s, size_type pos = npos) const { |
| return rfind(s, pos, traits_type::length(s)); |
| } |
| |
| size_type rfind(value_type c, size_type pos = npos) const { |
| return rfind(&c, pos, 1); |
| } |
| |
| size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const { |
| return find_first_of(str.data(), pos, str.length()); |
| } |
| |
| size_type find_first_of(const value_type* s, |
| size_type pos, size_type n) const { |
| assert(s); |
| if (pos > length() || n == 0) return npos; |
| const_iterator i(begin() + pos), finish(end() + 1); |
| for (; i != finish; ++i) { |
| if (traits_type::find(s, n, *i) != 0) { |
| return i - begin(); |
| } |
| } |
| return npos; |
| } |
| |
| size_type find_first_of(const value_type* s, size_type pos = 0) const { |
| return find_first_of(s, pos, traits_type::length(s)); |
| } |
| |
| size_type find_first_of(value_type c, size_type pos = 0) const { |
| return find_first_of(&c, pos, 1); |
| } |
| |
| size_type find_last_of (const basic_fbstring& str, |
| size_type pos = npos) const { |
| return find_last_of(str.data(), pos, str.length()); |
| } |
| |
| size_type find_last_of (const value_type* s, size_type pos, |
| size_type n) const { |
| assert(s); |
| if (!empty() && n > 0) { |
| //pos = std::min(pos, length() - 1); |
| //why replace above line? |
| //to act as behavior of old NAString::last. |
| pos = std::min(pos, traits_type::length(data()) - 1); |
| const_iterator i(begin() + pos + 1); |
| for (;; --i) { |
| if (traits_type::find(s, n, *i) != 0) { |
| return i - begin(); |
| } |
| if (i == begin()) break; |
| } |
| } |
| return npos; |
| } |
| |
| size_type find_last_of (const value_type* s, |
| size_type pos = npos) const { |
| return find_last_of(s, pos, traits_type::length(s)); |
| } |
| |
| size_type find_last_of (value_type c, size_type pos = npos) const { |
| return find_last_of(&c, pos, 1); |
| } |
| |
| size_type find_first_not_of(const basic_fbstring& str, |
| size_type pos = 0) const { |
| return find_first_not_of(str.data(), pos, str.size()); |
| } |
| |
| size_type find_first_not_of(const value_type* s, size_type pos, |
| size_type n) const { |
| if (pos < length()) { |
| const_iterator |
| i(begin() + pos), |
| finish(end()); |
| for (; i != finish; ++i) { |
| if (traits_type::find(s, n, *i) == 0) { |
| return i - begin(); |
| } |
| } |
| } |
| return npos; |
| } |
| |
| size_type find_first_not_of(const value_type* s, |
| size_type pos = 0) const { |
| return find_first_not_of(s, pos, traits_type::length(s)); |
| } |
| |
| size_type find_first_not_of(value_type c, size_type pos = 0) const { |
| return find_first_not_of(&c, pos, 1); |
| } |
| |
| size_type find_last_not_of(const basic_fbstring& str, |
| size_type pos = npos) const { |
| return find_last_not_of(str.data(), pos, str.length()); |
| } |
| |
| size_type find_last_not_of(const value_type* s, size_type pos, |
| size_type n) const { |
| if (!this->empty()) { |
| pos = std::min(pos, size() - 1); |
| const_iterator i(begin() + pos); |
| for (;; --i) { |
| if (traits_type::find(s, n, *i) == 0) { |
| return i - begin(); |
| } |
| if (i == begin()) break; |
| } |
| } |
| return npos; |
| } |
| |
| size_type find_last_not_of(const value_type* s, |
| size_type pos = npos) const { |
| return find_last_not_of(s, pos, traits_type::length(s)); |
| } |
| |
| size_type find_last_not_of (value_type c, size_type pos = npos) const { |
| return find_last_not_of(&c, pos, 1); |
| } |
| |
| basic_fbstring substr(size_type pos = 0, size_type n = npos) const { |
| enforce(pos <= size(), std::__throw_out_of_range, ""); |
| return basic_fbstring(data() + pos, std::min(n, size() - pos), store_.heap()); |
| } |
| |
| int compare(const basic_fbstring& str) const { |
| // FIX due to Goncalo N M de Carvalho July 18, 2005 |
| return compare(0, size(), str); |
| } |
| |
| int compare(size_type pos1, size_type n1, |
| const basic_fbstring& str) const { |
| return compare(pos1, n1, str.data(), str.size()); |
| } |
| |
| int compare(size_type pos1, size_type n1, |
| const value_type* s) const { |
| return compare(pos1, n1, s, traits_type::length(s)); |
| } |
| |
| int compare(size_type pos1, size_type n1, |
| const value_type* s, size_type n2) const { |
| enforce(pos1 <= size(), std::__throw_out_of_range, ""); |
| procrustes(n1, size() - pos1); |
| // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks! |
| const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2)); |
| int rTmp = r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0; |
| /*************************************************************** |
| * for return value of char_traits<char/char16_t>::compare(), |
| * positive value of r may not be 1, and negetive may not be -1, |
| * transforming is needed. |
| **************************************************************/ |
| return rTmp > 0 ? 1 : (rTmp < 0 ? -1 : 0); |
| } |
| |
| int compare(size_type pos1, size_type n1, |
| const basic_fbstring& str, |
| size_type pos2, size_type n2) const { |
| enforce(pos2 <= str.size(), std::__throw_out_of_range, ""); |
| return compare(pos1, n1, str.data() + pos2, |
| std::min(n2, str.size() - pos2)); |
| } |
| |
| // Code from Jean-Francois Bastien (03/26/2007) |
| int compare(const value_type* s) const { |
| // Could forward to compare(0, size(), s, traits_type::length(s)) |
| // but that does two extra checks |
| const size_type n1(size()), n2(traits_type::length(s)); |
| const int r = traits_type::compare(data(), s, std::min(n1, n2)); |
| int rTmp = r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0; |
| /*************************************************************** |
| * for return value of char_traits<char/char16_t>::compare(), |
| * positive value of r may not be 1, and negetive may not be -1, |
| * transforming is needed. |
| **************************************************************/ |
| return rTmp > 0 ? 1 : (rTmp < 0 ? -1 : 0); |
| } |
| |
| private: |
| // Data |
| Storage store_; |
| }; |
| |
| // non-member functions |
| // C++11 21.4.8.1/2 |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| |
| basic_fbstring<E, T, A, S> result; |
| result.reserve(lhs.size() + rhs.size()); |
| result.append(lhs).append(rhs); |
| return std::move(result); |
| } |
| |
| // C++11 21.4.8.1/2 |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return std::move(lhs.append(rhs)); |
| } |
| |
| // C++11 21.4.8.1/3 |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs, |
| basic_fbstring<E, T, A, S>&& rhs) { |
| if (rhs.capacity() >= lhs.size() + rhs.size()) { |
| // Good, at least we don't need to reallocate |
| return std::move(rhs.insert(0, lhs)); |
| } |
| // Meh, no go. Forward to operator+(const&, const&). |
| auto const& rhsC = rhs; |
| return lhs + rhsC; |
| } |
| |
| // C++11 21.4.8.1/4 |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs, |
| basic_fbstring<E, T, A, S>&& rhs) { |
| return std::move(lhs.append(rhs)); |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+( |
| const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| // |
| basic_fbstring<E, T, A, S> result; |
| const typename basic_fbstring<E, T, A, S>::size_type len = |
| basic_fbstring<E, T, A, S>::traits_type::length(lhs); |
| result.reserve(len + rhs.size()); |
| result.append(lhs, len).append(rhs); |
| return result; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+( |
| typename basic_fbstring<E, T, A, S>::value_type lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| |
| basic_fbstring<E, T, A, S> result; |
| result.reserve(1 + rhs.size()); |
| result.push_back(lhs); |
| result.append(rhs); |
| return result; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+( |
| const basic_fbstring<E, T, A, S>& lhs, |
| const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
| |
| typedef typename basic_fbstring<E, T, A, S>::size_type size_type; |
| typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type; |
| |
| basic_fbstring<E, T, A, S> result; |
| const size_type len = traits_type::length(rhs); |
| result.reserve(lhs.size() + len); |
| result.append(lhs).append(rhs, len); |
| return result; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| basic_fbstring<E, T, A, S> operator+( |
| const basic_fbstring<E, T, A, S>& lhs, |
| typename basic_fbstring<E, T, A, S>::value_type rhs) { |
| |
| basic_fbstring<E, T, A, S> result; |
| result.reserve(lhs.size() + 1); |
| result.append(lhs); |
| result.push_back(rhs); |
| return result; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator==(const basic_fbstring<E, T, A, S>& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return rhs == lhs; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator==(const basic_fbstring<E, T, A, S>& lhs, |
| const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
| return lhs.compare(rhs) == 0; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator!=(const basic_fbstring<E, T, A, S>& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return !(lhs == rhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return !(lhs == rhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator!=(const basic_fbstring<E, T, A, S>& lhs, |
| const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
| return !(lhs == rhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator<(const basic_fbstring<E, T, A, S>& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return lhs.compare(rhs) < 0; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator<(const basic_fbstring<E, T, A, S>& lhs, |
| const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
| return lhs.compare(rhs) < 0; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return rhs.compare(lhs) > 0; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator>(const basic_fbstring<E, T, A, S>& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return rhs < lhs; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator>(const basic_fbstring<E, T, A, S>& lhs, |
| const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
| return rhs < lhs; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return rhs < lhs; } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator<=(const basic_fbstring<E, T, A, S>& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return !(rhs < lhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator<=(const basic_fbstring<E, T, A, S>& lhs, |
| const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
| return !(rhs < lhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return !(rhs < lhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator>=(const basic_fbstring<E, T, A, S>& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return !(lhs < rhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator>=(const basic_fbstring<E, T, A, S>& lhs, |
| const typename basic_fbstring<E, T, A, S>::value_type* rhs) { |
| return !(lhs < rhs); } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return !(lhs < rhs); |
| } |
| |
| // C++11 21.4.8.8 |
| template <typename E, class T, class A, class S> |
| void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) { |
| lhs.swap(rhs); |
| } |
| |
| // TODO: make this faster. |
| template <typename E, class T, class A, class S> |
| inline |
| std::basic_istream< |
| typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& |
| operator>>( |
| std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& is, |
| basic_fbstring<E, T, A, S>& str) { |
| typename std::basic_istream<E, T>::sentry sentry(is); |
| typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type> |
| __istream_type; |
| typedef typename __istream_type::ios_base __ios_base; |
| size_t extracted = 0; |
| auto err = __ios_base::goodbit; |
| if (sentry) { |
| auto n = is.width(); |
| if (n == 0) { |
| n = str.max_size(); |
| } |
| str.erase(); |
| auto got = is.rdbuf()->sgetc(); |
| for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) { |
| // Whew. We get to store this guy |
| str.push_back(got); |
| got = is.rdbuf()->snextc(); |
| } |
| if (got == T::eof()) { |
| err |= __ios_base::eofbit; |
| is.width(0); |
| } |
| } |
| if (!extracted) { |
| err |= __ios_base::failbit; |
| } |
| if (err) { |
| is.setstate(err); |
| } |
| return is; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& |
| operator<<( |
| std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& os, |
| const basic_fbstring<E, T, A, S>& str) { |
| os.write(str.data(), str.size()); |
| return os; |
| } |
| |
| #ifndef _LIBSTDCXX_FBSTRING |
| |
| template <typename E, class T, class A, class S> |
| inline |
| std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& |
| getline( |
| std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& is, |
| basic_fbstring<E, T, A, S>& str, |
| typename basic_fbstring<E, T, A, S>::value_type delim) { |
| // Use the nonstandard getdelim() |
| char * buf = NULL; |
| size_t size = 0; |
| for (;;) { |
| // This looks quadratic but it really depends on realloc |
| auto const newSize = size + 128; |
| |
| buf = static_cast<char*>(checkedRealloc(buf, size, newSize)); |
| |
| is.getline(buf + size, newSize - size, delim); |
| if (is.bad() || is.eof() || !is.fail()) { |
| // done by either failure, end of file, or normal read |
| size += std::strlen(buf + size); |
| break; |
| } |
| // Here we have failed due to too short a buffer |
| // Minus one to discount the terminating '\0' |
| size = newSize - 1; |
| assert(buf[size] == 0); |
| // Clear the error so we can continue reading |
| is.clear(); |
| } |
| basic_fbstring<E, T, A, S> result(buf, size, size + 1); |
| result.swap(str); |
| return is; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& |
| getline( |
| std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type, |
| typename basic_fbstring<E, T, A, S>::traits_type>& is, |
| basic_fbstring<E, T, A, S>& str) { |
| // Just forward to the version with a delimiter |
| return getline(is, str, '\n'); |
| } |
| |
| #endif |
| |
| template <typename E1, class T, class A, class S> |
| const typename basic_fbstring<E1, T, A, S>::size_type |
| basic_fbstring<E1, T, A, S>::npos = |
| static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1); |
| |
| #ifndef _LIBSTDCXX_FBSTRING |
| // basic_string compatibility routines |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator==(const basic_fbstring<E, T, A, S>& lhs, |
| const std::string& rhs) { |
| return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator==(const std::string& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return rhs == lhs; |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator!=(const basic_fbstring<E, T, A, S>& lhs, |
| const std::string& rhs) { |
| return !(lhs == rhs); |
| } |
| |
| template <typename E, class T, class A, class S> |
| inline |
| bool operator!=(const std::string& lhs, |
| const basic_fbstring<E, T, A, S>& rhs) { |
| return !(lhs == rhs); |
| } |
| |
| //#if !defined(_LIBSTDCXX_FBSTRING) |
| //typedef basic_fbstring<char> fbstring; |
| //#endif |
| |
| // fbstring is relocatable |
| //template <class T, class R, class A, class S> |
| //FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>); |
| |
| #else |
| _GLIBCXX_END_NAMESPACE_VERSION |
| #endif |
| |
| } // namespace folly |
| |
| //#pragma GCC diagnostic pop |
| |
| #ifndef _LIBSTDCXX_FBSTRING |
| /* |
| namespace std { |
| template <> |
| struct hash< ::folly::fbstring> { |
| size_t operator()(const ::folly::fbstring& s) const { |
| return ::folly::hash::fnv32_buf(s.data(), s.size()); |
| } |
| }; |
| } |
| */ |
| #endif // _LIBSTDCXX_FBSTRING |
| |
| #undef FBSTRING_LIKELY |
| #undef FBSTRING_UNLIKELY |
| |
| #endif // FOLLY_BASE_FBSTRING_H_ |