1// Protocol Buffers - Google's data interchange format
2// Copyright 2008 Google Inc. All rights reserved.
3// https://developers.google.com/protocol-buffers/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are
7// met:
8//
9// * Redistributions of source code must retain the above copyright
10// notice, this list of conditions and the following disclaimer.
11// * Redistributions in binary form must reproduce the above
12// copyright notice, this list of conditions and the following disclaimer
13// in the documentation and/or other materials provided with the
14// distribution.
15// * Neither the name of Google Inc. nor the names of its
16// contributors may be used to endorse or promote products derived from
17// this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31// Author: [email protected] (Kenton Varda)
32// Based on original Protocol Buffers design by
33// Sanjay Ghemawat, Jeff Dean, and others.
34//
35// RepeatedField and RepeatedPtrField are used by generated protocol message
36// classes to manipulate repeated fields. These classes are very similar to
37// STL's vector, but include a number of optimizations found to be useful
38// specifically in the case of Protocol Buffers. RepeatedPtrField is
39// particularly different from STL vector as it manages ownership of the
40// pointers that it contains.
41//
42// Typically, clients should not need to access RepeatedField objects directly,
43// but should instead use the accessor functions generated automatically by the
44// protocol compiler.
45
46#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__
47#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__
48
49#include <utility>
50#ifdef _MSC_VER
51// This is required for min/max on VS2013 only.
52#include <algorithm>
53#endif
54
55#include <iterator>
56#include <limits>
57#include <string>
58#include <type_traits>
59
60#include <google/protobuf/stubs/logging.h>
61#include <google/protobuf/stubs/common.h>
62#include <google/protobuf/arena.h>
63#include <google/protobuf/message_lite.h>
64#include <google/protobuf/port.h>
65#include <google/protobuf/stubs/casts.h>
66#include <type_traits>
67
68
69// Must be included last.
70#include <google/protobuf/port_def.inc>
71
72#ifdef SWIG
73#error "You cannot SWIG proto headers"
74#endif
75
76namespace google {
77namespace protobuf {
78
79class Message;
80class Reflection;
81
82template <typename T>
83struct WeakRepeatedPtrField;
84
85namespace internal {
86
87class MergePartialFromCodedStreamHelper;
88
89// kRepeatedFieldLowerClampLimit is the smallest size that will be allocated
90// when growing a repeated field.
91constexpr int kRepeatedFieldLowerClampLimit = 4;
92
93// kRepeatedFieldUpperClampLimit is the lowest signed integer value that
94// overflows when multiplied by 2 (which is undefined behavior). Sizes above
95// this will clamp to the maximum int value instead of following exponential
96// growth when growing a repeated field.
97constexpr int kRepeatedFieldUpperClampLimit =
98 (std::numeric_limits<int>::max() / 2) + 1;
99
100// A utility function for logging that doesn't need any template types.
101void LogIndexOutOfBounds(int index, int size);
102
103template <typename Iter>
104inline int CalculateReserve(Iter begin, Iter end, std::forward_iterator_tag) {
105 return static_cast<int>(std::distance(begin, end));
106}
107
108template <typename Iter>
109inline int CalculateReserve(Iter /*begin*/, Iter /*end*/,
110 std::input_iterator_tag /*unused*/) {
111 return -1;
112}
113
114template <typename Iter>
115inline int CalculateReserve(Iter begin, Iter end) {
116 typedef typename std::iterator_traits<Iter>::iterator_category Category;
117 return CalculateReserve(begin, end, Category());
118}
119
120// Swaps two blocks of memory of size sizeof(T).
121template <typename T>
122inline void SwapBlock(char* p, char* q) {
123 T tmp;
124 memcpy(&tmp, p, sizeof(T));
125 memcpy(p, q, sizeof(T));
126 memcpy(q, &tmp, sizeof(T));
127}
128
129// Swaps two blocks of memory of size kSize:
130// template <int kSize> void memswap(char* p, char* q);
131
132template <int kSize>
133inline typename std::enable_if<(kSize == 0), void>::type memswap(char*, char*) {
134}
135
136#define PROTO_MEMSWAP_DEF_SIZE(reg_type, max_size) \
137 template <int kSize> \
138 typename std::enable_if<(kSize >= sizeof(reg_type) && kSize < (max_size)), \
139 void>::type \
140 memswap(char* p, char* q) { \
141 SwapBlock<reg_type>(p, q); \
142 memswap<kSize - sizeof(reg_type)>(p + sizeof(reg_type), \
143 q + sizeof(reg_type)); \
144 }
145
146PROTO_MEMSWAP_DEF_SIZE(uint8, 2)
147PROTO_MEMSWAP_DEF_SIZE(uint16, 4)
148PROTO_MEMSWAP_DEF_SIZE(uint32, 8)
149
150#ifdef __SIZEOF_INT128__
151PROTO_MEMSWAP_DEF_SIZE(uint64, 16)
152PROTO_MEMSWAP_DEF_SIZE(__uint128_t, (1u << 31))
153#else
154PROTO_MEMSWAP_DEF_SIZE(uint64, (1u << 31))
155#endif
156
157#undef PROTO_MEMSWAP_DEF_SIZE
158
159} // namespace internal
160
161// RepeatedField is used to represent repeated fields of a primitive type (in
162// other words, everything except strings and nested Messages). Most users will
163// not ever use a RepeatedField directly; they will use the get-by-index,
164// set-by-index, and add accessors that are generated for all repeated fields.
165template <typename Element>
166class RepeatedField final {
167 static_assert(
168 alignof(Arena) >= alignof(Element),
169 "We only support types that have an alignment smaller than Arena");
170
171 public:
172 RepeatedField();
173 explicit RepeatedField(Arena* arena);
174 RepeatedField(const RepeatedField& other);
175 template <typename Iter>
176 RepeatedField(Iter begin, const Iter& end);
177 ~RepeatedField();
178
179 RepeatedField& operator=(const RepeatedField& other);
180
181 RepeatedField(RepeatedField&& other) noexcept;
182 RepeatedField& operator=(RepeatedField&& other) noexcept;
183
184 bool empty() const;
185 int size() const;
186
187 const Element& Get(int index) const;
188 Element* Mutable(int index);
189
190 const Element& operator[](int index) const { return Get(index); }
191 Element& operator[](int index) { return *Mutable(index); }
192
193 const Element& at(int index) const;
194 Element& at(int index);
195
196 void Set(int index, const Element& value);
197 void Add(const Element& value);
198 // Appends a new element and return a pointer to it.
199 // The new element is uninitialized if |Element| is a POD type.
200 Element* Add();
201 // Append elements in the range [begin, end) after reserving
202 // the appropriate number of elements.
203 template <typename Iter>
204 void Add(Iter begin, Iter end);
205
206 // Remove the last element in the array.
207 void RemoveLast();
208
209 // Extract elements with indices in "[start .. start+num-1]".
210 // Copy them into "elements[0 .. num-1]" if "elements" is not NULL.
211 // Caution: implementation also moves elements with indices [start+num ..].
212 // Calling this routine inside a loop can cause quadratic behavior.
213 void ExtractSubrange(int start, int num, Element* elements);
214
215 void Clear();
216 void MergeFrom(const RepeatedField& other);
217 void CopyFrom(const RepeatedField& other);
218
219 // Reserve space to expand the field to at least the given size. If the
220 // array is grown, it will always be at least doubled in size.
221 void Reserve(int new_size);
222
223 // Resize the RepeatedField to a new, smaller size. This is O(1).
224 void Truncate(int new_size);
225
226 void AddAlreadyReserved(const Element& value);
227 // Appends a new element and return a pointer to it.
228 // The new element is uninitialized if |Element| is a POD type.
229 // Should be called only if Capacity() > Size().
230 Element* AddAlreadyReserved();
231 Element* AddNAlreadyReserved(int elements);
232 int Capacity() const;
233
234 // Like STL resize. Uses value to fill appended elements.
235 // Like Truncate() if new_size <= size(), otherwise this is
236 // O(new_size - size()).
237 void Resize(int new_size, const Element& value);
238
239 // Gets the underlying array. This pointer is possibly invalidated by
240 // any add or remove operation.
241 Element* mutable_data();
242 const Element* data() const;
243
244 // Swap entire contents with "other". If they are separate arenas then, copies
245 // data between each other.
246 void Swap(RepeatedField* other);
247
248 // Swap entire contents with "other". Should be called only if the caller can
249 // guarantee that both repeated fields are on the same arena or are on the
250 // heap. Swapping between different arenas is disallowed and caught by a
251 // GOOGLE_DCHECK (see API docs for details).
252 void UnsafeArenaSwap(RepeatedField* other);
253
254 // Swap two elements.
255 void SwapElements(int index1, int index2);
256
257 // STL-like iterator support
258 typedef Element* iterator;
259 typedef const Element* const_iterator;
260 typedef Element value_type;
261 typedef value_type& reference;
262 typedef const value_type& const_reference;
263 typedef value_type* pointer;
264 typedef const value_type* const_pointer;
265 typedef int size_type;
266 typedef ptrdiff_t difference_type;
267
268 iterator begin();
269 const_iterator begin() const;
270 const_iterator cbegin() const;
271 iterator end();
272 const_iterator end() const;
273 const_iterator cend() const;
274
275 // Reverse iterator support
276 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
277 typedef std::reverse_iterator<iterator> reverse_iterator;
278 reverse_iterator rbegin() { return reverse_iterator(end()); }
279 const_reverse_iterator rbegin() const {
280 return const_reverse_iterator(end());
281 }
282 reverse_iterator rend() { return reverse_iterator(begin()); }
283 const_reverse_iterator rend() const {
284 return const_reverse_iterator(begin());
285 }
286
287 // Returns the number of bytes used by the repeated field, excluding
288 // sizeof(*this)
289 size_t SpaceUsedExcludingSelfLong() const;
290
291 int SpaceUsedExcludingSelf() const {
292 return internal::ToIntSize(SpaceUsedExcludingSelfLong());
293 }
294
295 // Removes the element referenced by position.
296 //
297 // Returns an iterator to the element immediately following the removed
298 // element.
299 //
300 // Invalidates all iterators at or after the removed element, including end().
301 iterator erase(const_iterator position);
302
303 // Removes the elements in the range [first, last).
304 //
305 // Returns an iterator to the element immediately following the removed range.
306 //
307 // Invalidates all iterators at or after the removed range, including end().
308 iterator erase(const_iterator first, const_iterator last);
309
310 // Get the Arena on which this RepeatedField stores its elements.
311 inline Arena* GetArena() const {
312 return (total_size_ == 0) ? static_cast<Arena*>(arena_or_elements_)
313 : rep()->arena;
314 }
315
316 // For internal use only.
317 //
318 // This is public due to it being called by generated code.
319 inline void InternalSwap(RepeatedField* other);
320
321 private:
322 static constexpr int kInitialSize = 0;
323 // A note on the representation here (see also comment below for
324 // RepeatedPtrFieldBase's struct Rep):
325 //
326 // We maintain the same sizeof(RepeatedField) as before we added arena support
327 // so that we do not degrade performance by bloating memory usage. Directly
328 // adding an arena_ element to RepeatedField is quite costly. By using
329 // indirection in this way, we keep the same size when the RepeatedField is
330 // empty (common case), and add only an 8-byte header to the elements array
331 // when non-empty. We make sure to place the size fields directly in the
332 // RepeatedField class to avoid costly cache misses due to the indirection.
333 int current_size_;
334 int total_size_;
335 struct Rep {
336 Arena* arena;
337 Element elements[1];
338 };
339 // We can not use sizeof(Rep) - sizeof(Element) due to the trailing padding on
340 // the struct. We can not use sizeof(Arena*) as well because there might be
341 // a "gap" after the field arena and before the field elements (e.g., when
342 // Element is double and pointer is 32bit).
343 static const size_t kRepHeaderSize;
344
345 // If total_size_ == 0 this points to an Arena otherwise it points to the
346 // elements member of a Rep struct. Using this invariant allows the storage of
347 // the arena pointer without an extra allocation in the constructor.
348 void* arena_or_elements_;
349
350 // Return pointer to elements array.
351 // pre-condition: the array must have been allocated.
352 Element* elements() const {
353 GOOGLE_DCHECK_GT(total_size_, 0);
354 // Because of above pre-condition this cast is safe.
355 return unsafe_elements();
356 }
357
358 // Return pointer to elements array if it exists otherwise either null or
359 // a invalid pointer is returned. This only happens for empty repeated fields,
360 // where you can't dereference this pointer anyway (it's empty).
361 Element* unsafe_elements() const {
362 return static_cast<Element*>(arena_or_elements_);
363 }
364
365 // Return pointer to the Rep struct.
366 // pre-condition: the Rep must have been allocated, ie elements() is safe.
367 Rep* rep() const {
368 char* addr = reinterpret_cast<char*>(elements()) - offsetof(Rep, elements);
369 return reinterpret_cast<Rep*>(addr);
370 }
371
372 friend class Arena;
373 typedef void InternalArenaConstructable_;
374
375 // Move the contents of |from| into |to|, possibly clobbering |from| in the
376 // process. For primitive types this is just a memcpy(), but it could be
377 // specialized for non-primitive types to, say, swap each element instead.
378 void MoveArray(Element* to, Element* from, int size);
379
380 // Copy the elements of |from| into |to|.
381 void CopyArray(Element* to, const Element* from, int size);
382
383 // Internal helper to delete all elements and deallocate the storage.
384 // If Element has a trivial destructor (for example, if it's a fundamental
385 // type, like int32), the loop will be removed by the optimizer.
386 void InternalDeallocate(Rep* rep, int size) {
387 if (rep != NULL) {
388 Element* e = &rep->elements[0];
389 Element* limit = &rep->elements[size];
390 for (; e < limit; e++) {
391 e->~Element();
392 }
393 if (rep->arena == NULL) {
394#if defined(__GXX_DELETE_WITH_SIZE__) || defined(__cpp_sized_deallocation)
395 const size_t bytes = size * sizeof(*e) + kRepHeaderSize;
396 ::operator delete(static_cast<void*>(rep), bytes);
397#else
398 ::operator delete(static_cast<void*>(rep));
399#endif
400 }
401 }
402 }
403
404 // This class is a performance wrapper around RepeatedField::Add(const T&)
405 // function. In general unless a RepeatedField is a local stack variable LLVM
406 // has a hard time optimizing Add. The machine code tends to be
407 // loop:
408 // mov %size, dword ptr [%repeated_field] // load
409 // cmp %size, dword ptr [%repeated_field + 4]
410 // jae fallback
411 // mov %buffer, qword ptr [%repeated_field + 8]
412 // mov dword [%buffer + %size * 4], %value
413 // inc %size // increment
414 // mov dword ptr [%repeated_field], %size // store
415 // jmp loop
416 //
417 // This puts a load/store in each iteration of the important loop variable
418 // size. It's a pretty bad compile that happens even in simple cases, but
419 // largely the presence of the fallback path disturbs the compilers mem-to-reg
420 // analysis.
421 //
422 // This class takes ownership of a repeated field for the duration of it's
423 // lifetime. The repeated field should not be accessed during this time, ie.
424 // only access through this class is allowed. This class should always be a
425 // function local stack variable. Intended use
426 //
427 // void AddSequence(const int* begin, const int* end, RepeatedField<int>* out)
428 // {
429 // RepeatedFieldAdder<int> adder(out); // Take ownership of out
430 // for (auto it = begin; it != end; ++it) {
431 // adder.Add(*it);
432 // }
433 // }
434 //
435 // Typically due to the fact adder is a local stack variable. The compiler
436 // will be successful in mem-to-reg transformation and the machine code will
437 // be loop: cmp %size, %capacity jae fallback mov dword ptr [%buffer + %size *
438 // 4], %val inc %size jmp loop
439 //
440 // The first version executes at 7 cycles per iteration while the second
441 // version near 1 or 2 cycles.
442 template <int = 0, bool = std::is_pod<Element>::value>
443 class FastAdderImpl {
444 public:
445 explicit FastAdderImpl(RepeatedField* rf) : repeated_field_(rf) {
446 index_ = repeated_field_->current_size_;
447 capacity_ = repeated_field_->total_size_;
448 buffer_ = repeated_field_->unsafe_elements();
449 }
450 ~FastAdderImpl() { repeated_field_->current_size_ = index_; }
451
452 void Add(Element val) {
453 if (index_ == capacity_) {
454 repeated_field_->current_size_ = index_;
455 repeated_field_->Reserve(index_ + 1);
456 capacity_ = repeated_field_->total_size_;
457 buffer_ = repeated_field_->unsafe_elements();
458 }
459 buffer_[index_++] = val;
460 }
461
462 private:
463 RepeatedField* repeated_field_;
464 int index_;
465 int capacity_;
466 Element* buffer_;
467
468 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(FastAdderImpl);
469 };
470
471 // FastAdder is a wrapper for adding fields. The specialization above handles
472 // POD types more efficiently than RepeatedField.
473 template <int I>
474 class FastAdderImpl<I, false> {
475 public:
476 explicit FastAdderImpl(RepeatedField* rf) : repeated_field_(rf) {}
477 void Add(const Element& val) { repeated_field_->Add(val); }
478
479 private:
480 RepeatedField* repeated_field_;
481 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(FastAdderImpl);
482 };
483
484 using FastAdder = FastAdderImpl<>;
485
486 friend class TestRepeatedFieldHelper;
487 friend class ::google::protobuf::internal::ParseContext;
488};
489
490template <typename Element>
491const size_t RepeatedField<Element>::kRepHeaderSize =
492 reinterpret_cast<size_t>(&reinterpret_cast<Rep*>(16)->elements[0]) - 16;
493
494namespace internal {
495template <typename It>
496class RepeatedPtrIterator;
497template <typename It, typename VoidPtr>
498class RepeatedPtrOverPtrsIterator;
499} // namespace internal
500
501namespace internal {
502
503// This is a helper template to copy an array of elements efficiently when they
504// have a trivial copy constructor, and correctly otherwise. This really
505// shouldn't be necessary, but our compiler doesn't optimize std::copy very
506// effectively.
507template <typename Element,
508 bool HasTrivialCopy =
509 std::is_pod<Element>::value>
510struct ElementCopier {
511 void operator()(Element* to, const Element* from, int array_size);
512};
513
514} // namespace internal
515
516namespace internal {
517
518// type-traits helper for RepeatedPtrFieldBase: we only want to invoke
519// arena-related "copy if on different arena" behavior if the necessary methods
520// exist on the contained type. In particular, we rely on MergeFrom() existing
521// as a general proxy for the fact that a copy will work, and we also provide a
522// specific override for std::string*.
523template <typename T>
524struct TypeImplementsMergeBehaviorProbeForMergeFrom {
525 typedef char HasMerge;
526 typedef long HasNoMerge;
527
528 // We accept either of:
529 // - void MergeFrom(const T& other)
530 // - bool MergeFrom(const T& other)
531 //
532 // We mangle these names a bit to avoid compatibility issues in 'unclean'
533 // include environments that may have, e.g., "#define test ..." (yes, this
534 // exists).
535 template <typename U, typename RetType, RetType (U::*)(const U& arg)>
536 struct CheckType;
537 template <typename U>
538 static HasMerge Check(CheckType<U, void, &U::MergeFrom>*);
539 template <typename U>
540 static HasMerge Check(CheckType<U, bool, &U::MergeFrom>*);
541 template <typename U>
542 static HasNoMerge Check(...);
543
544 // Resolves to either std::true_type or std::false_type.
545 typedef std::integral_constant<bool,
546 (sizeof(Check<T>(0)) == sizeof(HasMerge))>
547 type;
548};
549
550template <typename T, typename = void>
551struct TypeImplementsMergeBehavior
552 : TypeImplementsMergeBehaviorProbeForMergeFrom<T> {};
553
554
555template <>
556struct TypeImplementsMergeBehavior<std::string> {
557 typedef std::true_type type;
558};
559
560template <typename T>
561struct IsMovable
562 : std::integral_constant<bool, std::is_move_constructible<T>::value &&
563 std::is_move_assignable<T>::value> {};
564
565// This is the common base class for RepeatedPtrFields. It deals only in void*
566// pointers. Users should not use this interface directly.
567//
568// The methods of this interface correspond to the methods of RepeatedPtrField,
569// but may have a template argument called TypeHandler. Its signature is:
570// class TypeHandler {
571// public:
572// typedef MyType Type;
573// static Type* New();
574// static Type* NewFromPrototype(const Type* prototype,
575// Arena* arena);
576// static void Delete(Type*);
577// static void Clear(Type*);
578// static void Merge(const Type& from, Type* to);
579//
580// // Only needs to be implemented if SpaceUsedExcludingSelf() is called.
581// static int SpaceUsedLong(const Type&);
582// };
583class PROTOBUF_EXPORT RepeatedPtrFieldBase {
584 protected:
585 RepeatedPtrFieldBase();
586 explicit RepeatedPtrFieldBase(Arena* arena);
587 ~RepeatedPtrFieldBase() {
588#ifndef NDEBUG
589 // Try to trigger segfault / asan failure in non-opt builds. If arena_
590 // lifetime has ended before the destructor.
591 if (arena_) (void)arena_->SpaceAllocated();
592#endif
593 }
594
595 public:
596 // Must be called from destructor.
597 template <typename TypeHandler>
598 void Destroy();
599
600 protected:
601 bool empty() const;
602 int size() const;
603
604 template <typename TypeHandler>
605 const typename TypeHandler::Type& at(int index) const;
606 template <typename TypeHandler>
607 typename TypeHandler::Type& at(int index);
608
609 template <typename TypeHandler>
610 typename TypeHandler::Type* Mutable(int index);
611 template <typename TypeHandler>
612 void Delete(int index);
613 template <typename TypeHandler>
614 typename TypeHandler::Type* Add(typename TypeHandler::Type* prototype = NULL);
615
616 public:
617 // The next few methods are public so that they can be called from generated
618 // code when implicit weak fields are used, but they should never be called by
619 // application code.
620
621 template <typename TypeHandler>
622 const typename TypeHandler::Type& Get(int index) const;
623
624 // Creates and adds an element using the given prototype, without introducing
625 // a link-time dependency on the concrete message type. This method is used to
626 // implement implicit weak fields. The prototype may be NULL, in which case an
627 // ImplicitWeakMessage will be used as a placeholder.
628 MessageLite* AddWeak(const MessageLite* prototype);
629
630 template <typename TypeHandler>
631 void Clear();
632
633 template <typename TypeHandler>
634 void MergeFrom(const RepeatedPtrFieldBase& other);
635
636 inline void InternalSwap(RepeatedPtrFieldBase* other);
637
638 protected:
639 template <
640 typename TypeHandler,
641 typename std::enable_if<TypeHandler::Movable::value>::type* = nullptr>
642 void Add(typename TypeHandler::Type&& value);
643
644 template <typename TypeHandler>
645 void RemoveLast();
646 template <typename TypeHandler>
647 void CopyFrom(const RepeatedPtrFieldBase& other);
648
649 void CloseGap(int start, int num);
650
651 void Reserve(int new_size);
652
653 int Capacity() const;
654
655 // Used for constructing iterators.
656 void* const* raw_data() const;
657 void** raw_mutable_data() const;
658
659 template <typename TypeHandler>
660 typename TypeHandler::Type** mutable_data();
661 template <typename TypeHandler>
662 const typename TypeHandler::Type* const* data() const;
663
664 template <typename TypeHandler>
665 PROTOBUF_ALWAYS_INLINE void Swap(RepeatedPtrFieldBase* other);
666
667 void SwapElements(int index1, int index2);
668
669 template <typename TypeHandler>
670 size_t SpaceUsedExcludingSelfLong() const;
671
672 // Advanced memory management --------------------------------------
673
674 // Like Add(), but if there are no cleared objects to use, returns NULL.
675 template <typename TypeHandler>
676 typename TypeHandler::Type* AddFromCleared();
677
678 template <typename TypeHandler>
679 void AddAllocated(typename TypeHandler::Type* value) {
680 typename TypeImplementsMergeBehavior<typename TypeHandler::Type>::type t;
681 AddAllocatedInternal<TypeHandler>(value, t);
682 }
683
684 template <typename TypeHandler>
685 void UnsafeArenaAddAllocated(typename TypeHandler::Type* value);
686
687 template <typename TypeHandler>
688 typename TypeHandler::Type* ReleaseLast() {
689 typename TypeImplementsMergeBehavior<typename TypeHandler::Type>::type t;
690 return ReleaseLastInternal<TypeHandler>(t);
691 }
692
693 // Releases last element and returns it, but does not do out-of-arena copy.
694 // And just returns the raw pointer to the contained element in the arena.
695 template <typename TypeHandler>
696 typename TypeHandler::Type* UnsafeArenaReleaseLast();
697
698 int ClearedCount() const;
699 template <typename TypeHandler>
700 void AddCleared(typename TypeHandler::Type* value);
701 template <typename TypeHandler>
702 typename TypeHandler::Type* ReleaseCleared();
703
704 template <typename TypeHandler>
705 void AddAllocatedInternal(typename TypeHandler::Type* value, std::true_type);
706 template <typename TypeHandler>
707 void AddAllocatedInternal(typename TypeHandler::Type* value, std::false_type);
708
709 template <typename TypeHandler>
710 PROTOBUF_NOINLINE void AddAllocatedSlowWithCopy(
711 typename TypeHandler::Type* value, Arena* value_arena, Arena* my_arena);
712 template <typename TypeHandler>
713 PROTOBUF_NOINLINE void AddAllocatedSlowWithoutCopy(
714 typename TypeHandler::Type* value);
715
716 template <typename TypeHandler>
717 typename TypeHandler::Type* ReleaseLastInternal(std::true_type);
718 template <typename TypeHandler>
719 typename TypeHandler::Type* ReleaseLastInternal(std::false_type);
720
721 template <typename TypeHandler>
722 PROTOBUF_NOINLINE void SwapFallback(RepeatedPtrFieldBase* other);
723
724 inline Arena* GetArena() const { return arena_; }
725
726 private:
727 static constexpr int kInitialSize = 0;
728 // A few notes on internal representation:
729 //
730 // We use an indirected approach, with struct Rep, to keep
731 // sizeof(RepeatedPtrFieldBase) equivalent to what it was before arena support
732 // was added, namely, 3 8-byte machine words on x86-64. An instance of Rep is
733 // allocated only when the repeated field is non-empty, and it is a
734 // dynamically-sized struct (the header is directly followed by elements[]).
735 // We place arena_ and current_size_ directly in the object to avoid cache
736 // misses due to the indirection, because these fields are checked frequently.
737 // Placing all fields directly in the RepeatedPtrFieldBase instance costs
738 // significant performance for memory-sensitive workloads.
739 Arena* arena_;
740 int current_size_;
741 int total_size_;
742 struct Rep {
743 int allocated_size;
744 void* elements[1];
745 };
746 static constexpr size_t kRepHeaderSize = sizeof(Rep) - sizeof(void*);
747 Rep* rep_;
748
749 template <typename TypeHandler>
750 static inline typename TypeHandler::Type* cast(void* element) {
751 return reinterpret_cast<typename TypeHandler::Type*>(element);
752 }
753 template <typename TypeHandler>
754 static inline const typename TypeHandler::Type* cast(const void* element) {
755 return reinterpret_cast<const typename TypeHandler::Type*>(element);
756 }
757
758 // Non-templated inner function to avoid code duplication. Takes a function
759 // pointer to the type-specific (templated) inner allocate/merge loop.
760 void MergeFromInternal(const RepeatedPtrFieldBase& other,
761 void (RepeatedPtrFieldBase::*inner_loop)(void**,
762 void**, int,
763 int));
764
765 template <typename TypeHandler>
766 void MergeFromInnerLoop(void** our_elems, void** other_elems, int length,
767 int already_allocated);
768
769 // Internal helper: extend array space if necessary to contain |extend_amount|
770 // more elements, and return a pointer to the element immediately following
771 // the old list of elements. This interface factors out common behavior from
772 // Reserve() and MergeFrom() to reduce code size. |extend_amount| must be > 0.
773 void** InternalExtend(int extend_amount);
774
775 // The reflection implementation needs to call protected methods directly,
776 // reinterpreting pointers as being to Message instead of a specific Message
777 // subclass.
778 friend class ::PROTOBUF_NAMESPACE_ID::Reflection;
779
780 // ExtensionSet stores repeated message extensions as
781 // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to implement
782 // SpaceUsedLong(), and thus need to call SpaceUsedExcludingSelfLong()
783 // reinterpreting MessageLite as Message. ExtensionSet also needs to make use
784 // of AddFromCleared(), which is not part of the public interface.
785 friend class ExtensionSet;
786
787 // The MapFieldBase implementation needs to call protected methods directly,
788 // reinterpreting pointers as being to Message instead of a specific Message
789 // subclass.
790 friend class MapFieldBase;
791
792 // The table-driven MergePartialFromCodedStream implementation needs to
793 // operate on RepeatedPtrField<MessageLite>.
794 friend class MergePartialFromCodedStreamHelper;
795 friend class AccessorHelper;
796 template <typename T>
797 friend struct google::protobuf::WeakRepeatedPtrField;
798
799 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase);
800};
801
802template <typename GenericType>
803class GenericTypeHandler {
804 public:
805 typedef GenericType Type;
806 using Movable = IsMovable<GenericType>;
807
808 static inline GenericType* New(Arena* arena) {
809 return Arena::CreateMaybeMessage<Type>(arena);
810 }
811 static inline GenericType* New(Arena* arena, GenericType&& value) {
812 return Arena::Create<GenericType>(arena, std::move(value));
813 }
814 static inline GenericType* NewFromPrototype(const GenericType* prototype,
815 Arena* arena = NULL);
816 static inline void Delete(GenericType* value, Arena* arena) {
817 if (arena == NULL) {
818 delete value;
819 }
820 }
821 static inline Arena* GetArena(GenericType* value) {
822 return Arena::GetArena<Type>(value);
823 }
824 static inline void* GetMaybeArenaPointer(GenericType* value) {
825 return Arena::GetArena<Type>(value);
826 }
827
828 static inline void Clear(GenericType* value) { value->Clear(); }
829 PROTOBUF_NOINLINE
830 static void Merge(const GenericType& from, GenericType* to);
831 static inline size_t SpaceUsedLong(const GenericType& value) {
832 return value.SpaceUsedLong();
833 }
834};
835
836template <typename GenericType>
837GenericType* GenericTypeHandler<GenericType>::NewFromPrototype(
838 const GenericType* /* prototype */, Arena* arena) {
839 return New(arena);
840}
841template <typename GenericType>
842void GenericTypeHandler<GenericType>::Merge(const GenericType& from,
843 GenericType* to) {
844 to->MergeFrom(from);
845}
846
847// NewFromPrototype() and Merge() are not defined inline here, as we will need
848// to do a virtual function dispatch anyways to go from Message* to call
849// New/Merge.
850template <>
851MessageLite* GenericTypeHandler<MessageLite>::NewFromPrototype(
852 const MessageLite* prototype, Arena* arena);
853template <>
854inline Arena* GenericTypeHandler<MessageLite>::GetArena(MessageLite* value) {
855 return value->GetArena();
856}
857template <>
858inline void* GenericTypeHandler<MessageLite>::GetMaybeArenaPointer(
859 MessageLite* value) {
860 return value->GetMaybeArenaPointer();
861}
862template <>
863void GenericTypeHandler<MessageLite>::Merge(const MessageLite& from,
864 MessageLite* to);
865template <>
866inline void GenericTypeHandler<std::string>::Clear(std::string* value) {
867 value->clear();
868}
869template <>
870void GenericTypeHandler<std::string>::Merge(const std::string& from,
871 std::string* to);
872
873// Message specialization bodies defined in message.cc. This split is necessary
874// to allow proto2-lite (which includes this header) to be independent of
875// Message.
876template <>
877PROTOBUF_EXPORT Message* GenericTypeHandler<Message>::NewFromPrototype(
878 const Message* prototype, Arena* arena);
879template <>
880PROTOBUF_EXPORT Arena* GenericTypeHandler<Message>::GetArena(Message* value);
881template <>
882PROTOBUF_EXPORT void* GenericTypeHandler<Message>::GetMaybeArenaPointer(
883 Message* value);
884
885class StringTypeHandler {
886 public:
887 typedef std::string Type;
888 using Movable = IsMovable<Type>;
889
890 static inline std::string* New(Arena* arena) {
891 return Arena::Create<std::string>(arena);
892 }
893 static inline std::string* New(Arena* arena, std::string&& value) {
894 return Arena::Create<std::string>(arena, std::move(value));
895 }
896 static inline std::string* NewFromPrototype(const std::string*,
897 Arena* arena) {
898 return New(arena);
899 }
900 static inline Arena* GetArena(std::string*) { return NULL; }
901 static inline void* GetMaybeArenaPointer(std::string* /* value */) {
902 return NULL;
903 }
904 static inline void Delete(std::string* value, Arena* arena) {
905 if (arena == NULL) {
906 delete value;
907 }
908 }
909 static inline void Clear(std::string* value) { value->clear(); }
910 static inline void Merge(const std::string& from, std::string* to) {
911 *to = from;
912 }
913 static size_t SpaceUsedLong(const std::string& value) {
914 return sizeof(value) + StringSpaceUsedExcludingSelfLong(value);
915 }
916};
917
918} // namespace internal
919
920// RepeatedPtrField is like RepeatedField, but used for repeated strings or
921// Messages.
922template <typename Element>
923class RepeatedPtrField final : private internal::RepeatedPtrFieldBase {
924 public:
925 RepeatedPtrField();
926 explicit RepeatedPtrField(Arena* arena);
927
928 RepeatedPtrField(const RepeatedPtrField& other);
929 template <typename Iter>
930 RepeatedPtrField(Iter begin, const Iter& end);
931 ~RepeatedPtrField();
932
933 RepeatedPtrField& operator=(const RepeatedPtrField& other);
934
935 RepeatedPtrField(RepeatedPtrField&& other) noexcept;
936 RepeatedPtrField& operator=(RepeatedPtrField&& other) noexcept;
937
938 bool empty() const;
939 int size() const;
940
941 const Element& Get(int index) const;
942 Element* Mutable(int index);
943 Element* Add();
944 void Add(Element&& value);
945
946 const Element& operator[](int index) const { return Get(index); }
947 Element& operator[](int index) { return *Mutable(index); }
948
949 const Element& at(int index) const;
950 Element& at(int index);
951
952 // Remove the last element in the array.
953 // Ownership of the element is retained by the array.
954 void RemoveLast();
955
956 // Delete elements with indices in the range [start .. start+num-1].
957 // Caution: implementation moves all elements with indices [start+num .. ].
958 // Calling this routine inside a loop can cause quadratic behavior.
959 void DeleteSubrange(int start, int num);
960
961 void Clear();
962 void MergeFrom(const RepeatedPtrField& other);
963 void CopyFrom(const RepeatedPtrField& other);
964
965 // Reserve space to expand the field to at least the given size. This only
966 // resizes the pointer array; it doesn't allocate any objects. If the
967 // array is grown, it will always be at least doubled in size.
968 void Reserve(int new_size);
969
970 int Capacity() const;
971
972 // Gets the underlying array. This pointer is possibly invalidated by
973 // any add or remove operation.
974 Element** mutable_data();
975 const Element* const* data() const;
976
977 // Swap entire contents with "other". If they are on separate arenas, then
978 // copies data.
979 void Swap(RepeatedPtrField* other);
980
981 // Swap entire contents with "other". Caller should guarantee that either both
982 // fields are on the same arena or both are on the heap. Swapping between
983 // different arenas with this function is disallowed and is caught via
984 // GOOGLE_DCHECK.
985 void UnsafeArenaSwap(RepeatedPtrField* other);
986
987 // Swap two elements.
988 void SwapElements(int index1, int index2);
989
990 // STL-like iterator support
991 typedef internal::RepeatedPtrIterator<Element> iterator;
992 typedef internal::RepeatedPtrIterator<const Element> const_iterator;
993 typedef Element value_type;
994 typedef value_type& reference;
995 typedef const value_type& const_reference;
996 typedef value_type* pointer;
997 typedef const value_type* const_pointer;
998 typedef int size_type;
999 typedef ptrdiff_t difference_type;
1000
1001 iterator begin();
1002 const_iterator begin() const;
1003 const_iterator cbegin() const;
1004 iterator end();
1005 const_iterator end() const;
1006 const_iterator cend() const;
1007
1008 // Reverse iterator support
1009 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1010 typedef std::reverse_iterator<iterator> reverse_iterator;
1011 reverse_iterator rbegin() { return reverse_iterator(end()); }
1012 const_reverse_iterator rbegin() const {
1013 return const_reverse_iterator(end());
1014 }
1015 reverse_iterator rend() { return reverse_iterator(begin()); }
1016 const_reverse_iterator rend() const {
1017 return const_reverse_iterator(begin());
1018 }
1019
1020 // Custom STL-like iterator that iterates over and returns the underlying
1021 // pointers to Element rather than Element itself.
1022 typedef internal::RepeatedPtrOverPtrsIterator<Element*, void*>
1023 pointer_iterator;
1024 typedef internal::RepeatedPtrOverPtrsIterator<const Element* const,
1025 const void* const>
1026 const_pointer_iterator;
1027 pointer_iterator pointer_begin();
1028 const_pointer_iterator pointer_begin() const;
1029 pointer_iterator pointer_end();
1030 const_pointer_iterator pointer_end() const;
1031
1032 // Returns (an estimate of) the number of bytes used by the repeated field,
1033 // excluding sizeof(*this).
1034 size_t SpaceUsedExcludingSelfLong() const;
1035
1036 int SpaceUsedExcludingSelf() const {
1037 return internal::ToIntSize(SpaceUsedExcludingSelfLong());
1038 }
1039
1040 // Advanced memory management --------------------------------------
1041 // When hardcore memory management becomes necessary -- as it sometimes
1042 // does here at Google -- the following methods may be useful.
1043
1044 // Add an already-allocated object, passing ownership to the
1045 // RepeatedPtrField.
1046 //
1047 // Note that some special behavior occurs with respect to arenas:
1048 //
1049 // (i) if this field holds submessages, the new submessage will be copied if
1050 // the original is in an arena and this RepeatedPtrField is either in a
1051 // different arena, or on the heap.
1052 // (ii) if this field holds strings, the passed-in string *must* be
1053 // heap-allocated, not arena-allocated. There is no way to dynamically check
1054 // this at runtime, so User Beware.
1055 void AddAllocated(Element* value);
1056
1057 // Remove the last element and return it, passing ownership to the caller.
1058 // Requires: size() > 0
1059 //
1060 // If this RepeatedPtrField is on an arena, an object copy is required to pass
1061 // ownership back to the user (for compatible semantics). Use
1062 // UnsafeArenaReleaseLast() if this behavior is undesired.
1063 Element* ReleaseLast();
1064
1065 // Add an already-allocated object, skipping arena-ownership checks. The user
1066 // must guarantee that the given object is in the same arena as this
1067 // RepeatedPtrField.
1068 // It is also useful in legacy code that uses temporary ownership to avoid
1069 // copies. Example:
1070 // RepeatedPtrField<T> temp_field;
1071 // temp_field.AddAllocated(new T);
1072 // ... // Do something with temp_field
1073 // temp_field.ExtractSubrange(0, temp_field.size(), nullptr);
1074 // If you put temp_field on the arena this fails, because the ownership
1075 // transfers to the arena at the "AddAllocated" call and is not released
1076 // anymore causing a double delete. UnsafeArenaAddAllocated prevents this.
1077 void UnsafeArenaAddAllocated(Element* value);
1078
1079 // Remove the last element and return it. Works only when operating on an
1080 // arena. The returned pointer is to the original object in the arena, hence
1081 // has the arena's lifetime.
1082 // Requires: current_size_ > 0
1083 Element* UnsafeArenaReleaseLast();
1084
1085 // Extract elements with indices in the range "[start .. start+num-1]".
1086 // The caller assumes ownership of the extracted elements and is responsible
1087 // for deleting them when they are no longer needed.
1088 // If "elements" is non-NULL, then pointers to the extracted elements
1089 // are stored in "elements[0 .. num-1]" for the convenience of the caller.
1090 // If "elements" is NULL, then the caller must use some other mechanism
1091 // to perform any further operations (like deletion) on these elements.
1092 // Caution: implementation also moves elements with indices [start+num ..].
1093 // Calling this routine inside a loop can cause quadratic behavior.
1094 //
1095 // Memory copying behavior is identical to ReleaseLast(), described above: if
1096 // this RepeatedPtrField is on an arena, an object copy is performed for each
1097 // returned element, so that all returned element pointers are to
1098 // heap-allocated copies. If this copy is not desired, the user should call
1099 // UnsafeArenaExtractSubrange().
1100 void ExtractSubrange(int start, int num, Element** elements);
1101
1102 // Identical to ExtractSubrange() described above, except that when this
1103 // repeated field is on an arena, no object copies are performed. Instead, the
1104 // raw object pointers are returned. Thus, if on an arena, the returned
1105 // objects must not be freed, because they will not be heap-allocated objects.
1106 void UnsafeArenaExtractSubrange(int start, int num, Element** elements);
1107
1108 // When elements are removed by calls to RemoveLast() or Clear(), they
1109 // are not actually freed. Instead, they are cleared and kept so that
1110 // they can be reused later. This can save lots of CPU time when
1111 // repeatedly reusing a protocol message for similar purposes.
1112 //
1113 // Hardcore programs may choose to manipulate these cleared objects
1114 // to better optimize memory management using the following routines.
1115
1116 // Get the number of cleared objects that are currently being kept
1117 // around for reuse.
1118 int ClearedCount() const;
1119 // Add an element to the pool of cleared objects, passing ownership to
1120 // the RepeatedPtrField. The element must be cleared prior to calling
1121 // this method.
1122 //
1123 // This method cannot be called when the repeated field is on an arena or when
1124 // |value| is; both cases will trigger a GOOGLE_DCHECK-failure.
1125 void AddCleared(Element* value);
1126 // Remove a single element from the cleared pool and return it, passing
1127 // ownership to the caller. The element is guaranteed to be cleared.
1128 // Requires: ClearedCount() > 0
1129 //
1130 //
1131 // This method cannot be called when the repeated field is on an arena; doing
1132 // so will trigger a GOOGLE_DCHECK-failure.
1133 Element* ReleaseCleared();
1134
1135 // Removes the element referenced by position.
1136 //
1137 // Returns an iterator to the element immediately following the removed
1138 // element.
1139 //
1140 // Invalidates all iterators at or after the removed element, including end().
1141 iterator erase(const_iterator position);
1142
1143 // Removes the elements in the range [first, last).
1144 //
1145 // Returns an iterator to the element immediately following the removed range.
1146 //
1147 // Invalidates all iterators at or after the removed range, including end().
1148 iterator erase(const_iterator first, const_iterator last);
1149
1150 // Gets the arena on which this RepeatedPtrField stores its elements.
1151 inline Arena* GetArena() const;
1152
1153 // For internal use only.
1154 //
1155 // This is public due to it being called by generated code.
1156 void InternalSwap(RepeatedPtrField* other) {
1157 internal::RepeatedPtrFieldBase::InternalSwap(other);
1158 }
1159
1160 private:
1161 // Note: RepeatedPtrField SHOULD NOT be subclassed by users.
1162 class TypeHandler;
1163
1164 // Implementations for ExtractSubrange(). The copying behavior must be
1165 // included only if the type supports the necessary operations (e.g.,
1166 // MergeFrom()), so we must resolve this at compile time. ExtractSubrange()
1167 // uses SFINAE to choose one of the below implementations.
1168 void ExtractSubrangeInternal(int start, int num, Element** elements,
1169 std::true_type);
1170 void ExtractSubrangeInternal(int start, int num, Element** elements,
1171 std::false_type);
1172
1173 friend class Arena;
1174
1175 template <typename T>
1176 friend struct WeakRepeatedPtrField;
1177
1178 typedef void InternalArenaConstructable_;
1179
1180};
1181
1182// implementation ====================================================
1183
1184template <typename Element>
1185inline RepeatedField<Element>::RepeatedField()
1186 : current_size_(0), total_size_(0), arena_or_elements_(nullptr) {}
1187
1188template <typename Element>
1189inline RepeatedField<Element>::RepeatedField(Arena* arena)
1190 : current_size_(0), total_size_(0), arena_or_elements_(arena) {}
1191
1192template <typename Element>
1193inline RepeatedField<Element>::RepeatedField(const RepeatedField& other)
1194 : current_size_(0), total_size_(0), arena_or_elements_(nullptr) {
1195 if (other.current_size_ != 0) {
1196 Reserve(other.size());
1197 AddNAlreadyReserved(other.size());
1198 CopyArray(Mutable(0), &other.Get(0), other.size());
1199 }
1200}
1201
1202template <typename Element>
1203template <typename Iter>
1204RepeatedField<Element>::RepeatedField(Iter begin, const Iter& end)
1205 : current_size_(0), total_size_(0), arena_or_elements_(nullptr) {
1206 Add(begin, end);
1207}
1208
1209template <typename Element>
1210RepeatedField<Element>::~RepeatedField() {
1211 if (total_size_ > 0) {
1212 InternalDeallocate(rep(), total_size_);
1213 }
1214}
1215
1216template <typename Element>
1217inline RepeatedField<Element>& RepeatedField<Element>::operator=(
1218 const RepeatedField& other) {
1219 if (this != &other) CopyFrom(other);
1220 return *this;
1221}
1222
1223template <typename Element>
1224inline RepeatedField<Element>::RepeatedField(RepeatedField&& other) noexcept
1225 : RepeatedField() {
1226 // We don't just call Swap(&other) here because it would perform 3 copies if
1227 // other is on an arena. This field can't be on an arena because arena
1228 // construction always uses the Arena* accepting constructor.
1229 if (other.GetArena()) {
1230 CopyFrom(other);
1231 } else {
1232 InternalSwap(&other);
1233 }
1234}
1235
1236template <typename Element>
1237inline RepeatedField<Element>& RepeatedField<Element>::operator=(
1238 RepeatedField&& other) noexcept {
1239 // We don't just call Swap(&other) here because it would perform 3 copies if
1240 // the two fields are on different arenas.
1241 if (this != &other) {
1242 if (this->GetArena() != other.GetArena()) {
1243 CopyFrom(other);
1244 } else {
1245 InternalSwap(&other);
1246 }
1247 }
1248 return *this;
1249}
1250
1251template <typename Element>
1252inline bool RepeatedField<Element>::empty() const {
1253 return current_size_ == 0;
1254}
1255
1256template <typename Element>
1257inline int RepeatedField<Element>::size() const {
1258 return current_size_;
1259}
1260
1261template <typename Element>
1262inline int RepeatedField<Element>::Capacity() const {
1263 return total_size_;
1264}
1265
1266template <typename Element>
1267inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) {
1268 GOOGLE_DCHECK_LT(current_size_, total_size_);
1269 elements()[current_size_++] = value;
1270}
1271
1272template <typename Element>
1273inline Element* RepeatedField<Element>::AddAlreadyReserved() {
1274 GOOGLE_DCHECK_LT(current_size_, total_size_);
1275 return &elements()[current_size_++];
1276}
1277
1278template <typename Element>
1279inline Element* RepeatedField<Element>::AddNAlreadyReserved(int n) {
1280 GOOGLE_DCHECK_GE(total_size_ - current_size_, n)
1281 << total_size_ << ", " << current_size_;
1282 // Warning: sometimes people call this when n == 0 and total_size_ == 0. In
1283 // this case the return pointer points to a zero size array (n == 0). Hence
1284 // we can just use unsafe_elements(), because the user cannot dereference the
1285 // pointer anyway.
1286 Element* ret = unsafe_elements() + current_size_;
1287 current_size_ += n;
1288 return ret;
1289}
1290
1291template <typename Element>
1292inline void RepeatedField<Element>::Resize(int new_size, const Element& value) {
1293 GOOGLE_DCHECK_GE(new_size, 0);
1294 if (new_size > current_size_) {
1295 Reserve(new_size);
1296 std::fill(&elements()[current_size_], &elements()[new_size], value);
1297 }
1298 current_size_ = new_size;
1299}
1300
1301template <typename Element>
1302inline const Element& RepeatedField<Element>::Get(int index) const {
1303 GOOGLE_DCHECK_GE(index, 0);
1304 GOOGLE_DCHECK_LT(index, current_size_);
1305 return elements()[index];
1306}
1307
1308template <typename Element>
1309inline const Element& RepeatedField<Element>::at(int index) const {
1310 GOOGLE_CHECK_GE(index, 0);
1311 GOOGLE_CHECK_LT(index, current_size_);
1312 return elements()[index];
1313}
1314
1315template <typename Element>
1316inline Element& RepeatedField<Element>::at(int index) {
1317 GOOGLE_CHECK_GE(index, 0);
1318 GOOGLE_CHECK_LT(index, current_size_);
1319 return elements()[index];
1320}
1321
1322template <typename Element>
1323inline Element* RepeatedField<Element>::Mutable(int index) {
1324 GOOGLE_DCHECK_GE(index, 0);
1325 GOOGLE_DCHECK_LT(index, current_size_);
1326 return &elements()[index];
1327}
1328
1329template <typename Element>
1330inline void RepeatedField<Element>::Set(int index, const Element& value) {
1331 GOOGLE_DCHECK_GE(index, 0);
1332 GOOGLE_DCHECK_LT(index, current_size_);
1333 elements()[index] = value;
1334}
1335
1336template <typename Element>
1337inline void RepeatedField<Element>::Add(const Element& value) {
1338 uint32 size = current_size_;
1339 if (static_cast<int>(size) == total_size_) {
1340 // value could reference an element of the array. Reserving new space will
1341 // invalidate the reference. So we must make a copy first.
1342 auto tmp = value;
1343 Reserve(total_size_ + 1);
1344 elements()[size] = std::move(tmp);
1345 } else {
1346 elements()[size] = value;
1347 }
1348 current_size_ = size + 1;
1349}
1350
1351template <typename Element>
1352inline Element* RepeatedField<Element>::Add() {
1353 uint32 size = current_size_;
1354 if (static_cast<int>(size) == total_size_) Reserve(total_size_ + 1);
1355 auto ptr = &elements()[size];
1356 current_size_ = size + 1;
1357 return ptr;
1358}
1359
1360template <typename Element>
1361template <typename Iter>
1362inline void RepeatedField<Element>::Add(Iter begin, Iter end) {
1363 int reserve = internal::CalculateReserve(begin, end);
1364 if (reserve != -1) {
1365 if (reserve == 0) {
1366 return;
1367 }
1368
1369 Reserve(reserve + size());
1370 // TODO(ckennelly): The compiler loses track of the buffer freshly
1371 // allocated by Reserve() by the time we call elements, so it cannot
1372 // guarantee that elements does not alias [begin(), end()).
1373 //
1374 // If restrict is available, annotating the pointer obtained from elements()
1375 // causes this to lower to memcpy instead of memmove.
1376 std::copy(begin, end, elements() + size());
1377 current_size_ = reserve + size();
1378 } else {
1379 FastAdder fast_adder(this);
1380 for (; begin != end; ++begin) fast_adder.Add(*begin);
1381 }
1382}
1383
1384template <typename Element>
1385inline void RepeatedField<Element>::RemoveLast() {
1386 GOOGLE_DCHECK_GT(current_size_, 0);
1387 current_size_--;
1388}
1389
1390template <typename Element>
1391void RepeatedField<Element>::ExtractSubrange(int start, int num,
1392 Element* elements) {
1393 GOOGLE_DCHECK_GE(start, 0);
1394 GOOGLE_DCHECK_GE(num, 0);
1395 GOOGLE_DCHECK_LE(start + num, this->current_size_);
1396
1397 // Save the values of the removed elements if requested.
1398 if (elements != NULL) {
1399 for (int i = 0; i < num; ++i) elements[i] = this->Get(i + start);
1400 }
1401
1402 // Slide remaining elements down to fill the gap.
1403 if (num > 0) {
1404 for (int i = start + num; i < this->current_size_; ++i)
1405 this->Set(i - num, this->Get(i));
1406 this->Truncate(this->current_size_ - num);
1407 }
1408}
1409
1410template <typename Element>
1411inline void RepeatedField<Element>::Clear() {
1412 current_size_ = 0;
1413}
1414
1415template <typename Element>
1416inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) {
1417 GOOGLE_DCHECK_NE(&other, this);
1418 if (other.current_size_ != 0) {
1419 int existing_size = size();
1420 Reserve(existing_size + other.size());
1421 AddNAlreadyReserved(other.size());
1422 CopyArray(Mutable(existing_size), &other.Get(0), other.size());
1423 }
1424}
1425
1426template <typename Element>
1427inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) {
1428 if (&other == this) return;
1429 Clear();
1430 MergeFrom(other);
1431}
1432
1433template <typename Element>
1434inline typename RepeatedField<Element>::iterator RepeatedField<Element>::erase(
1435 const_iterator position) {
1436 return erase(position, position + 1);
1437}
1438
1439template <typename Element>
1440inline typename RepeatedField<Element>::iterator RepeatedField<Element>::erase(
1441 const_iterator first, const_iterator last) {
1442 size_type first_offset = first - cbegin();
1443 if (first != last) {
1444 Truncate(std::copy(last, cend(), begin() + first_offset) - cbegin());
1445 }
1446 return begin() + first_offset;
1447}
1448
1449template <typename Element>
1450inline Element* RepeatedField<Element>::mutable_data() {
1451 return unsafe_elements();
1452}
1453
1454template <typename Element>
1455inline const Element* RepeatedField<Element>::data() const {
1456 return unsafe_elements();
1457}
1458
1459template <typename Element>
1460inline void RepeatedField<Element>::InternalSwap(RepeatedField* other) {
1461 GOOGLE_DCHECK(this != other);
1462 GOOGLE_DCHECK(GetArena() == other->GetArena());
1463
1464 // Swap all fields at once.
1465 static_assert(std::is_standard_layout<RepeatedField<Element>>::value,
1466 "offsetof() requires standard layout before c++17");
1467 internal::memswap<offsetof(RepeatedField, arena_or_elements_) +
1468 sizeof(this->arena_or_elements_) -
1469 offsetof(RepeatedField, current_size_)>(
1470 reinterpret_cast<char*>(this) + offsetof(RepeatedField, current_size_),
1471 reinterpret_cast<char*>(other) + offsetof(RepeatedField, current_size_));
1472}
1473
1474template <typename Element>
1475void RepeatedField<Element>::Swap(RepeatedField* other) {
1476 if (this == other) return;
1477 if (GetArena() == other->GetArena()) {
1478 InternalSwap(other);
1479 } else {
1480 RepeatedField<Element> temp(other->GetArena());
1481 temp.MergeFrom(*this);
1482 CopyFrom(*other);
1483 other->UnsafeArenaSwap(&temp);
1484 }
1485}
1486
1487template <typename Element>
1488void RepeatedField<Element>::UnsafeArenaSwap(RepeatedField* other) {
1489 if (this == other) return;
1490 InternalSwap(other);
1491}
1492
1493template <typename Element>
1494void RepeatedField<Element>::SwapElements(int index1, int index2) {
1495 using std::swap; // enable ADL with fallback
1496 swap(elements()[index1], elements()[index2]);
1497}
1498
1499template <typename Element>
1500inline typename RepeatedField<Element>::iterator
1501RepeatedField<Element>::begin() {
1502 return unsafe_elements();
1503}
1504template <typename Element>
1505inline typename RepeatedField<Element>::const_iterator
1506RepeatedField<Element>::begin() const {
1507 return unsafe_elements();
1508}
1509template <typename Element>
1510inline typename RepeatedField<Element>::const_iterator
1511RepeatedField<Element>::cbegin() const {
1512 return unsafe_elements();
1513}
1514template <typename Element>
1515inline typename RepeatedField<Element>::iterator RepeatedField<Element>::end() {
1516 return unsafe_elements() + current_size_;
1517}
1518template <typename Element>
1519inline typename RepeatedField<Element>::const_iterator
1520RepeatedField<Element>::end() const {
1521 return unsafe_elements() + current_size_;
1522}
1523template <typename Element>
1524inline typename RepeatedField<Element>::const_iterator
1525RepeatedField<Element>::cend() const {
1526 return unsafe_elements() + current_size_;
1527}
1528
1529template <typename Element>
1530inline size_t RepeatedField<Element>::SpaceUsedExcludingSelfLong() const {
1531 return total_size_ > 0 ? (total_size_ * sizeof(Element) + kRepHeaderSize) : 0;
1532}
1533
1534namespace internal {
1535// Returns the new size for a reserved field based on its 'total_size' and the
1536// requested 'new_size'. The result is clamped to the closed interval:
1537// [internal::kMinRepeatedFieldAllocationSize,
1538// std::numeric_limits<int>::max()]
1539// Requires:
1540// new_size > total_size &&
1541// (total_size == 0 ||
1542// total_size >= kRepeatedFieldLowerClampLimit)
1543inline int CalculateReserveSize(int total_size, int new_size) {
1544 if (new_size < kRepeatedFieldLowerClampLimit) {
1545 // Clamp to smallest allowed size.
1546 return kRepeatedFieldLowerClampLimit;
1547 }
1548 if (total_size < kRepeatedFieldUpperClampLimit) {
1549 return std::max(total_size * 2, new_size);
1550 } else {
1551 // Clamp to largest allowed size.
1552 GOOGLE_DCHECK_GT(new_size, kRepeatedFieldUpperClampLimit);
1553 return std::numeric_limits<int>::max();
1554 }
1555}
1556} // namespace internal
1557
1558// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant
1559// amount of code bloat.
1560template <typename Element>
1561void RepeatedField<Element>::Reserve(int new_size) {
1562 if (total_size_ >= new_size) return;
1563 Rep* old_rep = total_size_ > 0 ? rep() : NULL;
1564 Rep* new_rep;
1565 Arena* arena = GetArena();
1566 new_size = internal::CalculateReserveSize(total_size_, new_size);
1567 GOOGLE_DCHECK_LE(
1568 static_cast<size_t>(new_size),
1569 (std::numeric_limits<size_t>::max() - kRepHeaderSize) / sizeof(Element))
1570 << "Requested size is too large to fit into size_t.";
1571 size_t bytes =
1572 kRepHeaderSize + sizeof(Element) * static_cast<size_t>(new_size);
1573 if (arena == NULL) {
1574 new_rep = static_cast<Rep*>(::operator new(bytes));
1575 } else {
1576 new_rep = reinterpret_cast<Rep*>(Arena::CreateArray<char>(arena, bytes));
1577 }
1578 new_rep->arena = arena;
1579 int old_total_size = total_size_;
1580 // Already known: new_size >= internal::kMinRepeatedFieldAllocationSize
1581 // Maintain invariant:
1582 // total_size_ == 0 ||
1583 // total_size_ >= internal::kMinRepeatedFieldAllocationSize
1584 total_size_ = new_size;
1585 arena_or_elements_ = new_rep->elements;
1586 // Invoke placement-new on newly allocated elements. We shouldn't have to do
1587 // this, since Element is supposed to be POD, but a previous version of this
1588 // code allocated storage with "new Element[size]" and some code uses
1589 // RepeatedField with non-POD types, relying on constructor invocation. If
1590 // Element has a trivial constructor (e.g., int32), gcc (tested with -O2)
1591 // completely removes this loop because the loop body is empty, so this has no
1592 // effect unless its side-effects are required for correctness.
1593 // Note that we do this before MoveArray() below because Element's copy
1594 // assignment implementation will want an initialized instance first.
1595 Element* e = &elements()[0];
1596 Element* limit = e + total_size_;
1597 for (; e < limit; e++) {
1598 new (e) Element;
1599 }
1600 if (current_size_ > 0) {
1601 MoveArray(&elements()[0], old_rep->elements, current_size_);
1602 }
1603
1604 // Likewise, we need to invoke destructors on the old array.
1605 InternalDeallocate(old_rep, old_total_size);
1606
1607}
1608
1609template <typename Element>
1610inline void RepeatedField<Element>::Truncate(int new_size) {
1611 GOOGLE_DCHECK_LE(new_size, current_size_);
1612 if (current_size_ > 0) {
1613 current_size_ = new_size;
1614 }
1615}
1616
1617template <typename Element>
1618inline void RepeatedField<Element>::MoveArray(Element* to, Element* from,
1619 int array_size) {
1620 CopyArray(to, from, array_size);
1621}
1622
1623template <typename Element>
1624inline void RepeatedField<Element>::CopyArray(Element* to, const Element* from,
1625 int array_size) {
1626 internal::ElementCopier<Element>()(to, from, array_size);
1627}
1628
1629namespace internal {
1630
1631template <typename Element, bool HasTrivialCopy>
1632void ElementCopier<Element, HasTrivialCopy>::operator()(Element* to,
1633 const Element* from,
1634 int array_size) {
1635 std::copy(from, from + array_size, to);
1636}
1637
1638template <typename Element>
1639struct ElementCopier<Element, true> {
1640 void operator()(Element* to, const Element* from, int array_size) {
1641 memcpy(to, from, static_cast<size_t>(array_size) * sizeof(Element));
1642 }
1643};
1644
1645} // namespace internal
1646
1647
1648// -------------------------------------------------------------------
1649
1650namespace internal {
1651
1652inline RepeatedPtrFieldBase::RepeatedPtrFieldBase()
1653 : arena_(NULL), current_size_(0), total_size_(0), rep_(NULL) {}
1654
1655inline RepeatedPtrFieldBase::RepeatedPtrFieldBase(Arena* arena)
1656 : arena_(arena), current_size_(0), total_size_(0), rep_(NULL) {}
1657
1658template <typename TypeHandler>
1659void RepeatedPtrFieldBase::Destroy() {
1660 if (rep_ != NULL && arena_ == NULL) {
1661 int n = rep_->allocated_size;
1662 void* const* elements = rep_->elements;
1663 for (int i = 0; i < n; i++) {
1664 TypeHandler::Delete(cast<TypeHandler>(elements[i]), NULL);
1665 }
1666#if defined(__GXX_DELETE_WITH_SIZE__) || defined(__cpp_sized_deallocation)
1667 const size_t size = total_size_ * sizeof(elements[0]) + kRepHeaderSize;
1668 ::operator delete(static_cast<void*>(rep_), size);
1669#else
1670 ::operator delete(static_cast<void*>(rep_));
1671#endif
1672 }
1673 rep_ = NULL;
1674}
1675
1676template <typename TypeHandler>
1677inline void RepeatedPtrFieldBase::Swap(RepeatedPtrFieldBase* other) {
1678 if (other->GetArena() == GetArena()) {
1679 InternalSwap(other);
1680 } else {
1681 SwapFallback<TypeHandler>(other);
1682 }
1683}
1684
1685template <typename TypeHandler>
1686void RepeatedPtrFieldBase::SwapFallback(RepeatedPtrFieldBase* other) {
1687 GOOGLE_DCHECK(other->GetArena() != GetArena());
1688
1689 // Copy semantics in this case. We try to improve efficiency by placing the
1690 // temporary on |other|'s arena so that messages are copied twice rather than
1691 // three times.
1692 RepeatedPtrFieldBase temp(other->GetArena());
1693 temp.MergeFrom<TypeHandler>(*this);
1694 this->Clear<TypeHandler>();
1695 this->MergeFrom<TypeHandler>(*other);
1696 other->InternalSwap(&temp);
1697 temp.Destroy<TypeHandler>(); // Frees rep_ if `other` had no arena.
1698}
1699
1700inline bool RepeatedPtrFieldBase::empty() const { return current_size_ == 0; }
1701
1702inline int RepeatedPtrFieldBase::size() const { return current_size_; }
1703
1704template <typename TypeHandler>
1705inline const typename TypeHandler::Type& RepeatedPtrFieldBase::Get(
1706 int index) const {
1707 GOOGLE_DCHECK_GE(index, 0);
1708 GOOGLE_DCHECK_LT(index, current_size_);
1709 return *cast<TypeHandler>(rep_->elements[index]);
1710}
1711
1712template <typename TypeHandler>
1713inline const typename TypeHandler::Type& RepeatedPtrFieldBase::at(
1714 int index) const {
1715 GOOGLE_CHECK_GE(index, 0);
1716 GOOGLE_CHECK_LT(index, current_size_);
1717 return *cast<TypeHandler>(rep_->elements[index]);
1718}
1719
1720template <typename TypeHandler>
1721inline typename TypeHandler::Type& RepeatedPtrFieldBase::at(int index) {
1722 GOOGLE_CHECK_GE(index, 0);
1723 GOOGLE_CHECK_LT(index, current_size_);
1724 return *cast<TypeHandler>(rep_->elements[index]);
1725}
1726
1727template <typename TypeHandler>
1728inline typename TypeHandler::Type* RepeatedPtrFieldBase::Mutable(int index) {
1729 GOOGLE_DCHECK_GE(index, 0);
1730 GOOGLE_DCHECK_LT(index, current_size_);
1731 return cast<TypeHandler>(rep_->elements[index]);
1732}
1733
1734template <typename TypeHandler>
1735inline void RepeatedPtrFieldBase::Delete(int index) {
1736 GOOGLE_DCHECK_GE(index, 0);
1737 GOOGLE_DCHECK_LT(index, current_size_);
1738 TypeHandler::Delete(cast<TypeHandler>(rep_->elements[index]), arena_);
1739}
1740
1741template <typename TypeHandler>
1742inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add(
1743 typename TypeHandler::Type* prototype) {
1744 if (rep_ != NULL && current_size_ < rep_->allocated_size) {
1745 return cast<TypeHandler>(rep_->elements[current_size_++]);
1746 }
1747 if (!rep_ || rep_->allocated_size == total_size_) {
1748 Reserve(total_size_ + 1);
1749 }
1750 ++rep_->allocated_size;
1751 typename TypeHandler::Type* result =
1752 TypeHandler::NewFromPrototype(prototype, arena_);
1753 rep_->elements[current_size_++] = result;
1754 return result;
1755}
1756
1757template <typename TypeHandler,
1758 typename std::enable_if<TypeHandler::Movable::value>::type*>
1759inline void RepeatedPtrFieldBase::Add(typename TypeHandler::Type&& value) {
1760 if (rep_ != NULL && current_size_ < rep_->allocated_size) {
1761 *cast<TypeHandler>(rep_->elements[current_size_++]) = std::move(value);
1762 return;
1763 }
1764 if (!rep_ || rep_->allocated_size == total_size_) {
1765 Reserve(total_size_ + 1);
1766 }
1767 ++rep_->allocated_size;
1768 typename TypeHandler::Type* result =
1769 TypeHandler::New(arena_, std::move(value));
1770 rep_->elements[current_size_++] = result;
1771}
1772
1773template <typename TypeHandler>
1774inline void RepeatedPtrFieldBase::RemoveLast() {
1775 GOOGLE_DCHECK_GT(current_size_, 0);
1776 TypeHandler::Clear(cast<TypeHandler>(rep_->elements[--current_size_]));
1777}
1778
1779template <typename TypeHandler>
1780void RepeatedPtrFieldBase::Clear() {
1781 const int n = current_size_;
1782 GOOGLE_DCHECK_GE(n, 0);
1783 if (n > 0) {
1784 void* const* elements = rep_->elements;
1785 int i = 0;
1786 do {
1787 TypeHandler::Clear(cast<TypeHandler>(elements[i++]));
1788 } while (i < n);
1789 current_size_ = 0;
1790 }
1791}
1792
1793// To avoid unnecessary code duplication and reduce binary size, we use a
1794// layered approach to implementing MergeFrom(). The toplevel method is
1795// templated, so we get a small thunk per concrete message type in the binary.
1796// This calls a shared implementation with most of the logic, passing a function
1797// pointer to another type-specific piece of code that calls the object-allocate
1798// and merge handlers.
1799template <typename TypeHandler>
1800inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) {
1801 GOOGLE_DCHECK_NE(&other, this);
1802 if (other.current_size_ == 0) return;
1803 MergeFromInternal(other,
1804 &RepeatedPtrFieldBase::MergeFromInnerLoop<TypeHandler>);
1805}
1806
1807inline void RepeatedPtrFieldBase::MergeFromInternal(
1808 const RepeatedPtrFieldBase& other,
1809 void (RepeatedPtrFieldBase::*inner_loop)(void**, void**, int, int)) {
1810 // Note: wrapper has already guaranteed that other.rep_ != NULL here.
1811 int other_size = other.current_size_;
1812 void** other_elements = other.rep_->elements;
1813 void** new_elements = InternalExtend(other_size);
1814 int allocated_elems = rep_->allocated_size - current_size_;
1815 (this->*inner_loop)(new_elements, other_elements, other_size,
1816 allocated_elems);
1817 current_size_ += other_size;
1818 if (rep_->allocated_size < current_size_) {
1819 rep_->allocated_size = current_size_;
1820 }
1821}
1822
1823// Merges other_elems to our_elems.
1824template <typename TypeHandler>
1825void RepeatedPtrFieldBase::MergeFromInnerLoop(void** our_elems,
1826 void** other_elems, int length,
1827 int already_allocated) {
1828 // Split into two loops, over ranges [0, allocated) and [allocated, length),
1829 // to avoid a branch within the loop.
1830 for (int i = 0; i < already_allocated && i < length; i++) {
1831 // Already allocated: use existing element.
1832 typename TypeHandler::Type* other_elem =
1833 reinterpret_cast<typename TypeHandler::Type*>(other_elems[i]);
1834 typename TypeHandler::Type* new_elem =
1835 reinterpret_cast<typename TypeHandler::Type*>(our_elems[i]);
1836 TypeHandler::Merge(*other_elem, new_elem);
1837 }
1838 Arena* arena = GetArena();
1839 for (int i = already_allocated; i < length; i++) {
1840 // Not allocated: alloc a new element first, then merge it.
1841 typename TypeHandler::Type* other_elem =
1842 reinterpret_cast<typename TypeHandler::Type*>(other_elems[i]);
1843 typename TypeHandler::Type* new_elem =
1844 TypeHandler::NewFromPrototype(other_elem, arena);
1845 TypeHandler::Merge(*other_elem, new_elem);
1846 our_elems[i] = new_elem;
1847 }
1848}
1849
1850template <typename TypeHandler>
1851inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) {
1852 if (&other == this) return;
1853 RepeatedPtrFieldBase::Clear<TypeHandler>();
1854 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
1855}
1856
1857inline int RepeatedPtrFieldBase::Capacity() const { return total_size_; }
1858
1859inline void* const* RepeatedPtrFieldBase::raw_data() const {
1860 return rep_ ? rep_->elements : NULL;
1861}
1862
1863inline void** RepeatedPtrFieldBase::raw_mutable_data() const {
1864 return rep_ ? const_cast<void**>(rep_->elements) : NULL;
1865}
1866
1867template <typename TypeHandler>
1868inline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() {
1869 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this
1870 // method entirely.
1871 return reinterpret_cast<typename TypeHandler::Type**>(raw_mutable_data());
1872}
1873
1874template <typename TypeHandler>
1875inline const typename TypeHandler::Type* const* RepeatedPtrFieldBase::data()
1876 const {
1877 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this
1878 // method entirely.
1879 return reinterpret_cast<const typename TypeHandler::Type* const*>(raw_data());
1880}
1881
1882inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) {
1883 using std::swap; // enable ADL with fallback
1884 swap(rep_->elements[index1], rep_->elements[index2]);
1885}
1886
1887template <typename TypeHandler>
1888inline size_t RepeatedPtrFieldBase::SpaceUsedExcludingSelfLong() const {
1889 size_t allocated_bytes = static_cast<size_t>(total_size_) * sizeof(void*);
1890 if (rep_ != NULL) {
1891 for (int i = 0; i < rep_->allocated_size; ++i) {
1892 allocated_bytes +=
1893 TypeHandler::SpaceUsedLong(*cast<TypeHandler>(rep_->elements[i]));
1894 }
1895 allocated_bytes += kRepHeaderSize;
1896 }
1897 return allocated_bytes;
1898}
1899
1900template <typename TypeHandler>
1901inline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() {
1902 if (rep_ != NULL && current_size_ < rep_->allocated_size) {
1903 return cast<TypeHandler>(rep_->elements[current_size_++]);
1904 } else {
1905 return NULL;
1906 }
1907}
1908
1909// AddAllocated version that implements arena-safe copying behavior.
1910template <typename TypeHandler>
1911void RepeatedPtrFieldBase::AddAllocatedInternal(
1912 typename TypeHandler::Type* value, std::true_type) {
1913 Arena* element_arena =
1914 reinterpret_cast<Arena*>(TypeHandler::GetMaybeArenaPointer(value));
1915 Arena* arena = GetArena();
1916 if (arena == element_arena && rep_ && rep_->allocated_size < total_size_) {
1917 // Fast path: underlying arena representation (tagged pointer) is equal to
1918 // our arena pointer, and we can add to array without resizing it (at least
1919 // one slot that is not allocated).
1920 void** elems = rep_->elements;
1921 if (current_size_ < rep_->allocated_size) {
1922 // Make space at [current] by moving first allocated element to end of
1923 // allocated list.
1924 elems[rep_->allocated_size] = elems[current_size_];
1925 }
1926 elems[current_size_] = value;
1927 current_size_ = current_size_ + 1;
1928 rep_->allocated_size = rep_->allocated_size + 1;
1929 } else {
1930 AddAllocatedSlowWithCopy<TypeHandler>(value, TypeHandler::GetArena(value),
1931 arena);
1932 }
1933}
1934
1935// Slowpath handles all cases, copying if necessary.
1936template <typename TypeHandler>
1937void RepeatedPtrFieldBase::AddAllocatedSlowWithCopy(
1938 // Pass value_arena and my_arena to avoid duplicate virtual call (value) or
1939 // load (mine).
1940 typename TypeHandler::Type* value, Arena* value_arena, Arena* my_arena) {
1941 // Ensure that either the value is in the same arena, or if not, we do the
1942 // appropriate thing: Own() it (if it's on heap and we're in an arena) or copy
1943 // it to our arena/heap (otherwise).
1944 if (my_arena != NULL && value_arena == NULL) {
1945 my_arena->Own(value);
1946 } else if (my_arena != value_arena) {
1947 typename TypeHandler::Type* new_value =
1948 TypeHandler::NewFromPrototype(value, my_arena);
1949 TypeHandler::Merge(*value, new_value);
1950 TypeHandler::Delete(value, value_arena);
1951 value = new_value;
1952 }
1953
1954 UnsafeArenaAddAllocated<TypeHandler>(value);
1955}
1956
1957// AddAllocated version that does not implement arena-safe copying behavior.
1958template <typename TypeHandler>
1959void RepeatedPtrFieldBase::AddAllocatedInternal(
1960 typename TypeHandler::Type* value, std::false_type) {
1961 if (rep_ && rep_->allocated_size < total_size_) {
1962 // Fast path: underlying arena representation (tagged pointer) is equal to
1963 // our arena pointer, and we can add to array without resizing it (at least
1964 // one slot that is not allocated).
1965 void** elems = rep_->elements;
1966 if (current_size_ < rep_->allocated_size) {
1967 // Make space at [current] by moving first allocated element to end of
1968 // allocated list.
1969 elems[rep_->allocated_size] = elems[current_size_];
1970 }
1971 elems[current_size_] = value;
1972 current_size_ = current_size_ + 1;
1973 ++rep_->allocated_size;
1974 } else {
1975 UnsafeArenaAddAllocated<TypeHandler>(value);
1976 }
1977}
1978
1979template <typename TypeHandler>
1980void RepeatedPtrFieldBase::UnsafeArenaAddAllocated(
1981 typename TypeHandler::Type* value) {
1982 // Make room for the new pointer.
1983 if (!rep_ || current_size_ == total_size_) {
1984 // The array is completely full with no cleared objects, so grow it.
1985 Reserve(total_size_ + 1);
1986 ++rep_->allocated_size;
1987 } else if (rep_->allocated_size == total_size_) {
1988 // There is no more space in the pointer array because it contains some
1989 // cleared objects awaiting reuse. We don't want to grow the array in this
1990 // case because otherwise a loop calling AddAllocated() followed by Clear()
1991 // would leak memory.
1992 TypeHandler::Delete(cast<TypeHandler>(rep_->elements[current_size_]),
1993 arena_);
1994 } else if (current_size_ < rep_->allocated_size) {
1995 // We have some cleared objects. We don't care about their order, so we
1996 // can just move the first one to the end to make space.
1997 rep_->elements[rep_->allocated_size] = rep_->elements[current_size_];
1998 ++rep_->allocated_size;
1999 } else {
2000 // There are no cleared objects.
2001 ++rep_->allocated_size;
2002 }
2003
2004 rep_->elements[current_size_++] = value;
2005}
2006
2007// ReleaseLast() for types that implement merge/copy behavior.
2008template <typename TypeHandler>
2009inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLastInternal(
2010 std::true_type) {
2011 // First, release an element.
2012 typename TypeHandler::Type* result = UnsafeArenaReleaseLast<TypeHandler>();
2013 // Now perform a copy if we're on an arena.
2014 Arena* arena = GetArena();
2015 if (arena == NULL) {
2016 return result;
2017 } else {
2018 typename TypeHandler::Type* new_result =
2019 TypeHandler::NewFromPrototype(result, NULL);
2020 TypeHandler::Merge(*result, new_result);
2021 return new_result;
2022 }
2023}
2024
2025// ReleaseLast() for types that *do not* implement merge/copy behavior -- this
2026// is the same as UnsafeArenaReleaseLast(). Note that we GOOGLE_DCHECK-fail if we're on
2027// an arena, since the user really should implement the copy operation in this
2028// case.
2029template <typename TypeHandler>
2030inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLastInternal(
2031 std::false_type) {
2032 GOOGLE_DCHECK(GetArena() == NULL)
2033 << "ReleaseLast() called on a RepeatedPtrField that is on an arena, "
2034 << "with a type that does not implement MergeFrom. This is unsafe; "
2035 << "please implement MergeFrom for your type.";
2036 return UnsafeArenaReleaseLast<TypeHandler>();
2037}
2038
2039template <typename TypeHandler>
2040inline typename TypeHandler::Type*
2041RepeatedPtrFieldBase::UnsafeArenaReleaseLast() {
2042 GOOGLE_DCHECK_GT(current_size_, 0);
2043 typename TypeHandler::Type* result =
2044 cast<TypeHandler>(rep_->elements[--current_size_]);
2045 --rep_->allocated_size;
2046 if (current_size_ < rep_->allocated_size) {
2047 // There are cleared elements on the end; replace the removed element
2048 // with the last allocated element.
2049 rep_->elements[current_size_] = rep_->elements[rep_->allocated_size];
2050 }
2051 return result;
2052}
2053
2054inline int RepeatedPtrFieldBase::ClearedCount() const {
2055 return rep_ ? (rep_->allocated_size - current_size_) : 0;
2056}
2057
2058template <typename TypeHandler>
2059inline void RepeatedPtrFieldBase::AddCleared(
2060 typename TypeHandler::Type* value) {
2061 GOOGLE_DCHECK(GetArena() == NULL)
2062 << "AddCleared() can only be used on a RepeatedPtrField not on an arena.";
2063 GOOGLE_DCHECK(TypeHandler::GetArena(value) == NULL)
2064 << "AddCleared() can only accept values not on an arena.";
2065 if (!rep_ || rep_->allocated_size == total_size_) {
2066 Reserve(total_size_ + 1);
2067 }
2068 rep_->elements[rep_->allocated_size++] = value;
2069}
2070
2071template <typename TypeHandler>
2072inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() {
2073 GOOGLE_DCHECK(GetArena() == NULL)
2074 << "ReleaseCleared() can only be used on a RepeatedPtrField not on "
2075 << "an arena.";
2076 GOOGLE_DCHECK(GetArena() == NULL);
2077 GOOGLE_DCHECK(rep_ != NULL);
2078 GOOGLE_DCHECK_GT(rep_->allocated_size, current_size_);
2079 return cast<TypeHandler>(rep_->elements[--rep_->allocated_size]);
2080}
2081
2082} // namespace internal
2083
2084// -------------------------------------------------------------------
2085
2086template <typename Element>
2087class RepeatedPtrField<Element>::TypeHandler
2088 : public internal::GenericTypeHandler<Element> {};
2089
2090template <>
2091class RepeatedPtrField<std::string>::TypeHandler
2092 : public internal::StringTypeHandler {};
2093
2094template <typename Element>
2095inline RepeatedPtrField<Element>::RepeatedPtrField() : RepeatedPtrFieldBase() {}
2096
2097template <typename Element>
2098inline RepeatedPtrField<Element>::RepeatedPtrField(Arena* arena)
2099 : RepeatedPtrFieldBase(arena) {}
2100
2101template <typename Element>
2102inline RepeatedPtrField<Element>::RepeatedPtrField(
2103 const RepeatedPtrField& other)
2104 : RepeatedPtrFieldBase() {
2105 MergeFrom(other);
2106}
2107
2108template <typename Element>
2109template <typename Iter>
2110inline RepeatedPtrField<Element>::RepeatedPtrField(Iter begin,
2111 const Iter& end) {
2112 int reserve = internal::CalculateReserve(begin, end);
2113 if (reserve != -1) {
2114 Reserve(reserve);
2115 }
2116 for (; begin != end; ++begin) {
2117 *Add() = *begin;
2118 }
2119}
2120
2121template <typename Element>
2122RepeatedPtrField<Element>::~RepeatedPtrField() {
2123 Destroy<TypeHandler>();
2124}
2125
2126template <typename Element>
2127inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=(
2128 const RepeatedPtrField& other) {
2129 if (this != &other) CopyFrom(other);
2130 return *this;
2131}
2132
2133template <typename Element>
2134inline RepeatedPtrField<Element>::RepeatedPtrField(
2135 RepeatedPtrField&& other) noexcept
2136 : RepeatedPtrField() {
2137 // We don't just call Swap(&other) here because it would perform 3 copies if
2138 // other is on an arena. This field can't be on an arena because arena
2139 // construction always uses the Arena* accepting constructor.
2140 if (other.GetArena()) {
2141 CopyFrom(other);
2142 } else {
2143 InternalSwap(&other);
2144 }
2145}
2146
2147template <typename Element>
2148inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=(
2149 RepeatedPtrField&& other) noexcept {
2150 // We don't just call Swap(&other) here because it would perform 3 copies if
2151 // the two fields are on different arenas.
2152 if (this != &other) {
2153 if (this->GetArena() != other.GetArena()) {
2154 CopyFrom(other);
2155 } else {
2156 InternalSwap(&other);
2157 }
2158 }
2159 return *this;
2160}
2161
2162template <typename Element>
2163inline bool RepeatedPtrField<Element>::empty() const {
2164 return RepeatedPtrFieldBase::empty();
2165}
2166
2167template <typename Element>
2168inline int RepeatedPtrField<Element>::size() const {
2169 return RepeatedPtrFieldBase::size();
2170}
2171
2172template <typename Element>
2173inline const Element& RepeatedPtrField<Element>::Get(int index) const {
2174 return RepeatedPtrFieldBase::Get<TypeHandler>(index);
2175}
2176
2177template <typename Element>
2178inline const Element& RepeatedPtrField<Element>::at(int index) const {
2179 return RepeatedPtrFieldBase::at<TypeHandler>(index);
2180}
2181
2182template <typename Element>
2183inline Element& RepeatedPtrField<Element>::at(int index) {
2184 return RepeatedPtrFieldBase::at<TypeHandler>(index);
2185}
2186
2187
2188template <typename Element>
2189inline Element* RepeatedPtrField<Element>::Mutable(int index) {
2190 return RepeatedPtrFieldBase::Mutable<TypeHandler>(index);
2191}
2192
2193template <typename Element>
2194inline Element* RepeatedPtrField<Element>::Add() {
2195 return RepeatedPtrFieldBase::Add<TypeHandler>();
2196}
2197
2198template <typename Element>
2199inline void RepeatedPtrField<Element>::Add(Element&& value) {
2200 RepeatedPtrFieldBase::Add<TypeHandler>(std::move(value));
2201}
2202
2203template <typename Element>
2204inline void RepeatedPtrField<Element>::RemoveLast() {
2205 RepeatedPtrFieldBase::RemoveLast<TypeHandler>();
2206}
2207
2208template <typename Element>
2209inline void RepeatedPtrField<Element>::DeleteSubrange(int start, int num) {
2210 GOOGLE_DCHECK_GE(start, 0);
2211 GOOGLE_DCHECK_GE(num, 0);
2212 GOOGLE_DCHECK_LE(start + num, size());
2213 for (int i = 0; i < num; ++i) {
2214 RepeatedPtrFieldBase::Delete<TypeHandler>(start + i);
2215 }
2216 ExtractSubrange(start, num, NULL);
2217}
2218
2219template <typename Element>
2220inline void RepeatedPtrField<Element>::ExtractSubrange(int start, int num,
2221 Element** elements) {
2222 typename internal::TypeImplementsMergeBehavior<
2223 typename TypeHandler::Type>::type t;
2224 ExtractSubrangeInternal(start, num, elements, t);
2225}
2226
2227// ExtractSubrange() implementation for types that implement merge/copy
2228// behavior.
2229template <typename Element>
2230inline void RepeatedPtrField<Element>::ExtractSubrangeInternal(
2231 int start, int num, Element** elements, std::true_type) {
2232 GOOGLE_DCHECK_GE(start, 0);
2233 GOOGLE_DCHECK_GE(num, 0);
2234 GOOGLE_DCHECK_LE(start + num, size());
2235
2236 if (num > 0) {
2237 // Save the values of the removed elements if requested.
2238 if (elements != NULL) {
2239 if (GetArena() != NULL) {
2240 // If we're on an arena, we perform a copy for each element so that the
2241 // returned elements are heap-allocated.
2242 for (int i = 0; i < num; ++i) {
2243 Element* element =
2244 RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start);
2245 typename TypeHandler::Type* new_value =
2246 TypeHandler::NewFromPrototype(element, NULL);
2247 TypeHandler::Merge(*element, new_value);
2248 elements[i] = new_value;
2249 }
2250 } else {
2251 for (int i = 0; i < num; ++i) {
2252 elements[i] = RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start);
2253 }
2254 }
2255 }
2256 CloseGap(start, num);
2257 }
2258}
2259
2260// ExtractSubrange() implementation for types that do not implement merge/copy
2261// behavior.
2262template <typename Element>
2263inline void RepeatedPtrField<Element>::ExtractSubrangeInternal(
2264 int start, int num, Element** elements, std::false_type) {
2265 // This case is identical to UnsafeArenaExtractSubrange(). However, since
2266 // ExtractSubrange() must return heap-allocated objects by contract, and we
2267 // cannot fulfill this contract if we are an on arena, we must GOOGLE_DCHECK() that
2268 // we are not on an arena.
2269 GOOGLE_DCHECK(GetArena() == NULL)
2270 << "ExtractSubrange() when arena is non-NULL is only supported when "
2271 << "the Element type supplies a MergeFrom() operation to make copies.";
2272 UnsafeArenaExtractSubrange(start, num, elements);
2273}
2274
2275template <typename Element>
2276inline void RepeatedPtrField<Element>::UnsafeArenaExtractSubrange(
2277 int start, int num, Element** elements) {
2278 GOOGLE_DCHECK_GE(start, 0);
2279 GOOGLE_DCHECK_GE(num, 0);
2280 GOOGLE_DCHECK_LE(start + num, size());
2281
2282 if (num > 0) {
2283 // Save the values of the removed elements if requested.
2284 if (elements != NULL) {
2285 for (int i = 0; i < num; ++i) {
2286 elements[i] = RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start);
2287 }
2288 }
2289 CloseGap(start, num);
2290 }
2291}
2292
2293template <typename Element>
2294inline void RepeatedPtrField<Element>::Clear() {
2295 RepeatedPtrFieldBase::Clear<TypeHandler>();
2296}
2297
2298template <typename Element>
2299inline void RepeatedPtrField<Element>::MergeFrom(
2300 const RepeatedPtrField& other) {
2301 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
2302}
2303
2304template <typename Element>
2305inline void RepeatedPtrField<Element>::CopyFrom(const RepeatedPtrField& other) {
2306 RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other);
2307}
2308
2309template <typename Element>
2310inline typename RepeatedPtrField<Element>::iterator
2311RepeatedPtrField<Element>::erase(const_iterator position) {
2312 return erase(position, position + 1);
2313}
2314
2315template <typename Element>
2316inline typename RepeatedPtrField<Element>::iterator
2317RepeatedPtrField<Element>::erase(const_iterator first, const_iterator last) {
2318 size_type pos_offset = std::distance(cbegin(), first);
2319 size_type last_offset = std::distance(cbegin(), last);
2320 DeleteSubrange(pos_offset, last_offset - pos_offset);
2321 return begin() + pos_offset;
2322}
2323
2324template <typename Element>
2325inline Element** RepeatedPtrField<Element>::mutable_data() {
2326 return RepeatedPtrFieldBase::mutable_data<TypeHandler>();
2327}
2328
2329template <typename Element>
2330inline const Element* const* RepeatedPtrField<Element>::data() const {
2331 return RepeatedPtrFieldBase::data<TypeHandler>();
2332}
2333
2334template <typename Element>
2335inline void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) {
2336 if (this == other) return;
2337 RepeatedPtrFieldBase::Swap<TypeHandler>(other);
2338}
2339
2340template <typename Element>
2341inline void RepeatedPtrField<Element>::UnsafeArenaSwap(
2342 RepeatedPtrField* other) {
2343 if (this == other) return;
2344 RepeatedPtrFieldBase::InternalSwap(other);
2345}
2346
2347template <typename Element>
2348inline void RepeatedPtrField<Element>::SwapElements(int index1, int index2) {
2349 RepeatedPtrFieldBase::SwapElements(index1, index2);
2350}
2351
2352template <typename Element>
2353inline Arena* RepeatedPtrField<Element>::GetArena() const {
2354 return RepeatedPtrFieldBase::GetArena();
2355}
2356
2357template <typename Element>
2358inline size_t RepeatedPtrField<Element>::SpaceUsedExcludingSelfLong() const {
2359 return RepeatedPtrFieldBase::SpaceUsedExcludingSelfLong<TypeHandler>();
2360}
2361
2362template <typename Element>
2363inline void RepeatedPtrField<Element>::AddAllocated(Element* value) {
2364 RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value);
2365}
2366
2367template <typename Element>
2368inline void RepeatedPtrField<Element>::UnsafeArenaAddAllocated(Element* value) {
2369 RepeatedPtrFieldBase::UnsafeArenaAddAllocated<TypeHandler>(value);
2370}
2371
2372template <typename Element>
2373inline Element* RepeatedPtrField<Element>::ReleaseLast() {
2374 return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>();
2375}
2376
2377template <typename Element>
2378inline Element* RepeatedPtrField<Element>::UnsafeArenaReleaseLast() {
2379 return RepeatedPtrFieldBase::UnsafeArenaReleaseLast<TypeHandler>();
2380}
2381
2382template <typename Element>
2383inline int RepeatedPtrField<Element>::ClearedCount() const {
2384 return RepeatedPtrFieldBase::ClearedCount();
2385}
2386
2387template <typename Element>
2388inline void RepeatedPtrField<Element>::AddCleared(Element* value) {
2389 return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value);
2390}
2391
2392template <typename Element>
2393inline Element* RepeatedPtrField<Element>::ReleaseCleared() {
2394 return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>();
2395}
2396
2397template <typename Element>
2398inline void RepeatedPtrField<Element>::Reserve(int new_size) {
2399 return RepeatedPtrFieldBase::Reserve(new_size);
2400}
2401
2402template <typename Element>
2403inline int RepeatedPtrField<Element>::Capacity() const {
2404 return RepeatedPtrFieldBase::Capacity();
2405}
2406
2407// -------------------------------------------------------------------
2408
2409namespace internal {
2410
2411// STL-like iterator implementation for RepeatedPtrField. You should not
2412// refer to this class directly; use RepeatedPtrField<T>::iterator instead.
2413//
2414// The iterator for RepeatedPtrField<T>, RepeatedPtrIterator<T>, is
2415// very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors.h,
2416// but adds random-access operators and is modified to wrap a void** base
2417// iterator (since RepeatedPtrField stores its array as a void* array and
2418// casting void** to T** would violate C++ aliasing rules).
2419//
2420// This code based on net/proto/proto-array-internal.h by Jeffrey Yasskin
2421// ([email protected]).
2422template <typename Element>
2423class RepeatedPtrIterator {
2424 public:
2425 using iterator = RepeatedPtrIterator<Element>;
2426 using iterator_category = std::random_access_iterator_tag;
2427 using value_type = typename std::remove_const<Element>::type;
2428 using difference_type = std::ptrdiff_t;
2429 using pointer = Element*;
2430 using reference = Element&;
2431
2432 RepeatedPtrIterator() : it_(NULL) {}
2433 explicit RepeatedPtrIterator(void* const* it) : it_(it) {}
2434
2435 // Allow "upcasting" from RepeatedPtrIterator<T**> to
2436 // RepeatedPtrIterator<const T*const*>.
2437 template <typename OtherElement>
2438 RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other)
2439 : it_(other.it_) {
2440 // Force a compiler error if the other type is not convertible to ours.
2441 if (false) {
2442 implicit_cast<Element*>(static_cast<OtherElement*>(nullptr));
2443 }
2444 }
2445
2446 // dereferenceable
2447 reference operator*() const { return *reinterpret_cast<Element*>(*it_); }
2448 pointer operator->() const { return &(operator*()); }
2449
2450 // {inc,dec}rementable
2451 iterator& operator++() {
2452 ++it_;
2453 return *this;
2454 }
2455 iterator operator++(int) { return iterator(it_++); }
2456 iterator& operator--() {
2457 --it_;
2458 return *this;
2459 }
2460 iterator operator--(int) { return iterator(it_--); }
2461
2462 // equality_comparable
2463 bool operator==(const iterator& x) const { return it_ == x.it_; }
2464 bool operator!=(const iterator& x) const { return it_ != x.it_; }
2465
2466 // less_than_comparable
2467 bool operator<(const iterator& x) const { return it_ < x.it_; }
2468 bool operator<=(const iterator& x) const { return it_ <= x.it_; }
2469 bool operator>(const iterator& x) const { return it_ > x.it_; }
2470 bool operator>=(const iterator& x) const { return it_ >= x.it_; }
2471
2472 // addable, subtractable
2473 iterator& operator+=(difference_type d) {
2474 it_ += d;
2475 return *this;
2476 }
2477 friend iterator operator+(iterator it, const difference_type d) {
2478 it += d;
2479 return it;
2480 }
2481 friend iterator operator+(const difference_type d, iterator it) {
2482 it += d;
2483 return it;
2484 }
2485 iterator& operator-=(difference_type d) {
2486 it_ -= d;
2487 return *this;
2488 }
2489 friend iterator operator-(iterator it, difference_type d) {
2490 it -= d;
2491 return it;
2492 }
2493
2494 // indexable
2495 reference operator[](difference_type d) const { return *(*this + d); }
2496
2497 // random access iterator
2498 difference_type operator-(const iterator& x) const { return it_ - x.it_; }
2499
2500 private:
2501 template <typename OtherElement>
2502 friend class RepeatedPtrIterator;
2503
2504 // The internal iterator.
2505 void* const* it_;
2506};
2507
2508// Provide an iterator that operates on pointers to the underlying objects
2509// rather than the objects themselves as RepeatedPtrIterator does.
2510// Consider using this when working with stl algorithms that change
2511// the array.
2512// The VoidPtr template parameter holds the type-agnostic pointer value
2513// referenced by the iterator. It should either be "void *" for a mutable
2514// iterator, or "const void* const" for a constant iterator.
2515template <typename Element, typename VoidPtr>
2516class RepeatedPtrOverPtrsIterator {
2517 public:
2518 using iterator = RepeatedPtrOverPtrsIterator<Element, VoidPtr>;
2519 using iterator_category = std::random_access_iterator_tag;
2520 using value_type = typename std::remove_const<Element>::type;
2521 using difference_type = std::ptrdiff_t;
2522 using pointer = Element*;
2523 using reference = Element&;
2524
2525 RepeatedPtrOverPtrsIterator() : it_(NULL) {}
2526 explicit RepeatedPtrOverPtrsIterator(VoidPtr* it) : it_(it) {}
2527
2528 // dereferenceable
2529 reference operator*() const { return *reinterpret_cast<Element*>(it_); }
2530 pointer operator->() const { return &(operator*()); }
2531
2532 // {inc,dec}rementable
2533 iterator& operator++() {
2534 ++it_;
2535 return *this;
2536 }
2537 iterator operator++(int) { return iterator(it_++); }
2538 iterator& operator--() {
2539 --it_;
2540 return *this;
2541 }
2542 iterator operator--(int) { return iterator(it_--); }
2543
2544 // equality_comparable
2545 bool operator==(const iterator& x) const { return it_ == x.it_; }
2546 bool operator!=(const iterator& x) const { return it_ != x.it_; }
2547
2548 // less_than_comparable
2549 bool operator<(const iterator& x) const { return it_ < x.it_; }
2550 bool operator<=(const iterator& x) const { return it_ <= x.it_; }
2551 bool operator>(const iterator& x) const { return it_ > x.it_; }
2552 bool operator>=(const iterator& x) const { return it_ >= x.it_; }
2553
2554 // addable, subtractable
2555 iterator& operator+=(difference_type d) {
2556 it_ += d;
2557 return *this;
2558 }
2559 friend iterator operator+(iterator it, difference_type d) {
2560 it += d;
2561 return it;
2562 }
2563 friend iterator operator+(difference_type d, iterator it) {
2564 it += d;
2565 return it;
2566 }
2567 iterator& operator-=(difference_type d) {
2568 it_ -= d;
2569 return *this;
2570 }
2571 friend iterator operator-(iterator it, difference_type d) {
2572 it -= d;
2573 return it;
2574 }
2575
2576 // indexable
2577 reference operator[](difference_type d) const { return *(*this + d); }
2578
2579 // random access iterator
2580 difference_type operator-(const iterator& x) const { return it_ - x.it_; }
2581
2582 private:
2583 template <typename OtherElement>
2584 friend class RepeatedPtrIterator;
2585
2586 // The internal iterator.
2587 VoidPtr* it_;
2588};
2589
2590void RepeatedPtrFieldBase::InternalSwap(RepeatedPtrFieldBase* other) {
2591 GOOGLE_DCHECK(this != other);
2592 GOOGLE_DCHECK(GetArena() == other->GetArena());
2593
2594 // Swap all fields at once.
2595 static_assert(std::is_standard_layout<RepeatedPtrFieldBase>::value,
2596 "offsetof() requires standard layout before c++17");
2597 internal::memswap<offsetof(RepeatedPtrFieldBase, rep_) + sizeof(this->rep_) -
2598 offsetof(RepeatedPtrFieldBase, current_size_)>(
2599 reinterpret_cast<char*>(this) +
2600 offsetof(RepeatedPtrFieldBase, current_size_),
2601 reinterpret_cast<char*>(other) +
2602 offsetof(RepeatedPtrFieldBase, current_size_));
2603}
2604
2605} // namespace internal
2606
2607template <typename Element>
2608inline typename RepeatedPtrField<Element>::iterator
2609RepeatedPtrField<Element>::begin() {
2610 return iterator(raw_data());
2611}
2612template <typename Element>
2613inline typename RepeatedPtrField<Element>::const_iterator
2614RepeatedPtrField<Element>::begin() const {
2615 return iterator(raw_data());
2616}
2617template <typename Element>
2618inline typename RepeatedPtrField<Element>::const_iterator
2619RepeatedPtrField<Element>::cbegin() const {
2620 return begin();
2621}
2622template <typename Element>
2623inline typename RepeatedPtrField<Element>::iterator
2624RepeatedPtrField<Element>::end() {
2625 return iterator(raw_data() + size());
2626}
2627template <typename Element>
2628inline typename RepeatedPtrField<Element>::const_iterator
2629RepeatedPtrField<Element>::end() const {
2630 return iterator(raw_data() + size());
2631}
2632template <typename Element>
2633inline typename RepeatedPtrField<Element>::const_iterator
2634RepeatedPtrField<Element>::cend() const {
2635 return end();
2636}
2637
2638template <typename Element>
2639inline typename RepeatedPtrField<Element>::pointer_iterator
2640RepeatedPtrField<Element>::pointer_begin() {
2641 return pointer_iterator(raw_mutable_data());
2642}
2643template <typename Element>
2644inline typename RepeatedPtrField<Element>::const_pointer_iterator
2645RepeatedPtrField<Element>::pointer_begin() const {
2646 return const_pointer_iterator(const_cast<const void* const*>(raw_data()));
2647}
2648template <typename Element>
2649inline typename RepeatedPtrField<Element>::pointer_iterator
2650RepeatedPtrField<Element>::pointer_end() {
2651 return pointer_iterator(raw_mutable_data() + size());
2652}
2653template <typename Element>
2654inline typename RepeatedPtrField<Element>::const_pointer_iterator
2655RepeatedPtrField<Element>::pointer_end() const {
2656 return const_pointer_iterator(
2657 const_cast<const void* const*>(raw_data() + size()));
2658}
2659
2660// Iterators and helper functions that follow the spirit of the STL
2661// std::back_insert_iterator and std::back_inserter but are tailor-made
2662// for RepeatedField and RepeatedPtrField. Typical usage would be:
2663//
2664// std::copy(some_sequence.begin(), some_sequence.end(),
2665// RepeatedFieldBackInserter(proto.mutable_sequence()));
2666//
2667// Ported by johannes from util/gtl/proto-array-iterators.h
2668
2669namespace internal {
2670// A back inserter for RepeatedField objects.
2671template <typename T>
2672class RepeatedFieldBackInsertIterator
2673 : public std::iterator<std::output_iterator_tag, T> {
2674 public:
2675 explicit RepeatedFieldBackInsertIterator(
2676 RepeatedField<T>* const mutable_field)
2677 : field_(mutable_field) {}
2678 RepeatedFieldBackInsertIterator<T>& operator=(const T& value) {
2679 field_->Add(value);
2680 return *this;
2681 }
2682 RepeatedFieldBackInsertIterator<T>& operator*() { return *this; }
2683 RepeatedFieldBackInsertIterator<T>& operator++() { return *this; }
2684 RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) {
2685 return *this;
2686 }
2687
2688 private:
2689 RepeatedField<T>* field_;
2690};
2691
2692// A back inserter for RepeatedPtrField objects.
2693template <typename T>
2694class RepeatedPtrFieldBackInsertIterator
2695 : public std::iterator<std::output_iterator_tag, T> {
2696 public:
2697 RepeatedPtrFieldBackInsertIterator(RepeatedPtrField<T>* const mutable_field)
2698 : field_(mutable_field) {}
2699 RepeatedPtrFieldBackInsertIterator<T>& operator=(const T& value) {
2700 *field_->Add() = value;
2701 return *this;
2702 }
2703 RepeatedPtrFieldBackInsertIterator<T>& operator=(
2704 const T* const ptr_to_value) {
2705 *field_->Add() = *ptr_to_value;
2706 return *this;
2707 }
2708 RepeatedPtrFieldBackInsertIterator<T>& operator=(T&& value) {
2709 *field_->Add() = std::move(value);
2710 return *this;
2711 }
2712 RepeatedPtrFieldBackInsertIterator<T>& operator*() { return *this; }
2713 RepeatedPtrFieldBackInsertIterator<T>& operator++() { return *this; }
2714 RepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) {
2715 return *this;
2716 }
2717
2718 private:
2719 RepeatedPtrField<T>* field_;
2720};
2721
2722// A back inserter for RepeatedPtrFields that inserts by transferring ownership
2723// of a pointer.
2724template <typename T>
2725class AllocatedRepeatedPtrFieldBackInsertIterator
2726 : public std::iterator<std::output_iterator_tag, T> {
2727 public:
2728 explicit AllocatedRepeatedPtrFieldBackInsertIterator(
2729 RepeatedPtrField<T>* const mutable_field)
2730 : field_(mutable_field) {}
2731 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator=(
2732 T* const ptr_to_value) {
2733 field_->AddAllocated(ptr_to_value);
2734 return *this;
2735 }
2736 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator*() { return *this; }
2737 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++() { return *this; }
2738 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) {
2739 return *this;
2740 }
2741
2742 private:
2743 RepeatedPtrField<T>* field_;
2744};
2745
2746// Almost identical to AllocatedRepeatedPtrFieldBackInsertIterator. This one
2747// uses the UnsafeArenaAddAllocated instead.
2748template <typename T>
2749class UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator
2750 : public std::iterator<std::output_iterator_tag, T> {
2751 public:
2752 explicit UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator(
2753 RepeatedPtrField<T>* const mutable_field)
2754 : field_(mutable_field) {}
2755 UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator<T>& operator=(
2756 T const* const ptr_to_value) {
2757 field_->UnsafeArenaAddAllocated(const_cast<T*>(ptr_to_value));
2758 return *this;
2759 }
2760 UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator<T>& operator*() {
2761 return *this;
2762 }
2763 UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++() {
2764 return *this;
2765 }
2766 UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++(
2767 int /* unused */) {
2768 return *this;
2769 }
2770
2771 private:
2772 RepeatedPtrField<T>* field_;
2773};
2774
2775} // namespace internal
2776
2777// Provides a back insert iterator for RepeatedField instances,
2778// similar to std::back_inserter().
2779template <typename T>
2780internal::RepeatedFieldBackInsertIterator<T> RepeatedFieldBackInserter(
2781 RepeatedField<T>* const mutable_field) {
2782 return internal::RepeatedFieldBackInsertIterator<T>(mutable_field);
2783}
2784
2785// Provides a back insert iterator for RepeatedPtrField instances,
2786// similar to std::back_inserter().
2787template <typename T>
2788internal::RepeatedPtrFieldBackInsertIterator<T> RepeatedPtrFieldBackInserter(
2789 RepeatedPtrField<T>* const mutable_field) {
2790 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
2791}
2792
2793// Special back insert iterator for RepeatedPtrField instances, just in
2794// case someone wants to write generic template code that can access both
2795// RepeatedFields and RepeatedPtrFields using a common name.
2796template <typename T>
2797internal::RepeatedPtrFieldBackInsertIterator<T> RepeatedFieldBackInserter(
2798 RepeatedPtrField<T>* const mutable_field) {
2799 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
2800}
2801
2802// Provides a back insert iterator for RepeatedPtrField instances
2803// similar to std::back_inserter() which transfers the ownership while
2804// copying elements.
2805template <typename T>
2806internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>
2807AllocatedRepeatedPtrFieldBackInserter(
2808 RepeatedPtrField<T>* const mutable_field) {
2809 return internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>(
2810 mutable_field);
2811}
2812
2813// Similar to AllocatedRepeatedPtrFieldBackInserter, using
2814// UnsafeArenaAddAllocated instead of AddAllocated.
2815// This is slightly faster if that matters. It is also useful in legacy code
2816// that uses temporary ownership to avoid copies. Example:
2817// RepeatedPtrField<T> temp_field;
2818// temp_field.AddAllocated(new T);
2819// ... // Do something with temp_field
2820// temp_field.ExtractSubrange(0, temp_field.size(), nullptr);
2821// If you put temp_field on the arena this fails, because the ownership
2822// transfers to the arena at the "AddAllocated" call and is not released anymore
2823// causing a double delete. Using UnsafeArenaAddAllocated prevents this.
2824template <typename T>
2825internal::UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator<T>
2826UnsafeArenaAllocatedRepeatedPtrFieldBackInserter(
2827 RepeatedPtrField<T>* const mutable_field) {
2828 return internal::UnsafeArenaAllocatedRepeatedPtrFieldBackInsertIterator<T>(
2829 mutable_field);
2830}
2831
2832// Extern declarations of common instantiations to reduce library bloat.
2833extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<bool>;
2834extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<int32>;
2835extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<uint32>;
2836extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<int64>;
2837extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<uint64>;
2838extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<float>;
2839extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE RepeatedField<double>;
2840extern template class PROTOBUF_EXPORT_TEMPLATE_DECLARE
2841 RepeatedPtrField<std::string>;
2842
2843} // namespace protobuf
2844} // namespace google
2845
2846#include <google/protobuf/port_undef.inc>
2847
2848#endif // GOOGLE_PROTOBUF_REPEATED_FIELD_H__
2849