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