/*
- * Copyright 2012 Facebook, Inc.
+ * 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.
#pragma GCC system_header
// Handle the cases where the fbcode version (folly/Malloc.h) is included
-// either before or after this inclusion. */home/engshare/third-party/src/
-// libgcc/libgcc-4.6.2/gcc-4.6.2-20111027/libstdc++-v3/include/bits/
-// basic_string.h* has a more detailed explanation of why this is necessary.
+// either before or after this inclusion.
#ifdef FOLLY_MALLOC_H_
#undef FOLLY_MALLOC_H_
#include "basic_fbstring_malloc.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>
/*
* Lightly structured memcpy, simplifies copying PODs and introduces
- * some asserts
+ * 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 Pod* pod_copy(const Pod* b, const Pod* e, Pod* d) {
+inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
assert(e >= b);
assert(d >= e || d + (e - b) <= b);
- const size_t s = e - b;
- std::memcpy(d, b, s * sizeof(*b));
- return d + s;
+ memcpy(d, b, (e - b) * sizeof(Pod));
}
/*
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. The caller is expected to fill
- // the expanded area appropriately.
- void expand_noinit(size_t delta);
+ // 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);
};
*/
+/**
+ * gcc-4.7 throws what appears to be some false positive uninitialized
+ * warnings for the members of the MediumLarge struct. So, mute them here.
+ */
+# pragma GCC diagnostic push
+# pragma GCC diagnostic ignored "-Wuninitialized"
+
/**
* 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
fbstring_core() {
// Only initialize the tag, will set the MSBs (i.e. the small
// string size) to zero too
- ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - 1));
+ ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
// or: setSmallSize(0);
writeTerminator();
assert(category() == isSmall && size() == 0);
// one extra Char for the null terminator.
auto const allocSize =
goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
- ml_.data_ = static_cast<Char*>(malloc(allocSize));
+ ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
fbstring_detail::pod_copy(rhs.ml_.data_,
// 1 for terminator
rhs.ml_.data_ + rhs.ml_.size_ + 1,
// 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*>(malloc(allocSize));
+ 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;
// 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*>(malloc(allocSizeBytes));
+ auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
auto const size = smallSize();
fbstring_detail::pod_copy(small_, small_ + size + 1, data);
// No need for writeTerminator(), we wrote it above with + 1.
assert(capacity() >= minCapacity);
}
- void expand_noinit(const size_t delta) {
+ Char * expand_noinit(const size_t delta) {
// Strategy is simple: make room, then change size
assert(capacity() >= size());
- size_t sz, newSz, cp;
+ size_t sz, newSz;
if (category() == isSmall) {
sz = smallSize();
newSz = sz + delta;
if (newSz <= maxSmallSize) {
setSmallSize(newSz);
writeTerminator();
- return;
+ return small_ + sz;
}
- cp = maxSmallSize;
+ reserve(newSz);
} else {
sz = ml_.size_;
- newSz = sz + delta;
- cp = capacity();
+ newSz = ml_.size_ + delta;
+ if (newSz > capacity()) {
+ reserve(newSz);
+ }
}
- if (newSz > cp) 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;
}
void push_back(Char c) {
assert(capacity() >= size());
- size_t sz, cp;
+ size_t sz;
if (category() == isSmall) {
sz = smallSize();
if (sz < maxSmallSize) {
writeTerminator();
return;
}
- reserve(maxSmallSize * 3 / 2);
+ reserve(maxSmallSize * 2);
} else {
sz = ml_.size_;
- cp = ml_.capacity();
- if (sz == cp) reserve(cp * 3 / 2);
+ 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;
- mutable_data()[sz] = c;
+ ml_.data_[sz] = c;
writeTerminator();
}
return static_cast<RefCounted*>(
static_cast<void*>(
static_cast<unsigned char*>(static_cast<void*>(p))
- - offsetof(RefCounted, data_)));
+ - sizeof(refCount_)));
}
static size_t refs(Char * p) {
// struct.
const size_t allocSize = goodMallocSize(
sizeof(RefCounted) + *size * sizeof(Char));
- auto result = static_cast<RefCounted*>(malloc(allocSize));
+ auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
result->refCount_.store(1, std::memory_order_release);
*size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
return result;
}
};
+# pragma GCC diagnostic pop
+
#ifndef _LIBSTDCXX_FBSTRING
/**
* Dummy fbstring core that uses an actual std::string. This doesn't
assert(delta <= size());
backend_.resize(size() - delta);
}
- void expand_noinit(size_t 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);
}
basic_fbstring(size_type n, value_type c, const A& a = A()) {
- store_.expand_noinit(n);
- auto const data = store_.mutable_data();
+ auto const data = store_.expand_noinit(n);
fbstring_detail::pod_fill(data, data + n, c);
store_.writeTerminator();
}
return const_reverse_iterator(begin());
}
- // Non-standard functions. They intentionally return by value to
- // reduce pressure on the reference counting mechanism.
- value_type front() const { return *begin(); }
- value_type back() const {
+ // 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());
- return begin()[size() - 1];
+ // 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);
}
- void pop_back() { assert(!empty()); store_.shrink(1); }
// 21.3.3 capacity:
size_type size() const { return store_.size(); }
return append(str.data() + pos, n);
}
- basic_fbstring& append(const value_type* s, const size_type n) {
+ basic_fbstring& append(const value_type* s, size_type n) {
#ifndef NDEBUG
- auto oldSize = size();
-#endif
Invariant checker(*this);
(void) checker;
- static std::less_equal<const value_type*> le;
- if (le(data(), s) && !le(data() + size(), s)) {// aliasing
- assert(le(s + n, data() + size()));
- const size_type offset = s - data();
- store_.reserve(size() + n);
+#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;
}
- store_.expand_noinit(n);
- fbstring_detail::pod_copy(s, s + n, end() - n);
- store_.writeTerminator();
- assert(size() == oldSize + n);
+ // 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;
}
}
// Replaces at most n1 chars of *this, starting with pos, with n2
- // occurences of c
+ // occurrences of c
//
// consolidated with
//
for (;;) {
// This looks quadratic but it really depends on realloc
auto const newSize = size + 128;
- buf = static_cast<char*>(realloc(buf, newSize));
+ buf = static_cast<char*>(checkedRealloc(buf, 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
static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
#ifndef _LIBSTDCXX_FBSTRING
-// basic_string compatiblity routines
+// basic_string compatibility routines
template <typename E, class T, class A, class S>
inline
template <>
struct hash< ::folly::fbstring> {
size_t operator()(const ::folly::fbstring& s) const {
- return ::folly::hash::fnv32(s.c_str());
+ return ::folly::hash::fnv32_buf(s.data(), s.size());
}
};
}
#endif // _LIBSTDCXX_FBSTRING
+#undef FBSTRING_LIKELY
+#undef FBSTRING_UNLIKELY
+
#endif // FOLLY_BASE_FBSTRING_H_
projects / folly.git / blobdiff