1// Protocol Buffers - Google's data interchange format
2// Copyright 2008 Google Inc.  All rights reserved.
3// http://code.google.com/p/protobuf/
4//
5// Redistribution and use in source and binary forms, with or without
6// modification, are permitted provided that the following conditions are
7// met:
8//
9//     * Redistributions of source code must retain the above copyright
10// notice, this list of conditions and the following disclaimer.
11//     * Redistributions in binary form must reproduce the above
12// copyright notice, this list of conditions and the following disclaimer
13// in the documentation and/or other materials provided with the
14// distribution.
15//     * Neither the name of Google Inc. nor the names of its
16// contributors may be used to endorse or promote products derived from
17// this software without specific prior written permission.
18//
19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31// Author: kenton@google.com (Kenton Varda)
32//  Based on original Protocol Buffers design by
33//  Sanjay Ghemawat, Jeff Dean, and others.
34//
35// RepeatedField and RepeatedPtrField are used by generated protocol message
36// classes to manipulate repeated fields.  These classes are very similar to
37// STL's vector, but include a number of optimizations found to be useful
38// specifically in the case of Protocol Buffers.  RepeatedPtrField is
39// particularly different from STL vector as it manages ownership of the
40// pointers that it contains.
41//
42// Typically, clients should not need to access RepeatedField objects directly,
43// but should instead use the accessor functions generated automatically by the
44// protocol compiler.
45
46#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__
47#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__
48
49#include <algorithm>
50#include <string>
51#include <iterator>
52#include <google/protobuf/stubs/common.h>
53#include <google/protobuf/stubs/type_traits.h>
54#include <google/protobuf/generated_message_util.h>
55#include <google/protobuf/message_lite.h>
56
57namespace google {
58
59namespace upb {
60namespace google_opensource {
61class GMR_Handlers;
62}  // namespace google_opensource
63}  // namespace upb
64
65namespace protobuf {
66
67class Message;
68
69namespace internal {
70
71static const int kMinRepeatedFieldAllocationSize = 4;
72
73// A utility function for logging that doesn't need any template types.
74void LogIndexOutOfBounds(int index, int size);
75}  // namespace internal
76
77
78// RepeatedField is used to represent repeated fields of a primitive type (in
79// other words, everything except strings and nested Messages).  Most users will
80// not ever use a RepeatedField directly; they will use the get-by-index,
81// set-by-index, and add accessors that are generated for all repeated fields.
82template <typename Element>
83class RepeatedField {
84 public:
85  RepeatedField();
86  RepeatedField(const RepeatedField& other);
87  template <typename Iter>
88  RepeatedField(Iter begin, const Iter& end);
89  ~RepeatedField();
90
91  RepeatedField& operator=(const RepeatedField& other);
92
93  int size() const;
94
95  const Element& Get(int index) const;
96  Element* Mutable(int index);
97  void Set(int index, const Element& value);
98  void Add(const Element& value);
99  Element* Add();
100  // Remove the last element in the array.
101  void RemoveLast();
102
103  // Extract elements with indices in "[start .. start+num-1]".
104  // Copy them into "elements[0 .. num-1]" if "elements" is not NULL.
105  // Caution: implementation also moves elements with indices [start+num ..].
106  // Calling this routine inside a loop can cause quadratic behavior.
107  void ExtractSubrange(int start, int num, Element* elements);
108
109  void Clear();
110  void MergeFrom(const RepeatedField& other);
111  void CopyFrom(const RepeatedField& other);
112
113  // Reserve space to expand the field to at least the given size.  If the
114  // array is grown, it will always be at least doubled in size.
115  void Reserve(int new_size);
116
117  // Resize the RepeatedField to a new, smaller size.  This is O(1).
118  void Truncate(int new_size);
119
120  void AddAlreadyReserved(const Element& value);
121  Element* AddAlreadyReserved();
122  int Capacity() const;
123
124  // Gets the underlying array.  This pointer is possibly invalidated by
125  // any add or remove operation.
126  Element* mutable_data();
127  const Element* data() const;
128
129  // Swap entire contents with "other".
130  void Swap(RepeatedField* other);
131
132  // Swap two elements.
133  void SwapElements(int index1, int index2);
134
135  // STL-like iterator support
136  typedef Element* iterator;
137  typedef const Element* const_iterator;
138  typedef Element value_type;
139  typedef value_type& reference;
140  typedef const value_type& const_reference;
141  typedef value_type* pointer;
142  typedef const value_type* const_pointer;
143  typedef int size_type;
144  typedef ptrdiff_t difference_type;
145
146  iterator begin();
147  const_iterator begin() const;
148  iterator end();
149  const_iterator end() const;
150
151  // Reverse iterator support
152  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
153  typedef std::reverse_iterator<iterator> reverse_iterator;
154  reverse_iterator rbegin() {
155    return reverse_iterator(end());
156  }
157  const_reverse_iterator rbegin() const {
158    return const_reverse_iterator(end());
159  }
160  reverse_iterator rend() {
161    return reverse_iterator(begin());
162  }
163  const_reverse_iterator rend() const {
164    return const_reverse_iterator(begin());
165  }
166
167  // Returns the number of bytes used by the repeated field, excluding
168  // sizeof(*this)
169  int SpaceUsedExcludingSelf() const;
170
171 private:
172  static const int kInitialSize = 0;
173
174  Element* elements_;
175  int      current_size_;
176  int      total_size_;
177
178  // Move the contents of |from| into |to|, possibly clobbering |from| in the
179  // process.  For primitive types this is just a memcpy(), but it could be
180  // specialized for non-primitive types to, say, swap each element instead.
181  void MoveArray(Element to[], Element from[], int size);
182
183  // Copy the elements of |from| into |to|.
184  void CopyArray(Element to[], const Element from[], int size);
185};
186
187namespace internal {
188template <typename It> class RepeatedPtrIterator;
189template <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator;
190}  // namespace internal
191
192namespace internal {
193
194// This is a helper template to copy an array of elements effeciently when they
195// have a trivial copy constructor, and correctly otherwise. This really
196// shouldn't be necessary, but our compiler doesn't optimize std::copy very
197// effectively.
198template <typename Element,
199          bool HasTrivialCopy = has_trivial_copy<Element>::value>
200struct ElementCopier {
201  void operator()(Element to[], const Element from[], int array_size);
202};
203
204}  // namespace internal
205
206namespace internal {
207
208// This is the common base class for RepeatedPtrFields.  It deals only in void*
209// pointers.  Users should not use this interface directly.
210//
211// The methods of this interface correspond to the methods of RepeatedPtrField,
212// but may have a template argument called TypeHandler.  Its signature is:
213//   class TypeHandler {
214//    public:
215//     typedef MyType Type;
216//     static Type* New();
217//     static void Delete(Type*);
218//     static void Clear(Type*);
219//     static void Merge(const Type& from, Type* to);
220//
221//     // Only needs to be implemented if SpaceUsedExcludingSelf() is called.
222//     static int SpaceUsed(const Type&);
223//   };
224class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase {
225 protected:
226  // The reflection implementation needs to call protected methods directly,
227  // reinterpreting pointers as being to Message instead of a specific Message
228  // subclass.
229  friend class GeneratedMessageReflection;
230
231  // ExtensionSet stores repeated message extensions as
232  // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to
233  // implement SpaceUsed(), and thus need to call SpaceUsedExcludingSelf()
234  // reinterpreting MessageLite as Message.  ExtensionSet also needs to make
235  // use of AddFromCleared(), which is not part of the public interface.
236  friend class ExtensionSet;
237
238  // To parse directly into a proto2 generated class, the upb class GMR_Handlers
239  // needs to be able to modify a RepeatedPtrFieldBase directly.
240  friend class LIBPROTOBUF_EXPORT upb::google_opensource::GMR_Handlers;
241
242  RepeatedPtrFieldBase();
243
244  // Must be called from destructor.
245  template <typename TypeHandler>
246  void Destroy();
247
248  int size() const;
249
250  template <typename TypeHandler>
251  const typename TypeHandler::Type& Get(int index) const;
252  template <typename TypeHandler>
253  typename TypeHandler::Type* Mutable(int index);
254  template <typename TypeHandler>
255  typename TypeHandler::Type* Add();
256  template <typename TypeHandler>
257  void RemoveLast();
258  template <typename TypeHandler>
259  void Clear();
260  template <typename TypeHandler>
261  void MergeFrom(const RepeatedPtrFieldBase& other);
262  template <typename TypeHandler>
263  void CopyFrom(const RepeatedPtrFieldBase& other);
264
265  void CloseGap(int start, int num) {
266    // Close up a gap of "num" elements starting at offset "start".
267    for (int i = start + num; i < allocated_size_; ++i)
268      elements_[i - num] = elements_[i];
269    current_size_ -= num;
270    allocated_size_ -= num;
271  }
272
273  void Reserve(int new_size);
274
275  int Capacity() const;
276
277  // Used for constructing iterators.
278  void* const* raw_data() const;
279  void** raw_mutable_data() const;
280
281  template <typename TypeHandler>
282  typename TypeHandler::Type** mutable_data();
283  template <typename TypeHandler>
284  const typename TypeHandler::Type* const* data() const;
285
286  void Swap(RepeatedPtrFieldBase* other);
287
288  void SwapElements(int index1, int index2);
289
290  template <typename TypeHandler>
291  int SpaceUsedExcludingSelf() const;
292
293
294  // Advanced memory management --------------------------------------
295
296  // Like Add(), but if there are no cleared objects to use, returns NULL.
297  template <typename TypeHandler>
298  typename TypeHandler::Type* AddFromCleared();
299
300  template <typename TypeHandler>
301  void AddAllocated(typename TypeHandler::Type* value);
302  template <typename TypeHandler>
303  typename TypeHandler::Type* ReleaseLast();
304
305  int ClearedCount() const;
306  template <typename TypeHandler>
307  void AddCleared(typename TypeHandler::Type* value);
308  template <typename TypeHandler>
309  typename TypeHandler::Type* ReleaseCleared();
310
311 private:
312  GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase);
313
314  static const int kInitialSize = 0;
315
316  void** elements_;
317  int    current_size_;
318  int    allocated_size_;
319  int    total_size_;
320
321  template <typename TypeHandler>
322  static inline typename TypeHandler::Type* cast(void* element) {
323    return reinterpret_cast<typename TypeHandler::Type*>(element);
324  }
325  template <typename TypeHandler>
326  static inline const typename TypeHandler::Type* cast(const void* element) {
327    return reinterpret_cast<const typename TypeHandler::Type*>(element);
328  }
329};
330
331template <typename GenericType>
332class GenericTypeHandler {
333 public:
334  typedef GenericType Type;
335  static GenericType* New() { return new GenericType; }
336  static void Delete(GenericType* value) { delete value; }
337  static void Clear(GenericType* value) { value->Clear(); }
338  static void Merge(const GenericType& from, GenericType* to) {
339    to->MergeFrom(from);
340  }
341  static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); }
342  static const Type& default_instance() { return Type::default_instance(); }
343};
344
345template <>
346inline void GenericTypeHandler<MessageLite>::Merge(
347    const MessageLite& from, MessageLite* to) {
348  to->CheckTypeAndMergeFrom(from);
349}
350
351template <>
352inline const MessageLite& GenericTypeHandler<MessageLite>::default_instance() {
353  // Yes, the behavior of the code is undefined, but this function is only
354  // called when we're already deep into the world of undefined, because the
355  // caller called Get(index) out of bounds.
356  MessageLite* null = NULL;
357  return *null;
358}
359
360template <>
361inline const Message& GenericTypeHandler<Message>::default_instance() {
362  // Yes, the behavior of the code is undefined, but this function is only
363  // called when we're already deep into the world of undefined, because the
364  // caller called Get(index) out of bounds.
365  Message* null = NULL;
366  return *null;
367}
368
369
370// HACK:  If a class is declared as DLL-exported in MSVC, it insists on
371//   generating copies of all its methods -- even inline ones -- to include
372//   in the DLL.  But SpaceUsed() calls StringSpaceUsedExcludingSelf() which
373//   isn't in the lite library, therefore the lite library cannot link if
374//   StringTypeHandler is exported.  So, we factor out StringTypeHandlerBase,
375//   export that, then make StringTypeHandler be a subclass which is NOT
376//   exported.
377// TODO(kenton):  There has to be a better way.
378class LIBPROTOBUF_EXPORT StringTypeHandlerBase {
379 public:
380  typedef string Type;
381  static string* New();
382  static void Delete(string* value);
383  static void Clear(string* value) { value->clear(); }
384  static void Merge(const string& from, string* to) { *to = from; }
385  static const Type& default_instance() {
386    return ::google::protobuf::internal::kEmptyString;
387  }
388};
389
390class StringTypeHandler : public StringTypeHandlerBase {
391 public:
392  static int SpaceUsed(const string& value)  {
393    return sizeof(value) + StringSpaceUsedExcludingSelf(value);
394  }
395};
396
397
398}  // namespace internal
399
400// RepeatedPtrField is like RepeatedField, but used for repeated strings or
401// Messages.
402template <typename Element>
403class RepeatedPtrField : public internal::RepeatedPtrFieldBase {
404 public:
405  RepeatedPtrField();
406  RepeatedPtrField(const RepeatedPtrField& other);
407  template <typename Iter>
408  RepeatedPtrField(Iter begin, const Iter& end);
409  ~RepeatedPtrField();
410
411  RepeatedPtrField& operator=(const RepeatedPtrField& other);
412
413  int size() const;
414
415  const Element& Get(int index) const;
416  Element* Mutable(int index);
417  Element* Add();
418
419  // Remove the last element in the array.
420  // Ownership of the element is retained by the array.
421  void RemoveLast();
422
423  // Delete elements with indices in the range [start .. start+num-1].
424  // Caution: implementation moves all elements with indices [start+num .. ].
425  // Calling this routine inside a loop can cause quadratic behavior.
426  void DeleteSubrange(int start, int num);
427
428  void Clear();
429  void MergeFrom(const RepeatedPtrField& other);
430  void CopyFrom(const RepeatedPtrField& other);
431
432  // Reserve space to expand the field to at least the given size.  This only
433  // resizes the pointer array; it doesn't allocate any objects.  If the
434  // array is grown, it will always be at least doubled in size.
435  void Reserve(int new_size);
436
437  int Capacity() const;
438
439  // Gets the underlying array.  This pointer is possibly invalidated by
440  // any add or remove operation.
441  Element** mutable_data();
442  const Element* const* data() const;
443
444  // Swap entire contents with "other".
445  void Swap(RepeatedPtrField* other);
446
447  // Swap two elements.
448  void SwapElements(int index1, int index2);
449
450  // STL-like iterator support
451  typedef internal::RepeatedPtrIterator<Element> iterator;
452  typedef internal::RepeatedPtrIterator<const Element> const_iterator;
453  typedef Element value_type;
454  typedef value_type& reference;
455  typedef const value_type& const_reference;
456  typedef value_type* pointer;
457  typedef const value_type* const_pointer;
458  typedef int size_type;
459  typedef ptrdiff_t difference_type;
460
461  iterator begin();
462  const_iterator begin() const;
463  iterator end();
464  const_iterator end() const;
465
466  // Reverse iterator support
467  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
468  typedef std::reverse_iterator<iterator> reverse_iterator;
469  reverse_iterator rbegin() {
470    return reverse_iterator(end());
471  }
472  const_reverse_iterator rbegin() const {
473    return const_reverse_iterator(end());
474  }
475  reverse_iterator rend() {
476    return reverse_iterator(begin());
477  }
478  const_reverse_iterator rend() const {
479    return const_reverse_iterator(begin());
480  }
481
482  // Custom STL-like iterator that iterates over and returns the underlying
483  // pointers to Element rather than Element itself.
484  typedef internal::RepeatedPtrOverPtrsIterator<Element, void*>
485  pointer_iterator;
486  typedef internal::RepeatedPtrOverPtrsIterator<const Element, const void*>
487  const_pointer_iterator;
488  pointer_iterator pointer_begin();
489  const_pointer_iterator pointer_begin() const;
490  pointer_iterator pointer_end();
491  const_pointer_iterator pointer_end() const;
492
493  // Returns (an estimate of) the number of bytes used by the repeated field,
494  // excluding sizeof(*this).
495  int SpaceUsedExcludingSelf() const;
496
497  // Advanced memory management --------------------------------------
498  // When hardcore memory management becomes necessary -- as it sometimes
499  // does here at Google -- the following methods may be useful.
500
501  // Add an already-allocated object, passing ownership to the
502  // RepeatedPtrField.
503  void AddAllocated(Element* value);
504  // Remove the last element and return it, passing ownership to the caller.
505  // Requires:  size() > 0
506  Element* ReleaseLast();
507
508  // Extract elements with indices in the range "[start .. start+num-1]".
509  // The caller assumes ownership of the extracted elements and is responsible
510  // for deleting them when they are no longer needed.
511  // If "elements" is non-NULL, then pointers to the extracted elements
512  // are stored in "elements[0 .. num-1]" for the convenience of the caller.
513  // If "elements" is NULL, then the caller must use some other mechanism
514  // to perform any further operations (like deletion) on these elements.
515  // Caution: implementation also moves elements with indices [start+num ..].
516  // Calling this routine inside a loop can cause quadratic behavior.
517  void ExtractSubrange(int start, int num, Element** elements);
518
519  // When elements are removed by calls to RemoveLast() or Clear(), they
520  // are not actually freed.  Instead, they are cleared and kept so that
521  // they can be reused later.  This can save lots of CPU time when
522  // repeatedly reusing a protocol message for similar purposes.
523  //
524  // Hardcore programs may choose to manipulate these cleared objects
525  // to better optimize memory management using the following routines.
526
527  // Get the number of cleared objects that are currently being kept
528  // around for reuse.
529  int ClearedCount() const;
530  // Add an element to the pool of cleared objects, passing ownership to
531  // the RepeatedPtrField.  The element must be cleared prior to calling
532  // this method.
533  void AddCleared(Element* value);
534  // Remove a single element from the cleared pool and return it, passing
535  // ownership to the caller.  The element is guaranteed to be cleared.
536  // Requires:  ClearedCount() > 0
537  Element* ReleaseCleared();
538
539 protected:
540  // Note:  RepeatedPtrField SHOULD NOT be subclassed by users.  We only
541  //   subclass it in one place as a hack for compatibility with proto1.  The
542  //   subclass needs to know about TypeHandler in order to call protected
543  //   methods on RepeatedPtrFieldBase.
544  class TypeHandler;
545
546};
547
548// implementation ====================================================
549
550template <typename Element>
551inline RepeatedField<Element>::RepeatedField()
552  : elements_(NULL),
553    current_size_(0),
554    total_size_(kInitialSize) {
555}
556
557template <typename Element>
558inline RepeatedField<Element>::RepeatedField(const RepeatedField& other)
559  : elements_(NULL),
560    current_size_(0),
561    total_size_(kInitialSize) {
562  CopyFrom(other);
563}
564
565template <typename Element>
566template <typename Iter>
567inline RepeatedField<Element>::RepeatedField(Iter begin, const Iter& end)
568  : elements_(NULL),
569    current_size_(0),
570    total_size_(kInitialSize) {
571  for (; begin != end; ++begin) {
572    Add(*begin);
573  }
574}
575
576template <typename Element>
577RepeatedField<Element>::~RepeatedField() {
578  delete [] elements_;
579}
580
581template <typename Element>
582inline RepeatedField<Element>&
583RepeatedField<Element>::operator=(const RepeatedField& other) {
584  if (this != &other)
585    CopyFrom(other);
586  return *this;
587}
588
589template <typename Element>
590inline int RepeatedField<Element>::size() const {
591  return current_size_;
592}
593
594template <typename Element>
595inline int RepeatedField<Element>::Capacity() const {
596  return total_size_;
597}
598
599template<typename Element>
600inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) {
601  GOOGLE_DCHECK_LT(size(), Capacity());
602  elements_[current_size_++] = value;
603}
604
605template<typename Element>
606inline Element* RepeatedField<Element>::AddAlreadyReserved() {
607  GOOGLE_DCHECK_LT(size(), Capacity());
608  return &elements_[current_size_++];
609}
610
611template <typename Element>
612inline const Element& RepeatedField<Element>::Get(int index) const {
613  GOOGLE_DCHECK_LT(index, size());
614  return elements_[index];
615}
616
617template <typename Element>
618inline Element* RepeatedField<Element>::Mutable(int index) {
619  GOOGLE_DCHECK_LT(index, size());
620  return elements_ + index;
621}
622
623template <typename Element>
624inline void RepeatedField<Element>::Set(int index, const Element& value) {
625  GOOGLE_DCHECK_LT(index, size());
626  elements_[index] = value;
627}
628
629template <typename Element>
630inline void RepeatedField<Element>::Add(const Element& value) {
631  if (current_size_ == total_size_) Reserve(total_size_ + 1);
632  elements_[current_size_++] = value;
633}
634
635template <typename Element>
636inline Element* RepeatedField<Element>::Add() {
637  if (current_size_ == total_size_) Reserve(total_size_ + 1);
638  return &elements_[current_size_++];
639}
640
641template <typename Element>
642inline void RepeatedField<Element>::RemoveLast() {
643  GOOGLE_DCHECK_GT(current_size_, 0);
644  --current_size_;
645}
646
647template <typename Element>
648void RepeatedField<Element>::ExtractSubrange(
649    int start, int num, Element* elements) {
650  GOOGLE_DCHECK_GE(start, 0);
651  GOOGLE_DCHECK_GE(num, 0);
652  GOOGLE_DCHECK_LE(start + num, this->size());
653
654  // Save the values of the removed elements if requested.
655  if (elements != NULL) {
656    for (int i = 0; i < num; ++i)
657      elements[i] = this->Get(i + start);
658  }
659
660  // Slide remaining elements down to fill the gap.
661  if (num > 0) {
662    for (int i = start + num; i < this->size(); ++i)
663      this->Set(i - num, this->Get(i));
664    this->Truncate(this->size() - num);
665  }
666}
667
668template <typename Element>
669inline void RepeatedField<Element>::Clear() {
670  current_size_ = 0;
671}
672
673template <typename Element>
674inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) {
675  if (other.current_size_ != 0) {
676    Reserve(current_size_ + other.current_size_);
677    CopyArray(elements_ + current_size_, other.elements_, other.current_size_);
678    current_size_ += other.current_size_;
679  }
680}
681
682template <typename Element>
683inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) {
684  Clear();
685  MergeFrom(other);
686}
687
688template <typename Element>
689inline Element* RepeatedField<Element>::mutable_data() {
690  return elements_;
691}
692
693template <typename Element>
694inline const Element* RepeatedField<Element>::data() const {
695  return elements_;
696}
697
698
699template <typename Element>
700void RepeatedField<Element>::Swap(RepeatedField* other) {
701  if (this == other) return;
702  Element* swap_elements     = elements_;
703  int      swap_current_size = current_size_;
704  int      swap_total_size   = total_size_;
705
706  elements_     = other->elements_;
707  current_size_ = other->current_size_;
708  total_size_   = other->total_size_;
709
710  other->elements_     = swap_elements;
711  other->current_size_ = swap_current_size;
712  other->total_size_   = swap_total_size;
713}
714
715template <typename Element>
716void RepeatedField<Element>::SwapElements(int index1, int index2) {
717  std::swap(elements_[index1], elements_[index2]);
718}
719
720template <typename Element>
721inline typename RepeatedField<Element>::iterator
722RepeatedField<Element>::begin() {
723  return elements_;
724}
725template <typename Element>
726inline typename RepeatedField<Element>::const_iterator
727RepeatedField<Element>::begin() const {
728  return elements_;
729}
730template <typename Element>
731inline typename RepeatedField<Element>::iterator
732RepeatedField<Element>::end() {
733  return elements_ + current_size_;
734}
735template <typename Element>
736inline typename RepeatedField<Element>::const_iterator
737RepeatedField<Element>::end() const {
738  return elements_ + current_size_;
739}
740
741template <typename Element>
742inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const {
743  return (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
744}
745
746// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant
747// amount of code bloat.
748template <typename Element>
749void RepeatedField<Element>::Reserve(int new_size) {
750  if (total_size_ >= new_size) return;
751
752  Element* old_elements = elements_;
753  total_size_ = max(google::protobuf::internal::kMinRepeatedFieldAllocationSize,
754                    max(total_size_ * 2, new_size));
755  elements_ = new Element[total_size_];
756  if (old_elements != NULL) {
757    MoveArray(elements_, old_elements, current_size_);
758    delete [] old_elements;
759  }
760}
761
762template <typename Element>
763inline void RepeatedField<Element>::Truncate(int new_size) {
764  GOOGLE_DCHECK_LE(new_size, current_size_);
765  current_size_ = new_size;
766}
767
768template <typename Element>
769inline void RepeatedField<Element>::MoveArray(
770    Element to[], Element from[], int array_size) {
771  CopyArray(to, from, array_size);
772}
773
774template <typename Element>
775inline void RepeatedField<Element>::CopyArray(
776    Element to[], const Element from[], int array_size) {
777  internal::ElementCopier<Element>()(to, from, array_size);
778}
779
780namespace internal {
781
782template <typename Element, bool HasTrivialCopy>
783void ElementCopier<Element, HasTrivialCopy>::operator()(
784    Element to[], const Element from[], int array_size) {
785  std::copy(from, from + array_size, to);
786}
787
788template <typename Element>
789struct ElementCopier<Element, true> {
790  void operator()(Element to[], const Element from[], int array_size) {
791    memcpy(to, from, array_size * sizeof(Element));
792  }
793};
794
795}  // namespace internal
796
797
798// -------------------------------------------------------------------
799
800namespace internal {
801
802inline RepeatedPtrFieldBase::RepeatedPtrFieldBase()
803  : elements_(NULL),
804    current_size_(0),
805    allocated_size_(0),
806    total_size_(kInitialSize) {
807}
808
809template <typename TypeHandler>
810void RepeatedPtrFieldBase::Destroy() {
811  for (int i = 0; i < allocated_size_; i++) {
812    TypeHandler::Delete(cast<TypeHandler>(elements_[i]));
813  }
814  delete [] elements_;
815}
816
817inline int RepeatedPtrFieldBase::size() const {
818  return current_size_;
819}
820
821template <typename TypeHandler>
822inline const typename TypeHandler::Type&
823RepeatedPtrFieldBase::Get(int index) const {
824  GOOGLE_DCHECK_LT(index, size());
825  return *cast<TypeHandler>(elements_[index]);
826}
827
828
829template <typename TypeHandler>
830inline typename TypeHandler::Type*
831RepeatedPtrFieldBase::Mutable(int index) {
832  GOOGLE_DCHECK_LT(index, size());
833  return cast<TypeHandler>(elements_[index]);
834}
835
836template <typename TypeHandler>
837inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() {
838  if (current_size_ < allocated_size_) {
839    return cast<TypeHandler>(elements_[current_size_++]);
840  }
841  if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
842  ++allocated_size_;
843  typename TypeHandler::Type* result = TypeHandler::New();
844  elements_[current_size_++] = result;
845  return result;
846}
847
848template <typename TypeHandler>
849inline void RepeatedPtrFieldBase::RemoveLast() {
850  GOOGLE_DCHECK_GT(current_size_, 0);
851  TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_]));
852}
853
854template <typename TypeHandler>
855void RepeatedPtrFieldBase::Clear() {
856  for (int i = 0; i < current_size_; i++) {
857    TypeHandler::Clear(cast<TypeHandler>(elements_[i]));
858  }
859  current_size_ = 0;
860}
861
862template <typename TypeHandler>
863inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) {
864  Reserve(current_size_ + other.current_size_);
865  for (int i = 0; i < other.current_size_; i++) {
866    TypeHandler::Merge(other.template Get<TypeHandler>(i), Add<TypeHandler>());
867  }
868}
869
870template <typename TypeHandler>
871inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) {
872  RepeatedPtrFieldBase::Clear<TypeHandler>();
873  RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
874}
875
876inline int RepeatedPtrFieldBase::Capacity() const {
877  return total_size_;
878}
879
880inline void* const* RepeatedPtrFieldBase::raw_data() const {
881  return elements_;
882}
883
884inline void** RepeatedPtrFieldBase::raw_mutable_data() const {
885  return elements_;
886}
887
888template <typename TypeHandler>
889inline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() {
890  // TODO(kenton):  Breaks C++ aliasing rules.  We should probably remove this
891  //   method entirely.
892  return reinterpret_cast<typename TypeHandler::Type**>(elements_);
893}
894
895template <typename TypeHandler>
896inline const typename TypeHandler::Type* const*
897RepeatedPtrFieldBase::data() const {
898  // TODO(kenton):  Breaks C++ aliasing rules.  We should probably remove this
899  //   method entirely.
900  return reinterpret_cast<const typename TypeHandler::Type* const*>(elements_);
901}
902
903inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) {
904  std::swap(elements_[index1], elements_[index2]);
905}
906
907template <typename TypeHandler>
908inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const {
909  int allocated_bytes =
910      (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
911  for (int i = 0; i < allocated_size_; ++i) {
912    allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i]));
913  }
914  return allocated_bytes;
915}
916
917template <typename TypeHandler>
918inline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() {
919  if (current_size_ < allocated_size_) {
920    return cast<TypeHandler>(elements_[current_size_++]);
921  } else {
922    return NULL;
923  }
924}
925
926template <typename TypeHandler>
927void RepeatedPtrFieldBase::AddAllocated(
928    typename TypeHandler::Type* value) {
929  // Make room for the new pointer.
930  if (current_size_ == total_size_) {
931    // The array is completely full with no cleared objects, so grow it.
932    Reserve(total_size_ + 1);
933    ++allocated_size_;
934  } else if (allocated_size_ == total_size_) {
935    // There is no more space in the pointer array because it contains some
936    // cleared objects awaiting reuse.  We don't want to grow the array in this
937    // case because otherwise a loop calling AddAllocated() followed by Clear()
938    // would leak memory.
939    TypeHandler::Delete(cast<TypeHandler>(elements_[current_size_]));
940  } else if (current_size_ < allocated_size_) {
941    // We have some cleared objects.  We don't care about their order, so we
942    // can just move the first one to the end to make space.
943    elements_[allocated_size_] = elements_[current_size_];
944    ++allocated_size_;
945  } else {
946    // There are no cleared objects.
947    ++allocated_size_;
948  }
949
950  elements_[current_size_++] = value;
951}
952
953template <typename TypeHandler>
954inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() {
955  GOOGLE_DCHECK_GT(current_size_, 0);
956  typename TypeHandler::Type* result =
957      cast<TypeHandler>(elements_[--current_size_]);
958  --allocated_size_;
959  if (current_size_ < allocated_size_) {
960    // There are cleared elements on the end; replace the removed element
961    // with the last allocated element.
962    elements_[current_size_] = elements_[allocated_size_];
963  }
964  return result;
965}
966
967inline int RepeatedPtrFieldBase::ClearedCount() const {
968  return allocated_size_ - current_size_;
969}
970
971template <typename TypeHandler>
972inline void RepeatedPtrFieldBase::AddCleared(
973    typename TypeHandler::Type* value) {
974  if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
975  elements_[allocated_size_++] = value;
976}
977
978template <typename TypeHandler>
979inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() {
980  GOOGLE_DCHECK_GT(allocated_size_, current_size_);
981  return cast<TypeHandler>(elements_[--allocated_size_]);
982}
983
984}  // namespace internal
985
986// -------------------------------------------------------------------
987
988template <typename Element>
989class RepeatedPtrField<Element>::TypeHandler
990    : public internal::GenericTypeHandler<Element> {
991};
992
993template <>
994class RepeatedPtrField<string>::TypeHandler
995    : public internal::StringTypeHandler {
996};
997
998
999template <typename Element>
1000inline RepeatedPtrField<Element>::RepeatedPtrField() {}
1001
1002template <typename Element>
1003inline RepeatedPtrField<Element>::RepeatedPtrField(
1004    const RepeatedPtrField& other) {
1005  CopyFrom(other);
1006}
1007
1008template <typename Element>
1009template <typename Iter>
1010inline RepeatedPtrField<Element>::RepeatedPtrField(
1011    Iter begin, const Iter& end) {
1012  for (; begin != end; ++begin) {
1013    *Add() = *begin;
1014  }
1015}
1016
1017template <typename Element>
1018RepeatedPtrField<Element>::~RepeatedPtrField() {
1019  Destroy<TypeHandler>();
1020}
1021
1022template <typename Element>
1023inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=(
1024    const RepeatedPtrField& other) {
1025  if (this != &other)
1026    CopyFrom(other);
1027  return *this;
1028}
1029
1030template <typename Element>
1031inline int RepeatedPtrField<Element>::size() const {
1032  return RepeatedPtrFieldBase::size();
1033}
1034
1035template <typename Element>
1036inline const Element& RepeatedPtrField<Element>::Get(int index) const {
1037  return RepeatedPtrFieldBase::Get<TypeHandler>(index);
1038}
1039
1040
1041template <typename Element>
1042inline Element* RepeatedPtrField<Element>::Mutable(int index) {
1043  return RepeatedPtrFieldBase::Mutable<TypeHandler>(index);
1044}
1045
1046template <typename Element>
1047inline Element* RepeatedPtrField<Element>::Add() {
1048  return RepeatedPtrFieldBase::Add<TypeHandler>();
1049}
1050
1051template <typename Element>
1052inline void RepeatedPtrField<Element>::RemoveLast() {
1053  RepeatedPtrFieldBase::RemoveLast<TypeHandler>();
1054}
1055
1056template <typename Element>
1057inline void RepeatedPtrField<Element>::DeleteSubrange(int start, int num) {
1058  GOOGLE_DCHECK_GE(start, 0);
1059  GOOGLE_DCHECK_GE(num, 0);
1060  GOOGLE_DCHECK_LE(start + num, size());
1061  for (int i = 0; i < num; ++i)
1062    delete RepeatedPtrFieldBase::Mutable<TypeHandler>(start + i);
1063  ExtractSubrange(start, num, NULL);
1064}
1065
1066template <typename Element>
1067inline void RepeatedPtrField<Element>::ExtractSubrange(
1068    int start, int num, Element** elements) {
1069  GOOGLE_DCHECK_GE(start, 0);
1070  GOOGLE_DCHECK_GE(num, 0);
1071  GOOGLE_DCHECK_LE(start + num, size());
1072
1073  if (num > 0) {
1074    // Save the values of the removed elements if requested.
1075    if (elements != NULL) {
1076      for (int i = 0; i < num; ++i)
1077        elements[i] = RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start);
1078    }
1079    CloseGap(start, num);
1080  }
1081}
1082
1083template <typename Element>
1084inline void RepeatedPtrField<Element>::Clear() {
1085  RepeatedPtrFieldBase::Clear<TypeHandler>();
1086}
1087
1088template <typename Element>
1089inline void RepeatedPtrField<Element>::MergeFrom(
1090    const RepeatedPtrField& other) {
1091  RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
1092}
1093
1094template <typename Element>
1095inline void RepeatedPtrField<Element>::CopyFrom(
1096    const RepeatedPtrField& other) {
1097  RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other);
1098}
1099
1100template <typename Element>
1101inline Element** RepeatedPtrField<Element>::mutable_data() {
1102  return RepeatedPtrFieldBase::mutable_data<TypeHandler>();
1103}
1104
1105template <typename Element>
1106inline const Element* const* RepeatedPtrField<Element>::data() const {
1107  return RepeatedPtrFieldBase::data<TypeHandler>();
1108}
1109
1110template <typename Element>
1111void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) {
1112  RepeatedPtrFieldBase::Swap(other);
1113}
1114
1115template <typename Element>
1116void RepeatedPtrField<Element>::SwapElements(int index1, int index2) {
1117  RepeatedPtrFieldBase::SwapElements(index1, index2);
1118}
1119
1120template <typename Element>
1121inline int RepeatedPtrField<Element>::SpaceUsedExcludingSelf() const {
1122  return RepeatedPtrFieldBase::SpaceUsedExcludingSelf<TypeHandler>();
1123}
1124
1125template <typename Element>
1126inline void RepeatedPtrField<Element>::AddAllocated(Element* value) {
1127  RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value);
1128}
1129
1130template <typename Element>
1131inline Element* RepeatedPtrField<Element>::ReleaseLast() {
1132  return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>();
1133}
1134
1135
1136template <typename Element>
1137inline int RepeatedPtrField<Element>::ClearedCount() const {
1138  return RepeatedPtrFieldBase::ClearedCount();
1139}
1140
1141template <typename Element>
1142inline void RepeatedPtrField<Element>::AddCleared(Element* value) {
1143  return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value);
1144}
1145
1146template <typename Element>
1147inline Element* RepeatedPtrField<Element>::ReleaseCleared() {
1148  return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>();
1149}
1150
1151template <typename Element>
1152inline void RepeatedPtrField<Element>::Reserve(int new_size) {
1153  return RepeatedPtrFieldBase::Reserve(new_size);
1154}
1155
1156template <typename Element>
1157inline int RepeatedPtrField<Element>::Capacity() const {
1158  return RepeatedPtrFieldBase::Capacity();
1159}
1160
1161// -------------------------------------------------------------------
1162
1163namespace internal {
1164
1165// STL-like iterator implementation for RepeatedPtrField.  You should not
1166// refer to this class directly; use RepeatedPtrField<T>::iterator instead.
1167//
1168// The iterator for RepeatedPtrField<T>, RepeatedPtrIterator<T>, is
1169// very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors.h,
1170// but adds random-access operators and is modified to wrap a void** base
1171// iterator (since RepeatedPtrField stores its array as a void* array and
1172// casting void** to T** would violate C++ aliasing rules).
1173//
1174// This code based on net/proto/proto-array-internal.h by Jeffrey Yasskin
1175// (jyasskin@google.com).
1176template<typename Element>
1177class RepeatedPtrIterator
1178    : public std::iterator<
1179          std::random_access_iterator_tag, Element> {
1180 public:
1181  typedef RepeatedPtrIterator<Element> iterator;
1182  typedef std::iterator<
1183          std::random_access_iterator_tag, Element> superclass;
1184
1185  // Let the compiler know that these are type names, so we don't have to
1186  // write "typename" in front of them everywhere.
1187  typedef typename superclass::reference reference;
1188  typedef typename superclass::pointer pointer;
1189  typedef typename superclass::difference_type difference_type;
1190
1191  RepeatedPtrIterator() : it_(NULL) {}
1192  explicit RepeatedPtrIterator(void* const* it) : it_(it) {}
1193
1194  // Allow "upcasting" from RepeatedPtrIterator<T**> to
1195  // RepeatedPtrIterator<const T*const*>.
1196  template<typename OtherElement>
1197  RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other)
1198      : it_(other.it_) {
1199    // Force a compiler error if the other type is not convertible to ours.
1200    if (false) {
1201      implicit_cast<Element*, OtherElement*>(0);
1202    }
1203  }
1204
1205  // dereferenceable
1206  reference operator*() const { return *reinterpret_cast<Element*>(*it_); }
1207  pointer   operator->() const { return &(operator*()); }
1208
1209  // {inc,dec}rementable
1210  iterator& operator++() { ++it_; return *this; }
1211  iterator  operator++(int) { return iterator(it_++); }
1212  iterator& operator--() { --it_; return *this; }
1213  iterator  operator--(int) { return iterator(it_--); }
1214
1215  // equality_comparable
1216  bool operator==(const iterator& x) const { return it_ == x.it_; }
1217  bool operator!=(const iterator& x) const { return it_ != x.it_; }
1218
1219  // less_than_comparable
1220  bool operator<(const iterator& x) const { return it_ < x.it_; }
1221  bool operator<=(const iterator& x) const { return it_ <= x.it_; }
1222  bool operator>(const iterator& x) const { return it_ > x.it_; }
1223  bool operator>=(const iterator& x) const { return it_ >= x.it_; }
1224
1225  // addable, subtractable
1226  iterator& operator+=(difference_type d) {
1227    it_ += d;
1228    return *this;
1229  }
1230  friend iterator operator+(iterator it, difference_type d) {
1231    it += d;
1232    return it;
1233  }
1234  friend iterator operator+(difference_type d, iterator it) {
1235    it += d;
1236    return it;
1237  }
1238  iterator& operator-=(difference_type d) {
1239    it_ -= d;
1240    return *this;
1241  }
1242  friend iterator operator-(iterator it, difference_type d) {
1243    it -= d;
1244    return it;
1245  }
1246
1247  // indexable
1248  reference operator[](difference_type d) const { return *(*this + d); }
1249
1250  // random access iterator
1251  difference_type operator-(const iterator& x) const { return it_ - x.it_; }
1252
1253 private:
1254  template<typename OtherElement>
1255  friend class RepeatedPtrIterator;
1256
1257  // The internal iterator.
1258  void* const* it_;
1259};
1260
1261// Provide an iterator that operates on pointers to the underlying objects
1262// rather than the objects themselves as RepeatedPtrIterator does.
1263// Consider using this when working with stl algorithms that change
1264// the array.
1265// The VoidPtr template parameter holds the type-agnostic pointer value
1266// referenced by the iterator.  It should either be "void *" for a mutable
1267// iterator, or "const void *" for a constant iterator.
1268template<typename Element, typename VoidPtr>
1269class RepeatedPtrOverPtrsIterator
1270    : public std::iterator<std::random_access_iterator_tag, Element*> {
1271 public:
1272  typedef RepeatedPtrOverPtrsIterator<Element, VoidPtr> iterator;
1273  typedef std::iterator<
1274          std::random_access_iterator_tag, Element*> superclass;
1275
1276  // Let the compiler know that these are type names, so we don't have to
1277  // write "typename" in front of them everywhere.
1278  typedef typename superclass::reference reference;
1279  typedef typename superclass::pointer pointer;
1280  typedef typename superclass::difference_type difference_type;
1281
1282  RepeatedPtrOverPtrsIterator() : it_(NULL) {}
1283  explicit RepeatedPtrOverPtrsIterator(VoidPtr* it) : it_(it) {}
1284
1285  // dereferenceable
1286  reference operator*() const { return *reinterpret_cast<Element**>(it_); }
1287  pointer   operator->() const { return &(operator*()); }
1288
1289  // {inc,dec}rementable
1290  iterator& operator++() { ++it_; return *this; }
1291  iterator  operator++(int) { return iterator(it_++); }
1292  iterator& operator--() { --it_; return *this; }
1293  iterator  operator--(int) { return iterator(it_--); }
1294
1295  // equality_comparable
1296  bool operator==(const iterator& x) const { return it_ == x.it_; }
1297  bool operator!=(const iterator& x) const { return it_ != x.it_; }
1298
1299  // less_than_comparable
1300  bool operator<(const iterator& x) const { return it_ < x.it_; }
1301  bool operator<=(const iterator& x) const { return it_ <= x.it_; }
1302  bool operator>(const iterator& x) const { return it_ > x.it_; }
1303  bool operator>=(const iterator& x) const { return it_ >= x.it_; }
1304
1305  // addable, subtractable
1306  iterator& operator+=(difference_type d) {
1307    it_ += d;
1308    return *this;
1309  }
1310  friend iterator operator+(iterator it, difference_type d) {
1311    it += d;
1312    return it;
1313  }
1314  friend iterator operator+(difference_type d, iterator it) {
1315    it += d;
1316    return it;
1317  }
1318  iterator& operator-=(difference_type d) {
1319    it_ -= d;
1320    return *this;
1321  }
1322  friend iterator operator-(iterator it, difference_type d) {
1323    it -= d;
1324    return it;
1325  }
1326
1327  // indexable
1328  reference operator[](difference_type d) const { return *(*this + d); }
1329
1330  // random access iterator
1331  difference_type operator-(const iterator& x) const { return it_ - x.it_; }
1332
1333 private:
1334  template<typename OtherElement>
1335  friend class RepeatedPtrIterator;
1336
1337  // The internal iterator.
1338  VoidPtr* it_;
1339};
1340
1341}  // namespace internal
1342
1343template <typename Element>
1344inline typename RepeatedPtrField<Element>::iterator
1345RepeatedPtrField<Element>::begin() {
1346  return iterator(raw_data());
1347}
1348template <typename Element>
1349inline typename RepeatedPtrField<Element>::const_iterator
1350RepeatedPtrField<Element>::begin() const {
1351  return iterator(raw_data());
1352}
1353template <typename Element>
1354inline typename RepeatedPtrField<Element>::iterator
1355RepeatedPtrField<Element>::end() {
1356  return iterator(raw_data() + size());
1357}
1358template <typename Element>
1359inline typename RepeatedPtrField<Element>::const_iterator
1360RepeatedPtrField<Element>::end() const {
1361  return iterator(raw_data() + size());
1362}
1363
1364template <typename Element>
1365inline typename RepeatedPtrField<Element>::pointer_iterator
1366RepeatedPtrField<Element>::pointer_begin() {
1367  return pointer_iterator(raw_mutable_data());
1368}
1369template <typename Element>
1370inline typename RepeatedPtrField<Element>::const_pointer_iterator
1371RepeatedPtrField<Element>::pointer_begin() const {
1372  return const_pointer_iterator(const_cast<const void**>(raw_mutable_data()));
1373}
1374template <typename Element>
1375inline typename RepeatedPtrField<Element>::pointer_iterator
1376RepeatedPtrField<Element>::pointer_end() {
1377  return pointer_iterator(raw_mutable_data() + size());
1378}
1379template <typename Element>
1380inline typename RepeatedPtrField<Element>::const_pointer_iterator
1381RepeatedPtrField<Element>::pointer_end() const {
1382  return const_pointer_iterator(
1383      const_cast<const void**>(raw_mutable_data() + size()));
1384}
1385
1386
1387// Iterators and helper functions that follow the spirit of the STL
1388// std::back_insert_iterator and std::back_inserter but are tailor-made
1389// for RepeatedField and RepatedPtrField. Typical usage would be:
1390//
1391//   std::copy(some_sequence.begin(), some_sequence.end(),
1392//             google::protobuf::RepeatedFieldBackInserter(proto.mutable_sequence()));
1393//
1394// Ported by johannes from util/gtl/proto-array-iterators.h
1395
1396namespace internal {
1397// A back inserter for RepeatedField objects.
1398template<typename T> class RepeatedFieldBackInsertIterator
1399    : public std::iterator<std::output_iterator_tag, T> {
1400 public:
1401  explicit RepeatedFieldBackInsertIterator(
1402      RepeatedField<T>* const mutable_field)
1403      : field_(mutable_field) {
1404  }
1405  RepeatedFieldBackInsertIterator<T>& operator=(const T& value) {
1406    field_->Add(value);
1407    return *this;
1408  }
1409  RepeatedFieldBackInsertIterator<T>& operator*() {
1410    return *this;
1411  }
1412  RepeatedFieldBackInsertIterator<T>& operator++() {
1413    return *this;
1414  }
1415  RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) {
1416    return *this;
1417  }
1418
1419 private:
1420  RepeatedField<T>* field_;
1421};
1422
1423// A back inserter for RepeatedPtrField objects.
1424template<typename T> class RepeatedPtrFieldBackInsertIterator
1425    : public std::iterator<std::output_iterator_tag, T> {
1426 public:
1427  RepeatedPtrFieldBackInsertIterator(
1428      RepeatedPtrField<T>* const mutable_field)
1429      : field_(mutable_field) {
1430  }
1431  RepeatedPtrFieldBackInsertIterator<T>& operator=(const T& value) {
1432    *field_->Add() = value;
1433    return *this;
1434  }
1435  RepeatedPtrFieldBackInsertIterator<T>& operator=(
1436      const T* const ptr_to_value) {
1437    *field_->Add() = *ptr_to_value;
1438    return *this;
1439  }
1440  RepeatedPtrFieldBackInsertIterator<T>& operator*() {
1441    return *this;
1442  }
1443  RepeatedPtrFieldBackInsertIterator<T>& operator++() {
1444    return *this;
1445  }
1446  RepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) {
1447    return *this;
1448  }
1449
1450 private:
1451  RepeatedPtrField<T>* field_;
1452};
1453
1454// A back inserter for RepeatedPtrFields that inserts by transfering ownership
1455// of a pointer.
1456template<typename T> class AllocatedRepeatedPtrFieldBackInsertIterator
1457    : public std::iterator<std::output_iterator_tag, T> {
1458 public:
1459  explicit AllocatedRepeatedPtrFieldBackInsertIterator(
1460      RepeatedPtrField<T>* const mutable_field)
1461      : field_(mutable_field) {
1462  }
1463  AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator=(
1464      T* const ptr_to_value) {
1465    field_->AddAllocated(ptr_to_value);
1466    return *this;
1467  }
1468  AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator*() {
1469    return *this;
1470  }
1471  AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++() {
1472    return *this;
1473  }
1474  AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++(
1475      int /* unused */) {
1476    return *this;
1477  }
1478
1479 private:
1480  RepeatedPtrField<T>* field_;
1481};
1482}  // namespace internal
1483
1484// Provides a back insert iterator for RepeatedField instances,
1485// similar to std::back_inserter().
1486template<typename T> internal::RepeatedFieldBackInsertIterator<T>
1487RepeatedFieldBackInserter(RepeatedField<T>* const mutable_field) {
1488  return internal::RepeatedFieldBackInsertIterator<T>(mutable_field);
1489}
1490
1491// Provides a back insert iterator for RepeatedPtrField instances,
1492// similar to std::back_inserter().
1493template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
1494RepeatedPtrFieldBackInserter(RepeatedPtrField<T>* const mutable_field) {
1495  return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
1496}
1497
1498// Special back insert iterator for RepeatedPtrField instances, just in
1499// case someone wants to write generic template code that can access both
1500// RepeatedFields and RepeatedPtrFields using a common name.
1501template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
1502RepeatedFieldBackInserter(RepeatedPtrField<T>* const mutable_field) {
1503  return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
1504}
1505
1506// Provides a back insert iterator for RepeatedPtrField instances
1507// similar to std::back_inserter() which transfers the ownership while
1508// copying elements.
1509template<typename T> internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>
1510AllocatedRepeatedPtrFieldBackInserter(
1511    RepeatedPtrField<T>* const mutable_field) {
1512  return internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>(
1513      mutable_field);
1514}
1515
1516}  // namespace protobuf
1517
1518}  // namespace google
1519#endif  // GOOGLE_PROTOBUF_REPEATED_FIELD_H__
1520