diff options
author | 2020-03-03 11:22:10 -0800 | |
---|---|---|
committer | 2020-03-03 17:32:55 -0500 | |
commit | b19ba96766db08b1f32605cb4424a0e7ea0c7584 (patch) | |
tree | c4ba295b067b000b9d84410ec81e0095715641a5 /absl/strings/cord.h | |
parent | 06f0e767d13d4d68071c4fc51e25724e0fc8bc74 (diff) |
Export of internal Abseil changes
--
a3e58c1870a9626039f4d178d2d599319bd9f8a8 by Matt Kulukundis <kfm@google.com>:
Allow MakeCordFromExternal to take a zero arg releaser.
PiperOrigin-RevId: 298650274
--
01897c4a9bb99f3dc329a794019498ad345ddebd by Samuel Benzaquen <sbenza@google.com>:
Reduce library bloat for absl::Flag by moving the definition of base virtual functions to a .cc file.
This removes the duplicate symbols in user translation units and has the side effect of moving the vtable definition too (re key function)
PiperOrigin-RevId: 298617920
--
190f0d3782c63aed01046886d7fbc1be5bca2de9 by Derek Mauro <dmauro@google.com>:
Import GitHub #596: Unbreak stacktrace code for UWP apps
PiperOrigin-RevId: 298600834
--
cd5cf6f8c87b35b85a9584e94da2a99057345b73 by Gennadiy Rozental <rogeeff@google.com>:
Use union of heap allocated pointer, one word atomic and two word atomic to represent flags value.
Any type T, which is trivially copy-able and with with sizeof(T) <= 8, will be stored in atomic int64_t.
Any type T, which is trivially copy-able and with with 8 < sizeof(T) <= 16, will be stored in atomic AlignedTwoWords.
We also introducing value storage type to distinguish these cases.
PiperOrigin-RevId: 298497200
--
f8fe7bd53bfed601f002f521e34ab4bc083fc28b by Matthew Brown <matthewbr@google.com>:
Ensure a deep copy and proper equality on absl::Status::ErasePayload
PiperOrigin-RevId: 298482742
--
a5c9ccddf4b04f444e3f7e27dbc14faf1fcb5373 by Gennadiy Rozental <rogeeff@google.com>:
Change ChunkIterator implementation to use fixed capacity collection of CordRep*. We can now assume that depth never exceeds 91. That makes comparison operator exception safe.
I've tested that with this CL we do not observe an overhead of chunk_end. Compiler optimized this iterator completely.
PiperOrigin-RevId: 298458472
--
327ea5e8910bc388b03389c730763f9823abfce5 by Abseil Team <absl-team@google.com>:
Minor cleanups in b-tree code:
- Rename some variables: fix issues of different param names between definition/declaration, move away from `x` as a default meaningless variable name.
- Make init_leaf/init_internal be non-static methods (they already take the node as the first parameter).
- In internal_emplace/try_shrink, update root/rightmost the same way as in insert_unique/insert_multi.
- Replace a TODO with a comment.
PiperOrigin-RevId: 298432836
--
8020ce9ec8558ee712d9733ae3d660ac1d3ffe1a by Abseil Team <absl-team@google.com>:
Guard against unnecessary copy in case the buffer is empty. This is important in cases were the user is explicitly tuning their chunks to match PiecewiseChunkSize().
PiperOrigin-RevId: 298366044
--
89324441d1c0c697c90ba7d8fc63639805fcaa9d by Abseil Team <absl-team@google.com>:
Internal change
PiperOrigin-RevId: 298219363
GitOrigin-RevId: a3e58c1870a9626039f4d178d2d599319bd9f8a8
Change-Id: I28dffc684b6fd0292b94807b88ec6664d5d0e183
Diffstat (limited to 'absl/strings/cord.h')
-rw-r--r-- | absl/strings/cord.h | 100 |
1 files changed, 91 insertions, 9 deletions
diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 40566cba..68a7e52f 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -41,13 +41,13 @@ #include <iostream> #include <iterator> #include <string> +#include <type_traits> #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" -#include "absl/container/inlined_vector.h" #include "absl/functional/function_ref.h" #include "absl/meta/type_traits.h" #include "absl/strings/internal/cord_internal.h" @@ -66,6 +66,73 @@ template <typename H> H HashFragmentedCord(H, const Cord&); } +namespace cord_internal { + +// It's expensive to keep a tree perfectly balanced, so instead we keep trees +// approximately balanced. A tree node N of depth D(N) that contains a string +// of L(N) characters is considered balanced if L >= Fibonacci(D + 2). +// The "+ 2" is used to ensure that every leaf node contains at least one +// character. Here we presume that +// Fibonacci(0) = 0 +// Fibonacci(1) = 1 +// Fibonacci(2) = 1 +// Fibonacci(3) = 2 +// ... +// +// Fibonacci numbers are convenient because it means when two balanced trees of +// the same depth are made the children of a new node, the resulting tree is +// guaranteed to also be balanced: +// +// +// L(left) >= Fibonacci(D(left) + 2) +// L(right) >= Fibonacci(D(right) + 2) +// +// L(left) + L(right) >= Fibonacci(D(left) + 2) + Fibonacci(D(right) + 2) +// L(left) + L(right) == L(new_tree) +// +// L(new_tree) >= 2 * Fibonacci(D(child) + 2) +// D(child) == D(new_tree) - 1 +// +// L(new_tree) >= 2 * Fibonacci(D(new_tree) + 1) +// 2 * Fibonacci(N) >= Fibonacci(N + 1) +// +// L(new_tree) >= Fibonacci(D(new_tree) + 2) +// +// +// The 93rd Fibonacci number is the largest Fibonacci number that can be +// represented in 64 bits, so the size of a balanced Cord of depth 92 is too big +// for an unsigned 64 bit integer to hold. Therefore we can safely assume that +// the maximum depth of a Cord is 91. +constexpr size_t MaxCordDepth() { return 91; } + +// This class models fixed max size stack of CordRep pointers. +// The elements are being pushed back and popped from the back. +template <typename CordRepPtr, size_t N> +class CordTreePath { + public: + CordTreePath() {} + explicit CordTreePath(CordRepPtr root) { push_back(root); } + + bool empty() const { return size_ == 0; } + size_t size() const { return size_; } + void clear() { size_ = 0; } + + CordRepPtr back() { return data_[size_ - 1]; } + + void pop_back() { + --size_; + assert(size_ < N); + } + void push_back(CordRepPtr elem) { data_[size_++] = elem; } + + private: + CordRepPtr data_[N]; + size_t size_ = 0; +}; + +using CordTreeMutablePath = CordTreePath<CordRep*, MaxCordDepth()>; +} // namespace cord_internal + // A Cord is a sequence of characters. class Cord { private: @@ -114,7 +181,8 @@ class Cord { // 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`, + // * supports `void operator()(absl::string_view) const` or + // `void operator()() 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 @@ -127,8 +195,8 @@ 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); // }); // } // @@ -282,8 +350,7 @@ 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_; + absl::cord_internal::CordTreeMutablePath stack_of_right_children_; }; // Returns an iterator to the first chunk of the `Cord`. @@ -667,6 +734,21 @@ ExternalRepReleaserPair NewExternalWithUninitializedReleaser( absl::string_view data, ExternalReleaserInvoker invoker, size_t releaser_size); +struct Rank1 {}; +struct Rank0 : Rank1 {}; + +template <typename Releaser, typename = ::absl::base_internal::InvokeT< + 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::InvokeT<Releaser>> +void InvokeReleaser(Rank1, Releaser&& releaser, absl::string_view) { + ::absl::base_internal::Invoke(std::forward<Releaser>(releaser)); +} + // Creates a new `CordRep` that owns `data` and `releaser` and returns a pointer // to it, or `nullptr` if `data` was empty. template <typename Releaser> @@ -684,14 +766,14 @@ CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) { 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); + InvokeReleaser(Rank0{}, std::move(*my_releaser), d); my_releaser->~ReleaserType(); return sizeof(Releaser); }; |