1// Protocol Buffers - Google's data interchange format 2// Copyright 2008 Google Inc. All rights reserved. 3// http://code.google.com/p/protobuf/ 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#include <string> 50#include <iterator> 51#include <google/protobuf/stubs/common.h> 52#include <google/protobuf/message_lite.h> 53 54namespace google { 55 56namespace protobuf { 57 58class Message; 59 60namespace internal { 61 62// We need this (from generated_message_reflection.cc). 63LIBPROTOBUF_EXPORT int StringSpaceUsedExcludingSelf(const string& str); 64 65} // namespace internal 66 67// RepeatedField is used to represent repeated fields of a primitive type (in 68// other words, everything except strings and nested Messages). Most users will 69// not ever use a RepeatedField directly; they will use the get-by-index, 70// set-by-index, and add accessors that are generated for all repeated fields. 71template <typename Element> 72class RepeatedField { 73 public: 74 RepeatedField(); 75 ~RepeatedField(); 76 77 int size() const; 78 79 const Element& Get(int index) const; 80 Element* Mutable(int index); 81 void Set(int index, const Element& value); 82 void Add(const Element& value); 83 Element* Add(); 84 // Remove the last element in the array. 85 // We don't provide a way to remove any element other than the last 86 // because it invites inefficient use, such as O(n^2) filtering loops 87 // that should have been O(n). If you want to remove an element other 88 // than the last, the best way to do it is to re-arrange the elements 89 // so that the one you want removed is at the end, then call RemoveLast(). 90 void RemoveLast(); 91 void Clear(); 92 void MergeFrom(const RepeatedField& other); 93 94 // Reserve space to expand the field to at least the given size. If the 95 // array is grown, it will always be at least doubled in size. 96 void Reserve(int new_size); 97 98 // Resize the RepeatedField to a new, smaller size. This is O(1). 99 void Truncate(int new_size); 100 101 void AddAlreadyReserved(const Element& value); 102 Element* AddAlreadyReserved(); 103 int Capacity() const; 104 105 // Gets the underlying array. This pointer is possibly invalidated by 106 // any add or remove operation. 107 Element* mutable_data(); 108 const Element* data() const; 109 110 // Swap entire contents with "other". 111 void Swap(RepeatedField* other); 112 113 // Swap two elements. 114 void SwapElements(int index1, int index2); 115 116 // STL-like iterator support 117 typedef Element* iterator; 118 typedef const Element* const_iterator; 119 120 iterator begin(); 121 const_iterator begin() const; 122 iterator end(); 123 const_iterator end() const; 124 125 // Returns the number of bytes used by the repeated field, excluding 126 // sizeof(*this) 127 int SpaceUsedExcludingSelf() const; 128 129 private: 130 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedField); 131 132 static const int kInitialSize = 4; 133 134 Element* elements_; 135 int current_size_; 136 int total_size_; 137 138 Element initial_space_[kInitialSize]; 139 140 // Move the contents of |from| into |to|, possibly clobbering |from| in the 141 // process. For primitive types this is just a memcpy(), but it could be 142 // specialized for non-primitive types to, say, swap each element instead. 143 void MoveArray(Element to[], Element from[], int size); 144 145 // Copy the elements of |from| into |to|. 146 void CopyArray(Element to[], const Element from[], int size); 147}; 148 149namespace internal { 150template <typename It> class RepeatedPtrIterator; 151template <typename It> class RepeatedPtrOverPtrsIterator; 152} // namespace internal 153 154namespace internal { 155 156// This is the common base class for RepeatedPtrFields. It deals only in void* 157// pointers. Users should not use this interface directly. 158// 159// The methods of this interface correspond to the methods of RepeatedPtrField, 160// but may have a template argument called TypeHandler. Its signature is: 161// class TypeHandler { 162// public: 163// typedef MyType Type; 164// static Type* New(); 165// static void Delete(Type*); 166// static void Clear(Type*); 167// static void Merge(const Type& from, Type* to); 168// 169// // Only needs to be implemented if SpaceUsedExcludingSelf() is called. 170// static int SpaceUsed(const Type&); 171// }; 172class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { 173 protected: 174 // The reflection implementation needs to call protected methods directly, 175 // reinterpreting pointers as being to Message instead of a specific Message 176 // subclass. 177 friend class GeneratedMessageReflection; 178 179 // ExtensionSet stores repeated message extensions as 180 // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to 181 // implement SpaceUsed(), and thus need to call SpaceUsedExcludingSelf() 182 // reinterpreting MessageLite as Message. ExtensionSet also needs to make 183 // use of AddFromCleared(), which is not part of the public interface. 184 friend class ExtensionSet; 185 186 RepeatedPtrFieldBase(); 187 188 // Must be called from destructor. 189 template <typename TypeHandler> 190 void Destroy(); 191 192 int size() const; 193 194 template <typename TypeHandler> 195 const typename TypeHandler::Type& Get(int index) const; 196 template <typename TypeHandler> 197 typename TypeHandler::Type* Mutable(int index); 198 template <typename TypeHandler> 199 typename TypeHandler::Type* Add(); 200 template <typename TypeHandler> 201 void RemoveLast(); 202 template <typename TypeHandler> 203 void Clear(); 204 template <typename TypeHandler> 205 void MergeFrom(const RepeatedPtrFieldBase& other); 206 207 void Reserve(int new_size); 208 209 int Capacity() const; 210 211 // Used for constructing iterators. 212 void* const* raw_data() const; 213 void** raw_mutable_data() const; 214 215 template <typename TypeHandler> 216 typename TypeHandler::Type** mutable_data(); 217 template <typename TypeHandler> 218 const typename TypeHandler::Type* const* data() const; 219 220 void Swap(RepeatedPtrFieldBase* other); 221 222 void SwapElements(int index1, int index2); 223 224 template <typename TypeHandler> 225 int SpaceUsedExcludingSelf() const; 226 227 228 // Advanced memory management -------------------------------------- 229 230 // Like Add(), but if there are no cleared objects to use, returns NULL. 231 template <typename TypeHandler> 232 typename TypeHandler::Type* AddFromCleared(); 233 234 template <typename TypeHandler> 235 void AddAllocated(typename TypeHandler::Type* value); 236 template <typename TypeHandler> 237 typename TypeHandler::Type* ReleaseLast(); 238 239 int ClearedCount() const; 240 template <typename TypeHandler> 241 void AddCleared(typename TypeHandler::Type* value); 242 template <typename TypeHandler> 243 typename TypeHandler::Type* ReleaseCleared(); 244 245 private: 246 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase); 247 248 static const int kInitialSize = 4; 249 250 void** elements_; 251 int current_size_; 252 int allocated_size_; 253 int total_size_; 254 255 void* initial_space_[kInitialSize]; 256 257 template <typename TypeHandler> 258 static inline typename TypeHandler::Type* cast(void* element) { 259 return reinterpret_cast<typename TypeHandler::Type*>(element); 260 } 261 template <typename TypeHandler> 262 static inline const typename TypeHandler::Type* cast(const void* element) { 263 return reinterpret_cast<const typename TypeHandler::Type*>(element); 264 } 265}; 266 267template <typename GenericType> 268class GenericTypeHandler { 269 public: 270 typedef GenericType Type; 271 static GenericType* New() { return new GenericType; } 272 static void Delete(GenericType* value) { delete value; } 273 static void Clear(GenericType* value) { value->Clear(); } 274 static void Merge(const GenericType& from, GenericType* to) { 275 to->MergeFrom(from); 276 } 277 static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); } 278}; 279 280template <> 281inline void GenericTypeHandler<MessageLite>::Merge( 282 const MessageLite& from, MessageLite* to) { 283 to->CheckTypeAndMergeFrom(from); 284} 285 286// HACK: If a class is declared as DLL-exported in MSVC, it insists on 287// generating copies of all its methods -- even inline ones -- to include 288// in the DLL. But SpaceUsed() calls StringSpaceUsedExcludingSelf() which 289// isn't in the lite library, therefore the lite library cannot link if 290// StringTypeHandler is exported. So, we factor out StringTypeHandlerBase, 291// export that, then make StringTypeHandler be a subclass which is NOT 292// exported. 293// TODO(kenton): There has to be a better way. 294class LIBPROTOBUF_EXPORT StringTypeHandlerBase { 295 public: 296 typedef string Type; 297 static string* New(); 298 static void Delete(string* value); 299 static void Clear(string* value) { value->clear(); } 300 static void Merge(const string& from, string* to) { *to = from; } 301}; 302 303class StringTypeHandler : public StringTypeHandlerBase { 304 public: 305 static int SpaceUsed(const string& value) { 306 return sizeof(value) + StringSpaceUsedExcludingSelf(value); 307 } 308}; 309 310 311} // namespace internal 312 313// RepeatedPtrField is like RepeatedField, but used for repeated strings or 314// Messages. 315template <typename Element> 316class RepeatedPtrField : public internal::RepeatedPtrFieldBase { 317 public: 318 RepeatedPtrField(); 319 320 ~RepeatedPtrField(); 321 322 int size() const; 323 324 const Element& Get(int index) const; 325 Element* Mutable(int index); 326 Element* Add(); 327 void RemoveLast(); // Remove the last element in the array. 328 void Clear(); 329 void MergeFrom(const RepeatedPtrField& other); 330 331 // Reserve space to expand the field to at least the given size. This only 332 // resizes the pointer array; it doesn't allocate any objects. If the 333 // array is grown, it will always be at least doubled in size. 334 void Reserve(int new_size); 335 336 int Capacity() const; 337 338 // Gets the underlying array. This pointer is possibly invalidated by 339 // any add or remove operation. 340 Element** mutable_data(); 341 const Element* const* data() const; 342 343 // Swap entire contents with "other". 344 void Swap(RepeatedPtrField* other); 345 346 // Swap two elements. 347 void SwapElements(int index1, int index2); 348 349 // STL-like iterator support 350 typedef internal::RepeatedPtrIterator<Element> iterator; 351 typedef internal::RepeatedPtrIterator<const Element> const_iterator; 352 353 iterator begin(); 354 const_iterator begin() const; 355 iterator end(); 356 const_iterator end() const; 357 358 // Custom STL-like iterator that iterates over and returns the underlying 359 // pointers to Element rather than Element itself. 360 typedef internal::RepeatedPtrOverPtrsIterator<Element> pointer_iterator; 361 pointer_iterator pointer_begin(); 362 pointer_iterator pointer_end(); 363 364 // Returns (an estimate of) the number of bytes used by the repeated field, 365 // excluding sizeof(*this). 366 int SpaceUsedExcludingSelf() const; 367 368 // The spaced used just by the pointer array, not counting the objects pointed 369 // at. Returns zero if the array is inlined (i.e. initial_space_ is being 370 // used). 371 int SpaceUsedByArray() const; 372 373 // Advanced memory management -------------------------------------- 374 // When hardcore memory management becomes necessary -- as it often 375 // does here at Google -- the following methods may be useful. 376 377 // Add an already-allocated object, passing ownership to the 378 // RepeatedPtrField. 379 void AddAllocated(Element* value); 380 // Remove the last element and return it, passing ownership to the 381 // caller. 382 // Requires: size() > 0 383 Element* ReleaseLast(); 384 385 // When elements are removed by calls to RemoveLast() or Clear(), they 386 // are not actually freed. Instead, they are cleared and kept so that 387 // they can be reused later. This can save lots of CPU time when 388 // repeatedly reusing a protocol message for similar purposes. 389 // 390 // Really, extremely hardcore programs may actually want to manipulate 391 // these objects to better-optimize memory management. These methods 392 // allow that. 393 394 // Get the number of cleared objects that are currently being kept 395 // around for reuse. 396 int ClearedCount() const; 397 // Add an element to the pool of cleared objects, passing ownership to 398 // the RepeatedPtrField. The element must be cleared prior to calling 399 // this method. 400 void AddCleared(Element* value); 401 // Remove a single element from the cleared pool and return it, passing 402 // ownership to the caller. The element is guaranteed to be cleared. 403 // Requires: ClearedCount() > 0 404 Element* ReleaseCleared(); 405 406 protected: 407 // Note: RepeatedPtrField SHOULD NOT be subclassed by users. We only 408 // subclass it in one place as a hack for compatibility with proto1. The 409 // subclass needs to know about TypeHandler in order to call protected 410 // methods on RepeatedPtrFieldBase. 411 class TypeHandler; 412 413 414 private: 415 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrField); 416}; 417 418// implementation ==================================================== 419 420template <typename Element> 421inline RepeatedField<Element>::RepeatedField() 422 : elements_(initial_space_), 423 current_size_(0), 424 total_size_(kInitialSize) { 425} 426 427template <typename Element> 428RepeatedField<Element>::~RepeatedField() { 429 if (elements_ != initial_space_) { 430 delete [] elements_; 431 } 432} 433 434template <typename Element> 435inline int RepeatedField<Element>::size() const { 436 return current_size_; 437} 438 439template <typename Element> 440inline int RepeatedField<Element>::Capacity() const { 441 return total_size_; 442} 443 444template<typename Element> 445inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) { 446 GOOGLE_DCHECK_LT(size(), Capacity()); 447 elements_[current_size_++] = value; 448} 449 450template<typename Element> 451inline Element* RepeatedField<Element>::AddAlreadyReserved() { 452 GOOGLE_DCHECK_LT(size(), Capacity()); 453 return &elements_[current_size_++]; 454} 455 456template <typename Element> 457inline const Element& RepeatedField<Element>::Get(int index) const { 458 GOOGLE_DCHECK_LT(index, size()); 459 return elements_[index]; 460} 461 462template <typename Element> 463inline Element* RepeatedField<Element>::Mutable(int index) { 464 GOOGLE_DCHECK_LT(index, size()); 465 return elements_ + index; 466} 467 468template <typename Element> 469inline void RepeatedField<Element>::Set(int index, const Element& value) { 470 GOOGLE_DCHECK_LT(index, size()); 471 elements_[index] = value; 472} 473 474template <typename Element> 475inline void RepeatedField<Element>::Add(const Element& value) { 476 if (current_size_ == total_size_) Reserve(total_size_ + 1); 477 elements_[current_size_++] = value; 478} 479 480template <typename Element> 481inline Element* RepeatedField<Element>::Add() { 482 if (current_size_ == total_size_) Reserve(total_size_ + 1); 483 return &elements_[current_size_++]; 484} 485 486template <typename Element> 487inline void RepeatedField<Element>::RemoveLast() { 488 GOOGLE_DCHECK_GT(current_size_, 0); 489 --current_size_; 490} 491 492template <typename Element> 493inline void RepeatedField<Element>::Clear() { 494 current_size_ = 0; 495} 496 497template <typename Element> 498inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) { 499 Reserve(current_size_ + other.current_size_); 500 CopyArray(elements_ + current_size_, other.elements_, other.current_size_); 501 current_size_ += other.current_size_; 502} 503 504template <typename Element> 505inline Element* RepeatedField<Element>::mutable_data() { 506 return elements_; 507} 508 509template <typename Element> 510inline const Element* RepeatedField<Element>::data() const { 511 return elements_; 512} 513 514 515template <typename Element> 516void RepeatedField<Element>::Swap(RepeatedField* other) { 517 Element* swap_elements = elements_; 518 int swap_current_size = current_size_; 519 int swap_total_size = total_size_; 520 // We may not be using initial_space_ but it's not worth checking. Just 521 // copy it anyway. 522 Element swap_initial_space[kInitialSize]; 523 MoveArray(swap_initial_space, initial_space_, kInitialSize); 524 525 elements_ = other->elements_; 526 current_size_ = other->current_size_; 527 total_size_ = other->total_size_; 528 MoveArray(initial_space_, other->initial_space_, kInitialSize); 529 530 other->elements_ = swap_elements; 531 other->current_size_ = swap_current_size; 532 other->total_size_ = swap_total_size; 533 MoveArray(other->initial_space_, swap_initial_space, kInitialSize); 534 535 if (elements_ == other->initial_space_) { 536 elements_ = initial_space_; 537 } 538 if (other->elements_ == initial_space_) { 539 other->elements_ = other->initial_space_; 540 } 541} 542 543template <typename Element> 544void RepeatedField<Element>::SwapElements(int index1, int index2) { 545 std::swap(elements_[index1], elements_[index2]); 546} 547 548template <typename Element> 549inline typename RepeatedField<Element>::iterator 550RepeatedField<Element>::begin() { 551 return elements_; 552} 553template <typename Element> 554inline typename RepeatedField<Element>::const_iterator 555RepeatedField<Element>::begin() const { 556 return elements_; 557} 558template <typename Element> 559inline typename RepeatedField<Element>::iterator 560RepeatedField<Element>::end() { 561 return elements_ + current_size_; 562} 563template <typename Element> 564inline typename RepeatedField<Element>::const_iterator 565RepeatedField<Element>::end() const { 566 return elements_ + current_size_; 567} 568 569template <typename Element> 570inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const { 571 return (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0; 572} 573 574// Avoid inlining of Reserve(): new, memcpy, and delete[] lead to a significant 575// amount of code bloat. 576template <typename Element> 577void RepeatedField<Element>::Reserve(int new_size) { 578 if (total_size_ >= new_size) return; 579 580 Element* old_elements = elements_; 581 total_size_ = max(total_size_ * 2, new_size); 582 elements_ = new Element[total_size_]; 583 MoveArray(elements_, old_elements, current_size_); 584 if (old_elements != initial_space_) { 585 delete [] old_elements; 586 } 587} 588 589template <typename Element> 590inline void RepeatedField<Element>::Truncate(int new_size) { 591 GOOGLE_DCHECK_LE(new_size, current_size_); 592 current_size_ = new_size; 593} 594 595template <typename Element> 596inline void RepeatedField<Element>::MoveArray( 597 Element to[], Element from[], int size) { 598 memcpy(to, from, size * sizeof(Element)); 599} 600 601template <typename Element> 602inline void RepeatedField<Element>::CopyArray( 603 Element to[], const Element from[], int size) { 604 memcpy(to, from, size * sizeof(Element)); 605} 606 607 608// ------------------------------------------------------------------- 609 610namespace internal { 611 612inline RepeatedPtrFieldBase::RepeatedPtrFieldBase() 613 : elements_(initial_space_), 614 current_size_(0), 615 allocated_size_(0), 616 total_size_(kInitialSize) { 617} 618 619template <typename TypeHandler> 620void RepeatedPtrFieldBase::Destroy() { 621 for (int i = 0; i < allocated_size_; i++) { 622 TypeHandler::Delete(cast<TypeHandler>(elements_[i])); 623 } 624 if (elements_ != initial_space_) { 625 delete [] elements_; 626 } 627} 628 629inline int RepeatedPtrFieldBase::size() const { 630 return current_size_; 631} 632 633 634template <typename TypeHandler> 635inline const typename TypeHandler::Type& 636RepeatedPtrFieldBase::Get(int index) const { 637 GOOGLE_DCHECK_LT(index, size()); 638 return *cast<TypeHandler>(elements_[index]); 639} 640 641template <typename TypeHandler> 642inline typename TypeHandler::Type* 643RepeatedPtrFieldBase::Mutable(int index) { 644 GOOGLE_DCHECK_LT(index, size()); 645 return cast<TypeHandler>(elements_[index]); 646} 647 648template <typename TypeHandler> 649inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() { 650 if (current_size_ < allocated_size_) { 651 return cast<TypeHandler>(elements_[current_size_++]); 652 } 653 if (allocated_size_ == total_size_) Reserve(total_size_ + 1); 654 ++allocated_size_; 655 typename TypeHandler::Type* result = TypeHandler::New(); 656 elements_[current_size_++] = result; 657 return result; 658} 659 660template <typename TypeHandler> 661inline void RepeatedPtrFieldBase::RemoveLast() { 662 GOOGLE_DCHECK_GT(current_size_, 0); 663 TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_])); 664} 665 666template <typename TypeHandler> 667void RepeatedPtrFieldBase::Clear() { 668 for (int i = 0; i < current_size_; i++) { 669 TypeHandler::Clear(cast<TypeHandler>(elements_[i])); 670 } 671 current_size_ = 0; 672} 673 674template <typename TypeHandler> 675inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) { 676 Reserve(current_size_ + other.current_size_); 677 for (int i = 0; i < other.current_size_; i++) { 678 TypeHandler::Merge(other.Get<TypeHandler>(i), Add<TypeHandler>()); 679 } 680} 681 682inline int RepeatedPtrFieldBase::Capacity() const { 683 return total_size_; 684} 685 686inline void* const* RepeatedPtrFieldBase::raw_data() const { 687 return elements_; 688} 689 690inline void** RepeatedPtrFieldBase::raw_mutable_data() const { 691 return elements_; 692} 693 694template <typename TypeHandler> 695inline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() { 696 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this 697 // method entirely. 698 return reinterpret_cast<typename TypeHandler::Type**>(elements_); 699} 700 701template <typename TypeHandler> 702inline const typename TypeHandler::Type* const* 703RepeatedPtrFieldBase::data() const { 704 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this 705 // method entirely. 706 return reinterpret_cast<const typename TypeHandler::Type* const*>(elements_); 707} 708 709inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) { 710 std::swap(elements_[index1], elements_[index2]); 711} 712 713template <typename TypeHandler> 714inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const { 715 int allocated_bytes = 716 (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0; 717 for (int i = 0; i < allocated_size_; ++i) { 718 allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i])); 719 } 720 return allocated_bytes; 721} 722 723template <typename TypeHandler> 724inline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() { 725 if (current_size_ < allocated_size_) { 726 return cast<TypeHandler>(elements_[current_size_++]); 727 } else { 728 return NULL; 729 } 730} 731 732template <typename TypeHandler> 733void RepeatedPtrFieldBase::AddAllocated( 734 typename TypeHandler::Type* value) { 735 // Make room for the new pointer. 736 if (current_size_ == total_size_) { 737 // The array is completely full with no cleared objects, so grow it. 738 Reserve(total_size_ + 1); 739 ++allocated_size_; 740 } else if (allocated_size_ == total_size_) { 741 // There is no more space in the pointer array because it contains some 742 // cleared objects awaiting reuse. We don't want to grow the array in this 743 // case because otherwise a loop calling AddAllocated() followed by Clear() 744 // would leak memory. 745 TypeHandler::Delete(cast<TypeHandler>(elements_[current_size_])); 746 } else if (current_size_ < allocated_size_) { 747 // We have some cleared objects. We don't care about their order, so we 748 // can just move the first one to the end to make space. 749 elements_[allocated_size_] = elements_[current_size_]; 750 ++allocated_size_; 751 } else { 752 // There are no cleared objects. 753 ++allocated_size_; 754 } 755 756 elements_[current_size_++] = value; 757} 758 759template <typename TypeHandler> 760inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() { 761 GOOGLE_DCHECK_GT(current_size_, 0); 762 typename TypeHandler::Type* result = 763 cast<TypeHandler>(elements_[--current_size_]); 764 --allocated_size_; 765 if (current_size_ < allocated_size_) { 766 // There are cleared elements on the end; replace the removed element 767 // with the last allocated element. 768 elements_[current_size_] = elements_[allocated_size_]; 769 } 770 return result; 771} 772 773 774inline int RepeatedPtrFieldBase::ClearedCount() const { 775 return allocated_size_ - current_size_; 776} 777 778template <typename TypeHandler> 779inline void RepeatedPtrFieldBase::AddCleared( 780 typename TypeHandler::Type* value) { 781 if (allocated_size_ == total_size_) Reserve(total_size_ + 1); 782 elements_[allocated_size_++] = value; 783} 784 785template <typename TypeHandler> 786inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() { 787 GOOGLE_DCHECK_GT(allocated_size_, current_size_); 788 return cast<TypeHandler>(elements_[--allocated_size_]); 789} 790 791} // namespace internal 792 793// ------------------------------------------------------------------- 794 795template <typename Element> 796class RepeatedPtrField<Element>::TypeHandler 797 : public internal::GenericTypeHandler<Element> {}; 798 799template <> 800class RepeatedPtrField<string>::TypeHandler 801 : public internal::StringTypeHandler {}; 802 803 804template <typename Element> 805inline RepeatedPtrField<Element>::RepeatedPtrField() {} 806 807template <typename Element> 808RepeatedPtrField<Element>::~RepeatedPtrField() { 809 Destroy<TypeHandler>(); 810} 811 812template <typename Element> 813inline int RepeatedPtrField<Element>::size() const { 814 return RepeatedPtrFieldBase::size(); 815} 816 817template <typename Element> 818inline const Element& RepeatedPtrField<Element>::Get(int index) const { 819 return RepeatedPtrFieldBase::Get<TypeHandler>(index); 820} 821 822template <typename Element> 823inline Element* RepeatedPtrField<Element>::Mutable(int index) { 824 return RepeatedPtrFieldBase::Mutable<TypeHandler>(index); 825} 826 827template <typename Element> 828inline Element* RepeatedPtrField<Element>::Add() { 829 return RepeatedPtrFieldBase::Add<TypeHandler>(); 830} 831 832template <typename Element> 833inline void RepeatedPtrField<Element>::RemoveLast() { 834 RepeatedPtrFieldBase::RemoveLast<TypeHandler>(); 835} 836 837template <typename Element> 838inline void RepeatedPtrField<Element>::Clear() { 839 RepeatedPtrFieldBase::Clear<TypeHandler>(); 840} 841 842template <typename Element> 843inline void RepeatedPtrField<Element>::MergeFrom( 844 const RepeatedPtrField& other) { 845 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other); 846} 847 848template <typename Element> 849inline Element** RepeatedPtrField<Element>::mutable_data() { 850 return RepeatedPtrFieldBase::mutable_data<TypeHandler>(); 851} 852 853template <typename Element> 854inline const Element* const* RepeatedPtrField<Element>::data() const { 855 return RepeatedPtrFieldBase::data<TypeHandler>(); 856} 857 858template <typename Element> 859void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) { 860 RepeatedPtrFieldBase::Swap(other); 861} 862 863template <typename Element> 864void RepeatedPtrField<Element>::SwapElements(int index1, int index2) { 865 RepeatedPtrFieldBase::SwapElements(index1, index2); 866} 867 868template <typename Element> 869inline int RepeatedPtrField<Element>::SpaceUsedExcludingSelf() const { 870 return RepeatedPtrFieldBase::SpaceUsedExcludingSelf<TypeHandler>(); 871} 872 873template <typename Element> 874inline void RepeatedPtrField<Element>::AddAllocated(Element* value) { 875 RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value); 876} 877 878template <typename Element> 879inline Element* RepeatedPtrField<Element>::ReleaseLast() { 880 return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>(); 881} 882 883 884template <typename Element> 885inline int RepeatedPtrField<Element>::ClearedCount() const { 886 return RepeatedPtrFieldBase::ClearedCount(); 887} 888 889template <typename Element> 890inline void RepeatedPtrField<Element>::AddCleared(Element* value) { 891 return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value); 892} 893 894template <typename Element> 895inline Element* RepeatedPtrField<Element>::ReleaseCleared() { 896 return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>(); 897} 898 899template <typename Element> 900inline void RepeatedPtrField<Element>::Reserve(int new_size) { 901 return RepeatedPtrFieldBase::Reserve(new_size); 902} 903 904template <typename Element> 905inline int RepeatedPtrField<Element>::Capacity() const { 906 return RepeatedPtrFieldBase::Capacity(); 907} 908 909// ------------------------------------------------------------------- 910 911namespace internal { 912 913// STL-like iterator implementation for RepeatedPtrField. You should not 914// refer to this class directly; use RepeatedPtrField<T>::iterator instead. 915// 916// The iterator for RepeatedPtrField<T>, RepeatedPtrIterator<T>, is 917// very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors-inl.h, 918// but adds random-access operators and is modified to wrap a void** base 919// iterator (since RepeatedPtrField stores its array as a void* array and 920// casting void** to T** would violate C++ aliasing rules). 921// 922// This code based on net/proto/proto-array-internal.h by Jeffrey Yasskin 923// (jyasskin@google.com). 924template<typename Element> 925class RepeatedPtrIterator 926 : public std::iterator< 927 std::random_access_iterator_tag, Element> { 928 public: 929 typedef RepeatedPtrIterator<Element> iterator; 930 typedef std::iterator< 931 std::random_access_iterator_tag, Element> superclass; 932 933 // Let the compiler know that these are type names, so we don't have to 934 // write "typename" in front of them everywhere. 935 typedef typename superclass::reference reference; 936 typedef typename superclass::pointer pointer; 937 typedef typename superclass::difference_type difference_type; 938 939 RepeatedPtrIterator() : it_(NULL) {} 940 explicit RepeatedPtrIterator(void* const* it) : it_(it) {} 941 942 // Allow "upcasting" from RepeatedPtrIterator<T**> to 943 // RepeatedPtrIterator<const T*const*>. 944 template<typename OtherElement> 945 RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other) 946 : it_(other.it_) { 947 // Force a compiler error if the other type is not convertable to ours. 948 if (false) { 949 implicit_cast<Element*, OtherElement*>(0); 950 } 951 } 952 953 // dereferenceable 954 reference operator*() const { return *reinterpret_cast<Element*>(*it_); } 955 pointer operator->() const { return &(operator*()); } 956 957 // {inc,dec}rementable 958 iterator& operator++() { ++it_; return *this; } 959 iterator operator++(int) { return iterator(it_++); } 960 iterator& operator--() { --it_; return *this; } 961 iterator operator--(int) { return iterator(it_--); } 962 963 // equality_comparable 964 bool operator==(const iterator& x) const { return it_ == x.it_; } 965 bool operator!=(const iterator& x) const { return it_ != x.it_; } 966 967 // less_than_comparable 968 bool operator<(const iterator& x) const { return it_ < x.it_; } 969 bool operator<=(const iterator& x) const { return it_ <= x.it_; } 970 bool operator>(const iterator& x) const { return it_ > x.it_; } 971 bool operator>=(const iterator& x) const { return it_ >= x.it_; } 972 973 // addable, subtractable 974 iterator& operator+=(difference_type d) { 975 it_ += d; 976 return *this; 977 } 978 friend iterator operator+(iterator it, difference_type d) { 979 it += d; 980 return it; 981 } 982 friend iterator operator+(difference_type d, iterator it) { 983 it += d; 984 return it; 985 } 986 iterator& operator-=(difference_type d) { 987 it_ -= d; 988 return *this; 989 } 990 friend iterator operator-(iterator it, difference_type d) { 991 it -= d; 992 return it; 993 } 994 995 // indexable 996 reference operator[](difference_type d) const { return *(*this + d); } 997 998 // random access iterator 999 difference_type operator-(const iterator& x) const { return it_ - x.it_; } 1000 1001 private: 1002 template<typename OtherElement> 1003 friend class RepeatedPtrIterator; 1004 1005 // The internal iterator. 1006 void* const* it_; 1007}; 1008 1009// Provide an iterator that operates on pointers to the underlying objects 1010// rather than the objects themselves as RepeatedPtrIterator does. 1011// Consider using this when working with stl algorithms that change 1012// the array. 1013template<typename Element> 1014class RepeatedPtrOverPtrsIterator 1015 : public std::iterator<std::random_access_iterator_tag, Element*> { 1016 public: 1017 typedef RepeatedPtrOverPtrsIterator<Element> iterator; 1018 typedef std::iterator< 1019 std::random_access_iterator_tag, Element*> superclass; 1020 1021 // Let the compiler know that these are type names, so we don't have to 1022 // write "typename" in front of them everywhere. 1023 typedef typename superclass::reference reference; 1024 typedef typename superclass::pointer pointer; 1025 typedef typename superclass::difference_type difference_type; 1026 1027 RepeatedPtrOverPtrsIterator() : it_(NULL) {} 1028 explicit RepeatedPtrOverPtrsIterator(void** it) : it_(it) {} 1029 1030 // dereferenceable 1031 reference operator*() const { return *reinterpret_cast<Element**>(it_); } 1032 pointer operator->() const { return &(operator*()); } 1033 1034 // {inc,dec}rementable 1035 iterator& operator++() { ++it_; return *this; } 1036 iterator operator++(int) { return iterator(it_++); } 1037 iterator& operator--() { --it_; return *this; } 1038 iterator operator--(int) { return iterator(it_--); } 1039 1040 // equality_comparable 1041 bool operator==(const iterator& x) const { return it_ == x.it_; } 1042 bool operator!=(const iterator& x) const { return it_ != x.it_; } 1043 1044 // less_than_comparable 1045 bool operator<(const iterator& x) const { return it_ < x.it_; } 1046 bool operator<=(const iterator& x) const { return it_ <= x.it_; } 1047 bool operator>(const iterator& x) const { return it_ > x.it_; } 1048 bool operator>=(const iterator& x) const { return it_ >= x.it_; } 1049 1050 // addable, subtractable 1051 iterator& operator+=(difference_type d) { 1052 it_ += d; 1053 return *this; 1054 } 1055 friend iterator operator+(iterator it, difference_type d) { 1056 it += d; 1057 return it; 1058 } 1059 friend iterator operator+(difference_type d, iterator it) { 1060 it += d; 1061 return it; 1062 } 1063 iterator& operator-=(difference_type d) { 1064 it_ -= d; 1065 return *this; 1066 } 1067 friend iterator operator-(iterator it, difference_type d) { 1068 it -= d; 1069 return it; 1070 } 1071 1072 // indexable 1073 reference operator[](difference_type d) const { return *(*this + d); } 1074 1075 // random access iterator 1076 difference_type operator-(const iterator& x) const { return it_ - x.it_; } 1077 1078 private: 1079 template<typename OtherElement> 1080 friend class RepeatedPtrIterator; 1081 1082 // The internal iterator. 1083 void** it_; 1084}; 1085 1086 1087} // namespace internal 1088 1089template <typename Element> 1090inline typename RepeatedPtrField<Element>::iterator 1091RepeatedPtrField<Element>::begin() { 1092 return iterator(raw_data()); 1093} 1094template <typename Element> 1095inline typename RepeatedPtrField<Element>::const_iterator 1096RepeatedPtrField<Element>::begin() const { 1097 return iterator(raw_data()); 1098} 1099template <typename Element> 1100inline typename RepeatedPtrField<Element>::iterator 1101RepeatedPtrField<Element>::end() { 1102 return iterator(raw_data() + size()); 1103} 1104template <typename Element> 1105inline typename RepeatedPtrField<Element>::const_iterator 1106RepeatedPtrField<Element>::end() const { 1107 return iterator(raw_data() + size()); 1108} 1109 1110template <typename Element> 1111inline typename RepeatedPtrField<Element>::pointer_iterator 1112RepeatedPtrField<Element>::pointer_begin() { 1113 return pointer_iterator(raw_mutable_data()); 1114} 1115template <typename Element> 1116inline typename RepeatedPtrField<Element>::pointer_iterator 1117RepeatedPtrField<Element>::pointer_end() { 1118 return pointer_iterator(raw_mutable_data() + size()); 1119} 1120 1121 1122// Iterators and helper functions that follow the spirit of the STL 1123// std::back_insert_iterator and std::back_inserter but are tailor-made 1124// for RepeatedField and RepatedPtrField. Typical usage would be: 1125// 1126// std::copy(some_sequence.begin(), some_sequence.end(), 1127// google::protobuf::RepeatedFieldBackInserter(proto.mutable_sequence())); 1128// 1129// Ported by johannes from util/gtl/proto-array-iterators-inl.h 1130 1131namespace internal { 1132// A back inserter for RepeatedField objects. 1133template<typename T> class RepeatedFieldBackInsertIterator 1134 : public std::iterator<std::output_iterator_tag, T> { 1135 public: 1136 explicit RepeatedFieldBackInsertIterator( 1137 RepeatedField<T>* const mutable_field) 1138 : field_(mutable_field) { 1139 } 1140 RepeatedFieldBackInsertIterator<T>& operator=(const T& value) { 1141 field_->Add(value); 1142 return *this; 1143 } 1144 RepeatedFieldBackInsertIterator<T>& operator*() { 1145 return *this; 1146 } 1147 RepeatedFieldBackInsertIterator<T>& operator++() { 1148 return *this; 1149 } 1150 RepeatedFieldBackInsertIterator<T>& operator++(int ignores_parameter) { 1151 return *this; 1152 } 1153 1154 private: 1155 RepeatedField<T>* const field_; 1156}; 1157 1158// A back inserter for RepeatedPtrField objects. 1159template<typename T> class RepeatedPtrFieldBackInsertIterator 1160 : public std::iterator<std::output_iterator_tag, T> { 1161 public: 1162 RepeatedPtrFieldBackInsertIterator( 1163 RepeatedPtrField<T>* const mutable_field) 1164 : field_(mutable_field) { 1165 } 1166 RepeatedPtrFieldBackInsertIterator<T>& operator=(const T& value) { 1167 *field_->Add() = value; 1168 return *this; 1169 } 1170 RepeatedPtrFieldBackInsertIterator<T>& operator=( 1171 const T* const ptr_to_value) { 1172 *field_->Add() = *ptr_to_value; 1173 return *this; 1174 } 1175 RepeatedPtrFieldBackInsertIterator<T>& operator*() { 1176 return *this; 1177 } 1178 RepeatedPtrFieldBackInsertIterator<T>& operator++() { 1179 return *this; 1180 } 1181 RepeatedPtrFieldBackInsertIterator<T>& operator++(int ignores_parameter) { 1182 return *this; 1183 } 1184 1185 private: 1186 RepeatedPtrField<T>* const field_; 1187}; 1188 1189// A back inserter for RepeatedPtrFields that inserts by transfering ownership 1190// of a pointer. 1191template<typename T> class AllocatedRepeatedPtrFieldBackInsertIterator 1192 : public std::iterator<std::output_iterator_tag, T> { 1193 public: 1194 explicit AllocatedRepeatedPtrFieldBackInsertIterator( 1195 RepeatedPtrField<T>* const mutable_field) 1196 : field_(mutable_field) { 1197 } 1198 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator=( 1199 T* const ptr_to_value) { 1200 field_->AddAllocated(ptr_to_value); 1201 return *this; 1202 } 1203 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator*() { 1204 return *this; 1205 } 1206 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++() { 1207 return *this; 1208 } 1209 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++( 1210 int ignores_parameter) { 1211 return *this; 1212 } 1213 1214 private: 1215 RepeatedPtrField<T>* const field_; 1216}; 1217} // namespace internal 1218 1219// Provides a back insert iterator for RepeatedField instances, 1220// similar to std::back_inserter(). Note the identically named 1221// function for RepeatedPtrField instances. 1222template<typename T> internal::RepeatedFieldBackInsertIterator<T> 1223RepeatedFieldBackInserter(RepeatedField<T>* const mutable_field) { 1224 return internal::RepeatedFieldBackInsertIterator<T>(mutable_field); 1225} 1226 1227// Provides a back insert iterator for RepeatedPtrField instances, 1228// similar to std::back_inserter(). Note the identically named 1229// function for RepeatedField instances. 1230template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> 1231RepeatedFieldBackInserter(RepeatedPtrField<T>* const mutable_field) { 1232 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field); 1233} 1234 1235// Provides a back insert iterator for RepeatedPtrField instances 1236// similar to std::back_inserter() which transfers the ownership while 1237// copying elements. 1238template<typename T> internal::AllocatedRepeatedPtrFieldBackInsertIterator<T> 1239AllocatedRepeatedPtrFieldBackInserter( 1240 RepeatedPtrField<T>* const mutable_field) { 1241 return internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>( 1242 mutable_field); 1243} 1244 1245} // namespace protobuf 1246 1247} // namespace google 1248#endif // GOOGLE_PROTOBUF_REPEATED_FIELD_H__ 1249