/*
- * Copyright 2013 Facebook, Inc.
+ * Copyright 2014 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
#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))
-
-#include <atomic>
-#include <limits>
-#include <type_traits>
+#else
+#define FBSTRING_LIKELY(x) (x)
+#define FBSTRING_UNLIKELY(x) (x)
+#endif
// Ignore shadowing warnings within this file, so includers can use -Wshadow.
#pragma GCC diagnostic push
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;
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_));
+ 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_;
// 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_.capacity_ = effectiveCapacity | isLarge;
}
writeTerminator();
- assert(this->size() == size);
- assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
}
~fbstring_core() noexcept {
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_;
}
// 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) {
newSz = sz + delta;
if (newSz <= maxSmallSize) {
setSmallSize(newSz);
- writeTerminator();
return small_ + sz;
}
reserve(newSz);
if (category() == isSmall) {
sz = smallSize();
if (sz < maxSmallSize) {
- setSmallSize(sz + 1);
small_[sz] = c;
- writeTerminator();
+ setSmallSize(sz + 1);
return;
}
reserve(maxSmallSize * 2);
return 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) {
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 {
}
size_t smallSize() const {
- assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
+ assert(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;
}
/* 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())
// 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);
}
}
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;
}
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) {
+#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
} // namespace folly
-#pragma GCC diagnostic pop
-
#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.
namespace std {
+
+template <class C>
+struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
+ size_t operator()(const folly::basic_fbstring<C> & s) const {
+ return hash<const C*>::operator()(s.c_str());
+ }
+};
+
+template <>
+struct hash< ::folly::fbstring> {
+ size_t operator()(const ::folly::fbstring& s) const {
+ return ::folly::hash::fnv32_buf(s.data(), s.size());
+ }
+};
+
+}
+
+#ifndef _LIBSTDCXX_FBSTRING
+#if FOLLY_HAVE_DEPRECATED_ASSOC
+#if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
+namespace __gnu_cxx {
+
+template <class C>
+struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
+ size_t operator()(const folly::basic_fbstring<C> & s) const {
+ return hash<const C*>::operator()(s.c_str());
+ }
+};
+
template <>
struct hash< ::folly::fbstring> {
size_t operator()(const ::folly::fbstring& s) const {
return ::folly::hash::fnv32_buf(s.data(), s.size());
}
};
+
}
+#endif // _GLIBCXX_SYMVER && !__BIONIC__
+#endif // FOLLY_HAVE_DEPRECATED_ASSOC
+#endif // _LIBSTDCXX_FBSTRING
#endif // _LIBSTDCXX_FBSTRING
+#pragma GCC diagnostic pop
+
#undef FBSTRING_DISABLE_ADDRESS_SANITIZER
#undef throw
#undef FBSTRING_LIKELY