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