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 (at) google.com (Kenton Varda) 32 // Based on original Protocol Buffers design by 33 // Sanjay Ghemawat, Jeff Dean, and others. 34 // 35 // RepeatedField and RepeatedPtrField are used by generated protocol message 36 // classes to manipulate repeated fields. These classes are very similar to 37 // STL's vector, but include a number of optimizations found to be useful 38 // specifically in the case of Protocol Buffers. RepeatedPtrField is 39 // particularly different from STL vector as it manages ownership of the 40 // pointers that it contains. 41 // 42 // Typically, clients should not need to access RepeatedField objects directly, 43 // but should instead use the accessor functions generated automatically by the 44 // protocol compiler. 45 46 #ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__ 47 #define GOOGLE_PROTOBUF_REPEATED_FIELD_H__ 48 49 #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 61 namespace google { 62 63 namespace upb { 64 namespace google_opensource { 65 class GMR_Handlers; 66 } // namespace google_opensource 67 } // namespace upb 68 69 namespace protobuf { 70 71 class Message; 72 73 namespace internal { 74 75 static const int kMinRepeatedFieldAllocationSize = 4; 76 77 // A utility function for logging that doesn't need any template types. 78 void LogIndexOutOfBounds(int index, int size); 79 80 template <typename Iter> 81 inline int CalculateReserve(Iter begin, Iter end, std::forward_iterator_tag) { 82 return std::distance(begin, end); 83 } 84 85 template <typename Iter> 86 inline int CalculateReserve(Iter /*begin*/, Iter /*end*/, 87 std::input_iterator_tag) { 88 return -1; 89 } 90 91 template <typename Iter> 92 inline 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. 103 template <typename Element> 104 class 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 214 namespace internal { 215 template <typename It> class RepeatedPtrIterator; 216 template <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator; 217 } // namespace internal 218 219 namespace 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. 225 template <typename Element, 226 bool HasTrivialCopy = has_trivial_copy<Element>::value> 227 struct ElementCopier { 228 void operator()(Element to[], const Element from[], int array_size); 229 }; 230 231 } // namespace internal 232 233 namespace 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 // }; 251 class 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 359 template <typename GenericType> 360 class 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 373 template <> 374 inline void GenericTypeHandler<MessageLite>::Merge( 375 const MessageLite& from, MessageLite* to) { 376 to->CheckTypeAndMergeFrom(from); 377 } 378 379 template <> 380 inline 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 388 template <> 389 inline 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. 406 class 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 418 class 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. 430 template <typename Element> 431 class 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 579 template <typename Element> 580 inline RepeatedField<Element>::RepeatedField() 581 : elements_(NULL), 582 current_size_(0), 583 total_size_(kInitialSize) { 584 } 585 586 template <typename Element> 587 inline RepeatedField<Element>::RepeatedField(const RepeatedField& other) 588 : elements_(NULL), 589 current_size_(0), 590 total_size_(kInitialSize) { 591 CopyFrom(other); 592 } 593 594 template <typename Element> 595 template <typename Iter> 596 inline 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 613 template <typename Element> 614 RepeatedField<Element>::~RepeatedField() { 615 delete [] elements_; 616 } 617 618 template <typename Element> 619 inline RepeatedField<Element>& 620 RepeatedField<Element>::operator=(const RepeatedField& other) { 621 if (this != &other) 622 CopyFrom(other); 623 return *this; 624 } 625 626 template <typename Element> 627 inline bool RepeatedField<Element>::empty() const { 628 return current_size_ == 0; 629 } 630 631 template <typename Element> 632 inline int RepeatedField<Element>::size() const { 633 return current_size_; 634 } 635 636 template <typename Element> 637 inline int RepeatedField<Element>::Capacity() const { 638 return total_size_; 639 } 640 641 template<typename Element> 642 inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) { 643 GOOGLE_DCHECK_LT(size(), Capacity()); 644 elements_[current_size_++] = value; 645 } 646 647 template<typename Element> 648 inline Element* RepeatedField<Element>::AddAlreadyReserved() { 649 GOOGLE_DCHECK_LT(size(), Capacity()); 650 return &elements_[current_size_++]; 651 } 652 653 template<typename Element> 654 inline 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 663 template <typename Element> 664 inline 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 670 template <typename Element> 671 inline Element* RepeatedField<Element>::Mutable(int index) { 672 GOOGLE_DCHECK_GE(index, 0); 673 GOOGLE_DCHECK_LT(index, size()); 674 return elements_ + index; 675 } 676 677 template <typename Element> 678 inline 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 684 template <typename Element> 685 inline void RepeatedField<Element>::Add(const Element& value) { 686 if (current_size_ == total_size_) Reserve(total_size_ + 1); 687 elements_[current_size_++] = value; 688 } 689 690 template <typename Element> 691 inline Element* RepeatedField<Element>::Add() { 692 if (current_size_ == total_size_) Reserve(total_size_ + 1); 693 return &elements_[current_size_++]; 694 } 695 696 template <typename Element> 697 inline void RepeatedField<Element>::RemoveLast() { 698 GOOGLE_DCHECK_GT(current_size_, 0); 699 --current_size_; 700 } 701 702 template <typename Element> 703 void 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 723 template <typename Element> 724 inline void RepeatedField<Element>::Clear() { 725 current_size_ = 0; 726 } 727 728 template <typename Element> 729 inline 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 738 template <typename Element> 739 inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) { 740 if (&other == this) return; 741 Clear(); 742 MergeFrom(other); 743 } 744 745 template <typename Element> 746 inline Element* RepeatedField<Element>::mutable_data() { 747 return elements_; 748 } 749 750 template <typename Element> 751 inline const Element* RepeatedField<Element>::data() const { 752 return elements_; 753 } 754 755 756 template <typename Element> 757 void 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 772 template <typename Element> 773 void RepeatedField<Element>::SwapElements(int index1, int index2) { 774 using std::swap; // enable ADL with fallback 775 swap(elements_[index1], elements_[index2]); 776 } 777 778 template <typename Element> 779 inline typename RepeatedField<Element>::iterator 780 RepeatedField<Element>::begin() { 781 return elements_; 782 } 783 template <typename Element> 784 inline typename RepeatedField<Element>::const_iterator 785 RepeatedField<Element>::begin() const { 786 return elements_; 787 } 788 template <typename Element> 789 inline typename RepeatedField<Element>::iterator 790 RepeatedField<Element>::end() { 791 return elements_ + current_size_; 792 } 793 template <typename Element> 794 inline typename RepeatedField<Element>::const_iterator 795 RepeatedField<Element>::end() const { 796 return elements_ + current_size_; 797 } 798 799 template <typename Element> 800 inline 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. 806 template <typename Element> 807 void 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 820 template <typename Element> 821 inline void RepeatedField<Element>::Truncate(int new_size) { 822 GOOGLE_DCHECK_LE(new_size, current_size_); 823 current_size_ = new_size; 824 } 825 826 template <typename Element> 827 inline void RepeatedField<Element>::MoveArray( 828 Element to[], Element from[], int array_size) { 829 CopyArray(to, from, array_size); 830 } 831 832 template <typename Element> 833 inline void RepeatedField<Element>::CopyArray( 834 Element to[], const Element from[], int array_size) { 835 internal::ElementCopier<Element>()(to, from, array_size); 836 } 837 838 namespace internal { 839 840 template <typename Element, bool HasTrivialCopy> 841 void ElementCopier<Element, HasTrivialCopy>::operator()( 842 Element to[], const Element from[], int array_size) { 843 std::copy(from, from + array_size, to); 844 } 845 846 template <typename Element> 847 struct 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 858 namespace internal { 859 860 inline RepeatedPtrFieldBase::RepeatedPtrFieldBase() 861 : elements_(NULL), 862 current_size_(0), 863 allocated_size_(0), 864 total_size_(kInitialSize) { 865 } 866 867 template <typename TypeHandler> 868 void RepeatedPtrFieldBase::Destroy() { 869 for (int i = 0; i < allocated_size_; i++) { 870 TypeHandler::Delete(cast<TypeHandler>(elements_[i])); 871 } 872 delete [] elements_; 873 } 874 875 inline bool RepeatedPtrFieldBase::empty() const { 876 return current_size_ == 0; 877 } 878 879 inline int RepeatedPtrFieldBase::size() const { 880 return current_size_; 881 } 882 883 template <typename TypeHandler> 884 inline const typename TypeHandler::Type& 885 RepeatedPtrFieldBase::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 892 template <typename TypeHandler> 893 inline typename TypeHandler::Type* 894 RepeatedPtrFieldBase::Mutable(int index) { 895 GOOGLE_DCHECK_GE(index, 0); 896 GOOGLE_DCHECK_LT(index, size()); 897 return cast<TypeHandler>(elements_[index]); 898 } 899 900 template <typename TypeHandler> 901 inline 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 912 template <typename TypeHandler> 913 inline void RepeatedPtrFieldBase::RemoveLast() { 914 GOOGLE_DCHECK_GT(current_size_, 0); 915 TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_])); 916 } 917 918 template <typename TypeHandler> 919 void 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 926 template <typename TypeHandler> 927 inline 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 935 template <typename TypeHandler> 936 inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) { 937 if (&other == this) return; 938 RepeatedPtrFieldBase::Clear<TypeHandler>(); 939 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other); 940 } 941 942 inline int RepeatedPtrFieldBase::Capacity() const { 943 return total_size_; 944 } 945 946 inline void* const* RepeatedPtrFieldBase::raw_data() const { 947 return elements_; 948 } 949 950 inline void** RepeatedPtrFieldBase::raw_mutable_data() const { 951 return elements_; 952 } 953 954 template <typename TypeHandler> 955 inline 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 961 template <typename TypeHandler> 962 inline const typename TypeHandler::Type* const* 963 RepeatedPtrFieldBase::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 969 inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) { 970 using std::swap; // enable ADL with fallback 971 swap(elements_[index1], elements_[index2]); 972 } 973 974 template <typename TypeHandler> 975 inline 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 984 template <typename TypeHandler> 985 inline 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 993 template <typename TypeHandler> 994 void 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 1020 template <typename TypeHandler> 1021 inline 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 1034 inline int RepeatedPtrFieldBase::ClearedCount() const { 1035 return allocated_size_ - current_size_; 1036 } 1037 1038 template <typename TypeHandler> 1039 inline 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 1045 template <typename TypeHandler> 1046 inline 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 1055 template <typename Element> 1056 class RepeatedPtrField<Element>::TypeHandler 1057 : public internal::GenericTypeHandler<Element> { 1058 }; 1059 1060 template <> 1061 class RepeatedPtrField<string>::TypeHandler 1062 : public internal::StringTypeHandler { 1063 }; 1064 1065 1066 template <typename Element> 1067 inline RepeatedPtrField<Element>::RepeatedPtrField() {} 1068 1069 template <typename Element> 1070 inline RepeatedPtrField<Element>::RepeatedPtrField( 1071 const RepeatedPtrField& other) 1072 : RepeatedPtrFieldBase() { 1073 CopyFrom(other); 1074 } 1075 1076 template <typename Element> 1077 template <typename Iter> 1078 inline 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 1089 template <typename Element> 1090 RepeatedPtrField<Element>::~RepeatedPtrField() { 1091 Destroy<TypeHandler>(); 1092 } 1093 1094 template <typename Element> 1095 inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=( 1096 const RepeatedPtrField& other) { 1097 if (this != &other) 1098 CopyFrom(other); 1099 return *this; 1100 } 1101 1102 template <typename Element> 1103 inline bool RepeatedPtrField<Element>::empty() const { 1104 return RepeatedPtrFieldBase::empty(); 1105 } 1106 1107 template <typename Element> 1108 inline int RepeatedPtrField<Element>::size() const { 1109 return RepeatedPtrFieldBase::size(); 1110 } 1111 1112 template <typename Element> 1113 inline const Element& RepeatedPtrField<Element>::Get(int index) const { 1114 return RepeatedPtrFieldBase::Get<TypeHandler>(index); 1115 } 1116 1117 1118 template <typename Element> 1119 inline Element* RepeatedPtrField<Element>::Mutable(int index) { 1120 return RepeatedPtrFieldBase::Mutable<TypeHandler>(index); 1121 } 1122 1123 template <typename Element> 1124 inline Element* RepeatedPtrField<Element>::Add() { 1125 return RepeatedPtrFieldBase::Add<TypeHandler>(); 1126 } 1127 1128 template <typename Element> 1129 inline void RepeatedPtrField<Element>::RemoveLast() { 1130 RepeatedPtrFieldBase::RemoveLast<TypeHandler>(); 1131 } 1132 1133 template <typename Element> 1134 inline 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 1143 template <typename Element> 1144 inline 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 1160 template <typename Element> 1161 inline void RepeatedPtrField<Element>::Clear() { 1162 RepeatedPtrFieldBase::Clear<TypeHandler>(); 1163 } 1164 1165 template <typename Element> 1166 inline void RepeatedPtrField<Element>::MergeFrom( 1167 const RepeatedPtrField& other) { 1168 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other); 1169 } 1170 1171 template <typename Element> 1172 inline void RepeatedPtrField<Element>::CopyFrom( 1173 const RepeatedPtrField& other) { 1174 RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other); 1175 } 1176 1177 template <typename Element> 1178 inline Element** RepeatedPtrField<Element>::mutable_data() { 1179 return RepeatedPtrFieldBase::mutable_data<TypeHandler>(); 1180 } 1181 1182 template <typename Element> 1183 inline const Element* const* RepeatedPtrField<Element>::data() const { 1184 return RepeatedPtrFieldBase::data<TypeHandler>(); 1185 } 1186 1187 template <typename Element> 1188 void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) { 1189 RepeatedPtrFieldBase::Swap(other); 1190 } 1191 1192 template <typename Element> 1193 void RepeatedPtrField<Element>::SwapElements(int index1, int index2) { 1194 RepeatedPtrFieldBase::SwapElements(index1, index2); 1195 } 1196 1197 template <typename Element> 1198 inline int RepeatedPtrField<Element>::SpaceUsedExcludingSelf() const { 1199 return RepeatedPtrFieldBase::SpaceUsedExcludingSelf<TypeHandler>(); 1200 } 1201 1202 template <typename Element> 1203 inline void RepeatedPtrField<Element>::AddAllocated(Element* value) { 1204 RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value); 1205 } 1206 1207 template <typename Element> 1208 inline Element* RepeatedPtrField<Element>::ReleaseLast() { 1209 return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>(); 1210 } 1211 1212 1213 template <typename Element> 1214 inline int RepeatedPtrField<Element>::ClearedCount() const { 1215 return RepeatedPtrFieldBase::ClearedCount(); 1216 } 1217 1218 template <typename Element> 1219 inline void RepeatedPtrField<Element>::AddCleared(Element* value) { 1220 return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value); 1221 } 1222 1223 template <typename Element> 1224 inline Element* RepeatedPtrField<Element>::ReleaseCleared() { 1225 return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>(); 1226 } 1227 1228 template <typename Element> 1229 inline void RepeatedPtrField<Element>::Reserve(int new_size) { 1230 return RepeatedPtrFieldBase::Reserve(new_size); 1231 } 1232 1233 template <typename Element> 1234 inline int RepeatedPtrField<Element>::Capacity() const { 1235 return RepeatedPtrFieldBase::Capacity(); 1236 } 1237 1238 // ------------------------------------------------------------------- 1239 1240 namespace 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 (at) google.com). 1253 template<typename Element> 1254 class 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. 1349 template<typename Element, typename VoidPtr> 1350 class 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 1428 template <typename Element> 1429 inline typename RepeatedPtrField<Element>::iterator 1430 RepeatedPtrField<Element>::begin() { 1431 return iterator(raw_data()); 1432 } 1433 template <typename Element> 1434 inline typename RepeatedPtrField<Element>::const_iterator 1435 RepeatedPtrField<Element>::begin() const { 1436 return iterator(raw_data()); 1437 } 1438 template <typename Element> 1439 inline typename RepeatedPtrField<Element>::iterator 1440 RepeatedPtrField<Element>::end() { 1441 return iterator(raw_data() + size()); 1442 } 1443 template <typename Element> 1444 inline typename RepeatedPtrField<Element>::const_iterator 1445 RepeatedPtrField<Element>::end() const { 1446 return iterator(raw_data() + size()); 1447 } 1448 1449 template <typename Element> 1450 inline typename RepeatedPtrField<Element>::pointer_iterator 1451 RepeatedPtrField<Element>::pointer_begin() { 1452 return pointer_iterator(raw_mutable_data()); 1453 } 1454 template <typename Element> 1455 inline typename RepeatedPtrField<Element>::const_pointer_iterator 1456 RepeatedPtrField<Element>::pointer_begin() const { 1457 return const_pointer_iterator(const_cast<const void**>(raw_mutable_data())); 1458 } 1459 template <typename Element> 1460 inline typename RepeatedPtrField<Element>::pointer_iterator 1461 RepeatedPtrField<Element>::pointer_end() { 1462 return pointer_iterator(raw_mutable_data() + size()); 1463 } 1464 template <typename Element> 1465 inline typename RepeatedPtrField<Element>::const_pointer_iterator 1466 RepeatedPtrField<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 1481 namespace internal { 1482 // A back inserter for RepeatedField objects. 1483 template<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. 1509 template<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. 1541 template<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(). 1571 template<typename T> internal::RepeatedFieldBackInsertIterator<T> 1572 RepeatedFieldBackInserter(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(). 1578 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> 1579 RepeatedPtrFieldBackInserter(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. 1586 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> 1587 RepeatedFieldBackInserter(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. 1594 template<typename T> internal::AllocatedRepeatedPtrFieldBackInsertIterator<T> 1595 AllocatedRepeatedPtrFieldBackInserter( 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