15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Protocol Buffers - Google's data interchange format
25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2008 Google Inc.  All rights reserved.
35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// http://code.google.com/p/protobuf/
45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without
65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are
75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met:
85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Redistributions of source code must retain the above copyright
105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer.
115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Redistributions in binary form must reproduce the above
125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer
135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the
145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution.
155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     * Neither the name of Google Inc. nor the names of its
165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from
175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission.
185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: kenton@google.com (Kenton Varda)
325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//  Based on original Protocol Buffers design by
335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//  Sanjay Ghemawat, Jeff Dean, and others.
345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// RepeatedField and RepeatedPtrField are used by generated protocol message
365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// classes to manipulate repeated fields.  These classes are very similar to
375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// STL's vector, but include a number of optimizations found to be useful
385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// specifically in the case of Protocol Buffers.  RepeatedPtrField is
395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// particularly different from STL vector as it manages ownership of the
405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// pointers that it contains.
415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Typically, clients should not need to access RepeatedField objects directly,
435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// but should instead use the accessor functions generated automatically by the
445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// protocol compiler.
455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__
475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__
485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
49ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch#include <algorithm>
505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string>
515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <iterator>
525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <google/protobuf/stubs/common.h>
53ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch#include <google/protobuf/stubs/type_traits.h>
54ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch#include <google/protobuf/generated_message_util.h>
555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <google/protobuf/message_lite.h>
565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace google {
585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
59ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochnamespace upb {
603551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)namespace google_opensource {
613551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)class GMR_Handlers;
623551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)}  // namespace google_opensource
63ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}  // namespace upb
64ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace protobuf {
665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Message;
685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace internal {
705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
71ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochstatic const int kMinRepeatedFieldAllocationSize = 4;
725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
73ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch// A utility function for logging that doesn't need any template types.
74ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochvoid LogIndexOutOfBounds(int index, int size);
755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace internal
765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
77ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// RepeatedField is used to represent repeated fields of a primitive type (in
795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// other words, everything except strings and nested Messages).  Most users will
805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// not ever use a RepeatedField directly; they will use the get-by-index,
815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// set-by-index, and add accessors that are generated for all repeated fields.
825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class RepeatedField {
845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedField();
865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedField(const RepeatedField& other);
87ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  template <typename Iter>
88ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  RepeatedField(Iter begin, const Iter& end);
895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ~RepeatedField();
905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedField& operator=(const RepeatedField& other);
925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int size() const;
945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const Element& Get(int index) const;
965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* Mutable(int index);
975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Set(int index, const Element& value);
985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Add(const Element& value);
995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* Add();
1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Remove the last element in the array.
1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void RemoveLast();
102ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
103ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Extract elements with indices in "[start .. start+num-1]".
104ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Copy them into "elements[0 .. num-1]" if "elements" is not NULL.
105ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Caution: implementation also moves elements with indices [start+num ..].
106ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Calling this routine inside a loop can cause quadratic behavior.
107ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  void ExtractSubrange(int start, int num, Element* elements);
108ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Clear();
1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void MergeFrom(const RepeatedField& other);
1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void CopyFrom(const RepeatedField& other);
1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Reserve space to expand the field to at least the given size.  If the
1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // array is grown, it will always be at least doubled in size.
1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Reserve(int new_size);
1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Resize the RepeatedField to a new, smaller size.  This is O(1).
1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Truncate(int new_size);
1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AddAlreadyReserved(const Element& value);
1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* AddAlreadyReserved();
1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int Capacity() const;
1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Gets the underlying array.  This pointer is possibly invalidated by
1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // any add or remove operation.
1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* mutable_data();
1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const Element* data() const;
1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Swap entire contents with "other".
1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Swap(RepeatedField* other);
1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Swap two elements.
1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void SwapElements(int index1, int index2);
1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // STL-like iterator support
1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef Element* iterator;
1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef const Element* const_iterator;
1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef Element value_type;
139ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef value_type& reference;
140ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef const value_type& const_reference;
141ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef value_type* pointer;
142ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef const value_type* const_pointer;
143ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef int size_type;
144ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef ptrdiff_t difference_type;
1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iterator begin();
1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const_iterator begin() const;
1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iterator end();
1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const_iterator end() const;
1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
151ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Reverse iterator support
152ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
153ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef std::reverse_iterator<iterator> reverse_iterator;
154ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  reverse_iterator rbegin() {
155ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return reverse_iterator(end());
156ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
157ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  const_reverse_iterator rbegin() const {
158ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return const_reverse_iterator(end());
159ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
160ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  reverse_iterator rend() {
161ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return reverse_iterator(begin());
162ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
163ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  const_reverse_iterator rend() const {
164ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return const_reverse_iterator(begin());
165ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
166ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Returns the number of bytes used by the repeated field, excluding
1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // sizeof(*this)
1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int SpaceUsedExcludingSelf() const;
1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private:
172ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  static const int kInitialSize = 0;
1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* elements_;
1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int      current_size_;
1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int      total_size_;
1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Move the contents of |from| into |to|, possibly clobbering |from| in the
1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // process.  For primitive types this is just a memcpy(), but it could be
1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // specialized for non-primitive types to, say, swap each element instead.
1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void MoveArray(Element to[], Element from[], int size);
1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Copy the elements of |from| into |to|.
1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void CopyArray(Element to[], const Element from[], int size);
1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace internal {
1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename It> class RepeatedPtrIterator;
189ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator;
190ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}  // namespace internal
191ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
192ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochnamespace internal {
193ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
194ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch// This is a helper template to copy an array of elements effeciently when they
195ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch// have a trivial copy constructor, and correctly otherwise. This really
196ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch// shouldn't be necessary, but our compiler doesn't optimize std::copy very
197ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch// effectively.
198ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <typename Element,
199ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch          bool HasTrivialCopy = has_trivial_copy<Element>::value>
200ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochstruct ElementCopier {
201ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  void operator()(Element to[], const Element from[], int array_size);
202ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch};
203ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace internal
2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace internal {
2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is the common base class for RepeatedPtrFields.  It deals only in void*
2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// pointers.  Users should not use this interface directly.
2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The methods of this interface correspond to the methods of RepeatedPtrField,
2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// but may have a template argument called TypeHandler.  Its signature is:
2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   class TypeHandler {
2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//    public:
2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     typedef MyType Type;
2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     static Type* New();
2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     static void Delete(Type*);
2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     static void Clear(Type*);
2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     static void Merge(const Type& from, Type* to);
2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     // Only needs to be implemented if SpaceUsedExcludingSelf() is called.
2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//     static int SpaceUsed(const Type&);
2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   };
2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase {
2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) protected:
2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // The reflection implementation needs to call protected methods directly,
2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // reinterpreting pointers as being to Message instead of a specific Message
2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // subclass.
2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  friend class GeneratedMessageReflection;
2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // ExtensionSet stores repeated message extensions as
2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to
2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // implement SpaceUsed(), and thus need to call SpaceUsedExcludingSelf()
2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // reinterpreting MessageLite as Message.  ExtensionSet also needs to make
2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // use of AddFromCleared(), which is not part of the public interface.
2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  friend class ExtensionSet;
2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2383551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)  // To parse directly into a proto2 generated class, the upb class GMR_Handlers
239ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // needs to be able to modify a RepeatedPtrFieldBase directly.
2403551c9c881056c480085172ff9840cab31610854Torne (Richard Coles)  friend class LIBPROTOBUF_EXPORT upb::google_opensource::GMR_Handlers;
241ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedPtrFieldBase();
2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Must be called from destructor.
2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Destroy();
2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int size() const;
2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const typename TypeHandler::Type& Get(int index) const;
2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type* Mutable(int index);
2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type* Add();
2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void RemoveLast();
2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Clear();
2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void MergeFrom(const RepeatedPtrFieldBase& other);
2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void CopyFrom(const RepeatedPtrFieldBase& other);
2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
265ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  void CloseGap(int start, int num) {
266ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    // Close up a gap of "num" elements starting at offset "start".
267ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    for (int i = start + num; i < allocated_size_; ++i)
268ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch      elements_[i - num] = elements_[i];
269ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    current_size_ -= num;
270ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    allocated_size_ -= num;
271ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
272ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Reserve(int new_size);
2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int Capacity() const;
2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Used for constructing iterators.
2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void* const* raw_data() const;
2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void** raw_mutable_data() const;
2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type** mutable_data();
2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const typename TypeHandler::Type* const* data() const;
2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Swap(RepeatedPtrFieldBase* other);
2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void SwapElements(int index1, int index2);
2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int SpaceUsedExcludingSelf() const;
2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Advanced memory management --------------------------------------
2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Like Add(), but if there are no cleared objects to use, returns NULL.
2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type* AddFromCleared();
2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AddAllocated(typename TypeHandler::Type* value);
3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type* ReleaseLast();
3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int ClearedCount() const;
3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AddCleared(typename TypeHandler::Type* value);
3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type* ReleaseCleared();
3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private:
3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase);
3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
314ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  static const int kInitialSize = 0;
3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void** elements_;
3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int    current_size_;
3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int    allocated_size_;
3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int    total_size_;
3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static inline typename TypeHandler::Type* cast(void* element) {
3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return reinterpret_cast<typename TypeHandler::Type*>(element);
3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  template <typename TypeHandler>
3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static inline const typename TypeHandler::Type* cast(const void* element) {
3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return reinterpret_cast<const typename TypeHandler::Type*>(element);
3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename GenericType>
3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class GenericTypeHandler {
3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef GenericType Type;
3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static GenericType* New() { return new GenericType; }
3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Delete(GenericType* value) { delete value; }
3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Clear(GenericType* value) { value->Clear(); }
3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Merge(const GenericType& from, GenericType* to) {
3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    to->MergeFrom(from);
3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); }
342ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  static const Type& default_instance() { return Type::default_instance(); }
3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <>
3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void GenericTypeHandler<MessageLite>::Merge(
3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    const MessageLite& from, MessageLite* to) {
3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  to->CheckTypeAndMergeFrom(from);
3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
351ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <>
352ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochinline const MessageLite& GenericTypeHandler<MessageLite>::default_instance() {
353ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Yes, the behavior of the code is undefined, but this function is only
354ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // called when we're already deep into the world of undefined, because the
355ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // caller called Get(index) out of bounds.
356ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  MessageLite* null = NULL;
357ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  return *null;
358ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}
359ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
360ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <>
361ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochinline const Message& GenericTypeHandler<Message>::default_instance() {
362ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Yes, the behavior of the code is undefined, but this function is only
363ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // called when we're already deep into the world of undefined, because the
364ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // caller called Get(index) out of bounds.
365ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  Message* null = NULL;
366ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  return *null;
367ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}
368ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
369ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// HACK:  If a class is declared as DLL-exported in MSVC, it insists on
3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   generating copies of all its methods -- even inline ones -- to include
3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   in the DLL.  But SpaceUsed() calls StringSpaceUsedExcludingSelf() which
3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   isn't in the lite library, therefore the lite library cannot link if
3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   StringTypeHandler is exported.  So, we factor out StringTypeHandlerBase,
3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   export that, then make StringTypeHandler be a subclass which is NOT
3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//   exported.
3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO(kenton):  There has to be a better way.
3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class LIBPROTOBUF_EXPORT StringTypeHandlerBase {
3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef string Type;
3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static string* New();
3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Delete(string* value);
3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Clear(string* value) { value->clear(); }
3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static void Merge(const string& from, string* to) { *to = from; }
385ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  static const Type& default_instance() {
3865d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)    return ::google::protobuf::internal::GetEmptyString();
387ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class StringTypeHandler : public StringTypeHandlerBase {
3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  static int SpaceUsed(const string& value)  {
3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return sizeof(value) + StringSpaceUsedExcludingSelf(value);
3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace internal
3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// RepeatedPtrField is like RepeatedField, but used for repeated strings or
4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Messages.
4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class RepeatedPtrField : public internal::RepeatedPtrFieldBase {
4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public:
4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedPtrField();
4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedPtrField(const RepeatedPtrField& other);
407ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  template <typename Iter>
408ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  RepeatedPtrField(Iter begin, const Iter& end);
4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ~RepeatedPtrField();
4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedPtrField& operator=(const RepeatedPtrField& other);
4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int size() const;
4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const Element& Get(int index) const;
4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* Mutable(int index);
4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* Add();
418ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
419ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Remove the last element in the array.
420ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Ownership of the element is retained by the array.
421ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  void RemoveLast();
422ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
423ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Delete elements with indices in the range [start .. start+num-1].
424ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Caution: implementation moves all elements with indices [start+num .. ].
425ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Calling this routine inside a loop can cause quadratic behavior.
426ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  void DeleteSubrange(int start, int num);
427ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Clear();
4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void MergeFrom(const RepeatedPtrField& other);
4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void CopyFrom(const RepeatedPtrField& other);
4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Reserve space to expand the field to at least the given size.  This only
4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // resizes the pointer array; it doesn't allocate any objects.  If the
4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // array is grown, it will always be at least doubled in size.
4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Reserve(int new_size);
4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int Capacity() const;
4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Gets the underlying array.  This pointer is possibly invalidated by
4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // any add or remove operation.
4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element** mutable_data();
4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const Element* const* data() const;
4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Swap entire contents with "other".
4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void Swap(RepeatedPtrField* other);
4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Swap two elements.
4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void SwapElements(int index1, int index2);
4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // STL-like iterator support
4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef internal::RepeatedPtrIterator<Element> iterator;
4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef internal::RepeatedPtrIterator<const Element> const_iterator;
4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typedef Element value_type;
454ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef value_type& reference;
455ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef const value_type& const_reference;
456ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef value_type* pointer;
457ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef const value_type* const_pointer;
458ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef int size_type;
459ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef ptrdiff_t difference_type;
4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iterator begin();
4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const_iterator begin() const;
4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  iterator end();
4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const_iterator end() const;
4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
466ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Reverse iterator support
467ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
468ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef std::reverse_iterator<iterator> reverse_iterator;
469ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  reverse_iterator rbegin() {
470ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return reverse_iterator(end());
471ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
472ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  const_reverse_iterator rbegin() const {
473ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return const_reverse_iterator(end());
474ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
475ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  reverse_iterator rend() {
476ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return reverse_iterator(begin());
477ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
478ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  const_reverse_iterator rend() const {
479ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    return const_reverse_iterator(begin());
480ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
481ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Custom STL-like iterator that iterates over and returns the underlying
4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // pointers to Element rather than Element itself.
484ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef internal::RepeatedPtrOverPtrsIterator<Element, void*>
485ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  pointer_iterator;
486ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  typedef internal::RepeatedPtrOverPtrsIterator<const Element, const void*>
487ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  const_pointer_iterator;
4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  pointer_iterator pointer_begin();
489ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  const_pointer_iterator pointer_begin() const;
4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  pointer_iterator pointer_end();
491ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  const_pointer_iterator pointer_end() const;
4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Returns (an estimate of) the number of bytes used by the repeated field,
4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // excluding sizeof(*this).
4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int SpaceUsedExcludingSelf() const;
4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Advanced memory management --------------------------------------
498ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // When hardcore memory management becomes necessary -- as it sometimes
4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // does here at Google -- the following methods may be useful.
5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Add an already-allocated object, passing ownership to the
5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // RepeatedPtrField.
5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AddAllocated(Element* value);
504ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Remove the last element and return it, passing ownership to the caller.
5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Requires:  size() > 0
5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* ReleaseLast();
5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
508ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Extract elements with indices in the range "[start .. start+num-1]".
509ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // The caller assumes ownership of the extracted elements and is responsible
510ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // for deleting them when they are no longer needed.
511ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // If "elements" is non-NULL, then pointers to the extracted elements
512ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // are stored in "elements[0 .. num-1]" for the convenience of the caller.
513ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // If "elements" is NULL, then the caller must use some other mechanism
514ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // to perform any further operations (like deletion) on these elements.
515ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Caution: implementation also moves elements with indices [start+num ..].
516ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Calling this routine inside a loop can cause quadratic behavior.
517ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  void ExtractSubrange(int start, int num, Element** elements);
518ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // When elements are removed by calls to RemoveLast() or Clear(), they
5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // are not actually freed.  Instead, they are cleared and kept so that
5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // they can be reused later.  This can save lots of CPU time when
5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // repeatedly reusing a protocol message for similar purposes.
5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //
524ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Hardcore programs may choose to manipulate these cleared objects
525ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // to better optimize memory management using the following routines.
5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Get the number of cleared objects that are currently being kept
5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // around for reuse.
5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int ClearedCount() const;
5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Add an element to the pool of cleared objects, passing ownership to
5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // the RepeatedPtrField.  The element must be cleared prior to calling
5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // this method.
5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  void AddCleared(Element* value);
5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Remove a single element from the cleared pool and return it, passing
5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // ownership to the caller.  The element is guaranteed to be cleared.
5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Requires:  ClearedCount() > 0
5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* ReleaseCleared();
5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) protected:
5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Note:  RepeatedPtrField SHOULD NOT be subclassed by users.  We only
5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //   subclass it in one place as a hack for compatibility with proto1.  The
5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //   subclass needs to know about TypeHandler in order to call protected
5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //   methods on RepeatedPtrFieldBase.
5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  class TypeHandler;
5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)};
5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// implementation ====================================================
5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline RepeatedField<Element>::RepeatedField()
552ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  : elements_(NULL),
5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    current_size_(0),
5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    total_size_(kInitialSize) {
5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline RepeatedField<Element>::RepeatedField(const RepeatedField& other)
559ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  : elements_(NULL),
5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    current_size_(0),
5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    total_size_(kInitialSize) {
5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CopyFrom(other);
5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
566ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <typename Iter>
567ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochinline RepeatedField<Element>::RepeatedField(Iter begin, const Iter& end)
568ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  : elements_(NULL),
569ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    current_size_(0),
570ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    total_size_(kInitialSize) {
571ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  for (; begin != end; ++begin) {
572ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    Add(*begin);
5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
577ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben MurdochRepeatedField<Element>::~RepeatedField() {
578ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  delete [] elements_;
579ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}
580ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
581ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <typename Element>
5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline RepeatedField<Element>&
5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedField<Element>::operator=(const RepeatedField& other) {
584ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  if (this != &other)
585ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    CopyFrom(other);
5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return *this;
5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int RepeatedField<Element>::size() const {
5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return current_size_;
5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int RepeatedField<Element>::Capacity() const {
5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return total_size_;
5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Element>
6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) {
6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LT(size(), Capacity());
6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_[current_size_++] = value;
6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename Element>
6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline Element* RepeatedField<Element>::AddAlreadyReserved() {
6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LT(size(), Capacity());
6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return &elements_[current_size_++];
6095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline const Element& RepeatedField<Element>::Get(int index) const {
6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LT(index, size());
6145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_[index];
6155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline Element* RepeatedField<Element>::Mutable(int index) {
6195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LT(index, size());
6205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_ + index;
6215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::Set(int index, const Element& value) {
6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LT(index, size());
6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_[index] = value;
6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::Add(const Element& value) {
6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (current_size_ == total_size_) Reserve(total_size_ + 1);
6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_[current_size_++] = value;
6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline Element* RepeatedField<Element>::Add() {
6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (current_size_ == total_size_) Reserve(total_size_ + 1);
6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return &elements_[current_size_++];
6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::RemoveLast() {
6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_GT(current_size_, 0);
6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  --current_size_;
6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
648ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochvoid RepeatedField<Element>::ExtractSubrange(
649ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    int start, int num, Element* elements) {
650ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  GOOGLE_DCHECK_GE(start, 0);
651ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  GOOGLE_DCHECK_GE(num, 0);
652ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  GOOGLE_DCHECK_LE(start + num, this->size());
653ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
654ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Save the values of the removed elements if requested.
655ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  if (elements != NULL) {
656ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    for (int i = 0; i < num; ++i)
657ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch      elements[i] = this->Get(i + start);
658ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
659ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
660ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  // Slide remaining elements down to fill the gap.
661ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  if (num > 0) {
662ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    for (int i = start + num; i < this->size(); ++i)
663ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch      this->Set(i - num, this->Get(i));
664ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    this->Truncate(this->size() - num);
665ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
666ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}
667ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
668ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <typename Element>
6695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::Clear() {
6705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  current_size_ = 0;
6715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) {
675ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  if (other.current_size_ != 0) {
676ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    Reserve(current_size_ + other.current_size_);
677ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    CopyArray(elements_ + current_size_, other.elements_, other.current_size_);
678ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    current_size_ += other.current_size_;
679ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
6805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) {
6845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Clear();
6855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MergeFrom(other);
6865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline Element* RepeatedField<Element>::mutable_data() {
6905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_;
6915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
6945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline const Element* RepeatedField<Element>::data() const {
6955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_;
6965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RepeatedField<Element>::Swap(RepeatedField* other) {
701ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  if (this == other) return;
7025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* swap_elements     = elements_;
7035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int      swap_current_size = current_size_;
7045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int      swap_total_size   = total_size_;
7055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_     = other->elements_;
7075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  current_size_ = other->current_size_;
7085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  total_size_   = other->total_size_;
7095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  other->elements_     = swap_elements;
7115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  other->current_size_ = swap_current_size;
7125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  other->total_size_   = swap_total_size;
7135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RepeatedField<Element>::SwapElements(int index1, int index2) {
7175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::swap(elements_[index1], elements_[index2]);
7185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename RepeatedField<Element>::iterator
7225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedField<Element>::begin() {
7235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_;
7245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename RepeatedField<Element>::const_iterator
7275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedField<Element>::begin() const {
7285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_;
7295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename RepeatedField<Element>::iterator
7325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedField<Element>::end() {
7335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_ + current_size_;
7345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename RepeatedField<Element>::const_iterator
7375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedField<Element>::end() const {
7385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_ + current_size_;
7395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const {
743ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  return (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
7445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
746ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant
7475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// amount of code bloat.
7485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RepeatedField<Element>::Reserve(int new_size) {
7505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (total_size_ >= new_size) return;
7515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Element* old_elements = elements_;
753ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  total_size_ = max(google::protobuf::internal::kMinRepeatedFieldAllocationSize,
754ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch                    max(total_size_ * 2, new_size));
7555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_ = new Element[total_size_];
756ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  if (old_elements != NULL) {
757ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    MoveArray(elements_, old_elements, current_size_);
7585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete [] old_elements;
7595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::Truncate(int new_size) {
7645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LE(new_size, current_size_);
7655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  current_size_ = new_size;
7665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::MoveArray(
7705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Element to[], Element from[], int array_size) {
771ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  CopyArray(to, from, array_size);
7725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Element>
7755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedField<Element>::CopyArray(
7765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Element to[], const Element from[], int array_size) {
777ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  internal::ElementCopier<Element>()(to, from, array_size);
7785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
780ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochnamespace internal {
781ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
782ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <typename Element, bool HasTrivialCopy>
783ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochvoid ElementCopier<Element, HasTrivialCopy>::operator()(
784ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    Element to[], const Element from[], int array_size) {
785ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  std::copy(from, from + array_size, to);
786ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}
787ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
788ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochtemplate <typename Element>
789ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdochstruct ElementCopier<Element, true> {
790ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  void operator()(Element to[], const Element from[], int array_size) {
791ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch    memcpy(to, from, array_size * sizeof(Element));
792ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  }
793ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch};
794ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
795ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch}  // namespace internal
796ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
7975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// -------------------------------------------------------------------
7995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace internal {
8015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline RepeatedPtrFieldBase::RepeatedPtrFieldBase()
803ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  : elements_(NULL),
8045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    current_size_(0),
8055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    allocated_size_(0),
8065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    total_size_(kInitialSize) {
8075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RepeatedPtrFieldBase::Destroy() {
8115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < allocated_size_; i++) {
8125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TypeHandler::Delete(cast<TypeHandler>(elements_[i]));
8135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
814ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch  delete [] elements_;
8155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int RepeatedPtrFieldBase::size() const {
8185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return current_size_;
8195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline const typename TypeHandler::Type&
8235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedPtrFieldBase::Get(int index) const {
8245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LT(index, size());
8255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return *cast<TypeHandler>(elements_[index]);
8265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
828ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch
8295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename TypeHandler::Type*
8315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedPtrFieldBase::Mutable(int index) {
8325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_LT(index, size());
8335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return cast<TypeHandler>(elements_[index]);
8345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() {
8385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (current_size_ < allocated_size_) {
8395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return cast<TypeHandler>(elements_[current_size_++]);
8405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
8425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  ++allocated_size_;
8435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type* result = TypeHandler::New();
8445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_[current_size_++] = result;
8455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return result;
8465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedPtrFieldBase::RemoveLast() {
8505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_GT(current_size_, 0);
8515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_]));
8525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RepeatedPtrFieldBase::Clear() {
8565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < current_size_; i++) {
8575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TypeHandler::Clear(cast<TypeHandler>(elements_[i]));
8585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  current_size_ = 0;
8605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) {
8645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Reserve(current_size_ + other.current_size_);
8655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < other.current_size_; i++) {
8665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TypeHandler::Merge(other.template Get<TypeHandler>(i), Add<TypeHandler>());
8675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) {
8725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedPtrFieldBase::Clear<TypeHandler>();
8735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
8745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int RepeatedPtrFieldBase::Capacity() const {
8775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return total_size_;
8785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void* const* RepeatedPtrFieldBase::raw_data() const {
8815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_;
8825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void** RepeatedPtrFieldBase::raw_mutable_data() const {
8855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return elements_;
8865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() {
8905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // TODO(kenton):  Breaks C++ aliasing rules.  We should probably remove this
8915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //   method entirely.
8925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return reinterpret_cast<typename TypeHandler::Type**>(elements_);
8935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
8965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline const typename TypeHandler::Type* const*
8975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RepeatedPtrFieldBase::data() const {
8985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // TODO(kenton):  Breaks C++ aliasing rules.  We should probably remove this
8995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  //   method entirely.
9005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return reinterpret_cast<const typename TypeHandler::Type* const*>(elements_);
9015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) {
9045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  std::swap(elements_[index1], elements_[index2]);
9055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
9085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const {
9095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int allocated_bytes =
910ba5b9a6411cb1792fd21f0a078d7a25cd1ceec16Ben Murdoch      (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
9115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < allocated_size_; ++i) {
9125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i]));
9135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
9145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return allocated_bytes;
9155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
9185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() {
9195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (current_size_ < allocated_size_) {
9205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return cast<TypeHandler>(elements_[current_size_++]);
9215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } else {
9225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    return NULL;
9235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
9245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
9275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RepeatedPtrFieldBase::AddAllocated(
9285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    typename TypeHandler::Type* value) {
9295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  // Make room for the new pointer.
9305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (current_size_ == total_size_) {
9315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // The array is completely full with no cleared objects, so grow it.
9325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Reserve(total_size_ + 1);
9335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ++allocated_size_;
9345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } else if (allocated_size_ == total_size_) {
9355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // There is no more space in the pointer array because it contains some
9365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // cleared objects awaiting reuse.  We don't want to grow the array in this
9375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // case because otherwise a loop calling AddAllocated() followed by Clear()
9385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // would leak memory.
9395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    TypeHandler::Delete(cast<TypeHandler>(elements_[current_size_]));
9405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } else if (current_size_ < allocated_size_) {
9415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // We have some cleared objects.  We don't care about their order, so we
9425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // can just move the first one to the end to make space.
9435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    elements_[allocated_size_] = elements_[current_size_];
9445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ++allocated_size_;
9455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  } else {
9465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // There are no cleared objects.
9475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    ++allocated_size_;
9485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
9495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_[current_size_++] = value;
9515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
9545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() {
9555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_GT(current_size_, 0);
9565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  typename TypeHandler::Type* result =
9575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      cast<TypeHandler>(elements_[--current_size_]);
9585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  --allocated_size_;
9595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (current_size_ < allocated_size_) {
9605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // There are cleared elements on the end; replace the removed element
9615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // with the last allocated element.
9625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    elements_[current_size_] = elements_[allocated_size_];
9635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
9645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return result;
9655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline int RepeatedPtrFieldBase::ClearedCount() const {
9685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return allocated_size_ - current_size_;
9695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
9725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void RepeatedPtrFieldBase::AddCleared(
9735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    typename TypeHandler::Type* value) {
9745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
9755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  elements_[allocated_size_++] = value;
9765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename TypeHandler>
9795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() {
9805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  GOOGLE_DCHECK_GT(allocated_size_, current_size_);
9815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return cast<TypeHandler>(elements_[--allocated_size_]);
9825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace internal
9855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// -------------------------------------------------------------------
987