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