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 // A Cord is a sequence of characters with some unusual access propreties.
16 // A Cord supports efficient insertions and deletions at the start and end of
17 // the byte sequence, but random access reads are slower, and random access
18 // modifications are not supported by the API. Cord also provides cheap copies
19 // (using a copy-on-write strategy) and cheap substring operations.
20 //
21 // Thread safety
22 // -------------
23 // Cord has the same thread-safety properties as many other types like
24 // std::string, std::vector<>, int, etc -- it is thread-compatible. In
25 // particular, if no thread may call a non-const method, then it is safe to
26 // concurrently call const methods. Copying a Cord produces a new instance that
27 // can be used concurrently with the original in arbitrary ways.
28 //
29 // Implementation is similar to the "Ropes" described in:
30 // Ropes: An alternative to strings
31 // Hans J. Boehm, Russ Atkinson, Michael Plass
32 // Software Practice and Experience, December 1995
33
34 #ifndef ABSL_STRINGS_CORD_H_
35 #define ABSL_STRINGS_CORD_H_
36
37 #include <algorithm>
38 #include <cstddef>
39 #include <cstdint>
40 #include <cstring>
41 #include <iostream>
42 #include <iterator>
43 #include <string>
44
45 #include "absl/base/internal/endian.h"
46 #include "absl/base/internal/invoke.h"
47 #include "absl/base/internal/per_thread_tls.h"
48 #include "absl/base/macros.h"
49 #include "absl/base/port.h"
50 #include "absl/container/inlined_vector.h"
51 #include "absl/functional/function_ref.h"
52 #include "absl/meta/type_traits.h"
53 #include "absl/strings/internal/cord_internal.h"
54 #include "absl/strings/internal/resize_uninitialized.h"
55 #include "absl/strings/string_view.h"
56
57 namespace absl {
58 ABSL_NAMESPACE_BEGIN
59 class Cord;
60 class CordTestPeer;
61 template <typename Releaser>
62 Cord MakeCordFromExternal(absl::string_view, Releaser&&);
63 void CopyCordToString(const Cord& src, std::string* dst);
64 namespace hash_internal {
65 template <typename H>
66 H HashFragmentedCord(H, const Cord&);
67 }
68
69 // A Cord is a sequence of characters.
70 class Cord {
71 private:
72 template <typename T>
73 using EnableIfString =
74 absl::enable_if_t<std::is_same<T, std::string>::value, int>;
75
76 public:
77 // --------------------------------------------------------------------
78 // Constructors, destructors and helper factories
79
80 // Create an empty cord
81 constexpr Cord() noexcept;
82
83 // Cord is copyable and efficiently movable.
84 // The moved-from state is valid but unspecified.
85 Cord(const Cord& src);
86 Cord(Cord&& src) noexcept;
87 Cord& operator=(const Cord& x);
88 Cord& operator=(Cord&& x) noexcept;
89
90 // Create a cord out of "src". This constructor is explicit on
91 // purpose so that people do not get automatic type conversions.
92 explicit Cord(absl::string_view src);
93 Cord& operator=(absl::string_view src);
94
95 // These are templated to avoid ambiguities for types that are convertible to
96 // both `absl::string_view` and `std::string`, such as `const char*`.
97 //
98 // Note that these functions reserve the right to reuse the `string&&`'s
99 // memory and that they will do so in the future.
100 template <typename T, EnableIfString<T> = 0>
Cord(T && src)101 explicit Cord(T&& src) : Cord(absl::string_view(src)) {}
102 template <typename T, EnableIfString<T> = 0>
103 Cord& operator=(T&& src);
104
105 // Destroy the cord
~Cord()106 ~Cord() {
107 if (contents_.is_tree()) DestroyCordSlow();
108 }
109
110 // Creates a Cord that takes ownership of external memory. The contents of
111 // `data` are not copied.
112 //
113 // This function takes a callable that is invoked when all Cords are
114 // finished with `data`. The data must remain live and unchanging until the
115 // releaser is called. The requirements for the releaser are that it:
116 // * is move constructible,
117 // * supports `void operator()(absl::string_view) const`,
118 // * does not have alignment requirement greater than what is guaranteed by
119 // ::operator new. This is dictated by alignof(std::max_align_t) before
120 // C++17 and __STDCPP_DEFAULT_NEW_ALIGNMENT__ if compiling with C++17 or
121 // it is supported by the implementation.
122 //
123 // Example:
124 //
125 // Cord MakeCord(BlockPool* pool) {
126 // Block* block = pool->NewBlock();
127 // FillBlock(block);
128 // return absl::MakeCordFromExternal(
129 // block->ToStringView(),
130 // [pool, block](absl::string_view /*ignored*/) {
131 // pool->FreeBlock(block);
132 // });
133 // }
134 //
135 // WARNING: It's likely a bug if your releaser doesn't do anything.
136 // For example, consider the following:
137 //
138 // void Foo(const char* buffer, int len) {
139 // auto c = absl::MakeCordFromExternal(absl::string_view(buffer, len),
140 // [](absl::string_view) {});
141 //
142 // // BUG: If Bar() copies its cord for any reason, including keeping a
143 // // substring of it, the lifetime of buffer might be extended beyond
144 // // when Foo() returns.
145 // Bar(c);
146 // }
147 template <typename Releaser>
148 friend Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser);
149
150 // --------------------------------------------------------------------
151 // Mutations
152
153 void Clear();
154
155 void Append(const Cord& src);
156 void Append(Cord&& src);
157 void Append(absl::string_view src);
158 template <typename T, EnableIfString<T> = 0>
159 void Append(T&& src);
160
161 void Prepend(const Cord& src);
162 void Prepend(absl::string_view src);
163 template <typename T, EnableIfString<T> = 0>
164 void Prepend(T&& src);
165
166 void RemovePrefix(size_t n);
167 void RemoveSuffix(size_t n);
168
169 // Returns a new cord representing the subrange [pos, pos + new_size) of
170 // *this. If pos >= size(), the result is empty(). If
171 // (pos + new_size) >= size(), the result is the subrange [pos, size()).
172 Cord Subcord(size_t pos, size_t new_size) const;
173
174 friend void swap(Cord& x, Cord& y) noexcept;
175
176 // --------------------------------------------------------------------
177 // Accessors
178
179 size_t size() const;
180 bool empty() const;
181
182 // Returns the approximate number of bytes pinned by this Cord. Note that
183 // Cords that share memory could each be "charged" independently for the same
184 // shared memory.
185 size_t EstimatedMemoryUsage() const;
186
187 // --------------------------------------------------------------------
188 // Comparators
189
190 // Compares 'this' Cord with rhs. This function and its relatives
191 // treat Cords as sequences of unsigned bytes. The comparison is a
192 // straightforward lexicographic comparison. Return value:
193 // -1 'this' Cord is smaller
194 // 0 two Cords are equal
195 // 1 'this' Cord is larger
196 int Compare(absl::string_view rhs) const;
197 int Compare(const Cord& rhs) const;
198
199 // Does 'this' cord start/end with rhs
200 bool StartsWith(const Cord& rhs) const;
201 bool StartsWith(absl::string_view rhs) const;
202 bool EndsWith(absl::string_view rhs) const;
203 bool EndsWith(const Cord& rhs) const;
204
205 // --------------------------------------------------------------------
206 // Conversion to other types
207
208 explicit operator std::string() const;
209
210 // Copies the contents from `src` to `*dst`.
211 //
212 // This function optimizes the case of reusing the destination std::string since it
213 // can reuse previously allocated capacity. However, this function does not
214 // guarantee that pointers previously returned by `dst->data()` remain valid
215 // even if `*dst` had enough capacity to hold `src`. If `*dst` is a new
216 // object, prefer to simply use the conversion operator to `std::string`.
217 friend void CopyCordToString(const Cord& src, std::string* dst);
218
219 // --------------------------------------------------------------------
220 // Iteration
221
222 class CharIterator;
223
224 // Type for iterating over the chunks of a `Cord`. See comments for
225 // `Cord::chunk_begin()`, `Cord::chunk_end()` and `Cord::Chunks()` below for
226 // preferred usage.
227 //
228 // Additional notes:
229 // * The `string_view` returned by dereferencing a valid, non-`end()`
230 // iterator is guaranteed to be non-empty.
231 // * A `ChunkIterator` object is invalidated after any non-const
232 // operation on the `Cord` object over which it iterates.
233 // * Two `ChunkIterator` objects can be equality compared if and only if
234 // they remain valid and iterate over the same `Cord`.
235 // * This is a proxy iterator. This means the `string_view` returned by the
236 // iterator does not live inside the Cord, and its lifetime is limited to
237 // the lifetime of the iterator itself. To help prevent issues,
238 // `ChunkIterator::reference` is not a true reference type and is
239 // equivalent to `value_type`.
240 // * The iterator keeps state that can grow for `Cord`s that contain many
241 // nodes and are imbalanced due to sharing. Prefer to pass this type by
242 // const reference instead of by value.
243 class ChunkIterator {
244 public:
245 using iterator_category = std::input_iterator_tag;
246 using value_type = absl::string_view;
247 using difference_type = ptrdiff_t;
248 using pointer = const value_type*;
249 using reference = value_type;
250
251 ChunkIterator() = default;
252
253 ChunkIterator& operator++();
254 ChunkIterator operator++(int);
255 bool operator==(const ChunkIterator& other) const;
256 bool operator!=(const ChunkIterator& other) const;
257 reference operator*() const;
258 pointer operator->() const;
259
260 friend class Cord;
261 friend class CharIterator;
262
263 private:
264 // Constructs a `begin()` iterator from `cord`.
265 explicit ChunkIterator(const Cord* cord);
266
267 // Removes `n` bytes from `current_chunk_`. Expects `n` to be smaller than
268 // `current_chunk_.size()`.
269 void RemoveChunkPrefix(size_t n);
270 Cord AdvanceAndReadBytes(size_t n);
271 void AdvanceBytes(size_t n);
272 // Iterates `n` bytes, where `n` is expected to be greater than or equal to
273 // `current_chunk_.size()`.
274 void AdvanceBytesSlowPath(size_t n);
275
276 // A view into bytes of the current `CordRep`. It may only be a view to a
277 // suffix of bytes if this is being used by `CharIterator`.
278 absl::string_view current_chunk_;
279 // The current leaf, or `nullptr` if the iterator points to short data.
280 // If the current chunk is a substring node, current_leaf_ points to the
281 // underlying flat or external node.
282 absl::cord_internal::CordRep* current_leaf_ = nullptr;
283 // The number of bytes left in the `Cord` over which we are iterating.
284 size_t bytes_remaining_ = 0;
285 absl::InlinedVector<absl::cord_internal::CordRep*, 4>
286 stack_of_right_children_;
287 };
288
289 // Returns an iterator to the first chunk of the `Cord`.
290 //
291 // This is useful for getting a `ChunkIterator` outside the context of a
292 // range-based for-loop (in which case see `Cord::Chunks()` below).
293 //
294 // Example:
295 //
296 // absl::Cord::ChunkIterator FindAsChunk(const absl::Cord& c,
297 // absl::string_view s) {
298 // return std::find(c.chunk_begin(), c.chunk_end(), s);
299 // }
300 ChunkIterator chunk_begin() const;
301 // Returns an iterator one increment past the last chunk of the `Cord`.
302 ChunkIterator chunk_end() const;
303
304 // Convenience wrapper over `Cord::chunk_begin()` and `Cord::chunk_end()` to
305 // enable range-based for-loop iteration over `Cord` chunks.
306 //
307 // Prefer to use `Cord::Chunks()` below instead of constructing this directly.
308 class ChunkRange {
309 public:
ChunkRange(const Cord * cord)310 explicit ChunkRange(const Cord* cord) : cord_(cord) {}
311
312 ChunkIterator begin() const;
313 ChunkIterator end() const;
314
315 private:
316 const Cord* cord_;
317 };
318
319 // Returns a range for iterating over the chunks of a `Cord` with a
320 // range-based for-loop.
321 //
322 // Example:
323 //
324 // void ProcessChunks(const Cord& cord) {
325 // for (absl::string_view chunk : cord.Chunks()) { ... }
326 // }
327 //
328 // Note that the ordinary caveats of temporary lifetime extension apply:
329 //
330 // void Process() {
331 // for (absl::string_view chunk : CordFactory().Chunks()) {
332 // // The temporary Cord returned by CordFactory has been destroyed!
333 // }
334 // }
335 ChunkRange Chunks() const;
336
337 // Type for iterating over the characters of a `Cord`. See comments for
338 // `Cord::char_begin()`, `Cord::char_end()` and `Cord::Chars()` below for
339 // preferred usage.
340 //
341 // Additional notes:
342 // * A `CharIterator` object is invalidated after any non-const
343 // operation on the `Cord` object over which it iterates.
344 // * Two `CharIterator` objects can be equality compared if and only if
345 // they remain valid and iterate over the same `Cord`.
346 // * The iterator keeps state that can grow for `Cord`s that contain many
347 // nodes and are imbalanced due to sharing. Prefer to pass this type by
348 // const reference instead of by value.
349 // * This type cannot be a forward iterator because a `Cord` can reuse
350 // sections of memory. This violates the requirement that if dereferencing
351 // two iterators returns the same object, the iterators must compare
352 // equal.
353 class CharIterator {
354 public:
355 using iterator_category = std::input_iterator_tag;
356 using value_type = char;
357 using difference_type = ptrdiff_t;
358 using pointer = const char*;
359 using reference = const char&;
360
361 CharIterator() = default;
362
363 CharIterator& operator++();
364 CharIterator operator++(int);
365 bool operator==(const CharIterator& other) const;
366 bool operator!=(const CharIterator& other) const;
367 reference operator*() const;
368 pointer operator->() const;
369
370 friend Cord;
371
372 private:
CharIterator(const Cord * cord)373 explicit CharIterator(const Cord* cord) : chunk_iterator_(cord) {}
374
375 ChunkIterator chunk_iterator_;
376 };
377
378 // Advances `*it` by `n_bytes` and returns the bytes passed as a `Cord`.
379 //
380 // `n_bytes` must be less than or equal to the number of bytes remaining for
381 // iteration. Otherwise the behavior is undefined. It is valid to pass
382 // `char_end()` and 0.
383 static Cord AdvanceAndRead(CharIterator* it, size_t n_bytes);
384
385 // Advances `*it` by `n_bytes`.
386 //
387 // `n_bytes` must be less than or equal to the number of bytes remaining for
388 // iteration. Otherwise the behavior is undefined. It is valid to pass
389 // `char_end()` and 0.
390 static void Advance(CharIterator* it, size_t n_bytes);
391
392 // Returns the longest contiguous view starting at the iterator's position.
393 //
394 // `it` must be dereferenceable.
395 static absl::string_view ChunkRemaining(const CharIterator& it);
396
397 // Returns an iterator to the first character of the `Cord`.
398 CharIterator char_begin() const;
399 // Returns an iterator to one past the last character of the `Cord`.
400 CharIterator char_end() const;
401
402 // Convenience wrapper over `Cord::char_begin()` and `Cord::char_end()` to
403 // enable range-based for-loop iterator over the characters of a `Cord`.
404 //
405 // Prefer to use `Cord::Chars()` below instead of constructing this directly.
406 class CharRange {
407 public:
CharRange(const Cord * cord)408 explicit CharRange(const Cord* cord) : cord_(cord) {}
409
410 CharIterator begin() const;
411 CharIterator end() const;
412
413 private:
414 const Cord* cord_;
415 };
416
417 // Returns a range for iterating over the characters of a `Cord` with a
418 // range-based for-loop.
419 //
420 // Example:
421 //
422 // void ProcessCord(const Cord& cord) {
423 // for (char c : cord.Chars()) { ... }
424 // }
425 //
426 // Note that the ordinary caveats of temporary lifetime extension apply:
427 //
428 // void Process() {
429 // for (char c : CordFactory().Chars()) {
430 // // The temporary Cord returned by CordFactory has been destroyed!
431 // }
432 // }
433 CharRange Chars() const;
434
435 // --------------------------------------------------------------------
436 // Miscellaneous
437
438 // Get the "i"th character of 'this' and return it.
439 // NOTE: This routine is reasonably efficient. It is roughly
440 // logarithmic in the number of nodes that make up the cord. Still,
441 // if you need to iterate over the contents of a cord, you should
442 // use a CharIterator/CordIterator rather than call operator[] or Get()
443 // repeatedly in a loop.
444 //
445 // REQUIRES: 0 <= i < size()
446 char operator[](size_t i) const;
447
448 // Flattens the cord into a single array and returns a view of the data.
449 //
450 // If the cord was already flat, the contents are not modified.
451 absl::string_view Flatten();
452
453 private:
454 friend class CordTestPeer;
455 template <typename H>
456 friend H absl::hash_internal::HashFragmentedCord(H, const Cord&);
457 friend bool operator==(const Cord& lhs, const Cord& rhs);
458 friend bool operator==(const Cord& lhs, absl::string_view rhs);
459
460 // Call the provided function once for each cord chunk, in order. Unlike
461 // Chunks(), this API will not allocate memory.
462 void ForEachChunk(absl::FunctionRef<void(absl::string_view)>) const;
463
464 // Allocates new contiguous storage for the contents of the cord. This is
465 // called by Flatten() when the cord was not already flat.
466 absl::string_view FlattenSlowPath();
467
468 // Actual cord contents are hidden inside the following simple
469 // class so that we can isolate the bulk of cord.cc from changes
470 // to the representation.
471 //
472 // InlineRep holds either either a tree pointer, or an array of kMaxInline
473 // bytes.
474 class InlineRep {
475 public:
476 static const unsigned char kMaxInline = 15;
477 static_assert(kMaxInline >= sizeof(absl::cord_internal::CordRep*), "");
478 // Tag byte & kMaxInline means we are storing a pointer.
479 static const unsigned char kTreeFlag = 1 << 4;
480 // Tag byte & kProfiledFlag means we are profiling the Cord.
481 static const unsigned char kProfiledFlag = 1 << 5;
482
InlineRep()483 constexpr InlineRep() : data_{} {}
484 InlineRep(const InlineRep& src);
485 InlineRep(InlineRep&& src);
486 InlineRep& operator=(const InlineRep& src);
487 InlineRep& operator=(InlineRep&& src) noexcept;
488
489 void Swap(InlineRep* rhs);
490 bool empty() const;
491 size_t size() const;
492 const char* data() const; // Returns nullptr if holding pointer
493 void set_data(const char* data, size_t n,
494 bool nullify_tail); // Discards pointer, if any
495 char* set_data(size_t n); // Write data to the result
496 // Returns nullptr if holding bytes
497 absl::cord_internal::CordRep* tree() const;
498 // Discards old pointer, if any
499 void set_tree(absl::cord_internal::CordRep* rep);
500 // Replaces a tree with a new root. This is faster than set_tree, but it
501 // should only be used when it's clear that the old rep was a tree.
502 void replace_tree(absl::cord_internal::CordRep* rep);
503 // Returns non-null iff was holding a pointer
504 absl::cord_internal::CordRep* clear();
505 // Convert to pointer if necessary
506 absl::cord_internal::CordRep* force_tree(size_t extra_hint);
507 void reduce_size(size_t n); // REQUIRES: holding data
508 void remove_prefix(size_t n); // REQUIRES: holding data
509 void AppendArray(const char* src_data, size_t src_size);
510 absl::string_view FindFlatStartPiece() const;
511 void AppendTree(absl::cord_internal::CordRep* tree);
512 void PrependTree(absl::cord_internal::CordRep* tree);
513 void GetAppendRegion(char** region, size_t* size, size_t max_length);
514 void GetAppendRegion(char** region, size_t* size);
IsSame(const InlineRep & other)515 bool IsSame(const InlineRep& other) const {
516 return memcmp(data_, other.data_, sizeof(data_)) == 0;
517 }
BitwiseCompare(const InlineRep & other)518 int BitwiseCompare(const InlineRep& other) const {
519 uint64_t x, y;
520 // Use memcpy to avoid anti-aliasing issues.
521 memcpy(&x, data_, sizeof(x));
522 memcpy(&y, other.data_, sizeof(y));
523 if (x == y) {
524 memcpy(&x, data_ + 8, sizeof(x));
525 memcpy(&y, other.data_ + 8, sizeof(y));
526 if (x == y) return 0;
527 }
528 return absl::big_endian::FromHost64(x) < absl::big_endian::FromHost64(y)
529 ? -1
530 : 1;
531 }
CopyTo(std::string * dst)532 void CopyTo(std::string* dst) const {
533 // memcpy is much faster when operating on a known size. On most supported
534 // platforms, the small std::string optimization is large enough that resizing
535 // to 15 bytes does not cause a memory allocation.
536 absl::strings_internal::STLStringResizeUninitialized(dst,
537 sizeof(data_) - 1);
538 memcpy(&(*dst)[0], data_, sizeof(data_) - 1);
539 // erase is faster than resize because the logic for memory allocation is
540 // not needed.
541 dst->erase(data_[kMaxInline]);
542 }
543
544 // Copies the inline contents into `dst`. Assumes the cord is not empty.
545 void CopyToArray(char* dst) const;
546
is_tree()547 bool is_tree() const { return data_[kMaxInline] > kMaxInline; }
548
549 private:
550 friend class Cord;
551
552 void AssignSlow(const InlineRep& src);
553 // Unrefs the tree, stops profiling, and zeroes the contents
554 void ClearSlow();
555
556 // If the data has length <= kMaxInline, we store it in data_[0..len-1],
557 // and store the length in data_[kMaxInline]. Else we store it in a tree
558 // and store a pointer to that tree in data_[0..sizeof(CordRep*)-1].
559 alignas(absl::cord_internal::CordRep*) char data_[kMaxInline + 1];
560 };
561 InlineRep contents_;
562
563 // Helper for MemoryUsage()
564 static size_t MemoryUsageAux(const absl::cord_internal::CordRep* rep);
565
566 // Helper for GetFlat()
567 static bool GetFlatAux(absl::cord_internal::CordRep* rep,
568 absl::string_view* fragment);
569
570 // Helper for ForEachChunk()
571 static void ForEachChunkAux(
572 absl::cord_internal::CordRep* rep,
573 absl::FunctionRef<void(absl::string_view)> callback);
574
575 // The destructor for non-empty Cords.
576 void DestroyCordSlow();
577
578 // Out-of-line implementation of slower parts of logic.
579 void CopyToArraySlowPath(char* dst) const;
580 int CompareSlowPath(absl::string_view rhs, size_t compared_size,
581 size_t size_to_compare) const;
582 int CompareSlowPath(const Cord& rhs, size_t compared_size,
583 size_t size_to_compare) const;
584 bool EqualsImpl(absl::string_view rhs, size_t size_to_compare) const;
585 bool EqualsImpl(const Cord& rhs, size_t size_to_compare) const;
586 int CompareImpl(const Cord& rhs) const;
587
588 template <typename ResultType, typename RHS>
589 friend ResultType GenericCompare(const Cord& lhs, const RHS& rhs,
590 size_t size_to_compare);
591 static absl::string_view GetFirstChunk(const Cord& c);
592 static absl::string_view GetFirstChunk(absl::string_view sv);
593
594 // Returns a new reference to contents_.tree(), or steals an existing
595 // reference if called on an rvalue.
596 absl::cord_internal::CordRep* TakeRep() const&;
597 absl::cord_internal::CordRep* TakeRep() &&;
598
599 // Helper for Append()
600 template <typename C>
601 void AppendImpl(C&& src);
602 };
603
604 ABSL_NAMESPACE_END
605 } // namespace absl
606
607 namespace absl {
608 ABSL_NAMESPACE_BEGIN
609
610 // allow a Cord to be logged
611 extern std::ostream& operator<<(std::ostream& out, const Cord& cord);
612
613 // ------------------------------------------------------------------
614 // Internal details follow. Clients should ignore.
615
616 namespace cord_internal {
617
618 // Fast implementation of memmove for up to 15 bytes. This implementation is
619 // safe for overlapping regions. If nullify_tail is true, the destination is
620 // padded with '\0' up to 16 bytes.
621 inline void SmallMemmove(char* dst, const char* src, size_t n,
622 bool nullify_tail = false) {
623 if (n >= 8) {
624 assert(n <= 16);
625 uint64_t buf1;
626 uint64_t buf2;
627 memcpy(&buf1, src, 8);
628 memcpy(&buf2, src + n - 8, 8);
629 if (nullify_tail) {
630 memset(dst + 8, 0, 8);
631 }
632 memcpy(dst, &buf1, 8);
633 memcpy(dst + n - 8, &buf2, 8);
634 } else if (n >= 4) {
635 uint32_t buf1;
636 uint32_t buf2;
637 memcpy(&buf1, src, 4);
638 memcpy(&buf2, src + n - 4, 4);
639 if (nullify_tail) {
640 memset(dst + 4, 0, 4);
641 memset(dst + 8, 0, 8);
642 }
643 memcpy(dst, &buf1, 4);
644 memcpy(dst + n - 4, &buf2, 4);
645 } else {
646 if (n != 0) {
647 dst[0] = src[0];
648 dst[n / 2] = src[n / 2];
649 dst[n - 1] = src[n - 1];
650 }
651 if (nullify_tail) {
652 memset(dst + 8, 0, 8);
653 memset(dst + n, 0, 8);
654 }
655 }
656 }
657
658 struct ExternalRepReleaserPair {
659 CordRep* rep;
660 void* releaser_address;
661 };
662
663 // Allocates a new external `CordRep` and returns a pointer to it and a pointer
664 // to `releaser_size` bytes where the desired releaser can be constructed.
665 // Expects `data` to be non-empty.
666 ExternalRepReleaserPair NewExternalWithUninitializedReleaser(
667 absl::string_view data, ExternalReleaserInvoker invoker,
668 size_t releaser_size);
669
670 // Creates a new `CordRep` that owns `data` and `releaser` and returns a pointer
671 // to it, or `nullptr` if `data` was empty.
672 template <typename Releaser>
673 // NOLINTNEXTLINE - suppress clang-tidy raw pointer return.
NewExternalRep(absl::string_view data,Releaser && releaser)674 CordRep* NewExternalRep(absl::string_view data, Releaser&& releaser) {
675 static_assert(
676 #if defined(__STDCPP_DEFAULT_NEW_ALIGNMENT__)
677 alignof(Releaser) <= __STDCPP_DEFAULT_NEW_ALIGNMENT__,
678 #else
679 alignof(Releaser) <= alignof(max_align_t),
680 #endif
681 "Releasers with alignment requirement greater than what is returned by "
682 "default `::operator new()` are not supported.");
683
684 using ReleaserType = absl::decay_t<Releaser>;
685 if (data.empty()) {
686 // Never create empty external nodes.
687 ::absl::base_internal::Invoke(
688 ReleaserType(std::forward<Releaser>(releaser)), data);
689 return nullptr;
690 }
691
692 auto releaser_invoker = [](void* type_erased_releaser, absl::string_view d) {
693 auto* my_releaser = static_cast<ReleaserType*>(type_erased_releaser);
694 ::absl::base_internal::Invoke(std::move(*my_releaser), d);
695 my_releaser->~ReleaserType();
696 return sizeof(Releaser);
697 };
698
699 ExternalRepReleaserPair external = NewExternalWithUninitializedReleaser(
700 data, releaser_invoker, sizeof(releaser));
701 ::new (external.releaser_address)
702 ReleaserType(std::forward<Releaser>(releaser));
703 return external.rep;
704 }
705
706 // Overload for function reference types that dispatches using a function
707 // pointer because there are no `alignof()` or `sizeof()` a function reference.
708 // NOLINTNEXTLINE - suppress clang-tidy raw pointer return.
NewExternalRep(absl::string_view data,void (& releaser)(absl::string_view))709 inline CordRep* NewExternalRep(absl::string_view data,
710 void (&releaser)(absl::string_view)) {
711 return NewExternalRep(data, &releaser);
712 }
713
714 } // namespace cord_internal
715
716 template <typename Releaser>
MakeCordFromExternal(absl::string_view data,Releaser && releaser)717 Cord MakeCordFromExternal(absl::string_view data, Releaser&& releaser) {
718 Cord cord;
719 cord.contents_.set_tree(::absl::cord_internal::NewExternalRep(
720 data, std::forward<Releaser>(releaser)));
721 return cord;
722 }
723
InlineRep(const Cord::InlineRep & src)724 inline Cord::InlineRep::InlineRep(const Cord::InlineRep& src) {
725 cord_internal::SmallMemmove(data_, src.data_, sizeof(data_));
726 }
727
InlineRep(Cord::InlineRep && src)728 inline Cord::InlineRep::InlineRep(Cord::InlineRep&& src) {
729 memcpy(data_, src.data_, sizeof(data_));
730 memset(src.data_, 0, sizeof(data_));
731 }
732
733 inline Cord::InlineRep& Cord::InlineRep::operator=(const Cord::InlineRep& src) {
734 if (this == &src) {
735 return *this;
736 }
737 if (!is_tree() && !src.is_tree()) {
738 cord_internal::SmallMemmove(data_, src.data_, sizeof(data_));
739 return *this;
740 }
741 AssignSlow(src);
742 return *this;
743 }
744
745 inline Cord::InlineRep& Cord::InlineRep::operator=(
746 Cord::InlineRep&& src) noexcept {
747 if (is_tree()) {
748 ClearSlow();
749 }
750 memcpy(data_, src.data_, sizeof(data_));
751 memset(src.data_, 0, sizeof(data_));
752 return *this;
753 }
754
Swap(Cord::InlineRep * rhs)755 inline void Cord::InlineRep::Swap(Cord::InlineRep* rhs) {
756 if (rhs == this) {
757 return;
758 }
759
760 Cord::InlineRep tmp;
761 cord_internal::SmallMemmove(tmp.data_, data_, sizeof(data_));
762 cord_internal::SmallMemmove(data_, rhs->data_, sizeof(data_));
763 cord_internal::SmallMemmove(rhs->data_, tmp.data_, sizeof(data_));
764 }
765
data()766 inline const char* Cord::InlineRep::data() const {
767 return is_tree() ? nullptr : data_;
768 }
769
tree()770 inline absl::cord_internal::CordRep* Cord::InlineRep::tree() const {
771 if (is_tree()) {
772 absl::cord_internal::CordRep* rep;
773 memcpy(&rep, data_, sizeof(rep));
774 return rep;
775 } else {
776 return nullptr;
777 }
778 }
779
empty()780 inline bool Cord::InlineRep::empty() const { return data_[kMaxInline] == 0; }
781
size()782 inline size_t Cord::InlineRep::size() const {
783 const char tag = data_[kMaxInline];
784 if (tag <= kMaxInline) return tag;
785 return static_cast<size_t>(tree()->length);
786 }
787
set_tree(absl::cord_internal::CordRep * rep)788 inline void Cord::InlineRep::set_tree(absl::cord_internal::CordRep* rep) {
789 if (rep == nullptr) {
790 memset(data_, 0, sizeof(data_));
791 } else {
792 bool was_tree = is_tree();
793 memcpy(data_, &rep, sizeof(rep));
794 memset(data_ + sizeof(rep), 0, sizeof(data_) - sizeof(rep) - 1);
795 if (!was_tree) {
796 data_[kMaxInline] = kTreeFlag;
797 }
798 }
799 }
800
replace_tree(absl::cord_internal::CordRep * rep)801 inline void Cord::InlineRep::replace_tree(absl::cord_internal::CordRep* rep) {
802 ABSL_ASSERT(is_tree());
803 if (ABSL_PREDICT_FALSE(rep == nullptr)) {
804 set_tree(rep);
805 return;
806 }
807 memcpy(data_, &rep, sizeof(rep));
808 memset(data_ + sizeof(rep), 0, sizeof(data_) - sizeof(rep) - 1);
809 }
810
clear()811 inline absl::cord_internal::CordRep* Cord::InlineRep::clear() {
812 const char tag = data_[kMaxInline];
813 absl::cord_internal::CordRep* result = nullptr;
814 if (tag > kMaxInline) {
815 memcpy(&result, data_, sizeof(result));
816 }
817 memset(data_, 0, sizeof(data_)); // Clear the cord
818 return result;
819 }
820
CopyToArray(char * dst)821 inline void Cord::InlineRep::CopyToArray(char* dst) const {
822 assert(!is_tree());
823 size_t n = data_[kMaxInline];
824 assert(n != 0);
825 cord_internal::SmallMemmove(dst, data_, n);
826 }
827
Cord()828 constexpr inline Cord::Cord() noexcept {}
829
830 inline Cord& Cord::operator=(const Cord& x) {
831 contents_ = x.contents_;
832 return *this;
833 }
834
Cord(Cord && src)835 inline Cord::Cord(Cord&& src) noexcept : contents_(std::move(src.contents_)) {}
836
837 inline Cord& Cord::operator=(Cord&& x) noexcept {
838 contents_ = std::move(x.contents_);
839 return *this;
840 }
841
842 template <typename T, Cord::EnableIfString<T>>
843 inline Cord& Cord::operator=(T&& src) {
844 *this = absl::string_view(src);
845 return *this;
846 }
847
size()848 inline size_t Cord::size() const {
849 // Length is 1st field in str.rep_
850 return contents_.size();
851 }
852
empty()853 inline bool Cord::empty() const { return contents_.empty(); }
854
EstimatedMemoryUsage()855 inline size_t Cord::EstimatedMemoryUsage() const {
856 size_t result = sizeof(Cord);
857 if (const absl::cord_internal::CordRep* rep = contents_.tree()) {
858 result += MemoryUsageAux(rep);
859 }
860 return result;
861 }
862
Flatten()863 inline absl::string_view Cord::Flatten() {
864 absl::cord_internal::CordRep* rep = contents_.tree();
865 if (rep == nullptr) {
866 return absl::string_view(contents_.data(), contents_.size());
867 } else {
868 absl::string_view already_flat_contents;
869 if (GetFlatAux(rep, &already_flat_contents)) {
870 return already_flat_contents;
871 }
872 }
873 return FlattenSlowPath();
874 }
875
Append(absl::string_view src)876 inline void Cord::Append(absl::string_view src) {
877 contents_.AppendArray(src.data(), src.size());
878 }
879
880 template <typename T, Cord::EnableIfString<T>>
Append(T && src)881 inline void Cord::Append(T&& src) {
882 // Note that this function reserves the right to reuse the `string&&`'s
883 // memory and that it will do so in the future.
884 Append(absl::string_view(src));
885 }
886
887 template <typename T, Cord::EnableIfString<T>>
Prepend(T && src)888 inline void Cord::Prepend(T&& src) {
889 // Note that this function reserves the right to reuse the `string&&`'s
890 // memory and that it will do so in the future.
891 Prepend(absl::string_view(src));
892 }
893
Compare(const Cord & rhs)894 inline int Cord::Compare(const Cord& rhs) const {
895 if (!contents_.is_tree() && !rhs.contents_.is_tree()) {
896 return contents_.BitwiseCompare(rhs.contents_);
897 }
898
899 return CompareImpl(rhs);
900 }
901
902 // Does 'this' cord start/end with rhs
StartsWith(const Cord & rhs)903 inline bool Cord::StartsWith(const Cord& rhs) const {
904 if (contents_.IsSame(rhs.contents_)) return true;
905 size_t rhs_size = rhs.size();
906 if (size() < rhs_size) return false;
907 return EqualsImpl(rhs, rhs_size);
908 }
909
StartsWith(absl::string_view rhs)910 inline bool Cord::StartsWith(absl::string_view rhs) const {
911 size_t rhs_size = rhs.size();
912 if (size() < rhs_size) return false;
913 return EqualsImpl(rhs, rhs_size);
914 }
915
ChunkIterator(const Cord * cord)916 inline Cord::ChunkIterator::ChunkIterator(const Cord* cord)
917 : bytes_remaining_(cord->size()) {
918 if (cord->empty()) return;
919 if (cord->contents_.is_tree()) {
920 stack_of_right_children_.push_back(cord->contents_.tree());
921 operator++();
922 } else {
923 current_chunk_ = absl::string_view(cord->contents_.data(), cord->size());
924 }
925 }
926
927 inline Cord::ChunkIterator Cord::ChunkIterator::operator++(int) {
928 ChunkIterator tmp(*this);
929 operator++();
930 return tmp;
931 }
932
933 inline bool Cord::ChunkIterator::operator==(const ChunkIterator& other) const {
934 return bytes_remaining_ == other.bytes_remaining_;
935 }
936
937 inline bool Cord::ChunkIterator::operator!=(const ChunkIterator& other) const {
938 return !(*this == other);
939 }
940
941 inline Cord::ChunkIterator::reference Cord::ChunkIterator::operator*() const {
942 assert(bytes_remaining_ != 0);
943 return current_chunk_;
944 }
945
946 inline Cord::ChunkIterator::pointer Cord::ChunkIterator::operator->() const {
947 assert(bytes_remaining_ != 0);
948 return ¤t_chunk_;
949 }
950
RemoveChunkPrefix(size_t n)951 inline void Cord::ChunkIterator::RemoveChunkPrefix(size_t n) {
952 assert(n < current_chunk_.size());
953 current_chunk_.remove_prefix(n);
954 bytes_remaining_ -= n;
955 }
956
AdvanceBytes(size_t n)957 inline void Cord::ChunkIterator::AdvanceBytes(size_t n) {
958 if (ABSL_PREDICT_TRUE(n < current_chunk_.size())) {
959 RemoveChunkPrefix(n);
960 } else if (n != 0) {
961 AdvanceBytesSlowPath(n);
962 }
963 }
964
chunk_begin()965 inline Cord::ChunkIterator Cord::chunk_begin() const {
966 return ChunkIterator(this);
967 }
968
chunk_end()969 inline Cord::ChunkIterator Cord::chunk_end() const { return ChunkIterator(); }
970
begin()971 inline Cord::ChunkIterator Cord::ChunkRange::begin() const {
972 return cord_->chunk_begin();
973 }
974
end()975 inline Cord::ChunkIterator Cord::ChunkRange::end() const {
976 return cord_->chunk_end();
977 }
978
Chunks()979 inline Cord::ChunkRange Cord::Chunks() const { return ChunkRange(this); }
980
981 inline Cord::CharIterator& Cord::CharIterator::operator++() {
982 if (ABSL_PREDICT_TRUE(chunk_iterator_->size() > 1)) {
983 chunk_iterator_.RemoveChunkPrefix(1);
984 } else {
985 ++chunk_iterator_;
986 }
987 return *this;
988 }
989
990 inline Cord::CharIterator Cord::CharIterator::operator++(int) {
991 CharIterator tmp(*this);
992 operator++();
993 return tmp;
994 }
995
996 inline bool Cord::CharIterator::operator==(const CharIterator& other) const {
997 return chunk_iterator_ == other.chunk_iterator_;
998 }
999
1000 inline bool Cord::CharIterator::operator!=(const CharIterator& other) const {
1001 return !(*this == other);
1002 }
1003
1004 inline Cord::CharIterator::reference Cord::CharIterator::operator*() const {
1005 return *chunk_iterator_->data();
1006 }
1007
1008 inline Cord::CharIterator::pointer Cord::CharIterator::operator->() const {
1009 return chunk_iterator_->data();
1010 }
1011
AdvanceAndRead(CharIterator * it,size_t n_bytes)1012 inline Cord Cord::AdvanceAndRead(CharIterator* it, size_t n_bytes) {
1013 assert(it != nullptr);
1014 return it->chunk_iterator_.AdvanceAndReadBytes(n_bytes);
1015 }
1016
Advance(CharIterator * it,size_t n_bytes)1017 inline void Cord::Advance(CharIterator* it, size_t n_bytes) {
1018 assert(it != nullptr);
1019 it->chunk_iterator_.AdvanceBytes(n_bytes);
1020 }
1021
ChunkRemaining(const CharIterator & it)1022 inline absl::string_view Cord::ChunkRemaining(const CharIterator& it) {
1023 return *it.chunk_iterator_;
1024 }
1025
char_begin()1026 inline Cord::CharIterator Cord::char_begin() const {
1027 return CharIterator(this);
1028 }
1029
char_end()1030 inline Cord::CharIterator Cord::char_end() const { return CharIterator(); }
1031
begin()1032 inline Cord::CharIterator Cord::CharRange::begin() const {
1033 return cord_->char_begin();
1034 }
1035
end()1036 inline Cord::CharIterator Cord::CharRange::end() const {
1037 return cord_->char_end();
1038 }
1039
Chars()1040 inline Cord::CharRange Cord::Chars() const { return CharRange(this); }
1041
ForEachChunk(absl::FunctionRef<void (absl::string_view)> callback)1042 inline void Cord::ForEachChunk(
1043 absl::FunctionRef<void(absl::string_view)> callback) const {
1044 absl::cord_internal::CordRep* rep = contents_.tree();
1045 if (rep == nullptr) {
1046 callback(absl::string_view(contents_.data(), contents_.size()));
1047 } else {
1048 return ForEachChunkAux(rep, callback);
1049 }
1050 }
1051
1052 // Nonmember Cord-to-Cord relational operarators.
1053 inline bool operator==(const Cord& lhs, const Cord& rhs) {
1054 if (lhs.contents_.IsSame(rhs.contents_)) return true;
1055 size_t rhs_size = rhs.size();
1056 if (lhs.size() != rhs_size) return false;
1057 return lhs.EqualsImpl(rhs, rhs_size);
1058 }
1059
1060 inline bool operator!=(const Cord& x, const Cord& y) { return !(x == y); }
1061 inline bool operator<(const Cord& x, const Cord& y) {
1062 return x.Compare(y) < 0;
1063 }
1064 inline bool operator>(const Cord& x, const Cord& y) {
1065 return x.Compare(y) > 0;
1066 }
1067 inline bool operator<=(const Cord& x, const Cord& y) {
1068 return x.Compare(y) <= 0;
1069 }
1070 inline bool operator>=(const Cord& x, const Cord& y) {
1071 return x.Compare(y) >= 0;
1072 }
1073
1074 // Nonmember Cord-to-absl::string_view relational operators.
1075 //
1076 // Due to implicit conversions, these also enable comparisons of Cord with
1077 // with std::string, ::string, and const char*.
1078 inline bool operator==(const Cord& lhs, absl::string_view rhs) {
1079 size_t lhs_size = lhs.size();
1080 size_t rhs_size = rhs.size();
1081 if (lhs_size != rhs_size) return false;
1082 return lhs.EqualsImpl(rhs, rhs_size);
1083 }
1084
1085 inline bool operator==(absl::string_view x, const Cord& y) { return y == x; }
1086 inline bool operator!=(const Cord& x, absl::string_view y) { return !(x == y); }
1087 inline bool operator!=(absl::string_view x, const Cord& y) { return !(x == y); }
1088 inline bool operator<(const Cord& x, absl::string_view y) {
1089 return x.Compare(y) < 0;
1090 }
1091 inline bool operator<(absl::string_view x, const Cord& y) {
1092 return y.Compare(x) > 0;
1093 }
1094 inline bool operator>(const Cord& x, absl::string_view y) { return y < x; }
1095 inline bool operator>(absl::string_view x, const Cord& y) { return y < x; }
1096 inline bool operator<=(const Cord& x, absl::string_view y) { return !(y < x); }
1097 inline bool operator<=(absl::string_view x, const Cord& y) { return !(y < x); }
1098 inline bool operator>=(const Cord& x, absl::string_view y) { return !(x < y); }
1099 inline bool operator>=(absl::string_view x, const Cord& y) { return !(x < y); }
1100
1101 // Overload of swap for Cord. The use of non-const references is
1102 // required. :(
swap(Cord & x,Cord & y)1103 inline void swap(Cord& x, Cord& y) noexcept { y.contents_.Swap(&x.contents_); }
1104
1105 // Some internals exposed to test code.
1106 namespace strings_internal {
1107 class CordTestAccess {
1108 public:
1109 static size_t FlatOverhead();
1110 static size_t MaxFlatLength();
1111 static size_t SizeofCordRepConcat();
1112 static size_t SizeofCordRepExternal();
1113 static size_t SizeofCordRepSubstring();
1114 static size_t FlatTagToLength(uint8_t tag);
1115 static uint8_t LengthToTag(size_t s);
1116 };
1117 } // namespace strings_internal
1118 ABSL_NAMESPACE_END
1119 } // namespace absl
1120
1121 #endif // ABSL_STRINGS_CORD_H_
1122