// Copyright 2020 The Abseil Authors. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // https://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // 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. #include "absl/strings/cord.h" #include <algorithm> #include <cassert> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <iomanip> #include <ios> #include <iostream> #include <limits> #include <memory> #include <ostream> #include <sstream> #include <string> #include <utility> #include "absl/base/attributes.h" #include "absl/base/config.h" #include "absl/base/internal/endian.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/macros.h" #include "absl/base/optimization.h" #include "absl/base/nullability.h" #include "absl/container/inlined_vector.h" #include "absl/crc/crc32c.h" #include "absl/crc/internal/crc_cord_state.h" #include "absl/functional/function_ref.h" #include "absl/strings/cord_buffer.h" #include "absl/strings/escaping.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_crc.h" #include "absl/strings/internal/cord_rep_flat.h" #include "absl/strings/internal/cordz_update_tracker.h" #include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/match.h" #include "absl/strings/str_cat.h" #include "absl/strings/string_view.h" #include "absl/strings/strip.h" #include "absl/types/optional.h" #include "absl/types/span.h" namespace absl { ABSL_NAMESPACE_BEGIN CordRep; CordRepBtree; CordRepCrc; CordRepExternal; CordRepFlat; CordRepSubstring; CordzUpdateTracker; InlineData; kMaxFlatLength; kMinFlatLength; kInlinedVectorSize; kMaxBytesToCopy; static void DumpNode(absl::Nonnull<CordRep*> nonnull_rep, bool include_data, absl::Nonnull<std::ostream*> os, int indent = 0); static bool VerifyNode(absl::Nonnull<CordRep*> root, absl::Nonnull<CordRep*> start_node); static inline absl::Nullable<CordRep*> VerifyTree( absl::Nullable<CordRep*> node) { … } static absl::Nonnull<CordRepFlat*> CreateFlat(absl::Nonnull<const char*> data, size_t length, size_t alloc_hint) { … } // Creates a new flat or Btree out of the specified array. // The returned node has a refcount of 1. static absl::Nonnull<CordRep*> NewBtree(absl::Nonnull<const char*> data, size_t length, size_t alloc_hint) { … } // Create a new tree out of the specified array. // The returned node has a refcount of 1. static absl::Nullable<CordRep*> NewTree(absl::Nullable<const char*> data, size_t length, size_t alloc_hint) { … } namespace cord_internal { void InitializeCordRepExternal(absl::string_view data, absl::Nonnull<CordRepExternal*> rep) { … } } // namespace cord_internal // Creates a CordRep from the provided string. If the string is large enough, // and not wasteful, we move the string into an external cord rep, preserving // the already allocated string contents. // Requires the provided string length to be larger than `kMaxInline`. static absl::Nonnull<CordRep*> CordRepFromString(std::string&& src) { … } // -------------------------------------------------------------------- // Cord::InlineRep functions #ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL constexpr unsigned char Cord::InlineRep::kMaxInline; #endif inline void Cord::InlineRep::set_data(absl::Nonnull<const char*> data, size_t n) { … } inline absl::Nonnull<char*> Cord::InlineRep::set_data(size_t n) { … } inline void Cord::InlineRep::reduce_size(size_t n) { … } inline void Cord::InlineRep::remove_prefix(size_t n) { … } // Returns `rep` converted into a CordRepBtree. // Directly returns `rep` if `rep` is already a CordRepBtree. static absl::Nonnull<CordRepBtree*> ForceBtree(CordRep* rep) { … } void Cord::InlineRep::AppendTreeToInlined(absl::Nonnull<CordRep*> tree, MethodIdentifier method) { … } void Cord::InlineRep::AppendTreeToTree(absl::Nonnull<CordRep*> tree, MethodIdentifier method) { … } void Cord::InlineRep::AppendTree(absl::Nonnull<CordRep*> tree, MethodIdentifier method) { … } void Cord::InlineRep::PrependTreeToInlined(absl::Nonnull<CordRep*> tree, MethodIdentifier method) { … } void Cord::InlineRep::PrependTreeToTree(absl::Nonnull<CordRep*> tree, MethodIdentifier method) { … } void Cord::InlineRep::PrependTree(absl::Nonnull<CordRep*> tree, MethodIdentifier method) { … } // Searches for a non-full flat node at the rightmost leaf of the tree. If a // suitable leaf is found, the function will update the length field for all // nodes to account for the size increase. The append region address will be // written to region and the actual size increase will be written to size. static inline bool PrepareAppendRegion( absl::Nonnull<CordRep*> root, absl::Nonnull<absl::Nullable<char*>*> region, absl::Nonnull<size_t*> size, size_t max_length) { … } void Cord::InlineRep::AssignSlow(const Cord::InlineRep& src) { … } void Cord::InlineRep::UnrefTree() { … } // -------------------------------------------------------------------- // Constructors and destructors Cord::Cord(absl::string_view src, MethodIdentifier method) : … { … } template <typename T, Cord::EnableIfString<T>> Cord::Cord(T&& src) : contents_(InlineData::kDefaultInit) { … } template Cord::Cord(std::string&& src); // The destruction code is separate so that the compiler can determine // that it does not need to call the destructor on a moved-from Cord. void Cord::DestroyCordSlow() { … } // -------------------------------------------------------------------- // Mutators void Cord::Clear() { … } Cord& Cord::AssignLargeString(std::string&& src) { … } Cord& Cord::operator=(absl::string_view src) { … } // TODO(sanjay): Move to Cord::InlineRep section of file. For now, // we keep it here to make diffs easier. void Cord::InlineRep::AppendArray(absl::string_view src, MethodIdentifier method) { … } inline absl::Nonnull<CordRep*> Cord::TakeRep() const& { … } inline absl::Nonnull<CordRep*> Cord::TakeRep() && { … } template <typename C> inline void Cord::AppendImpl(C&& src) { … } static CordRep::ExtractResult ExtractAppendBuffer(absl::Nonnull<CordRep*> rep, size_t min_capacity) { … } static CordBuffer CreateAppendBuffer(InlineData& data, size_t block_size, size_t capacity) { … } CordBuffer Cord::GetAppendBufferSlowPath(size_t block_size, size_t capacity, size_t min_capacity) { … } void Cord::Append(const Cord& src) { … } void Cord::Append(Cord&& src) { … } template <typename T, Cord::EnableIfString<T>> void Cord::Append(T&& src) { … } template void Cord::Append(std::string&& src); void Cord::Prepend(const Cord& src) { … } void Cord::PrependArray(absl::string_view src, MethodIdentifier method) { … } void Cord::AppendPrecise(absl::string_view src, MethodIdentifier method) { … } void Cord::PrependPrecise(absl::string_view src, MethodIdentifier method) { … } template <typename T, Cord::EnableIfString<T>> inline void Cord::Prepend(T&& src) { … } template void Cord::Prepend(std::string&& src); void Cord::RemovePrefix(size_t n) { … } void Cord::RemoveSuffix(size_t n) { … } Cord Cord::Subcord(size_t pos, size_t new_size) const { … } // -------------------------------------------------------------------- // Comparators namespace { int ClampResult(int memcmp_res) { … } int CompareChunks(absl::Nonnull<absl::string_view*> lhs, absl::Nonnull<absl::string_view*> rhs, absl::Nonnull<size_t*> size_to_compare) { … } // This overload set computes comparison results from memcmp result. This // interface is used inside GenericCompare below. Different implementations // are specialized for int and bool. For int we clamp result to {-1, 0, 1} // set. For bool we just interested in "value == 0". template <typename ResultType> ResultType ComputeCompareResult(int memcmp_res) { … } template <> bool ComputeCompareResult<bool>(int memcmp_res) { … } } // namespace // Helper routine. Locates the first flat or external chunk of the Cord without // initializing the iterator, and returns a string_view referencing the data. inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const { … } void Cord::SetCrcCordState(crc_internal::CrcCordState state) { … } void Cord::SetExpectedChecksum(uint32_t crc) { … } absl::Nullable<const crc_internal::CrcCordState*> Cord::MaybeGetCrcCordState() const { … } absl::optional<uint32_t> Cord::ExpectedChecksum() const { … } inline int Cord::CompareSlowPath(absl::string_view rhs, size_t compared_size, size_t size_to_compare) const { … } inline int Cord::CompareSlowPath(const Cord& rhs, size_t compared_size, size_t size_to_compare) const { … } inline absl::string_view Cord::GetFirstChunk(const Cord& c) { … } inline absl::string_view Cord::GetFirstChunk(absl::string_view sv) { … } // Compares up to 'size_to_compare' bytes of 'lhs' with 'rhs'. It is assumed // that 'size_to_compare' is greater that size of smallest of first chunks. template <typename ResultType, typename RHS> ResultType GenericCompare(const Cord& lhs, const RHS& rhs, size_t size_to_compare) { … } bool Cord::EqualsImpl(absl::string_view rhs, size_t size_to_compare) const { … } bool Cord::EqualsImpl(const Cord& rhs, size_t size_to_compare) const { … } template <typename RHS> inline int SharedCompareImpl(const Cord& lhs, const RHS& rhs) { … } int Cord::Compare(absl::string_view rhs) const { … } int Cord::CompareImpl(const Cord& rhs) const { … } bool Cord::EndsWith(absl::string_view rhs) const { … } bool Cord::EndsWith(const Cord& rhs) const { … } // -------------------------------------------------------------------- // Misc. operator basic_string() void CopyCordToString(const Cord& src, absl::Nonnull<std::string*> dst) { … } void AppendCordToString(const Cord& src, absl::Nonnull<std::string*> dst) { … } void Cord::CopyToArraySlowPath(absl::Nonnull<char*> dst) const { … } Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { … } char Cord::operator[](size_t i) const { … } namespace { // Tests whether the sequence of chunks beginning at `position` starts with // `needle`. // // REQUIRES: remaining `absl::Cord` starting at `position` is greater than or // equal to `needle.size()`. bool IsSubstringInCordAt(absl::Cord::CharIterator position, absl::string_view needle) { … } } // namespace // A few options how this could be implemented: // (a) Flatten the Cord and find, i.e. // haystack.Flatten().find(needle) // For large 'haystack' (where Cord makes sense to be used), this copies // the whole 'haystack' and can be slow. // (b) Use std::search, i.e. // std::search(haystack.char_begin(), haystack.char_end(), // needle.begin(), needle.end()) // This avoids the copy, but compares one byte at a time, and branches a // lot every time it has to advance. It is also not possible to use // std::search as is, because CharIterator is only an input iterator, not a // forward iterator. // (c) Use string_view::find in each fragment, and specifically handle fragment // boundaries. // // This currently implements option (b). absl::Cord::CharIterator absl::Cord::FindImpl(CharIterator it, absl::string_view needle) const { … } absl::Cord::CharIterator absl::Cord::Find(absl::string_view needle) const { … } namespace { // Tests whether the sequence of chunks beginning at `haystack` starts with the // sequence of chunks beginning at `needle_begin` and extending to `needle_end`. // // REQUIRES: remaining `absl::Cord` starting at `position` is greater than or // equal to `needle_end - needle_begin` and `advance`. bool IsSubcordInCordAt(absl::Cord::CharIterator haystack, absl::Cord::CharIterator needle_begin, absl::Cord::CharIterator needle_end) { … } // Tests whether the sequence of chunks beginning at `position` starts with the // cord `needle`. // // REQUIRES: remaining `absl::Cord` starting at `position` is greater than or // equal to `needle.size()`. bool IsSubcordInCordAt(absl::Cord::CharIterator position, const absl::Cord& needle) { … } } // namespace absl::Cord::CharIterator absl::Cord::Find(const absl::Cord& needle) const { … } bool Cord::Contains(absl::string_view rhs) const { … } bool Cord::Contains(const absl::Cord& rhs) const { … } absl::string_view Cord::FlattenSlowPath() { … } /* static */ bool Cord::GetFlatAux(absl::Nonnull<CordRep*> rep, absl::Nonnull<absl::string_view*> fragment) { … } /* static */ void Cord::ForEachChunkAux( absl::Nonnull<absl::cord_internal::CordRep*> rep, absl::FunctionRef<void(absl::string_view)> callback) { … } static void DumpNode(absl::Nonnull<CordRep*> nonnull_rep, bool include_data, absl::Nonnull<std::ostream*> os, int indent) { … } static std::string ReportError(absl::Nonnull<CordRep*> root, absl::Nonnull<CordRep*> node) { … } static bool VerifyNode(absl::Nonnull<CordRep*> root, absl::Nonnull<CordRep*> start_node) { … } std::ostream& operator<<(std::ostream& out, const Cord& cord) { … } namespace strings_internal { size_t CordTestAccess::FlatOverhead() { … } size_t CordTestAccess::MaxFlatLength() { … } size_t CordTestAccess::FlatTagToLength(uint8_t tag) { … } uint8_t CordTestAccess::LengthToTag(size_t s) { … } size_t CordTestAccess::SizeofCordRepExternal() { … } size_t CordTestAccess::SizeofCordRepSubstring() { … } } // namespace strings_internal ABSL_NAMESPACE_END } // namespace absl
Codebase Browser
chromium