/*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2017 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 once
#include <atomic>
+#include <cstddef>
+#include <ios>
#include <limits>
#include <type_traits>
inline void podFill(Pod* b, Pod* e, T c) {
FBSTRING_ASSERT(b && e && b <= e);
/*static*/ if (sizeof(T) == 1) {
- memset(b, c, e - b);
+ memset(b, c, size_t(e - b));
} else {
auto const ee = b + ((e - b) & ~7u);
for (; b != ee; b += 8) {
* 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 (> 23 chars) are stored in
- * malloc-allocated memory that is copied eagerly.
- * There exists a third storage category: (c) "large", which has the
- * copy-on-write optimization. COW was disallowed in C++11, so large is
- * now deprecated in fbstring_core. fbstring_core no longer creates large
- * strings, though still works with them. Later, large strings will be
- * completely removed.
+ * 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 two
* bits of the rightmost char of the storage. If neither is set, then the
fbstring_core(const fbstring_core & rhs) {
FBSTRING_ASSERT(&rhs != this);
- if (rhs.category() == Category::isSmall) {
- makeSmall(rhs);
- } else {
- makeMedium(rhs);
+ switch (rhs.category()) {
+ case Category::isSmall:
+ copySmall(rhs);
+ break;
+ case Category::isMedium:
+ copyMedium(rhs);
+ break;
+ case Category::isLarge:
+ copyLarge(rhs);
+ break;
+ default:
+ fbstring_detail::assume_unreachable();
}
FBSTRING_ASSERT(size() == rhs.size());
FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
bool disableSSO = FBSTRING_DISABLE_SSO) {
if (!disableSSO && size <= maxSmallSize) {
initSmall(data, size);
- } else {
+ } else if (size <= maxMediumSize) {
initMedium(data, size);
+ } else {
+ initLarge(data, size);
}
FBSTRING_ASSERT(this->size() == size);
FBSTRING_ASSERT(
std::atomic<size_t> refCount_;
Char data_[1];
+ constexpr static size_t getDataOffset() {
+ return offsetof(RefCounted, data_);
+ }
+
static RefCounted * fromData(Char * p) {
- return static_cast<RefCounted*>(
- static_cast<void*>(
- static_cast<unsigned char*>(static_cast<void*>(p))
- - sizeof(refCount_)));
+ return static_cast<RefCounted*>(static_cast<void*>(
+ static_cast<unsigned char*>(static_cast<void*>(p)) -
+ getDataOffset()));
}
static size_t refs(Char * p) {
}
static RefCounted * create(size_t * size) {
- // 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));
+ const size_t allocSize =
+ goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
result->refCount_.store(1, std::memory_order_release);
- *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
+ *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
return result;
}
static RefCounted * reallocate(Char *const data,
const size_t currentSize,
const size_t currentCapacity,
- const size_t newCapacity) {
- FBSTRING_ASSERT(newCapacity > 0 && newCapacity > currentSize);
+ size_t * newCapacity) {
+ FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
+ const size_t allocNewCapacity =
+ goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
auto const dis = fromData(data);
FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 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)));
+ auto result = static_cast<RefCounted*>(smartRealloc(
+ dis,
+ getDataOffset() + (currentSize + 1) * sizeof(Char),
+ getDataOffset() + (currentCapacity + 1) * sizeof(Char),
+ allocNewCapacity));
FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
+ *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
return result;
}
};
}
void setCapacity(size_t cap, Category cat) {
- FBSTRING_ASSERT(cat != Category::isLarge);
capacity_ = kIsLittleEndian
? cap | (static_cast<size_t>(cat) << kCategoryShift)
: (cap << 2) | static_cast<size_t>(cat);
// small_[maxSmallSize].
FBSTRING_ASSERT(s <= maxSmallSize);
constexpr auto shift = kIsLittleEndian ? 0 : 2;
- small_[maxSmallSize] = (maxSmallSize - s) << shift;
+ small_[maxSmallSize] = char((maxSmallSize - s) << shift);
small_[s] = '\0';
FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
}
- void makeSmall(const fbstring_core&);
- void makeMedium(const fbstring_core&);
- void makeLarge(const fbstring_core&);
+ void copySmall(const fbstring_core&);
+ void copyMedium(const fbstring_core&);
+ void copyLarge(const fbstring_core&);
void initSmall(const Char* data, size_t size);
void initMedium(const Char* data, size_t size);
};
template <class Char>
-inline void fbstring_core<Char>::makeSmall(const fbstring_core& rhs) {
+inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
static_assert(
offsetof(MediumLarge, size_) == sizeof(ml_.data_),
}
template <class Char>
-FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::makeMedium(
+FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
const fbstring_core& rhs) {
// Medium strings are copied eagerly. Don't forget to allocate
// one extra Char for the null terminator.
}
template <class Char>
-FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::makeLarge(
+FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
const fbstring_core& rhs) {
// Large strings are just refcounted
ml_ = rhs.ml_;
if (minCapacity > ml_.capacity()) {
// Asking for more memory
auto const newRC = RefCounted::reallocate(
- ml_.data_, ml_.size_, ml_.capacity(), minCapacity);
+ ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
ml_.data_ = newRC->data_;
ml_.setCapacity(minCapacity, Category::isLarge);
}
if (minCapacity <= ml_.capacity()) {
return; // nothing to do, there's enough room
}
- // 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));
- // Also copies terminator.
- ml_.data_ = static_cast<Char*>(smartRealloc(
- ml_.data_,
- (ml_.size_ + 1) * sizeof(Char),
- (ml_.capacity() + 1) * sizeof(Char),
- capacityBytes));
- ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
+ 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));
+ // Also copies terminator.
+ ml_.data_ = static_cast<Char*>(smartRealloc(
+ ml_.data_,
+ (ml_.size_ + 1) * sizeof(Char),
+ (ml_.capacity() + 1) * sizeof(Char),
+ capacityBytes));
+ ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
+ } else {
+ // Conversion from medium to large string
+ fbstring_core nascent;
+ // Will recurse to another branch of this function
+ nascent.reserve(minCapacity);
+ nascent.ml_.size_ = ml_.size_;
+ // Also copies terminator.
+ fbstring_detail::podCopy(
+ ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
+ nascent.swap(*this);
+ FBSTRING_ASSERT(capacity() >= minCapacity);
+ }
}
template <class Char>
if (!disableSSO && minCapacity <= maxSmallSize) {
// small
// Nothing to do, everything stays put
- return;
+ } else if (minCapacity <= maxMediumSize) {
+ // medium
+ // Don't forget to allocate one extra Char for the terminating null
+ auto const allocSizeBytes =
+ goodMallocSize((1 + minCapacity) * sizeof(Char));
+ auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
+ auto const size = smallSize();
+ // Also copies terminator.
+ fbstring_detail::podCopy(small_, small_ + size + 1, pData);
+ ml_.data_ = pData;
+ ml_.size_ = size;
+ ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
+ } else {
+ // large
+ auto const newRC = RefCounted::create(&minCapacity);
+ auto const size = smallSize();
+ // Also copies terminator.
+ fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
+ ml_.data_ = newRC->data_;
+ ml_.size_ = size;
+ ml_.setCapacity(minCapacity, Category::isLarge);
+ FBSTRING_ASSERT(capacity() >= minCapacity);
}
- // Don't forget to allocate one extra Char for the terminating null
- auto const allocSizeBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
- auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
- auto const size = smallSize();
- // Also copies terminator.
- fbstring_detail::podCopy(small_, small_ + size + 1, pData);
- ml_.data_ = pData;
- ml_.size_ = size;
- ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
}
template <class Char>
// Specialization for const char*, const char*
FOLLY_MALLOC_NOINLINE
basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
- : store_(b, e - b) {
+ : store_(b, size_type(e - b)) {
}
// Nonstandard constructor
}
#elif defined(_MSC_VER)
// MSVC doesn't define __ostream_insert
- os.write(str.data(), str.size());
+ os.write(str.data(), std::streamsize(str.size()));
#else
std::__ostream_insert(os, str.data(), str.size());
#endif
projects / folly.git / blobdiff