X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FFBString.h;h=638ead111315c996f11b4640b1bf7e3c922a7434;hb=f3c3434c45603ab8a17614f0fc92cbc84ba5beec;hp=64249c2845408f390935280ade400a49405cbb43;hpb=427c43f4cb461f375b8598ebc55766fd677963c4;p=folly.git diff --git a/folly/FBString.h b/folly/FBString.h index 64249c28..638ead11 100644 --- a/folly/FBString.h +++ b/folly/FBString.h @@ -1,5 +1,5 @@ /* - * 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. @@ -20,6 +20,8 @@ #pragma once #include +#include +#include #include #include @@ -136,7 +138,7 @@ template 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) { @@ -166,6 +168,9 @@ inline void podFill(Pod* b, Pod* e, T c) { */ template inline void podCopy(const Pod* b, const Pod* e, Pod* d) { + FBSTRING_ASSERT(b != nullptr); + FBSTRING_ASSERT(e != nullptr); + FBSTRING_ASSERT(d != nullptr); FBSTRING_ASSERT(e >= b); FBSTRING_ASSERT(d >= e || d + (e - b) <= b); memcpy(d, b, (e - b) * sizeof(Pod)); @@ -286,13 +291,12 @@ private: * 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 @@ -323,10 +327,18 @@ public: 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); @@ -344,8 +356,10 @@ public: 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( @@ -515,11 +529,14 @@ private: std::atomic refCount_; Char data_[1]; + constexpr static size_t getDataOffset() { + return offsetof(RefCounted, data_); + } + static RefCounted * fromData(Char * p) { - return static_cast( - static_cast( - static_cast(static_cast(p)) - - sizeof(refCount_))); + return static_cast(static_cast( + static_cast(static_cast(p)) - + getDataOffset())); } static size_t refs(Char * p) { @@ -540,40 +557,39 @@ private: } 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(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 * create(const Char * data, size_t * size) { const size_t effectiveSize = *size; auto result = create(size); - fbstring_detail::podCopy(data, data + effectiveSize, result->data_); + if (FBSTRING_LIKELY(effectiveSize > 0)) { + fbstring_detail::podCopy(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) { - 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( - smartRealloc(dis, - sizeof(RefCounted) + currentSize * sizeof(Char), - sizeof(RefCounted) + currentCapacity * sizeof(Char), - sizeof(RefCounted) + newCapacity * sizeof(Char))); + auto result = static_cast(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; } }; @@ -603,7 +619,6 @@ private: } void setCapacity(size_t cap, Category cat) { - FBSTRING_ASSERT(cat != Category::isLarge); capacity_ = kIsLittleEndian ? cap | (static_cast(cat) << kCategoryShift) : (cap << 2) | static_cast(cat); @@ -642,14 +657,14 @@ private: // 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); @@ -668,7 +683,7 @@ private: }; template -inline void fbstring_core::makeSmall(const fbstring_core& rhs) { +inline void fbstring_core::copySmall(const fbstring_core& rhs) { static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure"); static_assert( offsetof(MediumLarge, size_) == sizeof(ml_.data_), @@ -687,7 +702,7 @@ inline void fbstring_core::makeSmall(const fbstring_core& rhs) { } template -FOLLY_MALLOC_NOINLINE inline void fbstring_core::makeMedium( +FOLLY_MALLOC_NOINLINE inline void fbstring_core::copyMedium( const fbstring_core& rhs) { // Medium strings are copied eagerly. Don't forget to allocate // one extra Char for the null terminator. @@ -702,7 +717,7 @@ FOLLY_MALLOC_NOINLINE inline void fbstring_core::makeMedium( } template -FOLLY_MALLOC_NOINLINE inline void fbstring_core::makeLarge( +FOLLY_MALLOC_NOINLINE inline void fbstring_core::copyLarge( const fbstring_core& rhs) { // Large strings are just refcounted ml_ = rhs.ml_; @@ -761,7 +776,9 @@ FOLLY_MALLOC_NOINLINE inline void fbstring_core::initMedium( // allocate one extra Char for the terminating null. auto const allocSize = goodMallocSize((1 + size) * sizeof(Char)); ml_.data_ = static_cast(checkedMalloc(allocSize)); - fbstring_detail::podCopy(data, data + size, ml_.data_); + if (FBSTRING_LIKELY(size > 0)) { + fbstring_detail::podCopy(data, data + size, ml_.data_); + } ml_.size_ = size; ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium); ml_.data_[size] = '\0'; @@ -821,7 +838,7 @@ FOLLY_MALLOC_NOINLINE inline void fbstring_core::reserveLarge( 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); } @@ -837,16 +854,29 @@ FOLLY_MALLOC_NOINLINE inline void fbstring_core::reserveMedium( 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(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(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 @@ -856,17 +886,29 @@ FOLLY_MALLOC_NOINLINE inline void fbstring_core::reserveSmall( 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(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(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 @@ -1144,7 +1186,7 @@ public: // 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 @@ -2665,7 +2707,7 @@ operator<<( } #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