1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 // http://code.google.com/p/protobuf/
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
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
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.
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.
31 // Author: kenton@google.com (Kenton Varda)
32 // Based on original Protocol Buffers design by
33 // Sanjay Ghemawat, Jeff Dean, and others.
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.
42 // Typically, clients should not need to access RepeatedField objects directly,
43 // but should instead use the accessor functions generated automatically by the
46 #ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__
47 #define GOOGLE_PROTOBUF_REPEATED_FIELD_H__
52 #include <google/protobuf/stubs/common.h>
53 #include <google/protobuf/stubs/type_traits.h>
54 #include <google/protobuf/generated_message_util.h>
55 #include <google/protobuf/message_lite.h>
60 namespace google_opensource {
62 } // namespace google_opensource
71 static const int kMinRepeatedFieldAllocationSize = 4;
73 // A utility function for logging that doesn't need any template types.
74 void LogIndexOutOfBounds(int index, int size);
75 } // namespace internal
78 // RepeatedField is used to represent repeated fields of a primitive type (in
79 // other words, everything except strings and nested Messages). Most users will
80 // not ever use a RepeatedField directly; they will use the get-by-index,
81 // set-by-index, and add accessors that are generated for all repeated fields.
82 template <typename Element>
86 RepeatedField(const RepeatedField& other);
87 template <typename Iter>
88 RepeatedField(Iter begin, const Iter& end);
91 RepeatedField& operator=(const RepeatedField& other);
95 const Element& Get(int index) const;
96 Element* Mutable(int index);
97 void Set(int index, const Element& value);
98 void Add(const Element& value);
100 // Remove the last element in the array.
103 // Extract elements with indices in "[start .. start+num-1]".
104 // Copy them into "elements[0 .. num-1]" if "elements" is not NULL.
105 // Caution: implementation also moves elements with indices [start+num ..].
106 // Calling this routine inside a loop can cause quadratic behavior.
107 void ExtractSubrange(int start, int num, Element* elements);
110 void MergeFrom(const RepeatedField& other);
111 void CopyFrom(const RepeatedField& other);
113 // Reserve space to expand the field to at least the given size. If the
114 // array is grown, it will always be at least doubled in size.
115 void Reserve(int new_size);
117 // Resize the RepeatedField to a new, smaller size. This is O(1).
118 void Truncate(int new_size);
120 void AddAlreadyReserved(const Element& value);
121 Element* AddAlreadyReserved();
122 int Capacity() const;
124 // Gets the underlying array. This pointer is possibly invalidated by
125 // any add or remove operation.
126 Element* mutable_data();
127 const Element* data() const;
129 // Swap entire contents with "other".
130 void Swap(RepeatedField* other);
132 // Swap two elements.
133 void SwapElements(int index1, int index2);
135 // STL-like iterator support
136 typedef Element* iterator;
137 typedef const Element* const_iterator;
138 typedef Element value_type;
139 typedef value_type& reference;
140 typedef const value_type& const_reference;
141 typedef value_type* pointer;
142 typedef const value_type* const_pointer;
143 typedef int size_type;
144 typedef ptrdiff_t difference_type;
147 const_iterator begin() const;
149 const_iterator end() const;
151 // Reverse iterator support
152 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
153 typedef std::reverse_iterator<iterator> reverse_iterator;
154 reverse_iterator rbegin() {
155 return reverse_iterator(end());
157 const_reverse_iterator rbegin() const {
158 return const_reverse_iterator(end());
160 reverse_iterator rend() {
161 return reverse_iterator(begin());
163 const_reverse_iterator rend() const {
164 return const_reverse_iterator(begin());
167 // Returns the number of bytes used by the repeated field, excluding
169 int SpaceUsedExcludingSelf() const;
172 static const int kInitialSize = 0;
178 // Move the contents of |from| into |to|, possibly clobbering |from| in the
179 // process. For primitive types this is just a memcpy(), but it could be
180 // specialized for non-primitive types to, say, swap each element instead.
181 void MoveArray(Element to[], Element from[], int size);
183 // Copy the elements of |from| into |to|.
184 void CopyArray(Element to[], const Element from[], int size);
188 template <typename It> class RepeatedPtrIterator;
189 template <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator;
190 } // namespace internal
194 // This is a helper template to copy an array of elements effeciently when they
195 // have a trivial copy constructor, and correctly otherwise. This really
196 // shouldn't be necessary, but our compiler doesn't optimize std::copy very
198 template <typename Element,
199 bool HasTrivialCopy = has_trivial_copy<Element>::value>
200 struct ElementCopier {
201 void operator()(Element to[], const Element from[], int array_size);
204 } // namespace internal
208 // This is the common base class for RepeatedPtrFields. It deals only in void*
209 // pointers. Users should not use this interface directly.
211 // The methods of this interface correspond to the methods of RepeatedPtrField,
212 // but may have a template argument called TypeHandler. Its signature is:
213 // class TypeHandler {
215 // typedef MyType Type;
216 // static Type* New();
217 // static void Delete(Type*);
218 // static void Clear(Type*);
219 // static void Merge(const Type& from, Type* to);
221 // // Only needs to be implemented if SpaceUsedExcludingSelf() is called.
222 // static int SpaceUsed(const Type&);
224 class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase {
226 // The reflection implementation needs to call protected methods directly,
227 // reinterpreting pointers as being to Message instead of a specific Message
229 friend class GeneratedMessageReflection;
231 // ExtensionSet stores repeated message extensions as
232 // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to
233 // implement SpaceUsed(), and thus need to call SpaceUsedExcludingSelf()
234 // reinterpreting MessageLite as Message. ExtensionSet also needs to make
235 // use of AddFromCleared(), which is not part of the public interface.
236 friend class ExtensionSet;
238 // To parse directly into a proto2 generated class, the upb class GMR_Handlers
239 // needs to be able to modify a RepeatedPtrFieldBase directly.
240 friend class LIBPROTOBUF_EXPORT upb::google_opensource::GMR_Handlers;
242 RepeatedPtrFieldBase();
244 // Must be called from destructor.
245 template <typename TypeHandler>
250 template <typename TypeHandler>
251 const typename TypeHandler::Type& Get(int index) const;
252 template <typename TypeHandler>
253 typename TypeHandler::Type* Mutable(int index);
254 template <typename TypeHandler>
255 typename TypeHandler::Type* Add();
256 template <typename TypeHandler>
258 template <typename TypeHandler>
260 template <typename TypeHandler>
261 void MergeFrom(const RepeatedPtrFieldBase& other);
262 template <typename TypeHandler>
263 void CopyFrom(const RepeatedPtrFieldBase& other);
265 void CloseGap(int start, int num) {
266 // Close up a gap of "num" elements starting at offset "start".
267 for (int i = start + num; i < allocated_size_; ++i)
268 elements_[i - num] = elements_[i];
269 current_size_ -= num;
270 allocated_size_ -= num;
273 void Reserve(int new_size);
275 int Capacity() const;
277 // Used for constructing iterators.
278 void* const* raw_data() const;
279 void** raw_mutable_data() const;
281 template <typename TypeHandler>
282 typename TypeHandler::Type** mutable_data();
283 template <typename TypeHandler>
284 const typename TypeHandler::Type* const* data() const;
286 void Swap(RepeatedPtrFieldBase* other);
288 void SwapElements(int index1, int index2);
290 template <typename TypeHandler>
291 int SpaceUsedExcludingSelf() const;
294 // Advanced memory management --------------------------------------
296 // Like Add(), but if there are no cleared objects to use, returns NULL.
297 template <typename TypeHandler>
298 typename TypeHandler::Type* AddFromCleared();
300 template <typename TypeHandler>
301 void AddAllocated(typename TypeHandler::Type* value);
302 template <typename TypeHandler>
303 typename TypeHandler::Type* ReleaseLast();
305 int ClearedCount() const;
306 template <typename TypeHandler>
307 void AddCleared(typename TypeHandler::Type* value);
308 template <typename TypeHandler>
309 typename TypeHandler::Type* ReleaseCleared();
312 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase);
314 static const int kInitialSize = 0;
321 template <typename TypeHandler>
322 static inline typename TypeHandler::Type* cast(void* element) {
323 return reinterpret_cast<typename TypeHandler::Type*>(element);
325 template <typename TypeHandler>
326 static inline const typename TypeHandler::Type* cast(const void* element) {
327 return reinterpret_cast<const typename TypeHandler::Type*>(element);
331 template <typename GenericType>
332 class GenericTypeHandler {
334 typedef GenericType Type;
335 static GenericType* New() { return new GenericType; }
336 static void Delete(GenericType* value) { delete value; }
337 static void Clear(GenericType* value) { value->Clear(); }
338 static void Merge(const GenericType& from, GenericType* to) {
341 static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); }
342 static const Type& default_instance() { return Type::default_instance(); }
346 inline void GenericTypeHandler<MessageLite>::Merge(
347 const MessageLite& from, MessageLite* to) {
348 to->CheckTypeAndMergeFrom(from);
352 inline const MessageLite& GenericTypeHandler<MessageLite>::default_instance() {
353 // Yes, the behavior of the code is undefined, but this function is only
354 // called when we're already deep into the world of undefined, because the
355 // caller called Get(index) out of bounds.
356 MessageLite* null = NULL;
361 inline const Message& GenericTypeHandler<Message>::default_instance() {
362 // Yes, the behavior of the code is undefined, but this function is only
363 // called when we're already deep into the world of undefined, because the
364 // caller called Get(index) out of bounds.
365 Message* null = NULL;
370 // HACK: If a class is declared as DLL-exported in MSVC, it insists on
371 // generating copies of all its methods -- even inline ones -- to include
372 // in the DLL. But SpaceUsed() calls StringSpaceUsedExcludingSelf() which
373 // isn't in the lite library, therefore the lite library cannot link if
374 // StringTypeHandler is exported. So, we factor out StringTypeHandlerBase,
375 // export that, then make StringTypeHandler be a subclass which is NOT
377 // TODO(kenton): There has to be a better way.
378 class LIBPROTOBUF_EXPORT StringTypeHandlerBase {
381 static string* New();
382 static void Delete(string* value);
383 static void Clear(string* value) { value->clear(); }
384 static void Merge(const string& from, string* to) { *to = from; }
385 static const Type& default_instance() {
386 return ::google::protobuf::internal::kEmptyString;
390 class StringTypeHandler : public StringTypeHandlerBase {
392 static int SpaceUsed(const string& value) {
393 return sizeof(value) + StringSpaceUsedExcludingSelf(value);
398 } // namespace internal
400 // RepeatedPtrField is like RepeatedField, but used for repeated strings or
402 template <typename Element>
403 class RepeatedPtrField : public internal::RepeatedPtrFieldBase {
406 RepeatedPtrField(const RepeatedPtrField& other);
407 template <typename Iter>
408 RepeatedPtrField(Iter begin, const Iter& end);
411 RepeatedPtrField& operator=(const RepeatedPtrField& other);
415 const Element& Get(int index) const;
416 Element* Mutable(int index);
419 // Remove the last element in the array.
420 // Ownership of the element is retained by the array.
423 // Delete elements with indices in the range [start .. start+num-1].
424 // Caution: implementation moves all elements with indices [start+num .. ].
425 // Calling this routine inside a loop can cause quadratic behavior.
426 void DeleteSubrange(int start, int num);
429 void MergeFrom(const RepeatedPtrField& other);
430 void CopyFrom(const RepeatedPtrField& other);
432 // Reserve space to expand the field to at least the given size. This only
433 // resizes the pointer array; it doesn't allocate any objects. If the
434 // array is grown, it will always be at least doubled in size.
435 void Reserve(int new_size);
437 int Capacity() const;
439 // Gets the underlying array. This pointer is possibly invalidated by
440 // any add or remove operation.
441 Element** mutable_data();
442 const Element* const* data() const;
444 // Swap entire contents with "other".
445 void Swap(RepeatedPtrField* other);
447 // Swap two elements.
448 void SwapElements(int index1, int index2);
450 // STL-like iterator support
451 typedef internal::RepeatedPtrIterator<Element> iterator;
452 typedef internal::RepeatedPtrIterator<const Element> const_iterator;
453 typedef Element value_type;
454 typedef value_type& reference;
455 typedef const value_type& const_reference;
456 typedef value_type* pointer;
457 typedef const value_type* const_pointer;
458 typedef int size_type;
459 typedef ptrdiff_t difference_type;
462 const_iterator begin() const;
464 const_iterator end() const;
466 // Reverse iterator support
467 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
468 typedef std::reverse_iterator<iterator> reverse_iterator;
469 reverse_iterator rbegin() {
470 return reverse_iterator(end());
472 const_reverse_iterator rbegin() const {
473 return const_reverse_iterator(end());
475 reverse_iterator rend() {
476 return reverse_iterator(begin());
478 const_reverse_iterator rend() const {
479 return const_reverse_iterator(begin());
482 // Custom STL-like iterator that iterates over and returns the underlying
483 // pointers to Element rather than Element itself.
484 typedef internal::RepeatedPtrOverPtrsIterator<Element, void*>
486 typedef internal::RepeatedPtrOverPtrsIterator<const Element, const void*>
487 const_pointer_iterator;
488 pointer_iterator pointer_begin();
489 const_pointer_iterator pointer_begin() const;
490 pointer_iterator pointer_end();
491 const_pointer_iterator pointer_end() const;
493 // Returns (an estimate of) the number of bytes used by the repeated field,
494 // excluding sizeof(*this).
495 int SpaceUsedExcludingSelf() const;
497 // Advanced memory management --------------------------------------
498 // When hardcore memory management becomes necessary -- as it sometimes
499 // does here at Google -- the following methods may be useful.
501 // Add an already-allocated object, passing ownership to the
503 void AddAllocated(Element* value);
504 // Remove the last element and return it, passing ownership to the caller.
505 // Requires: size() > 0
506 Element* ReleaseLast();
508 // Extract elements with indices in the range "[start .. start+num-1]".
509 // The caller assumes ownership of the extracted elements and is responsible
510 // for deleting them when they are no longer needed.
511 // If "elements" is non-NULL, then pointers to the extracted elements
512 // are stored in "elements[0 .. num-1]" for the convenience of the caller.
513 // If "elements" is NULL, then the caller must use some other mechanism
514 // to perform any further operations (like deletion) on these elements.
515 // Caution: implementation also moves elements with indices [start+num ..].
516 // Calling this routine inside a loop can cause quadratic behavior.
517 void ExtractSubrange(int start, int num, Element** elements);
519 // When elements are removed by calls to RemoveLast() or Clear(), they
520 // are not actually freed. Instead, they are cleared and kept so that
521 // they can be reused later. This can save lots of CPU time when
522 // repeatedly reusing a protocol message for similar purposes.
524 // Hardcore programs may choose to manipulate these cleared objects
525 // to better optimize memory management using the following routines.
527 // Get the number of cleared objects that are currently being kept
529 int ClearedCount() const;
530 // Add an element to the pool of cleared objects, passing ownership to
531 // the RepeatedPtrField. The element must be cleared prior to calling
533 void AddCleared(Element* value);
534 // Remove a single element from the cleared pool and return it, passing
535 // ownership to the caller. The element is guaranteed to be cleared.
536 // Requires: ClearedCount() > 0
537 Element* ReleaseCleared();
540 // Note: RepeatedPtrField SHOULD NOT be subclassed by users. We only
541 // subclass it in one place as a hack for compatibility with proto1. The
542 // subclass needs to know about TypeHandler in order to call protected
543 // methods on RepeatedPtrFieldBase.
548 // implementation ====================================================
550 template <typename Element>
551 inline RepeatedField<Element>::RepeatedField()
554 total_size_(kInitialSize) {
557 template <typename Element>
558 inline RepeatedField<Element>::RepeatedField(const RepeatedField& other)
561 total_size_(kInitialSize) {
565 template <typename Element>
566 template <typename Iter>
567 inline RepeatedField<Element>::RepeatedField(Iter begin, const Iter& end)
570 total_size_(kInitialSize) {
571 for (; begin != end; ++begin) {
576 template <typename Element>
577 RepeatedField<Element>::~RepeatedField() {
581 template <typename Element>
582 inline RepeatedField<Element>&
583 RepeatedField<Element>::operator=(const RepeatedField& other) {
589 template <typename Element>
590 inline int RepeatedField<Element>::size() const {
591 return current_size_;
594 template <typename Element>
595 inline int RepeatedField<Element>::Capacity() const {
599 template<typename Element>
600 inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) {
601 GOOGLE_DCHECK_LT(size(), Capacity());
602 elements_[current_size_++] = value;
605 template<typename Element>
606 inline Element* RepeatedField<Element>::AddAlreadyReserved() {
607 GOOGLE_DCHECK_LT(size(), Capacity());
608 return &elements_[current_size_++];
611 template <typename Element>
612 inline const Element& RepeatedField<Element>::Get(int index) const {
613 GOOGLE_DCHECK_LT(index, size());
614 return elements_[index];
617 template <typename Element>
618 inline Element* RepeatedField<Element>::Mutable(int index) {
619 GOOGLE_DCHECK_LT(index, size());
620 return elements_ + index;
623 template <typename Element>
624 inline void RepeatedField<Element>::Set(int index, const Element& value) {
625 GOOGLE_DCHECK_LT(index, size());
626 elements_[index] = value;
629 template <typename Element>
630 inline void RepeatedField<Element>::Add(const Element& value) {
631 if (current_size_ == total_size_) Reserve(total_size_ + 1);
632 elements_[current_size_++] = value;
635 template <typename Element>
636 inline Element* RepeatedField<Element>::Add() {
637 if (current_size_ == total_size_) Reserve(total_size_ + 1);
638 return &elements_[current_size_++];
641 template <typename Element>
642 inline void RepeatedField<Element>::RemoveLast() {
643 GOOGLE_DCHECK_GT(current_size_, 0);
647 template <typename Element>
648 void RepeatedField<Element>::ExtractSubrange(
649 int start, int num, Element* elements) {
650 GOOGLE_DCHECK_GE(start, 0);
651 GOOGLE_DCHECK_GE(num, 0);
652 GOOGLE_DCHECK_LE(start + num, this->size());
654 // Save the values of the removed elements if requested.
655 if (elements != NULL) {
656 for (int i = 0; i < num; ++i)
657 elements[i] = this->Get(i + start);
660 // Slide remaining elements down to fill the gap.
662 for (int i = start + num; i < this->size(); ++i)
663 this->Set(i - num, this->Get(i));
664 this->Truncate(this->size() - num);
668 template <typename Element>
669 inline void RepeatedField<Element>::Clear() {
673 template <typename Element>
674 inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) {
675 if (other.current_size_ != 0) {
676 Reserve(current_size_ + other.current_size_);
677 CopyArray(elements_ + current_size_, other.elements_, other.current_size_);
678 current_size_ += other.current_size_;
682 template <typename Element>
683 inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) {
688 template <typename Element>
689 inline Element* RepeatedField<Element>::mutable_data() {
693 template <typename Element>
694 inline const Element* RepeatedField<Element>::data() const {
699 template <typename Element>
700 void RepeatedField<Element>::Swap(RepeatedField* other) {
701 if (this == other) return;
702 Element* swap_elements = elements_;
703 int swap_current_size = current_size_;
704 int swap_total_size = total_size_;
706 elements_ = other->elements_;
707 current_size_ = other->current_size_;
708 total_size_ = other->total_size_;
710 other->elements_ = swap_elements;
711 other->current_size_ = swap_current_size;
712 other->total_size_ = swap_total_size;
715 template <typename Element>
716 void RepeatedField<Element>::SwapElements(int index1, int index2) {
717 std::swap(elements_[index1], elements_[index2]);
720 template <typename Element>
721 inline typename RepeatedField<Element>::iterator
722 RepeatedField<Element>::begin() {
725 template <typename Element>
726 inline typename RepeatedField<Element>::const_iterator
727 RepeatedField<Element>::begin() const {
730 template <typename Element>
731 inline typename RepeatedField<Element>::iterator
732 RepeatedField<Element>::end() {
733 return elements_ + current_size_;
735 template <typename Element>
736 inline typename RepeatedField<Element>::const_iterator
737 RepeatedField<Element>::end() const {
738 return elements_ + current_size_;
741 template <typename Element>
742 inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const {
743 return (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
746 // Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant
747 // amount of code bloat.
748 template <typename Element>
749 void RepeatedField<Element>::Reserve(int new_size) {
750 if (total_size_ >= new_size) return;
752 Element* old_elements = elements_;
753 total_size_ = max(google::protobuf::internal::kMinRepeatedFieldAllocationSize,
754 max(total_size_ * 2, new_size));
755 elements_ = new Element[total_size_];
756 if (old_elements != NULL) {
757 MoveArray(elements_, old_elements, current_size_);
758 delete [] old_elements;
762 template <typename Element>
763 inline void RepeatedField<Element>::Truncate(int new_size) {
764 GOOGLE_DCHECK_LE(new_size, current_size_);
765 current_size_ = new_size;
768 template <typename Element>
769 inline void RepeatedField<Element>::MoveArray(
770 Element to[], Element from[], int array_size) {
771 CopyArray(to, from, array_size);
774 template <typename Element>
775 inline void RepeatedField<Element>::CopyArray(
776 Element to[], const Element from[], int array_size) {
777 internal::ElementCopier<Element>()(to, from, array_size);
782 template <typename Element, bool HasTrivialCopy>
783 void ElementCopier<Element, HasTrivialCopy>::operator()(
784 Element to[], const Element from[], int array_size) {
785 std::copy(from, from + array_size, to);
788 template <typename Element>
789 struct ElementCopier<Element, true> {
790 void operator()(Element to[], const Element from[], int array_size) {
791 memcpy(to, from, array_size * sizeof(Element));
795 } // namespace internal
798 // -------------------------------------------------------------------
802 inline RepeatedPtrFieldBase::RepeatedPtrFieldBase()
806 total_size_(kInitialSize) {
809 template <typename TypeHandler>
810 void RepeatedPtrFieldBase::Destroy() {
811 for (int i = 0; i < allocated_size_; i++) {
812 TypeHandler::Delete(cast<TypeHandler>(elements_[i]));
817 inline int RepeatedPtrFieldBase::size() const {
818 return current_size_;
821 template <typename TypeHandler>
822 inline const typename TypeHandler::Type&
823 RepeatedPtrFieldBase::Get(int index) const {
824 GOOGLE_DCHECK_LT(index, size());
825 return *cast<TypeHandler>(elements_[index]);
829 template <typename TypeHandler>
830 inline typename TypeHandler::Type*
831 RepeatedPtrFieldBase::Mutable(int index) {
832 GOOGLE_DCHECK_LT(index, size());
833 return cast<TypeHandler>(elements_[index]);
836 template <typename TypeHandler>
837 inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() {
838 if (current_size_ < allocated_size_) {
839 return cast<TypeHandler>(elements_[current_size_++]);
841 if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
843 typename TypeHandler::Type* result = TypeHandler::New();
844 elements_[current_size_++] = result;
848 template <typename TypeHandler>
849 inline void RepeatedPtrFieldBase::RemoveLast() {
850 GOOGLE_DCHECK_GT(current_size_, 0);
851 TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_]));
854 template <typename TypeHandler>
855 void RepeatedPtrFieldBase::Clear() {
856 for (int i = 0; i < current_size_; i++) {
857 TypeHandler::Clear(cast<TypeHandler>(elements_[i]));
862 template <typename TypeHandler>
863 inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) {
864 Reserve(current_size_ + other.current_size_);
865 for (int i = 0; i < other.current_size_; i++) {
866 TypeHandler::Merge(other.template Get<TypeHandler>(i), Add<TypeHandler>());
870 template <typename TypeHandler>
871 inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) {
872 RepeatedPtrFieldBase::Clear<TypeHandler>();
873 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
876 inline int RepeatedPtrFieldBase::Capacity() const {
880 inline void* const* RepeatedPtrFieldBase::raw_data() const {
884 inline void** RepeatedPtrFieldBase::raw_mutable_data() const {
888 template <typename TypeHandler>
889 inline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() {
890 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this
892 return reinterpret_cast<typename TypeHandler::Type**>(elements_);
895 template <typename TypeHandler>
896 inline const typename TypeHandler::Type* const*
897 RepeatedPtrFieldBase::data() const {
898 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this
900 return reinterpret_cast<const typename TypeHandler::Type* const*>(elements_);
903 inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) {
904 std::swap(elements_[index1], elements_[index2]);
907 template <typename TypeHandler>
908 inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const {
909 int allocated_bytes =
910 (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
911 for (int i = 0; i < allocated_size_; ++i) {
912 allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i]));
914 return allocated_bytes;
917 template <typename TypeHandler>
918 inline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() {
919 if (current_size_ < allocated_size_) {
920 return cast<TypeHandler>(elements_[current_size_++]);
926 template <typename TypeHandler>
927 void RepeatedPtrFieldBase::AddAllocated(
928 typename TypeHandler::Type* value) {
929 // Make room for the new pointer.
930 if (current_size_ == total_size_) {
931 // The array is completely full with no cleared objects, so grow it.
932 Reserve(total_size_ + 1);
934 } else if (allocated_size_ == total_size_) {
935 // There is no more space in the pointer array because it contains some
936 // cleared objects awaiting reuse. We don't want to grow the array in this
937 // case because otherwise a loop calling AddAllocated() followed by Clear()
938 // would leak memory.
939 TypeHandler::Delete(cast<TypeHandler>(elements_[current_size_]));
940 } else if (current_size_ < allocated_size_) {
941 // We have some cleared objects. We don't care about their order, so we
942 // can just move the first one to the end to make space.
943 elements_[allocated_size_] = elements_[current_size_];
946 // There are no cleared objects.
950 elements_[current_size_++] = value;
953 template <typename TypeHandler>
954 inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() {
955 GOOGLE_DCHECK_GT(current_size_, 0);
956 typename TypeHandler::Type* result =
957 cast<TypeHandler>(elements_[--current_size_]);
959 if (current_size_ < allocated_size_) {
960 // There are cleared elements on the end; replace the removed element
961 // with the last allocated element.
962 elements_[current_size_] = elements_[allocated_size_];
967 inline int RepeatedPtrFieldBase::ClearedCount() const {
968 return allocated_size_ - current_size_;
971 template <typename TypeHandler>
972 inline void RepeatedPtrFieldBase::AddCleared(
973 typename TypeHandler::Type* value) {
974 if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
975 elements_[allocated_size_++] = value;
978 template <typename TypeHandler>
979 inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() {
980 GOOGLE_DCHECK_GT(allocated_size_, current_size_);
981 return cast<TypeHandler>(elements_[--allocated_size_]);
984 } // namespace internal
986 // -------------------------------------------------------------------
988 template <typename Element>
989 class RepeatedPtrField<Element>::TypeHandler
990 : public internal::GenericTypeHandler<Element> {
994 class RepeatedPtrField<string>::TypeHandler
995 : public internal::StringTypeHandler {
999 template <typename Element>
1000 inline RepeatedPtrField<Element>::RepeatedPtrField() {}
1002 template <typename Element>
1003 inline RepeatedPtrField<Element>::RepeatedPtrField(
1004 const RepeatedPtrField& other) {
1008 template <typename Element>
1009 template <typename Iter>
1010 inline RepeatedPtrField<Element>::RepeatedPtrField(
1011 Iter begin, const Iter& end) {
1012 for (; begin != end; ++begin) {
1017 template <typename Element>
1018 RepeatedPtrField<Element>::~RepeatedPtrField() {
1019 Destroy<TypeHandler>();
1022 template <typename Element>
1023 inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=(
1024 const RepeatedPtrField& other) {
1030 template <typename Element>
1031 inline int RepeatedPtrField<Element>::size() const {
1032 return RepeatedPtrFieldBase::size();
1035 template <typename Element>
1036 inline const Element& RepeatedPtrField<Element>::Get(int index) const {
1037 return RepeatedPtrFieldBase::Get<TypeHandler>(index);
1041 template <typename Element>
1042 inline Element* RepeatedPtrField<Element>::Mutable(int index) {
1043 return RepeatedPtrFieldBase::Mutable<TypeHandler>(index);
1046 template <typename Element>
1047 inline Element* RepeatedPtrField<Element>::Add() {
1048 return RepeatedPtrFieldBase::Add<TypeHandler>();
1051 template <typename Element>
1052 inline void RepeatedPtrField<Element>::RemoveLast() {
1053 RepeatedPtrFieldBase::RemoveLast<TypeHandler>();
1056 template <typename Element>
1057 inline void RepeatedPtrField<Element>::DeleteSubrange(int start, int num) {
1058 GOOGLE_DCHECK_GE(start, 0);
1059 GOOGLE_DCHECK_GE(num, 0);
1060 GOOGLE_DCHECK_LE(start + num, size());
1061 for (int i = 0; i < num; ++i)
1062 delete RepeatedPtrFieldBase::Mutable<TypeHandler>(start + i);
1063 ExtractSubrange(start, num, NULL);
1066 template <typename Element>
1067 inline void RepeatedPtrField<Element>::ExtractSubrange(
1068 int start, int num, Element** elements) {
1069 GOOGLE_DCHECK_GE(start, 0);
1070 GOOGLE_DCHECK_GE(num, 0);
1071 GOOGLE_DCHECK_LE(start + num, size());
1074 // Save the values of the removed elements if requested.
1075 if (elements != NULL) {
1076 for (int i = 0; i < num; ++i)
1077 elements[i] = RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start);
1079 CloseGap(start, num);
1083 template <typename Element>
1084 inline void RepeatedPtrField<Element>::Clear() {
1085 RepeatedPtrFieldBase::Clear<TypeHandler>();
1088 template <typename Element>
1089 inline void RepeatedPtrField<Element>::MergeFrom(
1090 const RepeatedPtrField& other) {
1091 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
1094 template <typename Element>
1095 inline void RepeatedPtrField<Element>::CopyFrom(
1096 const RepeatedPtrField& other) {
1097 RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other);
1100 template <typename Element>
1101 inline Element** RepeatedPtrField<Element>::mutable_data() {
1102 return RepeatedPtrFieldBase::mutable_data<TypeHandler>();
1105 template <typename Element>
1106 inline const Element* const* RepeatedPtrField<Element>::data() const {
1107 return RepeatedPtrFieldBase::data<TypeHandler>();
1110 template <typename Element>
1111 void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) {
1112 RepeatedPtrFieldBase::Swap(other);
1115 template <typename Element>
1116 void RepeatedPtrField<Element>::SwapElements(int index1, int index2) {
1117 RepeatedPtrFieldBase::SwapElements(index1, index2);
1120 template <typename Element>
1121 inline int RepeatedPtrField<Element>::SpaceUsedExcludingSelf() const {
1122 return RepeatedPtrFieldBase::SpaceUsedExcludingSelf<TypeHandler>();
1125 template <typename Element>
1126 inline void RepeatedPtrField<Element>::AddAllocated(Element* value) {
1127 RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value);
1130 template <typename Element>
1131 inline Element* RepeatedPtrField<Element>::ReleaseLast() {
1132 return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>();
1136 template <typename Element>
1137 inline int RepeatedPtrField<Element>::ClearedCount() const {
1138 return RepeatedPtrFieldBase::ClearedCount();
1141 template <typename Element>
1142 inline void RepeatedPtrField<Element>::AddCleared(Element* value) {
1143 return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value);
1146 template <typename Element>
1147 inline Element* RepeatedPtrField<Element>::ReleaseCleared() {
1148 return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>();
1151 template <typename Element>
1152 inline void RepeatedPtrField<Element>::Reserve(int new_size) {
1153 return RepeatedPtrFieldBase::Reserve(new_size);
1156 template <typename Element>
1157 inline int RepeatedPtrField<Element>::Capacity() const {
1158 return RepeatedPtrFieldBase::Capacity();
1161 // -------------------------------------------------------------------
1163 namespace internal {
1165 // STL-like iterator implementation for RepeatedPtrField. You should not
1166 // refer to this class directly; use RepeatedPtrField<T>::iterator instead.
1168 // The iterator for RepeatedPtrField<T>, RepeatedPtrIterator<T>, is
1169 // very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors.h,
1170 // but adds random-access operators and is modified to wrap a void** base
1171 // iterator (since RepeatedPtrField stores its array as a void* array and
1172 // casting void** to T** would violate C++ aliasing rules).
1174 // This code based on net/proto/proto-array-internal.h by Jeffrey Yasskin
1175 // (jyasskin@google.com).
1176 template<typename Element>
1177 class RepeatedPtrIterator
1178 : public std::iterator<
1179 std::random_access_iterator_tag, Element> {
1181 typedef RepeatedPtrIterator<Element> iterator;
1182 typedef std::iterator<
1183 std::random_access_iterator_tag, Element> superclass;
1185 // Let the compiler know that these are type names, so we don't have to
1186 // write "typename" in front of them everywhere.
1187 typedef typename superclass::reference reference;
1188 typedef typename superclass::pointer pointer;
1189 typedef typename superclass::difference_type difference_type;
1191 RepeatedPtrIterator() : it_(NULL) {}
1192 explicit RepeatedPtrIterator(void* const* it) : it_(it) {}
1194 // Allow "upcasting" from RepeatedPtrIterator<T**> to
1195 // RepeatedPtrIterator<const T*const*>.
1196 template<typename OtherElement>
1197 RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other)
1199 // Force a compiler error if the other type is not convertible to ours.
1201 implicit_cast<Element*, OtherElement*>(0);
1206 reference operator*() const { return *reinterpret_cast<Element*>(*it_); }
1207 pointer operator->() const { return &(operator*()); }
1209 // {inc,dec}rementable
1210 iterator& operator++() { ++it_; return *this; }
1211 iterator operator++(int) { return iterator(it_++); }
1212 iterator& operator--() { --it_; return *this; }
1213 iterator operator--(int) { return iterator(it_--); }
1215 // equality_comparable
1216 bool operator==(const iterator& x) const { return it_ == x.it_; }
1217 bool operator!=(const iterator& x) const { return it_ != x.it_; }
1219 // less_than_comparable
1220 bool operator<(const iterator& x) const { return it_ < x.it_; }
1221 bool operator<=(const iterator& x) const { return it_ <= x.it_; }
1222 bool operator>(const iterator& x) const { return it_ > x.it_; }
1223 bool operator>=(const iterator& x) const { return it_ >= x.it_; }
1225 // addable, subtractable
1226 iterator& operator+=(difference_type d) {
1230 friend iterator operator+(iterator it, difference_type d) {
1234 friend iterator operator+(difference_type d, iterator it) {
1238 iterator& operator-=(difference_type d) {
1242 friend iterator operator-(iterator it, difference_type d) {
1248 reference operator[](difference_type d) const { return *(*this + d); }
1250 // random access iterator
1251 difference_type operator-(const iterator& x) const { return it_ - x.it_; }
1254 template<typename OtherElement>
1255 friend class RepeatedPtrIterator;
1257 // The internal iterator.
1261 // Provide an iterator that operates on pointers to the underlying objects
1262 // rather than the objects themselves as RepeatedPtrIterator does.
1263 // Consider using this when working with stl algorithms that change
1265 // The VoidPtr template parameter holds the type-agnostic pointer value
1266 // referenced by the iterator. It should either be "void *" for a mutable
1267 // iterator, or "const void *" for a constant iterator.
1268 template<typename Element, typename VoidPtr>
1269 class RepeatedPtrOverPtrsIterator
1270 : public std::iterator<std::random_access_iterator_tag, Element*> {
1272 typedef RepeatedPtrOverPtrsIterator<Element, VoidPtr> iterator;
1273 typedef std::iterator<
1274 std::random_access_iterator_tag, Element*> superclass;
1276 // Let the compiler know that these are type names, so we don't have to
1277 // write "typename" in front of them everywhere.
1278 typedef typename superclass::reference reference;
1279 typedef typename superclass::pointer pointer;
1280 typedef typename superclass::difference_type difference_type;
1282 RepeatedPtrOverPtrsIterator() : it_(NULL) {}
1283 explicit RepeatedPtrOverPtrsIterator(VoidPtr* it) : it_(it) {}
1286 reference operator*() const { return *reinterpret_cast<Element**>(it_); }
1287 pointer operator->() const { return &(operator*()); }
1289 // {inc,dec}rementable
1290 iterator& operator++() { ++it_; return *this; }
1291 iterator operator++(int) { return iterator(it_++); }
1292 iterator& operator--() { --it_; return *this; }
1293 iterator operator--(int) { return iterator(it_--); }
1295 // equality_comparable
1296 bool operator==(const iterator& x) const { return it_ == x.it_; }
1297 bool operator!=(const iterator& x) const { return it_ != x.it_; }
1299 // less_than_comparable
1300 bool operator<(const iterator& x) const { return it_ < x.it_; }
1301 bool operator<=(const iterator& x) const { return it_ <= x.it_; }
1302 bool operator>(const iterator& x) const { return it_ > x.it_; }
1303 bool operator>=(const iterator& x) const { return it_ >= x.it_; }
1305 // addable, subtractable
1306 iterator& operator+=(difference_type d) {
1310 friend iterator operator+(iterator it, difference_type d) {
1314 friend iterator operator+(difference_type d, iterator it) {
1318 iterator& operator-=(difference_type d) {
1322 friend iterator operator-(iterator it, difference_type d) {
1328 reference operator[](difference_type d) const { return *(*this + d); }
1330 // random access iterator
1331 difference_type operator-(const iterator& x) const { return it_ - x.it_; }
1334 template<typename OtherElement>
1335 friend class RepeatedPtrIterator;
1337 // The internal iterator.
1341 } // namespace internal
1343 template <typename Element>
1344 inline typename RepeatedPtrField<Element>::iterator
1345 RepeatedPtrField<Element>::begin() {
1346 return iterator(raw_data());
1348 template <typename Element>
1349 inline typename RepeatedPtrField<Element>::const_iterator
1350 RepeatedPtrField<Element>::begin() const {
1351 return iterator(raw_data());
1353 template <typename Element>
1354 inline typename RepeatedPtrField<Element>::iterator
1355 RepeatedPtrField<Element>::end() {
1356 return iterator(raw_data() + size());
1358 template <typename Element>
1359 inline typename RepeatedPtrField<Element>::const_iterator
1360 RepeatedPtrField<Element>::end() const {
1361 return iterator(raw_data() + size());
1364 template <typename Element>
1365 inline typename RepeatedPtrField<Element>::pointer_iterator
1366 RepeatedPtrField<Element>::pointer_begin() {
1367 return pointer_iterator(raw_mutable_data());
1369 template <typename Element>
1370 inline typename RepeatedPtrField<Element>::const_pointer_iterator
1371 RepeatedPtrField<Element>::pointer_begin() const {
1372 return const_pointer_iterator(const_cast<const void**>(raw_mutable_data()));
1374 template <typename Element>
1375 inline typename RepeatedPtrField<Element>::pointer_iterator
1376 RepeatedPtrField<Element>::pointer_end() {
1377 return pointer_iterator(raw_mutable_data() + size());
1379 template <typename Element>
1380 inline typename RepeatedPtrField<Element>::const_pointer_iterator
1381 RepeatedPtrField<Element>::pointer_end() const {
1382 return const_pointer_iterator(
1383 const_cast<const void**>(raw_mutable_data() + size()));
1387 // Iterators and helper functions that follow the spirit of the STL
1388 // std::back_insert_iterator and std::back_inserter but are tailor-made
1389 // for RepeatedField and RepatedPtrField. Typical usage would be:
1391 // std::copy(some_sequence.begin(), some_sequence.end(),
1392 // google::protobuf::RepeatedFieldBackInserter(proto.mutable_sequence()));
1394 // Ported by johannes from util/gtl/proto-array-iterators.h
1396 namespace internal {
1397 // A back inserter for RepeatedField objects.
1398 template<typename T> class RepeatedFieldBackInsertIterator
1399 : public std::iterator<std::output_iterator_tag, T> {
1401 explicit RepeatedFieldBackInsertIterator(
1402 RepeatedField<T>* const mutable_field)
1403 : field_(mutable_field) {
1405 RepeatedFieldBackInsertIterator<T>& operator=(const T& value) {
1409 RepeatedFieldBackInsertIterator<T>& operator*() {
1412 RepeatedFieldBackInsertIterator<T>& operator++() {
1415 RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) {
1420 RepeatedField<T>* field_;
1423 // A back inserter for RepeatedPtrField objects.
1424 template<typename T> class RepeatedPtrFieldBackInsertIterator
1425 : public std::iterator<std::output_iterator_tag, T> {
1427 RepeatedPtrFieldBackInsertIterator(
1428 RepeatedPtrField<T>* const mutable_field)
1429 : field_(mutable_field) {
1431 RepeatedPtrFieldBackInsertIterator<T>& operator=(const T& value) {
1432 *field_->Add() = value;
1435 RepeatedPtrFieldBackInsertIterator<T>& operator=(
1436 const T* const ptr_to_value) {
1437 *field_->Add() = *ptr_to_value;
1440 RepeatedPtrFieldBackInsertIterator<T>& operator*() {
1443 RepeatedPtrFieldBackInsertIterator<T>& operator++() {
1446 RepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) {
1451 RepeatedPtrField<T>* field_;
1454 // A back inserter for RepeatedPtrFields that inserts by transfering ownership
1456 template<typename T> class AllocatedRepeatedPtrFieldBackInsertIterator
1457 : public std::iterator<std::output_iterator_tag, T> {
1459 explicit AllocatedRepeatedPtrFieldBackInsertIterator(
1460 RepeatedPtrField<T>* const mutable_field)
1461 : field_(mutable_field) {
1463 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator=(
1464 T* const ptr_to_value) {
1465 field_->AddAllocated(ptr_to_value);
1468 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator*() {
1471 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++() {
1474 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++(
1480 RepeatedPtrField<T>* field_;
1482 } // namespace internal
1484 // Provides a back insert iterator for RepeatedField instances,
1485 // similar to std::back_inserter().
1486 template<typename T> internal::RepeatedFieldBackInsertIterator<T>
1487 RepeatedFieldBackInserter(RepeatedField<T>* const mutable_field) {
1488 return internal::RepeatedFieldBackInsertIterator<T>(mutable_field);
1491 // Provides a back insert iterator for RepeatedPtrField instances,
1492 // similar to std::back_inserter().
1493 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
1494 RepeatedPtrFieldBackInserter(RepeatedPtrField<T>* const mutable_field) {
1495 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
1498 // Special back insert iterator for RepeatedPtrField instances, just in
1499 // case someone wants to write generic template code that can access both
1500 // RepeatedFields and RepeatedPtrFields using a common name.
1501 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
1502 RepeatedFieldBackInserter(RepeatedPtrField<T>* const mutable_field) {
1503 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
1506 // Provides a back insert iterator for RepeatedPtrField instances
1507 // similar to std::back_inserter() which transfers the ownership while
1508 // copying elements.
1509 template<typename T> internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>
1510 AllocatedRepeatedPtrFieldBackInserter(
1511 RepeatedPtrField<T>* const mutable_field) {
1512 return internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>(
1516 } // namespace protobuf
1518 } // namespace google
1519 #endif // GOOGLE_PROTOBUF_REPEATED_FIELD_H__