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