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