diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/strings/internal/cord_rep_ring.cc')
| -rw-r--r-- | third_party/abseil-cpp/absl/strings/internal/cord_rep_ring.cc | 771 |
1 files changed, 0 insertions, 771 deletions
diff --git a/third_party/abseil-cpp/absl/strings/internal/cord_rep_ring.cc b/third_party/abseil-cpp/absl/strings/internal/cord_rep_ring.cc deleted file mode 100644 index 07c77eb3e5..0000000000 --- a/third_party/abseil-cpp/absl/strings/internal/cord_rep_ring.cc +++ /dev/null @@ -1,771 +0,0 @@ -// 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. -#include "absl/strings/internal/cord_rep_ring.h" - -#include <cassert> -#include <cstddef> -#include <cstdint> -#include <iostream> -#include <limits> -#include <memory> -#include <string> - -#include "absl/base/internal/raw_logging.h" -#include "absl/base/internal/throw_delegate.h" -#include "absl/base/macros.h" -#include "absl/container/inlined_vector.h" -#include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_consume.h" -#include "absl/strings/internal/cord_rep_flat.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -namespace { - -using index_type = CordRepRing::index_type; - -enum class Direction { kForward, kReversed }; - -inline bool IsFlatOrExternal(CordRep* rep) { - return rep->IsFlat() || rep->IsExternal(); -} - -// Verifies that n + extra <= kMaxCapacity: throws std::length_error otherwise. -inline void CheckCapacity(size_t n, size_t extra) { - if (ABSL_PREDICT_FALSE(extra > CordRepRing::kMaxCapacity - n)) { - base_internal::ThrowStdLengthError("Maximum capacity exceeded"); - } -} - -// Creates a flat from the provided string data, allocating up to `extra` -// capacity in the returned flat depending on kMaxFlatLength limitations. -// Requires `len` to be less or equal to `kMaxFlatLength` -CordRepFlat* CreateFlat(const char* s, size_t n, size_t extra = 0) { // NOLINT - assert(n <= kMaxFlatLength); - auto* rep = CordRepFlat::New(n + extra); - rep->length = n; - memcpy(rep->Data(), s, n); - return rep; -} - -// Unrefs the entries in `[head, tail)`. -// Requires all entries to be a FLAT or EXTERNAL node. -void UnrefEntries(const CordRepRing* rep, index_type head, index_type tail) { - rep->ForEach(head, tail, [rep](index_type ix) { - CordRep* child = rep->entry_child(ix); - if (!child->refcount.Decrement()) { - if (child->tag >= FLAT) { - CordRepFlat::Delete(child->flat()); - } else { - CordRepExternal::Delete(child->external()); - } - } - }); -} - -} // namespace - -std::ostream& operator<<(std::ostream& s, const CordRepRing& rep) { - // Note: 'pos' values are defined as size_t (for overflow reasons), but that - // prints really awkward for small prepended values such as -5. ssize_t is not - // portable (POSIX), so we use ptrdiff_t instead to cast to signed values. - s << " CordRepRing(" << &rep << ", length = " << rep.length - << ", head = " << rep.head_ << ", tail = " << rep.tail_ - << ", cap = " << rep.capacity_ << ", rc = " << rep.refcount.Get() - << ", begin_pos_ = " << static_cast<ptrdiff_t>(rep.begin_pos_) << ") {\n"; - CordRepRing::index_type head = rep.head(); - do { - CordRep* child = rep.entry_child(head); - s << " entry[" << head << "] length = " << rep.entry_length(head) - << ", child " << child << ", clen = " << child->length - << ", tag = " << static_cast<int>(child->tag) - << ", rc = " << child->refcount.Get() - << ", offset = " << rep.entry_data_offset(head) - << ", end_pos = " << static_cast<ptrdiff_t>(rep.entry_end_pos(head)) - << "\n"; - head = rep.advance(head); - } while (head != rep.tail()); - return s << "}\n"; -} - -void CordRepRing::AddDataOffset(index_type index, size_t n) { - entry_data_offset()[index] += static_cast<offset_type>(n); -} - -void CordRepRing::SubLength(index_type index, size_t n) { - entry_end_pos()[index] -= n; -} - -class CordRepRing::Filler { - public: - Filler(CordRepRing* rep, index_type pos) : rep_(rep), head_(pos), pos_(pos) {} - - index_type head() const { return head_; } - index_type pos() const { return pos_; } - - void Add(CordRep* child, size_t offset, pos_type end_pos) { - rep_->entry_end_pos()[pos_] = end_pos; - rep_->entry_child()[pos_] = child; - rep_->entry_data_offset()[pos_] = static_cast<offset_type>(offset); - pos_ = rep_->advance(pos_); - } - - private: - CordRepRing* rep_; - index_type head_; - index_type pos_; -}; - -constexpr size_t CordRepRing::kMaxCapacity; // NOLINT: needed for c++11 - -bool CordRepRing::IsValid(std::ostream& output) const { - if (capacity_ == 0) { - output << "capacity == 0"; - return false; - } - - if (head_ >= capacity_ || tail_ >= capacity_) { - output << "head " << head_ << " and/or tail " << tail_ << "exceed capacity " - << capacity_; - return false; - } - - const index_type back = retreat(tail_); - size_t pos_length = Distance(begin_pos_, entry_end_pos(back)); - if (pos_length != length) { - output << "length " << length << " does not match positional length " - << pos_length << " from begin_pos " << begin_pos_ << " and entry[" - << back << "].end_pos " << entry_end_pos(back); - return false; - } - - index_type head = head_; - pos_type begin_pos = begin_pos_; - do { - pos_type end_pos = entry_end_pos(head); - size_t entry_length = Distance(begin_pos, end_pos); - if (entry_length == 0) { - output << "entry[" << head << "] has an invalid length " << entry_length - << " from begin_pos " << begin_pos << " and end_pos " << end_pos; - return false; - } - - CordRep* child = entry_child(head); - if (child == nullptr) { - output << "entry[" << head << "].child == nullptr"; - return false; - } - if (child->tag < FLAT && child->tag != EXTERNAL) { - output << "entry[" << head << "].child has an invalid tag " - << static_cast<int>(child->tag); - return false; - } - - size_t offset = entry_data_offset(head); - if (offset >= child->length || entry_length > child->length - offset) { - output << "entry[" << head << "] has offset " << offset - << " and entry length " << entry_length - << " which are outside of the child's length of " << child->length; - return false; - } - - begin_pos = end_pos; - head = advance(head); - } while (head != tail_); - - return true; -} - -#ifdef EXTRA_CORD_RING_VALIDATION -CordRepRing* CordRepRing::Validate(CordRepRing* rep, const char* file, - int line) { - if (!rep->IsValid(std::cerr)) { - std::cerr << "\nERROR: CordRepRing corrupted"; - if (line) std::cerr << " at line " << line; - if (file) std::cerr << " in file " << file; - std::cerr << "\nContent = " << *rep; - abort(); - } - return rep; -} -#endif // EXTRA_CORD_RING_VALIDATION - -CordRepRing* CordRepRing::New(size_t capacity, size_t extra) { - CheckCapacity(capacity, extra); - - size_t size = AllocSize(capacity += extra); - void* mem = ::operator new(size); - auto* rep = new (mem) CordRepRing(static_cast<index_type>(capacity)); - rep->tag = RING; - rep->capacity_ = static_cast<index_type>(capacity); - rep->begin_pos_ = 0; - return rep; -} - -void CordRepRing::SetCapacityForTesting(size_t capacity) { - // Adjust for the changed layout - assert(capacity <= capacity_); - assert(head() == 0 || head() < tail()); - memmove(Layout::Partial(capacity).Pointer<1>(data_) + head(), - Layout::Partial(capacity_).Pointer<1>(data_) + head(), - entries() * sizeof(Layout::ElementType<1>)); - memmove(Layout::Partial(capacity, capacity).Pointer<2>(data_) + head(), - Layout::Partial(capacity_, capacity_).Pointer<2>(data_) + head(), - entries() * sizeof(Layout::ElementType<2>)); - capacity_ = static_cast<index_type>(capacity); -} - -void CordRepRing::Delete(CordRepRing* rep) { - assert(rep != nullptr && rep->IsRing()); -#if defined(__cpp_sized_deallocation) - size_t size = AllocSize(rep->capacity_); - rep->~CordRepRing(); - ::operator delete(rep, size); -#else - rep->~CordRepRing(); - ::operator delete(rep); -#endif -} - -void CordRepRing::Destroy(CordRepRing* rep) { - UnrefEntries(rep, rep->head(), rep->tail()); - Delete(rep); -} - -template <bool ref> -void CordRepRing::Fill(const CordRepRing* src, index_type head, - index_type tail) { - this->length = src->length; - head_ = 0; - tail_ = advance(0, src->entries(head, tail)); - begin_pos_ = src->begin_pos_; - - // TODO(mvels): there may be opportunities here for large buffers. - auto* dst_pos = entry_end_pos(); - auto* dst_child = entry_child(); - auto* dst_offset = entry_data_offset(); - src->ForEach(head, tail, [&](index_type index) { - *dst_pos++ = src->entry_end_pos(index); - CordRep* child = src->entry_child(index); - *dst_child++ = ref ? CordRep::Ref(child) : child; - *dst_offset++ = src->entry_data_offset(index); - }); -} - -CordRepRing* CordRepRing::Copy(CordRepRing* rep, index_type head, - index_type tail, size_t extra) { - CordRepRing* newrep = CordRepRing::New(rep->entries(head, tail), extra); - newrep->Fill<true>(rep, head, tail); - CordRep::Unref(rep); - return newrep; -} - -CordRepRing* CordRepRing::Mutable(CordRepRing* rep, size_t extra) { - // Get current number of entries, and check for max capacity. - size_t entries = rep->entries(); - - if (!rep->refcount.IsMutable()) { - return Copy(rep, rep->head(), rep->tail(), extra); - } else if (entries + extra > rep->capacity()) { - const size_t min_grow = rep->capacity() + rep->capacity() / 2; - const size_t min_extra = (std::max)(extra, min_grow - entries); - CordRepRing* newrep = CordRepRing::New(entries, min_extra); - newrep->Fill<false>(rep, rep->head(), rep->tail()); - CordRepRing::Delete(rep); - return newrep; - } else { - return rep; - } -} - -Span<char> CordRepRing::GetAppendBuffer(size_t size) { - assert(refcount.IsMutable()); - index_type back = retreat(tail_); - CordRep* child = entry_child(back); - if (child->tag >= FLAT && child->refcount.IsMutable()) { - size_t capacity = child->flat()->Capacity(); - pos_type end_pos = entry_end_pos(back); - size_t data_offset = entry_data_offset(back); - size_t entry_length = Distance(entry_begin_pos(back), end_pos); - size_t used = data_offset + entry_length; - if (size_t n = (std::min)(capacity - used, size)) { - child->length = data_offset + entry_length + n; - entry_end_pos()[back] = end_pos + n; - this->length += n; - return {child->flat()->Data() + used, n}; - } - } - return {nullptr, 0}; -} - -Span<char> CordRepRing::GetPrependBuffer(size_t size) { - assert(refcount.IsMutable()); - CordRep* child = entry_child(head_); - size_t data_offset = entry_data_offset(head_); - if (data_offset && child->refcount.IsMutable() && child->tag >= FLAT) { - size_t n = (std::min)(data_offset, size); - this->length += n; - begin_pos_ -= n; - data_offset -= n; - entry_data_offset()[head_] = static_cast<offset_type>(data_offset); - return {child->flat()->Data() + data_offset, n}; - } - return {nullptr, 0}; -} - -CordRepRing* CordRepRing::CreateFromLeaf(CordRep* child, size_t offset, - size_t len, size_t extra) { - CordRepRing* rep = CordRepRing::New(1, extra); - rep->head_ = 0; - rep->tail_ = rep->advance(0); - rep->length = len; - rep->entry_end_pos()[0] = len; - rep->entry_child()[0] = child; - rep->entry_data_offset()[0] = static_cast<offset_type>(offset); - return Validate(rep); -} - -CordRepRing* CordRepRing::CreateSlow(CordRep* child, size_t extra) { - CordRepRing* rep = nullptr; - Consume(child, [&](CordRep* child_arg, size_t offset, size_t len) { - if (IsFlatOrExternal(child_arg)) { - rep = rep ? AppendLeaf(rep, child_arg, offset, len) - : CreateFromLeaf(child_arg, offset, len, extra); - } else if (rep) { - rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len); - } else if (offset == 0 && child_arg->length == len) { - rep = Mutable(child_arg->ring(), extra); - } else { - rep = SubRing(child_arg->ring(), offset, len, extra); - } - }); - return Validate(rep, nullptr, __LINE__); -} - -CordRepRing* CordRepRing::Create(CordRep* child, size_t extra) { - size_t length = child->length; - if (IsFlatOrExternal(child)) { - return CreateFromLeaf(child, 0, length, extra); - } - if (child->IsRing()) { - return Mutable(child->ring(), extra); - } - return CreateSlow(child, extra); -} - -template <CordRepRing::AddMode mode> -CordRepRing* CordRepRing::AddRing(CordRepRing* rep, CordRepRing* ring, - size_t offset, size_t len) { - assert(offset < ring->length); - constexpr bool append = mode == AddMode::kAppend; - Position head = ring->Find(offset); - Position tail = ring->FindTail(head.index, offset + len); - const index_type entries = ring->entries(head.index, tail.index); - - rep = Mutable(rep, entries); - - // The delta for making ring[head].end_pos into 'len - offset' - const pos_type delta_length = - (append ? rep->begin_pos_ + rep->length : rep->begin_pos_ - len) - - ring->entry_begin_pos(head.index) - head.offset; - - // Start filling at `tail`, or `entries` before `head` - Filler filler(rep, append ? rep->tail_ : rep->retreat(rep->head_, entries)); - - if (ring->refcount.IsOne()) { - // Copy entries from source stealing the ref and adjusting the end position. - // Commit the filler as this is no-op. - ring->ForEach(head.index, tail.index, [&](index_type ix) { - filler.Add(ring->entry_child(ix), ring->entry_data_offset(ix), - ring->entry_end_pos(ix) + delta_length); - }); - - // Unref entries we did not copy over, and delete source. - if (head.index != ring->head_) UnrefEntries(ring, ring->head_, head.index); - if (tail.index != ring->tail_) UnrefEntries(ring, tail.index, ring->tail_); - CordRepRing::Delete(ring); - } else { - ring->ForEach(head.index, tail.index, [&](index_type ix) { - CordRep* child = ring->entry_child(ix); - filler.Add(child, ring->entry_data_offset(ix), - ring->entry_end_pos(ix) + delta_length); - CordRep::Ref(child); - }); - CordRepRing::Unref(ring); - } - - if (head.offset) { - // Increase offset of first 'source' entry appended or prepended. - // This is always the entry in `filler.head()` - rep->AddDataOffset(filler.head(), head.offset); - } - - if (tail.offset) { - // Reduce length of last 'source' entry appended or prepended. - // This is always the entry tailed by `filler.pos()` - rep->SubLength(rep->retreat(filler.pos()), tail.offset); - } - - // Commit changes - rep->length += len; - if (append) { - rep->tail_ = filler.pos(); - } else { - rep->head_ = filler.head(); - rep->begin_pos_ -= len; - } - - return Validate(rep); -} - -CordRepRing* CordRepRing::AppendSlow(CordRepRing* rep, CordRep* child) { - Consume(child, [&rep](CordRep* child_arg, size_t offset, size_t len) { - if (child_arg->IsRing()) { - rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len); - } else { - rep = AppendLeaf(rep, child_arg, offset, len); - } - }); - return rep; -} - -CordRepRing* CordRepRing::AppendLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t len) { - rep = Mutable(rep, 1); - index_type back = rep->tail_; - const pos_type begin_pos = rep->begin_pos_ + rep->length; - rep->tail_ = rep->advance(rep->tail_); - rep->length += len; - rep->entry_end_pos()[back] = begin_pos + len; - rep->entry_child()[back] = child; - rep->entry_data_offset()[back] = static_cast<offset_type>(offset); - return Validate(rep, nullptr, __LINE__); -} - -CordRepRing* CordRepRing::Append(CordRepRing* rep, CordRep* child) { - size_t length = child->length; - if (IsFlatOrExternal(child)) { - return AppendLeaf(rep, child, 0, length); - } - if (child->IsRing()) { - return AddRing<AddMode::kAppend>(rep, child->ring(), 0, length); - } - return AppendSlow(rep, child); -} - -CordRepRing* CordRepRing::PrependSlow(CordRepRing* rep, CordRep* child) { - ReverseConsume(child, [&](CordRep* child_arg, size_t offset, size_t len) { - if (IsFlatOrExternal(child_arg)) { - rep = PrependLeaf(rep, child_arg, offset, len); - } else { - rep = AddRing<AddMode::kPrepend>(rep, child_arg->ring(), offset, len); - } - }); - return Validate(rep); -} - -CordRepRing* CordRepRing::PrependLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t len) { - rep = Mutable(rep, 1); - index_type head = rep->retreat(rep->head_); - pos_type end_pos = rep->begin_pos_; - rep->head_ = head; - rep->length += len; - rep->begin_pos_ -= len; - rep->entry_end_pos()[head] = end_pos; - rep->entry_child()[head] = child; - rep->entry_data_offset()[head] = static_cast<offset_type>(offset); - return Validate(rep); -} - -CordRepRing* CordRepRing::Prepend(CordRepRing* rep, CordRep* child) { - size_t length = child->length; - if (IsFlatOrExternal(child)) { - return PrependLeaf(rep, child, 0, length); - } - if (child->IsRing()) { - return AddRing<AddMode::kPrepend>(rep, child->ring(), 0, length); - } - return PrependSlow(rep, child); -} - -CordRepRing* CordRepRing::Append(CordRepRing* rep, absl::string_view data, - size_t extra) { - if (rep->refcount.IsMutable()) { - Span<char> avail = rep->GetAppendBuffer(data.length()); - if (!avail.empty()) { - memcpy(avail.data(), data.data(), avail.length()); - data.remove_prefix(avail.length()); - } - } - if (data.empty()) return Validate(rep); - - const size_t flats = (data.length() - 1) / kMaxFlatLength + 1; - rep = Mutable(rep, flats); - - Filler filler(rep, rep->tail_); - pos_type pos = rep->begin_pos_ + rep->length; - - while (data.length() >= kMaxFlatLength) { - auto* flat = CreateFlat(data.data(), kMaxFlatLength); - filler.Add(flat, 0, pos += kMaxFlatLength); - data.remove_prefix(kMaxFlatLength); - } - - if (data.length()) { - auto* flat = CreateFlat(data.data(), data.length(), extra); - filler.Add(flat, 0, pos += data.length()); - } - - rep->length = pos - rep->begin_pos_; - rep->tail_ = filler.pos(); - - return Validate(rep); -} - -CordRepRing* CordRepRing::Prepend(CordRepRing* rep, absl::string_view data, - size_t extra) { - if (rep->refcount.IsMutable()) { - Span<char> avail = rep->GetPrependBuffer(data.length()); - if (!avail.empty()) { - const char* tail = data.data() + data.length() - avail.length(); - memcpy(avail.data(), tail, avail.length()); - data.remove_suffix(avail.length()); - } - } - if (data.empty()) return rep; - - const size_t flats = (data.length() - 1) / kMaxFlatLength + 1; - rep = Mutable(rep, flats); - pos_type pos = rep->begin_pos_; - Filler filler(rep, rep->retreat(rep->head_, static_cast<index_type>(flats))); - - size_t first_size = data.size() - (flats - 1) * kMaxFlatLength; - CordRepFlat* flat = CordRepFlat::New(first_size + extra); - flat->length = first_size + extra; - memcpy(flat->Data() + extra, data.data(), first_size); - data.remove_prefix(first_size); - filler.Add(flat, extra, pos); - pos -= first_size; - - while (!data.empty()) { - assert(data.size() >= kMaxFlatLength); - flat = CreateFlat(data.data(), kMaxFlatLength); - filler.Add(flat, 0, pos); - pos -= kMaxFlatLength; - data.remove_prefix(kMaxFlatLength); - } - - rep->head_ = filler.head(); - rep->length += rep->begin_pos_ - pos; - rep->begin_pos_ = pos; - - return Validate(rep); -} - -// 32 entries is 32 * sizeof(pos_type) = 4 cache lines on x86 -static constexpr index_type kBinarySearchThreshold = 32; -static constexpr index_type kBinarySearchEndCount = 8; - -template <bool wrap> -CordRepRing::index_type CordRepRing::FindBinary(index_type head, - index_type tail, - size_t offset) const { - index_type count = tail + (wrap ? capacity_ : 0) - head; - do { - count = (count - 1) / 2; - assert(count < entries(head, tail_)); - index_type mid = wrap ? advance(head, count) : head + count; - index_type after_mid = wrap ? advance(mid) : mid + 1; - bool larger = (offset >= entry_end_offset(mid)); - head = larger ? after_mid : head; - tail = larger ? tail : mid; - assert(head != tail); - } while (ABSL_PREDICT_TRUE(count > kBinarySearchEndCount)); - return head; -} - -CordRepRing::Position CordRepRing::FindSlow(index_type head, - size_t offset) const { - index_type tail = tail_; - - // Binary search until we are good for linear search - // Optimize for branchless / non wrapping ops - if (tail > head) { - index_type count = tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<false>(head, tail, offset); - } - } else { - index_type count = capacity_ + tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<true>(head, tail, offset); - } - } - - pos_type pos = entry_begin_pos(head); - pos_type end_pos = entry_end_pos(head); - while (offset >= Distance(begin_pos_, end_pos)) { - head = advance(head); - pos = end_pos; - end_pos = entry_end_pos(head); - } - - return {head, offset - Distance(begin_pos_, pos)}; -} - -CordRepRing::Position CordRepRing::FindTailSlow(index_type head, - size_t offset) const { - index_type tail = tail_; - const size_t tail_offset = offset - 1; - - // Binary search until we are good for linear search - // Optimize for branchless / non wrapping ops - if (tail > head) { - index_type count = tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<false>(head, tail, tail_offset); - } - } else { - index_type count = capacity_ + tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<true>(head, tail, tail_offset); - } - } - - size_t end_offset = entry_end_offset(head); - while (tail_offset >= end_offset) { - head = advance(head); - end_offset = entry_end_offset(head); - } - - return {advance(head), end_offset - offset}; -} - -char CordRepRing::GetCharacter(size_t offset) const { - assert(offset < length); - - Position pos = Find(offset); - size_t data_offset = entry_data_offset(pos.index) + pos.offset; - return GetRepData(entry_child(pos.index))[data_offset]; -} - -CordRepRing* CordRepRing::SubRing(CordRepRing* rep, size_t offset, - size_t len, size_t extra) { - assert(offset <= rep->length); - assert(offset <= rep->length - len); - - if (len == 0) { - CordRep::Unref(rep); - return nullptr; - } - - // Find position of first byte - Position head = rep->Find(offset); - Position tail = rep->FindTail(head.index, offset + len); - const size_t new_entries = rep->entries(head.index, tail.index); - - if (rep->refcount.IsMutable() && extra <= (rep->capacity() - new_entries)) { - // We adopt a privately owned rep and no extra entries needed. - if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); - if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); - rep->head_ = head.index; - rep->tail_ = tail.index; - } else { - // Copy subset to new rep - rep = Copy(rep, head.index, tail.index, extra); - head.index = rep->head_; - tail.index = rep->tail_; - } - - // Adjust begin_pos and length - rep->length = len; - rep->begin_pos_ += offset; - - // Adjust head and tail blocks - if (head.offset) { - rep->AddDataOffset(head.index, head.offset); - } - if (tail.offset) { - rep->SubLength(rep->retreat(tail.index), tail.offset); - } - - return Validate(rep); -} - -CordRepRing* CordRepRing::RemovePrefix(CordRepRing* rep, size_t len, - size_t extra) { - assert(len <= rep->length); - if (len == rep->length) { - CordRep::Unref(rep); - return nullptr; - } - - Position head = rep->Find(len); - if (rep->refcount.IsMutable()) { - if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); - rep->head_ = head.index; - } else { - rep = Copy(rep, head.index, rep->tail_, extra); - head.index = rep->head_; - } - - // Adjust begin_pos and length - rep->length -= len; - rep->begin_pos_ += len; - - // Adjust head block - if (head.offset) { - rep->AddDataOffset(head.index, head.offset); - } - - return Validate(rep); -} - -CordRepRing* CordRepRing::RemoveSuffix(CordRepRing* rep, size_t len, - size_t extra) { - assert(len <= rep->length); - - if (len == rep->length) { - CordRep::Unref(rep); - return nullptr; - } - - Position tail = rep->FindTail(rep->length - len); - if (rep->refcount.IsMutable()) { - // We adopt a privately owned rep, scrub. - if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); - rep->tail_ = tail.index; - } else { - // Copy subset to new rep - rep = Copy(rep, rep->head_, tail.index, extra); - tail.index = rep->tail_; - } - - // Adjust length - rep->length -= len; - - // Adjust tail block - if (tail.offset) { - rep->SubLength(rep->retreat(tail.index), tail.offset); - } - - return Validate(rep); -} - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl |