1// Copyright 2020 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// -----------------------------------------------------------------------------
16// File: cord.h
17// -----------------------------------------------------------------------------
18//
19// This file defines the `absl::Cord` data structure and operations on that data
20// structure. A Cord is a string-like sequence of characters optimized for
21// specific use cases. Unlike a `std::string`, which stores an array of
22// contiguous characters, Cord data is stored in a structure consisting of
23// separate, reference-counted "chunks." (Currently, this implementation is a
24// tree structure, though that implementation may change.)
25//
26// Because a Cord consists of these chunks, data can be added to or removed from
27// a Cord during its lifetime. Chunks may also be shared between Cords. Unlike a
28// `std::string`, a Cord can therefore accommodate data that changes over its
29// lifetime, though it's not quite "mutable"; it can change only in the
30// attachment, detachment, or rearrangement of chunks of its constituent data.
31//
32// A Cord provides some benefit over `std::string` under the following (albeit
33// narrow) circumstances:
34//
35// * Cord data is designed to grow and shrink over a Cord's lifetime. Cord
36// provides efficient insertions and deletions at the start and end of the
37// character sequences, avoiding copies in those cases. Static data should
38// generally be stored as strings.
39// * External memory consisting of string-like data can be directly added to
40// a Cord without requiring copies or allocations.
41// * Cord data may be shared and copied cheaply. Cord provides a copy-on-write
42// implementation and cheap sub-Cord operations. Copying a Cord is an O(1)
43// operation.
44//
45// As a consequence to the above, Cord data is generally large. Small data
46// should generally use strings, as construction of a Cord requires some
47// overhead. Small Cords (<= 15 bytes) are represented inline, but most small
48// Cords are expected to grow over their lifetimes.
49//
50// Note that because a Cord is made up of separate chunked data, random access
51// to character data within a Cord is slower than within a `std::string`.
52//
53// Thread Safety
54//
55// Cord has the same thread-safety properties as many other types like
56// std::string, std::vector<>, int, etc -- it is thread-compatible. In
57// particular, if threads do not call non-const methods, then it is safe to call
58// const methods without synchronization. Copying a Cord produces a new instance
59// that can be used concurrently with the original in arbitrary ways.
60
61#ifndef ABSL_STRINGS_CORD_H_
62#define ABSL_STRINGS_CORD_H_
63
64#include <algorithm>
65#include <cstddef>
66#include <cstdint>
67#include <cstring>
68#include <iosfwd>
69#include <iterator>
70#include <string>
71#include <type_traits>
72
73#include "absl/base/attributes.h"
74#include "absl/base/config.h"
75#include "absl/base/internal/endian.h"
76#include "absl/base/internal/per_thread_tls.h"
77#include "absl/base/macros.h"
78#include "absl/base/port.h"
79#include "absl/container/inlined_vector.h"
80#include "absl/functional/function_ref.h"
81#include "absl/meta/type_traits.h"
82#include "absl/strings/cord_analysis.h"
83#include "absl/strings/cord_buffer.h"
84#include "absl/strings/internal/cord_data_edge.h"
85#include "absl/strings/internal/cord_internal.h"
86#include "absl/strings/internal/cord_rep_btree.h"
87#include "absl/strings/internal/cord_rep_btree_reader.h"
88#include "absl/strings/internal/cord_rep_crc.h"
89#include "absl/strings/internal/cord_rep_ring.h"
90#include "absl/strings/internal/cordz_functions.h"
91#include "absl/strings/internal/cordz_info.h"
92#include "absl/strings/internal/cordz_statistics.h"
93#include "absl/strings/internal/cordz_update_scope.h"
94#include "absl/strings/internal/cordz_update_tracker.h"
95#include "absl/strings/internal/resize_uninitialized.h"
96#include "absl/strings/internal/string_constant.h"
97#include "absl/strings/string_view.h"
98#include "absl/types/optional.h"
99
100namespace absl {
101ABSL_NAMESPACE_BEGIN
102class Cord;
103class CordTestPeer;
104template <typename Releaser>
105Cord MakeCordFromExternal(absl::string_view, Releaser&&);
106void CopyCordToString(const Cord& src, std::string* dst);
107
108// Cord memory accounting modes
109enum class CordMemoryAccounting {
110 // Counts the *approximate* number of bytes held in full or in part by this
111 // Cord (which may not remain the same between invocations). Cords that share
112 // memory could each be "charged" independently for the same shared memory.
113 kTotal,
114
115 // Counts the *approximate* number of bytes held in full or in part by this
116 // Cord weighted by the sharing ratio of that data. For example, if some data
117 // edge is shared by 4 different Cords, then each cord is attributed 1/4th of
118 // the total memory usage as a 'fair share' of the total memory usage.
119 kFairShare,
120};
121
122// Cord
123//
124// A Cord is a sequence of characters, designed to be more efficient than a
125// `std::string` in certain circumstances: namely, large string data that needs
126// to change over its lifetime or shared, especially when such data is shared
127// across API boundaries.
128//
129// A Cord stores its character data in a structure that allows efficient prepend
130// and append operations. This makes a Cord useful for large string data sent
131// over in a wire format that may need to be prepended or appended at some point
132// during the data exchange (e.g. HTTP, protocol buffers). For example, a
133// Cord is useful for storing an HTTP request, and prepending an HTTP header to
134// such a request.
135//
136// Cords should not be used for storing general string data, however. They
137// require overhead to construct and are slower than strings for random access.
138//
139// The Cord API provides the following common API operations:
140//
141// * Create or assign Cords out of existing string data, memory, or other Cords
142// * Append and prepend data to an existing Cord
143// * Create new Sub-Cords from existing Cord data
144// * Swap Cord data and compare Cord equality
145// * Write out Cord data by constructing a `std::string`
146//
147// Additionally, the API provides iterator utilities to iterate through Cord
148// data via chunks or character bytes.
149//
150class Cord {
151 private:
152 template <typename T>
153 using EnableIfString =
154 absl::enable_if_t<std::is_same<T, std::string>::value, int>;
155
156 public:
157 // Cord::Cord() Constructors.
158
159 // Creates an empty Cord.
160 constexpr Cord() noexcept;
161
162 // Creates a Cord from an existing Cord. Cord is copyable and efficiently
163 // movable. The moved-from state is valid but unspecified.
164 Cord(const Cord& src);
165 Cord(Cord&& src) noexcept;
166 Cord& operator=(const Cord& x);
167 Cord& operator=(Cord&& x) noexcept;
168
169 // Creates a Cord from a `src` string. This constructor is marked explicit to
170 // prevent implicit Cord constructions from arguments convertible to an
171 // `absl::string_view`.
172 explicit Cord(absl::string_view src);
173 Cord& operator=(absl::string_view src);
174
175 // Creates a Cord from a `std::string&&` rvalue. These constructors are
176 // templated to avoid ambiguities for types that are convertible to both
177 // `absl::string_view` and `std::string`, such as `const char*`.
178 template <typename T, EnableIfString<T> = 0>
179 explicit Cord(T&& src);
180 template <typename T, EnableIfString<T> = 0>
181 Cord& operator=(T&& src);
182
183 // Cord::~Cord()
184 //
185 // Destructs the Cord.
186 ~Cord() {
187 if (contents_.is_tree()) DestroyCordSlow();
188 }
189
190 // MakeCordFromExternal()
191 //
192 // Creates a Cord that takes ownership of external string memory. The
193 // contents of `data` are not copied to the Cord; instead, the external
194 // memory is added to the Cord and reference-counted. This data may not be
195 // changed for the life of the Cord, though it may be prepended or appended
196 // to.
197 //
198 // `MakeCordFromExternal()` takes a callable "releaser" that is invoked when
199 // the reference count for `data` reaches zero. As noted above, this data must
200 // remain live until the releaser is invoked. The callable releaser also must:
201 //
202 // * be move constructible
203 // * support `void operator()(absl::string_view) const` or `void operator()`
204 //
205 // Example:
206 //
207 // Cord MakeCord(BlockPool* pool) {
208 // Block* block = pool->NewBlock();
209 // FillBlock(block);
210 // return absl::MakeCordFromExternal(
211 // block->ToStringView(),
212 // [pool, block](absl::string_view v) {
213 // pool->FreeBlock(block, v);
214 // });
215 // }
216 //
217 // WARNING: Because a Cord can be reference-counted, it's likely a bug if your
218 // releaser doesn't do anything. For example, consider the following:
219 //
220 // void Foo(const char* buffer, int len) {
221 // auto c = absl::MakeCordFromExternal(absl::string_view(buffer, len),
222 // [](absl::string_view) {});
223 //
224 // // BUG: If Bar() copies its cord for any reason, including keeping a
225 // // substring of it, the lifetime of buffer might be extended beyond
226 // // when Foo() returns.
227 // Bar(c);
228 // }
229 template <typename Releaser>
230 friend Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser);
231
232 // Cord::Clear()
233 //
234 // Releases the Cord data. Any nodes that share data with other Cords, if
235 // applicable, will have their reference counts reduced by 1.
236 ABSL_ATTRIBUTE_REINITIALIZES void Clear();
237
238 // Cord::Append()
239 //
240 // Appends data to the Cord, which may come from another Cord or other string
241 // data.
242 void Append(const Cord& src);
243 void Append(Cord&& src);
244 void Append(absl::string_view src);
245 template <typename T, EnableIfString<T> = 0>
246 void Append(T&& src);
247
248 // Appends `buffer` to this cord, unless `buffer` has a zero length in which
249 // case this method has no effect on this cord instance.
250 // This method is guaranteed to consume `buffer`.
251 void Append(CordBuffer buffer);
252
253 // Returns a CordBuffer, re-using potential existing capacity in this cord.
254 //
255 // Cord instances may have additional unused capacity in the last (or first)
256 // nodes of the underlying tree to facilitate amortized growth. This method
257 // allows applications to explicitly use this spare capacity if available,
258 // or create a new CordBuffer instance otherwise.
259 // If this cord has a final non-shared node with at least `min_capacity`
260 // available, then this method will return that buffer including its data
261 // contents. I.e.; the returned buffer will have a non-zero length, and
262 // a capacity of at least `buffer.length + min_capacity`. Otherwise, this
263 // method will return `CordBuffer::CreateWithDefaultLimit(capacity)`.
264 //
265 // Below an example of using GetAppendBuffer. Notice that in this example we
266 // use `GetAppendBuffer()` only on the first iteration. As we know nothing
267 // about any initial extra capacity in `cord`, we may be able to use the extra
268 // capacity. But as we add new buffers with fully utilized contents after that
269 // we avoid calling `GetAppendBuffer()` on subsequent iterations: while this
270 // works fine, it results in an unnecessary inspection of cord contents:
271 //
272 // void AppendRandomDataToCord(absl::Cord &cord, size_t n) {
273 // bool first = true;
274 // while (n > 0) {
275 // CordBuffer buffer = first ? cord.GetAppendBuffer(n)
276 // : CordBuffer::CreateWithDefaultLimit(n);
277 // absl::Span<char> data = buffer.available_up_to(n);
278 // FillRandomValues(data.data(), data.size());
279 // buffer.IncreaseLengthBy(data.size());
280 // cord.Append(std::move(buffer));
281 // n -= data.size();
282 // first = false;
283 // }
284 // }
285 CordBuffer GetAppendBuffer(size_t capacity, size_t min_capacity = 16);
286
287 // Returns a CordBuffer, re-using potential existing capacity in this cord.
288 //
289 // This function is identical to `GetAppendBuffer`, except that in the case
290 // where a new `CordBuffer` is allocated, it is allocated using the provided
291 // custom limit instead of the default limit. `GetAppendBuffer` will default
292 // to `CordBuffer::CreateWithDefaultLimit(capacity)` whereas this method
293 // will default to `CordBuffer::CreateWithCustomLimit(block_size, capacity)`.
294 // This method is equivalent to `GetAppendBuffer` if `block_size` is zero.
295 // See the documentation for `CreateWithCustomLimit` for more details on the
296 // restrictions and legal values for `block_size`.
297 CordBuffer GetCustomAppendBuffer(size_t block_size, size_t capacity,
298 size_t min_capacity = 16);
299
300 // Cord::Prepend()
301 //
302 // Prepends data to the Cord, which may come from another Cord or other string
303 // data.
304 void Prepend(const Cord& src);
305 void Prepend(absl::string_view src);
306 template <typename T, EnableIfString<T> = 0>
307 void Prepend(T&& src);
308
309 // Prepends `buffer` to this cord, unless `buffer` has a zero length in which
310 // case this method has no effect on this cord instance.
311 // This method is guaranteed to consume `buffer`.
312 void Prepend(CordBuffer buffer);
313
314 // Cord::RemovePrefix()
315 //
316 // Removes the first `n` bytes of a Cord.
317 void RemovePrefix(size_t n);
318 void RemoveSuffix(size_t n);
319
320 // Cord::Subcord()
321 //
322 // Returns a new Cord representing the subrange [pos, pos + new_size) of
323 // *this. If pos >= size(), the result is empty(). If
324 // (pos + new_size) >= size(), the result is the subrange [pos, size()).
325 Cord Subcord(size_t pos, size_t new_size) const;
326
327 // Cord::swap()
328 //
329 // Swaps the contents of the Cord with `other`.
330 void swap(Cord& other) noexcept;
331
332 // swap()
333 //
334 // Swaps the contents of two Cords.
335 friend void swap(Cord& x, Cord& y) noexcept { x.swap(other&: y); }
336
337 // Cord::size()
338 //
339 // Returns the size of the Cord.
340 size_t size() const;
341
342 // Cord::empty()
343 //
344 // Determines whether the given Cord is empty, returning `true` is so.
345 bool empty() const;
346
347 // Cord::EstimatedMemoryUsage()
348 //
349 // Returns the *approximate* number of bytes held by this cord.
350 // See CordMemoryAccounting for more information on the accounting method.
351 size_t EstimatedMemoryUsage(CordMemoryAccounting accounting_method =
352 CordMemoryAccounting::kTotal) const;
353
354 // Cord::Compare()
355 //
356 // Compares 'this' Cord with rhs. This function and its relatives treat Cords
357 // as sequences of unsigned bytes. The comparison is a straightforward
358 // lexicographic comparison. `Cord::Compare()` returns values as follows:
359 //
360 // -1 'this' Cord is smaller
361 // 0 two Cords are equal
362 // 1 'this' Cord is larger
363 int Compare(absl::string_view rhs) const;
364 int Compare(const Cord& rhs) const;
365
366 // Cord::StartsWith()
367 //
368 // Determines whether the Cord starts with the passed string data `rhs`.
369 bool StartsWith(const Cord& rhs) const;
370 bool StartsWith(absl::string_view rhs) const;
371
372 // Cord::EndsWith()
373 //
374 // Determines whether the Cord ends with the passed string data `rhs`.
375 bool EndsWith(absl::string_view rhs) const;
376 bool EndsWith(const Cord& rhs) const;
377
378 // Cord::operator std::string()
379 //
380 // Converts a Cord into a `std::string()`. This operator is marked explicit to
381 // prevent unintended Cord usage in functions that take a string.
382 explicit operator std::string() const;
383
384 // CopyCordToString()
385 //
386 // Copies the contents of a `src` Cord into a `*dst` string.
387 //
388 // This function optimizes the case of reusing the destination string since it
389 // can reuse previously allocated capacity. However, this function does not
390 // guarantee that pointers previously returned by `dst->data()` remain valid
391 // even if `*dst` had enough capacity to hold `src`. If `*dst` is a new
392 // object, prefer to simply use the conversion operator to `std::string`.
393 friend void CopyCordToString(const Cord& src, std::string* dst);
394
395 class CharIterator;
396
397 //----------------------------------------------------------------------------
398 // Cord::ChunkIterator
399 //----------------------------------------------------------------------------
400 //
401 // A `Cord::ChunkIterator` allows iteration over the constituent chunks of its
402 // Cord. Such iteration allows you to perform non-const operations on the data
403 // of a Cord without modifying it.
404 //
405 // Generally, you do not instantiate a `Cord::ChunkIterator` directly;
406 // instead, you create one implicitly through use of the `Cord::Chunks()`
407 // member function.
408 //
409 // The `Cord::ChunkIterator` has the following properties:
410 //
411 // * The iterator is invalidated after any non-const operation on the
412 // Cord object over which it iterates.
413 // * The `string_view` returned by dereferencing a valid, non-`end()`
414 // iterator is guaranteed to be non-empty.
415 // * Two `ChunkIterator` objects can be compared equal if and only if they
416 // remain valid and iterate over the same Cord.
417 // * The iterator in this case is a proxy iterator; the `string_view`
418 // returned by the iterator does not live inside the Cord, and its
419 // lifetime is limited to the lifetime of the iterator itself. To help
420 // prevent lifetime issues, `ChunkIterator::reference` is not a true
421 // reference type and is equivalent to `value_type`.
422 // * The iterator keeps state that can grow for Cords that contain many
423 // nodes and are imbalanced due to sharing. Prefer to pass this type by
424 // const reference instead of by value.
425 class ChunkIterator {
426 public:
427 using iterator_category = std::input_iterator_tag;
428 using value_type = absl::string_view;
429 using difference_type = ptrdiff_t;
430 using pointer = const value_type*;
431 using reference = value_type;
432
433 ChunkIterator() = default;
434
435 ChunkIterator& operator++();
436 ChunkIterator operator++(int);
437 bool operator==(const ChunkIterator& other) const;
438 bool operator!=(const ChunkIterator& other) const;
439 reference operator*() const;
440 pointer operator->() const;
441
442 friend class Cord;
443 friend class CharIterator;
444
445 private:
446 using CordRep = absl::cord_internal::CordRep;
447 using CordRepBtree = absl::cord_internal::CordRepBtree;
448 using CordRepBtreeReader = absl::cord_internal::CordRepBtreeReader;
449
450 // Constructs a `begin()` iterator from `tree`. `tree` must not be null.
451 explicit ChunkIterator(cord_internal::CordRep* tree);
452
453 // Constructs a `begin()` iterator from `cord`.
454 explicit ChunkIterator(const Cord* cord);
455
456 // Initializes this instance from a tree. Invoked by constructors.
457 void InitTree(cord_internal::CordRep* tree);
458
459 // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
460 // `current_chunk_.size()`.
461 void RemoveChunkPrefix(size_t n);
462 Cord AdvanceAndReadBytes(size_t n);
463 void AdvanceBytes(size_t n);
464
465 // Btree specific operator++
466 ChunkIterator& AdvanceBtree();
467 void AdvanceBytesBtree(size_t n);
468
469 // A view into bytes of the current `CordRep`. It may only be a view to a
470 // suffix of bytes if this is being used by `CharIterator`.
471 absl::string_view current_chunk_;
472 // The current leaf, or `nullptr` if the iterator points to short data.
473 // If the current chunk is a substring node, current_leaf_ points to the
474 // underlying flat or external node.
475 absl::cord_internal::CordRep* current_leaf_ = nullptr;
476 // The number of bytes left in the `Cord` over which we are iterating.
477 size_t bytes_remaining_ = 0;
478
479 // Cord reader for cord btrees. Empty if not traversing a btree.
480 CordRepBtreeReader btree_reader_;
481 };
482
483 // Cord::chunk_begin()
484 //
485 // Returns an iterator to the first chunk of the `Cord`.
486 //
487 // Generally, prefer using `Cord::Chunks()` within a range-based for loop for
488 // iterating over the chunks of a Cord. This method may be useful for getting
489 // a `ChunkIterator` where range-based for-loops are not useful.
490 //
491 // Example:
492 //
493 // absl::Cord::ChunkIterator FindAsChunk(const absl::Cord& c,
494 // absl::string_view s) {
495 // return std::find(c.chunk_begin(), c.chunk_end(), s);
496 // }
497 ChunkIterator chunk_begin() const;
498
499 // Cord::chunk_end()
500 //
501 // Returns an iterator one increment past the last chunk of the `Cord`.
502 //
503 // Generally, prefer using `Cord::Chunks()` within a range-based for loop for
504 // iterating over the chunks of a Cord. This method may be useful for getting
505 // a `ChunkIterator` where range-based for-loops may not be available.
506 ChunkIterator chunk_end() const;
507
508 //----------------------------------------------------------------------------
509 // Cord::ChunkRange
510 //----------------------------------------------------------------------------
511 //
512 // `ChunkRange` is a helper class for iterating over the chunks of the `Cord`,
513 // producing an iterator which can be used within a range-based for loop.
514 // Construction of a `ChunkRange` will return an iterator pointing to the
515 // first chunk of the Cord. Generally, do not construct a `ChunkRange`
516 // directly; instead, prefer to use the `Cord::Chunks()` method.
517 //
518 // Implementation note: `ChunkRange` is simply a convenience wrapper over
519 // `Cord::chunk_begin()` and `Cord::chunk_end()`.
520 class ChunkRange {
521 public:
522 // Fulfill minimum c++ container requirements [container.requirements]
523 // These (partial) container type definitions allow ChunkRange to be used
524 // in various utilities expecting a subset of [container.requirements].
525 // For example, the below enables using `::testing::ElementsAre(...)`
526 using value_type = absl::string_view;
527 using reference = value_type&;
528 using const_reference = const value_type&;
529 using iterator = ChunkIterator;
530 using const_iterator = ChunkIterator;
531
532 explicit ChunkRange(const Cord* cord) : cord_(cord) {}
533
534 ChunkIterator begin() const;
535 ChunkIterator end() const;
536
537 private:
538 const Cord* cord_;
539 };
540
541 // Cord::Chunks()
542 //
543 // Returns a `Cord::ChunkRange` for iterating over the chunks of a `Cord` with
544 // a range-based for-loop. For most iteration tasks on a Cord, use
545 // `Cord::Chunks()` to retrieve this iterator.
546 //
547 // Example:
548 //
549 // void ProcessChunks(const Cord& cord) {
550 // for (absl::string_view chunk : cord.Chunks()) { ... }
551 // }
552 //
553 // Note that the ordinary caveats of temporary lifetime extension apply:
554 //
555 // void Process() {
556 // for (absl::string_view chunk : CordFactory().Chunks()) {
557 // // The temporary Cord returned by CordFactory has been destroyed!
558 // }
559 // }
560 ChunkRange Chunks() const;
561
562 //----------------------------------------------------------------------------
563 // Cord::CharIterator
564 //----------------------------------------------------------------------------
565 //
566 // A `Cord::CharIterator` allows iteration over the constituent characters of
567 // a `Cord`.
568 //
569 // Generally, you do not instantiate a `Cord::CharIterator` directly; instead,
570 // you create one implicitly through use of the `Cord::Chars()` member
571 // function.
572 //
573 // A `Cord::CharIterator` has the following properties:
574 //
575 // * The iterator is invalidated after any non-const operation on the
576 // Cord object over which it iterates.
577 // * Two `CharIterator` objects can be compared equal if and only if they
578 // remain valid and iterate over the same Cord.
579 // * The iterator keeps state that can grow for Cords that contain many
580 // nodes and are imbalanced due to sharing. Prefer to pass this type by
581 // const reference instead of by value.
582 // * This type cannot act as a forward iterator because a `Cord` can reuse
583 // sections of memory. This fact violates the requirement for forward
584 // iterators to compare equal if dereferencing them returns the same
585 // object.
586 class CharIterator {
587 public:
588 using iterator_category = std::input_iterator_tag;
589 using value_type = char;
590 using difference_type = ptrdiff_t;
591 using pointer = const char*;
592 using reference = const char&;
593
594 CharIterator() = default;
595
596 CharIterator& operator++();
597 CharIterator operator++(int);
598 bool operator==(const CharIterator& other) const;
599 bool operator!=(const CharIterator& other) const;
600 reference operator*() const;
601 pointer operator->() const;
602
603 friend Cord;
604
605 private:
606 explicit CharIterator(const Cord* cord) : chunk_iterator_(cord) {}
607
608 ChunkIterator chunk_iterator_;
609 };
610
611 // Cord::AdvanceAndRead()
612 //
613 // Advances the `Cord::CharIterator` by `n_bytes` and returns the bytes
614 // advanced as a separate `Cord`. `n_bytes` must be less than or equal to the
615 // number of bytes within the Cord; otherwise, behavior is undefined. It is
616 // valid to pass `char_end()` and `0`.
617 static Cord AdvanceAndRead(CharIterator* it, size_t n_bytes);
618
619 // Cord::Advance()
620 //
621 // Advances the `Cord::CharIterator` by `n_bytes`. `n_bytes` must be less than
622 // or equal to the number of bytes remaining within the Cord; otherwise,
623 // behavior is undefined. It is valid to pass `char_end()` and `0`.
624 static void Advance(CharIterator* it, size_t n_bytes);
625
626 // Cord::ChunkRemaining()
627 //
628 // Returns the longest contiguous view starting at the iterator's position.
629 //
630 // `it` must be dereferenceable.
631 static absl::string_view ChunkRemaining(const CharIterator& it);
632
633 // Cord::char_begin()
634 //
635 // Returns an iterator to the first character of the `Cord`.
636 //
637 // Generally, prefer using `Cord::Chars()` within a range-based for loop for
638 // iterating over the chunks of a Cord. This method may be useful for getting
639 // a `CharIterator` where range-based for-loops may not be available.
640 CharIterator char_begin() const;
641
642 // Cord::char_end()
643 //
644 // Returns an iterator to one past the last character of the `Cord`.
645 //
646 // Generally, prefer using `Cord::Chars()` within a range-based for loop for
647 // iterating over the chunks of a Cord. This method may be useful for getting
648 // a `CharIterator` where range-based for-loops are not useful.
649 CharIterator char_end() const;
650
651 // Cord::CharRange
652 //
653 // `CharRange` is a helper class for iterating over the characters of a
654 // producing an iterator which can be used within a range-based for loop.
655 // Construction of a `CharRange` will return an iterator pointing to the first
656 // character of the Cord. Generally, do not construct a `CharRange` directly;
657 // instead, prefer to use the `Cord::Chars()` method shown below.
658 //
659 // Implementation note: `CharRange` is simply a convenience wrapper over
660 // `Cord::char_begin()` and `Cord::char_end()`.
661 class CharRange {
662 public:
663 // Fulfill minimum c++ container requirements [container.requirements]
664 // Theses (partial) container type definitions allow CharRange to be used
665 // in various utilities expecting a subset of [container.requirements].
666 // For example, the below enables using `::testing::ElementsAre(...)`
667 using value_type = char;
668 using reference = value_type&;
669 using const_reference = const value_type&;
670 using iterator = CharIterator;
671 using const_iterator = CharIterator;
672
673 explicit CharRange(const Cord* cord) : cord_(cord) {}
674
675 CharIterator begin() const;
676 CharIterator end() const;
677
678 private:
679 const Cord* cord_;
680 };
681
682 // Cord::Chars()
683 //
684 // Returns a `Cord::CharRange` for iterating over the characters of a `Cord`
685 // with a range-based for-loop. For most character-based iteration tasks on a
686 // Cord, use `Cord::Chars()` to retrieve this iterator.
687 //
688 // Example:
689 //
690 // void ProcessCord(const Cord& cord) {
691 // for (char c : cord.Chars()) { ... }
692 // }
693 //
694 // Note that the ordinary caveats of temporary lifetime extension apply:
695 //
696 // void Process() {
697 // for (char c : CordFactory().Chars()) {
698 // // The temporary Cord returned by CordFactory has been destroyed!
699 // }
700 // }
701 CharRange Chars() const;
702
703 // Cord::operator[]
704 //
705 // Gets the "i"th character of the Cord and returns it, provided that
706 // 0 <= i < Cord.size().
707 //
708 // NOTE: This routine is reasonably efficient. It is roughly
709 // logarithmic based on the number of chunks that make up the cord. Still,
710 // if you need to iterate over the contents of a cord, you should
711 // use a CharIterator/ChunkIterator rather than call operator[] or Get()
712 // repeatedly in a loop.
713 char operator[](size_t i) const;
714
715 // Cord::TryFlat()
716 //
717 // If this cord's representation is a single flat array, returns a
718 // string_view referencing that array. Otherwise returns nullopt.
719 absl::optional<absl::string_view> TryFlat() const;
720
721 // Cord::Flatten()
722 //
723 // Flattens the cord into a single array and returns a view of the data.
724 //
725 // If the cord was already flat, the contents are not modified.
726 absl::string_view Flatten();
727
728 // Supports absl::Cord as a sink object for absl::Format().
729 friend void AbslFormatFlush(absl::Cord* cord, absl::string_view part) {
730 cord->Append(src: part);
731 }
732
733 // Cord::SetExpectedChecksum()
734 //
735 // Stores a checksum value with this non-empty cord instance, for later
736 // retrieval.
737 //
738 // The expected checksum is a number stored out-of-band, alongside the data.
739 // It is preserved across copies and assignments, but any mutations to a cord
740 // will cause it to lose its expected checksum.
741 //
742 // The expected checksum is not part of a Cord's value, and does not affect
743 // operations such as equality or hashing.
744 //
745 // This field is intended to store a CRC32C checksum for later validation, to
746 // help support end-to-end checksum workflows. However, the Cord API itself
747 // does no CRC validation, and assigns no meaning to this number.
748 //
749 // This call has no effect if this cord is empty.
750 void SetExpectedChecksum(uint32_t crc);
751
752 // Returns this cord's expected checksum, if it has one. Otherwise, returns
753 // nullopt.
754 absl::optional<uint32_t> ExpectedChecksum() const;
755
756 template <typename H>
757 friend H AbslHashValue(H hash_state, const absl::Cord& c) {
758 absl::optional<absl::string_view> maybe_flat = c.TryFlat();
759 if (maybe_flat.has_value()) {
760 return H::combine(std::move(hash_state), *maybe_flat);
761 }
762 return c.HashFragmented(std::move(hash_state));
763 }
764
765 // Create a Cord with the contents of StringConstant<T>::value.
766 // No allocations will be done and no data will be copied.
767 // This is an INTERNAL API and subject to change or removal. This API can only
768 // be used by spelling absl::strings_internal::MakeStringConstant, which is
769 // also an internal API.
770 template <typename T>
771 // NOLINTNEXTLINE(google-explicit-constructor)
772 constexpr Cord(strings_internal::StringConstant<T>);
773
774 private:
775 using CordRep = absl::cord_internal::CordRep;
776 using CordRepFlat = absl::cord_internal::CordRepFlat;
777 using CordzInfo = cord_internal::CordzInfo;
778 using CordzUpdateScope = cord_internal::CordzUpdateScope;
779 using CordzUpdateTracker = cord_internal::CordzUpdateTracker;
780 using InlineData = cord_internal::InlineData;
781 using MethodIdentifier = CordzUpdateTracker::MethodIdentifier;
782
783 // Creates a cord instance with `method` representing the originating
784 // public API call causing the cord to be created.
785 explicit Cord(absl::string_view src, MethodIdentifier method);
786
787 friend class CordTestPeer;
788 friend bool operator==(const Cord& lhs, const Cord& rhs);
789 friend bool operator==(const Cord& lhs, absl::string_view rhs);
790
791 friend const CordzInfo* GetCordzInfoForTesting(const Cord& cord);
792
793 // Calls the provided function once for each cord chunk, in order. Unlike
794 // Chunks(), this API will not allocate memory.
795 void ForEachChunk(absl::FunctionRef<void(absl::string_view)>) const;
796
797 // Allocates new contiguous storage for the contents of the cord. This is
798 // called by Flatten() when the cord was not already flat.
799 absl::string_view FlattenSlowPath();
800
801 // Actual cord contents are hidden inside the following simple
802 // class so that we can isolate the bulk of cord.cc from changes
803 // to the representation.
804 //
805 // InlineRep holds either a tree pointer, or an array of kMaxInline bytes.
806 class InlineRep {
807 public:
808 static constexpr unsigned char kMaxInline = cord_internal::kMaxInline;
809 static_assert(kMaxInline >= sizeof(absl::cord_internal::CordRep*), "");
810
811 constexpr InlineRep() : data_() {}
812 explicit InlineRep(InlineData::DefaultInitType init) : data_(init) {}
813 InlineRep(const InlineRep& src);
814 InlineRep(InlineRep&& src);
815 InlineRep& operator=(const InlineRep& src);
816 InlineRep& operator=(InlineRep&& src) noexcept;
817
818 explicit constexpr InlineRep(cord_internal::InlineData data);
819
820 void Swap(InlineRep* rhs);
821 bool empty() const;
822 size_t size() const;
823 const char* data() const; // Returns nullptr if holding pointer
824 void set_data(const char* data, size_t n); // Discards pointer, if any
825 char* set_data(size_t n); // Write data to the result
826 // Returns nullptr if holding bytes
827 absl::cord_internal::CordRep* tree() const;
828 absl::cord_internal::CordRep* as_tree() const;
829 const char* as_chars() const;
830 // Returns non-null iff was holding a pointer
831 absl::cord_internal::CordRep* clear();
832 // Converts to pointer if necessary.
833 void reduce_size(size_t n); // REQUIRES: holding data
834 void remove_prefix(size_t n); // REQUIRES: holding data
835 void AppendArray(absl::string_view src, MethodIdentifier method);
836 absl::string_view FindFlatStartPiece() const;
837
838 // Creates a CordRepFlat instance from the current inlined data with `extra'
839 // bytes of desired additional capacity.
840 CordRepFlat* MakeFlatWithExtraCapacity(size_t extra);
841
842 // Sets the tree value for this instance. `rep` must not be null.
843 // Requires the current instance to hold a tree, and a lock to be held on
844 // any CordzInfo referenced by this instance. The latter is enforced through
845 // the CordzUpdateScope argument. If the current instance is sampled, then
846 // the CordzInfo instance is updated to reference the new `rep` value.
847 void SetTree(CordRep* rep, const CordzUpdateScope& scope);
848
849 // Identical to SetTree(), except that `rep` is allowed to be null, in
850 // which case the current instance is reset to an empty value.
851 void SetTreeOrEmpty(CordRep* rep, const CordzUpdateScope& scope);
852
853 // Sets the tree value for this instance, and randomly samples this cord.
854 // This function disregards existing contents in `data_`, and should be
855 // called when a Cord is 'promoted' from an 'uninitialized' or 'inlined'
856 // value to a non-inlined (tree / ring) value.
857 void EmplaceTree(CordRep* rep, MethodIdentifier method);
858
859 // Identical to EmplaceTree, except that it copies the parent stack from
860 // the provided `parent` data if the parent is sampled.
861 void EmplaceTree(CordRep* rep, const InlineData& parent,
862 MethodIdentifier method);
863
864 // Commits the change of a newly created, or updated `rep` root value into
865 // this cord. `old_rep` indicates the old (inlined or tree) value of the
866 // cord, and determines if the commit invokes SetTree() or EmplaceTree().
867 void CommitTree(const CordRep* old_rep, CordRep* rep,
868 const CordzUpdateScope& scope, MethodIdentifier method);
869
870 void AppendTreeToInlined(CordRep* tree, MethodIdentifier method);
871 void AppendTreeToTree(CordRep* tree, MethodIdentifier method);
872 void AppendTree(CordRep* tree, MethodIdentifier method);
873 void PrependTreeToInlined(CordRep* tree, MethodIdentifier method);
874 void PrependTreeToTree(CordRep* tree, MethodIdentifier method);
875 void PrependTree(CordRep* tree, MethodIdentifier method);
876
877 bool IsSame(const InlineRep& other) const {
878 return memcmp(s1: &data_, s2: &other.data_, n: sizeof(data_)) == 0;
879 }
880 int BitwiseCompare(const InlineRep& other) const {
881 uint64_t x, y;
882 // Use memcpy to avoid aliasing issues.
883 memcpy(dest: &x, src: &data_, n: sizeof(x));
884 memcpy(dest: &y, src: &other.data_, n: sizeof(y));
885 if (x == y) {
886 memcpy(dest: &x, src: reinterpret_cast<const char*>(&data_) + 8, n: sizeof(x));
887 memcpy(dest: &y, src: reinterpret_cast<const char*>(&other.data_) + 8, n: sizeof(y));
888 if (x == y) return 0;
889 }
890 return absl::big_endian::FromHost64(x) < absl::big_endian::FromHost64(x: y)
891 ? -1
892 : 1;
893 }
894 void CopyTo(std::string* dst) const {
895 // memcpy is much faster when operating on a known size. On most supported
896 // platforms, the small string optimization is large enough that resizing
897 // to 15 bytes does not cause a memory allocation.
898 absl::strings_internal::STLStringResizeUninitialized(s: dst,
899 new_size: sizeof(data_) - 1);
900 memcpy(dest: &(*dst)[0], src: &data_, n: sizeof(data_) - 1);
901 // erase is faster than resize because the logic for memory allocation is
902 // not needed.
903 dst->erase(pos: inline_size());
904 }
905
906 // Copies the inline contents into `dst`. Assumes the cord is not empty.
907 void CopyToArray(char* dst) const;
908
909 bool is_tree() const { return data_.is_tree(); }
910
911 // Returns true if the Cord is being profiled by cordz.
912 bool is_profiled() const { return data_.is_tree() && data_.is_profiled(); }
913
914 // Returns the available inlined capacity, or 0 if is_tree() == true.
915 size_t remaining_inline_capacity() const {
916 return data_.is_tree() ? 0 : kMaxInline - data_.inline_size();
917 }
918
919 // Returns the profiled CordzInfo, or nullptr if not sampled.
920 absl::cord_internal::CordzInfo* cordz_info() const {
921 return data_.cordz_info();
922 }
923
924 // Sets the profiled CordzInfo. `cordz_info` must not be null.
925 void set_cordz_info(cord_internal::CordzInfo* cordz_info) {
926 assert(cordz_info != nullptr);
927 data_.set_cordz_info(cordz_info);
928 }
929
930 // Resets the current cordz_info to null / empty.
931 void clear_cordz_info() { data_.clear_cordz_info(); }
932
933 private:
934 friend class Cord;
935
936 void AssignSlow(const InlineRep& src);
937 // Unrefs the tree and stops profiling.
938 void UnrefTree();
939
940 void ResetToEmpty() { data_ = {}; }
941
942 void set_inline_size(size_t size) { data_.set_inline_size(size); }
943 size_t inline_size() const { return data_.inline_size(); }
944
945 cord_internal::InlineData data_;
946 };
947 InlineRep contents_;
948
949 // Helper for GetFlat() and TryFlat().
950 static bool GetFlatAux(absl::cord_internal::CordRep* rep,
951 absl::string_view* fragment);
952
953 // Helper for ForEachChunk().
954 static void ForEachChunkAux(
955 absl::cord_internal::CordRep* rep,
956 absl::FunctionRef<void(absl::string_view)> callback);
957
958 // The destructor for non-empty Cords.
959 void DestroyCordSlow();
960
961 // Out-of-line implementation of slower parts of logic.
962 void CopyToArraySlowPath(char* dst) const;
963 int CompareSlowPath(absl::string_view rhs, size_t compared_size,
964 size_t size_to_compare) const;
965 int CompareSlowPath(const Cord& rhs, size_t compared_size,
966 size_t size_to_compare) const;
967 bool EqualsImpl(absl::string_view rhs, size_t size_to_compare) const;
968 bool EqualsImpl(const Cord& rhs, size_t size_to_compare) const;
969 int CompareImpl(const Cord& rhs) const;
970
971 template <typename ResultType, typename RHS>
972 friend ResultType GenericCompare(const Cord& lhs, const RHS& rhs,
973 size_t size_to_compare);
974 static absl::string_view GetFirstChunk(const Cord& c);
975 static absl::string_view GetFirstChunk(absl::string_view sv);
976
977 // Returns a new reference to contents_.tree(), or steals an existing
978 // reference if called on an rvalue.
979 absl::cord_internal::CordRep* TakeRep() const&;
980 absl::cord_internal::CordRep* TakeRep() &&;
981
982 // Helper for Append().
983 template <typename C>
984 void AppendImpl(C&& src);
985
986 // Appends / Prepends `src` to this instance, using precise sizing.
987 // This method does explicitly not attempt to use any spare capacity
988 // in any pending last added private owned flat.
989 // Requires `src` to be <= kMaxFlatLength.
990 void AppendPrecise(absl::string_view src, MethodIdentifier method);
991 void PrependPrecise(absl::string_view src, MethodIdentifier method);
992
993 CordBuffer GetAppendBufferSlowPath(size_t block_size, size_t capacity,
994 size_t min_capacity);
995
996 // Prepends the provided data to this instance. `method` contains the public
997 // API method for this action which is tracked for Cordz sampling purposes.
998 void PrependArray(absl::string_view src, MethodIdentifier method);
999
1000 // Assigns the value in 'src' to this instance, 'stealing' its contents.
1001 // Requires src.length() > kMaxBytesToCopy.
1002 Cord& AssignLargeString(std::string&& src);
1003
1004 // Helper for AbslHashValue().
1005 template <typename H>
1006 H HashFragmented(H hash_state) const {
1007 typename H::AbslInternalPiecewiseCombiner combiner;
1008 ForEachChunk([&combiner, &hash_state](absl::string_view chunk) {
1009 hash_state = combiner.add_buffer(std::move(hash_state), chunk.data(),
1010 chunk.size());
1011 });
1012 return H::combine(combiner.finalize(std::move(hash_state)), size());
1013 }
1014};
1015
1016ABSL_NAMESPACE_END
1017} // namespace absl
1018
1019namespace absl {
1020ABSL_NAMESPACE_BEGIN
1021
1022// allow a Cord to be logged
1023extern std::ostream& operator<<(std::ostream& out, const Cord& cord);
1024
1025// ------------------------------------------------------------------
1026// Internal details follow. Clients should ignore.
1027
1028namespace cord_internal {
1029
1030// Fast implementation of memmove for up to 15 bytes. This implementation is
1031// safe for overlapping regions. If nullify_tail is true, the destination is
1032// padded with '\0' up to 16 bytes.
1033template <bool nullify_tail = false>
1034inline void SmallMemmove(char* dst, const char* src, size_t n) {
1035 if (n >= 8) {
1036 assert(n <= 16);
1037 uint64_t buf1;
1038 uint64_t buf2;
1039 memcpy(dest: &buf1, src: src, n: 8);
1040 memcpy(dest: &buf2, src: src + n - 8, n: 8);
1041 if (nullify_tail) {
1042 memset(s: dst + 8, c: 0, n: 8);
1043 }
1044 memcpy(dest: dst, src: &buf1, n: 8);
1045 memcpy(dest: dst + n - 8, src: &buf2, n: 8);
1046 } else if (n >= 4) {
1047 uint32_t buf1;
1048 uint32_t buf2;
1049 memcpy(dest: &buf1, src: src, n: 4);
1050 memcpy(dest: &buf2, src: src + n - 4, n: 4);
1051 if (nullify_tail) {
1052 memset(s: dst + 4, c: 0, n: 4);
1053 memset(s: dst + 8, c: 0, n: 8);
1054 }
1055 memcpy(dest: dst, src: &buf1, n: 4);
1056 memcpy(dest: dst + n - 4, src: &buf2, n: 4);
1057 } else {
1058 if (n != 0) {
1059 dst[0] = src[0];
1060 dst[n / 2] = src[n / 2];
1061 dst[n - 1] = src[n - 1];
1062 }
1063 if (nullify_tail) {
1064 memset(s: dst + 8, c: 0, n: 8);
1065 memset(s: dst + n, c: 0, n: 8);
1066 }
1067 }
1068}
1069
1070// Does non-template-specific `CordRepExternal` initialization.
1071// Requires `data` to be non-empty.
1072void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep);
1073
1074// Creates a new `CordRep` that owns `data` and `releaser` and returns a pointer
1075// to it. Requires `data` to be non-empty.
1076template <typename Releaser>
1077// NOLINTNEXTLINE - suppress clang-tidy raw pointer return.
1078CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) {
1079 assert(!data.empty());
1080 using ReleaserType = absl::decay_t<Releaser>;
1081 CordRepExternal* rep = new CordRepExternalImpl<ReleaserType>(
1082 std::forward<Releaser>(releaser), 0);
1083 InitializeCordRepExternal(data, rep);
1084 return rep;
1085}
1086
1087// Overload for function reference types that dispatches using a function
1088// pointer because there are no `alignof()` or `sizeof()` a function reference.
1089// NOLINTNEXTLINE - suppress clang-tidy raw pointer return.
1090inline CordRep* NewExternalRep(absl::string_view data,
1091 void (&releaser)(absl::string_view)) {
1092 return NewExternalRep(data, releaser: &releaser);
1093}
1094
1095} // namespace cord_internal
1096
1097template <typename Releaser>
1098Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser) {
1099 Cord cord;
1100 if (ABSL_PREDICT_TRUE(!data.empty())) {
1101 cord.contents_.EmplaceTree(::absl::cord_internal::NewExternalRep(
1102 data, std::forward<Releaser>(releaser)),
1103 Cord::MethodIdentifier::kMakeCordFromExternal);
1104 } else {
1105 using ReleaserType = absl::decay_t<Releaser>;
1106 cord_internal::InvokeReleaser(
1107 cord_internal::Rank0{}, ReleaserType(std::forward<Releaser>(releaser)),
1108 data);
1109 }
1110 return cord;
1111}
1112
1113constexpr Cord::InlineRep::InlineRep(cord_internal::InlineData data)
1114 : data_(data) {}
1115
1116inline Cord::InlineRep::InlineRep(const Cord::InlineRep& src)
1117 : data_(InlineData::kDefaultInit) {
1118 if (CordRep* tree = src.tree()) {
1119 EmplaceTree(rep: CordRep::Ref(rep: tree), parent: src.data_,
1120 method: CordzUpdateTracker::kConstructorCord);
1121 } else {
1122 data_ = src.data_;
1123 }
1124}
1125
1126inline Cord::InlineRep::InlineRep(Cord::InlineRep&& src) : data_(src.data_) {
1127 src.ResetToEmpty();
1128}
1129
1130inline Cord::InlineRep& Cord::InlineRep::operator=(const Cord::InlineRep& src) {
1131 if (this == &src) {
1132 return *this;
1133 }
1134 if (!is_tree() && !src.is_tree()) {
1135 data_ = src.data_;
1136 return *this;
1137 }
1138 AssignSlow(src);
1139 return *this;
1140}
1141
1142inline Cord::InlineRep& Cord::InlineRep::operator=(
1143 Cord::InlineRep&& src) noexcept {
1144 if (is_tree()) {
1145 UnrefTree();
1146 }
1147 data_ = src.data_;
1148 src.ResetToEmpty();
1149 return *this;
1150}
1151
1152inline void Cord::InlineRep::Swap(Cord::InlineRep* rhs) {
1153 if (rhs == this) {
1154 return;
1155 }
1156 std::swap(x&: data_, y&: rhs->data_);
1157}
1158
1159inline const char* Cord::InlineRep::data() const {
1160 return is_tree() ? nullptr : data_.as_chars();
1161}
1162
1163inline const char* Cord::InlineRep::as_chars() const {
1164 assert(!data_.is_tree());
1165 return data_.as_chars();
1166}
1167
1168inline absl::cord_internal::CordRep* Cord::InlineRep::as_tree() const {
1169 assert(data_.is_tree());
1170 return data_.as_tree();
1171}
1172
1173inline absl::cord_internal::CordRep* Cord::InlineRep::tree() const {
1174 if (is_tree()) {
1175 return as_tree();
1176 } else {
1177 return nullptr;
1178 }
1179}
1180
1181inline bool Cord::InlineRep::empty() const { return data_.is_empty(); }
1182
1183inline size_t Cord::InlineRep::size() const {
1184 return is_tree() ? as_tree()->length : inline_size();
1185}
1186
1187inline cord_internal::CordRepFlat* Cord::InlineRep::MakeFlatWithExtraCapacity(
1188 size_t extra) {
1189 static_assert(cord_internal::kMinFlatLength >= sizeof(data_), "");
1190 size_t len = data_.inline_size();
1191 auto* result = CordRepFlat::New(len: len + extra);
1192 result->length = len;
1193 memcpy(dest: result->Data(), src: data_.as_chars(), n: sizeof(data_));
1194 return result;
1195}
1196
1197inline void Cord::InlineRep::EmplaceTree(CordRep* rep,
1198 MethodIdentifier method) {
1199 assert(rep);
1200 data_.make_tree(rep);
1201 CordzInfo::MaybeTrackCord(cord&: data_, method);
1202}
1203
1204inline void Cord::InlineRep::EmplaceTree(CordRep* rep, const InlineData& parent,
1205 MethodIdentifier method) {
1206 data_.make_tree(rep);
1207 CordzInfo::MaybeTrackCord(cord&: data_, src: parent, method);
1208}
1209
1210inline void Cord::InlineRep::SetTree(CordRep* rep,
1211 const CordzUpdateScope& scope) {
1212 assert(rep);
1213 assert(data_.is_tree());
1214 data_.set_tree(rep);
1215 scope.SetCordRep(rep);
1216}
1217
1218inline void Cord::InlineRep::SetTreeOrEmpty(CordRep* rep,
1219 const CordzUpdateScope& scope) {
1220 assert(data_.is_tree());
1221 if (rep) {
1222 data_.set_tree(rep);
1223 } else {
1224 data_ = {};
1225 }
1226 scope.SetCordRep(rep);
1227}
1228
1229inline void Cord::InlineRep::CommitTree(const CordRep* old_rep, CordRep* rep,
1230 const CordzUpdateScope& scope,
1231 MethodIdentifier method) {
1232 if (old_rep) {
1233 SetTree(rep, scope);
1234 } else {
1235 EmplaceTree(rep, method);
1236 }
1237}
1238
1239inline absl::cord_internal::CordRep* Cord::InlineRep::clear() {
1240 if (is_tree()) {
1241 CordzInfo::MaybeUntrackCord(info: cordz_info());
1242 }
1243 absl::cord_internal::CordRep* result = tree();
1244 ResetToEmpty();
1245 return result;
1246}
1247
1248inline void Cord::InlineRep::CopyToArray(char* dst) const {
1249 assert(!is_tree());
1250 size_t n = inline_size();
1251 assert(n != 0);
1252 cord_internal::SmallMemmove(dst, src: data_.as_chars(), n);
1253}
1254
1255constexpr inline Cord::Cord() noexcept {}
1256
1257inline Cord::Cord(absl::string_view src)
1258 : Cord(src, CordzUpdateTracker::kConstructorString) {}
1259
1260template <typename T>
1261constexpr Cord::Cord(strings_internal::StringConstant<T>)
1262 : contents_(strings_internal::StringConstant<T>::value.size() <=
1263 cord_internal::kMaxInline
1264 ? cord_internal::InlineData(
1265 strings_internal::StringConstant<T>::value)
1266 : cord_internal::InlineData(
1267 &cord_internal::ConstInitExternalStorage<
1268 strings_internal::StringConstant<T>>::value)) {}
1269
1270inline Cord& Cord::operator=(const Cord& x) {
1271 contents_ = x.contents_;
1272 return *this;
1273}
1274
1275template <typename T, Cord::EnableIfString<T>>
1276Cord& Cord::operator=(T&& src) {
1277 if (src.size() <= cord_internal::kMaxBytesToCopy) {
1278 return operator=(src: absl::string_view(src));
1279 } else {
1280 return AssignLargeString(src: std::forward<T>(src));
1281 }
1282}
1283
1284inline Cord::Cord(const Cord& src) : contents_(src.contents_) {}
1285
1286inline Cord::Cord(Cord&& src) noexcept : contents_(std::move(src.contents_)) {}
1287
1288inline void Cord::swap(Cord& other) noexcept {
1289 contents_.Swap(rhs: &other.contents_);
1290}
1291
1292inline Cord& Cord::operator=(Cord&& x) noexcept {
1293 contents_ = std::move(x.contents_);
1294 return *this;
1295}
1296
1297extern template Cord::Cord(std::string&& src);
1298
1299inline size_t Cord::size() const {
1300 // Length is 1st field in str.rep_
1301 return contents_.size();
1302}
1303
1304inline bool Cord::empty() const { return contents_.empty(); }
1305
1306inline size_t Cord::EstimatedMemoryUsage(
1307 CordMemoryAccounting accounting_method) const {
1308 size_t result = sizeof(Cord);
1309 if (const absl::cord_internal::CordRep* rep = contents_.tree()) {
1310 if (accounting_method == CordMemoryAccounting::kFairShare) {
1311 result += cord_internal::GetEstimatedFairShareMemoryUsage(rep);
1312 } else {
1313 result += cord_internal::GetEstimatedMemoryUsage(rep);
1314 }
1315 }
1316 return result;
1317}
1318
1319inline absl::optional<absl::string_view> Cord::TryFlat() const {
1320 absl::cord_internal::CordRep* rep = contents_.tree();
1321 if (rep == nullptr) {
1322 return absl::string_view(contents_.data(), contents_.size());
1323 }
1324 absl::string_view fragment;
1325 if (GetFlatAux(rep, fragment: &fragment)) {
1326 return fragment;
1327 }
1328 return absl::nullopt;
1329}
1330
1331inline absl::string_view Cord::Flatten() {
1332 absl::cord_internal::CordRep* rep = contents_.tree();
1333 if (rep == nullptr) {
1334 return absl::string_view(contents_.data(), contents_.size());
1335 } else {
1336 absl::string_view already_flat_contents;
1337 if (GetFlatAux(rep, fragment: &already_flat_contents)) {
1338 return already_flat_contents;
1339 }
1340 }
1341 return FlattenSlowPath();
1342}
1343
1344inline void Cord::Append(absl::string_view src) {
1345 contents_.AppendArray(src, method: CordzUpdateTracker::kAppendString);
1346}
1347
1348inline void Cord::Prepend(absl::string_view src) {
1349 PrependArray(src, method: CordzUpdateTracker::kPrependString);
1350}
1351
1352inline void Cord::Append(CordBuffer buffer) {
1353 if (ABSL_PREDICT_FALSE(buffer.length() == 0)) return;
1354 absl::string_view short_value;
1355 if (CordRep* rep = buffer.ConsumeValue(short_value)) {
1356 contents_.AppendTree(tree: rep, method: CordzUpdateTracker::kAppendCordBuffer);
1357 } else {
1358 AppendPrecise(src: short_value, method: CordzUpdateTracker::kAppendCordBuffer);
1359 }
1360}
1361
1362inline void Cord::Prepend(CordBuffer buffer) {
1363 if (ABSL_PREDICT_FALSE(buffer.length() == 0)) return;
1364 absl::string_view short_value;
1365 if (CordRep* rep = buffer.ConsumeValue(short_value)) {
1366 contents_.PrependTree(tree: rep, method: CordzUpdateTracker::kPrependCordBuffer);
1367 } else {
1368 PrependPrecise(src: short_value, method: CordzUpdateTracker::kPrependCordBuffer);
1369 }
1370}
1371
1372inline CordBuffer Cord::GetAppendBuffer(size_t capacity, size_t min_capacity) {
1373 if (empty()) return CordBuffer::CreateWithDefaultLimit(capacity);
1374 return GetAppendBufferSlowPath(block_size: 0, capacity, min_capacity);
1375}
1376
1377inline CordBuffer Cord::GetCustomAppendBuffer(size_t block_size,
1378 size_t capacity,
1379 size_t min_capacity) {
1380 if (empty()) {
1381 return block_size ? CordBuffer::CreateWithCustomLimit(block_size, capacity)
1382 : CordBuffer::CreateWithDefaultLimit(capacity);
1383 }
1384 return GetAppendBufferSlowPath(block_size, capacity, min_capacity);
1385}
1386
1387extern template void Cord::Append(std::string&& src);
1388extern template void Cord::Prepend(std::string&& src);
1389
1390inline int Cord::Compare(const Cord& rhs) const {
1391 if (!contents_.is_tree() && !rhs.contents_.is_tree()) {
1392 return contents_.BitwiseCompare(other: rhs.contents_);
1393 }
1394
1395 return CompareImpl(rhs);
1396}
1397
1398// Does 'this' cord start/end with rhs
1399inline bool Cord::StartsWith(const Cord& rhs) const {
1400 if (contents_.IsSame(other: rhs.contents_)) return true;
1401 size_t rhs_size = rhs.size();
1402 if (size() < rhs_size) return false;
1403 return EqualsImpl(rhs, size_to_compare: rhs_size);
1404}
1405
1406inline bool Cord::StartsWith(absl::string_view rhs) const {
1407 size_t rhs_size = rhs.size();
1408 if (size() < rhs_size) return false;
1409 return EqualsImpl(rhs, size_to_compare: rhs_size);
1410}
1411
1412inline void Cord::ChunkIterator::InitTree(cord_internal::CordRep* tree) {
1413 tree = cord_internal::SkipCrcNode(rep: tree);
1414 if (tree->tag == cord_internal::BTREE) {
1415 current_chunk_ = btree_reader_.Init(tree: tree->btree());
1416 } else {
1417 current_leaf_ = tree;
1418 current_chunk_ = cord_internal::EdgeData(edge: tree);
1419 }
1420}
1421
1422inline Cord::ChunkIterator::ChunkIterator(cord_internal::CordRep* tree) {
1423 bytes_remaining_ = tree->length;
1424 InitTree(tree);
1425}
1426
1427inline Cord::ChunkIterator::ChunkIterator(const Cord* cord) {
1428 if (CordRep* tree = cord->contents_.tree()) {
1429 bytes_remaining_ = tree->length;
1430 InitTree(tree);
1431 } else {
1432 bytes_remaining_ = cord->contents_.inline_size();
1433 current_chunk_ = {cord->contents_.data(), bytes_remaining_};
1434 }
1435}
1436
1437inline Cord::ChunkIterator& Cord::ChunkIterator::AdvanceBtree() {
1438 current_chunk_ = btree_reader_.Next();
1439 return *this;
1440}
1441
1442inline void Cord::ChunkIterator::AdvanceBytesBtree(size_t n) {
1443 assert(n >= current_chunk_.size());
1444 bytes_remaining_ -= n;
1445 if (bytes_remaining_) {
1446 if (n == current_chunk_.size()) {
1447 current_chunk_ = btree_reader_.Next();
1448 } else {
1449 size_t offset = btree_reader_.length() - bytes_remaining_;
1450 current_chunk_ = btree_reader_.Seek(offset);
1451 }
1452 } else {
1453 current_chunk_ = {};
1454 }
1455}
1456
1457inline Cord::ChunkIterator& Cord::ChunkIterator::operator++() {
1458 ABSL_HARDENING_ASSERT(bytes_remaining_ > 0 &&
1459 "Attempted to iterate past `end()`");
1460 assert(bytes_remaining_ >= current_chunk_.size());
1461 bytes_remaining_ -= current_chunk_.size();
1462 if (bytes_remaining_ > 0) {
1463 if (btree_reader_) {
1464 return AdvanceBtree();
1465 } else {
1466 assert(!current_chunk_.empty()); // Called on invalid iterator.
1467 }
1468 current_chunk_ = {};
1469 }
1470 return *this;
1471}
1472
1473inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) {
1474 ChunkIterator tmp(*this);
1475 operator++();
1476 return tmp;
1477}
1478
1479inline bool Cord::ChunkIterator::operator==(const ChunkIterator& other) const {
1480 return bytes_remaining_ == other.bytes_remaining_;
1481}
1482
1483inline bool Cord::ChunkIterator::operator!=(const ChunkIterator& other) const {
1484 return !(*this == other);
1485}
1486
1487inline Cord::ChunkIterator::reference Cord::ChunkIterator::operator*() const {
1488 ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
1489 return current_chunk_;
1490}
1491
1492inline Cord::ChunkIterator::pointer Cord::ChunkIterator::operator->() const {
1493 ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
1494 return &current_chunk_;
1495}
1496
1497inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) {
1498 assert(n < current_chunk_.size());
1499 current_chunk_.remove_prefix(n);
1500 bytes_remaining_ -= n;
1501}
1502
1503inline void Cord::ChunkIterator::AdvanceBytes(size_t n) {
1504 assert(bytes_remaining_ >= n);
1505 if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) {
1506 RemoveChunkPrefix(n);
1507 } else if (n != 0) {
1508 if (btree_reader_) {
1509 AdvanceBytesBtree(n);
1510 } else {
1511 bytes_remaining_ = 0;
1512 }
1513 }
1514}
1515
1516inline Cord::ChunkIterator Cord::chunk_begin() const {
1517 return ChunkIterator(this);
1518}
1519
1520inline Cord::ChunkIterator Cord::chunk_end() const { return ChunkIterator(); }
1521
1522inline Cord::ChunkIterator Cord::ChunkRange::begin() const {
1523 return cord_->chunk_begin();
1524}
1525
1526inline Cord::ChunkIterator Cord::ChunkRange::end() const {
1527 return cord_->chunk_end();
1528}
1529
1530inline Cord::ChunkRange Cord::Chunks() const { return ChunkRange(this); }
1531
1532inline Cord::CharIterator& Cord::CharIterator::operator++() {
1533 if (ABSL_PREDICT_TRUE(chunk_iterator_->size() > 1)) {
1534 chunk_iterator_.RemoveChunkPrefix(n: 1);
1535 } else {
1536 ++chunk_iterator_;
1537 }
1538 return *this;
1539}
1540
1541inline Cord::CharIterator Cord::CharIterator::operator++(int) {
1542 CharIterator tmp(*this);
1543 operator++();
1544 return tmp;
1545}
1546
1547inline bool Cord::CharIterator::operator==(const CharIterator& other) const {
1548 return chunk_iterator_ == other.chunk_iterator_;
1549}
1550
1551inline bool Cord::CharIterator::operator!=(const CharIterator& other) const {
1552 return !(*this == other);
1553}
1554
1555inline Cord::CharIterator::reference Cord::CharIterator::operator*() const {
1556 return *chunk_iterator_->data();
1557}
1558
1559inline Cord::CharIterator::pointer Cord::CharIterator::operator->() const {
1560 return chunk_iterator_->data();
1561}
1562
1563inline Cord Cord::AdvanceAndRead(CharIterator* it, size_t n_bytes) {
1564 assert(it != nullptr);
1565 return it->chunk_iterator_.AdvanceAndReadBytes(n: n_bytes);
1566}
1567
1568inline void Cord::Advance(CharIterator* it, size_t n_bytes) {
1569 assert(it != nullptr);
1570 it->chunk_iterator_.AdvanceBytes(n: n_bytes);
1571}
1572
1573inline absl::string_view Cord::ChunkRemaining(const CharIterator& it) {
1574 return *it.chunk_iterator_;
1575}
1576
1577inline Cord::CharIterator Cord::char_begin() const {
1578 return CharIterator(this);
1579}
1580
1581inline Cord::CharIterator Cord::char_end() const { return CharIterator(); }
1582
1583inline Cord::CharIterator Cord::CharRange::begin() const {
1584 return cord_->char_begin();
1585}
1586
1587inline Cord::CharIterator Cord::CharRange::end() const {
1588 return cord_->char_end();
1589}
1590
1591inline Cord::CharRange Cord::Chars() const { return CharRange(this); }
1592
1593inline void Cord::ForEachChunk(
1594 absl::FunctionRef<void(absl::string_view)> callback) const {
1595 absl::cord_internal::CordRep* rep = contents_.tree();
1596 if (rep == nullptr) {
1597 callback(absl::string_view(contents_.data(), contents_.size()));
1598 } else {
1599 return ForEachChunkAux(rep, callback);
1600 }
1601}
1602
1603// Nonmember Cord-to-Cord relational operators.
1604inline bool operator==(const Cord& lhs, const Cord& rhs) {
1605 if (lhs.contents_.IsSame(other: rhs.contents_)) return true;
1606 size_t rhs_size = rhs.size();
1607 if (lhs.size() != rhs_size) return false;
1608 return lhs.EqualsImpl(rhs, size_to_compare: rhs_size);
1609}
1610
1611inline bool operator!=(const Cord& x, const Cord& y) { return !(x == y); }
1612inline bool operator<(const Cord& x, const Cord& y) { return x.Compare(rhs: y) < 0; }
1613inline bool operator>(const Cord& x, const Cord& y) { return x.Compare(rhs: y) > 0; }
1614inline bool operator<=(const Cord& x, const Cord& y) {
1615 return x.Compare(rhs: y) <= 0;
1616}
1617inline bool operator>=(const Cord& x, const Cord& y) {
1618 return x.Compare(rhs: y) >= 0;
1619}
1620
1621// Nonmember Cord-to-absl::string_view relational operators.
1622//
1623// Due to implicit conversions, these also enable comparisons of Cord with
1624// with std::string, ::string, and const char*.
1625inline bool operator==(const Cord& lhs, absl::string_view rhs) {
1626 size_t lhs_size = lhs.size();
1627 size_t rhs_size = rhs.size();
1628 if (lhs_size != rhs_size) return false;
1629 return lhs.EqualsImpl(rhs, size_to_compare: rhs_size);
1630}
1631
1632inline bool operator==(absl::string_view x, const Cord& y) { return y == x; }
1633inline bool operator!=(const Cord& x, absl::string_view y) { return !(x == y); }
1634inline bool operator!=(absl::string_view x, const Cord& y) { return !(x == y); }
1635inline bool operator<(const Cord& x, absl::string_view y) {
1636 return x.Compare(rhs: y) < 0;
1637}
1638inline bool operator<(absl::string_view x, const Cord& y) {
1639 return y.Compare(rhs: x) > 0;
1640}
1641inline bool operator>(const Cord& x, absl::string_view y) { return y < x; }
1642inline bool operator>(absl::string_view x, const Cord& y) { return y < x; }
1643inline bool operator<=(const Cord& x, absl::string_view y) { return !(y < x); }
1644inline bool operator<=(absl::string_view x, const Cord& y) { return !(y < x); }
1645inline bool operator>=(const Cord& x, absl::string_view y) { return !(x < y); }
1646inline bool operator>=(absl::string_view x, const Cord& y) { return !(x < y); }
1647
1648// Some internals exposed to test code.
1649namespace strings_internal {
1650class CordTestAccess {
1651 public:
1652 static size_t FlatOverhead();
1653 static size_t MaxFlatLength();
1654 static size_t SizeofCordRepExternal();
1655 static size_t SizeofCordRepSubstring();
1656 static size_t FlatTagToLength(uint8_t tag);
1657 static uint8_t LengthToTag(size_t s);
1658};
1659} // namespace strings_internal
1660ABSL_NAMESPACE_END
1661} // namespace absl
1662
1663#endif // ABSL_STRINGS_CORD_H_
1664

source code of flutter_engine/third_party/abseil-cpp/absl/strings/cord.h