diff options
Diffstat (limited to 'abseil-cpp/absl/strings/cord.h')
| -rw-r--r-- | abseil-cpp/absl/strings/cord.h | 798 |
1 files changed, 591 insertions, 207 deletions
diff --git a/abseil-cpp/absl/strings/cord.h b/abseil-cpp/absl/strings/cord.h index b8b251b..457ccf0 100644 --- a/abseil-cpp/absl/strings/cord.h +++ b/abseil-cpp/absl/strings/cord.h @@ -20,12 +20,11 @@ // structure. A Cord is a string-like sequence of characters optimized for // specific use cases. Unlike a `std::string`, which stores an array of // contiguous characters, Cord data is stored in a structure consisting of -// separate, reference-counted "chunks." (Currently, this implementation is a -// tree structure, though that implementation may change.) +// separate, reference-counted "chunks." // // Because a Cord consists of these chunks, data can be added to or removed from // a Cord during its lifetime. Chunks may also be shared between Cords. Unlike a -// `std::string`, a Cord can therefore accomodate data that changes over its +// `std::string`, a Cord can therefore accommodate data that changes over its // lifetime, though it's not quite "mutable"; it can change only in the // attachment, detachment, or rearrangement of chunks of its constituent data. // @@ -70,15 +69,31 @@ #include <string> #include <type_traits> +#include "absl/base/attributes.h" +#include "absl/base/config.h" #include "absl/base/internal/endian.h" #include "absl/base/internal/per_thread_tls.h" #include "absl/base/macros.h" #include "absl/base/port.h" #include "absl/container/inlined_vector.h" +#include "absl/crc/internal/crc_cord_state.h" #include "absl/functional/function_ref.h" #include "absl/meta/type_traits.h" +#include "absl/strings/cord_analysis.h" +#include "absl/strings/cord_buffer.h" +#include "absl/strings/internal/cord_data_edge.h" #include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_btree.h" +#include "absl/strings/internal/cord_rep_btree_reader.h" +#include "absl/strings/internal/cord_rep_crc.h" +#include "absl/strings/internal/cord_rep_ring.h" +#include "absl/strings/internal/cordz_functions.h" +#include "absl/strings/internal/cordz_info.h" +#include "absl/strings/internal/cordz_statistics.h" +#include "absl/strings/internal/cordz_update_scope.h" +#include "absl/strings/internal/cordz_update_tracker.h" #include "absl/strings/internal/resize_uninitialized.h" +#include "absl/strings/internal/string_constant.h" #include "absl/strings/string_view.h" #include "absl/types/optional.h" @@ -90,6 +105,41 @@ template <typename Releaser> Cord MakeCordFromExternal(absl::string_view, Releaser&&); void CopyCordToString(const Cord& src, std::string* dst); +// Cord memory accounting modes +enum class CordMemoryAccounting { + // Counts the *approximate* number of bytes held in full or in part by this + // Cord (which may not remain the same between invocations). Cords that share + // memory could each be "charged" independently for the same shared memory. + // See also comment on `kTotalMorePrecise` on internally shared memory. + kTotal, + + // Counts the *approximate* number of bytes held in full or in part by this + // Cord for the distinct memory held by this cord. This option is similar + // to `kTotal`, except that if the cord has multiple references to the same + // memory, that memory is only counted once. + // + // For example: + // absl::Cord cord; + // cord.append(some_other_cord); + // cord.append(some_other_cord); + // // Counts `some_other_cord` twice: + // cord.EstimatedMemoryUsage(kTotal); + // // Counts `some_other_cord` once: + // cord.EstimatedMemoryUsage(kTotalMorePrecise); + // + // The `kTotalMorePrecise` number is more expensive to compute as it requires + // deduplicating all memory references. Applications should prefer to use + // `kFairShare` or `kTotal` unless they really need a more precise estimate + // on "how much memory is potentially held / kept alive by this cord?" + kTotalMorePrecise, + + // Counts the *approximate* number of bytes held in full or in part by this + // Cord weighted by the sharing ratio of that data. For example, if some data + // edge is shared by 4 different Cords, then each cord is attributed 1/4th of + // the total memory usage as a 'fair share' of the total memory usage. + kFairShare, +}; + // Cord // // A Cord is a sequence of characters, designed to be more efficient than a @@ -204,7 +254,7 @@ class Cord { // // Releases the Cord data. Any nodes that share data with other Cords, if // applicable, will have their reference counts reduced by 1. - void Clear(); + ABSL_ATTRIBUTE_REINITIALIZES void Clear(); // Cord::Append() // @@ -216,6 +266,58 @@ class Cord { template <typename T, EnableIfString<T> = 0> void Append(T&& src); + // Appends `buffer` to this cord, unless `buffer` has a zero length in which + // case this method has no effect on this cord instance. + // This method is guaranteed to consume `buffer`. + void Append(CordBuffer buffer); + + // Returns a CordBuffer, re-using potential existing capacity in this cord. + // + // Cord instances may have additional unused capacity in the last (or first) + // nodes of the underlying tree to facilitate amortized growth. This method + // allows applications to explicitly use this spare capacity if available, + // or create a new CordBuffer instance otherwise. + // If this cord has a final non-shared node with at least `min_capacity` + // available, then this method will return that buffer including its data + // contents. I.e.; the returned buffer will have a non-zero length, and + // a capacity of at least `buffer.length + min_capacity`. Otherwise, this + // method will return `CordBuffer::CreateWithDefaultLimit(capacity)`. + // + // Below an example of using GetAppendBuffer. Notice that in this example we + // use `GetAppendBuffer()` only on the first iteration. As we know nothing + // about any initial extra capacity in `cord`, we may be able to use the extra + // capacity. But as we add new buffers with fully utilized contents after that + // we avoid calling `GetAppendBuffer()` on subsequent iterations: while this + // works fine, it results in an unnecessary inspection of cord contents: + // + // void AppendRandomDataToCord(absl::Cord &cord, size_t n) { + // bool first = true; + // while (n > 0) { + // CordBuffer buffer = first ? cord.GetAppendBuffer(n) + // : CordBuffer::CreateWithDefaultLimit(n); + // absl::Span<char> data = buffer.available_up_to(n); + // FillRandomValues(data.data(), data.size()); + // buffer.IncreaseLengthBy(data.size()); + // cord.Append(std::move(buffer)); + // n -= data.size(); + // first = false; + // } + // } + CordBuffer GetAppendBuffer(size_t capacity, size_t min_capacity = 16); + + // Returns a CordBuffer, re-using potential existing capacity in this cord. + // + // This function is identical to `GetAppendBuffer`, except that in the case + // where a new `CordBuffer` is allocated, it is allocated using the provided + // custom limit instead of the default limit. `GetAppendBuffer` will default + // to `CordBuffer::CreateWithDefaultLimit(capacity)` whereas this method + // will default to `CordBuffer::CreateWithCustomLimit(block_size, capacity)`. + // This method is equivalent to `GetAppendBuffer` if `block_size` is zero. + // See the documentation for `CreateWithCustomLimit` for more details on the + // restrictions and legal values for `block_size`. + CordBuffer GetCustomAppendBuffer(size_t block_size, size_t capacity, + size_t min_capacity = 16); + // Cord::Prepend() // // Prepends data to the Cord, which may come from another Cord or other string @@ -225,6 +327,11 @@ class Cord { template <typename T, EnableIfString<T> = 0> void Prepend(T&& src); + // Prepends `buffer` to this cord, unless `buffer` has a zero length in which + // case this method has no effect on this cord instance. + // This method is guaranteed to consume `buffer`. + void Prepend(CordBuffer buffer); + // Cord::RemovePrefix() // // Removes the first `n` bytes of a Cord. @@ -246,9 +353,7 @@ class Cord { // swap() // // Swaps the contents of two Cords. - friend void swap(Cord& x, Cord& y) noexcept { - x.swap(y); - } + friend void swap(Cord& x, Cord& y) noexcept { x.swap(y); } // Cord::size() // @@ -262,11 +367,10 @@ class Cord { // Cord::EstimatedMemoryUsage() // - // Returns the *approximate* number of bytes held in full or in part by this - // Cord (which may not remain the same between invocations). Note that Cords - // that share memory could each be "charged" independently for the same shared - // memory. - size_t EstimatedMemoryUsage() const; + // Returns the *approximate* number of bytes held by this cord. + // See CordMemoryAccounting for more information on the accounting method. + size_t EstimatedMemoryUsage(CordMemoryAccounting accounting_method = + CordMemoryAccounting::kTotal) const; // Cord::Compare() // @@ -286,7 +390,7 @@ class Cord { bool StartsWith(const Cord& rhs) const; bool StartsWith(absl::string_view rhs) const; - // Cord::EndsWidth() + // Cord::EndsWith() // // Determines whether the Cord ends with the passed string data `rhs`. bool EndsWith(absl::string_view rhs) const; @@ -316,7 +420,7 @@ class Cord { //---------------------------------------------------------------------------- // // A `Cord::ChunkIterator` allows iteration over the constituent chunks of its - // Cord. Such iteration allows you to perform non-const operatons on the data + // Cord. Such iteration allows you to perform non-const operations on the data // of a Cord without modifying it. // // Generally, you do not instantiate a `Cord::ChunkIterator` directly; @@ -360,17 +464,28 @@ class Cord { friend class CharIterator; private: + using CordRep = absl::cord_internal::CordRep; + using CordRepBtree = absl::cord_internal::CordRepBtree; + using CordRepBtreeReader = absl::cord_internal::CordRepBtreeReader; + + // Constructs a `begin()` iterator from `tree`. `tree` must not be null. + explicit ChunkIterator(cord_internal::CordRep* tree); + // Constructs a `begin()` iterator from `cord`. explicit ChunkIterator(const Cord* cord); + // Initializes this instance from a tree. Invoked by constructors. + void InitTree(cord_internal::CordRep* tree); + // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than // `current_chunk_.size()`. void RemoveChunkPrefix(size_t n); Cord AdvanceAndReadBytes(size_t n); void AdvanceBytes(size_t n); - // Iterates `n` bytes, where `n` is expected to be greater than or equal to - // `current_chunk_.size()`. - void AdvanceBytesSlowPath(size_t n); + + // Btree specific operator++ + ChunkIterator& AdvanceBtree(); + void AdvanceBytesBtree(size_t n); // A view into bytes of the current `CordRep`. It may only be a view to a // suffix of bytes if this is being used by `CharIterator`. @@ -381,11 +496,12 @@ class Cord { absl::cord_internal::CordRep* current_leaf_ = nullptr; // The number of bytes left in the `Cord` over which we are iterating. size_t bytes_remaining_ = 0; - absl::InlinedVector<absl::cord_internal::CordRep*, 4> - stack_of_right_children_; + + // Cord reader for cord btrees. Empty if not traversing a btree. + CordRepBtreeReader btree_reader_; }; - // Cord::ChunkIterator::chunk_begin() + // Cord::chunk_begin() // // Returns an iterator to the first chunk of the `Cord`. // @@ -401,7 +517,7 @@ class Cord { // } ChunkIterator chunk_begin() const; - // Cord::ChunkItertator::chunk_end() + // Cord::chunk_end() // // Returns an iterator one increment past the last chunk of the `Cord`. // @@ -411,7 +527,7 @@ class Cord { ChunkIterator chunk_end() const; //---------------------------------------------------------------------------- - // Cord::ChunkIterator::ChunkRange + // Cord::ChunkRange //---------------------------------------------------------------------------- // // `ChunkRange` is a helper class for iterating over the chunks of the `Cord`, @@ -424,6 +540,16 @@ class Cord { // `Cord::chunk_begin()` and `Cord::chunk_end()`. class ChunkRange { public: + // Fulfill minimum c++ container requirements [container.requirements] + // These (partial) container type definitions allow ChunkRange to be used + // in various utilities expecting a subset of [container.requirements]. + // For example, the below enables using `::testing::ElementsAre(...)` + using value_type = absl::string_view; + using reference = value_type&; + using const_reference = const value_type&; + using iterator = ChunkIterator; + using const_iterator = ChunkIterator; + explicit ChunkRange(const Cord* cord) : cord_(cord) {} ChunkIterator begin() const; @@ -435,9 +561,9 @@ class Cord { // Cord::Chunks() // - // Returns a `Cord::ChunkIterator::ChunkRange` for iterating over the chunks - // of a `Cord` with a range-based for-loop. For most iteration tasks on a - // Cord, use `Cord::Chunks()` to retrieve this iterator. + // Returns a `Cord::ChunkRange` for iterating over the chunks of a `Cord` with + // a range-based for-loop. For most iteration tasks on a Cord, use + // `Cord::Chunks()` to retrieve this iterator. // // Example: // @@ -503,7 +629,7 @@ class Cord { ChunkIterator chunk_iterator_; }; - // Cord::CharIterator::AdvanceAndRead() + // Cord::AdvanceAndRead() // // Advances the `Cord::CharIterator` by `n_bytes` and returns the bytes // advanced as a separate `Cord`. `n_bytes` must be less than or equal to the @@ -511,21 +637,21 @@ class Cord { // valid to pass `char_end()` and `0`. static Cord AdvanceAndRead(CharIterator* it, size_t n_bytes); - // Cord::CharIterator::Advance() + // Cord::Advance() // // Advances the `Cord::CharIterator` by `n_bytes`. `n_bytes` must be less than // or equal to the number of bytes remaining within the Cord; otherwise, // behavior is undefined. It is valid to pass `char_end()` and `0`. static void Advance(CharIterator* it, size_t n_bytes); - // Cord::CharIterator::ChunkRemaining() + // Cord::ChunkRemaining() // // Returns the longest contiguous view starting at the iterator's position. // // `it` must be dereferenceable. static absl::string_view ChunkRemaining(const CharIterator& it); - // Cord::CharIterator::char_begin() + // Cord::char_begin() // // Returns an iterator to the first character of the `Cord`. // @@ -534,7 +660,7 @@ class Cord { // a `CharIterator` where range-based for-loops may not be available. CharIterator char_begin() const; - // Cord::CharIterator::char_end() + // Cord::char_end() // // Returns an iterator to one past the last character of the `Cord`. // @@ -543,18 +669,28 @@ class Cord { // a `CharIterator` where range-based for-loops are not useful. CharIterator char_end() const; - // Cord::CharIterator::CharRange + // Cord::CharRange // // `CharRange` is a helper class for iterating over the characters of a // producing an iterator which can be used within a range-based for loop. // Construction of a `CharRange` will return an iterator pointing to the first // character of the Cord. Generally, do not construct a `CharRange` directly; - // instead, prefer to use the `Cord::Chars()` method show below. + // instead, prefer to use the `Cord::Chars()` method shown below. // // Implementation note: `CharRange` is simply a convenience wrapper over // `Cord::char_begin()` and `Cord::char_end()`. class CharRange { public: + // Fulfill minimum c++ container requirements [container.requirements] + // These (partial) container type definitions allow CharRange to be used + // in various utilities expecting a subset of [container.requirements]. + // For example, the below enables using `::testing::ElementsAre(...)` + using value_type = char; + using reference = value_type&; + using const_reference = const value_type&; + using iterator = CharIterator; + using const_iterator = CharIterator; + explicit CharRange(const Cord* cord) : cord_(cord) {} CharIterator begin() const; @@ -564,11 +700,11 @@ class Cord { const Cord* cord_; }; - // Cord::CharIterator::Chars() + // Cord::Chars() // - // Returns a `Cord::CharIterator` for iterating over the characters of a - // `Cord` with a range-based for-loop. For most character-based iteration - // tasks on a Cord, use `Cord::Chars()` to retrieve this iterator. + // Returns a `Cord::CharRange` for iterating over the characters of a `Cord` + // with a range-based for-loop. For most character-based iteration tasks on a + // Cord, use `Cord::Chars()` to retrieve this iterator. // // Example: // @@ -615,6 +751,29 @@ class Cord { cord->Append(part); } + // Cord::SetExpectedChecksum() + // + // Stores a checksum value with this non-empty cord instance, for later + // retrieval. + // + // The expected checksum is a number stored out-of-band, alongside the data. + // It is preserved across copies and assignments, but any mutations to a cord + // will cause it to lose its expected checksum. + // + // The expected checksum is not part of a Cord's value, and does not affect + // operations such as equality or hashing. + // + // This field is intended to store a CRC32C checksum for later validation, to + // help support end-to-end checksum workflows. However, the Cord API itself + // does no CRC validation, and assigns no meaning to this number. + // + // This call has no effect if this cord is empty. + void SetExpectedChecksum(uint32_t crc); + + // Returns this cord's expected checksum, if it has one. Otherwise, returns + // nullopt. + absl::optional<uint32_t> ExpectedChecksum() const; + template <typename H> friend H AbslHashValue(H hash_state, const absl::Cord& c) { absl::optional<absl::string_view> maybe_flat = c.TryFlat(); @@ -624,11 +783,34 @@ class Cord { return c.HashFragmented(std::move(hash_state)); } + // Create a Cord with the contents of StringConstant<T>::value. + // No allocations will be done and no data will be copied. + // This is an INTERNAL API and subject to change or removal. This API can only + // be used by spelling absl::strings_internal::MakeStringConstant, which is + // also an internal API. + template <typename T> + // NOLINTNEXTLINE(google-explicit-constructor) + constexpr Cord(strings_internal::StringConstant<T>); + private: + using CordRep = absl::cord_internal::CordRep; + using CordRepFlat = absl::cord_internal::CordRepFlat; + using CordzInfo = cord_internal::CordzInfo; + using CordzUpdateScope = cord_internal::CordzUpdateScope; + using CordzUpdateTracker = cord_internal::CordzUpdateTracker; + using InlineData = cord_internal::InlineData; + using MethodIdentifier = CordzUpdateTracker::MethodIdentifier; + + // Creates a cord instance with `method` representing the originating + // public API call causing the cord to be created. + explicit Cord(absl::string_view src, MethodIdentifier method); + friend class CordTestPeer; friend bool operator==(const Cord& lhs, const Cord& rhs); friend bool operator==(const Cord& lhs, absl::string_view rhs); + friend const CordzInfo* GetCordzInfoForTesting(const Cord& cord); + // Calls the provided function once for each cord chunk, in order. Unlike // Chunks(), this API will not allocate memory. void ForEachChunk(absl::FunctionRef<void(absl::string_view)>) const; @@ -644,96 +826,138 @@ class Cord { // InlineRep holds either a tree pointer, or an array of kMaxInline bytes. class InlineRep { public: - static constexpr unsigned char kMaxInline = 15; + static constexpr unsigned char kMaxInline = cord_internal::kMaxInline; static_assert(kMaxInline >= sizeof(absl::cord_internal::CordRep*), ""); - // Tag byte & kMaxInline means we are storing a pointer. - static constexpr unsigned char kTreeFlag = 1 << 4; - // Tag byte & kProfiledFlag means we are profiling the Cord. - static constexpr unsigned char kProfiledFlag = 1 << 5; - constexpr InlineRep() : data_{} {} + constexpr InlineRep() : data_() {} + explicit InlineRep(InlineData::DefaultInitType init) : data_(init) {} InlineRep(const InlineRep& src); InlineRep(InlineRep&& src); InlineRep& operator=(const InlineRep& src); InlineRep& operator=(InlineRep&& src) noexcept; + explicit constexpr InlineRep(absl::string_view sv, CordRep* rep); + void Swap(InlineRep* rhs); bool empty() const; size_t size() const; const char* data() const; // Returns nullptr if holding pointer - void set_data(const char* data, size_t n, - bool nullify_tail); // Discards pointer, if any - char* set_data(size_t n); // Write data to the result + void set_data(const char* data, size_t n); // Discards pointer, if any + char* set_data(size_t n); // Write data to the result // Returns nullptr if holding bytes absl::cord_internal::CordRep* tree() const; - // Discards old pointer, if any - void set_tree(absl::cord_internal::CordRep* rep); - // Replaces a tree with a new root. This is faster than set_tree, but it - // should only be used when it's clear that the old rep was a tree. - void replace_tree(absl::cord_internal::CordRep* rep); + absl::cord_internal::CordRep* as_tree() const; + const char* as_chars() const; // Returns non-null iff was holding a pointer absl::cord_internal::CordRep* clear(); // Converts to pointer if necessary. - absl::cord_internal::CordRep* force_tree(size_t extra_hint); - void reduce_size(size_t n); // REQUIRES: holding data + void reduce_size(size_t n); // REQUIRES: holding data void remove_prefix(size_t n); // REQUIRES: holding data - void AppendArray(const char* src_data, size_t src_size); + void AppendArray(absl::string_view src, MethodIdentifier method); absl::string_view FindFlatStartPiece() const; - void AppendTree(absl::cord_internal::CordRep* tree); - void PrependTree(absl::cord_internal::CordRep* tree); - void GetAppendRegion(char** region, size_t* size, size_t max_length); - void GetAppendRegion(char** region, size_t* size); - bool IsSame(const InlineRep& other) const { - return memcmp(data_, other.data_, sizeof(data_)) == 0; - } - int BitwiseCompare(const InlineRep& other) const { - uint64_t x, y; - // Use memcpy to avoid anti-aliasing issues. - memcpy(&x, data_, sizeof(x)); - memcpy(&y, other.data_, sizeof(y)); - if (x == y) { - memcpy(&x, data_ + 8, sizeof(x)); - memcpy(&y, other.data_ + 8, sizeof(y)); - if (x == y) return 0; - } - return absl::big_endian::FromHost64(x) < absl::big_endian::FromHost64(y) - ? -1 - : 1; - } + + // Creates a CordRepFlat instance from the current inlined data with `extra' + // bytes of desired additional capacity. + CordRepFlat* MakeFlatWithExtraCapacity(size_t extra); + + // Sets the tree value for this instance. `rep` must not be null. + // Requires the current instance to hold a tree, and a lock to be held on + // any CordzInfo referenced by this instance. The latter is enforced through + // the CordzUpdateScope argument. If the current instance is sampled, then + // the CordzInfo instance is updated to reference the new `rep` value. + void SetTree(CordRep* rep, const CordzUpdateScope& scope); + + // Identical to SetTree(), except that `rep` is allowed to be null, in + // which case the current instance is reset to an empty value. + void SetTreeOrEmpty(CordRep* rep, const CordzUpdateScope& scope); + + // Sets the tree value for this instance, and randomly samples this cord. + // This function disregards existing contents in `data_`, and should be + // called when a Cord is 'promoted' from an 'uninitialized' or 'inlined' + // value to a non-inlined (tree / ring) value. + void EmplaceTree(CordRep* rep, MethodIdentifier method); + + // Identical to EmplaceTree, except that it copies the parent stack from + // the provided `parent` data if the parent is sampled. + void EmplaceTree(CordRep* rep, const InlineData& parent, + MethodIdentifier method); + + // Commits the change of a newly created, or updated `rep` root value into + // this cord. `old_rep` indicates the old (inlined or tree) value of the + // cord, and determines if the commit invokes SetTree() or EmplaceTree(). + void CommitTree(const CordRep* old_rep, CordRep* rep, + const CordzUpdateScope& scope, MethodIdentifier method); + + void AppendTreeToInlined(CordRep* tree, MethodIdentifier method); + void AppendTreeToTree(CordRep* tree, MethodIdentifier method); + void AppendTree(CordRep* tree, MethodIdentifier method); + void PrependTreeToInlined(CordRep* tree, MethodIdentifier method); + void PrependTreeToTree(CordRep* tree, MethodIdentifier method); + void PrependTree(CordRep* tree, MethodIdentifier method); + + bool IsSame(const InlineRep& other) const { return data_ == other.data_; } + void CopyTo(std::string* dst) const { // memcpy is much faster when operating on a known size. On most supported // platforms, the small string optimization is large enough that resizing // to 15 bytes does not cause a memory allocation. - absl::strings_internal::STLStringResizeUninitialized(dst, - sizeof(data_) - 1); - memcpy(&(*dst)[0], data_, sizeof(data_) - 1); + absl::strings_internal::STLStringResizeUninitialized(dst, kMaxInline); + data_.copy_max_inline_to(&(*dst)[0]); // erase is faster than resize because the logic for memory allocation is // not needed. - dst->erase(data_[kMaxInline]); + dst->erase(inline_size()); } // Copies the inline contents into `dst`. Assumes the cord is not empty. void CopyToArray(char* dst) const; - bool is_tree() const { return data_[kMaxInline] > kMaxInline; } + bool is_tree() const { return data_.is_tree(); } + + // Returns true if the Cord is being profiled by cordz. + bool is_profiled() const { return data_.is_tree() && data_.is_profiled(); } + + // Returns the available inlined capacity, or 0 if is_tree() == true. + size_t remaining_inline_capacity() const { + return data_.is_tree() ? 0 : kMaxInline - data_.inline_size(); + } + + // Returns the profiled CordzInfo, or nullptr if not sampled. + absl::cord_internal::CordzInfo* cordz_info() const { + return data_.cordz_info(); + } + + // Sets the profiled CordzInfo. `cordz_info` must not be null. + void set_cordz_info(cord_internal::CordzInfo* cordz_info) { + assert(cordz_info != nullptr); + data_.set_cordz_info(cordz_info); + } + + // Resets the current cordz_info to null / empty. + void clear_cordz_info() { data_.clear_cordz_info(); } private: friend class Cord; void AssignSlow(const InlineRep& src); - // Unrefs the tree, stops profiling, and zeroes the contents - void ClearSlow(); + // Unrefs the tree and stops profiling. + void UnrefTree(); + + void ResetToEmpty() { data_ = {}; } - // If the data has length <= kMaxInline, we store it in data_[0..len-1], - // and store the length in data_[kMaxInline]. Else we store it in a tree - // and store a pointer to that tree in data_[0..sizeof(CordRep*)-1]. - alignas(absl::cord_internal::CordRep*) char data_[kMaxInline + 1]; + void set_inline_size(size_t size) { data_.set_inline_size(size); } + size_t inline_size() const { return data_.inline_size(); } + + // Empty cords that carry a checksum have a CordRepCrc node with a null + // child node. The code can avoid lots of special cases where it would + // otherwise transition from tree to inline storage if we just remove the + // CordRepCrc node before mutations. Must never be called inside a + // CordzUpdateScope since it untracks the cordz info. + void MaybeRemoveEmptyCrcNode(); + + cord_internal::InlineData data_; }; InlineRep contents_; - // Helper for MemoryUsage(). - static size_t MemoryUsageAux(const absl::cord_internal::CordRep* rep); - // Helper for GetFlat() and TryFlat(). static bool GetFlatAux(absl::cord_internal::CordRep* rep, absl::string_view* fragment); @@ -771,6 +995,24 @@ class Cord { template <typename C> void AppendImpl(C&& src); + // Appends / Prepends `src` to this instance, using precise sizing. + // This method does explicitly not attempt to use any spare capacity + // in any pending last added private owned flat. + // Requires `src` to be <= kMaxFlatLength. + void AppendPrecise(absl::string_view src, MethodIdentifier method); + void PrependPrecise(absl::string_view src, MethodIdentifier method); + + CordBuffer GetAppendBufferSlowPath(size_t block_size, size_t capacity, + size_t min_capacity); + + // Prepends the provided data to this instance. `method` contains the public + // API method for this action which is tracked for Cordz sampling purposes. + void PrependArray(absl::string_view src, MethodIdentifier method); + + // Assigns the value in 'src' to this instance, 'stealing' its contents. + // Requires src.length() > kMaxBytesToCopy. + Cord& AssignLargeString(std::string&& src); + // Helper for AbslHashValue(). template <typename H> H HashFragmented(H hash_state) const { @@ -781,6 +1023,10 @@ class Cord { }); return H::combine(combiner.finalize(std::move(hash_state)), size()); } + + friend class CrcCord; + void SetCrcCordState(crc_internal::CrcCordState state); + const crc_internal::CrcCordState* MaybeGetCrcCordState() const; }; ABSL_NAMESPACE_END @@ -797,63 +1043,17 @@ extern std::ostream& operator<<(std::ostream& out, const Cord& cord); namespace cord_internal { -// Fast implementation of memmove for up to 15 bytes. This implementation is -// safe for overlapping regions. If nullify_tail is true, the destination is -// padded with '\0' up to 16 bytes. -inline void SmallMemmove(char* dst, const char* src, size_t n, - bool nullify_tail = false) { - if (n >= 8) { - assert(n <= 16); - uint64_t buf1; - uint64_t buf2; - memcpy(&buf1, src, 8); - memcpy(&buf2, src + n - 8, 8); - if (nullify_tail) { - memset(dst + 8, 0, 8); - } - memcpy(dst, &buf1, 8); - memcpy(dst + n - 8, &buf2, 8); - } else if (n >= 4) { - uint32_t buf1; - uint32_t buf2; - memcpy(&buf1, src, 4); - memcpy(&buf2, src + n - 4, 4); - if (nullify_tail) { - memset(dst + 4, 0, 4); - memset(dst + 8, 0, 8); - } - memcpy(dst, &buf1, 4); - memcpy(dst + n - 4, &buf2, 4); - } else { - if (n != 0) { - dst[0] = src[0]; - dst[n / 2] = src[n / 2]; - dst[n - 1] = src[n - 1]; - } - if (nullify_tail) { - memset(dst + 8, 0, 8); - memset(dst + n, 0, 8); - } - } -} - // Does non-template-specific `CordRepExternal` initialization. -// Expects `data` to be non-empty. +// Requires `data` to be non-empty. void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep); // Creates a new `CordRep` that owns `data` and `releaser` and returns a pointer -// to it, or `nullptr` if `data` was empty. +// to it. Requires `data` to be non-empty. template <typename Releaser> // NOLINTNEXTLINE - suppress clang-tidy raw pointer return. CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) { + assert(!data.empty()); using ReleaserType = absl::decay_t<Releaser>; - if (data.empty()) { - // Never create empty external nodes. - InvokeReleaser(Rank0{}, ReleaserType(std::forward<Releaser>(releaser)), - data); - return nullptr; - } - CordRepExternal* rep = new CordRepExternalImpl<ReleaserType>( std::forward<Releaser>(releaser), 0); InitializeCordRepExternal(data, rep); @@ -873,18 +1073,34 @@ inline CordRep* NewExternalRep(absl::string_view data, template <typename Releaser> Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser) { Cord cord; - cord.contents_.set_tree(::absl::cord_internal::NewExternalRep( - data, std::forward<Releaser>(releaser))); + if (ABSL_PREDICT_TRUE(!data.empty())) { + cord.contents_.EmplaceTree(::absl::cord_internal::NewExternalRep( + data, std::forward<Releaser>(releaser)), + Cord::MethodIdentifier::kMakeCordFromExternal); + } else { + using ReleaserType = absl::decay_t<Releaser>; + cord_internal::InvokeReleaser( + cord_internal::Rank0{}, ReleaserType(std::forward<Releaser>(releaser)), + data); + } return cord; } -inline Cord::InlineRep::InlineRep(const Cord::InlineRep& src) { - cord_internal::SmallMemmove(data_, src.data_, sizeof(data_)); +constexpr Cord::InlineRep::InlineRep(absl::string_view sv, CordRep* rep) + : data_(sv, rep) {} + +inline Cord::InlineRep::InlineRep(const Cord::InlineRep& src) + : data_(InlineData::kDefaultInit) { + if (CordRep* tree = src.tree()) { + EmplaceTree(CordRep::Ref(tree), src.data_, + CordzUpdateTracker::kConstructorCord); + } else { + data_ = src.data_; + } } -inline Cord::InlineRep::InlineRep(Cord::InlineRep&& src) { - memcpy(data_, src.data_, sizeof(data_)); - memset(src.data_, 0, sizeof(data_)); +inline Cord::InlineRep::InlineRep(Cord::InlineRep&& src) : data_(src.data_) { + src.ResetToEmpty(); } inline Cord::InlineRep& Cord::InlineRep::operator=(const Cord::InlineRep& src) { @@ -892,7 +1108,7 @@ inline Cord::InlineRep& Cord::InlineRep::operator=(const Cord::InlineRep& src) { return *this; } if (!is_tree() && !src.is_tree()) { - cord_internal::SmallMemmove(data_, src.data_, sizeof(data_)); + data_ = src.data_; return *this; } AssignSlow(src); @@ -902,10 +1118,10 @@ inline Cord::InlineRep& Cord::InlineRep::operator=(const Cord::InlineRep& src) { inline Cord::InlineRep& Cord::InlineRep::operator=( Cord::InlineRep&& src) noexcept { if (is_tree()) { - ClearSlow(); + UnrefTree(); } - memcpy(data_, src.data_, sizeof(data_)); - memset(src.data_, 0, sizeof(data_)); + data_ = src.data_; + src.ResetToEmpty(); return *this; } @@ -913,82 +1129,147 @@ inline void Cord::InlineRep::Swap(Cord::InlineRep* rhs) { if (rhs == this) { return; } - - Cord::InlineRep tmp; - cord_internal::SmallMemmove(tmp.data_, data_, sizeof(data_)); - cord_internal::SmallMemmove(data_, rhs->data_, sizeof(data_)); - cord_internal::SmallMemmove(rhs->data_, tmp.data_, sizeof(data_)); + std::swap(data_, rhs->data_); } inline const char* Cord::InlineRep::data() const { - return is_tree() ? nullptr : data_; + return is_tree() ? nullptr : data_.as_chars(); +} + +inline const char* Cord::InlineRep::as_chars() const { + assert(!data_.is_tree()); + return data_.as_chars(); +} + +inline absl::cord_internal::CordRep* Cord::InlineRep::as_tree() const { + assert(data_.is_tree()); + return data_.as_tree(); } inline absl::cord_internal::CordRep* Cord::InlineRep::tree() const { if (is_tree()) { - absl::cord_internal::CordRep* rep; - memcpy(&rep, data_, sizeof(rep)); - return rep; + return as_tree(); } else { return nullptr; } } -inline bool Cord::InlineRep::empty() const { return data_[kMaxInline] == 0; } +inline bool Cord::InlineRep::empty() const { return data_.is_empty(); } inline size_t Cord::InlineRep::size() const { - const char tag = data_[kMaxInline]; - if (tag <= kMaxInline) return tag; - return static_cast<size_t>(tree()->length); + return is_tree() ? as_tree()->length : inline_size(); } -inline void Cord::InlineRep::set_tree(absl::cord_internal::CordRep* rep) { - if (rep == nullptr) { - memset(data_, 0, sizeof(data_)); +inline cord_internal::CordRepFlat* Cord::InlineRep::MakeFlatWithExtraCapacity( + size_t extra) { + static_assert(cord_internal::kMinFlatLength >= sizeof(data_), ""); + size_t len = data_.inline_size(); + auto* result = CordRepFlat::New(len + extra); + result->length = len; + data_.copy_max_inline_to(result->Data()); + return result; +} + +inline void Cord::InlineRep::EmplaceTree(CordRep* rep, + MethodIdentifier method) { + assert(rep); + data_.make_tree(rep); + CordzInfo::MaybeTrackCord(data_, method); +} + +inline void Cord::InlineRep::EmplaceTree(CordRep* rep, const InlineData& parent, + MethodIdentifier method) { + data_.make_tree(rep); + CordzInfo::MaybeTrackCord(data_, parent, method); +} + +inline void Cord::InlineRep::SetTree(CordRep* rep, + const CordzUpdateScope& scope) { + assert(rep); + assert(data_.is_tree()); + data_.set_tree(rep); + scope.SetCordRep(rep); +} + +inline void Cord::InlineRep::SetTreeOrEmpty(CordRep* rep, + const CordzUpdateScope& scope) { + assert(data_.is_tree()); + if (rep) { + data_.set_tree(rep); } else { - bool was_tree = is_tree(); - memcpy(data_, &rep, sizeof(rep)); - memset(data_ + sizeof(rep), 0, sizeof(data_) - sizeof(rep) - 1); - if (!was_tree) { - data_[kMaxInline] = kTreeFlag; - } + data_ = {}; } + scope.SetCordRep(rep); } -inline void Cord::InlineRep::replace_tree(absl::cord_internal::CordRep* rep) { - ABSL_ASSERT(is_tree()); - if (ABSL_PREDICT_FALSE(rep == nullptr)) { - set_tree(rep); - return; +inline void Cord::InlineRep::CommitTree(const CordRep* old_rep, CordRep* rep, + const CordzUpdateScope& scope, + MethodIdentifier method) { + if (old_rep) { + SetTree(rep, scope); + } else { + EmplaceTree(rep, method); } - memcpy(data_, &rep, sizeof(rep)); - memset(data_ + sizeof(rep), 0, sizeof(data_) - sizeof(rep) - 1); } inline absl::cord_internal::CordRep* Cord::InlineRep::clear() { - const char tag = data_[kMaxInline]; - absl::cord_internal::CordRep* result = nullptr; - if (tag > kMaxInline) { - memcpy(&result, data_, sizeof(result)); + if (is_tree()) { + CordzInfo::MaybeUntrackCord(cordz_info()); } - memset(data_, 0, sizeof(data_)); // Clear the cord + absl::cord_internal::CordRep* result = tree(); + ResetToEmpty(); return result; } inline void Cord::InlineRep::CopyToArray(char* dst) const { assert(!is_tree()); - size_t n = data_[kMaxInline]; + size_t n = inline_size(); assert(n != 0); - cord_internal::SmallMemmove(dst, data_, n); + cord_internal::SmallMemmove(dst, data_.as_chars(), n); +} + +inline void Cord::InlineRep::MaybeRemoveEmptyCrcNode() { + CordRep* rep = tree(); + if (rep == nullptr || ABSL_PREDICT_TRUE(rep->length > 0)) { + return; + } + assert(rep->IsCrc()); + assert(rep->crc()->child == nullptr); + CordzInfo::MaybeUntrackCord(cordz_info()); + CordRep::Unref(rep); + ResetToEmpty(); } constexpr inline Cord::Cord() noexcept {} +inline Cord::Cord(absl::string_view src) + : Cord(src, CordzUpdateTracker::kConstructorString) {} + +template <typename T> +constexpr Cord::Cord(strings_internal::StringConstant<T>) + : contents_(strings_internal::StringConstant<T>::value, + strings_internal::StringConstant<T>::value.size() <= + cord_internal::kMaxInline + ? nullptr + : &cord_internal::ConstInitExternalStorage< + strings_internal::StringConstant<T>>::value) {} + inline Cord& Cord::operator=(const Cord& x) { contents_ = x.contents_; return *this; } +template <typename T, Cord::EnableIfString<T>> +Cord& Cord::operator=(T&& src) { + if (src.size() <= cord_internal::kMaxBytesToCopy) { + return operator=(absl::string_view(src)); + } else { + return AssignLargeString(std::forward<T>(src)); + } +} + +inline Cord::Cord(const Cord& src) : contents_(src.contents_) {} + inline Cord::Cord(Cord&& src) noexcept : contents_(std::move(src.contents_)) {} inline void Cord::swap(Cord& other) noexcept { @@ -1001,19 +1282,29 @@ inline Cord& Cord::operator=(Cord&& x) noexcept { } extern template Cord::Cord(std::string&& src); -extern template Cord& Cord::operator=(std::string&& src); inline size_t Cord::size() const { // Length is 1st field in str.rep_ return contents_.size(); } -inline bool Cord::empty() const { return contents_.empty(); } +inline bool Cord::empty() const { return size() == 0; } -inline size_t Cord::EstimatedMemoryUsage() const { +inline size_t Cord::EstimatedMemoryUsage( + CordMemoryAccounting accounting_method) const { size_t result = sizeof(Cord); if (const absl::cord_internal::CordRep* rep = contents_.tree()) { - result += MemoryUsageAux(rep); + switch (accounting_method) { + case CordMemoryAccounting::kFairShare: + result += cord_internal::GetEstimatedFairShareMemoryUsage(rep); + break; + case CordMemoryAccounting::kTotalMorePrecise: + result += cord_internal::GetMorePreciseMemoryUsage(rep); + break; + case CordMemoryAccounting::kTotal: + result += cord_internal::GetEstimatedMemoryUsage(rep); + break; + } } return result; } @@ -1044,7 +1335,46 @@ inline absl::string_view Cord::Flatten() { } inline void Cord::Append(absl::string_view src) { - contents_.AppendArray(src.data(), src.size()); + contents_.AppendArray(src, CordzUpdateTracker::kAppendString); +} + +inline void Cord::Prepend(absl::string_view src) { + PrependArray(src, CordzUpdateTracker::kPrependString); +} + +inline void Cord::Append(CordBuffer buffer) { + if (ABSL_PREDICT_FALSE(buffer.length() == 0)) return; + absl::string_view short_value; + if (CordRep* rep = buffer.ConsumeValue(short_value)) { + contents_.AppendTree(rep, CordzUpdateTracker::kAppendCordBuffer); + } else { + AppendPrecise(short_value, CordzUpdateTracker::kAppendCordBuffer); + } +} + +inline void Cord::Prepend(CordBuffer buffer) { + if (ABSL_PREDICT_FALSE(buffer.length() == 0)) return; + absl::string_view short_value; + if (CordRep* rep = buffer.ConsumeValue(short_value)) { + contents_.PrependTree(rep, CordzUpdateTracker::kPrependCordBuffer); + } else { + PrependPrecise(short_value, CordzUpdateTracker::kPrependCordBuffer); + } +} + +inline CordBuffer Cord::GetAppendBuffer(size_t capacity, size_t min_capacity) { + if (empty()) return CordBuffer::CreateWithDefaultLimit(capacity); + return GetAppendBufferSlowPath(0, capacity, min_capacity); +} + +inline CordBuffer Cord::GetCustomAppendBuffer(size_t block_size, + size_t capacity, + size_t min_capacity) { + if (empty()) { + return block_size ? CordBuffer::CreateWithCustomLimit(block_size, capacity) + : CordBuffer::CreateWithDefaultLimit(capacity); + } + return GetAppendBufferSlowPath(block_size, capacity, min_capacity); } extern template void Cord::Append(std::string&& src); @@ -1052,7 +1382,7 @@ extern template void Cord::Prepend(std::string&& src); inline int Cord::Compare(const Cord& rhs) const { if (!contents_.is_tree() && !rhs.contents_.is_tree()) { - return contents_.BitwiseCompare(rhs.contents_); + return contents_.data_.Compare(rhs.contents_.data_); } return CompareImpl(rhs); @@ -1072,17 +1402,71 @@ inline bool Cord::StartsWith(absl::string_view rhs) const { return EqualsImpl(rhs, rhs_size); } -inline Cord::ChunkIterator::ChunkIterator(const Cord* cord) - : bytes_remaining_(cord->size()) { - if (cord->empty()) return; - if (cord->contents_.is_tree()) { - stack_of_right_children_.push_back(cord->contents_.tree()); - operator++(); +inline void Cord::ChunkIterator::InitTree(cord_internal::CordRep* tree) { + tree = cord_internal::SkipCrcNode(tree); + if (tree->tag == cord_internal::BTREE) { + current_chunk_ = btree_reader_.Init(tree->btree()); + } else { + current_leaf_ = tree; + current_chunk_ = cord_internal::EdgeData(tree); + } +} + +inline Cord::ChunkIterator::ChunkIterator(cord_internal::CordRep* tree) { + bytes_remaining_ = tree->length; + InitTree(tree); +} + +inline Cord::ChunkIterator::ChunkIterator(const Cord* cord) { + if (CordRep* tree = cord->contents_.tree()) { + bytes_remaining_ = tree->length; + if (ABSL_PREDICT_TRUE(bytes_remaining_ != 0)) { + InitTree(tree); + } else { + current_chunk_ = {}; + } + } else { + bytes_remaining_ = cord->contents_.inline_size(); + current_chunk_ = {cord->contents_.data(), bytes_remaining_}; + } +} + +inline Cord::ChunkIterator& Cord::ChunkIterator::AdvanceBtree() { + current_chunk_ = btree_reader_.Next(); + return *this; +} + +inline void Cord::ChunkIterator::AdvanceBytesBtree(size_t n) { + assert(n >= current_chunk_.size()); + bytes_remaining_ -= n; + if (bytes_remaining_) { + if (n == current_chunk_.size()) { + current_chunk_ = btree_reader_.Next(); + } else { + size_t offset = btree_reader_.length() - bytes_remaining_; + current_chunk_ = btree_reader_.Seek(offset); + } } else { - current_chunk_ = absl::string_view(cord->contents_.data(), cord->size()); + current_chunk_ = {}; } } +inline Cord::ChunkIterator& Cord::ChunkIterator::operator++() { + ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 && + "Attempted to iterate past `end()`"); + assert(bytes_remaining_ >= current_chunk_.size()); + bytes_remaining_ -= current_chunk_.size(); + if (bytes_remaining_ > 0) { + if (btree_reader_) { + return AdvanceBtree(); + } else { + assert(!current_chunk_.empty()); // Called on invalid iterator. + } + current_chunk_ = {}; + } + return *this; +} + inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) { ChunkIterator tmp(*this); operator++(); @@ -1114,10 +1498,15 @@ inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) { } inline void Cord::ChunkIterator::AdvanceBytes(size_t n) { + assert(bytes_remaining_ >= n); if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) { RemoveChunkPrefix(n); } else if (n != 0) { - AdvanceBytesSlowPath(n); + if (btree_reader_) { + AdvanceBytesBtree(n); + } else { + bytes_remaining_ = 0; + } } } @@ -1204,11 +1593,11 @@ inline void Cord::ForEachChunk( if (rep == nullptr) { callback(absl::string_view(contents_.data(), contents_.size())); } else { - return ForEachChunkAux(rep, callback); + ForEachChunkAux(rep, callback); } } -// Nonmember Cord-to-Cord relational operarators. +// Nonmember Cord-to-Cord relational operators. inline bool operator==(const Cord& lhs, const Cord& rhs) { if (lhs.contents_.IsSame(rhs.contents_)) return true; size_t rhs_size = rhs.size(); @@ -1217,12 +1606,8 @@ inline bool operator==(const Cord& lhs, const Cord& rhs) { } inline bool operator!=(const Cord& x, const Cord& y) { return !(x == y); } -inline bool operator<(const Cord& x, const Cord& y) { - return x.Compare(y) < 0; -} -inline bool operator>(const Cord& x, const Cord& y) { - return x.Compare(y) > 0; -} +inline bool operator<(const Cord& x, const Cord& y) { return x.Compare(y) < 0; } +inline bool operator>(const Cord& x, const Cord& y) { return x.Compare(y) > 0; } inline bool operator<=(const Cord& x, const Cord& y) { return x.Compare(y) <= 0; } @@ -1263,7 +1648,6 @@ class CordTestAccess { public: static size_t FlatOverhead(); static size_t MaxFlatLength(); - static size_t SizeofCordRepConcat(); static size_t SizeofCordRepExternal(); static size_t SizeofCordRepSubstring(); static size_t FlatTagToLength(uint8_t tag); |