1fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// Protocol Buffers - Google's data interchange format
2fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// Copyright 2008 Google Inc.  All rights reserved.
3fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// http://code.google.com/p/protobuf/
4fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//
5fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// Redistribution and use in source and binary forms, with or without
6fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// modification, are permitted provided that the following conditions are
7fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// met:
8fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//
9fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     * Redistributions of source code must retain the above copyright
10fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// notice, this list of conditions and the following disclaimer.
11fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     * Redistributions in binary form must reproduce the above
12fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// copyright notice, this list of conditions and the following disclaimer
13fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// in the documentation and/or other materials provided with the
14fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// distribution.
15fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     * Neither the name of Google Inc. nor the names of its
16fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// contributors may be used to endorse or promote products derived from
17fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// this software without specific prior written permission.
18fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//
19fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
31fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// Author: kenton@google.com (Kenton Varda)
32fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//  Based on original Protocol Buffers design by
33fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//  Sanjay Ghemawat, Jeff Dean, and others.
34fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//
35fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// RepeatedField and RepeatedPtrField are used by generated protocol message
36fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// classes to manipulate repeated fields.  These classes are very similar to
37fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// STL's vector, but include a number of optimizations found to be useful
38fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// specifically in the case of Protocol Buffers.  RepeatedPtrField is
39fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// particularly different from STL vector as it manages ownership of the
40fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// pointers that it contains.
41fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//
42fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// Typically, clients should not need to access RepeatedField objects directly,
43fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// but should instead use the accessor functions generated automatically by the
44fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// protocol compiler.
45fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
46fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__
47fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__
48fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
49fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville#include <string>
50fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville#include <iterator>
51fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville#include <google/protobuf/stubs/common.h>
52fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville#include <google/protobuf/message_lite.h>
53fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
54fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillenamespace google {
55d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
56fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillenamespace protobuf {
57fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
58fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass Message;
59fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
60fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillenamespace internal {
61fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
62fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// We need this (from generated_message_reflection.cc).
63fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleLIBPROTOBUF_EXPORT int StringSpaceUsedExcludingSelf(const string& str);
64fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
65fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}  // namespace internal
66fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
67fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// RepeatedField is used to represent repeated fields of a primitive type (in
68fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// other words, everything except strings and nested Messages).  Most users will
69fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// not ever use a RepeatedField directly; they will use the get-by-index,
70fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// set-by-index, and add accessors that are generated for all repeated fields.
71fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
72fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass RepeatedField {
73fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville public:
74fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedField();
75fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  ~RepeatedField();
76fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
77fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int size() const;
78fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
79d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  const Element& Get(int index) const;
80fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* Mutable(int index);
81d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  void Set(int index, const Element& value);
82d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  void Add(const Element& value);
83d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  Element* Add();
84fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Remove the last element in the array.
85fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // We don't provide a way to remove any element other than the last
86fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // because it invites inefficient use, such as O(n^2) filtering loops
87fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // that should have been O(n).  If you want to remove an element other
88fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // than the last, the best way to do it is to re-arrange the elements
89fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // so that the one you want removed is at the end, then call RemoveLast().
90fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void RemoveLast();
91fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Clear();
92fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void MergeFrom(const RepeatedField& other);
93fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
94fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Reserve space to expand the field to at least the given size.  If the
95fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // array is grown, it will always be at least doubled in size.
96fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Reserve(int new_size);
97fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
98d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // Resize the RepeatedField to a new, smaller size.  This is O(1).
99d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  void Truncate(int new_size);
100d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
101d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  void AddAlreadyReserved(const Element& value);
102d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  Element* AddAlreadyReserved();
103d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  int Capacity() const;
104d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
105fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Gets the underlying array.  This pointer is possibly invalidated by
106fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // any add or remove operation.
107fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* mutable_data();
108fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const Element* data() const;
109fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
110fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Swap entire contents with "other".
111fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Swap(RepeatedField* other);
112fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
113fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Swap two elements.
114fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void SwapElements(int index1, int index2);
115fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
116fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // STL-like iterator support
117fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typedef Element* iterator;
118fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typedef const Element* const_iterator;
119fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
120fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  iterator begin();
121fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const_iterator begin() const;
122fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  iterator end();
123fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const_iterator end() const;
124fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
125fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Returns the number of bytes used by the repeated field, excluding
126fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // sizeof(*this)
127fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int SpaceUsedExcludingSelf() const;
128fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
129fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville private:
130fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedField);
131fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
132fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static const int kInitialSize = 4;
133fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
134fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* elements_;
135fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int      current_size_;
136fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int      total_size_;
137fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
138fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element  initial_space_[kInitialSize];
139d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
140d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // Move the contents of |from| into |to|, possibly clobbering |from| in the
141d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // process.  For primitive types this is just a memcpy(), but it could be
142d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // specialized for non-primitive types to, say, swap each element instead.
143d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  void MoveArray(Element to[], Element from[], int size);
144d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
145d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // Copy the elements of |from| into |to|.
146d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  void CopyArray(Element to[], const Element from[], int size);
147fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville};
148fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
149fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillenamespace internal {
150fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename It> class RepeatedPtrIterator;
151d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate <typename It> class RepeatedPtrOverPtrsIterator;
152fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}  // namespace internal
153fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
154fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillenamespace internal {
155fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
156fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// This is the common base class for RepeatedPtrFields.  It deals only in void*
157fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// pointers.  Users should not use this interface directly.
158fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//
159fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// The methods of this interface correspond to the methods of RepeatedPtrField,
160fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// but may have a template argument called TypeHandler.  Its signature is:
161fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   class TypeHandler {
162fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//    public:
163fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     typedef MyType Type;
164fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     static Type* New();
165fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     static void Delete(Type*);
166fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     static void Clear(Type*);
167fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     static void Merge(const Type& from, Type* to);
168fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//
169fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     // Only needs to be implemented if SpaceUsedExcludingSelf() is called.
170fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//     static int SpaceUsed(const Type&);
171fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   };
172fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass LIBPROTOBUF_EXPORT RepeatedPtrFieldBase {
173fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville protected:
174fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // The reflection implementation needs to call protected methods directly,
175fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // reinterpreting pointers as being to Message instead of a specific Message
176fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // subclass.
177fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  friend class GeneratedMessageReflection;
178fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
179fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // ExtensionSet stores repeated message extensions as
180fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to
181fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // implement SpaceUsed(), and thus need to call SpaceUsedExcludingSelf()
182fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // reinterpreting MessageLite as Message.  ExtensionSet also needs to make
183fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // use of AddFromCleared(), which is not part of the public interface.
184fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  friend class ExtensionSet;
185fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
186fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedPtrFieldBase();
187fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
188fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Must be called from destructor.
189fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
190fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Destroy();
191fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
192fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int size() const;
193fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
194fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
195fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const typename TypeHandler::Type& Get(int index) const;
196fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
197fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type* Mutable(int index);
198fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
199fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type* Add();
200fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
201fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void RemoveLast();
202fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
203fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Clear();
204fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
205fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void MergeFrom(const RepeatedPtrFieldBase& other);
206fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
207fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Reserve(int new_size);
208fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
209d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  int Capacity() const;
210d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
211fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Used for constructing iterators.
212fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void* const* raw_data() const;
213d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  void** raw_mutable_data() const;
214fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
215fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
216fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type** mutable_data();
217fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
218fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const typename TypeHandler::Type* const* data() const;
219fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
220fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Swap(RepeatedPtrFieldBase* other);
221fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
222fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void SwapElements(int index1, int index2);
223fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
224fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
225fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int SpaceUsedExcludingSelf() const;
226fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
227d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
228fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Advanced memory management --------------------------------------
229fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
230fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Like Add(), but if there are no cleared objects to use, returns NULL.
231fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
232fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type* AddFromCleared();
233fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
234fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
235fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void AddAllocated(typename TypeHandler::Type* value);
236fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
237fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type* ReleaseLast();
238fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
239d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  int ClearedCount() const;
240fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
241fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void AddCleared(typename TypeHandler::Type* value);
242fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
243fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type* ReleaseCleared();
244fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
245fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville private:
246fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase);
247fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
248fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static const int kInitialSize = 4;
249fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
250fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void** elements_;
251fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int    current_size_;
252fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int    allocated_size_;
253fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int    total_size_;
254fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
255fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void*  initial_space_[kInitialSize];
256fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
257fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
258fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static inline typename TypeHandler::Type* cast(void* element) {
259fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    return reinterpret_cast<typename TypeHandler::Type*>(element);
260fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
261fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  template <typename TypeHandler>
262fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static inline const typename TypeHandler::Type* cast(const void* element) {
263fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    return reinterpret_cast<const typename TypeHandler::Type*>(element);
264fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
265fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville};
266fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
267fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename GenericType>
268fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass GenericTypeHandler {
269fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville public:
270fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typedef GenericType Type;
271fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static GenericType* New() { return new GenericType; }
272fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static void Delete(GenericType* value) { delete value; }
273fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static void Clear(GenericType* value) { value->Clear(); }
274fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static void Merge(const GenericType& from, GenericType* to) {
275fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    to->MergeFrom(from);
276fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
277fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); }
278fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville};
279fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
280fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <>
281fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void GenericTypeHandler<MessageLite>::Merge(
282fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    const MessageLite& from, MessageLite* to) {
283fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  to->CheckTypeAndMergeFrom(from);
284fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
285fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
286fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// HACK:  If a class is declared as DLL-exported in MSVC, it insists on
287fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   generating copies of all its methods -- even inline ones -- to include
288fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   in the DLL.  But SpaceUsed() calls StringSpaceUsedExcludingSelf() which
289fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   isn't in the lite library, therefore the lite library cannot link if
290fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   StringTypeHandler is exported.  So, we factor out StringTypeHandlerBase,
291fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   export that, then make StringTypeHandler be a subclass which is NOT
292fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville//   exported.
293fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// TODO(kenton):  There has to be a better way.
294fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass LIBPROTOBUF_EXPORT StringTypeHandlerBase {
295fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville public:
296fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typedef string Type;
297fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static string* New();
298fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static void Delete(string* value);
299fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static void Clear(string* value) { value->clear(); }
300fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static void Merge(const string& from, string* to) { *to = from; }
301fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville};
302fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
303fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass StringTypeHandler : public StringTypeHandlerBase {
304fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville public:
305fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  static int SpaceUsed(const string& value)  {
306fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    return sizeof(value) + StringSpaceUsedExcludingSelf(value);
307fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
308fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville};
309fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
310d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
311fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}  // namespace internal
312fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
313fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// RepeatedPtrField is like RepeatedField, but used for repeated strings or
314fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// Messages.
315fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
316fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass RepeatedPtrField : public internal::RepeatedPtrFieldBase {
317fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville public:
318fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedPtrField();
319fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
320fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  ~RepeatedPtrField();
321fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
322fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int size() const;
323fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
324fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const Element& Get(int index) const;
325fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* Mutable(int index);
326fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* Add();
327fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void RemoveLast();  // Remove the last element in the array.
328fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Clear();
329fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void MergeFrom(const RepeatedPtrField& other);
330fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
331fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Reserve space to expand the field to at least the given size.  This only
332fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // resizes the pointer array; it doesn't allocate any objects.  If the
333fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // array is grown, it will always be at least doubled in size.
334fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Reserve(int new_size);
335fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
336d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  int Capacity() const;
337d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
338fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Gets the underlying array.  This pointer is possibly invalidated by
339fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // any add or remove operation.
340fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element** mutable_data();
341fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const Element* const* data() const;
342fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
343fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Swap entire contents with "other".
344fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void Swap(RepeatedPtrField* other);
345fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
346fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Swap two elements.
347fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void SwapElements(int index1, int index2);
348fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
349fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // STL-like iterator support
350fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typedef internal::RepeatedPtrIterator<Element> iterator;
351fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typedef internal::RepeatedPtrIterator<const Element> const_iterator;
352fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
353fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  iterator begin();
354fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const_iterator begin() const;
355fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  iterator end();
356fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  const_iterator end() const;
357fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
358d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // Custom STL-like iterator that iterates over and returns the underlying
359d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // pointers to Element rather than Element itself.
360d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  typedef internal::RepeatedPtrOverPtrsIterator<Element> pointer_iterator;
361d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  pointer_iterator pointer_begin();
362d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  pointer_iterator pointer_end();
363d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
364fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Returns (an estimate of) the number of bytes used by the repeated field,
365fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // excluding sizeof(*this).
366fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int SpaceUsedExcludingSelf() const;
367fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
368fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // The spaced used just by the pointer array, not counting the objects pointed
369fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // at.  Returns zero if the array is inlined (i.e. initial_space_ is being
370fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // used).
371fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int SpaceUsedByArray() const;
372fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
373fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Advanced memory management --------------------------------------
374fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // When hardcore memory management becomes necessary -- as it often
375fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // does here at Google -- the following methods may be useful.
376fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
377fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Add an already-allocated object, passing ownership to the
378fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // RepeatedPtrField.
379fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void AddAllocated(Element* value);
380fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Remove the last element and return it, passing ownership to the
381fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // caller.
382fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Requires:  size() > 0
383fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* ReleaseLast();
384fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
385fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // When elements are removed by calls to RemoveLast() or Clear(), they
386fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // are not actually freed.  Instead, they are cleared and kept so that
387fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // they can be reused later.  This can save lots of CPU time when
388fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // repeatedly reusing a protocol message for similar purposes.
389fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  //
390fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Really, extremely hardcore programs may actually want to manipulate
391fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // these objects to better-optimize memory management.  These methods
392fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // allow that.
393fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
394fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Get the number of cleared objects that are currently being kept
395fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // around for reuse.
396d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  int ClearedCount() const;
397fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Add an element to the pool of cleared objects, passing ownership to
398fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // the RepeatedPtrField.  The element must be cleared prior to calling
399fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // this method.
400fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  void AddCleared(Element* value);
401fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Remove a single element from the cleared pool and return it, passing
402fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // ownership to the caller.  The element is guaranteed to be cleared.
403fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // Requires:  ClearedCount() > 0
404fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* ReleaseCleared();
405fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
406d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville protected:
407d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // Note:  RepeatedPtrField SHOULD NOT be subclassed by users.  We only
408d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  //   subclass it in one place as a hack for compatibility with proto1.  The
409d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  //   subclass needs to know about TypeHandler in order to call protected
410d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  //   methods on RepeatedPtrFieldBase.
411fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  class TypeHandler;
412fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
413fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
414d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville private:
415d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrField);
416fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville};
417fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
418fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// implementation ====================================================
419fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
420fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
421fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline RepeatedField<Element>::RepeatedField()
422fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  : elements_(initial_space_),
423fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    current_size_(0),
424fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    total_size_(kInitialSize) {
425fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
426fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
427fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
428fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedField<Element>::~RepeatedField() {
429fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (elements_ != initial_space_) {
430fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    delete [] elements_;
431fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
432fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
433fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
434fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
435fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline int RepeatedField<Element>::size() const {
436fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return current_size_;
437fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
438fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
439d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate <typename Element>
440d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline int RepeatedField<Element>::Capacity() const {
441d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  return total_size_;
442d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
443d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
444d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate<typename Element>
445d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) {
446d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  GOOGLE_DCHECK_LT(size(), Capacity());
447d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  elements_[current_size_++] = value;
448d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
449d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
450d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate<typename Element>
451d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline Element* RepeatedField<Element>::AddAlreadyReserved() {
452d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  GOOGLE_DCHECK_LT(size(), Capacity());
453d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  return &elements_[current_size_++];
454d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
455fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
456fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
457d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline const Element& RepeatedField<Element>::Get(int index) const {
458fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_LT(index, size());
459fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_[index];
460fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
461fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
462fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
463fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline Element* RepeatedField<Element>::Mutable(int index) {
464fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_LT(index, size());
465fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_ + index;
466fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
467fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
468fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
469d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedField<Element>::Set(int index, const Element& value) {
470fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_LT(index, size());
471fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  elements_[index] = value;
472fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
473fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
474fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
475d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedField<Element>::Add(const Element& value) {
476fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (current_size_ == total_size_) Reserve(total_size_ + 1);
477fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  elements_[current_size_++] = value;
478fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
479fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
480fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
481d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline Element* RepeatedField<Element>::Add() {
482d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  if (current_size_ == total_size_) Reserve(total_size_ + 1);
483d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  return &elements_[current_size_++];
484d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
485d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
486d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate <typename Element>
487fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedField<Element>::RemoveLast() {
488fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_GT(current_size_, 0);
489fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  --current_size_;
490fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
491fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
492fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
493fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedField<Element>::Clear() {
494fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  current_size_ = 0;
495fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
496fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
497fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
498d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) {
499fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Reserve(current_size_ + other.current_size_);
500d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  CopyArray(elements_ + current_size_, other.elements_, other.current_size_);
501fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  current_size_ += other.current_size_;
502fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
503fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
504fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
505fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline Element* RepeatedField<Element>::mutable_data() {
506fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_;
507fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
508fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
509fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
510fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline const Element* RepeatedField<Element>::data() const {
511fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_;
512fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
513fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
514fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
515fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
516fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillevoid RepeatedField<Element>::Swap(RepeatedField* other) {
517fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* swap_elements     = elements_;
518fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int      swap_current_size = current_size_;
519fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int      swap_total_size   = total_size_;
520fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // We may not be using initial_space_ but it's not worth checking.  Just
521fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // copy it anyway.
522fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element swap_initial_space[kInitialSize];
523d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  MoveArray(swap_initial_space, initial_space_, kInitialSize);
524fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
525fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  elements_     = other->elements_;
526fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  current_size_ = other->current_size_;
527fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  total_size_   = other->total_size_;
528d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  MoveArray(initial_space_, other->initial_space_, kInitialSize);
529fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
530fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  other->elements_     = swap_elements;
531fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  other->current_size_ = swap_current_size;
532fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  other->total_size_   = swap_total_size;
533d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  MoveArray(other->initial_space_, swap_initial_space, kInitialSize);
534fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
535fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (elements_ == other->initial_space_) {
536fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    elements_ = initial_space_;
537fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
538fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (other->elements_ == initial_space_) {
539fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    other->elements_ = other->initial_space_;
540fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
541fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
542fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
543fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
544fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillevoid RepeatedField<Element>::SwapElements(int index1, int index2) {
545d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  std::swap(elements_[index1], elements_[index2]);
546fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
547fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
548fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
549fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename RepeatedField<Element>::iterator
550fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedField<Element>::begin() {
551fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_;
552fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
553fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
554fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename RepeatedField<Element>::const_iterator
555fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedField<Element>::begin() const {
556fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_;
557fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
558fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
559fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename RepeatedField<Element>::iterator
560fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedField<Element>::end() {
561fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_ + current_size_;
562fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
563fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
564fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename RepeatedField<Element>::const_iterator
565fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedField<Element>::end() const {
566fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_ + current_size_;
567fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
568fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
569fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
570fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline int RepeatedField<Element>::SpaceUsedExcludingSelf() const {
571fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0;
572fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
573fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
574d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville// Avoid inlining of Reserve(): new, memcpy, and delete[] lead to a significant
575d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville// amount of code bloat.
576fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
577d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savillevoid RepeatedField<Element>::Reserve(int new_size) {
578fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (total_size_ >= new_size) return;
579fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
580fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Element* old_elements = elements_;
581fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  total_size_ = max(total_size_ * 2, new_size);
582fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  elements_ = new Element[total_size_];
583d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  MoveArray(elements_, old_elements, current_size_);
584fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (old_elements != initial_space_) {
585fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    delete [] old_elements;
586fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
587fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
588fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
589d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate <typename Element>
590d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedField<Element>::Truncate(int new_size) {
591d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  GOOGLE_DCHECK_LE(new_size, current_size_);
592d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  current_size_ = new_size;
593d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
594d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
595d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate <typename Element>
596d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedField<Element>::MoveArray(
597d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    Element to[], Element from[], int size) {
598d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  memcpy(to, from, size * sizeof(Element));
599d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
600d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
601d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilletemplate <typename Element>
602d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedField<Element>::CopyArray(
603d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    Element to[], const Element from[], int size) {
604d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  memcpy(to, from, size * sizeof(Element));
605d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
606d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
607d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
608fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// -------------------------------------------------------------------
609fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
610fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillenamespace internal {
611fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
612fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline RepeatedPtrFieldBase::RepeatedPtrFieldBase()
613fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  : elements_(initial_space_),
614fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    current_size_(0),
615fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    allocated_size_(0),
616fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    total_size_(kInitialSize) {
617fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
618fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
619fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
620fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillevoid RepeatedPtrFieldBase::Destroy() {
621fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  for (int i = 0; i < allocated_size_; i++) {
622fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    TypeHandler::Delete(cast<TypeHandler>(elements_[i]));
623fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
624fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (elements_ != initial_space_) {
625fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    delete [] elements_;
626fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
627fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
628fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
629fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline int RepeatedPtrFieldBase::size() const {
630fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return current_size_;
631fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
632fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
633fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
634fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
635fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline const typename TypeHandler::Type&
636fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedPtrFieldBase::Get(int index) const {
637fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_LT(index, size());
638fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return *cast<TypeHandler>(elements_[index]);
639fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
640fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
641fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
642fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename TypeHandler::Type*
643fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedPtrFieldBase::Mutable(int index) {
644fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_LT(index, size());
645fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return cast<TypeHandler>(elements_[index]);
646fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
647fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
648fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
649fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() {
650fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (current_size_ < allocated_size_) {
651fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    return cast<TypeHandler>(elements_[current_size_++]);
652fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
653fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
654fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  ++allocated_size_;
655fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type* result = TypeHandler::New();
656fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  elements_[current_size_++] = result;
657fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return result;
658fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
659fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
660fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
661fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedPtrFieldBase::RemoveLast() {
662fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_GT(current_size_, 0);
663fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_]));
664fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
665fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
666fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
667fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillevoid RepeatedPtrFieldBase::Clear() {
668fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  for (int i = 0; i < current_size_; i++) {
669fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    TypeHandler::Clear(cast<TypeHandler>(elements_[i]));
670fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
671fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  current_size_ = 0;
672fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
673fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
674fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
675d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) {
676fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Reserve(current_size_ + other.current_size_);
677fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  for (int i = 0; i < other.current_size_; i++) {
678fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    TypeHandler::Merge(other.Get<TypeHandler>(i), Add<TypeHandler>());
679fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
680fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
681fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
682d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline int RepeatedPtrFieldBase::Capacity() const {
683d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  return total_size_;
684d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
685d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
686fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void* const* RepeatedPtrFieldBase::raw_data() const {
687fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return elements_;
688fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
689fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
690d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline void** RepeatedPtrFieldBase::raw_mutable_data() const {
691d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  return elements_;
692d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville}
693d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
694fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
695fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() {
696fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // TODO(kenton):  Breaks C++ aliasing rules.  We should probably remove this
697fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  //   method entirely.
698fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return reinterpret_cast<typename TypeHandler::Type**>(elements_);
699fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
700fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
701fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
702fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline const typename TypeHandler::Type* const*
703fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedPtrFieldBase::data() const {
704fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  // TODO(kenton):  Breaks C++ aliasing rules.  We should probably remove this
705fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  //   method entirely.
706fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return reinterpret_cast<const typename TypeHandler::Type* const*>(elements_);
707fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
708fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
709fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) {
710d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  std::swap(elements_[index1], elements_[index2]);
711fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
712fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
713fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
714fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const {
715fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  int allocated_bytes =
716fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville      (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0;
717fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  for (int i = 0; i < allocated_size_; ++i) {
718fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i]));
719fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
720fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return allocated_bytes;
721fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
722fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
723fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
724fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() {
725fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (current_size_ < allocated_size_) {
726fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    return cast<TypeHandler>(elements_[current_size_++]);
727fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  } else {
728fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    return NULL;
729fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
730fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
731fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
732fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
733d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savillevoid RepeatedPtrFieldBase::AddAllocated(
734fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    typename TypeHandler::Type* value) {
735d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  // Make room for the new pointer.
736d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  if (current_size_ == total_size_) {
737d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // The array is completely full with no cleared objects, so grow it.
738d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    Reserve(total_size_ + 1);
739d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    ++allocated_size_;
740d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  } else if (allocated_size_ == total_size_) {
741d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // There is no more space in the pointer array because it contains some
742d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // cleared objects awaiting reuse.  We don't want to grow the array in this
743d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // case because otherwise a loop calling AddAllocated() followed by Clear()
744d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // would leak memory.
745d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    TypeHandler::Delete(cast<TypeHandler>(elements_[current_size_]));
746d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  } else if (current_size_ < allocated_size_) {
747d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // We have some cleared objects.  We don't care about their order, so we
748d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // can just move the first one to the end to make space.
749fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    elements_[allocated_size_] = elements_[current_size_];
750d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    ++allocated_size_;
751d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville  } else {
752d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    // There are no cleared objects.
753d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville    ++allocated_size_;
754fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
755d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Saville
756fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  elements_[current_size_++] = value;
757fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
758fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
759fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
760fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() {
761fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_GT(current_size_, 0);
762fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  typename TypeHandler::Type* result =
763fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville      cast<TypeHandler>(elements_[--current_size_]);
764fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  --allocated_size_;
765fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (current_size_ < allocated_size_) {
766fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    // There are cleared elements on the end; replace the removed element
767fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    // with the last allocated element.
768fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    elements_[current_size_] = elements_[allocated_size_];
769fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  }
770fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return result;
771fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
772fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
773fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
774d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline int RepeatedPtrFieldBase::ClearedCount() const {
775fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return allocated_size_ - current_size_;
776fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
777fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
778fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
779fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedPtrFieldBase::AddCleared(
780fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    typename TypeHandler::Type* value) {
781fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
782fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  elements_[allocated_size_++] = value;
783fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
784fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
785fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename TypeHandler>
786fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() {
787fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  GOOGLE_DCHECK_GT(allocated_size_, current_size_);
788fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return cast<TypeHandler>(elements_[--allocated_size_]);
789fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
790fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
791fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}  // namespace internal
792fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
793fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville// -------------------------------------------------------------------
794fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
795fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
796fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass RepeatedPtrField<Element>::TypeHandler
797fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    : public internal::GenericTypeHandler<Element> {};
798fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
799fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <>
800fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleclass RepeatedPtrField<string>::TypeHandler
801fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    : public internal::StringTypeHandler {};
802fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
803fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
804fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
805d0332953cda33fb4f8e24ebff9c49159b69c43d6Wink Savilleinline RepeatedPtrField<Element>::RepeatedPtrField() {}
806fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
807fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
808fbaaef999ba563838ebd00874ed8a1c01fbf286dWink SavilleRepeatedPtrField<Element>::~RepeatedPtrField() {
809fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  Destroy<TypeHandler>();
810fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
811fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
812fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
813fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline int RepeatedPtrField<Element>::size() const {
814fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return RepeatedPtrFieldBase::size();
815fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
816fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
817fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
818fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline const Element& RepeatedPtrField<Element>::Get(int index) const {
819fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return RepeatedPtrFieldBase::Get<TypeHandler>(index);
820fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
821fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
822fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
823fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline Element* RepeatedPtrField<Element>::Mutable(int index) {
824fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return RepeatedPtrFieldBase::Mutable<TypeHandler>(index);
825fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
826fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
827fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
828fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline Element* RepeatedPtrField<Element>::Add() {
829fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return RepeatedPtrFieldBase::Add<TypeHandler>();
830fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
831fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
832fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
833fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedPtrField<Element>::RemoveLast() {
834fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedPtrFieldBase::RemoveLast<TypeHandler>();
835fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
836fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
837fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
838fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedPtrField<Element>::Clear() {
839fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedPtrFieldBase::Clear<TypeHandler>();
840fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
841fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
842fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
843fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline void RepeatedPtrField<Element>::MergeFrom(
844fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville    const RepeatedPtrField& other) {
845fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
846fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
847fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
848fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
849fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline Element** RepeatedPtrField<Element>::mutable_data() {
850fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return RepeatedPtrFieldBase::mutable_data<TypeHandler>();
851fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
852fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
853fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
854fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilleinline const Element* const* RepeatedPtrField<Element>::data() const {
855fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  return RepeatedPtrFieldBase::data<TypeHandler>();
856fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
857fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
858fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
859fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillevoid RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) {
860fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedPtrFieldBase::Swap(other);
861fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
862fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
863fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
864fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savillevoid RepeatedPtrField<Element>::SwapElements(int index1, int index2) {
865fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville  RepeatedPtrFieldBase::SwapElements(index1, index2);
866fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville}
867fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Saville
868fbaaef999ba563838ebd00874ed8a1c01fbf286dWink Savilletemplate <typename Element>
869fbaaef999ba563838ebd00874e