diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/strings/cord.h')
| -rw-r--r-- | third_party/abseil-cpp/absl/strings/cord.h | 990 |
1 files changed, 695 insertions, 295 deletions
diff --git a/third_party/abseil-cpp/absl/strings/cord.h b/third_party/abseil-cpp/absl/strings/cord.h index 40566cbaa0..f0a1991471 100644 --- a/third_party/abseil-cpp/absl/strings/cord.h +++ b/third_party/abseil-cpp/absl/strings/cord.h @@ -11,25 +11,52 @@ // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. - -// A Cord is a sequence of characters with some unusual access propreties. -// A Cord supports efficient insertions and deletions at the start and end of -// the byte sequence, but random access reads are slower, and random access -// modifications are not supported by the API. Cord also provides cheap copies -// (using a copy-on-write strategy) and cheap substring operations. // -// Thread safety -// ------------- +// ----------------------------------------------------------------------------- +// File: cord.h +// ----------------------------------------------------------------------------- +// +// This file defines the `absl::Cord` data structure and operations on that data +// 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.) +// +// 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 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. +// +// A Cord provides some benefit over `std::string` under the following (albeit +// narrow) circumstances: +// +// * Cord data is designed to grow and shrink over a Cord's lifetime. Cord +// provides efficient insertions and deletions at the start and end of the +// character sequences, avoiding copies in those cases. Static data should +// generally be stored as strings. +// * External memory consisting of string-like data can be directly added to +// a Cord without requiring copies or allocations. +// * Cord data may be shared and copied cheaply. Cord provides a copy-on-write +// implementation and cheap sub-Cord operations. Copying a Cord is an O(1) +// operation. +// +// As a consequence to the above, Cord data is generally large. Small data +// should generally use strings, as construction of a Cord requires some +// overhead. Small Cords (<= 15 bytes) are represented inline, but most small +// Cords are expected to grow over their lifetimes. +// +// Note that because a Cord is made up of separate chunked data, random access +// to character data within a Cord is slower than within a `std::string`. +// +// Thread Safety +// // Cord has the same thread-safety properties as many other types like // std::string, std::vector<>, int, etc -- it is thread-compatible. In -// particular, if no thread may call a non-const method, then it is safe to -// concurrently call const methods. Copying a Cord produces a new instance that -// can be used concurrently with the original in arbitrary ways. -// -// Implementation is similar to the "Ropes" described in: -// Ropes: An alternative to strings -// Hans J. Boehm, Russ Atkinson, Michael Plass -// Software Practice and Experience, December 1995 +// particular, if threads do not call non-const methods, then it is safe to call +// const methods without synchronization. Copying a Cord produces a new instance +// that can be used concurrently with the original in arbitrary ways. #ifndef ABSL_STRINGS_CORD_H_ #define ABSL_STRINGS_CORD_H_ @@ -38,12 +65,13 @@ #include <cstddef> #include <cstdint> #include <cstring> -#include <iostream> +#include <iosfwd> #include <iterator> #include <string> +#include <type_traits> +#include "absl/base/config.h" #include "absl/base/internal/endian.h" -#include "absl/base/internal/invoke.h" #include "absl/base/internal/per_thread_tls.h" #include "absl/base/macros.h" #include "absl/base/port.h" @@ -51,8 +79,18 @@ #include "absl/functional/function_ref.h" #include "absl/meta/type_traits.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_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" namespace absl { ABSL_NAMESPACE_BEGIN @@ -61,12 +99,35 @@ class CordTestPeer; template <typename Releaser> Cord MakeCordFromExternal(absl::string_view, Releaser&&); void CopyCordToString(const Cord& src, std::string* dst); -namespace hash_internal { -template <typename H> -H HashFragmentedCord(H, const Cord&); -} -// A Cord is a sequence of characters. +// Cord +// +// A Cord is a sequence of characters, designed to be more efficient than a +// `std::string` in certain circumstances: namely, large string data that needs +// to change over its lifetime or shared, especially when such data is shared +// across API boundaries. +// +// A Cord stores its character data in a structure that allows efficient prepend +// and append operations. This makes a Cord useful for large string data sent +// over in a wire format that may need to be prepended or appended at some point +// during the data exchange (e.g. HTTP, protocol buffers). For example, a +// Cord is useful for storing an HTTP request, and prepending an HTTP header to +// such a request. +// +// Cords should not be used for storing general string data, however. They +// require overhead to construct and are slower than strings for random access. +// +// The Cord API provides the following common API operations: +// +// * Create or assign Cords out of existing string data, memory, or other Cords +// * Append and prepend data to an existing Cord +// * Create new Sub-Cords from existing Cord data +// * Swap Cord data and compare Cord equality +// * Write out Cord data by constructing a `std::string` +// +// Additionally, the API provides iterator utilities to iterate through Cord +// data via chunks or character bytes. +// class Cord { private: template <typename T> @@ -74,51 +135,53 @@ class Cord { absl::enable_if_t<std::is_same<T, std::string>::value, int>; public: - // -------------------------------------------------------------------- - // Constructors, destructors and helper factories + // Cord::Cord() Constructors. - // Create an empty cord + // Creates an empty Cord. constexpr Cord() noexcept; - // Cord is copyable and efficiently movable. - // The moved-from state is valid but unspecified. + // Creates a Cord from an existing Cord. Cord is copyable and efficiently + // movable. The moved-from state is valid but unspecified. Cord(const Cord& src); Cord(Cord&& src) noexcept; Cord& operator=(const Cord& x); Cord& operator=(Cord&& x) noexcept; - // Create a cord out of "src". This constructor is explicit on - // purpose so that people do not get automatic type conversions. + // Creates a Cord from a `src` string. This constructor is marked explicit to + // prevent implicit Cord constructions from arguments convertible to an + // `absl::string_view`. explicit Cord(absl::string_view src); Cord& operator=(absl::string_view src); - // These are templated to avoid ambiguities for types that are convertible to - // both `absl::string_view` and `std::string`, such as `const char*`. - // - // Note that these functions reserve the right to reuse the `string&&`'s - // memory and that they will do so in the future. + // Creates a Cord from a `std::string&&` rvalue. These constructors are + // templated to avoid ambiguities for types that are convertible to both + // `absl::string_view` and `std::string`, such as `const char*`. template <typename T, EnableIfString<T> = 0> - explicit Cord(T&& src) : Cord(absl::string_view(src)) {} + explicit Cord(T&& src); template <typename T, EnableIfString<T> = 0> Cord& operator=(T&& src); - // Destroy the cord + // Cord::~Cord() + // + // Destructs the Cord. ~Cord() { if (contents_.is_tree()) DestroyCordSlow(); } - // Creates a Cord that takes ownership of external memory. The contents of - // `data` are not copied. + // MakeCordFromExternal() + // + // Creates a Cord that takes ownership of external string memory. The + // contents of `data` are not copied to the Cord; instead, the external + // memory is added to the Cord and reference-counted. This data may not be + // changed for the life of the Cord, though it may be prepended or appended + // to. // - // This function takes a callable that is invoked when all Cords are - // finished with `data`. The data must remain live and unchanging until the - // releaser is called. The requirements for the releaser are that it: - // * is move constructible, - // * supports `void operator()(absl::string_view) const`, - // * does not have alignment requirement greater than what is guaranteed by - // ::operator new. This is dictated by alignof(std::max_align_t) before - // C++17 and __STDCPP_DEFAULT_NEW_ALIGNMENT__ if compiling with C++17 or - // it is supported by the implementation. + // `MakeCordFromExternal()` takes a callable "releaser" that is invoked when + // the reference count for `data` reaches zero. As noted above, this data must + // remain live until the releaser is invoked. The callable releaser also must: + // + // * be move constructible + // * support `void operator()(absl::string_view) const` or `void operator()` // // Example: // @@ -127,13 +190,13 @@ class Cord { // FillBlock(block); // return absl::MakeCordFromExternal( // block->ToStringView(), - // [pool, block](absl::string_view /*ignored*/) { - // pool->FreeBlock(block); + // [pool, block](absl::string_view v) { + // pool->FreeBlock(block, v); // }); // } // - // WARNING: It's likely a bug if your releaser doesn't do anything. - // For example, consider the following: + // WARNING: Because a Cord can be reference-counted, it's likely a bug if your + // releaser doesn't do anything. For example, consider the following: // // void Foo(const char* buffer, int len) { // auto c = absl::MakeCordFromExternal(absl::string_view(buffer, len), @@ -147,97 +210,141 @@ class Cord { template <typename Releaser> friend Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser); - // -------------------------------------------------------------------- - // Mutations - + // Cord::Clear() + // + // Releases the Cord data. Any nodes that share data with other Cords, if + // applicable, will have their reference counts reduced by 1. void Clear(); + // Cord::Append() + // + // Appends data to the Cord, which may come from another Cord or other string + // data. void Append(const Cord& src); void Append(Cord&& src); void Append(absl::string_view src); template <typename T, EnableIfString<T> = 0> void Append(T&& src); + // Cord::Prepend() + // + // Prepends data to the Cord, which may come from another Cord or other string + // data. void Prepend(const Cord& src); void Prepend(absl::string_view src); template <typename T, EnableIfString<T> = 0> void Prepend(T&& src); + // Cord::RemovePrefix() + // + // Removes the first `n` bytes of a Cord. void RemovePrefix(size_t n); void RemoveSuffix(size_t n); - // Returns a new cord representing the subrange [pos, pos + new_size) of + // Cord::Subcord() + // + // Returns a new Cord representing the subrange [pos, pos + new_size) of // *this. If pos >= size(), the result is empty(). If // (pos + new_size) >= size(), the result is the subrange [pos, size()). Cord Subcord(size_t pos, size_t new_size) const; - friend void swap(Cord& x, Cord& y) noexcept; + // Cord::swap() + // + // Swaps the contents of the Cord with `other`. + void swap(Cord& other) noexcept; - // -------------------------------------------------------------------- - // Accessors + // swap() + // + // Swaps the contents of two Cords. + friend void swap(Cord& x, Cord& y) noexcept { x.swap(y); } + // Cord::size() + // + // Returns the size of the Cord. size_t size() const; + + // Cord::empty() + // + // Determines whether the given Cord is empty, returning `true` is so. bool empty() const; - // Returns the approximate number of bytes pinned by this Cord. Note that - // Cords that share memory could each be "charged" independently for the same - // shared memory. + // 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; - // -------------------------------------------------------------------- - // Comparators - - // Compares 'this' Cord with rhs. This function and its relatives - // treat Cords as sequences of unsigned bytes. The comparison is a - // straightforward lexicographic comparison. Return value: + // Cord::Compare() + // + // Compares 'this' Cord with rhs. This function and its relatives treat Cords + // as sequences of unsigned bytes. The comparison is a straightforward + // lexicographic comparison. `Cord::Compare()` returns values as follows: + // // -1 'this' Cord is smaller // 0 two Cords are equal // 1 'this' Cord is larger int Compare(absl::string_view rhs) const; int Compare(const Cord& rhs) const; - // Does 'this' cord start/end with rhs + // Cord::StartsWith() + // + // Determines whether the Cord starts with the passed string data `rhs`. bool StartsWith(const Cord& rhs) const; bool StartsWith(absl::string_view rhs) const; + + // Cord::EndsWith() + // + // Determines whether the Cord ends with the passed string data `rhs`. bool EndsWith(absl::string_view rhs) const; bool EndsWith(const Cord& rhs) const; - // -------------------------------------------------------------------- - // Conversion to other types - + // Cord::operator std::string() + // + // Converts a Cord into a `std::string()`. This operator is marked explicit to + // prevent unintended Cord usage in functions that take a string. explicit operator std::string() const; - // Copies the contents from `src` to `*dst`. + // CopyCordToString() // - // This function optimizes the case of reusing the destination std::string since it + // Copies the contents of a `src` Cord into a `*dst` string. + // + // This function optimizes the case of reusing the destination string since it // can reuse previously allocated capacity. However, this function does not // guarantee that pointers previously returned by `dst->data()` remain valid // even if `*dst` had enough capacity to hold `src`. If `*dst` is a new // object, prefer to simply use the conversion operator to `std::string`. friend void CopyCordToString(const Cord& src, std::string* dst); - // -------------------------------------------------------------------- - // Iteration - class CharIterator; - // Type for iterating over the chunks of a `Cord`. See comments for - // `Cord::chunk_begin()`, `Cord::chunk_end()` and `Cord::Chunks()` below for - // preferred usage. + //---------------------------------------------------------------------------- + // Cord::ChunkIterator + //---------------------------------------------------------------------------- + // + // A `Cord::ChunkIterator` allows iteration over the constituent chunks of its + // Cord. Such iteration allows you to perform non-const operatons on the data + // of a Cord without modifying it. + // + // Generally, you do not instantiate a `Cord::ChunkIterator` directly; + // instead, you create one implicitly through use of the `Cord::Chunks()` + // member function. + // + // The `Cord::ChunkIterator` has the following properties: // - // Additional notes: + // * The iterator is invalidated after any non-const operation on the + // Cord object over which it iterates. // * The `string_view` returned by dereferencing a valid, non-`end()` // iterator is guaranteed to be non-empty. - // * A `ChunkIterator` object is invalidated after any non-const - // operation on the `Cord` object over which it iterates. - // * Two `ChunkIterator` objects can be equality compared if and only if - // they remain valid and iterate over the same `Cord`. - // * This is a proxy iterator. This means the `string_view` returned by the - // iterator does not live inside the Cord, and its lifetime is limited to - // the lifetime of the iterator itself. To help prevent issues, - // `ChunkIterator::reference` is not a true reference type and is - // equivalent to `value_type`. - // * The iterator keeps state that can grow for `Cord`s that contain many + // * Two `ChunkIterator` objects can be compared equal if and only if they + // remain valid and iterate over the same Cord. + // * The iterator in this case is a proxy iterator; the `string_view` + // returned by the iterator does not live inside the Cord, and its + // lifetime is limited to the lifetime of the iterator itself. To help + // prevent lifetime issues, `ChunkIterator::reference` is not a true + // reference type and is equivalent to `value_type`. + // * The iterator keeps state that can grow for Cords that contain many // nodes and are imbalanced due to sharing. Prefer to pass this type by // const reference instead of by value. class ChunkIterator { @@ -261,14 +368,38 @@ class Cord { friend class CharIterator; private: + using CordRep = absl::cord_internal::CordRep; + using CordRepBtree = absl::cord_internal::CordRepBtree; + using CordRepBtreeReader = absl::cord_internal::CordRepBtreeReader; + + // Stack of right children of concat nodes that we have to visit. + // Keep this at the end of the structure to avoid cache-thrashing. + // TODO(jgm): Benchmark to see if there's a more optimal value than 47 for + // the inlined vector size (47 exists for backward compatibility). + using Stack = absl::InlinedVector<absl::cord_internal::CordRep*, 47>; + + // 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); + + // Stack specific operator++ + ChunkIterator& AdvanceStack(); + + // Btree specific operator++ + ChunkIterator& AdvanceBtree(); + void AdvanceBytesBtree(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); @@ -282,14 +413,21 @@ 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_; + + // See 'Stack' alias definition. + Stack stack_of_right_children_; }; + // Cord::ChunkIterator::chunk_begin() + // // Returns an iterator to the first chunk of the `Cord`. // - // This is useful for getting a `ChunkIterator` outside the context of a - // range-based for-loop (in which case see `Cord::Chunks()` below). + // Generally, prefer using `Cord::Chunks()` within a range-based for loop for + // iterating over the chunks of a Cord. This method may be useful for getting + // a `ChunkIterator` where range-based for-loops are not useful. // // Example: // @@ -298,15 +436,40 @@ class Cord { // return std::find(c.chunk_begin(), c.chunk_end(), s); // } ChunkIterator chunk_begin() const; + + // Cord::ChunkItertator::chunk_end() + // // Returns an iterator one increment past the last chunk of the `Cord`. + // + // Generally, prefer using `Cord::Chunks()` within a range-based for loop for + // iterating over the chunks of a Cord. This method may be useful for getting + // a `ChunkIterator` where range-based for-loops may not be available. ChunkIterator chunk_end() const; - // Convenience wrapper over `Cord::chunk_begin()` and `Cord::chunk_end()` to - // enable range-based for-loop iteration over `Cord` chunks. + //---------------------------------------------------------------------------- + // Cord::ChunkIterator::ChunkRange + //---------------------------------------------------------------------------- + // + // `ChunkRange` is a helper class for iterating over the chunks of the `Cord`, + // producing an iterator which can be used within a range-based for loop. + // Construction of a `ChunkRange` will return an iterator pointing to the + // first chunk of the Cord. Generally, do not construct a `ChunkRange` + // directly; instead, prefer to use the `Cord::Chunks()` method. // - // Prefer to use `Cord::Chunks()` below instead of constructing this directly. + // Implementation note: `ChunkRange` is simply a convenience wrapper over + // `Cord::chunk_begin()` and `Cord::chunk_end()`. class ChunkRange { public: + // Fulfill minimum c++ container requirements [container.requirements] + // Theses (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; @@ -316,8 +479,11 @@ class Cord { const Cord* cord_; }; - // Returns a range for iterating over the chunks of a `Cord` with a - // range-based for-loop. + // 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. // // Example: // @@ -334,22 +500,30 @@ class Cord { // } ChunkRange Chunks() const; - // Type for iterating over the characters of a `Cord`. See comments for - // `Cord::char_begin()`, `Cord::char_end()` and `Cord::Chars()` below for - // preferred usage. + //---------------------------------------------------------------------------- + // Cord::CharIterator + //---------------------------------------------------------------------------- + // + // A `Cord::CharIterator` allows iteration over the constituent characters of + // a `Cord`. // - // Additional notes: - // * A `CharIterator` object is invalidated after any non-const - // operation on the `Cord` object over which it iterates. - // * Two `CharIterator` objects can be equality compared if and only if - // they remain valid and iterate over the same `Cord`. - // * The iterator keeps state that can grow for `Cord`s that contain many + // Generally, you do not instantiate a `Cord::CharIterator` directly; instead, + // you create one implicitly through use of the `Cord::Chars()` member + // function. + // + // A `Cord::CharIterator` has the following properties: + // + // * The iterator is invalidated after any non-const operation on the + // Cord object over which it iterates. + // * Two `CharIterator` objects can be compared equal if and only if they + // remain valid and iterate over the same Cord. + // * The iterator keeps state that can grow for Cords that contain many // nodes and are imbalanced due to sharing. Prefer to pass this type by // const reference instead of by value. - // * This type cannot be a forward iterator because a `Cord` can reuse - // sections of memory. This violates the requirement that if dereferencing - // two iterators returns the same object, the iterators must compare - // equal. + // * This type cannot act as a forward iterator because a `Cord` can reuse + // sections of memory. This fact violates the requirement for forward + // iterators to compare equal if dereferencing them returns the same + // object. class CharIterator { public: using iterator_category = std::input_iterator_tag; @@ -375,36 +549,68 @@ class Cord { ChunkIterator chunk_iterator_; }; - // Advances `*it` by `n_bytes` and returns the bytes passed as a `Cord`. + // Cord::CharIterator::AdvanceAndRead() // - // `n_bytes` must be less than or equal to the number of bytes remaining for - // iteration. Otherwise the behavior is undefined. It is valid to pass - // `char_end()` and 0. + // 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 + // number of bytes within the Cord; otherwise, behavior is undefined. It is + // valid to pass `char_end()` and `0`. static Cord AdvanceAndRead(CharIterator* it, size_t n_bytes); - // Advances `*it` by `n_bytes`. + // Cord::CharIterator::Advance() // - // `n_bytes` must be less than or equal to the number of bytes remaining for - // iteration. Otherwise the behavior is undefined. It is valid to pass - // `char_end()` and 0. + // 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() + // // 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() + // // Returns an iterator to the first character of the `Cord`. + // + // Generally, prefer using `Cord::Chars()` within a range-based for loop for + // iterating over the chunks of a Cord. This method may be useful for getting + // a `CharIterator` where range-based for-loops may not be available. CharIterator char_begin() const; + + // Cord::CharIterator::char_end() + // // Returns an iterator to one past the last character of the `Cord`. + // + // Generally, prefer using `Cord::Chars()` within a range-based for loop for + // iterating over the chunks of a Cord. This method may be useful for getting + // a `CharIterator` where range-based for-loops are not useful. CharIterator char_end() const; - // Convenience wrapper over `Cord::char_begin()` and `Cord::char_end()` to - // enable range-based for-loop iterator over the characters of a `Cord`. + // Cord::CharIterator::CharRange // - // Prefer to use `Cord::Chars()` below instead of constructing this directly. + // `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. + // + // 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] + // Theses (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; @@ -414,8 +620,11 @@ class Cord { const Cord* cord_; }; - // Returns a range for iterating over the characters of a `Cord` with a - // range-based for-loop. + // Cord::CharIterator::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. // // Example: // @@ -432,32 +641,73 @@ class Cord { // } CharRange Chars() const; - // -------------------------------------------------------------------- - // Miscellaneous - - // Get the "i"th character of 'this' and return it. - // NOTE: This routine is reasonably efficient. It is roughly - // logarithmic in the number of nodes that make up the cord. Still, - // if you need to iterate over the contents of a cord, you should - // use a CharIterator/CordIterator rather than call operator[] or Get() - // repeatedly in a loop. + // Cord::operator[] // - // REQUIRES: 0 <= i < size() + // Gets the "i"th character of the Cord and returns it, provided that + // 0 <= i < Cord.size(). + // + // NOTE: This routine is reasonably efficient. It is roughly + // logarithmic based on the number of chunks that make up the cord. Still, + // if you need to iterate over the contents of a cord, you should + // use a CharIterator/ChunkIterator rather than call operator[] or Get() + // repeatedly in a loop. char operator[](size_t i) const; + // Cord::TryFlat() + // + // If this cord's representation is a single flat array, returns a + // string_view referencing that array. Otherwise returns nullopt. + absl::optional<absl::string_view> TryFlat() const; + + // Cord::Flatten() + // // Flattens the cord into a single array and returns a view of the data. // // If the cord was already flat, the contents are not modified. absl::string_view Flatten(); + // Supports absl::Cord as a sink object for absl::Format(). + friend void AbslFormatFlush(absl::Cord* cord, absl::string_view part) { + cord->Append(part); + } + + template <typename H> + friend H AbslHashValue(H hash_state, const absl::Cord& c) { + absl::optional<absl::string_view> maybe_flat = c.TryFlat(); + if (maybe_flat.has_value()) { + return H::combine(std::move(hash_state), *maybe_flat); + } + 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> + explicit 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; - template <typename H> - friend H absl::hash_internal::HashFragmentedCord(H, const Cord&); friend bool operator==(const Cord& lhs, const Cord& rhs); friend bool operator==(const Cord& lhs, absl::string_view rhs); - // Call the provided function once for each cord chunk, in order. Unlike + 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; @@ -469,60 +719,92 @@ class Cord { // class so that we can isolate the bulk of cord.cc from changes // to the representation. // - // InlineRep holds either either a tree pointer, or an array of kMaxInline - // bytes. + // InlineRep holds either a tree pointer, or an array of kMaxInline bytes. class InlineRep { public: - static const 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 const unsigned char kTreeFlag = 1 << 4; - // Tag byte & kProfiledFlag means we are profiling the Cord. - static const 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(cord_internal::InlineData data); + 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 + 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; // Returns non-null iff was holding a pointer absl::cord_internal::CordRep* clear(); - // Convert to pointer if necessary - absl::cord_internal::CordRep* force_tree(size_t extra_hint); - void reduce_size(size_t n); // REQUIRES: holding data + // Converts to pointer if necessary. + 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); + + // 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); + + template <bool has_length> + void GetAppendRegion(char** region, size_t* size, size_t length); + bool IsSame(const InlineRep& other) const { - return memcmp(data_, other.data_, sizeof(data_)) == 0; + 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)); + // Use memcpy to avoid 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)); + memcpy(&x, reinterpret_cast<const char*>(&data_) + 8, sizeof(x)); + memcpy(&y, reinterpret_cast<const char*>(&other.data_) + 8, sizeof(y)); if (x == y) return 0; } return absl::big_endian::FromHost64(x) < absl::big_endian::FromHost64(y) @@ -531,43 +813,62 @@ class Cord { } void CopyTo(std::string* dst) const { // memcpy is much faster when operating on a known size. On most supported - // platforms, the small std::string optimization is large enough that resizing + // 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); + memcpy(&(*dst)[0], &data_, sizeof(data_) - 1); // 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 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(); } + + cord_internal::InlineData data_; }; InlineRep contents_; - // Helper for MemoryUsage() + // Helper for MemoryUsage(). static size_t MemoryUsageAux(const absl::cord_internal::CordRep* rep); - // Helper for GetFlat() + // Helper for GetFlat() and TryFlat(). static bool GetFlatAux(absl::cord_internal::CordRep* rep, absl::string_view* fragment); - // Helper for ForEachChunk() + // Helper for ForEachChunk(). static void ForEachChunkAux( absl::cord_internal::CordRep* rep, absl::FunctionRef<void(absl::string_view)> callback); @@ -596,9 +897,28 @@ class Cord { absl::cord_internal::CordRep* TakeRep() const&; absl::cord_internal::CordRep* TakeRep() &&; - // Helper for Append() + // Helper for Append(). template <typename C> void AppendImpl(C&& src); + + // 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 { + typename H::AbslInternalPiecewiseCombiner combiner; + ForEachChunk([&combiner, &hash_state](absl::string_view chunk) { + hash_state = combiner.add_buffer(std::move(hash_state), chunk.data(), + chunk.size()); + }); + return H::combine(combiner.finalize(std::move(hash_state)), size()); + } }; ABSL_NAMESPACE_END @@ -655,52 +975,27 @@ inline void SmallMemmove(char* dst, const char* src, size_t n, } } -struct ExternalRepReleaserPair { - CordRep* rep; - void* releaser_address; -}; - -// Allocates a new external `CordRep` and returns a pointer to it and a pointer -// to `releaser_size` bytes where the desired releaser can be constructed. +// Does non-template-specific `CordRepExternal` initialization. // Expects `data` to be non-empty. -ExternalRepReleaserPair NewExternalWithUninitializedReleaser( - absl::string_view data, ExternalReleaserInvoker invoker, - size_t releaser_size); +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. template <typename Releaser> // NOLINTNEXTLINE - suppress clang-tidy raw pointer return. CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) { - static_assert( -#if defined(__STDCPP_DEFAULT_NEW_ALIGNMENT__) - alignof(Releaser) <= __STDCPP_DEFAULT_NEW_ALIGNMENT__, -#else - alignof(Releaser) <= alignof(max_align_t), -#endif - "Releasers with alignment requirement greater than what is returned by " - "default `::operator new()` are not supported."); - using ReleaserType = absl::decay_t<Releaser>; if (data.empty()) { // Never create empty external nodes. - ::absl::base_internal::Invoke( - ReleaserType(std::forward<Releaser>(releaser)), data); + InvokeReleaser(Rank0{}, ReleaserType(std::forward<Releaser>(releaser)), + data); return nullptr; } - auto releaser_invoker = [](void* type_erased_releaser, absl::string_view d) { - auto* my_releaser = static_cast<ReleaserType*>(type_erased_releaser); - ::absl::base_internal::Invoke(std::move(*my_releaser), d); - my_releaser->~ReleaserType(); - return sizeof(Releaser); - }; - - ExternalRepReleaserPair external = NewExternalWithUninitializedReleaser( - data, releaser_invoker, sizeof(releaser)); - ::new (external.releaser_address) - ReleaserType(std::forward<Releaser>(releaser)); - return external.rep; + CordRepExternal* rep = new CordRepExternalImpl<ReleaserType>( + std::forward<Releaser>(releaser), 0); + InitializeCordRepExternal(data, rep); + return rep; } // Overload for function reference types that dispatches using a function @@ -716,18 +1011,29 @@ 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 (auto* rep = ::absl::cord_internal::NewExternalRep( + data, std::forward<Releaser>(releaser))) { + cord.contents_.EmplaceTree(rep, + Cord::MethodIdentifier::kMakeCordFromExternal); + } return cord; } -inline Cord::InlineRep::InlineRep(const Cord::InlineRep& src) { - cord_internal::SmallMemmove(data_, src.data_, sizeof(data_)); +constexpr Cord::InlineRep::InlineRep(cord_internal::InlineData data) + : data_(data) {} + +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) { @@ -735,7 +1041,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); @@ -745,10 +1051,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; } @@ -756,94 +1062,143 @@ 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 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; + memcpy(result->Data(), data_.as_chars(), sizeof(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); } 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.size() <= + cord_internal::kMaxInline + ? cord_internal::InlineData( + strings_internal::StringConstant<T>::value) + : cord_internal::InlineData( + &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 { + contents_.Swap(&other.contents_); +} + inline Cord& Cord::operator=(Cord&& x) noexcept { contents_ = std::move(x.contents_); return *this; } -template <typename T, Cord::EnableIfString<T>> -inline Cord& Cord::operator=(T&& src) { - *this = absl::string_view(src); - return *this; -} +extern template Cord::Cord(std::string&& src); inline size_t Cord::size() const { // Length is 1st field in str.rep_ @@ -860,6 +1215,18 @@ inline size_t Cord::EstimatedMemoryUsage() const { return result; } +inline absl::optional<absl::string_view> Cord::TryFlat() const { + absl::cord_internal::CordRep* rep = contents_.tree(); + if (rep == nullptr) { + return absl::string_view(contents_.data(), contents_.size()); + } + absl::string_view fragment; + if (GetFlatAux(rep, &fragment)) { + return fragment; + } + return absl::nullopt; +} + inline absl::string_view Cord::Flatten() { absl::cord_internal::CordRep* rep = contents_.tree(); if (rep == nullptr) { @@ -874,22 +1241,15 @@ 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); } -template <typename T, Cord::EnableIfString<T>> -inline void Cord::Append(T&& src) { - // Note that this function reserves the right to reuse the `string&&`'s - // memory and that it will do so in the future. - Append(absl::string_view(src)); +inline void Cord::Prepend(absl::string_view src) { + PrependArray(src, CordzUpdateTracker::kPrependString); } -template <typename T, Cord::EnableIfString<T>> -inline void Cord::Prepend(T&& src) { - // Note that this function reserves the right to reuse the `string&&`'s - // memory and that it will do so in the future. - Prepend(absl::string_view(src)); -} +extern template void Cord::Append(std::string&& src); +extern template void Cord::Prepend(std::string&& src); inline int Cord::Compare(const Cord& rhs) const { if (!contents_.is_tree() && !rhs.contents_.is_tree()) { @@ -913,17 +1273,64 @@ inline bool Cord::StartsWith(absl::string_view rhs) const { return EqualsImpl(rhs, rhs_size); } +inline void Cord::ChunkIterator::InitTree(cord_internal::CordRep* tree) { + if (tree->tag == cord_internal::BTREE) { + current_chunk_ = btree_reader_.Init(tree->btree()); + return; + } + + stack_of_right_children_.push_back(tree); + operator++(); +} + +inline Cord::ChunkIterator::ChunkIterator(cord_internal::CordRep* tree) + : bytes_remaining_(tree->length) { + InitTree(tree); +} + 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++(); + InitTree(cord->contents_.as_tree()); } else { - current_chunk_ = absl::string_view(cord->contents_.data(), cord->size()); + current_chunk_ = + absl::string_view(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_ = {}; + } +} + +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) { + return btree_reader_ ? AdvanceBtree() : AdvanceStack(); + } else { + current_chunk_ = {}; + } + return *this; +} + inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) { ChunkIterator tmp(*this); operator++(); @@ -939,12 +1346,12 @@ inline bool Cord::ChunkIterator::operator!=(const ChunkIterator& other) const { } inline Cord::ChunkIterator::reference Cord::ChunkIterator::operator*() const { - assert(bytes_remaining_ != 0); + ABSL_HARDENING_ASSERT(bytes_remaining_ != 0); return current_chunk_; } inline Cord::ChunkIterator::pointer Cord::ChunkIterator::operator->() const { - assert(bytes_remaining_ != 0); + ABSL_HARDENING_ASSERT(bytes_remaining_ != 0); return ¤t_chunk_; } @@ -955,10 +1362,11 @@ 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); + btree_reader_ ? AdvanceBytesBtree(n) : AdvanceBytesSlowPath(n); } } @@ -1058,12 +1466,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; } @@ -1098,10 +1502,6 @@ inline bool operator<=(absl::string_view x, const Cord& y) { return !(y < x); } inline bool operator>=(const Cord& x, absl::string_view y) { return !(x < y); } inline bool operator>=(absl::string_view x, const Cord& y) { return !(x < y); } -// Overload of swap for Cord. The use of non-const references is -// required. :( -inline void swap(Cord& x, Cord& y) noexcept { y.contents_.Swap(&x.contents_); } - // Some internals exposed to test code. namespace strings_internal { class CordTestAccess { |