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