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