/*
- * Copyright 2013 Facebook, Inc.
+ * Copyright 2015 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#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
+#include <atomic>
+#include <limits>
+#include <type_traits>
// 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>
-
+// To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
+// libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
#ifdef _LIBSTDCXX_FBSTRING
#pragma GCC system_header
// either before or after this inclusion.
#ifdef FOLLY_MALLOC_H_
#undef FOLLY_MALLOC_H_
-#include "basic_fbstring_malloc.h"
+#include "basic_fbstring_malloc.h" // nolint
#else
-#include "basic_fbstring_malloc.h"
+#include "basic_fbstring_malloc.h" // nolint
#undef FOLLY_MALLOC_H_
#endif
#else // !_LIBSTDCXX_FBSTRING
+#include <folly/Portability.h>
+
+// libc++ doesn't provide this header, nor does msvc
+#ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
+#include <bits/c++config.h>
+#endif
+
#include <string>
#include <cstring>
#include <cassert>
+#include <algorithm>
+
+#include <folly/Traits.h>
+#include <folly/Malloc.h>
+#include <folly/Hash.h>
+#include <folly/ScopeGuard.h>
-#include "folly/Traits.h"
-#include "folly/Malloc.h"
-#include "folly/Hash.h"
+#if FOLLY_HAVE_DEPRECATED_ASSOC
+#ifdef _GLIBCXX_SYMVER
+#include <ext/hash_set>
+#include <ext/hash_map>
+#endif
+#endif
#endif
// We defined these here rather than including Likely.h to avoid
// redefinition errors when fbstring is imported into libstdc++.
+#if defined(__GNUC__) && __GNUC__ >= 4
#define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
#define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
+#else
+#define FBSTRING_LIKELY(x) (x)
+#define FBSTRING_UNLIKELY(x) (x)
+#endif
-#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"
+
+// FBString cannot use throw when replacing std::string, though it may still
+// use std::__throw_*
+// nolint
+#define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
#ifdef _LIBSTDCXX_FBSTRING
namespace std _GLIBCXX_VISIBILITY(default) {
namespace folly {
#endif
+// Different versions of gcc/clang support different versions of
+// the address sanitizer attribute. Unfortunately, this attribute
+// has issues when inlining is used, so disable that as well.
+#if defined(__clang__)
+# if __has_feature(address_sanitizer)
+# if __has_attribute(__no_address_safety_analysis__)
+# define FBSTRING_DISABLE_ADDRESS_SANITIZER \
+ __attribute__((__no_address_safety_analysis__, __noinline__))
+# elif __has_attribute(__no_sanitize_address__)
+# define FBSTRING_DISABLE_ADDRESS_SANITIZER \
+ __attribute__((__no_sanitize_address__, __noinline__))
+# endif
+# endif
+#elif defined (__GNUC__) && \
+ (__GNUC__ == 4) && \
+ (__GNUC_MINOR__ >= 8) && \
+ __SANITIZE_ADDRESS__
+# define FBSTRING_DISABLE_ADDRESS_SANITIZER \
+ __attribute__((__no_address_safety_analysis__, __noinline__))
+#endif
+#ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
+# define FBSTRING_DISABLE_ADDRESS_SANITIZER
+#endif
+
namespace fbstring_detail {
template <class InIt, class OutIt>
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 Char> class fbstring_core {
public:
- fbstring_core() {
+ fbstring_core() noexcept {
// Only initialize the tag, will set the MSBs (i.e. the small
// string size) to zero too
ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
// or: setSmallSize(0);
writeTerminator();
- assert(category() == isSmall && size() == 0);
+ assert(category() == Category::isSmall && size() == 0);
}
fbstring_core(const fbstring_core & rhs) {
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_));
+ if (rhs.category() == Category::isSmall) {
+ static_assert(offsetof(MediumLarge, data_) == 0,
+ "fbstring layout failure");
+ static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
+ "fbstring layout failure");
+ static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
+ "fbstring layout failure");
const size_t size = rhs.smallSize();
if (size == 0) {
ml_.capacity_ = rhs.ml_.capacity_;
// ml_.capacity field).
ml_ = rhs.ml_;
}
- assert(category() == isSmall && this->size() == rhs.size());
- } else if (rhs.category() == isLarge) {
+ assert(category() == Category::isSmall && this->size() == rhs.size());
+ } else if (rhs.category() == Category::isLarge) {
// Large strings are just refcounted
ml_ = rhs.ml_;
RefCounted::incrementRefs(ml_.data_);
- assert(category() == isLarge && size() == rhs.size());
+ assert(category() == Category::isLarge && size() == rhs.size());
} else {
// Medium strings are copied eagerly. Don't forget to allocate
// one extra Char for the null terminator.
// 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);
+ ml_.capacity_ = (allocSize / sizeof(Char) - 1)
+ | static_cast<category_type>(Category::isMedium);
+ assert(category() == Category::isMedium);
}
assert(size() == rhs.size());
assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
}
- fbstring_core(fbstring_core&& goner) {
- if (goner.category() == isSmall) {
+ fbstring_core(fbstring_core&& goner) noexcept {
+ if (goner.category() == Category::isSmall) {
// Just copy, leave the goner in peace
new(this) fbstring_core(goner.small_, goner.smallSize());
} else {
}
}
- fbstring_core(const Char *const data, const size_t size) {
+ // NOTE(agallagher): The word-aligned copy path copies bytes which are
+ // outside the range of the string, and makes address sanitizer unhappy,
+ // so just disable it on this function.
+ fbstring_core(const Char *const data, const size_t size)
+ FBSTRING_DISABLE_ADDRESS_SANITIZER {
+#ifndef NDEBUG
+#ifndef _LIBSTDCXX_FBSTRING
+ SCOPE_EXIT {
+ assert(this->size() == size);
+ assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
+ };
+#endif
+#endif
+
// 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(Char*) + 2 * sizeof(size_t));
- /*static_*/assert(sizeof(Char*) == sizeof(size_t));
+ static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
+ "fbstring has unexpected size");
+ static_assert(sizeof(Char*) == sizeof(size_t),
+ "fbstring size assumption violation");
// sizeof(size_t) must be a power of 2
- /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
+ static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
+ "fbstring size assumption violation");
// If data is aligned, use fast word-wise copying. Otherwise,
// use conservative memcpy.
}
}
setSmallSize(size);
+ return;
} else if (size <= maxMediumSize) {
// Medium strings are allocated normally. Don't forget to
// allocate one extra Char for the terminating null.
ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
fbstring_detail::pod_copy(data, data + size, ml_.data_);
ml_.size_ = size;
- ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
+ ml_.capacity_ = (allocSize / sizeof(Char) - 1)
+ | static_cast<category_type>(Category::isMedium);
} else {
// Large strings are allocated differently
size_t effectiveCapacity = size;
auto const newRC = RefCounted::create(data, & effectiveCapacity);
ml_.data_ = newRC->data_;
ml_.size_ = size;
- ml_.capacity_ = effectiveCapacity | isLarge;
+ ml_.capacity_ = effectiveCapacity
+ | static_cast<category_type>(Category::isLarge);
}
writeTerminator();
- assert(this->size() == size);
- assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
}
- ~fbstring_core() {
+ ~fbstring_core() noexcept {
auto const c = category();
- if (c == isSmall) {
+ if (c == Category::isSmall) {
return;
}
- if (c == isMedium) {
+ if (c == Category::isMedium) {
free(ml_.data_);
return;
}
}
// Snatches a previously mallocated string. The parameter "size"
- // is the size of the string, and the parameter "capacity" is the size
- // of the mallocated block. The string must be \0-terminated, so
- // data[size] == '\0' and capacity >= size + 1.
+ // is the size of the string, and the parameter "allocatedSize"
+ // is the size of the mallocated block. The string must be
+ // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
//
- // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
- // "size", and pass 3 as "capacity".
- fbstring_core(Char *const data, const size_t size,
- const size_t capacity,
+ // So if you want a 2-character string, pass malloc(3) as "data",
+ // pass 2 as "size", and pass 3 as "allocatedSize".
+ fbstring_core(Char * const data,
+ const size_t size,
+ const size_t allocatedSize,
AcquireMallocatedString) {
if (size > 0) {
- assert(capacity > size);
+ assert(allocatedSize >= size + 1);
assert(data[size] == '\0');
// Use the medium string storage
ml_.data_ = data;
ml_.size_ = size;
- ml_.capacity_ = capacity | isMedium;
+ // Don't forget about null terminator
+ ml_.capacity_ = (allocatedSize - 1)
+ | static_cast<category_type>(Category::isMedium);
} else {
// No need for the memory
free(data);
Char * mutable_data() {
auto const c = category();
- if (c == isSmall) {
+ if (c == Category::isSmall) {
return small_;
}
- assert(c == isMedium || c == isLarge);
- if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
+ assert(c == Category::isMedium || c == Category::isLarge);
+ if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
// Ensure unique.
size_t effectiveCapacity = ml_.capacity();
auto const newRC = RefCounted::create(& effectiveCapacity);
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) {
+ if (c == Category::isSmall) {
assert(small_[smallSize()] == '\0');
return small_;
}
- assert(c == isMedium || c == isLarge);
+ assert(c == Category::isMedium || c == Category::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_;
}
void shrink(const size_t delta) {
- if (category() == isSmall) {
+ if (category() == Category::isSmall) {
// Check for underflow
assert(delta <= smallSize());
setSmallSize(smallSize() - delta);
- } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
+ } else if (category() == Category::isMedium ||
+ RefCounted::refs(ml_.data_) == 1) {
// Medium strings and unique large strings need no special
// handling.
assert(ml_.size_ >= delta);
ml_.size_ -= delta;
+ writeTerminator();
} else {
assert(ml_.size_ >= delta);
// Shared large string, must make unique. This is because of the
fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
}
// No need to write the terminator.
- return;
}
- writeTerminator();
}
void reserve(size_t minCapacity) {
- if (category() == isLarge) {
+ if (category() == Category::isLarge) {
// Ensure unique
if (RefCounted::refs(ml_.data_) > 1) {
// We must make it unique regardless; in-place reallocation is
// we have + 1 above.
RefCounted::decrementRefs(ml_.data_);
ml_.data_ = newRC->data_;
- ml_.capacity_ = minCapacity | isLarge;
+ ml_.capacity_ = minCapacity
+ | static_cast<category_type>(Category::isLarge);
// size remains unchanged
} else {
// String is not shared, so let's try to realloc (if needed)
RefCounted::reallocate(ml_.data_, ml_.size_,
ml_.capacity(), minCapacity);
ml_.data_ = newRC->data_;
- ml_.capacity_ = minCapacity | isLarge;
+ ml_.capacity_ = minCapacity
+ | static_cast<category_type>(Category::isLarge);
writeTerminator();
}
assert(capacity() >= minCapacity);
}
- } else if (category() == isMedium) {
+ } else if (category() == Category::isMedium) {
// String is not shared
if (minCapacity <= ml_.capacity()) {
return; // nothing to do, there's enough room
smartRealloc(
ml_.data_,
ml_.size_ * sizeof(Char),
- ml_.capacity() * sizeof(Char),
+ (ml_.capacity() + 1) * sizeof(Char),
capacityBytes));
writeTerminator();
- ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
+ ml_.capacity_ = (capacityBytes / sizeof(Char) - 1)
+ | static_cast<category_type>(Category::isMedium);
} else {
// Conversion from medium to large string
fbstring_core nascent;
assert(capacity() >= minCapacity);
}
} else {
- assert(category() == isSmall);
+ assert(category() == Category::isSmall);
if (minCapacity > maxMediumSize) {
// large
auto const newRC = RefCounted::create(& minCapacity);
// No need for writeTerminator(), we wrote it above with + 1.
ml_.data_ = newRC->data_;
ml_.size_ = size;
- ml_.capacity_ = minCapacity | isLarge;
+ ml_.capacity_ = minCapacity
+ | static_cast<category_type>(Category::isLarge);
assert(capacity() >= minCapacity);
} else if (minCapacity > maxSmallSize) {
// medium
// No need for writeTerminator(), we wrote it above with + 1.
ml_.data_ = data;
ml_.size_ = size;
- ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
+ ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1)
+ | static_cast<category_type>(Category::isMedium);
} else {
// small
// Nothing to do, everything stays put
// Strategy is simple: make room, then change size
assert(capacity() >= size());
size_t sz, newSz;
- if (category() == isSmall) {
+ if (category() == Category::isSmall) {
sz = smallSize();
newSz = sz + delta;
if (newSz <= maxSmallSize) {
setSmallSize(newSz);
- writeTerminator();
return small_ + sz;
}
reserve(newSz);
}
assert(capacity() >= newSz);
// Category can't be small - we took care of that above
- assert(category() == isMedium || category() == isLarge);
+ assert(category() == Category::isMedium || category() == Category::isLarge);
ml_.size_ = newSz;
writeTerminator();
assert(size() == newSz);
void push_back(Char c) {
assert(capacity() >= size());
size_t sz;
- if (category() == isSmall) {
+ if (category() == Category::isSmall) {
sz = smallSize();
if (sz < maxSmallSize) {
- setSmallSize(sz + 1);
small_[sz] = c;
- writeTerminator();
+ setSmallSize(sz + 1);
return;
}
reserve(maxSmallSize * 2);
} else {
sz = ml_.size_;
if (sz == capacity()) { // always true for isShared()
- reserve(sz * 3 / 2); // ensures not shared
+ reserve(1 + 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);
+ assert(category() == Category::isMedium || category() == Category::isLarge);
ml_.size_ = sz + 1;
ml_.data_[sz] = c;
writeTerminator();
}
size_t size() const {
- return category() == isSmall ? smallSize() : ml_.size_;
+ return category() == Category::isSmall ? smallSize() : ml_.size_;
}
size_t capacity() const {
switch (category()) {
- case isSmall:
+ case Category::isSmall:
return maxSmallSize;
- case isLarge:
+ case Category::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.
}
bool isShared() const {
- return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
+ return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
}
-#ifdef FBSTRING_PERVERSE
- enum { TERMINATOR = '^' };
-#else
- enum { TERMINATOR = '\0' };
-#endif
-
void writeTerminator() {
-#if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
- if (category() == isSmall) {
+ if (category() == Category::isSmall) {
const auto s = smallSize();
if (s != maxSmallSize) {
- small_[s] = TERMINATOR;
+ small_[s] = '\0';
}
} else {
- ml_.data_[ml_.size_] = TERMINATOR;
+ ml_.data_[ml_.size_] = '\0';
}
-#endif
}
private:
};
union {
- mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
- mutable MediumLarge ml_;
+ Char small_[sizeof(MediumLarge) / sizeof(Char)];
+ MediumLarge ml_;
};
enum {
static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
"Corrupt memory layout for fbstring.");
- enum Category {
+ typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
+ category_type;
+
+ enum class Category : category_type {
isSmall = 0,
isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
}
size_t smallSize() const {
- assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
+ assert(category() == Category::isSmall &&
+ static_cast<size_t>(small_[maxSmallSize])
+ <= static_cast<size_t>(maxSmallSize));
return static_cast<size_t>(maxSmallSize)
- static_cast<size_t>(small_[maxSmallSize]);
}
// small_[maxSmallSize].
assert(s <= maxSmallSize);
small_[maxSmallSize] = maxSmallSize - s;
+ writeTerminator();
}
};
size() <= max_size() &&
capacity() <= max_size() &&
size() <= capacity() &&
- (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
+ begin()[size()] == '\0';
}
struct Invariant;
}
public:
- // 21.3.1 construct/copy/destroy
- explicit basic_fbstring(const A& a = A()) {
+ // C++11 21.4.2 construct/copy/destroy
+ explicit basic_fbstring(const A& a = A()) noexcept {
}
basic_fbstring(const basic_fbstring& str)
}
// Move constructor
- basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
+ basic_fbstring(basic_fbstring&& goner) noexcept
+ : store_(std::move(goner.store_)) {
}
#ifndef _LIBSTDCXX_FBSTRING
}
/* implicit */ basic_fbstring(const value_type* s, const A& a = A())
- : 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;
- })) {
+ : store_(s, s
+ ? traits_type::length(s)
+ : (std::__throw_logic_error(
+ "basic_fbstring: null pointer initializer not valid"),
+ 0)) {
}
basic_fbstring(const value_type* s, size_type n, const A& a = A())
: store_(s, n, c, a) {
}
- ~basic_fbstring() {
+ // Construction from initialization list
+ basic_fbstring(std::initializer_list<value_type> il) {
+ assign(il.begin(), il.end());
+ }
+
+ ~basic_fbstring() noexcept {
}
basic_fbstring& operator=(const basic_fbstring& lhs) {
}
// Move assignment
- basic_fbstring& operator=(basic_fbstring&& goner) {
- // Self move assignment is illegal, see 17.6.4.9 for the explanation
- assert(&goner != this);
+ basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
+ 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
return *this;
}
- // 21.3.2 iterators:
+ 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();
}
return store_.data() + store_.size();
}
+ const_iterator cend() const { return end(); }
+
reverse_iterator rbegin() {
return reverse_iterator(end());
}
return const_reverse_iterator(end());
}
+ const_reverse_iterator crbegin() const { return rbegin(); }
+
reverse_iterator rend() {
return reverse_iterator(begin());
}
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(); }
store_.shrink(1);
}
- // 21.3.3 capacity:
+ // C++11 21.4.4 capacity:
size_type size() const { return store_.size(); }
size_type length() const { return size(); }
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()).swap(*this);
+ }
+
void clear() { resize(0); }
bool empty() const { return size() == 0; }
- // 21.3.4 element access:
+ // C++11 21.4.5 element access:
const_reference operator[](size_type pos) const {
- return *(c_str() + pos);
+ return *(begin() + pos);
}
reference operator[](size_type pos) {
- if (pos == size()) {
- // Just call c_str() to make sure '\0' is present
- c_str();
- }
return *(begin() + pos);
}
return (*this)[n];
}
- // 21.3.5 modifiers:
+ // C++11 21.4.6 modifiers:
basic_fbstring& operator+=(const basic_fbstring& str) {
return append(str);
}
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();
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);
}
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();
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);
return *this;
}
- iterator insert(const iterator p, const value_type c) {
+ 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 {};
- basic_fbstring& insertImplDiscr(iterator p,
- size_type n, value_type c, Selector<1>) {
+ 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();
p = begin() + sz;
}
const iterator oldEnd = end();
- if( n < size_type(oldEnd - p)) {
+ 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, &*p + n);
- std::fill(p, p + n, c);
+ 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(p, oldEnd);
- std::fill(p, oldEnd, c);
+ append(iterator(p), oldEnd);
+ std::fill(iterator(p), oldEnd, c);
}
store_.writeTerminator();
- return *this;
+ return begin() + pos;
}
template<class InputIter>
- basic_fbstring& insertImplDiscr(iterator i,
- InputIter b, InputIter e, Selector<0>) {
- insertImpl(i, b, e,
+ iterator insertImplDiscr(const_iterator i,
+ InputIter b, InputIter e, Selector<0>) {
+ return insertImpl(i, b, e,
typename std::iterator_traits<InputIter>::iterator_category());
- return *this;
}
template <class FwdIterator>
- void insertImpl(iterator i,
+ iterator insertImpl(const_iterator i,
FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
Invariant checker(*this);
(void) checker;
const iterator tailBegin = end() - n2;
store_.expand_noinit(n2);
fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
- std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
+ std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
reverse_iterator(tailBegin + n2));
- std::copy(s1, s2, i);
+ std::copy(s1, s2, begin() + pos);
} else {
FwdIterator t = s1;
const size_type old_size = size();
std::copy(t, s2, begin() + old_size);
fbstring_detail::pod_copy(data() + pos, data() + old_size,
begin() + old_size + newElems);
- std::copy(s1, t, i);
+ std::copy(s1, t, begin() + pos);
}
store_.writeTerminator();
+ return begin() + pos;
}
template <class InputIterator>
- void insertImpl(iterator i,
- InputIterator b, InputIterator e, std::input_iterator_tag) {
+ iterator insertImpl(const_iterator i,
+ InputIterator b, InputIterator e,
+ std::input_iterator_tag) {
+ const auto pos = i - begin();
basic_fbstring temp(begin(), i);
for (; b != e; ++b) {
temp.push_back(*b);
}
- temp.append(i, end());
+ temp.append(i, cend());
swap(temp);
+ return begin() + pos;
}
public:
template <class ItOrLength, class ItOrChar>
- void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
+ iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
- insertImplDiscr(p, first_or_n, last_or_c, 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) {
}
private:
- template <class FwdIterator, class P>
+ template <class FwdIterator>
bool replaceAliased(iterator i1, iterator i2,
- FwdIterator s1, FwdIterator s2, P*) {
+ FwdIterator s1, FwdIterator s2, std::false_type) {
return false;
}
template <class FwdIterator>
bool replaceAliased(iterator i1, iterator i2,
- FwdIterator s1, FwdIterator s2, value_type*) {
+ FwdIterator s1, FwdIterator s2, std::true_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());
return true;
}
-public:
template <class FwdIterator>
void replaceImpl(iterator i1, iterator i2,
FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
(void) checker;
// Handle aliased replace
- if (replaceAliased(i1, i2, s1, s2, &*s1)) {
+ if (replaceAliased(i1, i2, s1, s2,
+ std::integral_constant<bool,
+ std::is_same<FwdIterator, iterator>::value ||
+ std::is_same<FwdIterator, const_iterator>::value>())) {
return;
}
store_.swap(rhs.store_);
}
- // 21.3.6 string operations:
const value_type* c_str() const {
return store_.c_str();
}
const size_type nsize) const {
if (!nsize) return pos;
auto const size = this->size();
- if (nsize + pos > size) return npos;
+ // nsize + pos can overflow (eg pos == npos), guard against that by checking
+ // that nsize + pos does not wrap around.
+ if (nsize + pos > size || nsize + pos < pos) return npos;
// Don't use std::search, use a Boyer-Moore-like trick by comparing
// the last characters first
auto const haystack = data();
return find_last_not_of(&c, pos, 1);
}
- basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
+ 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));
}
+ basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
+ enforce(pos <= size(), std::__throw_out_of_range, "");
+ erase(0, pos);
+ if (n < size()) resize(n);
+ return std::move(*this);
+ }
+
int compare(const basic_fbstring& str) const {
// FIX due to Goncalo N M de Carvalho July 18, 2005
return compare(0, size(), str);
};
// non-member functions
-// C++11 21.4.8.1/2
+// C++11 21.4.8.1/1
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,
return std::move(lhs.append(rhs));
}
+// C++11 21.4.8.1/5
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 E* 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);
+ const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
+ result.reserve(len + rhs.size());
+ result.append(lhs, len).append(rhs);
+ return result;
+}
+
+// C++11 21.4.8.1/6
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(
+ const E* lhs,
+ basic_fbstring<E, T, A, S>&& rhs) {
+ //
+ const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
+ if (rhs.capacity() >= len + rhs.size()) {
+ // Good, at least we don't need to reallocate
+ return std::move(rhs.insert(rhs.begin(), lhs, lhs + len));
+ }
+ // Meh, no go. Do it by hand since we have len already.
+ basic_fbstring<E, T, A, S> result;
result.reserve(len + rhs.size());
result.append(lhs, len).append(rhs);
return result;
}
+// C++11 21.4.8.1/7
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,
+ E lhs,
const basic_fbstring<E, T, A, S>& rhs) {
basic_fbstring<E, T, A, S> result;
return result;
}
+// C++11 21.4.8.1/8
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(
+ E lhs,
+ basic_fbstring<E, T, A, S>&& rhs) {
+ //
+ if (rhs.capacity() > rhs.size()) {
+ // Good, at least we don't need to reallocate
+ return std::move(rhs.insert(rhs.begin(), lhs));
+ }
+ // Meh, no go. Forward to operator+(E, const&).
+ auto const& rhsC = rhs;
+ return lhs + rhsC;
+}
+
+// C++11 21.4.8.1/9
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) {
+ const E* 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;
return result;
}
+// C++11 21.4.8.1/10
+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 E* rhs) {
+ //
+ return std::move(lhs += rhs);
+}
+
+// C++11 21.4.8.1/11
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) {
+ E rhs) {
basic_fbstring<E, T, A, S> result;
result.reserve(lhs.size() + 1);
return result;
}
+// C++11 21.4.8.1/12
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(
+ basic_fbstring<E, T, A, S>&& lhs,
+ E rhs) {
+ //
+ return std::move(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; }
+ return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
template <typename E, class T, class A, class S>
inline
return !(lhs < rhs);
}
-// subclause 21.3.7.8:
+// 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);
auto err = __ios_base::goodbit;
if (sentry) {
auto n = is.width();
- if (n == 0) {
+ 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
+ for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
+ if (got == T::eof()) {
+ err |= __ios_base::eofbit;
+ is.width(0);
+ break;
+ }
+ if (isspace(got)) break;
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;
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());
+#if _LIBCPP_VERSION
+ typename std::basic_ostream<
+ typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
+ if (__s) {
+ typedef std::ostreambuf_iterator<
+ typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
+ size_t __len = str.size();
+ bool __left =
+ (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
+ if (__pad_and_output(_Ip(os),
+ str.data(),
+ __left ? str.data() + __len : str.data(),
+ str.data() + __len,
+ os,
+ os.fill()).failed()) {
+ os.setstate(std::ios_base::badbit | std::ios_base::failbit);
+ }
+ }
+#else
+ std::__ostream_insert(os, str.data(), str.size());
+#endif
return os;
}
basic_fbstring<E, T, A, S>& str,
typename basic_fbstring<E, T, A, S>::value_type delim) {
// Use the nonstandard getdelim()
- char * buf = NULL;
+ char * buf = nullptr;
size_t size = 0;
for (;;) {
// This looks quadratic but it really depends on realloc
#ifndef _LIBSTDCXX_FBSTRING
+// Hash functions to make fbstring usable with e.g. hash_map
+//
+// Handle interaction with different C++ standard libraries, which
+// expect these types to be in different namespaces.
+
+#define FOLLY_FBSTRING_HASH1(T) \
+ template <> \
+ struct hash< ::folly::basic_fbstring<T> > { \
+ size_t operator()(const ::folly::fbstring& s) const { \
+ return ::folly::hash::fnv32_buf(s.data(), s.size()); \
+ } \
+ };
+
+// The C++11 standard says that these four are defined
+#define FOLLY_FBSTRING_HASH \
+ FOLLY_FBSTRING_HASH1(char) \
+ FOLLY_FBSTRING_HASH1(char16_t) \
+ FOLLY_FBSTRING_HASH1(char32_t) \
+ FOLLY_FBSTRING_HASH1(wchar_t)
+
namespace std {
-template <>
-struct hash< ::folly::fbstring> {
- size_t operator()(const ::folly::fbstring& s) const {
- return ::folly::hash::fnv32_buf(s.data(), s.size());
- }
-};
-}
+
+FOLLY_FBSTRING_HASH
+
+} // namespace std
+
+#if FOLLY_HAVE_DEPRECATED_ASSOC
+#if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
+namespace __gnu_cxx {
+
+FOLLY_FBSTRING_HASH
+
+} // namespace __gnu_cxx
+#endif // _GLIBCXX_SYMVER && !__BIONIC__
+#endif // FOLLY_HAVE_DEPRECATED_ASSOC
+
+#undef FOLLY_FBSTRING_HASH
+#undef FOLLY_FBSTRING_HASH1
#endif // _LIBSTDCXX_FBSTRING
+#pragma GCC diagnostic pop
+
+#undef FBSTRING_DISABLE_ADDRESS_SANITIZER
+#undef throw
#undef FBSTRING_LIKELY
#undef FBSTRING_UNLIKELY
projects / folly.git / blobdiff