repeated_field.h revision 5d1f7b1de12d16ceb2c938c56701a3e8bfa558f7
158537e28ecd584eab876aee8be7156509866d23aTorne (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)// 558537e28ecd584eab876aee8be7156509866d23aTorne (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 77dbb3d5cf0c15f500944d211057644d6a2f37371Ben Murdoch// met: 890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// 990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// * Redistributions of source code must retain the above copyright 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 11eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// * Redistributions in binary form must reproduce the above 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 13c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// in the documentation and/or other materials provided with the 14a93a17c8d99d686bd4a1511e5504e5e6cc9fcadfTorne (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 177d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// this software without specific prior written permission. 1890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// 1958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (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 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 237d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 3190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// Author: kenton@google.com (Kenton Varda) 3290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// Based on original Protocol Buffers design by 3390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// Sanjay Ghemawat, Jeff Dean, and others. 3490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// 3590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// RepeatedField and RepeatedPtrField are used by generated protocol message 3690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// classes to manipulate repeated fields. These classes are very similar to 3790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// STL's vector, but include a number of optimizations found to be useful 387d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// specifically in the case of Protocol Buffers. RepeatedPtrField is 3958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// particularly different from STL vector as it manages ownership of the 407d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// pointers that it contains. 417d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// 427d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// Typically, clients should not need to access RepeatedField objects directly, 437d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// but should instead use the accessor functions generated automatically by the 4458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// protocol compiler. 4558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 4658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__ 4758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__ 4890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 4990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include <algorithm> 5090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include <string> 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <iterator> 5258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#include <google/protobuf/stubs/common.h> 5358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#include <google/protobuf/stubs/type_traits.h> 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <google/protobuf/generated_message_util.h> 5558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)#include <google/protobuf/message_lite.h> 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)namespace google { 5858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)namespace upb { 6058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)namespace google_opensource { 612a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class GMR_Handlers; 6258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)} // namespace google_opensource 6358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)} // namespace upb 6458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 6558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)namespace protobuf { 6658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 672a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)class Message; 6858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace internal { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)static const int kMinRepeatedFieldAllocationSize = 4; 7258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 7358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// A utility function for logging that doesn't need any template types. 7458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)void LogIndexOutOfBounds(int index, int size); 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace internal 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 7858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// RepeatedField is used to represent repeated fields of a primitive type (in 7958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// other words, everything except strings and nested Messages). Most users will 8058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// not ever use a RepeatedField directly; they will use the get-by-index, 8158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// set-by-index, and add accessors that are generated for all repeated fields. 8258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)template <typename Element> 8358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)class RepeatedField { 8458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) public: 8558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) RepeatedField(); 8658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) RepeatedField(const RepeatedField& other); 8758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) template <typename Iter> 8858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) RepeatedField(Iter begin, const Iter& end); 8958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) ~RepeatedField(); 9058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RepeatedField& operator=(const RepeatedField& other); 9258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 9358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) int size() const; 9458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 9558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) const Element& Get(int index) const; 9658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) Element* Mutable(int index); 977d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void Set(int index, const Element& value); 987d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void Add(const Element& value); 99c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Element* Add(); 100c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Remove the last element in the array. 1017d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void RemoveLast(); 10258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 1037d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Extract elements with indices in "[start .. start+num-1]". 1047d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Copy them into "elements[0 .. num-1]" if "elements" is not NULL. 1057d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Caution: implementation also moves elements with indices [start+num ..]. 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Calling this routine inside a loop can cause quadratic behavior. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void ExtractSubrange(int start, int num, Element* elements); 10858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 10958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) void Clear(); 11058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) void MergeFrom(const RepeatedField& other); 111c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) void CopyFrom(const RepeatedField& other); 1127d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 1137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Reserve space to expand the field to at least the given size. If the 1147d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // array is grown, it will always be at least doubled in size. 11558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) void Reserve(int new_size); 1167d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 1177d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Resize the RepeatedField to a new, smaller size. This is O(1). 1187d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void Truncate(int new_size); 11958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 1207d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void AddAlreadyReserved(const Element& value); 1217d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) Element* AddAlreadyReserved(); 1227d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) int Capacity() const; 1237d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 1247d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Gets the underlying array. This pointer is possibly invalidated by 1257d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // any add or remove operation. 1267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) Element* mutable_data(); 1277d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) const Element* data() const; 12858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 12958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // Swap entire contents with "other". 13058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) void Swap(RepeatedField* other); 1317d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 1327d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Swap two elements. 1337d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void SwapElements(int index1, int index2); 134c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 135c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // STL-like iterator support 13658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef Element* iterator; 1377d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typedef const Element* const_iterator; 1387d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typedef Element value_type; 139c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) typedef value_type& reference; 14058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef const value_type& const_reference; 141c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) typedef value_type* pointer; 14258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef const value_type* const_pointer; 143c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) typedef int size_type; 14458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef ptrdiff_t difference_type; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iterator begin(); 1477d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) const_iterator begin() const; 14858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) iterator end(); 1497d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) const_iterator end() const; 15058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 1517d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Reverse iterator support 15258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1537d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typedef std::reverse_iterator<iterator> reverse_iterator; 1547d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) reverse_iterator rbegin() { 1557d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) return reverse_iterator(end()); 1567d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) } 1577d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) const_reverse_iterator rbegin() const { 1587d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) return const_reverse_iterator(end()); 15958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reverse_iterator rend() { 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return reverse_iterator(begin()); 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 16358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) const_reverse_iterator rend() const { 16490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return const_reverse_iterator(begin()); 16590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 16690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 16790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Returns the number of bytes used by the repeated field, excluding 16890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // sizeof(*this) 16990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) int SpaceUsedExcludingSelf() const; 17090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 1717d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) private: 1727d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) static const int kInitialSize = 0; 1737d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 17490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Element* elements_; 17590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) int current_size_; 17690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) int total_size_; 17790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 17890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Move the contents of |from| into |to|, possibly clobbering |from| in the 1797d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // process. For primitive types this is just a memcpy(), but it could be 1807d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // specialized for non-primitive types to, say, swap each element instead. 1817d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void MoveArray(Element to[], Element from[], int size); 1827d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 18390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Copy the elements of |from| into |to|. 1847d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void CopyArray(Element to[], const Element from[], int size); 1857d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)}; 18658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 18790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)namespace internal { 1887d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)template <typename It> class RepeatedPtrIterator; 1897d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)template <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator; 19090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} // namespace internal 1917d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 1927d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)namespace internal { 1937d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 1947d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// This is a helper template to copy an array of elements effeciently when they 1957d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// have a trivial copy constructor, and correctly otherwise. This really 19658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// shouldn't be necessary, but our compiler doesn't optimize std::copy very 1977d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// effectively. 1987d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)template <typename Element, 1997d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) bool HasTrivialCopy = has_trivial_copy<Element>::value> 2007d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct ElementCopier { 2017d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void operator()(Element to[], const Element from[], int array_size); 20290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)}; 2037d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 20490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} // namespace internal 20590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 2067d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)namespace internal { 2077d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 2087d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// This is the common base class for RepeatedPtrFields. It deals only in void* 2097d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// pointers. Users should not use this interface directly. 2107d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// 2117d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// The methods of this interface correspond to the methods of RepeatedPtrField, 2127d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// but may have a template argument called TypeHandler. Its signature is: 2137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// class TypeHandler { 21490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// public: 21590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// typedef MyType Type; 21690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// static Type* New(); 21758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// static void Delete(Type*); 21890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// static void Clear(Type*); 21990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// static void Merge(const Type& from, Type* to); 22090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// 22190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// // Only needs to be implemented if SpaceUsedExcludingSelf() is called. 22290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// static int SpaceUsed(const Type&); 22358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// }; 22458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { 22590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) protected: 22690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // The reflection implementation needs to call protected methods directly, 2277d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // reinterpreting pointers as being to Message instead of a specific Message 2287d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // subclass. 22958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) friend class GeneratedMessageReflection; 23090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 2317d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // ExtensionSet stores repeated message extensions as 2327d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to 2337d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // implement SpaceUsed(), and thus need to call SpaceUsedExcludingSelf() 2347d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // reinterpreting MessageLite as Message. ExtensionSet also needs to make 2357d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // use of AddFromCleared(), which is not part of the public interface. 23658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) friend class ExtensionSet; 23758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 2387d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // To parse directly into a proto2 generated class, the upb class GMR_Handlers 2397d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // needs to be able to modify a RepeatedPtrFieldBase directly. 2407d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) friend class LIBPROTOBUF_EXPORT upb::google_opensource::GMR_Handlers; 24190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 24290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) RepeatedPtrFieldBase(); 24390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 24458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // Must be called from destructor. 24590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) template <typename TypeHandler> 24690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void Destroy(); 24790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 24890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) int size() const; 24990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 25090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) template <typename TypeHandler> 25190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) const typename TypeHandler::Type& Get(int index) const; 25290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) template <typename TypeHandler> 2537d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typename TypeHandler::Type* Mutable(int index); 2547d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 25590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) typename TypeHandler::Type* Add(); 25690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) template <typename TypeHandler> 25790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void RemoveLast(); 2587d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 2597d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void Clear(); 26090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) template <typename TypeHandler> 2617d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void MergeFrom(const RepeatedPtrFieldBase& other); 26290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) template <typename TypeHandler> 26390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void CopyFrom(const RepeatedPtrFieldBase& other); 2647d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 26590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void CloseGap(int start, int num) { 2667d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Close up a gap of "num" elements starting at offset "start". 26790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (int i = start + num; i < allocated_size_; ++i) 26890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) elements_[i - num] = elements_[i]; 26990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) current_size_ -= num; 2707d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) allocated_size_ -= num; 2717d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) } 2727d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 27390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void Reserve(int new_size); 27490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 27590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) int Capacity() const; 27690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 27790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Used for constructing iterators. 27890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void* const* raw_data() const; 27990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void** raw_mutable_data() const; 28090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 2817d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 2827d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typename TypeHandler::Type** mutable_data(); 28358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) template <typename TypeHandler> 2847d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) const typename TypeHandler::Type* const* data() const; 2857d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 28690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void Swap(RepeatedPtrFieldBase* other); 28790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 28890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) void SwapElements(int index1, int index2); 28958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 29058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) template <typename TypeHandler> 29158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) int SpaceUsedExcludingSelf() const; 29258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 29358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 29458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // Advanced memory management -------------------------------------- 2957d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 2967d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Like Add(), but if there are no cleared objects to use, returns NULL. 29758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) template <typename TypeHandler> 2987d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typename TypeHandler::Type* AddFromCleared(); 299c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 3007d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 3017d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void AddAllocated(typename TypeHandler::Type* value); 3027d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 3037d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typename TypeHandler::Type* ReleaseLast(); 3047d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3057d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) int ClearedCount() const; 3067d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 3077d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) void AddCleared(typename TypeHandler::Type* value); 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) template <typename TypeHandler> 3097d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typename TypeHandler::Type* ReleaseCleared(); 3107d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3117d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) private: 31258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase); 3137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3147d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) static const int kInitialSize = 0; 3157d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 31658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) void** elements_; 3177d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) int current_size_; 3187d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) int allocated_size_; 3197d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) int total_size_; 32058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 3217d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 3227d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) static inline typename TypeHandler::Type* cast(void* element) { 3237d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) return reinterpret_cast<typename TypeHandler::Type*>(element); 32458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) } 3257d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) template <typename TypeHandler> 3267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) static inline const typename TypeHandler::Type* cast(const void* element) { 3277d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) return reinterpret_cast<const typename TypeHandler::Type*>(element); 3287d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) } 3297d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)}; 3307d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3317d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)template <typename GenericType> 332c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)class GenericTypeHandler { 3337d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) public: 3347d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typedef GenericType Type; 3357d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) static GenericType* New() { return new GenericType; } 3367d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) static void Delete(GenericType* value) { delete value; } 3377d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) static void Clear(GenericType* value) { value->Clear(); } 3387d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (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(); } 34258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) static const Type& default_instance() { return Type::default_instance(); } 34358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)}; 34458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 34558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)template <> 34658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)inline void GenericTypeHandler<MessageLite>::Merge( 34758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) const MessageLite& from, MessageLite* to) { 3487d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) to->CheckTypeAndMergeFrom(from); 3497d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)} 3507d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3517d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)template <> 35258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)inline const MessageLite& GenericTypeHandler<MessageLite>::default_instance() { 3537d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Yes, the behavior of the code is undefined, but this function is only 3547d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // called when we're already deep into the world of undefined, because the 35558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // caller called Get(index) out of bounds. 3567d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) MessageLite* null = NULL; 3577d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) return *null; 3587d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)} 3597d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3607d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)template <> 36158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)inline const Message& GenericTypeHandler<Message>::default_instance() { 3627d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // Yes, the behavior of the code is undefined, but this function is only 3637d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) // called when we're already deep into the world of undefined, because the 36458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) // caller called Get(index) out of bounds. 365c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Message* null = NULL; 36658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) return *null; 36758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)} 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 37058537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// HACK: If a class is declared as DLL-exported in MSVC, it insists on 37158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// generating copies of all its methods -- even inline ones -- to include 37258537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// in the DLL. But SpaceUsed() calls StringSpaceUsedExcludingSelf() which 37358537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// isn't in the lite library, therefore the lite library cannot link if 37458537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// StringTypeHandler is exported. So, we factor out StringTypeHandlerBase, 37558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// export that, then make StringTypeHandler be a subclass which is NOT 37658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// exported. 37758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)// TODO(kenton): There has to be a better way. 37858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)class LIBPROTOBUF_EXPORT StringTypeHandlerBase { 37958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) public: 380 typedef string Type; 381 static string* New(); 382 static void Delete(string* value); 383 static void Clear(string* value) { value->clear(); } 384 static void Merge(const string& from, string* to) { *to = from; } 385 static const Type& default_instance() { 386 return ::google::protobuf::internal::GetEmptyString(); 387 } 388}; 389 390class StringTypeHandler : public StringTypeHandlerBase { 391 public: 392 static int SpaceUsed(const string& value) { 393 return sizeof(value) + StringSpaceUsedExcludingSelf(value); 394 } 395}; 396 397 398} // namespace internal 399 400// RepeatedPtrField is like RepeatedField, but used for repeated strings or 401// Messages. 402template <typename Element> 403class RepeatedPtrField : public internal::RepeatedPtrFieldBase { 404 public: 405 RepeatedPtrField(); 406 RepeatedPtrField(const RepeatedPtrField& other); 407 template <typename Iter> 408 RepeatedPtrField(Iter begin, const Iter& end); 409 ~RepeatedPtrField(); 410 411 RepeatedPtrField& operator=(const RepeatedPtrField& other); 412 413 int size() const; 414 415 const Element& Get(int index) const; 416 Element* Mutable(int index); 417 Element* Add(); 418 419 // Remove the last element in the array. 420 // Ownership of the element is retained by the array. 421 void RemoveLast(); 422 423 // Delete elements with indices in the range [start .. start+num-1]. 424 // Caution: implementation moves all elements with indices [start+num .. ]. 425 // Calling this routine inside a loop can cause quadratic behavior. 426 void DeleteSubrange(int start, int num); 427 428 void Clear(); 429 void MergeFrom(const RepeatedPtrField& other); 430 void CopyFrom(const RepeatedPtrField& other); 431 432 // Reserve space to expand the field to at least the given size. This only 433 // resizes the pointer array; it doesn't allocate any objects. If the 434 // array is grown, it will always be at least doubled in size. 435 void Reserve(int new_size); 436 437 int Capacity() const; 438 439 // Gets the underlying array. This pointer is possibly invalidated by 440 // any add or remove operation. 441 Element** mutable_data(); 442 const Element* const* data() const; 443 444 // Swap entire contents with "other". 445 void Swap(RepeatedPtrField* other); 446 447 // Swap two elements. 448 void SwapElements(int index1, int index2); 449 450 // STL-like iterator support 451 typedef internal::RepeatedPtrIterator<Element> iterator; 452 typedef internal::RepeatedPtrIterator<const Element> const_iterator; 453 typedef Element value_type; 454 typedef value_type& reference; 455 typedef const value_type& const_reference; 456 typedef value_type* pointer; 457 typedef const value_type* const_pointer; 458 typedef int size_type; 459 typedef ptrdiff_t difference_type; 460 461 iterator begin(); 462 const_iterator begin() const; 463 iterator end(); 464 const_iterator end() const; 465 466 // Reverse iterator support 467 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 468 typedef std::reverse_iterator<iterator> reverse_iterator; 469 reverse_iterator rbegin() { 470 return reverse_iterator(end()); 471 } 472 const_reverse_iterator rbegin() const { 473 return const_reverse_iterator(end()); 474 } 475 reverse_iterator rend() { 476 return reverse_iterator(begin()); 477 } 478 const_reverse_iterator rend() const { 479 return const_reverse_iterator(begin()); 480 } 481 482 // Custom STL-like iterator that iterates over and returns the underlying 483 // pointers to Element rather than Element itself. 484 typedef internal::RepeatedPtrOverPtrsIterator<Element, void*> 485 pointer_iterator; 486 typedef internal::RepeatedPtrOverPtrsIterator<const Element, const void*> 487 const_pointer_iterator; 488 pointer_iterator pointer_begin(); 489 const_pointer_iterator pointer_begin() const; 490 pointer_iterator pointer_end(); 491 const_pointer_iterator pointer_end() const; 492 493 // Returns (an estimate of) the number of bytes used by the repeated field, 494 // excluding sizeof(*this). 495 int SpaceUsedExcludingSelf() const; 496 497 // Advanced memory management -------------------------------------- 498 // When hardcore memory management becomes necessary -- as it sometimes 499 // does here at Google -- the following methods may be useful. 500 501 // Add an already-allocated object, passing ownership to the 502 // RepeatedPtrField. 503 void AddAllocated(Element* value); 504 // Remove the last element and return it, passing ownership to the caller. 505 // Requires: size() > 0 506 Element* ReleaseLast(); 507 508 // Extract elements with indices in the range "[start .. start+num-1]". 509 // The caller assumes ownership of the extracted elements and is responsible 510 // for deleting them when they are no longer needed. 511 // If "elements" is non-NULL, then pointers to the extracted elements 512 // are stored in "elements[0 .. num-1]" for the convenience of the caller. 513 // If "elements" is NULL, then the caller must use some other mechanism 514 // to perform any further operations (like deletion) on these elements. 515 // Caution: implementation also moves elements with indices [start+num ..]. 516 // Calling this routine inside a loop can cause quadratic behavior. 517 void ExtractSubrange(int start, int num, Element** elements); 518 519 // When elements are removed by calls to RemoveLast() or Clear(), they 520 // are not actually freed. Instead, they are cleared and kept so that 521 // they can be reused later. This can save lots of CPU time when 522 // repeatedly reusing a protocol message for similar purposes. 523 // 524 // Hardcore programs may choose to manipulate these cleared objects 525 // to better optimize memory management using the following routines. 526 527 // Get the number of cleared objects that are currently being kept 528 // around for reuse. 529 int ClearedCount() const; 530 // Add an element to the pool of cleared objects, passing ownership to 531 // the RepeatedPtrField. The element must be cleared prior to calling 532 // this method. 533 void AddCleared(Element* value); 534 // Remove a single element from the cleared pool and return it, passing 535 // ownership to the caller. The element is guaranteed to be cleared. 536 // Requires: ClearedCount() > 0 537 Element* ReleaseCleared(); 538 539 protected: 540 // Note: RepeatedPtrField SHOULD NOT be subclassed by users. We only 541 // subclass it in one place as a hack for compatibility with proto1. The 542 // subclass needs to know about TypeHandler in order to call protected 543 // methods on RepeatedPtrFieldBase. 544 class TypeHandler; 545 546}; 547 548// implementation ==================================================== 549 550template <typename Element> 551inline RepeatedField<Element>::RepeatedField() 552 : elements_(NULL), 553 current_size_(0), 554 total_size_(kInitialSize) { 555} 556 557template <typename Element> 558inline RepeatedField<Element>::RepeatedField(const RepeatedField& other) 559 : elements_(NULL), 560 current_size_(0), 561 total_size_(kInitialSize) { 562 CopyFrom(other); 563} 564 565template <typename Element> 566template <typename Iter> 567inline RepeatedField<Element>::RepeatedField(Iter begin, const Iter& end) 568 : elements_(NULL), 569 current_size_(0), 570 total_size_(kInitialSize) { 571 for (; begin != end; ++begin) { 572 Add(*begin); 573 } 574} 575 576template <typename Element> 577RepeatedField<Element>::~RepeatedField() { 578 delete [] elements_; 579} 580 581template <typename Element> 582inline RepeatedField<Element>& 583RepeatedField<Element>::operator=(const RepeatedField& other) { 584 if (this != &other) 585 CopyFrom(other); 586 return *this; 587} 588 589template <typename Element> 590inline int RepeatedField<Element>::size() const { 591 return current_size_; 592} 593 594template <typename Element> 595inline int RepeatedField<Element>::Capacity() const { 596 return total_size_; 597} 598 599template<typename Element> 600inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) { 601 GOOGLE_DCHECK_LT(size(), Capacity()); 602 elements_[current_size_++] = value; 603} 604 605template<typename Element> 606inline Element* RepeatedField<Element>::AddAlreadyReserved() { 607 GOOGLE_DCHECK_LT(size(), Capacity()); 608 return &elements_[current_size_++]; 609} 610 611template <typename Element> 612inline const Element& RepeatedField<Element>::Get(int index) const { 613 GOOGLE_DCHECK_LT(index, size()); 614 return elements_[index]; 615} 616 617template <typename Element> 618inline Element* RepeatedField<Element>::Mutable(int index) { 619 GOOGLE_DCHECK_LT(index, size()); 620 return elements_ + index; 621} 622 623template <typename Element> 624inline void RepeatedField<Element>::Set(int index, const Element& value) { 625 GOOGLE_DCHECK_LT(index, size()); 626 elements_[index] = value; 627} 628 629template <typename Element> 630inline void RepeatedField<Element>::Add(const Element& value) { 631 if (current_size_ == total_size_) Reserve(total_size_ + 1); 632 elements_[current_size_++] = value; 633} 634 635template <typename Element> 636inline Element* RepeatedField<Element>::Add() { 637 if (current_size_ == total_size_) Reserve(total_size_ + 1); 638 return &elements_[current_size_++]; 639} 640 641template <typename Element> 642inline void RepeatedField<Element>::RemoveLast() { 643 GOOGLE_DCHECK_GT(current_size_, 0); 644 --current_size_; 645} 646 647template <typename Element> 648void RepeatedField<Element>::ExtractSubrange( 649 int start, int num, Element* elements) { 650 GOOGLE_DCHECK_GE(start, 0); 651 GOOGLE_DCHECK_GE(num, 0); 652 GOOGLE_DCHECK_LE(start + num, this->size()); 653 654 // Save the values of the removed elements if requested. 655 if (elements != NULL) { 656 for (int i = 0; i < num; ++i) 657 elements[i] = this->Get(i + start); 658 } 659 660 // Slide remaining elements down to fill the gap. 661 if (num > 0) { 662 for (int i = start + num; i < this->size(); ++i) 663 this->Set(i - num, this->Get(i)); 664 this->Truncate(this->size() - num); 665 } 666} 667 668template <typename Element> 669inline void RepeatedField<Element>::Clear() { 670 current_size_ = 0; 671} 672 673template <typename Element> 674inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) { 675 if (other.current_size_ != 0) { 676 Reserve(current_size_ + other.current_size_); 677 CopyArray(elements_ + current_size_, other.elements_, other.current_size_); 678 current_size_ += other.current_size_; 679 } 680} 681 682template <typename Element> 683inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) { 684 Clear(); 685 MergeFrom(other); 686} 687 688template <typename Element> 689inline Element* RepeatedField<Element>::mutable_data() { 690 return elements_; 691} 692 693template <typename Element> 694inline const Element* RepeatedField<Element>::data() const { 695 return elements_; 696} 697 698 699template <typename Element> 700void RepeatedField<Element>::Swap(RepeatedField* other) { 701 if (this == other) return; 702 Element* swap_elements = elements_; 703 int swap_current_size = current_size_; 704 int swap_total_size = total_size_; 705 706 elements_ = other->elements_; 707 current_size_ = other->current_size_; 708 total_size_ = other->total_size_; 709 710 other->elements_ = swap_elements; 711 other->current_size_ = swap_current_size; 712 other->total_size_ = swap_total_size; 713} 714 715template <typename Element> 716void RepeatedField<Element>::SwapElements(int index1, int index2) { 717 std::swap(elements_[index1], elements_[index2]); 718} 719 720template <typename Element> 721inline typename RepeatedField<Element>::iterator 722RepeatedField<Element>::begin() { 723 return elements_; 724} 725template <typename Element> 726inline typename RepeatedField<Element>::const_iterator 727RepeatedField<Element>::begin() const { 728 return elements_; 729} 730template <typename Element> 731inline typename RepeatedField<Element>::iterator 732RepeatedField<Element>::end() { 733 return elements_ + current_size_; 734} 735template <typename Element> 736inline typename RepeatedField<Element>::const_iterator 737RepeatedField<Element>::end() const { 738 return elements_ + current_size_; 739} 740 741template <typename Element> 742inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const { 743 return (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0; 744} 745 746// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant 747// amount of code bloat. 748template <typename Element> 749void RepeatedField<Element>::Reserve(int new_size) { 750 if (total_size_ >= new_size) return; 751 752 Element* old_elements = elements_; 753 total_size_ = max(google::protobuf::internal::kMinRepeatedFieldAllocationSize, 754 max(total_size_ * 2, new_size)); 755 elements_ = new Element[total_size_]; 756 if (old_elements != NULL) { 757 MoveArray(elements_, old_elements, current_size_); 758 delete [] old_elements; 759 } 760} 761 762template <typename Element> 763inline void RepeatedField<Element>::Truncate(int new_size) { 764 GOOGLE_DCHECK_LE(new_size, current_size_); 765 current_size_ = new_size; 766} 767 768template <typename Element> 769inline void RepeatedField<Element>::MoveArray( 770 Element to[], Element from[], int array_size) { 771 CopyArray(to, from, array_size); 772} 773 774template <typename Element> 775inline void RepeatedField<Element>::CopyArray( 776 Element to[], const Element from[], int array_size) { 777 internal::ElementCopier<Element>()(to, from, array_size); 778} 779 780namespace internal { 781 782template <typename Element, bool HasTrivialCopy> 783void ElementCopier<Element, HasTrivialCopy>::operator()( 784 Element to[], const Element from[], int array_size) { 785 std::copy(from, from + array_size, to); 786} 787 788template <typename Element> 789struct ElementCopier<Element, true> { 790 void operator()(Element to[], const Element from[], int array_size) { 791 memcpy(to, from, array_size * sizeof(Element)); 792 } 793}; 794 795} // namespace internal 796 797 798// ------------------------------------------------------------------- 799 800namespace internal { 801 802inline RepeatedPtrFieldBase::RepeatedPtrFieldBase() 803 : elements_(NULL), 804 current_size_(0), 805 allocated_size_(0), 806 total_size_(kInitialSize) { 807} 808 809template <typename TypeHandler> 810void RepeatedPtrFieldBase::Destroy() { 811 for (int i = 0; i < allocated_size_; i++) { 812 TypeHandler::Delete(cast<TypeHandler>(elements_[i])); 813 } 814 delete [] elements_; 815} 816 817inline int RepeatedPtrFieldBase::size() const { 818 return current_size_; 819} 820 821template <typename TypeHandler> 822inline const typename TypeHandler::Type& 823RepeatedPtrFieldBase::Get(int index) const { 824 GOOGLE_DCHECK_LT(index, size()); 825 return *cast<TypeHandler>(elements_[index]); 826} 827 828 829template <typename TypeHandler> 830inline typename TypeHandler::Type* 831RepeatedPtrFieldBase::Mutable(int index) { 832 GOOGLE_DCHECK_LT(index, size()); 833 return cast<TypeHandler>(elements_[index]); 834} 835 836template <typename TypeHandler> 837inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() { 838 if (current_size_ < allocated_size_) { 839 return cast<TypeHandler>(elements_[current_size_++]); 840 } 841 if (allocated_size_ == total_size_) Reserve(total_size_ + 1); 842 ++allocated_size_; 843 typename TypeHandler::Type* result = TypeHandler::New(); 844 elements_[current_size_++] = result; 845 return result; 846} 847 848template <typename TypeHandler> 849inline void RepeatedPtrFieldBase::RemoveLast() { 850 GOOGLE_DCHECK_GT(current_size_, 0); 851 TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_])); 852} 853 854template <typename TypeHandler> 855void RepeatedPtrFieldBase::Clear() { 856 for (int i = 0; i < current_size_; i++) { 857 TypeHandler::Clear(cast<TypeHandler>(elements_[i])); 858 } 859 current_size_ = 0; 860} 861 862template <typename TypeHandler> 863inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) { 864 Reserve(current_size_ + other.current_size_); 865 for (int i = 0; i < other.current_size_; i++) { 866 TypeHandler::Merge(other.template Get<TypeHandler>(i), Add<TypeHandler>()); 867 } 868} 869 870template <typename TypeHandler> 871inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) { 872 RepeatedPtrFieldBase::Clear<TypeHandler>(); 873 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other); 874} 875 876inline int RepeatedPtrFieldBase::Capacity() const { 877 return total_size_; 878} 879 880inline void* const* RepeatedPtrFieldBase::raw_data() const { 881 return elements_; 882} 883 884inline void** RepeatedPtrFieldBase::raw_mutable_data() const { 885 return elements_; 886} 887 888template <typename TypeHandler> 889inline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() { 890 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this 891 // method entirely. 892 return reinterpret_cast<typename TypeHandler::Type**>(elements_); 893} 894 895template <typename TypeHandler> 896inline const typename TypeHandler::Type* const* 897RepeatedPtrFieldBase::data() const { 898 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this 899 // method entirely. 900 return reinterpret_cast<const typename TypeHandler::Type* const*>(elements_); 901} 902 903inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) { 904 std::swap(elements_[index1], elements_[index2]); 905} 906 907template <typename TypeHandler> 908inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const { 909 int allocated_bytes = 910 (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0; 911 for (int i = 0; i < allocated_size_; ++i) { 912 allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i])); 913 } 914 return allocated_bytes; 915} 916 917template <typename TypeHandler> 918inline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() { 919 if (current_size_ < allocated_size_) { 920 return cast<TypeHandler>(elements_[current_size_++]); 921 } else { 922 return NULL; 923 } 924} 925 926template <typename TypeHandler> 927void RepeatedPtrFieldBase::AddAllocated( 928 typename TypeHandler::Type* value) { 929 // Make room for the new pointer. 930 if (current_size_ == total_size_) { 931 // The array is completely full with no cleared objects, so grow it. 932 Reserve(total_size_ + 1); 933 ++allocated_size_; 934 } else if (allocated_size_ == total_size_) { 935 // There is no more space in the pointer array because it contains some 936 // cleared objects awaiting reuse. We don't want to grow the array in this 937 // case because otherwise a loop calling AddAllocated() followed by Clear() 938 // would leak memory. 939 TypeHandler::Delete(cast<TypeHandler>(elements_[current_size_])); 940 } else if (current_size_ < allocated_size_) { 941 // We have some cleared objects. We don't care about their order, so we 942 // can just move the first one to the end to make space. 943 elements_[allocated_size_] = elements_[current_size_]; 944 ++allocated_size_; 945 } else { 946 // There are no cleared objects. 947 ++allocated_size_; 948 } 949 950 elements_[current_size_++] = value; 951} 952 953template <typename TypeHandler> 954inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() { 955 GOOGLE_DCHECK_GT(current_size_, 0); 956 typename TypeHandler::Type* result = 957 cast<TypeHandler>(elements_[--current_size_]); 958 --allocated_size_; 959 if (current_size_ < allocated_size_) { 960 // There are cleared elements on the end; replace the removed element 961 // with the last allocated element. 962 elements_[current_size_] = elements_[allocated_size_]; 963 } 964 return result; 965} 966 967inline int RepeatedPtrFieldBase::ClearedCount() const { 968 return allocated_size_ - current_size_; 969} 970 971template <typename TypeHandler> 972inline void RepeatedPtrFieldBase::AddCleared( 973 typename TypeHandler::Type* value) { 974 if (allocated_size_ == total_size_) Reserve(total_size_ + 1); 975 elements_[allocated_size_++] = value; 976} 977 978template <typename TypeHandler> 979inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() { 980 GOOGLE_DCHECK_GT(allocated_size_, current_size_); 981 return cast<TypeHandler>(elements_[--allocated_size_]); 982} 983 984} // namespace internal 985 986// ------------------------------------------------------------------- 987 988template <typename Element> 989class RepeatedPtrField<Element>::TypeHandler 990 : public internal::GenericTypeHandler<Element> { 991}; 992 993template <> 994class RepeatedPtrField<string>::TypeHandler 995 : public internal::StringTypeHandler { 996}; 997 998 999template <typename Element> 1000inline RepeatedPtrField<Element>::RepeatedPtrField() {} 1001 1002template <typename Element> 1003inline RepeatedPtrField<Element>::RepeatedPtrField( 1004 const RepeatedPtrField& other) { 1005 CopyFrom(other); 1006} 1007 1008template <typename Element> 1009template <typename Iter> 1010inline RepeatedPtrField<Element>::RepeatedPtrField( 1011 Iter begin, const Iter& end) { 1012 for (; begin != end; ++begin) { 1013 *Add() = *begin; 1014 } 1015} 1016 1017template <typename Element> 1018RepeatedPtrField<Element>::~RepeatedPtrField() { 1019 Destroy<TypeHandler>(); 1020} 1021 1022template <typename Element> 1023inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=( 1024 const RepeatedPtrField& other) { 1025 if (this != &other) 1026 CopyFrom(other); 1027 return *this; 1028} 1029 1030template <typename Element> 1031inline int RepeatedPtrField<Element>::size() const { 1032 return RepeatedPtrFieldBase::size(); 1033} 1034 1035template <typename Element> 1036inline const Element& RepeatedPtrField<Element>::Get(int index) const { 1037 return RepeatedPtrFieldBase::Get<TypeHandler>(index); 1038} 1039 1040 1041template <typename Element> 1042inline Element* RepeatedPtrField<Element>::Mutable(int index) { 1043 return RepeatedPtrFieldBase::Mutable<TypeHandler>(index); 1044} 1045 1046template <typename Element> 1047inline Element* RepeatedPtrField<Element>::Add() { 1048 return RepeatedPtrFieldBase::Add<TypeHandler>(); 1049} 1050 1051template <typename Element> 1052inline void RepeatedPtrField<Element>::RemoveLast() { 1053 RepeatedPtrFieldBase::RemoveLast<TypeHandler>(); 1054} 1055 1056template <typename Element> 1057inline void RepeatedPtrField<Element>::DeleteSubrange(int start, int num) { 1058 GOOGLE_DCHECK_GE(start, 0); 1059 GOOGLE_DCHECK_GE(num, 0); 1060 GOOGLE_DCHECK_LE(start + num, size()); 1061 for (int i = 0; i < num; ++i) 1062 delete RepeatedPtrFieldBase::Mutable<TypeHandler>(start + i); 1063 ExtractSubrange(start, num, NULL); 1064} 1065 1066template <typename Element> 1067inline void RepeatedPtrField<Element>::ExtractSubrange( 1068 int start, int num, Element** elements) { 1069 GOOGLE_DCHECK_GE(start, 0); 1070 GOOGLE_DCHECK_GE(num, 0); 1071 GOOGLE_DCHECK_LE(start + num, size()); 1072 1073 if (num > 0) { 1074 // Save the values of the removed elements if requested. 1075 if (elements != NULL) { 1076 for (int i = 0; i < num; ++i) 1077 elements[i] = RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start); 1078 } 1079 CloseGap(start, num); 1080 } 1081} 1082 1083template <typename Element> 1084inline void RepeatedPtrField<Element>::Clear() { 1085 RepeatedPtrFieldBase::Clear<TypeHandler>(); 1086} 1087 1088template <typename Element> 1089inline void RepeatedPtrField<Element>::MergeFrom( 1090 const RepeatedPtrField& other) { 1091 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other); 1092} 1093 1094template <typename Element> 1095inline void RepeatedPtrField<Element>::CopyFrom( 1096 const RepeatedPtrField& other) { 1097 RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other); 1098} 1099 1100template <typename Element> 1101inline Element** RepeatedPtrField<Element>::mutable_data() { 1102 return RepeatedPtrFieldBase::mutable_data<TypeHandler>(); 1103} 1104 1105template <typename Element> 1106inline const Element* const* RepeatedPtrField<Element>::data() const { 1107 return RepeatedPtrFieldBase::data<TypeHandler>(); 1108} 1109 1110template <typename Element> 1111void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) { 1112 RepeatedPtrFieldBase::Swap(other); 1113} 1114 1115template <typename Element> 1116void RepeatedPtrField<Element>::SwapElements(int index1, int index2) { 1117 RepeatedPtrFieldBase::SwapElements(index1, index2); 1118} 1119 1120template <typename Element> 1121inline int RepeatedPtrField<Element>::SpaceUsedExcludingSelf() const { 1122 return RepeatedPtrFieldBase::SpaceUsedExcludingSelf<TypeHandler>(); 1123} 1124 1125template <typename Element> 1126inline void RepeatedPtrField<Element>::AddAllocated(Element* value) { 1127 RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value); 1128} 1129 1130template <typename Element> 1131inline Element* RepeatedPtrField<Element>::ReleaseLast() { 1132 return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>(); 1133} 1134 1135 1136template <typename Element> 1137inline int RepeatedPtrField<Element>::ClearedCount() const { 1138 return RepeatedPtrFieldBase::ClearedCount(); 1139} 1140 1141template <typename Element> 1142inline void RepeatedPtrField<Element>::AddCleared(Element* value) { 1143 return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value); 1144} 1145 1146template <typename Element> 1147inline Element* RepeatedPtrField<Element>::ReleaseCleared() { 1148 return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>(); 1149} 1150 1151template <typename Element> 1152inline void RepeatedPtrField<Element>::Reserve(int new_size) { 1153 return RepeatedPtrFieldBase::Reserve(new_size); 1154} 1155 1156template <typename Element> 1157inline int RepeatedPtrField<Element>::Capacity() const { 1158 return RepeatedPtrFieldBase::Capacity(); 1159} 1160 1161// ------------------------------------------------------------------- 1162 1163namespace internal { 1164 1165// STL-like iterator implementation for RepeatedPtrField. You should not 1166// refer to this class directly; use RepeatedPtrField<T>::iterator instead. 1167// 1168// The iterator for RepeatedPtrField<T>, RepeatedPtrIterator<T>, is 1169// very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors.h, 1170// but adds random-access operators and is modified to wrap a void** base 1171// iterator (since RepeatedPtrField stores its array as a void* array and 1172// casting void** to T** would violate C++ aliasing rules). 1173// 1174// This code based on net/proto/proto-array-internal.h by Jeffrey Yasskin 1175// (jyasskin@google.com). 1176template<typename Element> 1177class RepeatedPtrIterator 1178 : public std::iterator< 1179 std::random_access_iterator_tag, Element> { 1180 public: 1181 typedef RepeatedPtrIterator<Element> iterator; 1182 typedef std::iterator< 1183 std::random_access_iterator_tag, Element> superclass; 1184 1185 // Let the compiler know that these are type names, so we don't have to 1186 // write "typename" in front of them everywhere. 1187 typedef typename superclass::reference reference; 1188 typedef typename superclass::pointer pointer; 1189 typedef typename superclass::difference_type difference_type; 1190 1191 RepeatedPtrIterator() : it_(NULL) {} 1192 explicit RepeatedPtrIterator(void* const* it) : it_(it) {} 1193 1194 // Allow "upcasting" from RepeatedPtrIterator<T**> to 1195 // RepeatedPtrIterator<const T*const*>. 1196 template<typename OtherElement> 1197 RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other) 1198 : it_(other.it_) { 1199 // Force a compiler error if the other type is not convertible to ours. 1200 if (false) { 1201 implicit_cast<Element*, OtherElement*>(0); 1202 } 1203 } 1204 1205 // dereferenceable 1206 reference operator*() const { return *reinterpret_cast<Element*>(*it_); } 1207 pointer operator->() const { return &(operator*()); } 1208 1209 // {inc,dec}rementable 1210 iterator& operator++() { ++it_; return *this; } 1211 iterator operator++(int) { return iterator(it_++); } 1212 iterator& operator--() { --it_; return *this; } 1213 iterator operator--(int) { return iterator(it_--); } 1214 1215 // equality_comparable 1216 bool operator==(const iterator& x) const { return it_ == x.it_; } 1217 bool operator!=(const iterator& x) const { return it_ != x.it_; } 1218 1219 // less_than_comparable 1220 bool operator<(const iterator& x) const { return it_ < x.it_; } 1221 bool operator<=(const iterator& x) const { return it_ <= x.it_; } 1222 bool operator>(const iterator& x) const { return it_ > x.it_; } 1223 bool operator>=(const iterator& x) const { return it_ >= x.it_; } 1224 1225 // addable, subtractable 1226 iterator& operator+=(difference_type d) { 1227 it_ += d; 1228 return *this; 1229 } 1230 friend iterator operator+(iterator it, difference_type d) { 1231 it += d; 1232 return it; 1233 } 1234 friend iterator operator+(difference_type d, iterator it) { 1235 it += d; 1236 return it; 1237 } 1238 iterator& operator-=(difference_type d) { 1239 it_ -= d; 1240 return *this; 1241 } 1242 friend iterator operator-(iterator it, difference_type d) { 1243 it -= d; 1244 return it; 1245 } 1246 1247 // indexable 1248 reference operator[](difference_type d) const { return *(*this + d); } 1249 1250 // random access iterator 1251 difference_type operator-(const iterator& x) const { return it_ - x.it_; } 1252 1253 private: 1254 template<typename OtherElement> 1255 friend class RepeatedPtrIterator; 1256 1257 // The internal iterator. 1258 void* const* it_; 1259}; 1260 1261// Provide an iterator that operates on pointers to the underlying objects 1262// rather than the objects themselves as RepeatedPtrIterator does. 1263// Consider using this when working with stl algorithms that change 1264// the array. 1265// The VoidPtr template parameter holds the type-agnostic pointer value 1266// referenced by the iterator. It should either be "void *" for a mutable 1267// iterator, or "const void *" for a constant iterator. 1268template<typename Element, typename VoidPtr> 1269class RepeatedPtrOverPtrsIterator 1270 : public std::iterator<std::random_access_iterator_tag, Element*> { 1271 public: 1272 typedef RepeatedPtrOverPtrsIterator<Element, VoidPtr> iterator; 1273 typedef std::iterator< 1274 std::random_access_iterator_tag, Element*> superclass; 1275 1276 // Let the compiler know that these are type names, so we don't have to 1277 // write "typename" in front of them everywhere. 1278 typedef typename superclass::reference reference; 1279 typedef typename superclass::pointer pointer; 1280 typedef typename superclass::difference_type difference_type; 1281 1282 RepeatedPtrOverPtrsIterator() : it_(NULL) {} 1283 explicit RepeatedPtrOverPtrsIterator(VoidPtr* it) : it_(it) {} 1284 1285 // dereferenceable 1286 reference operator*() const { return *reinterpret_cast<Element**>(it_); } 1287 pointer operator->() const { return &(operator*()); } 1288 1289 // {inc,dec}rementable 1290 iterator& operator++() { ++it_; return *this; } 1291 iterator operator++(int) { return iterator(it_++); } 1292 iterator& operator--() { --it_; return *this; } 1293 iterator operator--(int) { return iterator(it_--); } 1294 1295 // equality_comparable 1296 bool operator==(const iterator& x) const { return it_ == x.it_; } 1297 bool operator!=(const iterator& x) const { return it_ != x.it_; } 1298 1299 // less_than_comparable 1300 bool operator<(const iterator& x) const { return it_ < x.it_; } 1301 bool operator<=(const iterator& x) const { return it_ <= x.it_; } 1302 bool operator>(const iterator& x) const { return it_ > x.it_; } 1303 bool operator>=(const iterator& x) const { return it_ >= x.it_; } 1304 1305 // addable, subtractable 1306 iterator& operator+=(difference_type d) { 1307 it_ += d; 1308 return *this; 1309 } 1310 friend iterator operator+(iterator it, difference_type d) { 1311 it += d; 1312 return it; 1313 } 1314 friend iterator operator+(difference_type d, iterator it) { 1315 it += d; 1316 return it; 1317 } 1318 iterator& operator-=(difference_type d) { 1319 it_ -= d; 1320 return *this; 1321 } 1322 friend iterator operator-(iterator it, difference_type d) { 1323 it -= d; 1324 return it; 1325 } 1326 1327 // indexable 1328 reference operator[](difference_type d) const { return *(*this + d); } 1329 1330 // random access iterator 1331 difference_type operator-(const iterator& x) const { return it_ - x.it_; } 1332 1333 private: 1334 template<typename OtherElement> 1335 friend class RepeatedPtrIterator; 1336 1337 // The internal iterator. 1338 VoidPtr* it_; 1339}; 1340 1341} // namespace internal 1342 1343template <typename Element> 1344inline typename RepeatedPtrField<Element>::iterator 1345RepeatedPtrField<Element>::begin() { 1346 return iterator(raw_data()); 1347} 1348template <typename Element> 1349inline typename RepeatedPtrField<Element>::const_iterator 1350RepeatedPtrField<Element>::begin() const { 1351 return iterator(raw_data()); 1352} 1353template <typename Element> 1354inline typename RepeatedPtrField<Element>::iterator 1355RepeatedPtrField<Element>::end() { 1356 return iterator(raw_data() + size()); 1357} 1358template <typename Element> 1359inline typename RepeatedPtrField<Element>::const_iterator 1360RepeatedPtrField<Element>::end() const { 1361 return iterator(raw_data() + size()); 1362} 1363 1364template <typename Element> 1365inline typename RepeatedPtrField<Element>::pointer_iterator 1366RepeatedPtrField<Element>::pointer_begin() { 1367 return pointer_iterator(raw_mutable_data()); 1368} 1369template <typename Element> 1370inline typename RepeatedPtrField<Element>::const_pointer_iterator 1371RepeatedPtrField<Element>::pointer_begin() const { 1372 return const_pointer_iterator(const_cast<const void**>(raw_mutable_data())); 1373} 1374template <typename Element> 1375inline typename RepeatedPtrField<Element>::pointer_iterator 1376RepeatedPtrField<Element>::pointer_end() { 1377 return pointer_iterator(raw_mutable_data() + size()); 1378} 1379template <typename Element> 1380inline typename RepeatedPtrField<Element>::const_pointer_iterator 1381RepeatedPtrField<Element>::pointer_end() const { 1382 return const_pointer_iterator( 1383 const_cast<const void**>(raw_mutable_data() + size())); 1384} 1385 1386 1387// Iterators and helper functions that follow the spirit of the STL 1388// std::back_insert_iterator and std::back_inserter but are tailor-made 1389// for RepeatedField and RepatedPtrField. Typical usage would be: 1390// 1391// std::copy(some_sequence.begin(), some_sequence.end(), 1392// google::protobuf::RepeatedFieldBackInserter(proto.mutable_sequence())); 1393// 1394// Ported by johannes from util/gtl/proto-array-iterators.h 1395 1396namespace internal { 1397// A back inserter for RepeatedField objects. 1398template<typename T> class RepeatedFieldBackInsertIterator 1399 : public std::iterator<std::output_iterator_tag, T> { 1400 public: 1401 explicit RepeatedFieldBackInsertIterator( 1402 RepeatedField<T>* const mutable_field) 1403 : field_(mutable_field) { 1404 } 1405 RepeatedFieldBackInsertIterator<T>& operator=(const T& value) { 1406 field_->Add(value); 1407 return *this; 1408 } 1409 RepeatedFieldBackInsertIterator<T>& operator*() { 1410 return *this; 1411 } 1412 RepeatedFieldBackInsertIterator<T>& operator++() { 1413 return *this; 1414 } 1415 RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) { 1416 return *this; 1417 } 1418 1419 private: 1420 RepeatedField<T>* field_; 1421}; 1422 1423// A back inserter for RepeatedPtrField objects. 1424template<typename T> class RepeatedPtrFieldBackInsertIterator 1425 : public std::iterator<std::output_iterator_tag, T> { 1426 public: 1427 RepeatedPtrFieldBackInsertIterator( 1428 RepeatedPtrField<T>* const mutable_field) 1429 : field_(mutable_field) { 1430 } 1431 RepeatedPtrFieldBackInsertIterator<T>& operator=(const T& value) { 1432 *field_->Add() = value; 1433 return *this; 1434 } 1435 RepeatedPtrFieldBackInsertIterator<T>& operator=( 1436 const T* const ptr_to_value) { 1437 *field_->Add() = *ptr_to_value; 1438 return *this; 1439 } 1440 RepeatedPtrFieldBackInsertIterator<T>& operator*() { 1441 return *this; 1442 } 1443 RepeatedPtrFieldBackInsertIterator<T>& operator++() { 1444 return *this; 1445 } 1446 RepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) { 1447 return *this; 1448 } 1449 1450 private: 1451 RepeatedPtrField<T>* field_; 1452}; 1453 1454// A back inserter for RepeatedPtrFields that inserts by transfering ownership 1455// of a pointer. 1456template<typename T> class AllocatedRepeatedPtrFieldBackInsertIterator 1457 : public std::iterator<std::output_iterator_tag, T> { 1458 public: 1459 explicit AllocatedRepeatedPtrFieldBackInsertIterator( 1460 RepeatedPtrField<T>* const mutable_field) 1461 : field_(mutable_field) { 1462 } 1463 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator=( 1464 T* const ptr_to_value) { 1465 field_->AddAllocated(ptr_to_value); 1466 return *this; 1467 } 1468 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator*() { 1469 return *this; 1470 } 1471 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++() { 1472 return *this; 1473 } 1474 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++( 1475 int /* unused */) { 1476 return *this; 1477 } 1478 1479 private: 1480 RepeatedPtrField<T>* field_; 1481}; 1482} // namespace internal 1483 1484// Provides a back insert iterator for RepeatedField instances, 1485// similar to std::back_inserter(). 1486template<typename T> internal::RepeatedFieldBackInsertIterator<T> 1487RepeatedFieldBackInserter(RepeatedField<T>* const mutable_field) { 1488 return internal::RepeatedFieldBackInsertIterator<T>(mutable_field); 1489} 1490 1491// Provides a back insert iterator for RepeatedPtrField instances, 1492// similar to std::back_inserter(). 1493template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> 1494RepeatedPtrFieldBackInserter(RepeatedPtrField<T>* const mutable_field) { 1495 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field); 1496} 1497 1498// Special back insert iterator for RepeatedPtrField instances, just in 1499// case someone wants to write generic template code that can access both 1500// RepeatedFields and RepeatedPtrFields using a common name. 1501template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> 1502RepeatedFieldBackInserter(RepeatedPtrField<T>* const mutable_field) { 1503 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field); 1504} 1505 1506// Provides a back insert iterator for RepeatedPtrField instances 1507// similar to std::back_inserter() which transfers the ownership while 1508// copying elements. 1509template<typename T> internal::AllocatedRepeatedPtrFieldBackInsertIterator<T> 1510AllocatedRepeatedPtrFieldBackInserter( 1511 RepeatedPtrField<T>* const mutable_field) { 1512 return internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>( 1513 mutable_field); 1514} 1515 1516} // namespace protobuf 1517 1518} // namespace google 1519#endif // GOOGLE_PROTOBUF_REPEATED_FIELD_H__ 1520