diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/strings/internal/cord_internal.h')
-rw-r--r-- | third_party/abseil_cpp/absl/strings/internal/cord_internal.h | 270 |
1 files changed, 0 insertions, 270 deletions
diff --git a/third_party/abseil_cpp/absl/strings/internal/cord_internal.h b/third_party/abseil_cpp/absl/strings/internal/cord_internal.h deleted file mode 100644 index aa91a691b949..000000000000 --- a/third_party/abseil_cpp/absl/strings/internal/cord_internal.h +++ /dev/null @@ -1,270 +0,0 @@ -// 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. - -#ifndef ABSL_STRINGS_INTERNAL_CORD_INTERNAL_H_ -#define ABSL_STRINGS_INTERNAL_CORD_INTERNAL_H_ - -#include <atomic> -#include <cassert> -#include <cstddef> -#include <cstdint> -#include <type_traits> - -#include "absl/base/internal/invoke.h" -#include "absl/container/internal/compressed_tuple.h" -#include "absl/meta/type_traits.h" -#include "absl/strings/string_view.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -// Wraps std::atomic for reference counting. -class Refcount { - public: - constexpr Refcount() : count_{kRefIncrement} {} - struct Immortal {}; - explicit constexpr Refcount(Immortal) : count_(kImmortalTag) {} - - // Increments the reference count. Imposes no memory ordering. - inline void Increment() { - count_.fetch_add(kRefIncrement, std::memory_order_relaxed); - } - - // Asserts that the current refcount is greater than 0. If the refcount is - // greater than 1, decrements the reference count. - // - // Returns false if there are no references outstanding; true otherwise. - // Inserts barriers to ensure that state written before this method returns - // false will be visible to a thread that just observed this method returning - // false. - inline bool Decrement() { - int32_t refcount = count_.load(std::memory_order_acquire); - assert(refcount > 0 || refcount & kImmortalTag); - return refcount != kRefIncrement && - count_.fetch_sub(kRefIncrement, std::memory_order_acq_rel) != - kRefIncrement; - } - - // Same as Decrement but expect that refcount is greater than 1. - inline bool DecrementExpectHighRefcount() { - int32_t refcount = - count_.fetch_sub(kRefIncrement, std::memory_order_acq_rel); - assert(refcount > 0 || refcount & kImmortalTag); - return refcount != kRefIncrement; - } - - // Returns the current reference count using acquire semantics. - inline int32_t Get() const { - return count_.load(std::memory_order_acquire) >> kImmortalShift; - } - - // Returns whether the atomic integer is 1. - // If the reference count is used in the conventional way, a - // reference count of 1 implies that the current thread owns the - // reference and no other thread shares it. - // This call performs the test for a reference count of one, and - // performs the memory barrier needed for the owning thread - // to act on the object, knowing that it has exclusive access to the - // object. - inline bool IsOne() { - return count_.load(std::memory_order_acquire) == kRefIncrement; - } - - bool IsImmortal() const { - return (count_.load(std::memory_order_relaxed) & kImmortalTag) != 0; - } - - private: - // We reserve the bottom bit to tag a reference count as immortal. - // By making it `1` we ensure that we never reach `0` when adding/subtracting - // `2`, thus it never looks as if it should be destroyed. - // These are used for the StringConstant constructor where we do not increase - // the refcount at construction time (due to constinit requirements) but we - // will still decrease it at destruction time to avoid branching on Unref. - enum { - kImmortalShift = 1, - kRefIncrement = 1 << kImmortalShift, - kImmortalTag = kRefIncrement - 1 - }; - - std::atomic<int32_t> count_; -}; - -// The overhead of a vtable is too much for Cord, so we roll our own subclasses -// using only a single byte to differentiate classes from each other - the "tag" -// byte. Define the subclasses first so we can provide downcasting helper -// functions in the base class. - -struct CordRepConcat; -struct CordRepSubstring; -struct CordRepExternal; - -// Various representations that we allow -enum CordRepKind { - CONCAT = 0, - EXTERNAL = 1, - SUBSTRING = 2, - - // We have different tags for different sized flat arrays, - // starting with FLAT - FLAT = 3, -}; - -struct CordRep { - CordRep() = default; - constexpr CordRep(Refcount::Immortal immortal, size_t l) - : length(l), refcount(immortal), tag(EXTERNAL), data{} {} - - // The following three fields have to be less than 32 bytes since - // that is the smallest supported flat node size. - size_t length; - Refcount refcount; - // If tag < FLAT, it represents CordRepKind and indicates the type of node. - // Otherwise, the node type is CordRepFlat and the tag is the encoded size. - uint8_t tag; - char data[1]; // Starting point for flat array: MUST BE LAST FIELD of CordRep - - inline CordRepConcat* concat(); - inline const CordRepConcat* concat() const; - inline CordRepSubstring* substring(); - inline const CordRepSubstring* substring() const; - inline CordRepExternal* external(); - inline const CordRepExternal* external() const; -}; - -struct CordRepConcat : public CordRep { - CordRep* left; - CordRep* right; - - uint8_t depth() const { return static_cast<uint8_t>(data[0]); } - void set_depth(uint8_t depth) { data[0] = static_cast<char>(depth); } -}; - -struct CordRepSubstring : public CordRep { - size_t start; // Starting offset of substring in child - CordRep* child; -}; - -// Type for function pointer that will invoke the releaser function and also -// delete the `CordRepExternalImpl` corresponding to the passed in -// `CordRepExternal`. -using ExternalReleaserInvoker = void (*)(CordRepExternal*); - -// External CordReps are allocated together with a type erased releaser. The -// releaser is stored in the memory directly following the CordRepExternal. -struct CordRepExternal : public CordRep { - CordRepExternal() = default; - explicit constexpr CordRepExternal(absl::string_view str) - : CordRep(Refcount::Immortal{}, str.size()), - base(str.data()), - releaser_invoker(nullptr) {} - - const char* base; - // Pointer to function that knows how to call and destroy the releaser. - ExternalReleaserInvoker releaser_invoker; -}; - -struct Rank1 {}; -struct Rank0 : Rank1 {}; - -template <typename Releaser, typename = ::absl::base_internal::invoke_result_t< - Releaser, absl::string_view>> -void InvokeReleaser(Rank0, Releaser&& releaser, absl::string_view data) { - ::absl::base_internal::invoke(std::forward<Releaser>(releaser), data); -} - -template <typename Releaser, - typename = ::absl::base_internal::invoke_result_t<Releaser>> -void InvokeReleaser(Rank1, Releaser&& releaser, absl::string_view) { - ::absl::base_internal::invoke(std::forward<Releaser>(releaser)); -} - -// We use CompressedTuple so that we can benefit from EBCO. -template <typename Releaser> -struct CordRepExternalImpl - : public CordRepExternal, - public ::absl::container_internal::CompressedTuple<Releaser> { - // The extra int arg is so that we can avoid interfering with copy/move - // constructors while still benefitting from perfect forwarding. - template <typename T> - CordRepExternalImpl(T&& releaser, int) - : CordRepExternalImpl::CompressedTuple(std::forward<T>(releaser)) { - this->releaser_invoker = &Release; - } - - ~CordRepExternalImpl() { - InvokeReleaser(Rank0{}, std::move(this->template get<0>()), - absl::string_view(base, length)); - } - - static void Release(CordRepExternal* rep) { - delete static_cast<CordRepExternalImpl*>(rep); - } -}; - -template <typename Str> -struct ConstInitExternalStorage { - ABSL_CONST_INIT static CordRepExternal value; -}; - -template <typename Str> -CordRepExternal ConstInitExternalStorage<Str>::value(Str::value); - -enum { - kMaxInline = 15, - // Tag byte & kMaxInline means we are storing a pointer. - kTreeFlag = 1 << 4, - // Tag byte & kProfiledFlag means we are profiling the Cord. - kProfiledFlag = 1 << 5 -}; - -// If the data has length <= kMaxInline, we store it in `as_chars`, and -// store the size in `tagged_size`. -// Else we store it in a tree and store a pointer to that tree in -// `as_tree.rep` and store a tag in `tagged_size`. -struct AsTree { - absl::cord_internal::CordRep* rep; - char padding[kMaxInline + 1 - sizeof(absl::cord_internal::CordRep*) - 1]; - char tagged_size; -}; - -constexpr char GetOrNull(absl::string_view data, size_t pos) { - return pos < data.size() ? data[pos] : '\0'; -} - -union InlineData { - constexpr InlineData() : as_chars{} {} - explicit constexpr InlineData(AsTree tree) : as_tree(tree) {} - explicit constexpr InlineData(absl::string_view chars) - : as_chars{GetOrNull(chars, 0), GetOrNull(chars, 1), - GetOrNull(chars, 2), GetOrNull(chars, 3), - GetOrNull(chars, 4), GetOrNull(chars, 5), - GetOrNull(chars, 6), GetOrNull(chars, 7), - GetOrNull(chars, 8), GetOrNull(chars, 9), - GetOrNull(chars, 10), GetOrNull(chars, 11), - GetOrNull(chars, 12), GetOrNull(chars, 13), - GetOrNull(chars, 14), static_cast<char>(chars.size())} {} - - AsTree as_tree; - char as_chars[kMaxInline + 1]; -}; -static_assert(sizeof(InlineData) == kMaxInline + 1, ""); -static_assert(sizeof(AsTree) == sizeof(InlineData), ""); -static_assert(offsetof(AsTree, tagged_size) == kMaxInline, ""); - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl -#endif // ABSL_STRINGS_INTERNAL_CORD_INTERNAL_H_ |