xref: /aosp_15_r20/external/openscreen/third_party/abseil/src/absl/strings/cord.h (revision 3f982cf4871df8771c9d4abe6e9a6f8d829b2736)
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 accomodate 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/internal/endian.h"
74 #include "absl/base/internal/per_thread_tls.h"
75 #include "absl/base/macros.h"
76 #include "absl/base/port.h"
77 #include "absl/container/inlined_vector.h"
78 #include "absl/functional/function_ref.h"
79 #include "absl/meta/type_traits.h"
80 #include "absl/strings/internal/cord_internal.h"
81 #include "absl/strings/internal/resize_uninitialized.h"
82 #include "absl/strings/internal/string_constant.h"
83 #include "absl/strings/string_view.h"
84 #include "absl/types/optional.h"
85 
86 namespace absl {
87 ABSL_NAMESPACE_BEGIN
88 class Cord;
89 class CordTestPeer;
90 template <typename Releaser>
91 Cord MakeCordFromExternal(absl::string_view, Releaser&&);
92 void CopyCordToString(const Cord& src, std::string* dst);
93 
94 // Cord
95 //
96 // A Cord is a sequence of characters, designed to be more efficient than a
97 // `std::string` in certain circumstances: namely, large string data that needs
98 // to change over its lifetime or shared, especially when such data is shared
99 // across API boundaries.
100 //
101 // A Cord stores its character data in a structure that allows efficient prepend
102 // and append operations. This makes a Cord useful for large string data sent
103 // over in a wire format that may need to be prepended or appended at some point
104 // during the data exchange (e.g. HTTP, protocol buffers). For example, a
105 // Cord is useful for storing an HTTP request, and prepending an HTTP header to
106 // such a request.
107 //
108 // Cords should not be used for storing general string data, however. They
109 // require overhead to construct and are slower than strings for random access.
110 //
111 // The Cord API provides the following common API operations:
112 //
113 // * Create or assign Cords out of existing string data, memory, or other Cords
114 // * Append and prepend data to an existing Cord
115 // * Create new Sub-Cords from existing Cord data
116 // * Swap Cord data and compare Cord equality
117 // * Write out Cord data by constructing a `std::string`
118 //
119 // Additionally, the API provides iterator utilities to iterate through Cord
120 // data via chunks or character bytes.
121 //
122 class Cord {
123  private:
124   template <typename T>
125   using EnableIfString =
126       absl::enable_if_t<std::is_same<T, std::string>::value, int>;
127 
128  public:
129   // Cord::Cord() Constructors.
130 
131   // Creates an empty Cord.
132   constexpr Cord() noexcept;
133 
134   // Creates a Cord from an existing Cord. Cord is copyable and efficiently
135   // movable. The moved-from state is valid but unspecified.
136   Cord(const Cord& src);
137   Cord(Cord&& src) noexcept;
138   Cord& operator=(const Cord& x);
139   Cord& operator=(Cord&& x) noexcept;
140 
141   // Creates a Cord from a `src` string. This constructor is marked explicit to
142   // prevent implicit Cord constructions from arguments convertible to an
143   // `absl::string_view`.
144   explicit Cord(absl::string_view src);
145   Cord& operator=(absl::string_view src);
146 
147   // Creates a Cord from a `std::string&&` rvalue. These constructors are
148   // templated to avoid ambiguities for types that are convertible to both
149   // `absl::string_view` and `std::string`, such as `const char*`.
150   template <typename T, EnableIfString<T> = 0>
151   explicit Cord(T&& src);
152   template <typename T, EnableIfString<T> = 0>
153   Cord& operator=(T&& src);
154 
155   // Cord::~Cord()
156   //
157   // Destructs the Cord.
~Cord()158   ~Cord() {
159     if (contents_.is_tree()) DestroyCordSlow();
160   }
161 
162   // MakeCordFromExternal()
163   //
164   // Creates a Cord that takes ownership of external string memory. The
165   // contents of `data` are not copied to the Cord; instead, the external
166   // memory is added to the Cord and reference-counted. This data may not be
167   // changed for the life of the Cord, though it may be prepended or appended
168   // to.
169   //
170   // `MakeCordFromExternal()` takes a callable "releaser" that is invoked when
171   // the reference count for `data` reaches zero. As noted above, this data must
172   // remain live until the releaser is invoked. The callable releaser also must:
173   //
174   //   * be move constructible
175   //   * support `void operator()(absl::string_view) const` or `void operator()`
176   //
177   // Example:
178   //
179   // Cord MakeCord(BlockPool* pool) {
180   //   Block* block = pool->NewBlock();
181   //   FillBlock(block);
182   //   return absl::MakeCordFromExternal(
183   //       block->ToStringView(),
184   //       [pool, block](absl::string_view v) {
185   //         pool->FreeBlock(block, v);
186   //       });
187   // }
188   //
189   // WARNING: Because a Cord can be reference-counted, it's likely a bug if your
190   // releaser doesn't do anything. For example, consider the following:
191   //
192   // void Foo(const char* buffer, int len) {
193   //   auto c = absl::MakeCordFromExternal(absl::string_view(buffer, len),
194   //                                       [](absl::string_view) {});
195   //
196   //   // BUG: If Bar() copies its cord for any reason, including keeping a
197   //   // substring of it, the lifetime of buffer might be extended beyond
198   //   // when Foo() returns.
199   //   Bar(c);
200   // }
201   template <typename Releaser>
202   friend Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser);
203 
204   // Cord::Clear()
205   //
206   // Releases the Cord data. Any nodes that share data with other Cords, if
207   // applicable, will have their reference counts reduced by 1.
208   void Clear();
209 
210   // Cord::Append()
211   //
212   // Appends data to the Cord, which may come from another Cord or other string
213   // data.
214   void Append(const Cord& src);
215   void Append(Cord&& src);
216   void Append(absl::string_view src);
217   template <typename T, EnableIfString<T> = 0>
218   void Append(T&& src);
219 
220   // Cord::Prepend()
221   //
222   // Prepends data to the Cord, which may come from another Cord or other string
223   // data.
224   void Prepend(const Cord& src);
225   void Prepend(absl::string_view src);
226   template <typename T, EnableIfString<T> = 0>
227   void Prepend(T&& src);
228 
229   // Cord::RemovePrefix()
230   //
231   // Removes the first `n` bytes of a Cord.
232   void RemovePrefix(size_t n);
233   void RemoveSuffix(size_t n);
234 
235   // Cord::Subcord()
236   //
237   // Returns a new Cord representing the subrange [pos, pos + new_size) of
238   // *this. If pos >= size(), the result is empty(). If
239   // (pos + new_size) >= size(), the result is the subrange [pos, size()).
240   Cord Subcord(size_t pos, size_t new_size) const;
241 
242   // Cord::swap()
243   //
244   // Swaps the contents of the Cord with `other`.
245   void swap(Cord& other) noexcept;
246 
247   // swap()
248   //
249   // Swaps the contents of two Cords.
swap(Cord & x,Cord & y)250   friend void swap(Cord& x, Cord& y) noexcept {
251     x.swap(y);
252   }
253 
254   // Cord::size()
255   //
256   // Returns the size of the Cord.
257   size_t size() const;
258 
259   // Cord::empty()
260   //
261   // Determines whether the given Cord is empty, returning `true` is so.
262   bool empty() const;
263 
264   // Cord::EstimatedMemoryUsage()
265   //
266   // Returns the *approximate* number of bytes held in full or in part by this
267   // Cord (which may not remain the same between invocations).  Note that Cords
268   // that share memory could each be "charged" independently for the same shared
269   // memory.
270   size_t EstimatedMemoryUsage() const;
271 
272   // Cord::Compare()
273   //
274   // Compares 'this' Cord with rhs. This function and its relatives treat Cords
275   // as sequences of unsigned bytes. The comparison is a straightforward
276   // lexicographic comparison. `Cord::Compare()` returns values as follows:
277   //
278   //   -1  'this' Cord is smaller
279   //    0  two Cords are equal
280   //    1  'this' Cord is larger
281   int Compare(absl::string_view rhs) const;
282   int Compare(const Cord& rhs) const;
283 
284   // Cord::StartsWith()
285   //
286   // Determines whether the Cord starts with the passed string data `rhs`.
287   bool StartsWith(const Cord& rhs) const;
288   bool StartsWith(absl::string_view rhs) const;
289 
290   // Cord::EndsWidth()
291   //
292   // Determines whether the Cord ends with the passed string data `rhs`.
293   bool EndsWith(absl::string_view rhs) const;
294   bool EndsWith(const Cord& rhs) const;
295 
296   // Cord::operator std::string()
297   //
298   // Converts a Cord into a `std::string()`. This operator is marked explicit to
299   // prevent unintended Cord usage in functions that take a string.
300   explicit operator std::string() const;
301 
302   // CopyCordToString()
303   //
304   // Copies the contents of a `src` Cord into a `*dst` string.
305   //
306   // This function optimizes the case of reusing the destination string since it
307   // can reuse previously allocated capacity. However, this function does not
308   // guarantee that pointers previously returned by `dst->data()` remain valid
309   // even if `*dst` had enough capacity to hold `src`. If `*dst` is a new
310   // object, prefer to simply use the conversion operator to `std::string`.
311   friend void CopyCordToString(const Cord& src, std::string* dst);
312 
313   class CharIterator;
314 
315   //----------------------------------------------------------------------------
316   // Cord::ChunkIterator
317   //----------------------------------------------------------------------------
318   //
319   // A `Cord::ChunkIterator` allows iteration over the constituent chunks of its
320   // Cord. Such iteration allows you to perform non-const operatons on the data
321   // of a Cord without modifying it.
322   //
323   // Generally, you do not instantiate a `Cord::ChunkIterator` directly;
324   // instead, you create one implicitly through use of the `Cord::Chunks()`
325   // member function.
326   //
327   // The `Cord::ChunkIterator` has the following properties:
328   //
329   //   * The iterator is invalidated after any non-const operation on the
330   //     Cord object over which it iterates.
331   //   * The `string_view` returned by dereferencing a valid, non-`end()`
332   //     iterator is guaranteed to be non-empty.
333   //   * Two `ChunkIterator` objects can be compared equal if and only if they
334   //     remain valid and iterate over the same Cord.
335   //   * The iterator in this case is a proxy iterator; the `string_view`
336   //     returned by the iterator does not live inside the Cord, and its
337   //     lifetime is limited to the lifetime of the iterator itself. To help
338   //     prevent lifetime issues, `ChunkIterator::reference` is not a true
339   //     reference type and is equivalent to `value_type`.
340   //   * The iterator keeps state that can grow for Cords that contain many
341   //     nodes and are imbalanced due to sharing. Prefer to pass this type by
342   //     const reference instead of by value.
343   class ChunkIterator {
344    public:
345     using iterator_category = std::input_iterator_tag;
346     using value_type = absl::string_view;
347     using difference_type = ptrdiff_t;
348     using pointer = const value_type*;
349     using reference = value_type;
350 
351     ChunkIterator() = default;
352 
353     ChunkIterator& operator++();
354     ChunkIterator operator++(int);
355     bool operator==(const ChunkIterator& other) const;
356     bool operator!=(const ChunkIterator& other) const;
357     reference operator*() const;
358     pointer operator->() const;
359 
360     friend class Cord;
361     friend class CharIterator;
362 
363    private:
364     // Constructs a `begin()` iterator from `cord`.
365     explicit ChunkIterator(const Cord* cord);
366 
367     // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
368     // `current_chunk_.size()`.
369     void RemoveChunkPrefix(size_t n);
370     Cord AdvanceAndReadBytes(size_t n);
371     void AdvanceBytes(size_t n);
372     // Iterates `n` bytes, where `n` is expected to be greater than or equal to
373     // `current_chunk_.size()`.
374     void AdvanceBytesSlowPath(size_t n);
375 
376     // A view into bytes of the current `CordRep`. It may only be a view to a
377     // suffix of bytes if this is being used by `CharIterator`.
378     absl::string_view current_chunk_;
379     // The current leaf, or `nullptr` if the iterator points to short data.
380     // If the current chunk is a substring node, current_leaf_ points to the
381     // underlying flat or external node.
382     absl::cord_internal::CordRep* current_leaf_ = nullptr;
383     // The number of bytes left in the `Cord` over which we are iterating.
384     size_t bytes_remaining_ = 0;
385     absl::InlinedVector<absl::cord_internal::CordRep*, 4>
386         stack_of_right_children_;
387   };
388 
389   // Cord::ChunkIterator::chunk_begin()
390   //
391   // Returns an iterator to the first chunk of the `Cord`.
392   //
393   // Generally, prefer using `Cord::Chunks()` within a range-based for loop for
394   // iterating over the chunks of a Cord. This method may be useful for getting
395   // a `ChunkIterator` where range-based for-loops are not useful.
396   //
397   // Example:
398   //
399   //   absl::Cord::ChunkIterator FindAsChunk(const absl::Cord& c,
400   //                                         absl::string_view s) {
401   //     return std::find(c.chunk_begin(), c.chunk_end(), s);
402   //   }
403   ChunkIterator chunk_begin() const;
404 
405   // Cord::ChunkItertator::chunk_end()
406   //
407   // Returns an iterator one increment past the last chunk of the `Cord`.
408   //
409   // Generally, prefer using `Cord::Chunks()` within a range-based for loop for
410   // iterating over the chunks of a Cord. This method may be useful for getting
411   // a `ChunkIterator` where range-based for-loops may not be available.
412   ChunkIterator chunk_end() const;
413 
414   //----------------------------------------------------------------------------
415   // Cord::ChunkIterator::ChunkRange
416   //----------------------------------------------------------------------------
417   //
418   // `ChunkRange` is a helper class for iterating over the chunks of the `Cord`,
419   // producing an iterator which can be used within a range-based for loop.
420   // Construction of a `ChunkRange` will return an iterator pointing to the
421   // first chunk of the Cord. Generally, do not construct a `ChunkRange`
422   // directly; instead, prefer to use the `Cord::Chunks()` method.
423   //
424   // Implementation note: `ChunkRange` is simply a convenience wrapper over
425   // `Cord::chunk_begin()` and `Cord::chunk_end()`.
426   class ChunkRange {
427    public:
ChunkRange(const Cord * cord)428     explicit ChunkRange(const Cord* cord) : cord_(cord) {}
429 
430     ChunkIterator begin() const;
431     ChunkIterator end() const;
432 
433    private:
434     const Cord* cord_;
435   };
436 
437   // Cord::Chunks()
438   //
439   // Returns a `Cord::ChunkIterator::ChunkRange` for iterating over the chunks
440   // of a `Cord` with a range-based for-loop. For most iteration tasks on a
441   // Cord, use `Cord::Chunks()` to retrieve this iterator.
442   //
443   // Example:
444   //
445   //   void ProcessChunks(const Cord& cord) {
446   //     for (absl::string_view chunk : cord.Chunks()) { ... }
447   //   }
448   //
449   // Note that the ordinary caveats of temporary lifetime extension apply:
450   //
451   //   void Process() {
452   //     for (absl::string_view chunk : CordFactory().Chunks()) {
453   //       // The temporary Cord returned by CordFactory has been destroyed!
454   //     }
455   //   }
456   ChunkRange Chunks() const;
457 
458   //----------------------------------------------------------------------------
459   // Cord::CharIterator
460   //----------------------------------------------------------------------------
461   //
462   // A `Cord::CharIterator` allows iteration over the constituent characters of
463   // a `Cord`.
464   //
465   // Generally, you do not instantiate a `Cord::CharIterator` directly; instead,
466   // you create one implicitly through use of the `Cord::Chars()` member
467   // function.
468   //
469   // A `Cord::CharIterator` has the following properties:
470   //
471   //   * The iterator is invalidated after any non-const operation on the
472   //     Cord object over which it iterates.
473   //   * Two `CharIterator` objects can be compared equal if and only if they
474   //     remain valid and iterate over the same Cord.
475   //   * The iterator keeps state that can grow for Cords that contain many
476   //     nodes and are imbalanced due to sharing. Prefer to pass this type by
477   //     const reference instead of by value.
478   //   * This type cannot act as a forward iterator because a `Cord` can reuse
479   //     sections of memory. This fact violates the requirement for forward
480   //     iterators to compare equal if dereferencing them returns the same
481   //     object.
482   class CharIterator {
483    public:
484     using iterator_category = std::input_iterator_tag;
485     using value_type = char;
486     using difference_type = ptrdiff_t;
487     using pointer = const char*;
488     using reference = const char&;
489 
490     CharIterator() = default;
491 
492     CharIterator& operator++();
493     CharIterator operator++(int);
494     bool operator==(const CharIterator& other) const;
495     bool operator!=(const CharIterator& other) const;
496     reference operator*() const;
497     pointer operator->() const;
498 
499     friend Cord;
500 
501    private:
CharIterator(const Cord * cord)502     explicit CharIterator(const Cord* cord) : chunk_iterator_(cord) {}
503 
504     ChunkIterator chunk_iterator_;
505   };
506 
507   // Cord::CharIterator::AdvanceAndRead()
508   //
509   // Advances the `Cord::CharIterator` by `n_bytes` and returns the bytes
510   // advanced as a separate `Cord`. `n_bytes` must be less than or equal to the
511   // number of bytes within the Cord; otherwise, behavior is undefined. It is
512   // valid to pass `char_end()` and `0`.
513   static Cord AdvanceAndRead(CharIterator* it, size_t n_bytes);
514 
515   // Cord::CharIterator::Advance()
516   //
517   // Advances the `Cord::CharIterator` by `n_bytes`. `n_bytes` must be less than
518   // or equal to the number of bytes remaining within the Cord; otherwise,
519   // behavior is undefined. It is valid to pass `char_end()` and `0`.
520   static void Advance(CharIterator* it, size_t n_bytes);
521 
522   // Cord::CharIterator::ChunkRemaining()
523   //
524   // Returns the longest contiguous view starting at the iterator's position.
525   //
526   // `it` must be dereferenceable.
527   static absl::string_view ChunkRemaining(const CharIterator& it);
528 
529   // Cord::CharIterator::char_begin()
530   //
531   // Returns an iterator to the first character of the `Cord`.
532   //
533   // Generally, prefer using `Cord::Chars()` within a range-based for loop for
534   // iterating over the chunks of a Cord. This method may be useful for getting
535   // a `CharIterator` where range-based for-loops may not be available.
536   CharIterator char_begin() const;
537 
538   // Cord::CharIterator::char_end()
539   //
540   // Returns an iterator to one past the last character of the `Cord`.
541   //
542   // Generally, prefer using `Cord::Chars()` within a range-based for loop for
543   // iterating over the chunks of a Cord. This method may be useful for getting
544   // a `CharIterator` where range-based for-loops are not useful.
545   CharIterator char_end() const;
546 
547   // Cord::CharIterator::CharRange
548   //
549   // `CharRange` is a helper class for iterating over the characters of a
550   // producing an iterator which can be used within a range-based for loop.
551   // Construction of a `CharRange` will return an iterator pointing to the first
552   // character of the Cord. Generally, do not construct a `CharRange` directly;
553   // instead, prefer to use the `Cord::Chars()` method show below.
554   //
555   // Implementation note: `CharRange` is simply a convenience wrapper over
556   // `Cord::char_begin()` and `Cord::char_end()`.
557   class CharRange {
558    public:
CharRange(const Cord * cord)559     explicit CharRange(const Cord* cord) : cord_(cord) {}
560 
561     CharIterator begin() const;
562     CharIterator end() const;
563 
564    private:
565     const Cord* cord_;
566   };
567 
568   // Cord::CharIterator::Chars()
569   //
570   // Returns a `Cord::CharIterator` for iterating over the characters of a
571   // `Cord` with a range-based for-loop. For most character-based iteration
572   // tasks on a Cord, use `Cord::Chars()` to retrieve this iterator.
573   //
574   // Example:
575   //
576   //   void ProcessCord(const Cord& cord) {
577   //     for (char c : cord.Chars()) { ... }
578   //   }
579   //
580   // Note that the ordinary caveats of temporary lifetime extension apply:
581   //
582   //   void Process() {
583   //     for (char c : CordFactory().Chars()) {
584   //       // The temporary Cord returned by CordFactory has been destroyed!
585   //     }
586   //   }
587   CharRange Chars() const;
588 
589   // Cord::operator[]
590   //
591   // Gets the "i"th character of the Cord and returns it, provided that
592   // 0 <= i < Cord.size().
593   //
594   // NOTE: This routine is reasonably efficient. It is roughly
595   // logarithmic based on the number of chunks that make up the cord. Still,
596   // if you need to iterate over the contents of a cord, you should
597   // use a CharIterator/ChunkIterator rather than call operator[] or Get()
598   // repeatedly in a loop.
599   char operator[](size_t i) const;
600 
601   // Cord::TryFlat()
602   //
603   // If this cord's representation is a single flat array, returns a
604   // string_view referencing that array.  Otherwise returns nullopt.
605   absl::optional<absl::string_view> TryFlat() const;
606 
607   // Cord::Flatten()
608   //
609   // Flattens the cord into a single array and returns a view of the data.
610   //
611   // If the cord was already flat, the contents are not modified.
612   absl::string_view Flatten();
613 
614   // Supports absl::Cord as a sink object for absl::Format().
AbslFormatFlush(absl::Cord * cord,absl::string_view part)615   friend void AbslFormatFlush(absl::Cord* cord, absl::string_view part) {
616     cord->Append(part);
617   }
618 
619   template <typename H>
AbslHashValue(H hash_state,const absl::Cord & c)620   friend H AbslHashValue(H hash_state, const absl::Cord& c) {
621     absl::optional<absl::string_view> maybe_flat = c.TryFlat();
622     if (maybe_flat.has_value()) {
623       return H::combine(std::move(hash_state), *maybe_flat);
624     }
625     return c.HashFragmented(std::move(hash_state));
626   }
627 
628   // Create a Cord with the contents of StringConstant<T>::value.
629   // No allocations will be done and no data will be copied.
630   // This is an INTERNAL API and subject to change or removal. This API can only
631   // be used by spelling absl::strings_internal::MakeStringConstant, which is
632   // also an internal API.
633   template <typename T>
634   explicit constexpr Cord(strings_internal::StringConstant<T>);
635 
636  private:
637   friend class CordTestPeer;
638   friend bool operator==(const Cord& lhs, const Cord& rhs);
639   friend bool operator==(const Cord& lhs, absl::string_view rhs);
640 
641   // Calls the provided function once for each cord chunk, in order.  Unlike
642   // Chunks(), this API will not allocate memory.
643   void ForEachChunk(absl::FunctionRef<void(absl::string_view)>) const;
644 
645   // Allocates new contiguous storage for the contents of the cord. This is
646   // called by Flatten() when the cord was not already flat.
647   absl::string_view FlattenSlowPath();
648 
649   // Actual cord contents are hidden inside the following simple
650   // class so that we can isolate the bulk of cord.cc from changes
651   // to the representation.
652   //
653   // InlineRep holds either a tree pointer, or an array of kMaxInline bytes.
654   class InlineRep {
655    public:
656     static constexpr unsigned char kMaxInline = cord_internal::kMaxInline;
657     static_assert(kMaxInline >= sizeof(absl::cord_internal::CordRep*), "");
658     static constexpr unsigned char kTreeFlag = cord_internal::kTreeFlag;
659     static constexpr unsigned char kProfiledFlag = cord_internal::kProfiledFlag;
660 
InlineRep()661     constexpr InlineRep() : data_() {}
662     InlineRep(const InlineRep& src);
663     InlineRep(InlineRep&& src);
664     InlineRep& operator=(const InlineRep& src);
665     InlineRep& operator=(InlineRep&& src) noexcept;
666 
667     explicit constexpr InlineRep(cord_internal::InlineData data);
668 
669     void Swap(InlineRep* rhs);
670     bool empty() const;
671     size_t size() const;
672     const char* data() const;  // Returns nullptr if holding pointer
673     void set_data(const char* data, size_t n,
674                   bool nullify_tail);  // Discards pointer, if any
675     char* set_data(size_t n);  // Write data to the result
676     // Returns nullptr if holding bytes
677     absl::cord_internal::CordRep* tree() const;
678     // Discards old pointer, if any
679     void set_tree(absl::cord_internal::CordRep* rep);
680     // Replaces a tree with a new root. This is faster than set_tree, but it
681     // should only be used when it's clear that the old rep was a tree.
682     void replace_tree(absl::cord_internal::CordRep* rep);
683     // Returns non-null iff was holding a pointer
684     absl::cord_internal::CordRep* clear();
685     // Converts to pointer if necessary.
686     absl::cord_internal::CordRep* force_tree(size_t extra_hint);
687     void reduce_size(size_t n);  // REQUIRES: holding data
688     void remove_prefix(size_t n);  // REQUIRES: holding data
689     void AppendArray(const char* src_data, size_t src_size);
690     absl::string_view FindFlatStartPiece() const;
691     void AppendTree(absl::cord_internal::CordRep* tree);
692     void PrependTree(absl::cord_internal::CordRep* tree);
693     void GetAppendRegion(char** region, size_t* size, size_t max_length);
694     void GetAppendRegion(char** region, size_t* size);
IsSame(const InlineRep & other)695     bool IsSame(const InlineRep& other) const {
696       return memcmp(&data_, &other.data_, sizeof(data_)) == 0;
697     }
BitwiseCompare(const InlineRep & other)698     int BitwiseCompare(const InlineRep& other) const {
699       uint64_t x, y;
700       // Use memcpy to avoid aliasing issues.
701       memcpy(&x, &data_, sizeof(x));
702       memcpy(&y, &other.data_, sizeof(y));
703       if (x == y) {
704         memcpy(&x, reinterpret_cast<const char*>(&data_) + 8, sizeof(x));
705         memcpy(&y, reinterpret_cast<const char*>(&other.data_) + 8, sizeof(y));
706         if (x == y) return 0;
707       }
708       return absl::big_endian::FromHost64(x) < absl::big_endian::FromHost64(y)
709                  ? -1
710                  : 1;
711     }
CopyTo(std::string * dst)712     void CopyTo(std::string* dst) const {
713       // memcpy is much faster when operating on a known size. On most supported
714       // platforms, the small string optimization is large enough that resizing
715       // to 15 bytes does not cause a memory allocation.
716       absl::strings_internal::STLStringResizeUninitialized(dst,
717                                                            sizeof(data_) - 1);
718       memcpy(&(*dst)[0], &data_, sizeof(data_) - 1);
719       // erase is faster than resize because the logic for memory allocation is
720       // not needed.
721       dst->erase(tagged_size());
722     }
723 
724     // Copies the inline contents into `dst`. Assumes the cord is not empty.
725     void CopyToArray(char* dst) const;
726 
is_tree()727     bool is_tree() const { return tagged_size() > kMaxInline; }
728 
729    private:
730     friend class Cord;
731 
732     void AssignSlow(const InlineRep& src);
733     // Unrefs the tree, stops profiling, and zeroes the contents
734     void ClearSlow();
735 
ResetToEmpty()736     void ResetToEmpty() { data_ = {}; }
737 
738     // This uses reinterpret_cast instead of the union to avoid accessing the
739     // inactive union element. The tagged size is not a common prefix.
set_tagged_size(char new_tag)740     void set_tagged_size(char new_tag) {
741       reinterpret_cast<char*>(&data_)[kMaxInline] = new_tag;
742     }
tagged_size()743     char tagged_size() const {
744       return reinterpret_cast<const char*>(&data_)[kMaxInline];
745     }
746 
747     cord_internal::InlineData data_;
748   };
749   InlineRep contents_;
750 
751   // Helper for MemoryUsage().
752   static size_t MemoryUsageAux(const absl::cord_internal::CordRep* rep);
753 
754   // Helper for GetFlat() and TryFlat().
755   static bool GetFlatAux(absl::cord_internal::CordRep* rep,
756                          absl::string_view* fragment);
757 
758   // Helper for ForEachChunk().
759   static void ForEachChunkAux(
760       absl::cord_internal::CordRep* rep,
761       absl::FunctionRef<void(absl::string_view)> callback);
762 
763   // The destructor for non-empty Cords.
764   void DestroyCordSlow();
765 
766   // Out-of-line implementation of slower parts of logic.
767   void CopyToArraySlowPath(char* dst) const;
768   int CompareSlowPath(absl::string_view rhs, size_t compared_size,
769                       size_t size_to_compare) const;
770   int CompareSlowPath(const Cord& rhs, size_t compared_size,
771                       size_t size_to_compare) const;
772   bool EqualsImpl(absl::string_view rhs, size_t size_to_compare) const;
773   bool EqualsImpl(const Cord& rhs, size_t size_to_compare) const;
774   int CompareImpl(const Cord& rhs) const;
775 
776   template <typename ResultType, typename RHS>
777   friend ResultType GenericCompare(const Cord& lhs, const RHS& rhs,
778                                    size_t size_to_compare);
779   static absl::string_view GetFirstChunk(const Cord& c);
780   static absl::string_view GetFirstChunk(absl::string_view sv);
781 
782   // Returns a new reference to contents_.tree(), or steals an existing
783   // reference if called on an rvalue.
784   absl::cord_internal::CordRep* TakeRep() const&;
785   absl::cord_internal::CordRep* TakeRep() &&;
786 
787   // Helper for Append().
788   template <typename C>
789   void AppendImpl(C&& src);
790 
791   // Helper for AbslHashValue().
792   template <typename H>
HashFragmented(H hash_state)793   H HashFragmented(H hash_state) const {
794     typename H::AbslInternalPiecewiseCombiner combiner;
795     ForEachChunk([&combiner, &hash_state](absl::string_view chunk) {
796       hash_state = combiner.add_buffer(std::move(hash_state), chunk.data(),
797                                        chunk.size());
798     });
799     return H::combine(combiner.finalize(std::move(hash_state)), size());
800   }
801 };
802 
803 ABSL_NAMESPACE_END
804 }  // namespace absl
805 
806 namespace absl {
807 ABSL_NAMESPACE_BEGIN
808 
809 // allow a Cord to be logged
810 extern std::ostream& operator<<(std::ostream& out, const Cord& cord);
811 
812 // ------------------------------------------------------------------
813 // Internal details follow.  Clients should ignore.
814 
815 namespace cord_internal {
816 
817 // Fast implementation of memmove for up to 15 bytes. This implementation is
818 // safe for overlapping regions. If nullify_tail is true, the destination is
819 // padded with '\0' up to 16 bytes.
820 inline void SmallMemmove(char* dst, const char* src, size_t n,
821                          bool nullify_tail = false) {
822   if (n >= 8) {
823     assert(n <= 16);
824     uint64_t buf1;
825     uint64_t buf2;
826     memcpy(&buf1, src, 8);
827     memcpy(&buf2, src + n - 8, 8);
828     if (nullify_tail) {
829       memset(dst + 8, 0, 8);
830     }
831     memcpy(dst, &buf1, 8);
832     memcpy(dst + n - 8, &buf2, 8);
833   } else if (n >= 4) {
834     uint32_t buf1;
835     uint32_t buf2;
836     memcpy(&buf1, src, 4);
837     memcpy(&buf2, src + n - 4, 4);
838     if (nullify_tail) {
839       memset(dst + 4, 0, 4);
840       memset(dst + 8, 0, 8);
841     }
842     memcpy(dst, &buf1, 4);
843     memcpy(dst + n - 4, &buf2, 4);
844   } else {
845     if (n != 0) {
846       dst[0] = src[0];
847       dst[n / 2] = src[n / 2];
848       dst[n - 1] = src[n - 1];
849     }
850     if (nullify_tail) {
851       memset(dst + 8, 0, 8);
852       memset(dst + n, 0, 8);
853     }
854   }
855 }
856 
857 // Does non-template-specific `CordRepExternal` initialization.
858 // Expects `data` to be non-empty.
859 void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep);
860 
861 // Creates a new `CordRep` that owns `data` and `releaser` and returns a pointer
862 // to it, or `nullptr` if `data` was empty.
863 template <typename Releaser>
864 // NOLINTNEXTLINE - suppress clang-tidy raw pointer return.
NewExternalRep(absl::string_view data,Releaser && releaser)865 CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) {
866   using ReleaserType = absl::decay_t<Releaser>;
867   if (data.empty()) {
868     // Never create empty external nodes.
869     InvokeReleaser(Rank0{}, ReleaserType(std::forward<Releaser>(releaser)),
870                    data);
871     return nullptr;
872   }
873 
874   CordRepExternal* rep = new CordRepExternalImpl<ReleaserType>(
875       std::forward<Releaser>(releaser), 0);
876   InitializeCordRepExternal(data, rep);
877   return rep;
878 }
879 
880 // Overload for function reference types that dispatches using a function
881 // pointer because there are no `alignof()` or `sizeof()` a function reference.
882 // NOLINTNEXTLINE - suppress clang-tidy raw pointer return.
NewExternalRep(absl::string_view data,void (& releaser)(absl::string_view))883 inline CordRep* NewExternalRep(absl::string_view data,
884                                void (&releaser)(absl::string_view)) {
885   return NewExternalRep(data, &releaser);
886 }
887 
888 }  // namespace cord_internal
889 
890 template <typename Releaser>
MakeCordFromExternal(absl::string_view data,Releaser && releaser)891 Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser) {
892   Cord cord;
893   cord.contents_.set_tree(::absl::cord_internal::NewExternalRep(
894       data, std::forward<Releaser>(releaser)));
895   return cord;
896 }
897 
InlineRep(cord_internal::InlineData data)898 constexpr Cord::InlineRep::InlineRep(cord_internal::InlineData data)
899     : data_(data) {}
900 
InlineRep(const Cord::InlineRep & src)901 inline Cord::InlineRep::InlineRep(const Cord::InlineRep& src) {
902   data_ = src.data_;
903 }
904 
InlineRep(Cord::InlineRep && src)905 inline Cord::InlineRep::InlineRep(Cord::InlineRep&& src) {
906   data_ = src.data_;
907   src.ResetToEmpty();
908 }
909 
910 inline Cord::InlineRep& Cord::InlineRep::operator=(const Cord::InlineRep& src) {
911   if (this == &src) {
912     return *this;
913   }
914   if (!is_tree() && !src.is_tree()) {
915     data_ = src.data_;
916     return *this;
917   }
918   AssignSlow(src);
919   return *this;
920 }
921 
922 inline Cord::InlineRep& Cord::InlineRep::operator=(
923     Cord::InlineRep&& src) noexcept {
924   if (is_tree()) {
925     ClearSlow();
926   }
927   data_ = src.data_;
928   src.ResetToEmpty();
929   return *this;
930 }
931 
Swap(Cord::InlineRep * rhs)932 inline void Cord::InlineRep::Swap(Cord::InlineRep* rhs) {
933   if (rhs == this) {
934     return;
935   }
936 
937   std::swap(data_, rhs->data_);
938 }
939 
data()940 inline const char* Cord::InlineRep::data() const {
941   return is_tree() ? nullptr : data_.as_chars;
942 }
943 
tree()944 inline absl::cord_internal::CordRep* Cord::InlineRep::tree() const {
945   if (is_tree()) {
946     return data_.as_tree.rep;
947   } else {
948     return nullptr;
949   }
950 }
951 
empty()952 inline bool Cord::InlineRep::empty() const { return tagged_size() == 0; }
953 
size()954 inline size_t Cord::InlineRep::size() const {
955   const char tag = tagged_size();
956   if (tag <= kMaxInline) return tag;
957   return static_cast<size_t>(tree()->length);
958 }
959 
set_tree(absl::cord_internal::CordRep * rep)960 inline void Cord::InlineRep::set_tree(absl::cord_internal::CordRep* rep) {
961   if (rep == nullptr) {
962     ResetToEmpty();
963   } else {
964     bool was_tree = is_tree();
965     data_.as_tree = {rep, {}, tagged_size()};
966     if (!was_tree) {
967       // If we were not a tree already, set the tag.
968       // Otherwise, leave it alone because it might have the profile bit on.
969       set_tagged_size(kTreeFlag);
970     }
971   }
972 }
973 
replace_tree(absl::cord_internal::CordRep * rep)974 inline void Cord::InlineRep::replace_tree(absl::cord_internal::CordRep* rep) {
975   ABSL_ASSERT(is_tree());
976   if (ABSL_PREDICT_FALSE(rep == nullptr)) {
977     set_tree(rep);
978     return;
979   }
980   data_.as_tree = {rep, {}, tagged_size()};
981 }
982 
clear()983 inline absl::cord_internal::CordRep* Cord::InlineRep::clear() {
984   absl::cord_internal::CordRep* result = tree();
985   ResetToEmpty();
986   return result;
987 }
988 
CopyToArray(char * dst)989 inline void Cord::InlineRep::CopyToArray(char* dst) const {
990   assert(!is_tree());
991   size_t n = tagged_size();
992   assert(n != 0);
993   cord_internal::SmallMemmove(dst, data_.as_chars, n);
994 }
995 
Cord()996 constexpr inline Cord::Cord() noexcept {}
997 
998 template <typename T>
Cord(strings_internal::StringConstant<T>)999 constexpr Cord::Cord(strings_internal::StringConstant<T>)
1000     : contents_(strings_internal::StringConstant<T>::value.size() <=
1001                         cord_internal::kMaxInline
1002                     ? cord_internal::InlineData(
1003                           strings_internal::StringConstant<T>::value)
1004                     : cord_internal::InlineData(cord_internal::AsTree{
1005                           &cord_internal::ConstInitExternalStorage<
1006                               strings_internal::StringConstant<T>>::value,
1007                           {},
1008                           cord_internal::kTreeFlag})) {}
1009 
1010 inline Cord& Cord::operator=(const Cord& x) {
1011   contents_ = x.contents_;
1012   return *this;
1013 }
1014 
Cord(Cord && src)1015 inline Cord::Cord(Cord&& src) noexcept : contents_(std::move(src.contents_)) {}
1016 
swap(Cord & other)1017 inline void Cord::swap(Cord& other) noexcept {
1018   contents_.Swap(&other.contents_);
1019 }
1020 
1021 inline Cord& Cord::operator=(Cord&& x) noexcept {
1022   contents_ = std::move(x.contents_);
1023   return *this;
1024 }
1025 
1026 extern template Cord::Cord(std::string&& src);
1027 extern template Cord& Cord::operator=(std::string&& src);
1028 
size()1029 inline size_t Cord::size() const {
1030   // Length is 1st field in str.rep_
1031   return contents_.size();
1032 }
1033 
empty()1034 inline bool Cord::empty() const { return contents_.empty(); }
1035 
EstimatedMemoryUsage()1036 inline size_t Cord::EstimatedMemoryUsage() const {
1037   size_t result = sizeof(Cord);
1038   if (const absl::cord_internal::CordRep* rep = contents_.tree()) {
1039     result += MemoryUsageAux(rep);
1040   }
1041   return result;
1042 }
1043 
TryFlat()1044 inline absl::optional<absl::string_view> Cord::TryFlat() const {
1045   absl::cord_internal::CordRep* rep = contents_.tree();
1046   if (rep == nullptr) {
1047     return absl::string_view(contents_.data(), contents_.size());
1048   }
1049   absl::string_view fragment;
1050   if (GetFlatAux(rep, &fragment)) {
1051     return fragment;
1052   }
1053   return absl::nullopt;
1054 }
1055 
Flatten()1056 inline absl::string_view Cord::Flatten() {
1057   absl::cord_internal::CordRep* rep = contents_.tree();
1058   if (rep == nullptr) {
1059     return absl::string_view(contents_.data(), contents_.size());
1060   } else {
1061     absl::string_view already_flat_contents;
1062     if (GetFlatAux(rep, &already_flat_contents)) {
1063       return already_flat_contents;
1064     }
1065   }
1066   return FlattenSlowPath();
1067 }
1068 
Append(absl::string_view src)1069 inline void Cord::Append(absl::string_view src) {
1070   contents_.AppendArray(src.data(), src.size());
1071 }
1072 
1073 extern template void Cord::Append(std::string&& src);
1074 extern template void Cord::Prepend(std::string&& src);
1075 
Compare(const Cord & rhs)1076 inline int Cord::Compare(const Cord& rhs) const {
1077   if (!contents_.is_tree() && !rhs.contents_.is_tree()) {
1078     return contents_.BitwiseCompare(rhs.contents_);
1079   }
1080 
1081   return CompareImpl(rhs);
1082 }
1083 
1084 // Does 'this' cord start/end with rhs
StartsWith(const Cord & rhs)1085 inline bool Cord::StartsWith(const Cord& rhs) const {
1086   if (contents_.IsSame(rhs.contents_)) return true;
1087   size_t rhs_size = rhs.size();
1088   if (size() < rhs_size) return false;
1089   return EqualsImpl(rhs, rhs_size);
1090 }
1091 
StartsWith(absl::string_view rhs)1092 inline bool Cord::StartsWith(absl::string_view rhs) const {
1093   size_t rhs_size = rhs.size();
1094   if (size() < rhs_size) return false;
1095   return EqualsImpl(rhs, rhs_size);
1096 }
1097 
ChunkIterator(const Cord * cord)1098 inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
1099     : bytes_remaining_(cord->size()) {
1100   if (cord->empty()) return;
1101   if (cord->contents_.is_tree()) {
1102     stack_of_right_children_.push_back(cord->contents_.tree());
1103     operator++();
1104   } else {
1105     current_chunk_ = absl::string_view(cord->contents_.data(), cord->size());
1106   }
1107 }
1108 
1109 inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) {
1110   ChunkIterator tmp(*this);
1111   operator++();
1112   return tmp;
1113 }
1114 
1115 inline bool Cord::ChunkIterator::operator==(const ChunkIterator& other) const {
1116   return bytes_remaining_ == other.bytes_remaining_;
1117 }
1118 
1119 inline bool Cord::ChunkIterator::operator!=(const ChunkIterator& other) const {
1120   return !(*this == other);
1121 }
1122 
1123 inline Cord::ChunkIterator::reference Cord::ChunkIterator::operator*() const {
1124   ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
1125   return current_chunk_;
1126 }
1127 
1128 inline Cord::ChunkIterator::pointer Cord::ChunkIterator::operator->() const {
1129   ABSL_HARDENING_ASSERT(bytes_remaining_ != 0);
1130   return &current_chunk_;
1131 }
1132 
RemoveChunkPrefix(size_t n)1133 inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) {
1134   assert(n < current_chunk_.size());
1135   current_chunk_.remove_prefix(n);
1136   bytes_remaining_ -= n;
1137 }
1138 
AdvanceBytes(size_t n)1139 inline void Cord::ChunkIterator::AdvanceBytes(size_t n) {
1140   if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) {
1141     RemoveChunkPrefix(n);
1142   } else if (n != 0) {
1143     AdvanceBytesSlowPath(n);
1144   }
1145 }
1146 
chunk_begin()1147 inline Cord::ChunkIterator Cord::chunk_begin() const {
1148   return ChunkIterator(this);
1149 }
1150 
chunk_end()1151 inline Cord::ChunkIterator Cord::chunk_end() const { return ChunkIterator(); }
1152 
begin()1153 inline Cord::ChunkIterator Cord::ChunkRange::begin() const {
1154   return cord_->chunk_begin();
1155 }
1156 
end()1157 inline Cord::ChunkIterator Cord::ChunkRange::end() const {
1158   return cord_->chunk_end();
1159 }
1160 
Chunks()1161 inline Cord::ChunkRange Cord::Chunks() const { return ChunkRange(this); }
1162 
1163 inline Cord::CharIterator& Cord::CharIterator::operator++() {
1164   if (ABSL_PREDICT_TRUE(chunk_iterator_->size() > 1)) {
1165     chunk_iterator_.RemoveChunkPrefix(1);
1166   } else {
1167     ++chunk_iterator_;
1168   }
1169   return *this;
1170 }
1171 
1172 inline Cord::CharIterator Cord::CharIterator::operator++(int) {
1173   CharIterator tmp(*this);
1174   operator++();
1175   return tmp;
1176 }
1177 
1178 inline bool Cord::CharIterator::operator==(const CharIterator& other) const {
1179   return chunk_iterator_ == other.chunk_iterator_;
1180 }
1181 
1182 inline bool Cord::CharIterator::operator!=(const CharIterator& other) const {
1183   return !(*this == other);
1184 }
1185 
1186 inline Cord::CharIterator::reference Cord::CharIterator::operator*() const {
1187   return *chunk_iterator_->data();
1188 }
1189 
1190 inline Cord::CharIterator::pointer Cord::CharIterator::operator->() const {
1191   return chunk_iterator_->data();
1192 }
1193 
AdvanceAndRead(CharIterator * it,size_t n_bytes)1194 inline Cord Cord::AdvanceAndRead(CharIterator* it, size_t n_bytes) {
1195   assert(it != nullptr);
1196   return it->chunk_iterator_.AdvanceAndReadBytes(n_bytes);
1197 }
1198 
Advance(CharIterator * it,size_t n_bytes)1199 inline void Cord::Advance(CharIterator* it, size_t n_bytes) {
1200   assert(it != nullptr);
1201   it->chunk_iterator_.AdvanceBytes(n_bytes);
1202 }
1203 
ChunkRemaining(const CharIterator & it)1204 inline absl::string_view Cord::ChunkRemaining(const CharIterator& it) {
1205   return *it.chunk_iterator_;
1206 }
1207 
char_begin()1208 inline Cord::CharIterator Cord::char_begin() const {
1209   return CharIterator(this);
1210 }
1211 
char_end()1212 inline Cord::CharIterator Cord::char_end() const { return CharIterator(); }
1213 
begin()1214 inline Cord::CharIterator Cord::CharRange::begin() const {
1215   return cord_->char_begin();
1216 }
1217 
end()1218 inline Cord::CharIterator Cord::CharRange::end() const {
1219   return cord_->char_end();
1220 }
1221 
Chars()1222 inline Cord::CharRange Cord::Chars() const { return CharRange(this); }
1223 
ForEachChunk(absl::FunctionRef<void (absl::string_view)> callback)1224 inline void Cord::ForEachChunk(
1225     absl::FunctionRef<void(absl::string_view)> callback) const {
1226   absl::cord_internal::CordRep* rep = contents_.tree();
1227   if (rep == nullptr) {
1228     callback(absl::string_view(contents_.data(), contents_.size()));
1229   } else {
1230     return ForEachChunkAux(rep, callback);
1231   }
1232 }
1233 
1234 // Nonmember Cord-to-Cord relational operarators.
1235 inline bool operator==(const Cord& lhs, const Cord& rhs) {
1236   if (lhs.contents_.IsSame(rhs.contents_)) return true;
1237   size_t rhs_size = rhs.size();
1238   if (lhs.size() != rhs_size) return false;
1239   return lhs.EqualsImpl(rhs, rhs_size);
1240 }
1241 
1242 inline bool operator!=(const Cord& x, const Cord& y) { return !(x == y); }
1243 inline bool operator<(const Cord& x, const Cord& y) {
1244   return x.Compare(y) < 0;
1245 }
1246 inline bool operator>(const Cord& x, const Cord& y) {
1247   return x.Compare(y) > 0;
1248 }
1249 inline bool operator<=(const Cord& x, const Cord& y) {
1250   return x.Compare(y) <= 0;
1251 }
1252 inline bool operator>=(const Cord& x, const Cord& y) {
1253   return x.Compare(y) >= 0;
1254 }
1255 
1256 // Nonmember Cord-to-absl::string_view relational operators.
1257 //
1258 // Due to implicit conversions, these also enable comparisons of Cord with
1259 // with std::string, ::string, and const char*.
1260 inline bool operator==(const Cord& lhs, absl::string_view rhs) {
1261   size_t lhs_size = lhs.size();
1262   size_t rhs_size = rhs.size();
1263   if (lhs_size != rhs_size) return false;
1264   return lhs.EqualsImpl(rhs, rhs_size);
1265 }
1266 
1267 inline bool operator==(absl::string_view x, const Cord& y) { return y == x; }
1268 inline bool operator!=(const Cord& x, absl::string_view y) { return !(x == y); }
1269 inline bool operator!=(absl::string_view x, const Cord& y) { return !(x == y); }
1270 inline bool operator<(const Cord& x, absl::string_view y) {
1271   return x.Compare(y) < 0;
1272 }
1273 inline bool operator<(absl::string_view x, const Cord& y) {
1274   return y.Compare(x) > 0;
1275 }
1276 inline bool operator>(const Cord& x, absl::string_view y) { return y < x; }
1277 inline bool operator>(absl::string_view x, const Cord& y) { return y < x; }
1278 inline bool operator<=(const Cord& x, absl::string_view y) { return !(y < x); }
1279 inline bool operator<=(absl::string_view x, const Cord& y) { return !(y < x); }
1280 inline bool operator>=(const Cord& x, absl::string_view y) { return !(x < y); }
1281 inline bool operator>=(absl::string_view x, const Cord& y) { return !(x < y); }
1282 
1283 // Some internals exposed to test code.
1284 namespace strings_internal {
1285 class CordTestAccess {
1286  public:
1287   static size_t FlatOverhead();
1288   static size_t MaxFlatLength();
1289   static size_t SizeofCordRepConcat();
1290   static size_t SizeofCordRepExternal();
1291   static size_t SizeofCordRepSubstring();
1292   static size_t FlatTagToLength(uint8_t tag);
1293   static uint8_t LengthToTag(size_t s);
1294 };
1295 }  // namespace strings_internal
1296 ABSL_NAMESPACE_END
1297 }  // namespace absl
1298 
1299 #endif  // ABSL_STRINGS_CORD_H_
1300