diff options
Diffstat (limited to 'include/google/protobuf/repeated_field.h')
| -rw-r--r-- | include/google/protobuf/repeated_field.h | 1219 |
1 files changed, 1219 insertions, 0 deletions
diff --git a/include/google/protobuf/repeated_field.h b/include/google/protobuf/repeated_field.h new file mode 100644 index 0000000000..3fb734e5cb --- /dev/null +++ b/include/google/protobuf/repeated_field.h @@ -0,0 +1,1219 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2008 Google Inc. All rights reserved. +// https://developers.google.com/protocol-buffers/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// Author: kenton@google.com (Kenton Varda) +// Based on original Protocol Buffers design by +// Sanjay Ghemawat, Jeff Dean, and others. +// +// RepeatedField and RepeatedPtrField are used by generated protocol message +// classes to manipulate repeated fields. These classes are very similar to +// STL's vector, but include a number of optimizations found to be useful +// specifically in the case of Protocol Buffers. RepeatedPtrField is +// particularly different from STL vector as it manages ownership of the +// pointers that it contains. +// +// This header covers RepeatedField. + +#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__ +#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__ + + +#include <algorithm> +#include <iterator> +#include <limits> +#include <string> +#include <type_traits> +#include <utility> + +#include <google/protobuf/stubs/logging.h> +#include <google/protobuf/stubs/common.h> +#include <google/protobuf/arena.h> +#include <google/protobuf/port.h> +#include <google/protobuf/message_lite.h> +#include <google/protobuf/repeated_ptr_field.h> + + +// Must be included last. +#include <google/protobuf/port_def.inc> + +#ifdef SWIG +#error "You cannot SWIG proto headers" +#endif + +namespace google { +namespace protobuf { + +class Message; + +namespace internal { + +template <typename T, int kRepHeaderSize> +constexpr int RepeatedFieldLowerClampLimit() { + // The header is padded to be at least `sizeof(T)` when it would be smaller + // otherwise. + static_assert(sizeof(T) <= kRepHeaderSize, ""); + // We want to pad the minimum size to be a power of two bytes, including the + // header. + // The first allocation is kRepHeaderSize bytes worth of elements for a total + // of 2*kRepHeaderSize bytes. + // For an 8-byte header, we allocate 8 bool, 2 ints, or 1 int64. + return kRepHeaderSize / sizeof(T); +} + +// kRepeatedFieldUpperClampLimit is the lowest signed integer value that +// overflows when multiplied by 2 (which is undefined behavior). Sizes above +// this will clamp to the maximum int value instead of following exponential +// growth when growing a repeated field. +constexpr int kRepeatedFieldUpperClampLimit = + (std::numeric_limits<int>::max() / 2) + 1; + +template <typename Iter> +inline int CalculateReserve(Iter begin, Iter end, std::forward_iterator_tag) { + return static_cast<int>(std::distance(begin, end)); +} + +template <typename Iter> +inline int CalculateReserve(Iter /*begin*/, Iter /*end*/, + std::input_iterator_tag /*unused*/) { + return -1; +} + +template <typename Iter> +inline int CalculateReserve(Iter begin, Iter end) { + typedef typename std::iterator_traits<Iter>::iterator_category Category; + return CalculateReserve(begin, end, Category()); +} + +// Swaps two blocks of memory of size sizeof(T). +template <typename T> +inline void SwapBlock(char* p, char* q) { + T tmp; + memcpy(&tmp, p, sizeof(T)); + memcpy(p, q, sizeof(T)); + memcpy(q, &tmp, sizeof(T)); +} + +// Swaps two blocks of memory of size kSize: +// template <int kSize> void memswap(char* p, char* q); +template <int kSize> +inline typename std::enable_if<(kSize == 0), void>::type memswap(char*, char*) { +} + +#define PROTO_MEMSWAP_DEF_SIZE(reg_type, max_size) \ + template <int kSize> \ + typename std::enable_if<(kSize >= sizeof(reg_type) && kSize < (max_size)), \ + void>::type \ + memswap(char* p, char* q) { \ + SwapBlock<reg_type>(p, q); \ + memswap<kSize - sizeof(reg_type)>(p + sizeof(reg_type), \ + q + sizeof(reg_type)); \ + } + +PROTO_MEMSWAP_DEF_SIZE(uint8_t, 2) +PROTO_MEMSWAP_DEF_SIZE(uint16_t, 4) +PROTO_MEMSWAP_DEF_SIZE(uint32_t, 8) + +#ifdef __SIZEOF_INT128__ +PROTO_MEMSWAP_DEF_SIZE(uint64_t, 16) +PROTO_MEMSWAP_DEF_SIZE(__uint128_t, (1u << 31)) +#else +PROTO_MEMSWAP_DEF_SIZE(uint64_t, (1u << 31)) +#endif + +#undef PROTO_MEMSWAP_DEF_SIZE + +template <typename Element> +class RepeatedIterator; + +} // namespace internal + +// RepeatedField is used to represent repeated fields of a primitive type (in +// other words, everything except strings and nested Messages). Most users will +// not ever use a RepeatedField directly; they will use the get-by-index, +// set-by-index, and add accessors that are generated for all repeated fields. +template <typename Element> +class RepeatedField final { + static_assert( + alignof(Arena) >= alignof(Element), + "We only support types that have an alignment smaller than Arena"); + + public: + constexpr RepeatedField(); + explicit RepeatedField(Arena* arena); + + RepeatedField(const RepeatedField& other); + + template <typename Iter, + typename = typename std::enable_if<std::is_constructible< + Element, decltype(*std::declval<Iter>())>::value>::type> + RepeatedField(Iter begin, Iter end); + + ~RepeatedField(); + + RepeatedField& operator=(const RepeatedField& other); + + RepeatedField(RepeatedField&& other) noexcept; + RepeatedField& operator=(RepeatedField&& other) noexcept; + + bool empty() const; + int size() const; + + const Element& Get(int index) const; + Element* Mutable(int index); + + const Element& operator[](int index) const { return Get(index); } + Element& operator[](int index) { return *Mutable(index); } + + const Element& at(int index) const; + Element& at(int index); + + void Set(int index, const Element& value); + void Add(const Element& value); + // Appends a new element and returns a pointer to it. + // The new element is uninitialized if |Element| is a POD type. + Element* Add(); + // Appends elements in the range [begin, end) after reserving + // the appropriate number of elements. + template <typename Iter> + void Add(Iter begin, Iter end); + + // Removes the last element in the array. + void RemoveLast(); + + // Extracts elements with indices in "[start .. start+num-1]". + // Copies them into "elements[0 .. num-1]" if "elements" is not nullptr. + // Caution: also moves elements with indices [start+num ..]. + // Calling this routine inside a loop can cause quadratic behavior. + void ExtractSubrange(int start, int num, Element* elements); + + PROTOBUF_ATTRIBUTE_REINITIALIZES void Clear(); + void MergeFrom(const RepeatedField& other); + PROTOBUF_ATTRIBUTE_REINITIALIZES void CopyFrom(const RepeatedField& other); + + // Replaces the contents with RepeatedField(begin, end). + template <typename Iter> + PROTOBUF_ATTRIBUTE_REINITIALIZES void Assign(Iter begin, Iter end); + + // Reserves space to expand the field to at least the given size. If the + // array is grown, it will always be at least doubled in size. + void Reserve(int new_size); + + // Resizes the RepeatedField to a new, smaller size. This is O(1). + void Truncate(int new_size); + + void AddAlreadyReserved(const Element& value); + // Appends a new element and return a pointer to it. + // The new element is uninitialized if |Element| is a POD type. + // Should be called only if Capacity() > Size(). + Element* AddAlreadyReserved(); + Element* AddNAlreadyReserved(int elements); + int Capacity() const; + + // Like STL resize. Uses value to fill appended elements. + // Like Truncate() if new_size <= size(), otherwise this is + // O(new_size - size()). + void Resize(int new_size, const Element& value); + + // Gets the underlying array. This pointer is possibly invalidated by + // any add or remove operation. + Element* mutable_data(); + const Element* data() const; + + // Swaps entire contents with "other". If they are separate arenas then, + // copies data between each other. + void Swap(RepeatedField* other); + + // Swaps entire contents with "other". Should be called only if the caller can + // guarantee that both repeated fields are on the same arena or are on the + // heap. Swapping between different arenas is disallowed and caught by a + // GOOGLE_DCHECK (see API docs for details). + void UnsafeArenaSwap(RepeatedField* other); + + // Swaps two elements. + void SwapElements(int index1, int index2); + + // STL-like iterator support + typedef internal::RepeatedIterator<Element> iterator; + typedef internal::RepeatedIterator<const Element> const_iterator; + typedef Element value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef int size_type; + typedef ptrdiff_t difference_type; + + iterator begin(); + const_iterator begin() const; + const_iterator cbegin() const; + iterator end(); + const_iterator end() const; + const_iterator cend() const; + + // Reverse iterator support + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + reverse_iterator rbegin() { return reverse_iterator(end()); } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + reverse_iterator rend() { return reverse_iterator(begin()); } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + + // Returns the number of bytes used by the repeated field, excluding + // sizeof(*this) + size_t SpaceUsedExcludingSelfLong() const; + + int SpaceUsedExcludingSelf() const { + return internal::ToIntSize(SpaceUsedExcludingSelfLong()); + } + + // Removes the element referenced by position. + // + // Returns an iterator to the element immediately following the removed + // element. + // + // Invalidates all iterators at or after the removed element, including end(). + iterator erase(const_iterator position); + + // Removes the elements in the range [first, last). + // + // Returns an iterator to the element immediately following the removed range. + // + // Invalidates all iterators at or after the removed range, including end(). + iterator erase(const_iterator first, const_iterator last); + + // Gets the Arena on which this RepeatedField stores its elements. + inline Arena* GetArena() const { + return GetOwningArena(); + } + + // For internal use only. + // + // This is public due to it being called by generated code. + inline void InternalSwap(RepeatedField* other); + + private: + template <typename T> friend class Arena::InternalHelper; + + // Gets the Arena on which this RepeatedField stores its elements. + inline Arena* GetOwningArena() const { + return (total_size_ == 0) ? static_cast<Arena*>(arena_or_elements_) + : rep()->arena; + } + + static constexpr int kInitialSize = 0; + // A note on the representation here (see also comment below for + // RepeatedPtrFieldBase's struct Rep): + // + // We maintain the same sizeof(RepeatedField) as before we added arena support + // so that we do not degrade performance by bloating memory usage. Directly + // adding an arena_ element to RepeatedField is quite costly. By using + // indirection in this way, we keep the same size when the RepeatedField is + // empty (common case), and add only an 8-byte header to the elements array + // when non-empty. We make sure to place the size fields directly in the + // RepeatedField class to avoid costly cache misses due to the indirection. + int current_size_; + int total_size_; + // Pad the Rep after arena allow for power-of-two byte sizes when + // sizeof(Element) > sizeof(Arena*). eg for 16-byte objects. + static PROTOBUF_CONSTEXPR const size_t kRepHeaderSize = + sizeof(Arena*) < sizeof(Element) ? sizeof(Element) : sizeof(Arena*); + struct Rep { + Arena* arena; + Element* elements() { + return reinterpret_cast<Element*>(reinterpret_cast<char*>(this) + + kRepHeaderSize); + } + }; + + // If total_size_ == 0 this points to an Arena otherwise it points to the + // elements member of a Rep struct. Using this invariant allows the storage of + // the arena pointer without an extra allocation in the constructor. + void* arena_or_elements_; + + // Returns a pointer to elements array. + // pre-condition: the array must have been allocated. + Element* elements() const { + GOOGLE_DCHECK_GT(total_size_, 0); + // Because of above pre-condition this cast is safe. + return unsafe_elements(); + } + + // Returns a pointer to elements array if it exists; otherwise either null or + // an invalid pointer is returned. This only happens for empty repeated + // fields, where you can't dereference this pointer anyway (it's empty). + Element* unsafe_elements() const { + return static_cast<Element*>(arena_or_elements_); + } + + // Returns a pointer to the Rep struct. + // pre-condition: the Rep must have been allocated, ie elements() is safe. + Rep* rep() const { + return reinterpret_cast<Rep*>(reinterpret_cast<char*>(elements()) - + kRepHeaderSize); + } + + friend class Arena; + typedef void InternalArenaConstructable_; + + // Moves the contents of |from| into |to|, possibly clobbering |from| in the + // process. For primitive types this is just a memcpy(), but it could be + // specialized for non-primitive types to, say, swap each element instead. + void MoveArray(Element* to, Element* from, int size); + + // Copies the elements of |from| into |to|. + void CopyArray(Element* to, const Element* from, int size); + + // Internal helper to delete all elements and deallocate the storage. + void InternalDeallocate(Rep* rep, int size, bool in_destructor) { + if (rep != nullptr) { + Element* e = &rep->elements()[0]; + if (!std::is_trivial<Element>::value) { + Element* limit = &rep->elements()[size]; + for (; e < limit; e++) { + e->~Element(); + } + } + const size_t bytes = size * sizeof(*e) + kRepHeaderSize; + if (rep->arena == nullptr) { + internal::SizedDelete(rep, bytes); + } else if (!in_destructor) { + // If we are in the destructor, we might be being destroyed as part of + // the arena teardown. We can't try and return blocks to the arena then. + rep->arena->ReturnArrayMemory(rep, bytes); + } + } + } + + // This class is a performance wrapper around RepeatedField::Add(const T&) + // function. In general unless a RepeatedField is a local stack variable LLVM + // has a hard time optimizing Add. The machine code tends to be + // loop: + // mov %size, dword ptr [%repeated_field] // load + // cmp %size, dword ptr [%repeated_field + 4] + // jae fallback + // mov %buffer, qword ptr [%repeated_field + 8] + // mov dword [%buffer + %size * 4], %value + // inc %size // increment + // mov dword ptr [%repeated_field], %size // store + // jmp loop + // + // This puts a load/store in each iteration of the important loop variable + // size. It's a pretty bad compile that happens even in simple cases, but + // largely the presence of the fallback path disturbs the compilers mem-to-reg + // analysis. + // + // This class takes ownership of a repeated field for the duration of its + // lifetime. The repeated field should not be accessed during this time, ie. + // only access through this class is allowed. This class should always be a + // function local stack variable. Intended use + // + // void AddSequence(const int* begin, const int* end, RepeatedField<int>* out) + // { + // RepeatedFieldAdder<int> adder(out); // Take ownership of out + // for (auto it = begin; it != end; ++it) { + // adder.Add(*it); + // } + // } + // + // Typically, due to the fact that adder is a local stack variable, the + // compiler will be successful in mem-to-reg transformation and the machine + // code will be loop: cmp %size, %capacity jae fallback mov dword ptr [%buffer + // + %size * 4], %val inc %size jmp loop + // + // The first version executes at 7 cycles per iteration while the second + // version executes at only 1 or 2 cycles. + template <int = 0, bool = std::is_trivial<Element>::value> + class FastAdderImpl { + public: + explicit FastAdderImpl(RepeatedField* rf) : repeated_field_(rf) { + index_ = repeated_field_->current_size_; + capacity_ = repeated_field_->total_size_; + buffer_ = repeated_field_->unsafe_elements(); + } + ~FastAdderImpl() { repeated_field_->current_size_ = index_; } + + void Add(Element val) { + if (index_ == capacity_) { + repeated_field_->current_size_ = index_; + repeated_field_->Reserve(index_ + 1); + capacity_ = repeated_field_->total_size_; + buffer_ = repeated_field_->unsafe_elements(); + } + buffer_[index_++] = val; + } + + private: + RepeatedField* repeated_field_; + int index_; + int capacity_; + Element* buffer_; + + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(FastAdderImpl); + }; + + // FastAdder is a wrapper for adding fields. The specialization above handles + // POD types more efficiently than RepeatedField. + template <int I> + class FastAdderImpl<I, false> { + public: + explicit FastAdderImpl(RepeatedField* rf) : repeated_field_(rf) {} + void Add(const Element& val) { repeated_field_->Add(val); } + + private: + RepeatedField* repeated_field_; + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(FastAdderImpl); + }; + + using FastAdder = FastAdderImpl<>; + + friend class TestRepeatedFieldHelper; + friend class ::google::protobuf::internal::ParseContext; +}; + +namespace internal { + +// This is a helper template to copy an array of elements efficiently when they +// have a trivial copy constructor, and correctly otherwise. This really +// shouldn't be necessary, but our compiler doesn't optimize std::copy very +// effectively. +template <typename Element, + bool HasTrivialCopy = std::is_trivial<Element>::value> +struct ElementCopier { + void operator()(Element* to, const Element* from, int array_size); +}; + +} // namespace internal + +// implementation ==================================================== + +template <typename Element> +constexpr RepeatedField<Element>::RepeatedField() + : current_size_(0), total_size_(0), arena_or_elements_(nullptr) {} + +template <typename Element> +inline RepeatedField<Element>::RepeatedField(Arena* arena) + : current_size_(0), total_size_(0), arena_or_elements_(arena) {} + +template <typename Element> +inline RepeatedField<Element>::RepeatedField(const RepeatedField& other) + : current_size_(0), total_size_(0), arena_or_elements_(nullptr) { + if (other.current_size_ != 0) { + Reserve(other.size()); + AddNAlreadyReserved(other.size()); + CopyArray(Mutable(0), &other.Get(0), other.size()); + } +} + +template <typename Element> +template <typename Iter, typename> +RepeatedField<Element>::RepeatedField(Iter begin, Iter end) + : current_size_(0), total_size_(0), arena_or_elements_(nullptr) { + Add(begin, end); +} + +template <typename Element> +RepeatedField<Element>::~RepeatedField() { +#ifndef NDEBUG + // Try to trigger segfault / asan failure in non-opt builds if arena_ + // lifetime has ended before the destructor. + auto arena = GetOwningArena(); + if (arena) (void)arena->SpaceAllocated(); +#endif + if (total_size_ > 0) { + InternalDeallocate(rep(), total_size_, true); + } +} + +template <typename Element> +inline RepeatedField<Element>& RepeatedField<Element>::operator=( + const RepeatedField& other) { + if (this != &other) CopyFrom(other); + return *this; +} + +template <typename Element> +inline RepeatedField<Element>::RepeatedField(RepeatedField&& other) noexcept + : RepeatedField() { +#ifdef PROTOBUF_FORCE_COPY_IN_MOVE + CopyFrom(other); +#else // PROTOBUF_FORCE_COPY_IN_MOVE + // We don't just call Swap(&other) here because it would perform 3 copies if + // other is on an arena. This field can't be on an arena because arena + // construction always uses the Arena* accepting constructor. + if (other.GetOwningArena()) { + CopyFrom(other); + } else { + InternalSwap(&other); + } +#endif // !PROTOBUF_FORCE_COPY_IN_MOVE +} + +template <typename Element> +inline RepeatedField<Element>& RepeatedField<Element>::operator=( + RepeatedField&& other) noexcept { + // We don't just call Swap(&other) here because it would perform 3 copies if + // the two fields are on different arenas. + if (this != &other) { + if (GetOwningArena() != other.GetOwningArena() +#ifdef PROTOBUF_FORCE_COPY_IN_MOVE + || GetOwningArena() == nullptr +#endif // !PROTOBUF_FORCE_COPY_IN_MOVE + ) { + CopyFrom(other); + } else { + InternalSwap(&other); + } + } + return *this; +} + +template <typename Element> +inline bool RepeatedField<Element>::empty() const { + return current_size_ == 0; +} + +template <typename Element> +inline int RepeatedField<Element>::size() const { + return current_size_; +} + +template <typename Element> +inline int RepeatedField<Element>::Capacity() const { + return total_size_; +} + +template <typename Element> +inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) { + GOOGLE_DCHECK_LT(current_size_, total_size_); + elements()[current_size_++] = value; +} + +template <typename Element> +inline Element* RepeatedField<Element>::AddAlreadyReserved() { + GOOGLE_DCHECK_LT(current_size_, total_size_); + return &elements()[current_size_++]; +} + +template <typename Element> +inline Element* RepeatedField<Element>::AddNAlreadyReserved(int elements) { + GOOGLE_DCHECK_GE(total_size_ - current_size_, elements) + << total_size_ << ", " << current_size_; + // Warning: sometimes people call this when elements == 0 and + // total_size_ == 0. In this case the return pointer points to a zero size + // array (n == 0). Hence we can just use unsafe_elements(), because the user + // cannot dereference the pointer anyway. + Element* ret = unsafe_elements() + current_size_; + current_size_ += elements; + return ret; +} + +template <typename Element> +inline void RepeatedField<Element>::Resize(int new_size, const Element& value) { + GOOGLE_DCHECK_GE(new_size, 0); + if (new_size > current_size_) { + Reserve(new_size); + std::fill(&elements()[current_size_], &elements()[new_size], value); + } + current_size_ = new_size; +} + +template <typename Element> +inline const Element& RepeatedField<Element>::Get(int index) const { + GOOGLE_DCHECK_GE(index, 0); + GOOGLE_DCHECK_LT(index, current_size_); + return elements()[index]; +} + +template <typename Element> +inline const Element& RepeatedField<Element>::at(int index) const { + GOOGLE_CHECK_GE(index, 0); + GOOGLE_CHECK_LT(index, current_size_); + return elements()[index]; +} + +template <typename Element> +inline Element& RepeatedField<Element>::at(int index) { + GOOGLE_CHECK_GE(index, 0); + GOOGLE_CHECK_LT(index, current_size_); + return elements()[index]; +} + +template <typename Element> +inline Element* RepeatedField<Element>::Mutable(int index) { + GOOGLE_DCHECK_GE(index, 0); + GOOGLE_DCHECK_LT(index, current_size_); + return &elements()[index]; +} + +template <typename Element> +inline void RepeatedField<Element>::Set(int index, const Element& value) { + GOOGLE_DCHECK_GE(index, 0); + GOOGLE_DCHECK_LT(index, current_size_); + elements()[index] = value; +} + +template <typename Element> +inline void RepeatedField<Element>::Add(const Element& value) { + uint32_t size = current_size_; + if (static_cast<int>(size) == total_size_) { + // value could reference an element of the array. Reserving new space will + // invalidate the reference. So we must make a copy first. + auto tmp = value; + Reserve(total_size_ + 1); + elements()[size] = std::move(tmp); + } else { + elements()[size] = value; + } + current_size_ = size + 1; +} + +template <typename Element> +inline Element* RepeatedField<Element>::Add() { + uint32_t size = current_size_; + if (static_cast<int>(size) == total_size_) Reserve(total_size_ + 1); + auto ptr = &elements()[size]; + current_size_ = size + 1; + return ptr; +} + +template <typename Element> +template <typename Iter> +inline void RepeatedField<Element>::Add(Iter begin, Iter end) { + int reserve = internal::CalculateReserve(begin, end); + if (reserve != -1) { + if (reserve == 0) { + return; + } + + Reserve(reserve + size()); + // TODO(ckennelly): The compiler loses track of the buffer freshly + // allocated by Reserve() by the time we call elements, so it cannot + // guarantee that elements does not alias [begin(), end()). + // + // If restrict is available, annotating the pointer obtained from elements() + // causes this to lower to memcpy instead of memmove. + std::copy(begin, end, elements() + size()); + current_size_ = reserve + size(); + } else { + FastAdder fast_adder(this); + for (; begin != end; ++begin) fast_adder.Add(*begin); + } +} + +template <typename Element> +inline void RepeatedField<Element>::RemoveLast() { + GOOGLE_DCHECK_GT(current_size_, 0); + current_size_--; +} + +template <typename Element> +void RepeatedField<Element>::ExtractSubrange(int start, int num, + Element* elements) { + GOOGLE_DCHECK_GE(start, 0); + GOOGLE_DCHECK_GE(num, 0); + GOOGLE_DCHECK_LE(start + num, this->current_size_); + + // Save the values of the removed elements if requested. + if (elements != nullptr) { + for (int i = 0; i < num; ++i) elements[i] = this->Get(i + start); + } + + // Slide remaining elements down to fill the gap. + if (num > 0) { + for (int i = start + num; i < this->current_size_; ++i) + this->Set(i - num, this->Get(i)); + this->Truncate(this->current_size_ - num); + } +} + +template <typename Element> +inline void RepeatedField<Element>::Clear() { + current_size_ = 0; +} + +template <typename Element> +inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) { + GOOGLE_DCHECK_NE(&other, this); + if (other.current_size_ != 0) { + int existing_size = size(); + Reserve(existing_size + other.size()); + AddNAlreadyReserved(other.size()); + CopyArray(Mutable(existing_size), &other.Get(0), other.size()); + } +} + +template <typename Element> +inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) { + if (&other == this) return; + Clear(); + MergeFrom(other); +} + +template <typename Element> +template <typename Iter> +inline void RepeatedField<Element>::Assign(Iter begin, Iter end) { + Clear(); + Add(begin, end); +} + +template <typename Element> +inline typename RepeatedField<Element>::iterator RepeatedField<Element>::erase( + const_iterator position) { + return erase(position, position + 1); +} + +template <typename Element> +inline typename RepeatedField<Element>::iterator RepeatedField<Element>::erase( + const_iterator first, const_iterator last) { + size_type first_offset = first - cbegin(); + if (first != last) { + Truncate(std::copy(last, cend(), begin() + first_offset) - cbegin()); + } + return begin() + first_offset; +} + +template <typename Element> +inline Element* RepeatedField<Element>::mutable_data() { + return unsafe_elements(); +} + +template <typename Element> +inline const Element* RepeatedField<Element>::data() const { + return unsafe_elements(); +} + +template <typename Element> +inline void RepeatedField<Element>::InternalSwap(RepeatedField* other) { + GOOGLE_DCHECK(this != other); + + // Swap all fields at once. + static_assert(std::is_standard_layout<RepeatedField<Element>>::value, + "offsetof() requires standard layout before c++17"); + internal::memswap<offsetof(RepeatedField, arena_or_elements_) + + sizeof(this->arena_or_elements_) - + offsetof(RepeatedField, current_size_)>( + reinterpret_cast<char*>(this) + offsetof(RepeatedField, current_size_), + reinterpret_cast<char*>(other) + offsetof(RepeatedField, current_size_)); +} + +template <typename Element> +void RepeatedField<Element>::Swap(RepeatedField* other) { + if (this == other) return; +#ifdef PROTOBUF_FORCE_COPY_IN_SWAP + if (GetOwningArena() != nullptr && + GetOwningArena() == other->GetOwningArena()) { +#else // PROTOBUF_FORCE_COPY_IN_SWAP + if (GetOwningArena() == other->GetOwningArena()) { +#endif // !PROTOBUF_FORCE_COPY_IN_SWAP + InternalSwap(other); + } else { + RepeatedField<Element> temp(other->GetOwningArena()); + temp.MergeFrom(*this); + CopyFrom(*other); + other->UnsafeArenaSwap(&temp); + } +} + +template <typename Element> +void RepeatedField<Element>::UnsafeArenaSwap(RepeatedField* other) { + if (this == other) return; + GOOGLE_DCHECK_EQ(GetOwningArena(), other->GetOwningArena()); + InternalSwap(other); +} + +template <typename Element> +void RepeatedField<Element>::SwapElements(int index1, int index2) { + using std::swap; // enable ADL with fallback + swap(elements()[index1], elements()[index2]); +} + +template <typename Element> +inline typename RepeatedField<Element>::iterator +RepeatedField<Element>::begin() { + return iterator(unsafe_elements()); +} +template <typename Element> +inline typename RepeatedField<Element>::const_iterator +RepeatedField<Element>::begin() const { + return const_iterator(unsafe_elements()); +} +template <typename Element> +inline typename RepeatedField<Element>::const_iterator +RepeatedField<Element>::cbegin() const { + return const_iterator(unsafe_elements()); +} +template <typename Element> +inline typename RepeatedField<Element>::iterator RepeatedField<Element>::end() { + return iterator(unsafe_elements() + current_size_); +} +template <typename Element> +inline typename RepeatedField<Element>::const_iterator +RepeatedField<Element>::end() const { + return const_iterator(unsafe_elements() + current_size_); +} +template <typename Element> +inline typename RepeatedField<Element>::const_iterator +RepeatedField<Element>::cend() const { + return const_iterator(unsafe_elements() + current_size_); +} + +template <typename Element> +inline size_t RepeatedField<Element>::SpaceUsedExcludingSelfLong() const { + return total_size_ > 0 ? (total_size_ * sizeof(Element) + kRepHeaderSize) : 0; +} + +namespace internal { +// Returns the new size for a reserved field based on its 'total_size' and the +// requested 'new_size'. The result is clamped to the closed interval: +// [internal::kMinRepeatedFieldAllocationSize, +// std::numeric_limits<int>::max()] +// Requires: +// new_size > total_size && +// (total_size == 0 || +// total_size >= kRepeatedFieldLowerClampLimit) +template <typename T, int kRepHeaderSize> +inline int CalculateReserveSize(int total_size, int new_size) { + constexpr int lower_limit = RepeatedFieldLowerClampLimit<T, kRepHeaderSize>(); + if (new_size < lower_limit) { + // Clamp to smallest allowed size. + return lower_limit; + } + constexpr int kMaxSizeBeforeClamp = + (std::numeric_limits<int>::max() - kRepHeaderSize) / 2; + if (PROTOBUF_PREDICT_FALSE(total_size > kMaxSizeBeforeClamp)) { + return std::numeric_limits<int>::max(); + } + // We want to double the number of bytes, not the number of elements, to try + // to stay within power-of-two allocations. + // The allocation has kRepHeaderSize + sizeof(T) * capacity. + int doubled_size = 2 * total_size + kRepHeaderSize / sizeof(T); + return std::max(doubled_size, new_size); +} +} // namespace internal + +// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant +// amount of code bloat. +template <typename Element> +void RepeatedField<Element>::Reserve(int new_size) { + if (total_size_ >= new_size) return; + Rep* old_rep = total_size_ > 0 ? rep() : nullptr; + Rep* new_rep; + Arena* arena = GetOwningArena(); + + new_size = internal::CalculateReserveSize<Element, kRepHeaderSize>( + total_size_, new_size); + + GOOGLE_DCHECK_LE( + static_cast<size_t>(new_size), + (std::numeric_limits<size_t>::max() - kRepHeaderSize) / sizeof(Element)) + << "Requested size is too large to fit into size_t."; + size_t bytes = + kRepHeaderSize + sizeof(Element) * static_cast<size_t>(new_size); + if (arena == nullptr) { + new_rep = static_cast<Rep*>(::operator new(bytes)); + } else { + new_rep = reinterpret_cast<Rep*>(Arena::CreateArray<char>(arena, bytes)); + } + new_rep->arena = arena; + int old_total_size = total_size_; + // Already known: new_size >= internal::kMinRepeatedFieldAllocationSize + // Maintain invariant: + // total_size_ == 0 || + // total_size_ >= internal::kMinRepeatedFieldAllocationSize + total_size_ = new_size; + arena_or_elements_ = new_rep->elements(); + // Invoke placement-new on newly allocated elements. We shouldn't have to do + // this, since Element is supposed to be POD, but a previous version of this + // code allocated storage with "new Element[size]" and some code uses + // RepeatedField with non-POD types, relying on constructor invocation. If + // Element has a trivial constructor (e.g., int32_t), gcc (tested with -O2) + // completely removes this loop because the loop body is empty, so this has no + // effect unless its side-effects are required for correctness. + // Note that we do this before MoveArray() below because Element's copy + // assignment implementation will want an initialized instance first. + Element* e = &elements()[0]; + Element* limit = e + total_size_; + for (; e < limit; e++) { + new (e) Element; + } + if (current_size_ > 0) { + MoveArray(&elements()[0], old_rep->elements(), current_size_); + } + + // Likewise, we need to invoke destructors on the old array. + InternalDeallocate(old_rep, old_total_size, false); + +} + +template <typename Element> +inline void RepeatedField<Element>::Truncate(int new_size) { + GOOGLE_DCHECK_LE(new_size, current_size_); + if (current_size_ > 0) { + current_size_ = new_size; + } +} + +template <typename Element> +inline void RepeatedField<Element>::MoveArray(Element* to, Element* from, + int array_size) { + CopyArray(to, from, array_size); +} + +template <typename Element> +inline void RepeatedField<Element>::CopyArray(Element* to, const Element* from, + int array_size) { + internal::ElementCopier<Element>()(to, from, array_size); +} + +namespace internal { + +template <typename Element, bool HasTrivialCopy> +void ElementCopier<Element, HasTrivialCopy>::operator()(Element* to, + const Element* from, + int array_size) { + std::copy(from, from + array_size, to); +} + +template <typename Element> +struct ElementCopier<Element, true> { + void operator()(Element* to, const Element* from, int array_size) { + memcpy(to, from, static_cast<size_t>(array_size) * sizeof(Element)); + } +}; + +} // namespace internal + + +// ------------------------------------------------------------------- + +// Iterators and helper functions that follow the spirit of the STL +// std::back_insert_iterator and std::back_inserter but are tailor-made +// for RepeatedField and RepeatedPtrField. Typical usage would be: +// +// std::copy(some_sequence.begin(), some_sequence.end(), +// RepeatedFieldBackInserter(proto.mutable_sequence())); +// +// Ported by johannes from util/gtl/proto-array-iterators.h + +namespace internal { + +// STL-like iterator implementation for RepeatedField. You should not +// refer to this class directly; use RepeatedField<T>::iterator instead. +// +// Note: All of the iterator operators *must* be inlined to avoid performance +// regressions. This is caused by the extern template declarations below (which +// are required because of the RepeatedField extern template declarations). If +// any of these functions aren't explicitly inlined (e.g. defined in the class), +// the compiler isn't allowed to inline them. +template <typename Element> +class RepeatedIterator { + public: + using iterator_category = std::random_access_iterator_tag; + // Note: remove_const is necessary for std::partial_sum, which uses value_type + // to determine the summation variable type. + using value_type = typename std::remove_const<Element>::type; + using difference_type = std::ptrdiff_t; + using pointer = Element*; + using reference = Element&; + + constexpr RepeatedIterator() noexcept : it_(nullptr) {} + + // Allows "upcasting" from RepeatedIterator<T**> to + // RepeatedIterator<const T*const*>. + template <typename OtherElement, + typename std::enable_if<std::is_convertible< + OtherElement*, pointer>::value>::type* = nullptr> + constexpr RepeatedIterator( + const RepeatedIterator<OtherElement>& other) noexcept + : it_(other.it_) {} + + // dereferenceable + constexpr reference operator*() const noexcept { return *it_; } + constexpr pointer operator->() const noexcept { return it_; } + + private: + // Helper alias to hide the internal type. + using iterator = RepeatedIterator<Element>; + + public: + // {inc,dec}rementable + iterator& operator++() noexcept { + ++it_; + return *this; + } + iterator operator++(int) noexcept { return iterator(it_++); } + iterator& operator--() noexcept { + --it_; + return *this; + } + iterator operator--(int) noexcept { return iterator(it_--); } + + // equality_comparable + friend constexpr bool operator==(const iterator& x, + const iterator& y) noexcept { + return x.it_ == y.it_; + } + friend constexpr bool operator!=(const iterator& x, + const iterator& y) noexcept { + return x.it_ != y.it_; + } + + // less_than_comparable + friend constexpr bool operator<(const iterator& x, + const iterator& y) noexcept { + return x.it_ < y.it_; + } + friend constexpr bool operator<=(const iterator& x, + const iterator& y) noexcept { + return x.it_ <= y.it_; + } + friend constexpr bool operator>(const iterator& x, + const iterator& y) noexcept { + return x.it_ > y.it_; + } + friend constexpr bool operator>=(const iterator& x, + const iterator& y) noexcept { + return x.it_ >= y.it_; + } + + // addable, subtractable + iterator& operator+=(difference_type d) noexcept { + it_ += d; + return *this; + } + constexpr iterator operator+(difference_type d) const noexcept { + return iterator(it_ + d); + } + friend constexpr iterator operator+(const difference_type d, + iterator it) noexcept { + return it + d; + } + + iterator& operator-=(difference_type d) noexcept { + it_ -= d; + return *this; + } + iterator constexpr operator-(difference_type d) const noexcept { + return iterator(it_ - d); + } + + // indexable + constexpr reference operator[](difference_type d) const noexcept { + return it_[d]; + } + + // random access iterator + friend constexpr difference_type operator-(iterator it1, + iterator it2) noexcept { + return it1.it_ - it2.it_; + } + + private: + template <typename OtherElement> + friend class RepeatedIterator; + + // Allow construction from RepeatedField. + friend class RepeatedField<value_type>; + explicit RepeatedIterator(Element* it) noexcept : it_(it) {} + + // The internal iterator. + Element* it_; +}; + +// A back inserter for RepeatedField objects. +template <typename T> +class RepeatedFieldBackInsertIterator { + public: + using iterator_category = std::output_iterator_tag; + using value_type = T; + using pointer = void; + using reference = void; + using difference_type = std::ptrdiff_t; + + explicit RepeatedFieldBackInsertIterator( + RepeatedField<T>* const mutable_field) + : field_(mutable_field) {} + RepeatedFieldBackInsertIterator<T>& operator=(const T& value) { + field_->Add(value); + return *this; + } + RepeatedFieldBackInsertIterator<T>& operator*() { return *this; } + RepeatedFieldBackInsertIterator<T>& operator++() { return *this; } + RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) { + return *this; + } + + private: + RepeatedField<T>* field_; +}; + +} // namespace internal + +// Provides a back insert iterator for RepeatedField instances, +// similar to std::back_inserter(). +template <typename T> +internal::RepeatedFieldBackInsertIterator<T> RepeatedFieldBackInserter( + RepeatedField<T>* const mutable_field) { + return internal::RepeatedFieldBackInsertIterator<T>(mutable_field); +} + +// Extern declarations of common instantiations to reduce library bloat. +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<bool>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<int32_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<uint32_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<int64_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<uint64_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<float>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<double>; + +namespace internal { +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedIterator<bool>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE + RepeatedIterator<int32_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE + RepeatedIterator<uint32_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE + RepeatedIterator<int64_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE + RepeatedIterator<uint64_t>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedIterator<float>; +extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedIterator<double>; +} // namespace internal + +} // namespace protobuf +} // namespace google + +#include <google/protobuf/port_undef.inc> + +#endif // GOOGLE_PROTOBUF_REPEATED_FIELD_H__ |