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 ¤t_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