summaryrefslogtreecommitdiff
path: root/absl/strings/internal/cord_rep_ring.h
blob: 2082a5653f492b649c0fdd59400e248b79de890d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
// Copyright 2020 The Abseil Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_
#define ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iosfwd>
#include <limits>
#include <memory>

#include "absl/container/internal/layout.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_flat.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {

// All operations modifying a ring buffer are implemented as static methods
// requiring a CordRepRing instance with a reference adopted by the method.
//
// The methods return the modified ring buffer, which may be equal to the input
// if the input was not shared, and having large enough capacity to accommodate
// any newly added node(s). Otherwise, a copy of the input rep with the new
// node(s) added is returned.
//
// Any modification on non shared ring buffers with enough capacity will then
// require minimum atomic operations. Caller should where possible provide
// reasonable `extra` hints for both anticipated extra `flat` byte space, as
// well as anticipated extra nodes required for complex operations.
//
// Example of code creating a ring buffer, adding some data to it,
// and discarding the buffer when done:
//
//   void FunWithRings() {
//     // Create ring with 3 flats
//     CordRep* flat = CreateFlat("Hello");
//     CordRepRing* ring = CordRepRing::Create(flat, 2);
//     ring = CordRepRing::Append(ring, CreateFlat(" "));
//     ring = CordRepRing::Append(ring, CreateFlat("world"));
//     DoSomethingWithRing(ring);
//     CordRep::Unref(ring);
//   }
//
// Example of code Copying an existing ring buffer and modifying it:
//
//   void MoreFunWithRings(CordRepRing* src) {
//     CordRepRing* ring = CordRep::Ref(src)->ring();
//     ring = CordRepRing::Append(ring, CreateFlat("Hello"));
//     ring = CordRepRing::Append(ring, CreateFlat(" "));
//     ring = CordRepRing::Append(ring, CreateFlat("world"));
//     DoSomethingWithRing(ring);
//     CordRep::Unref(ring);
//   }
//
class CordRepRing : public CordRep {
 public:
  // `pos_type` represents a 'logical position'. A CordRepRing instance has a
  // `begin_pos` (default 0), and each node inside the buffer will have an
  // `end_pos` which is the `end_pos` of the previous node (or `begin_pos`) plus
  // this node's length. The purpose is to allow for a binary search on this
  // position, while allowing O(1) prepend and append operations.
  using pos_type = size_t;

  // `index_type` is the type for the `head`, `tail` and `capacity` indexes.
  // Ring buffers are limited to having no more than four billion entries.
  using index_type = uint32_t;

  // `offset_type` is the type for the data offset inside a child rep's data.
  using offset_type = uint32_t;

  // Position holds the node index and relative offset into the node for
  // some physical offset in the contained data as returned by the Find()
  // and FindTail() methods.
  struct Position {
    index_type index;
    size_t offset;
  };

  // The maximum # of child nodes that can be hosted inside a CordRepRing.
  static constexpr size_t kMaxCapacity = (std::numeric_limits<uint32_t>::max)();

  // CordRepring can not be default constructed, moved, copied or assigned.
  CordRepRing() = delete;
  CordRepRing(const CordRepRing&) = delete;
  CordRepRing& operator=(const CordRepRing&) = delete;

  // Returns true if this instance is valid, false if some or all of the
  // invariants are broken. Intended for debug purposes only.
  // `output` receives an explanation of the broken invariants.
  bool IsValid(std::ostream& output) const;

  // Returns the size in bytes for a CordRepRing with `capacity' entries.
  static constexpr size_t AllocSize(size_t capacity);

  // Returns the distance in bytes from `pos` to `end_pos`.
  static constexpr size_t Distance(pos_type pos, pos_type end_pos);

  // Creates a new ring buffer from the provided `rep`. Adopts a reference
  // on `rep`. The returned ring buffer has a capacity of at least `extra + 1`
  static CordRepRing* Create(CordRep* child, size_t extra = 0);

  // `head`, `tail` and `capacity` indexes defining the ring buffer boundaries.
  index_type head() const { return head_; }
  index_type tail() const { return tail_; }
  index_type capacity() const { return capacity_; }

  // Returns the number of entries in this instance.
  index_type entries() const { return entries(head_, tail_); }

  // Returns the logical begin position of this instance.
  pos_type begin_pos() const { return begin_pos_; }

  // Returns the number of entries for a given head-tail range.
  // Requires `head` and `tail` values to be less than `capacity()`.
  index_type entries(index_type head, index_type tail) const {
    assert(head < capacity_ && tail < capacity_);
    return tail - head + ((tail > head) ? 0 : capacity_);
  }

  // Returns the logical end position of entry `index`.
  pos_type const& entry_end_pos(index_type index) const {
    assert(IsValidIndex(index));
    return Layout::Partial().Pointer<0>(data_)[index];
  }

  // Returns the child pointer of entry `index`.
  CordRep* const& entry_child(index_type index) const {
    assert(IsValidIndex(index));
    return Layout::Partial(capacity()).Pointer<1>(data_)[index];
  }

  // Returns the data offset of entry `index`
  offset_type const& entry_data_offset(index_type index) const {
    assert(IsValidIndex(index));
    return Layout::Partial(capacity(), capacity()).Pointer<2>(data_)[index];
  }

  // Appends the provided child node to the `rep` instance.
  // Adopts a reference from `rep` and `child` which may not be null.
  // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node
  // containing a FLAT or EXTERNAL node, then flat or external the node is added
  // 'as is', with an offset added for the SUBSTRING case.
  // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING or
  // CONCAT tree, then all child nodes not excluded by any start offset or
  // length values are added recursively.
  static CordRepRing* Append(CordRepRing* rep, CordRep* child);

  // Appends the provided string data to the `rep` instance.
  // This function will attempt to utilize any remaining capacity in the last
  // node of the input if that node is not shared (directly or indirectly), and
  // of type FLAT. Remaining data will be added as one or more FLAT nodes.
  // Any last node added to the ring buffer will be allocated with up to
  // `extra` bytes of capacity for (anticipated) subsequent append actions.
  static CordRepRing* Append(CordRepRing* rep, string_view data,
                             size_t extra = 0);

  // Prepends the provided child node to the `rep` instance.
  // Adopts a reference from `rep` and `child` which may not be null.
  // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node
  // containing a FLAT or EXTERNAL node, then flat or external the node is
  // prepended 'as is', with an optional offset added for the SUBSTRING case.
  // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING
  // or CONCAT tree, then all child nodes not excluded by any start offset or
  // length values are added recursively.
  static CordRepRing* Prepend(CordRepRing* rep, CordRep* child);

  // Prepends the provided string data to the `rep` instance.
  // This function will attempt to utilize any remaining capacity in the first
  // node of the input if that node is not shared (directly or indirectly), and
  // of type FLAT. Remaining data will be added as one or more FLAT nodes.
  // Any first node prepnded to the ring buffer will be allocated with up to
  // `extra` bytes of capacity for (anticipated) subsequent prepend actions.
  static CordRepRing* Prepend(CordRepRing* rep, string_view data,
                              size_t extra = 0);

  // Returns a span referencing potentially unused capacity in the last node.
  // The returned span may be empty if no such capacity is available, or if the
  // current instance is shared. Else, a span of size `n <= size` is returned.
  // If non empty, the ring buffer is adjusted to the new length, with the newly
  // added capacity left uninitialized. Callers should assign a value to the
  // entire span before any other operations on this instance.
  Span<char> GetAppendBuffer(size_t size);

  // Returns a span referencing potentially unused capacity in the first node.
  // This function is identical to GetAppendBuffer except that it returns a span
  // referencing up to `size` capacity directly before the existing data.
  Span<char> GetPrependBuffer(size_t size);

  // Returns a cord ring buffer containing `len` bytes of data starting at
  // `offset`. If the input is not shared, this function will remove all head
  // and tail child nodes outside of the requested range, and adjust the new
  // head and tail nodes as required. If the input is shared, this function
  // returns a new instance sharing some or all of the nodes from the input.
  static CordRepRing* SubRing(CordRepRing* r, size_t offset, size_t len,
                              size_t extra = 0);

  // Returns a cord ring buffer with the first `len` bytes removed.
  // If the input is not shared, this function will remove all head child nodes
  // fully inside the first `length` bytes, and adjust the new head as required.
  // If the input is shared, this function returns a new instance sharing some
  // or all of the nodes from the input.
  static CordRepRing* RemoveSuffix(CordRepRing* r, size_t len,
                                   size_t extra = 0);

  // Returns a cord ring buffer with the last `len` bytes removed.
  // If the input is not shared, this function will remove all head child nodes
  // fully inside the first `length` bytes, and adjust the new head as required.
  // If the input is shared, this function returns a new instance sharing some
  // or all of the nodes from the input.
  static CordRepRing* RemovePrefix(CordRepRing* r, size_t len,
                                   size_t extra = 0);

  // Returns the character at `offset`. Requires that `offset < length`.
  char GetCharacter(size_t offset) const;

  // Returns true if this instance manages a single contiguous buffer, in which
  // case the (optional) output parameter `fragment` is set. Otherwise, the
  // function returns false, and `fragment` is left unchanged.
  bool IsFlat(absl::string_view* fragment) const;

  // Returns true if the data starting at `offset` with length `len` is
  // managed by this instance inside a single contiguous buffer, in which case
  // the (optional) output parameter `fragment` is set to the contiguous memory
  // starting at offset `offset` with length `length`. Otherwise, the function
  // returns false, and `fragment` is left unchanged.
  bool IsFlat(size_t offset, size_t len, absl::string_view* fragment) const;

  // Testing only: set capacity to requested capacity.
  void SetCapacityForTesting(size_t capacity);

  // Returns the CordRep data pointer for the provided CordRep.
  // Requires that the provided `rep` is either a FLAT or EXTERNAL CordRep.
  static const char* GetLeafData(const CordRep* rep);

  // Returns the CordRep data pointer for the provided CordRep.
  // Requires that `rep` is either a FLAT, EXTERNAL, or SUBSTRING CordRep.
  static const char* GetRepData(const CordRep* rep);

  // Advances the provided position, wrapping around capacity as needed.
  // Requires `index` < capacity()
  inline index_type advance(index_type index) const;

  // Advances the provided position by 'n`, wrapping around capacity as needed.
  // Requires `index` < capacity() and `n` <= capacity.
  inline index_type advance(index_type index, index_type n) const;

  // Retreats the provided position, wrapping around 0 as needed.
  // Requires `index` < capacity()
  inline index_type retreat(index_type index) const;

  // Retreats the provided position by 'n', wrapping around 0 as needed.
  // Requires `index` < capacity()
  inline index_type retreat(index_type index, index_type n) const;

  // Returns the logical begin position of entry `index`
  pos_type const& entry_begin_pos(index_type index) const {
    return (index == head_) ? begin_pos_ : entry_end_pos(retreat(index));
  }

  // Returns the physical start offset of entry `index`
  size_t entry_start_offset(index_type index) const {
    return Distance(begin_pos_, entry_begin_pos(index));
  }

  // Returns the physical end offset of entry `index`
  size_t entry_end_offset(index_type index) const {
    return Distance(begin_pos_, entry_end_pos(index));
  }

  // Returns the data length for entry `index`
  size_t entry_length(index_type index) const {
    return Distance(entry_begin_pos(index), entry_end_pos(index));
  }

  // Returns the data for entry `index`
  absl::string_view entry_data(index_type index) const;

  // Returns the position for `offset` as {index, prefix}. `index` holds the
  // index of the entry at the specified offset and `prefix` holds the relative
  // offset inside that entry.
  // Requires `offset` < length.
  //
  // For example we can implement GetCharacter(offset) as:
  //   char GetCharacter(size_t offset) {
  //     Position pos = this->Find(offset);
  //     return this->entry_data(pos.pos)[pos.offset];
  //   }
  inline Position Find(size_t offset) const;

  // Find starting at `head`
  inline Position Find(index_type head, size_t offset) const;

  // Returns the tail position for `offset` as {tail index, suffix}.
  // `tail index` holds holds the index of the entry holding the offset directly
  // before 'offset` advanced by one. 'suffix` holds the relative offset from
  // that relative offset in the entry to the end of the entry.
  // For example, FindTail(length) will return {tail(), 0}, FindTail(length - 5)
  // will return {retreat(tail), 5)} provided the preceding entry contains at
  // least 5 bytes of data.
  // Requires offset >= 1 && offset <= length.
  //
  // This function is very useful in functions that need to clip the end of some
  // ring buffer such as 'RemovePrefix'.
  // For example, we could implement RemovePrefix for non shared instances as:
  //   void RemoveSuffix(size_t n) {
  //     Position pos = FindTail(length - n);
  //     UnrefEntries(pos.pos, this->tail_);
  //     this->tail_ = pos.pos;
  //     entry(retreat(pos.pos)).end_pos -= pos.offset;
  //   }
  inline Position FindTail(size_t offset) const;

  // Find tail starting at `head`
  inline Position FindTail(index_type head, size_t offset) const;

  // Invokes f(index_type index) for each entry inside the range [head, tail>
  template <typename F>
  void ForEach(index_type head, index_type tail, F&& f) const {
    index_type n1 = (tail > head) ? tail : capacity_;
    for (index_type i = head; i < n1; ++i) f(i);
    if (tail <= head) {
      for (index_type i = 0; i < tail; ++i) f(i);
    }
  }

  // Invokes f(index_type index) for each entry inside this instance.
  template <typename F>
  void ForEach(F&& f) const {
    ForEach(head_, tail_, std::forward<F>(f));
  }

  // Dump this instance's data tp stream `s` in human readable format, excluding
  // the actual data content itself. Intended for debug purposes only.
  friend std::ostream& operator<<(std::ostream& s, const CordRepRing& rep);

 private:
  enum class AddMode { kAppend, kPrepend };

  using Layout = container_internal::Layout<pos_type, CordRep*, offset_type>;

  class Filler;
  class Transaction;
  class CreateTransaction;

  static constexpr size_t kLayoutAlignment = Layout::Partial().Alignment();

  // Creates a new CordRepRing.
  explicit CordRepRing(index_type capacity) : capacity_(capacity) {}

  // Returns true if `index` is a valid index into this instance.
  bool IsValidIndex(index_type index) const;

  // Debug use only: validates the provided CordRepRing invariants.
  // Verification of all CordRepRing methods can be enabled by defining
  // EXTRA_CORD_RING_VALIDATION, i.e.: `--copts=-DEXTRA_CORD_RING_VALIDATION`
  // Verification is VERY expensive, so only do it for debugging purposes.
  static CordRepRing* Validate(CordRepRing* rep, const char* file = nullptr,
                               int line = 0);

  // Allocates a CordRepRing large enough to hold `capacity + extra' entries.
  // The returned capacity may be larger if the allocated memory allows for it.
  // The maximum capacity of a CordRepRing is capped at kMaxCapacity.
  // Throws `std::length_error` if `capacity + extra' exceeds kMaxCapacity.
  static CordRepRing* New(size_t capacity, size_t extra);

  // Deallocates (but does not destroy) the provided ring buffer.
  static void Delete(CordRepRing* rep);

  // Destroys the provided ring buffer, decrementing the reference count of all
  // contained child CordReps. The provided 1\`rep` should have a ref count of
  // one (pre decrement destroy call observing `refcount.IsOne()`) or zero (post
  // decrement destroy call observing `!refcount.Decrement()`).
  static void Destroy(CordRepRing* rep);

  // Returns a mutable reference to the logical end position array.
  pos_type* entry_end_pos() {
    return Layout::Partial().Pointer<0>(data_);
  }

  // Returns a mutable reference to the child pointer array.
  CordRep** entry_child() {
    return Layout::Partial(capacity()).Pointer<1>(data_);
  }

  // Returns a mutable reference to the data offset array.
  offset_type* entry_data_offset() {
    return Layout::Partial(capacity(), capacity()).Pointer<2>(data_);
  }

  // Find implementations for the non fast path 0 / length cases.
  Position FindSlow(index_type head, size_t offset) const;
  Position FindTailSlow(index_type head, size_t offset) const;

  // Finds the index of the first node that is inside a reasonable distance
  // of the node at `offset` from which we can continue with a linear search.
  template <bool wrap>
  index_type FindBinary(index_type head, index_type tail, size_t offset) const;

  // Fills the current (initialized) instance from the provided source, copying
  // entries [head, tail). Adds a reference to copied entries if `ref` is true.
  template <bool ref>
  void Fill(const CordRepRing* src, index_type head, index_type tail);

  // Create a copy of 'rep', copying all entries [head, tail), allocating room
  // for `extra` entries. Adds a reference on all copied entries.
  static CordRepRing* Copy(CordRepRing* rep, index_type head, index_type tail,
                           size_t extra = 0);

  // Returns a Mutable CordRepRing reference from `rep` with room for at least
  // `extra` additional nodes. Adopts a reference count from `rep`.
  // This function will return `rep` if, and only if:
  // - rep.entries + extra <= rep.capacity
  // - rep.refcount == 1
  // Otherwise, this function will create a new copy of `rep` with additional
  // capacity to satisfy `extra` extra nodes, and unref the old `rep` instance.
  //
  // If a new CordRepRing can not be allocated, or the new capacity would exceed
  // the maxmimum capacity, then the input is consumed only, and an exception is
  // thrown.
  static CordRepRing* Mutable(CordRepRing* rep, size_t extra);

  // Slow path for Append(CordRepRing* rep, CordRep* child). This function is
  // exercised if the provided `child` in Append() is not a leaf node, i.e., a
  // ring buffer or old (concat) cord tree.
  static CordRepRing* AppendSlow(CordRepRing* rep, CordRep* child);

  // Appends the provided leaf node. Requires `child` to be FLAT or EXTERNAL.
  static CordRepRing* AppendLeaf(CordRepRing* rep, CordRep* child,
                                 size_t offset, size_t length);

  // Prepends the provided leaf node. Requires `child` to be FLAT or EXTERNAL.
  static CordRepRing* PrependLeaf(CordRepRing* rep, CordRep* child,
                                  size_t offset, size_t length);

  // Slow path for Prepend(CordRepRing* rep, CordRep* child). This function is
  // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a
  // ring buffer or old (concat) cord tree.
  static CordRepRing* PrependSlow(CordRepRing* rep, CordRep* child);

  // Slow path for Create(CordRep* child, size_t extra). This function is
  // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a
  // ring buffer or old (concat) cord tree.
  static CordRepRing* CreateSlow(CordRep* child, size_t extra);

  // Creates a new ring buffer from the provided `child` leaf node. Requires
  // `child` to be FLAT or EXTERNAL. on `rep`.
  // The returned ring buffer has a capacity of at least `1 + extra`
  static CordRepRing* CreateFromLeaf(CordRep* child, size_t offset,
                                     size_t length, size_t extra);

  // Appends or prepends (depending on AddMode) the ring buffer in `ring' to
  // `rep` starting at `offset` with length `len`.
  template <AddMode mode>
  static CordRepRing* AddRing(CordRepRing* rep, CordRepRing* ring,
                              size_t offset, size_t len);

  // Increases the data offset for entry `index` by `n`.
  void AddDataOffset(index_type index, size_t n);

  // Descreases the length for entry `index` by `n`.
  void SubLength(index_type index, size_t n);

  index_type head_;
  index_type tail_;
  index_type capacity_;
  pos_type begin_pos_;

  alignas(kLayoutAlignment) char data_[kLayoutAlignment];

  friend struct CordRep;
};

constexpr size_t CordRepRing::AllocSize(size_t capacity) {
  return sizeof(CordRepRing) - sizeof(data_) +
         Layout(capacity, capacity, capacity).AllocSize();
}

inline constexpr size_t CordRepRing::Distance(pos_type pos, pos_type end_pos) {
  return (end_pos - pos);
}

inline const char* CordRepRing::GetLeafData(const CordRep* rep) {
  return rep->tag != EXTERNAL ? rep->flat()->Data() : rep->external()->base;
}

inline const char* CordRepRing::GetRepData(const CordRep* rep) {
  if (rep->tag >= FLAT) return rep->flat()->Data();
  if (rep->tag == EXTERNAL) return rep->external()->base;
  return GetLeafData(rep->substring()->child) + rep->substring()->start;
}

inline CordRepRing::index_type CordRepRing::advance(index_type index) const {
  assert(index < capacity_);
  return ++index == capacity_ ? 0 : index;
}

inline CordRepRing::index_type CordRepRing::advance(index_type index,
                                                    index_type n) const {
  assert(index < capacity_ && n <= capacity_);
  return (index += n) >= capacity_ ? index - capacity_ : index;
}

inline CordRepRing::index_type CordRepRing::retreat(index_type index) const {
  assert(index < capacity_);
  return (index > 0 ? index : capacity_) - 1;
}

inline CordRepRing::index_type CordRepRing::retreat(index_type index,
                                                    index_type n) const {
  assert(index < capacity_ && n <= capacity_);
  return index >= n ? index - n : capacity_ - n + index;
}

inline absl::string_view CordRepRing::entry_data(index_type index) const {
  size_t data_offset = entry_data_offset(index);
  return {GetRepData(entry_child(index)) + data_offset, entry_length(index)};
}

inline bool CordRepRing::IsValidIndex(index_type index) const {
  if (index >= capacity_) return false;
  return (tail_ > head_) ? (index >= head_ && index < tail_)
                         : (index >= head_ || index < tail_);
}

#ifndef EXTRA_CORD_RING_VALIDATION
inline CordRepRing* CordRepRing::Validate(CordRepRing* rep,
                                          const char* /*file*/, int /*line*/) {
  return rep;
}
#endif

inline CordRepRing::Position CordRepRing::Find(size_t offset) const {
  assert(offset < length);
  return (offset == 0) ? Position{head_, 0} : FindSlow(head_, offset);
}

inline CordRepRing::Position CordRepRing::Find(index_type head,
                                               size_t offset) const {
  assert(offset < length);
  assert(IsValidIndex(head) && offset >= entry_start_offset(head));
  return (offset == 0) ? Position{head_, 0} : FindSlow(head, offset);
}

inline CordRepRing::Position CordRepRing::FindTail(size_t offset) const {
  assert(offset > 0 && offset <= length);
  return (offset == length) ? Position{tail_, 0} : FindTailSlow(head_, offset);
}

inline CordRepRing::Position CordRepRing::FindTail(index_type head,
                                                   size_t offset) const {
  assert(offset > 0 && offset <= length);
  assert(IsValidIndex(head) && offset >= entry_start_offset(head) + 1);
  return (offset == length) ? Position{tail_, 0} : FindTailSlow(head, offset);
}

// Now that CordRepRing is defined, we can define CordRep's helper casts:
inline CordRepRing* CordRep::ring() {
  assert(tag == RING);
  return static_cast<CordRepRing*>(this);
}

inline const CordRepRing* CordRep::ring() const {
  assert(tag == RING);
  return static_cast<const CordRepRing*>(this);
}

inline bool CordRepRing::IsFlat(absl::string_view* fragment) const {
  if (entries() == 1) {
    if (fragment) *fragment = entry_data(head());
    return true;
  }
  return false;
}

inline bool CordRepRing::IsFlat(size_t offset, size_t len,
                                absl::string_view* fragment) const {
  const Position pos = Find(offset);
  const absl::string_view data = entry_data(pos.index);
  if (data.length() >= len && data.length() - len >= pos.offset) {
    if (fragment) *fragment = data.substr(pos.offset, len);
    return true;
  }
  return false;
}

std::ostream& operator<<(std::ostream& s, const CordRepRing& rep);

}  // namespace cord_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_