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