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