Home | History | Annotate | Download | only in protobuf
      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 (at) 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 
     57 namespace google {
     58 
     59 namespace upb {
     60 namespace google_opensource {
     61 class GMR_Handlers;
     62 }  // namespace google_opensource
     63 }  // namespace upb
     64 
     65 namespace protobuf {
     66 
     67 class Message;
     68 
     69 namespace internal {
     70 
     71 static const int kMinRepeatedFieldAllocationSize = 4;
     72 
     73 // A utility function for logging that doesn't need any template types.
     74 void 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.
     82 template <typename Element>
     83 class 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 
    187 namespace internal {
    188 template <typename It> class RepeatedPtrIterator;
    189 template <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator;
    190 }  // namespace internal
    191 
    192 namespace 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.
    198 template <typename Element,
    199           bool HasTrivialCopy = has_trivial_copy<Element>::value>
    200 struct ElementCopier {
    201   void operator()(Element to[], const Element from[], int array_size);
    202 };
    203 
    204 }  // namespace internal
    205 
    206 namespace 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 //   };
    224 class 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 
    331 template <typename GenericType>
    332 class 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 
    345 template <>
    346 inline void GenericTypeHandler<MessageLite>::Merge(
    347     const MessageLite& from, MessageLite* to) {
    348   to->CheckTypeAndMergeFrom(from);
    349 }
    350 
    351 template <>
    352 inline 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 
    360 template <>
    361 inline 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.
    378 class 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 
    390 class 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.
    402 template <typename Element>
    403 class 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 
    550 template <typename Element>
    551 inline RepeatedField<Element>::RepeatedField()
    552   : elements_(NULL),
    553     current_size_(0),
    554     total_size_(kInitialSize) {
    555 }
    556 
    557 template <typename Element>
    558 inline RepeatedField<Element>::RepeatedField(const RepeatedField& other)
    559   : elements_(NULL),
    560     current_size_(0),
    561     total_size_(kInitialSize) {
    562   CopyFrom(other);
    563 }
    564 
    565 template <typename Element>
    566 template <typename Iter>
    567 inline 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 
    576 template <typename Element>
    577 RepeatedField<Element>::~RepeatedField() {
    578   delete [] elements_;
    579 }
    580 
    581 template <typename Element>
    582 inline RepeatedField<Element>&
    583 RepeatedField<Element>::operator=(const RepeatedField& other) {
    584   if (this != &other)
    585     CopyFrom(other);
    586   return *this;
    587 }
    588 
    589 template <typename Element>
    590 inline int RepeatedField<Element>::size() const {
    591   return current_size_;
    592 }
    593 
    594 template <typename Element>
    595 inline int RepeatedField<Element>::Capacity() const {
    596   return total_size_;
    597 }
    598 
    599 template<typename Element>
    600 inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) {
    601   GOOGLE_DCHECK_LT(size(), Capacity());
    602   elements_[current_size_++] = value;
    603 }
    604 
    605 template<typename Element>
    606 inline Element* RepeatedField<Element>::AddAlreadyReserved() {
    607   GOOGLE_DCHECK_LT(size(), Capacity());
    608   return &elements_[current_size_++];
    609 }
    610 
    611 template <typename Element>
    612 inline const Element& RepeatedField<Element>::Get(int index) const {
    613   GOOGLE_DCHECK_LT(index, size());
    614   return elements_[index];
    615 }
    616 
    617 template <typename Element>
    618 inline Element* RepeatedField<Element>::Mutable(int index) {
    619   GOOGLE_DCHECK_LT(index, size());
    620   return elements_ + index;
    621 }
    622 
    623 template <typename Element>
    624 inline void RepeatedField<Element>::Set(int index, const Element& value) {
    625   GOOGLE_DCHECK_LT(index, size());
    626   elements_[index] = value;
    627 }
    628 
    629 template <typename Element>
    630 inline void RepeatedField<Element>::Add(const Element& value) {
    631   if (current_size_ == total_size_) Reserve(total_size_ + 1);
    632   elements_[current_size_++] = value;
    633 }
    634 
    635 template <typename Element>
    636 inline Element* RepeatedField<Element>::Add() {
    637   if (current_size_ == total_size_) Reserve(total_size_ + 1);
    638   return &elements_[current_size_++];
    639 }
    640 
    641 template <typename Element>
    642 inline void RepeatedField<Element>::RemoveLast() {
    643   GOOGLE_DCHECK_GT(current_size_, 0);
    644   --current_size_;
    645 }
    646 
    647 template <typename Element>
    648 void 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 
    668 template <typename Element>
    669 inline void RepeatedField<Element>::Clear() {
    670   current_size_ = 0;
    671 }
    672 
    673 template <typename Element>
    674 inline 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 
    682 template <typename Element>
    683 inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) {
    684   Clear();
    685   MergeFrom(other);
    686 }
    687 
    688 template <typename Element>
    689 inline Element* RepeatedField<Element>::mutable_data() {
    690   return elements_;
    691 }
    692 
    693 template <typename Element>
    694 inline const Element* RepeatedField<Element>::data() const {
    695   return elements_;
    696 }
    697 
    698 
    699 template <typename Element>
    700 void 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 
    715 template <typename Element>
    716 void RepeatedField<Element>::SwapElements(int index1, int index2) {
    717   std::swap(elements_[index1], elements_[index2]);
    718 }
    719 
    720 template <typename Element>
    721 inline typename RepeatedField<Element>::iterator
    722 RepeatedField<Element>::begin() {
    723   return elements_;
    724 }
    725 template <typename Element>
    726 inline typename RepeatedField<Element>::const_iterator
    727 RepeatedField<Element>::begin() const {
    728   return elements_;
    729 }
    730 template <typename Element>
    731 inline typename RepeatedField<Element>::iterator
    732 RepeatedField<Element>::end() {
    733   return elements_ + current_size_;
    734 }
    735 template <typename Element>
    736 inline typename RepeatedField<Element>::const_iterator
    737 RepeatedField<Element>::end() const {
    738   return elements_ + current_size_;
    739 }
    740 
    741 template <typename Element>
    742 inline 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.
    748 template <typename Element>
    749 void 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 
    762 template <typename Element>
    763 inline void RepeatedField<Element>::Truncate(int new_size) {
    764   GOOGLE_DCHECK_LE(new_size, current_size_);
    765   current_size_ = new_size;
    766 }
    767 
    768 template <typename Element>
    769 inline void RepeatedField<Element>::MoveArray(
    770     Element to[], Element from[], int array_size) {
    771   CopyArray(to, from, array_size);
    772 }
    773 
    774 template <typename Element>
    775 inline void RepeatedField<Element>::CopyArray(
    776     Element to[], const Element from[], int array_size) {
    777   internal::ElementCopier<Element>()(to, from, array_size);
    778 }
    779 
    780 namespace internal {
    781 
    782 template <typename Element, bool HasTrivialCopy>
    783 void ElementCopier<Element, HasTrivialCopy>::operator()(
    784     Element to[], const Element from[], int array_size) {
    785   std::copy(from, from + array_size, to);
    786 }
    787 
    788 template <typename Element>
    789 struct 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 
    800 namespace internal {
    801 
    802 inline RepeatedPtrFieldBase::RepeatedPtrFieldBase()
    803   : elements_(NULL),
    804     current_size_(0),
    805     allocated_size_(0),
    806     total_size_(kInitialSize) {
    807 }
    808 
    809 template <typename TypeHandler>
    810 void RepeatedPtrFieldBase::Destroy() {
    811   for (int i = 0; i < allocated_size_; i++) {
    812     TypeHandler::Delete(cast<TypeHandler>(elements_[i]));
    813   }
    814   delete [] elements_;
    815 }
    816 
    817 inline int RepeatedPtrFieldBase::size() const {
    818   return current_size_;
    819 }
    820 
    821 template <typename TypeHandler>
    822 inline const typename TypeHandler::Type&
    823 RepeatedPtrFieldBase::Get(int index) const {
    824   GOOGLE_DCHECK_LT(index, size());
    825   return *cast<TypeHandler>(elements_[index]);
    826 }
    827 
    828 
    829 template <typename TypeHandler>
    830 inline typename TypeHandler::Type*
    831 RepeatedPtrFieldBase::Mutable(int index) {
    832   GOOGLE_DCHECK_LT(index, size());
    833   return cast<TypeHandler>(elements_[index]);
    834 }
    835 
    836 template <typename TypeHandler>
    837 inline 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 
    848 template <typename TypeHandler>
    849 inline void RepeatedPtrFieldBase::RemoveLast() {
    850   GOOGLE_DCHECK_GT(current_size_, 0);
    851   TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_]));
    852 }
    853 
    854 template <typename TypeHandler>
    855 void 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 
    862 template <typename TypeHandler>
    863 inline 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 
    870 template <typename TypeHandler>
    871 inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) {
    872   RepeatedPtrFieldBase::Clear<TypeHandler>();
    873   RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
    874 }
    875 
    876 inline int RepeatedPtrFieldBase::Capacity() const {
    877   return total_size_;
    878 }
    879 
    880 inline void* const* RepeatedPtrFieldBase::raw_data() const {
    881   return elements_;
    882 }
    883 
    884 inline void** RepeatedPtrFieldBase::raw_mutable_data() const {
    885   return elements_;
    886 }
    887 
    888 template <typename TypeHandler>
    889 inline 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 
    895 template <typename TypeHandler>
    896 inline const typename TypeHandler::Type* const*
    897 RepeatedPtrFieldBase::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 
    903 inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) {
    904   std::swap(elements_[index1], elements_[index2]);
    905 }
    906 
    907 template <typename TypeHandler>
    908 inline 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 
    917 template <typename TypeHandler>
    918 inline 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 
    926 template <typename TypeHandler>
    927 void 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 
    953 template <typename TypeHandler>
    954 inline 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 
    967 inline int RepeatedPtrFieldBase::ClearedCount() const {
    968   return allocated_size_ - current_size_;
    969 }
    970 
    971 template <typename TypeHandler>
    972 inline 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 
    978 template <typename TypeHandler>
    979 inline 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 
    988 template <typename Element>
    989 class RepeatedPtrField<Element>::TypeHandler
    990     : public internal::GenericTypeHandler<Element> {
    991 };
    992 
    993 template <>
    994 class RepeatedPtrField<string>::TypeHandler
    995     : public internal::StringTypeHandler {
    996 };
    997 
    998 
    999 template <typename Element>
   1000 inline RepeatedPtrField<Element>::RepeatedPtrField() {}
   1001 
   1002 template <typename Element>
   1003 inline RepeatedPtrField<Element>::RepeatedPtrField(
   1004     const RepeatedPtrField& other) {
   1005   CopyFrom(other);
   1006 }
   1007 
   1008 template <typename Element>
   1009 template <typename Iter>
   1010 inline RepeatedPtrField<Element>::RepeatedPtrField(
   1011     Iter begin, const Iter& end) {
   1012   for (; begin != end; ++begin) {
   1013     *Add() = *begin;
   1014   }
   1015 }
   1016 
   1017 template <typename Element>
   1018 RepeatedPtrField<Element>::~RepeatedPtrField() {
   1019   Destroy<TypeHandler>();
   1020 }
   1021 
   1022 template <typename Element>
   1023 inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=(
   1024     const RepeatedPtrField& other) {
   1025   if (this != &other)
   1026     CopyFrom(other);
   1027   return *this;
   1028 }
   1029 
   1030 template <typename Element>
   1031 inline int RepeatedPtrField<Element>::size() const {
   1032   return RepeatedPtrFieldBase::size();
   1033 }
   1034 
   1035 template <typename Element>
   1036 inline const Element& RepeatedPtrField<Element>::Get(int index) const {
   1037   return RepeatedPtrFieldBase::Get<TypeHandler>(index);
   1038 }
   1039 
   1040 
   1041 template <typename Element>
   1042 inline Element* RepeatedPtrField<Element>::Mutable(int index) {
   1043   return RepeatedPtrFieldBase::Mutable<TypeHandler>(index);
   1044 }
   1045 
   1046 template <typename Element>
   1047 inline Element* RepeatedPtrField<Element>::Add() {
   1048   return RepeatedPtrFieldBase::Add<TypeHandler>();
   1049 }
   1050 
   1051 template <typename Element>
   1052 inline void RepeatedPtrField<Element>::RemoveLast() {
   1053   RepeatedPtrFieldBase::RemoveLast<TypeHandler>();
   1054 }
   1055 
   1056 template <typename Element>
   1057 inline 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 
   1066 template <typename Element>
   1067 inline 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 
   1083 template <typename Element>
   1084 inline void RepeatedPtrField<Element>::Clear() {
   1085   RepeatedPtrFieldBase::Clear<TypeHandler>();
   1086 }
   1087 
   1088 template <typename Element>
   1089 inline void RepeatedPtrField<Element>::MergeFrom(
   1090     const RepeatedPtrField& other) {
   1091   RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
   1092 }
   1093 
   1094 template <typename Element>
   1095 inline void RepeatedPtrField<Element>::CopyFrom(
   1096     const RepeatedPtrField& other) {
   1097   RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other);
   1098 }
   1099 
   1100 template <typename Element>
   1101 inline Element** RepeatedPtrField<Element>::mutable_data() {
   1102   return RepeatedPtrFieldBase::mutable_data<TypeHandler>();
   1103 }
   1104 
   1105 template <typename Element>
   1106 inline const Element* const* RepeatedPtrField<Element>::data() const {
   1107   return RepeatedPtrFieldBase::data<TypeHandler>();
   1108 }
   1109 
   1110 template <typename Element>
   1111 void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) {
   1112   RepeatedPtrFieldBase::Swap(other);
   1113 }
   1114 
   1115 template <typename Element>
   1116 void RepeatedPtrField<Element>::SwapElements(int index1, int index2) {
   1117   RepeatedPtrFieldBase::SwapElements(index1, index2);
   1118 }
   1119 
   1120 template <typename Element>
   1121 inline int RepeatedPtrField<Element>::SpaceUsedExcludingSelf() const {
   1122   return RepeatedPtrFieldBase::SpaceUsedExcludingSelf<TypeHandler>();
   1123 }
   1124 
   1125 template <typename Element>
   1126 inline void RepeatedPtrField<Element>::AddAllocated(Element* value) {
   1127   RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value);
   1128 }
   1129 
   1130 template <typename Element>
   1131 inline Element* RepeatedPtrField<Element>::ReleaseLast() {
   1132   return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>();
   1133 }
   1134 
   1135 
   1136 template <typename Element>
   1137 inline int RepeatedPtrField<Element>::ClearedCount() const {
   1138   return RepeatedPtrFieldBase::ClearedCount();
   1139 }
   1140 
   1141 template <typename Element>
   1142 inline void RepeatedPtrField<Element>::AddCleared(Element* value) {
   1143   return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value);
   1144 }
   1145 
   1146 template <typename Element>
   1147 inline Element* RepeatedPtrField<Element>::ReleaseCleared() {
   1148   return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>();
   1149 }
   1150 
   1151 template <typename Element>
   1152 inline void RepeatedPtrField<Element>::Reserve(int new_size) {
   1153   return RepeatedPtrFieldBase::Reserve(new_size);
   1154 }
   1155 
   1156 template <typename Element>
   1157 inline int RepeatedPtrField<Element>::Capacity() const {
   1158   return RepeatedPtrFieldBase::Capacity();
   1159 }
   1160 
   1161 // -------------------------------------------------------------------
   1162 
   1163 namespace 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 (at) google.com).
   1176 template<typename Element>
   1177 class 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.
   1268 template<typename Element, typename VoidPtr>
   1269 class 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 
   1343 template <typename Element>
   1344 inline typename RepeatedPtrField<Element>::iterator
   1345 RepeatedPtrField<Element>::begin() {
   1346   return iterator(raw_data());
   1347 }
   1348 template <typename Element>
   1349 inline typename RepeatedPtrField<Element>::const_iterator
   1350 RepeatedPtrField<Element>::begin() const {
   1351   return iterator(raw_data());
   1352 }
   1353 template <typename Element>
   1354 inline typename RepeatedPtrField<Element>::iterator
   1355 RepeatedPtrField<Element>::end() {
   1356   return iterator(raw_data() + size());
   1357 }
   1358 template <typename Element>
   1359 inline typename RepeatedPtrField<Element>::const_iterator
   1360 RepeatedPtrField<Element>::end() const {
   1361   return iterator(raw_data() + size());
   1362 }
   1363 
   1364 template <typename Element>
   1365 inline typename RepeatedPtrField<Element>::pointer_iterator
   1366 RepeatedPtrField<Element>::pointer_begin() {
   1367   return pointer_iterator(raw_mutable_data());
   1368 }
   1369 template <typename Element>
   1370 inline typename RepeatedPtrField<Element>::const_pointer_iterator
   1371 RepeatedPtrField<Element>::pointer_begin() const {
   1372   return const_pointer_iterator(const_cast<const void**>(raw_mutable_data()));
   1373 }
   1374 template <typename Element>
   1375 inline typename RepeatedPtrField<Element>::pointer_iterator
   1376 RepeatedPtrField<Element>::pointer_end() {
   1377   return pointer_iterator(raw_mutable_data() + size());
   1378 }
   1379 template <typename Element>
   1380 inline typename RepeatedPtrField<Element>::const_pointer_iterator
   1381 RepeatedPtrField<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 
   1396 namespace internal {
   1397 // A back inserter for RepeatedField objects.
   1398 template<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.
   1424 template<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.
   1456 template<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().
   1486 template<typename T> internal::RepeatedFieldBackInsertIterator<T>
   1487 RepeatedFieldBackInserter(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().
   1493 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
   1494 RepeatedPtrFieldBackInserter(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.
   1501 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
   1502 RepeatedFieldBackInserter(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.
   1509 template<typename T> internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>
   1510 AllocatedRepeatedPtrFieldBackInserter(
   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