1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2008 Google Inc. All rights reserved.
3 // https://developers.google.com/protocol-buffers/
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 // * Redistributions in binary form must reproduce the above
12 // copyright notice, this list of conditions and the following disclaimer
13 // in the documentation and/or other materials provided with the
14 // distribution.
15 // * Neither the name of Google Inc. nor the names of its
16 // contributors may be used to endorse or promote products derived from
17 // this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 // Author: kenton@google.com (Kenton Varda)
32 // Based on original Protocol Buffers design by
33 // Sanjay Ghemawat, Jeff Dean, and others.
34 //
35 // RepeatedField and RepeatedPtrField are used by generated protocol message
36 // classes to manipulate repeated fields. These classes are very similar to
37 // STL's vector, but include a number of optimizations found to be useful
38 // specifically in the case of Protocol Buffers. RepeatedPtrField is
39 // particularly different from STL vector as it manages ownership of the
40 // pointers that it contains.
41 //
42 // Typically, clients should not need to access RepeatedField objects directly,
43 // but should instead use the accessor functions generated automatically by the
44 // protocol compiler.
45
46 #ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__
47 #define GOOGLE_PROTOBUF_REPEATED_FIELD_H__
48
49 #ifdef _MSC_VER
50 // This is required for min/max on VS2013 only.
51 #include <algorithm>
52 #endif
53
54 #include <string>
55 #include <iterator>
56 #include <google/protobuf/stubs/common.h>
57 #include <google/protobuf/stubs/type_traits.h>
58 #include <google/protobuf/generated_message_util.h>
59 #include <google/protobuf/message_lite.h>
60
61 namespace google {
62
63 namespace upb {
64 namespace google_opensource {
65 class GMR_Handlers;
66 } // namespace google_opensource
67 } // namespace upb
68
69 namespace protobuf {
70
71 class Message;
72
73 namespace internal {
74
75 static const int kMinRepeatedFieldAllocationSize = 4;
76
77 // A utility function for logging that doesn't need any template types.
78 void LogIndexOutOfBounds(int index, int size);
79
80 template <typename Iter>
CalculateReserve(Iter begin,Iter end,std::forward_iterator_tag)81 inline int CalculateReserve(Iter begin, Iter end, std::forward_iterator_tag) {
82 return std::distance(begin, end);
83 }
84
85 template <typename Iter>
CalculateReserve(Iter,Iter,std::input_iterator_tag)86 inline int CalculateReserve(Iter /*begin*/, Iter /*end*/,
87 std::input_iterator_tag) {
88 return -1;
89 }
90
91 template <typename Iter>
CalculateReserve(Iter begin,Iter end)92 inline int CalculateReserve(Iter begin, Iter end) {
93 typedef typename std::iterator_traits<Iter>::iterator_category Category;
94 return CalculateReserve(begin, end, Category());
95 }
96 } // namespace internal
97
98
99 // RepeatedField is used to represent repeated fields of a primitive type (in
100 // other words, everything except strings and nested Messages). Most users will
101 // not ever use a RepeatedField directly; they will use the get-by-index,
102 // set-by-index, and add accessors that are generated for all repeated fields.
103 template <typename Element>
104 class RepeatedField {
105 public:
106 RepeatedField();
107 RepeatedField(const RepeatedField& other);
108 template <typename Iter>
109 RepeatedField(Iter begin, const Iter& end);
110 ~RepeatedField();
111
112 RepeatedField& operator=(const RepeatedField& other);
113
114 bool empty() const;
115 int size() const;
116
117 const Element& Get(int index) const;
118 Element* Mutable(int index);
119 void Set(int index, const Element& value);
120 void Add(const Element& value);
121 Element* Add();
122 // Remove the last element in the array.
123 void RemoveLast();
124
125 // Extract elements with indices in "[start .. start+num-1]".
126 // Copy them into "elements[0 .. num-1]" if "elements" is not NULL.
127 // Caution: implementation also moves elements with indices [start+num ..].
128 // Calling this routine inside a loop can cause quadratic behavior.
129 void ExtractSubrange(int start, int num, Element* elements);
130
131 void Clear();
132 void MergeFrom(const RepeatedField& other);
133 void CopyFrom(const RepeatedField& other);
134
135 // Reserve space to expand the field to at least the given size. If the
136 // array is grown, it will always be at least doubled in size.
137 void Reserve(int new_size);
138
139 // Resize the RepeatedField to a new, smaller size. This is O(1).
140 void Truncate(int new_size);
141
142 void AddAlreadyReserved(const Element& value);
143 Element* AddAlreadyReserved();
144 int Capacity() const;
145
146 // Like STL resize. Uses value to fill appended elements.
147 // Like Truncate() if new_size <= size(), otherwise this is
148 // O(new_size - size()).
149 void Resize(int new_size, const Element& value);
150
151 // Gets the underlying array. This pointer is possibly invalidated by
152 // any add or remove operation.
153 Element* mutable_data();
154 const Element* data() const;
155
156 // Swap entire contents with "other".
157 void Swap(RepeatedField* other);
158
159 // Swap two elements.
160 void SwapElements(int index1, int index2);
161
162 // STL-like iterator support
163 typedef Element* iterator;
164 typedef const Element* const_iterator;
165 typedef Element value_type;
166 typedef value_type& reference;
167 typedef const value_type& const_reference;
168 typedef value_type* pointer;
169 typedef const value_type* const_pointer;
170 typedef int size_type;
171 typedef ptrdiff_t difference_type;
172
173 iterator begin();
174 const_iterator begin() const;
175 iterator end();
176 const_iterator end() const;
177
178 // Reverse iterator support
179 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
180 typedef std::reverse_iterator<iterator> reverse_iterator;
rbegin()181 reverse_iterator rbegin() {
182 return reverse_iterator(end());
183 }
rbegin()184 const_reverse_iterator rbegin() const {
185 return const_reverse_iterator(end());
186 }
rend()187 reverse_iterator rend() {
188 return reverse_iterator(begin());
189 }
rend()190 const_reverse_iterator rend() const {
191 return const_reverse_iterator(begin());
192 }
193
194 // Returns the number of bytes used by the repeated field, excluding
195 // sizeof(*this)
196 int SpaceUsedExcludingSelf() const;
197
198 private:
199 static const int kInitialSize = 0;
200
201 Element* elements_;
202 int current_size_;
203 int total_size_;
204
205 // Move the contents of |from| into |to|, possibly clobbering |from| in the
206 // process. For primitive types this is just a memcpy(), but it could be
207 // specialized for non-primitive types to, say, swap each element instead.
208 void MoveArray(Element to[], Element from[], int size);
209
210 // Copy the elements of |from| into |to|.
211 void CopyArray(Element to[], const Element from[], int size);
212 };
213
214 namespace internal {
215 template <typename It> class RepeatedPtrIterator;
216 template <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator;
217 } // namespace internal
218
219 namespace internal {
220
221 // This is a helper template to copy an array of elements effeciently when they
222 // have a trivial copy constructor, and correctly otherwise. This really
223 // shouldn't be necessary, but our compiler doesn't optimize std::copy very
224 // effectively.
225 template <typename Element,
226 bool HasTrivialCopy = has_trivial_copy<Element>::value>
227 struct ElementCopier {
228 void operator()(Element to[], const Element from[], int array_size);
229 };
230
231 } // namespace internal
232
233 namespace internal {
234
235 // This is the common base class for RepeatedPtrFields. It deals only in void*
236 // pointers. Users should not use this interface directly.
237 //
238 // The methods of this interface correspond to the methods of RepeatedPtrField,
239 // but may have a template argument called TypeHandler. Its signature is:
240 // class TypeHandler {
241 // public:
242 // typedef MyType Type;
243 // static Type* New();
244 // static void Delete(Type*);
245 // static void Clear(Type*);
246 // static void Merge(const Type& from, Type* to);
247 //
248 // // Only needs to be implemented if SpaceUsedExcludingSelf() is called.
249 // static int SpaceUsed(const Type&);
250 // };
251 class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase {
252 protected:
253 // The reflection implementation needs to call protected methods directly,
254 // reinterpreting pointers as being to Message instead of a specific Message
255 // subclass.
256 friend class GeneratedMessageReflection;
257
258 // ExtensionSet stores repeated message extensions as
259 // RepeatedPtrField<MessageLite>, but non-lite ExtensionSets need to
260 // implement SpaceUsed(), and thus need to call SpaceUsedExcludingSelf()
261 // reinterpreting MessageLite as Message. ExtensionSet also needs to make
262 // use of AddFromCleared(), which is not part of the public interface.
263 friend class ExtensionSet;
264
265 // To parse directly into a proto2 generated class, the upb class GMR_Handlers
266 // needs to be able to modify a RepeatedPtrFieldBase directly.
267 friend class LIBPROTOBUF_EXPORT upb::google_opensource::GMR_Handlers;
268
269 RepeatedPtrFieldBase();
270
271 // Must be called from destructor.
272 template <typename TypeHandler>
273 void Destroy();
274
275 bool empty() const;
276 int size() const;
277
278 template <typename TypeHandler>
279 const typename TypeHandler::Type& Get(int index) const;
280 template <typename TypeHandler>
281 typename TypeHandler::Type* Mutable(int index);
282 template <typename TypeHandler>
283 typename TypeHandler::Type* Add();
284 template <typename TypeHandler>
285 void RemoveLast();
286 template <typename TypeHandler>
287 void Clear();
288 template <typename TypeHandler>
289 void MergeFrom(const RepeatedPtrFieldBase& other);
290 template <typename TypeHandler>
291 void CopyFrom(const RepeatedPtrFieldBase& other);
292
CloseGap(int start,int num)293 void CloseGap(int start, int num) {
294 // Close up a gap of "num" elements starting at offset "start".
295 for (int i = start + num; i < allocated_size_; ++i)
296 elements_[i - num] = elements_[i];
297 current_size_ -= num;
298 allocated_size_ -= num;
299 }
300
301 void Reserve(int new_size);
302
303 int Capacity() const;
304
305 // Used for constructing iterators.
306 void* const* raw_data() const;
307 void** raw_mutable_data() const;
308
309 template <typename TypeHandler>
310 typename TypeHandler::Type** mutable_data();
311 template <typename TypeHandler>
312 const typename TypeHandler::Type* const* data() const;
313
314 void Swap(RepeatedPtrFieldBase* other);
315
316 void SwapElements(int index1, int index2);
317
318 template <typename TypeHandler>
319 int SpaceUsedExcludingSelf() const;
320
321
322 // Advanced memory management --------------------------------------
323
324 // Like Add(), but if there are no cleared objects to use, returns NULL.
325 template <typename TypeHandler>
326 typename TypeHandler::Type* AddFromCleared();
327
328 template <typename TypeHandler>
329 void AddAllocated(typename TypeHandler::Type* value);
330 template <typename TypeHandler>
331 typename TypeHandler::Type* ReleaseLast();
332
333 int ClearedCount() const;
334 template <typename TypeHandler>
335 void AddCleared(typename TypeHandler::Type* value);
336 template <typename TypeHandler>
337 typename TypeHandler::Type* ReleaseCleared();
338
339 private:
340 static const int kInitialSize = 0;
341
342 void** elements_;
343 int current_size_;
344 int allocated_size_;
345 int total_size_;
346
347 template <typename TypeHandler>
cast(void * element)348 static inline typename TypeHandler::Type* cast(void* element) {
349 return reinterpret_cast<typename TypeHandler::Type*>(element);
350 }
351 template <typename TypeHandler>
cast(const void * element)352 static inline const typename TypeHandler::Type* cast(const void* element) {
353 return reinterpret_cast<const typename TypeHandler::Type*>(element);
354 }
355
356 GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase);
357 };
358
359 template <typename GenericType>
360 class GenericTypeHandler {
361 public:
362 typedef GenericType Type;
New()363 static GenericType* New() { return new GenericType; }
Delete(GenericType * value)364 static void Delete(GenericType* value) { delete value; }
Clear(GenericType * value)365 static void Clear(GenericType* value) { value->Clear(); }
Merge(const GenericType & from,GenericType * to)366 static void Merge(const GenericType& from, GenericType* to) {
367 to->MergeFrom(from);
368 }
SpaceUsed(const GenericType & value)369 static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); }
default_instance()370 static const Type& default_instance() { return Type::default_instance(); }
371 };
372
373 template <>
Merge(const MessageLite & from,MessageLite * to)374 inline void GenericTypeHandler<MessageLite>::Merge(
375 const MessageLite& from, MessageLite* to) {
376 to->CheckTypeAndMergeFrom(from);
377 }
378
379 template <>
default_instance()380 inline const MessageLite& GenericTypeHandler<MessageLite>::default_instance() {
381 // Yes, the behavior of the code is undefined, but this function is only
382 // called when we're already deep into the world of undefined, because the
383 // caller called Get(index) out of bounds.
384 MessageLite* null = NULL;
385 return *null;
386 }
387
388 template <>
default_instance()389 inline const Message& GenericTypeHandler<Message>::default_instance() {
390 // Yes, the behavior of the code is undefined, but this function is only
391 // called when we're already deep into the world of undefined, because the
392 // caller called Get(index) out of bounds.
393 Message* null = NULL;
394 return *null;
395 }
396
397
398 // HACK: If a class is declared as DLL-exported in MSVC, it insists on
399 // generating copies of all its methods -- even inline ones -- to include
400 // in the DLL. But SpaceUsed() calls StringSpaceUsedExcludingSelf() which
401 // isn't in the lite library, therefore the lite library cannot link if
402 // StringTypeHandler is exported. So, we factor out StringTypeHandlerBase,
403 // export that, then make StringTypeHandler be a subclass which is NOT
404 // exported.
405 // TODO(kenton): There has to be a better way.
406 class LIBPROTOBUF_EXPORT StringTypeHandlerBase {
407 public:
408 typedef string Type;
409 static string* New();
410 static void Delete(string* value);
Clear(string * value)411 static void Clear(string* value) { value->clear(); }
Merge(const string & from,string * to)412 static void Merge(const string& from, string* to) { *to = from; }
default_instance()413 static const Type& default_instance() {
414 return ::google::protobuf::internal::GetEmptyString();
415 }
416 };
417
418 class StringTypeHandler : public StringTypeHandlerBase {
419 public:
SpaceUsed(const string & value)420 static int SpaceUsed(const string& value) {
421 return sizeof(value) + StringSpaceUsedExcludingSelf(value);
422 }
423 };
424
425
426 } // namespace internal
427
428 // RepeatedPtrField is like RepeatedField, but used for repeated strings or
429 // Messages.
430 template <typename Element>
431 class RepeatedPtrField : public internal::RepeatedPtrFieldBase {
432 public:
433 RepeatedPtrField();
434 RepeatedPtrField(const RepeatedPtrField& other);
435 template <typename Iter>
436 RepeatedPtrField(Iter begin, const Iter& end);
437 ~RepeatedPtrField();
438
439 RepeatedPtrField& operator=(const RepeatedPtrField& other);
440
441 bool empty() const;
442 int size() const;
443
444 const Element& Get(int index) const;
445 Element* Mutable(int index);
446 Element* Add();
447
448 // Remove the last element in the array.
449 // Ownership of the element is retained by the array.
450 void RemoveLast();
451
452 // Delete elements with indices in the range [start .. start+num-1].
453 // Caution: implementation moves all elements with indices [start+num .. ].
454 // Calling this routine inside a loop can cause quadratic behavior.
455 void DeleteSubrange(int start, int num);
456
457 void Clear();
458 void MergeFrom(const RepeatedPtrField& other);
459 void CopyFrom(const RepeatedPtrField& other);
460
461 // Reserve space to expand the field to at least the given size. This only
462 // resizes the pointer array; it doesn't allocate any objects. If the
463 // array is grown, it will always be at least doubled in size.
464 void Reserve(int new_size);
465
466 int Capacity() const;
467
468 // Gets the underlying array. This pointer is possibly invalidated by
469 // any add or remove operation.
470 Element** mutable_data();
471 const Element* const* data() const;
472
473 // Swap entire contents with "other".
474 void Swap(RepeatedPtrField* other);
475
476 // Swap two elements.
477 void SwapElements(int index1, int index2);
478
479 // STL-like iterator support
480 typedef internal::RepeatedPtrIterator<Element> iterator;
481 typedef internal::RepeatedPtrIterator<const Element> const_iterator;
482 typedef Element value_type;
483 typedef value_type& reference;
484 typedef const value_type& const_reference;
485 typedef value_type* pointer;
486 typedef const value_type* const_pointer;
487 typedef int size_type;
488 typedef ptrdiff_t difference_type;
489
490 iterator begin();
491 const_iterator begin() const;
492 iterator end();
493 const_iterator end() const;
494
495 // Reverse iterator support
496 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
497 typedef std::reverse_iterator<iterator> reverse_iterator;
rbegin()498 reverse_iterator rbegin() {
499 return reverse_iterator(end());
500 }
rbegin()501 const_reverse_iterator rbegin() const {
502 return const_reverse_iterator(end());
503 }
rend()504 reverse_iterator rend() {
505 return reverse_iterator(begin());
506 }
rend()507 const_reverse_iterator rend() const {
508 return const_reverse_iterator(begin());
509 }
510
511 // Custom STL-like iterator that iterates over and returns the underlying
512 // pointers to Element rather than Element itself.
513 typedef internal::RepeatedPtrOverPtrsIterator<Element, void*>
514 pointer_iterator;
515 typedef internal::RepeatedPtrOverPtrsIterator<const Element, const void*>
516 const_pointer_iterator;
517 pointer_iterator pointer_begin();
518 const_pointer_iterator pointer_begin() const;
519 pointer_iterator pointer_end();
520 const_pointer_iterator pointer_end() const;
521
522 // Returns (an estimate of) the number of bytes used by the repeated field,
523 // excluding sizeof(*this).
524 int SpaceUsedExcludingSelf() const;
525
526 // Advanced memory management --------------------------------------
527 // When hardcore memory management becomes necessary -- as it sometimes
528 // does here at Google -- the following methods may be useful.
529
530 // Add an already-allocated object, passing ownership to the
531 // RepeatedPtrField.
532 void AddAllocated(Element* value);
533 // Remove the last element and return it, passing ownership to the caller.
534 // Requires: size() > 0
535 Element* ReleaseLast();
536
537 // Extract elements with indices in the range "[start .. start+num-1]".
538 // The caller assumes ownership of the extracted elements and is responsible
539 // for deleting them when they are no longer needed.
540 // If "elements" is non-NULL, then pointers to the extracted elements
541 // are stored in "elements[0 .. num-1]" for the convenience of the caller.
542 // If "elements" is NULL, then the caller must use some other mechanism
543 // to perform any further operations (like deletion) on these elements.
544 // Caution: implementation also moves elements with indices [start+num ..].
545 // Calling this routine inside a loop can cause quadratic behavior.
546 void ExtractSubrange(int start, int num, Element** elements);
547
548 // When elements are removed by calls to RemoveLast() or Clear(), they
549 // are not actually freed. Instead, they are cleared and kept so that
550 // they can be reused later. This can save lots of CPU time when
551 // repeatedly reusing a protocol message for similar purposes.
552 //
553 // Hardcore programs may choose to manipulate these cleared objects
554 // to better optimize memory management using the following routines.
555
556 // Get the number of cleared objects that are currently being kept
557 // around for reuse.
558 int ClearedCount() const;
559 // Add an element to the pool of cleared objects, passing ownership to
560 // the RepeatedPtrField. The element must be cleared prior to calling
561 // this method.
562 void AddCleared(Element* value);
563 // Remove a single element from the cleared pool and return it, passing
564 // ownership to the caller. The element is guaranteed to be cleared.
565 // Requires: ClearedCount() > 0
566 Element* ReleaseCleared();
567
568 protected:
569 // Note: RepeatedPtrField SHOULD NOT be subclassed by users. We only
570 // subclass it in one place as a hack for compatibility with proto1. The
571 // subclass needs to know about TypeHandler in order to call protected
572 // methods on RepeatedPtrFieldBase.
573 class TypeHandler;
574
575 };
576
577 // implementation ====================================================
578
579 template <typename Element>
RepeatedField()580 inline RepeatedField<Element>::RepeatedField()
581 : elements_(NULL),
582 current_size_(0),
583 total_size_(kInitialSize) {
584 }
585
586 template <typename Element>
RepeatedField(const RepeatedField & other)587 inline RepeatedField<Element>::RepeatedField(const RepeatedField& other)
588 : elements_(NULL),
589 current_size_(0),
590 total_size_(kInitialSize) {
591 CopyFrom(other);
592 }
593
594 template <typename Element>
595 template <typename Iter>
RepeatedField(Iter begin,const Iter & end)596 inline RepeatedField<Element>::RepeatedField(Iter begin, const Iter& end)
597 : elements_(NULL),
598 current_size_(0),
599 total_size_(kInitialSize) {
600 int reserve = internal::CalculateReserve(begin, end);
601 if (reserve != -1) {
602 Reserve(reserve);
603 for (; begin != end; ++begin) {
604 AddAlreadyReserved(*begin);
605 }
606 } else {
607 for (; begin != end; ++begin) {
608 Add(*begin);
609 }
610 }
611 }
612
613 template <typename Element>
~RepeatedField()614 RepeatedField<Element>::~RepeatedField() {
615 delete [] elements_;
616 }
617
618 template <typename Element>
619 inline RepeatedField<Element>&
620 RepeatedField<Element>::operator=(const RepeatedField& other) {
621 if (this != &other)
622 CopyFrom(other);
623 return *this;
624 }
625
626 template <typename Element>
empty()627 inline bool RepeatedField<Element>::empty() const {
628 return current_size_ == 0;
629 }
630
631 template <typename Element>
size()632 inline int RepeatedField<Element>::size() const {
633 return current_size_;
634 }
635
636 template <typename Element>
Capacity()637 inline int RepeatedField<Element>::Capacity() const {
638 return total_size_;
639 }
640
641 template<typename Element>
AddAlreadyReserved(const Element & value)642 inline void RepeatedField<Element>::AddAlreadyReserved(const Element& value) {
643 GOOGLE_DCHECK_LT(size(), Capacity());
644 elements_[current_size_++] = value;
645 }
646
647 template<typename Element>
AddAlreadyReserved()648 inline Element* RepeatedField<Element>::AddAlreadyReserved() {
649 GOOGLE_DCHECK_LT(size(), Capacity());
650 return &elements_[current_size_++];
651 }
652
653 template<typename Element>
Resize(int new_size,const Element & value)654 inline void RepeatedField<Element>::Resize(int new_size, const Element& value) {
655 GOOGLE_DCHECK_GE(new_size, 0);
656 if (new_size > size()) {
657 Reserve(new_size);
658 std::fill(&elements_[current_size_], &elements_[new_size], value);
659 }
660 current_size_ = new_size;
661 }
662
663 template <typename Element>
Get(int index)664 inline const Element& RepeatedField<Element>::Get(int index) const {
665 GOOGLE_DCHECK_GE(index, 0);
666 GOOGLE_DCHECK_LT(index, size());
667 return elements_[index];
668 }
669
670 template <typename Element>
Mutable(int index)671 inline Element* RepeatedField<Element>::Mutable(int index) {
672 GOOGLE_DCHECK_GE(index, 0);
673 GOOGLE_DCHECK_LT(index, size());
674 return elements_ + index;
675 }
676
677 template <typename Element>
Set(int index,const Element & value)678 inline void RepeatedField<Element>::Set(int index, const Element& value) {
679 GOOGLE_DCHECK_GE(index, 0);
680 GOOGLE_DCHECK_LT(index, size());
681 elements_[index] = value;
682 }
683
684 template <typename Element>
Add(const Element & value)685 inline void RepeatedField<Element>::Add(const Element& value) {
686 if (current_size_ == total_size_) Reserve(total_size_ + 1);
687 elements_[current_size_++] = value;
688 }
689
690 template <typename Element>
Add()691 inline Element* RepeatedField<Element>::Add() {
692 if (current_size_ == total_size_) Reserve(total_size_ + 1);
693 return &elements_[current_size_++];
694 }
695
696 template <typename Element>
RemoveLast()697 inline void RepeatedField<Element>::RemoveLast() {
698 GOOGLE_DCHECK_GT(current_size_, 0);
699 --current_size_;
700 }
701
702 template <typename Element>
ExtractSubrange(int start,int num,Element * elements)703 void RepeatedField<Element>::ExtractSubrange(
704 int start, int num, Element* elements) {
705 GOOGLE_DCHECK_GE(start, 0);
706 GOOGLE_DCHECK_GE(num, 0);
707 GOOGLE_DCHECK_LE(start + num, this->size());
708
709 // Save the values of the removed elements if requested.
710 if (elements != NULL) {
711 for (int i = 0; i < num; ++i)
712 elements[i] = this->Get(i + start);
713 }
714
715 // Slide remaining elements down to fill the gap.
716 if (num > 0) {
717 for (int i = start + num; i < this->size(); ++i)
718 this->Set(i - num, this->Get(i));
719 this->Truncate(this->size() - num);
720 }
721 }
722
723 template <typename Element>
Clear()724 inline void RepeatedField<Element>::Clear() {
725 current_size_ = 0;
726 }
727
728 template <typename Element>
MergeFrom(const RepeatedField & other)729 inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) {
730 GOOGLE_CHECK_NE(&other, this);
731 if (other.current_size_ != 0) {
732 Reserve(current_size_ + other.current_size_);
733 CopyArray(elements_ + current_size_, other.elements_, other.current_size_);
734 current_size_ += other.current_size_;
735 }
736 }
737
738 template <typename Element>
CopyFrom(const RepeatedField & other)739 inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) {
740 if (&other == this) return;
741 Clear();
742 MergeFrom(other);
743 }
744
745 template <typename Element>
mutable_data()746 inline Element* RepeatedField<Element>::mutable_data() {
747 return elements_;
748 }
749
750 template <typename Element>
data()751 inline const Element* RepeatedField<Element>::data() const {
752 return elements_;
753 }
754
755
756 template <typename Element>
Swap(RepeatedField * other)757 void RepeatedField<Element>::Swap(RepeatedField* other) {
758 if (this == other) return;
759 Element* swap_elements = elements_;
760 int swap_current_size = current_size_;
761 int swap_total_size = total_size_;
762
763 elements_ = other->elements_;
764 current_size_ = other->current_size_;
765 total_size_ = other->total_size_;
766
767 other->elements_ = swap_elements;
768 other->current_size_ = swap_current_size;
769 other->total_size_ = swap_total_size;
770 }
771
772 template <typename Element>
SwapElements(int index1,int index2)773 void RepeatedField<Element>::SwapElements(int index1, int index2) {
774 using std::swap; // enable ADL with fallback
775 swap(elements_[index1], elements_[index2]);
776 }
777
778 template <typename Element>
779 inline typename RepeatedField<Element>::iterator
begin()780 RepeatedField<Element>::begin() {
781 return elements_;
782 }
783 template <typename Element>
784 inline typename RepeatedField<Element>::const_iterator
begin()785 RepeatedField<Element>::begin() const {
786 return elements_;
787 }
788 template <typename Element>
789 inline typename RepeatedField<Element>::iterator
end()790 RepeatedField<Element>::end() {
791 return elements_ + current_size_;
792 }
793 template <typename Element>
794 inline typename RepeatedField<Element>::const_iterator
end()795 RepeatedField<Element>::end() const {
796 return elements_ + current_size_;
797 }
798
799 template <typename Element>
SpaceUsedExcludingSelf()800 inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const {
801 return (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
802 }
803
804 // Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant
805 // amount of code bloat.
806 template <typename Element>
Reserve(int new_size)807 void RepeatedField<Element>::Reserve(int new_size) {
808 if (total_size_ >= new_size) return;
809
810 Element* old_elements = elements_;
811 total_size_ = max(google::protobuf::internal::kMinRepeatedFieldAllocationSize,
812 max(total_size_ * 2, new_size));
813 elements_ = new Element[total_size_];
814 if (old_elements != NULL) {
815 MoveArray(elements_, old_elements, current_size_);
816 delete [] old_elements;
817 }
818 }
819
820 template <typename Element>
Truncate(int new_size)821 inline void RepeatedField<Element>::Truncate(int new_size) {
822 GOOGLE_DCHECK_LE(new_size, current_size_);
823 current_size_ = new_size;
824 }
825
826 template <typename Element>
MoveArray(Element to[],Element from[],int array_size)827 inline void RepeatedField<Element>::MoveArray(
828 Element to[], Element from[], int array_size) {
829 CopyArray(to, from, array_size);
830 }
831
832 template <typename Element>
CopyArray(Element to[],const Element from[],int array_size)833 inline void RepeatedField<Element>::CopyArray(
834 Element to[], const Element from[], int array_size) {
835 internal::ElementCopier<Element>()(to, from, array_size);
836 }
837
838 namespace internal {
839
840 template <typename Element, bool HasTrivialCopy>
operator()841 void ElementCopier<Element, HasTrivialCopy>::operator()(
842 Element to[], const Element from[], int array_size) {
843 std::copy(from, from + array_size, to);
844 }
845
846 template <typename Element>
847 struct ElementCopier<Element, true> {
848 void operator()(Element to[], const Element from[], int array_size) {
849 memcpy(to, from, array_size * sizeof(Element));
850 }
851 };
852
853 } // namespace internal
854
855
856 // -------------------------------------------------------------------
857
858 namespace internal {
859
860 inline RepeatedPtrFieldBase::RepeatedPtrFieldBase()
861 : elements_(NULL),
862 current_size_(0),
863 allocated_size_(0),
864 total_size_(kInitialSize) {
865 }
866
867 template <typename TypeHandler>
868 void RepeatedPtrFieldBase::Destroy() {
869 for (int i = 0; i < allocated_size_; i++) {
870 TypeHandler::Delete(cast<TypeHandler>(elements_[i]));
871 }
872 delete [] elements_;
873 }
874
875 inline bool RepeatedPtrFieldBase::empty() const {
876 return current_size_ == 0;
877 }
878
879 inline int RepeatedPtrFieldBase::size() const {
880 return current_size_;
881 }
882
883 template <typename TypeHandler>
884 inline const typename TypeHandler::Type&
885 RepeatedPtrFieldBase::Get(int index) const {
886 GOOGLE_DCHECK_GE(index, 0);
887 GOOGLE_DCHECK_LT(index, size());
888 return *cast<TypeHandler>(elements_[index]);
889 }
890
891
892 template <typename TypeHandler>
893 inline typename TypeHandler::Type*
894 RepeatedPtrFieldBase::Mutable(int index) {
895 GOOGLE_DCHECK_GE(index, 0);
896 GOOGLE_DCHECK_LT(index, size());
897 return cast<TypeHandler>(elements_[index]);
898 }
899
900 template <typename TypeHandler>
901 inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() {
902 if (current_size_ < allocated_size_) {
903 return cast<TypeHandler>(elements_[current_size_++]);
904 }
905 if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
906 typename TypeHandler::Type* result = TypeHandler::New();
907 ++allocated_size_;
908 elements_[current_size_++] = result;
909 return result;
910 }
911
912 template <typename TypeHandler>
913 inline void RepeatedPtrFieldBase::RemoveLast() {
914 GOOGLE_DCHECK_GT(current_size_, 0);
915 TypeHandler::Clear(cast<TypeHandler>(elements_[--current_size_]));
916 }
917
918 template <typename TypeHandler>
919 void RepeatedPtrFieldBase::Clear() {
920 for (int i = 0; i < current_size_; i++) {
921 TypeHandler::Clear(cast<TypeHandler>(elements_[i]));
922 }
923 current_size_ = 0;
924 }
925
926 template <typename TypeHandler>
927 inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) {
928 GOOGLE_CHECK_NE(&other, this);
929 Reserve(current_size_ + other.current_size_);
930 for (int i = 0; i < other.current_size_; i++) {
931 TypeHandler::Merge(other.template Get<TypeHandler>(i), Add<TypeHandler>());
932 }
933 }
934
935 template <typename TypeHandler>
936 inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) {
937 if (&other == this) return;
938 RepeatedPtrFieldBase::Clear<TypeHandler>();
939 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
940 }
941
942 inline int RepeatedPtrFieldBase::Capacity() const {
943 return total_size_;
944 }
945
946 inline void* const* RepeatedPtrFieldBase::raw_data() const {
947 return elements_;
948 }
949
950 inline void** RepeatedPtrFieldBase::raw_mutable_data() const {
951 return elements_;
952 }
953
954 template <typename TypeHandler>
955 inline typename TypeHandler::Type** RepeatedPtrFieldBase::mutable_data() {
956 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this
957 // method entirely.
958 return reinterpret_cast<typename TypeHandler::Type**>(elements_);
959 }
960
961 template <typename TypeHandler>
962 inline const typename TypeHandler::Type* const*
963 RepeatedPtrFieldBase::data() const {
964 // TODO(kenton): Breaks C++ aliasing rules. We should probably remove this
965 // method entirely.
966 return reinterpret_cast<const typename TypeHandler::Type* const*>(elements_);
967 }
968
969 inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) {
970 using std::swap; // enable ADL with fallback
971 swap(elements_[index1], elements_[index2]);
972 }
973
974 template <typename TypeHandler>
975 inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const {
976 int allocated_bytes =
977 (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0;
978 for (int i = 0; i < allocated_size_; ++i) {
979 allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i]));
980 }
981 return allocated_bytes;
982 }
983
984 template <typename TypeHandler>
985 inline typename TypeHandler::Type* RepeatedPtrFieldBase::AddFromCleared() {
986 if (current_size_ < allocated_size_) {
987 return cast<TypeHandler>(elements_[current_size_++]);
988 } else {
989 return NULL;
990 }
991 }
992
993 template <typename TypeHandler>
994 void RepeatedPtrFieldBase::AddAllocated(
995 typename TypeHandler::Type* value) {
996 // Make room for the new pointer.
997 if (current_size_ == total_size_) {
998 // The array is completely full with no cleared objects, so grow it.
999 Reserve(total_size_ + 1);
1000 ++allocated_size_;
1001 } else if (allocated_size_ == total_size_) {
1002 // There is no more space in the pointer array because it contains some
1003 // cleared objects awaiting reuse. We don't want to grow the array in this
1004 // case because otherwise a loop calling AddAllocated() followed by Clear()
1005 // would leak memory.
1006 TypeHandler::Delete(cast<TypeHandler>(elements_[current_size_]));
1007 } else if (current_size_ < allocated_size_) {
1008 // We have some cleared objects. We don't care about their order, so we
1009 // can just move the first one to the end to make space.
1010 elements_[allocated_size_] = elements_[current_size_];
1011 ++allocated_size_;
1012 } else {
1013 // There are no cleared objects.
1014 ++allocated_size_;
1015 }
1016
1017 elements_[current_size_++] = value;
1018 }
1019
1020 template <typename TypeHandler>
1021 inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() {
1022 GOOGLE_DCHECK_GT(current_size_, 0);
1023 typename TypeHandler::Type* result =
1024 cast<TypeHandler>(elements_[--current_size_]);
1025 --allocated_size_;
1026 if (current_size_ < allocated_size_) {
1027 // There are cleared elements on the end; replace the removed element
1028 // with the last allocated element.
1029 elements_[current_size_] = elements_[allocated_size_];
1030 }
1031 return result;
1032 }
1033
1034 inline int RepeatedPtrFieldBase::ClearedCount() const {
1035 return allocated_size_ - current_size_;
1036 }
1037
1038 template <typename TypeHandler>
1039 inline void RepeatedPtrFieldBase::AddCleared(
1040 typename TypeHandler::Type* value) {
1041 if (allocated_size_ == total_size_) Reserve(total_size_ + 1);
1042 elements_[allocated_size_++] = value;
1043 }
1044
1045 template <typename TypeHandler>
1046 inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() {
1047 GOOGLE_DCHECK_GT(allocated_size_, current_size_);
1048 return cast<TypeHandler>(elements_[--allocated_size_]);
1049 }
1050
1051 } // namespace internal
1052
1053 // -------------------------------------------------------------------
1054
1055 template <typename Element>
1056 class RepeatedPtrField<Element>::TypeHandler
1057 : public internal::GenericTypeHandler<Element> {
1058 };
1059
1060 template <>
1061 class RepeatedPtrField<string>::TypeHandler
1062 : public internal::StringTypeHandler {
1063 };
1064
1065
1066 template <typename Element>
1067 inline RepeatedPtrField<Element>::RepeatedPtrField() {}
1068
1069 template <typename Element>
1070 inline RepeatedPtrField<Element>::RepeatedPtrField(
1071 const RepeatedPtrField& other)
1072 : RepeatedPtrFieldBase() {
1073 CopyFrom(other);
1074 }
1075
1076 template <typename Element>
1077 template <typename Iter>
1078 inline RepeatedPtrField<Element>::RepeatedPtrField(
1079 Iter begin, const Iter& end) {
1080 int reserve = internal::CalculateReserve(begin, end);
1081 if (reserve != -1) {
1082 Reserve(reserve);
1083 }
1084 for (; begin != end; ++begin) {
1085 *Add() = *begin;
1086 }
1087 }
1088
1089 template <typename Element>
1090 RepeatedPtrField<Element>::~RepeatedPtrField() {
1091 Destroy<TypeHandler>();
1092 }
1093
1094 template <typename Element>
1095 inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=(
1096 const RepeatedPtrField& other) {
1097 if (this != &other)
1098 CopyFrom(other);
1099 return *this;
1100 }
1101
1102 template <typename Element>
1103 inline bool RepeatedPtrField<Element>::empty() const {
1104 return RepeatedPtrFieldBase::empty();
1105 }
1106
1107 template <typename Element>
1108 inline int RepeatedPtrField<Element>::size() const {
1109 return RepeatedPtrFieldBase::size();
1110 }
1111
1112 template <typename Element>
1113 inline const Element& RepeatedPtrField<Element>::Get(int index) const {
1114 return RepeatedPtrFieldBase::Get<TypeHandler>(index);
1115 }
1116
1117
1118 template <typename Element>
1119 inline Element* RepeatedPtrField<Element>::Mutable(int index) {
1120 return RepeatedPtrFieldBase::Mutable<TypeHandler>(index);
1121 }
1122
1123 template <typename Element>
1124 inline Element* RepeatedPtrField<Element>::Add() {
1125 return RepeatedPtrFieldBase::Add<TypeHandler>();
1126 }
1127
1128 template <typename Element>
1129 inline void RepeatedPtrField<Element>::RemoveLast() {
1130 RepeatedPtrFieldBase::RemoveLast<TypeHandler>();
1131 }
1132
1133 template <typename Element>
1134 inline void RepeatedPtrField<Element>::DeleteSubrange(int start, int num) {
1135 GOOGLE_DCHECK_GE(start, 0);
1136 GOOGLE_DCHECK_GE(num, 0);
1137 GOOGLE_DCHECK_LE(start + num, size());
1138 for (int i = 0; i < num; ++i)
1139 delete RepeatedPtrFieldBase::Mutable<TypeHandler>(start + i);
1140 ExtractSubrange(start, num, NULL);
1141 }
1142
1143 template <typename Element>
1144 inline void RepeatedPtrField<Element>::ExtractSubrange(
1145 int start, int num, Element** elements) {
1146 GOOGLE_DCHECK_GE(start, 0);
1147 GOOGLE_DCHECK_GE(num, 0);
1148 GOOGLE_DCHECK_LE(start + num, size());
1149
1150 if (num > 0) {
1151 // Save the values of the removed elements if requested.
1152 if (elements != NULL) {
1153 for (int i = 0; i < num; ++i)
1154 elements[i] = RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start);
1155 }
1156 CloseGap(start, num);
1157 }
1158 }
1159
1160 template <typename Element>
1161 inline void RepeatedPtrField<Element>::Clear() {
1162 RepeatedPtrFieldBase::Clear<TypeHandler>();
1163 }
1164
1165 template <typename Element>
1166 inline void RepeatedPtrField<Element>::MergeFrom(
1167 const RepeatedPtrField& other) {
1168 RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other);
1169 }
1170
1171 template <typename Element>
1172 inline void RepeatedPtrField<Element>::CopyFrom(
1173 const RepeatedPtrField& other) {
1174 RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other);
1175 }
1176
1177 template <typename Element>
1178 inline Element** RepeatedPtrField<Element>::mutable_data() {
1179 return RepeatedPtrFieldBase::mutable_data<TypeHandler>();
1180 }
1181
1182 template <typename Element>
1183 inline const Element* const* RepeatedPtrField<Element>::data() const {
1184 return RepeatedPtrFieldBase::data<TypeHandler>();
1185 }
1186
1187 template <typename Element>
1188 void RepeatedPtrField<Element>::Swap(RepeatedPtrField* other) {
1189 RepeatedPtrFieldBase::Swap(other);
1190 }
1191
1192 template <typename Element>
1193 void RepeatedPtrField<Element>::SwapElements(int index1, int index2) {
1194 RepeatedPtrFieldBase::SwapElements(index1, index2);
1195 }
1196
1197 template <typename Element>
1198 inline int RepeatedPtrField<Element>::SpaceUsedExcludingSelf() const {
1199 return RepeatedPtrFieldBase::SpaceUsedExcludingSelf<TypeHandler>();
1200 }
1201
1202 template <typename Element>
1203 inline void RepeatedPtrField<Element>::AddAllocated(Element* value) {
1204 RepeatedPtrFieldBase::AddAllocated<TypeHandler>(value);
1205 }
1206
1207 template <typename Element>
1208 inline Element* RepeatedPtrField<Element>::ReleaseLast() {
1209 return RepeatedPtrFieldBase::ReleaseLast<TypeHandler>();
1210 }
1211
1212
1213 template <typename Element>
1214 inline int RepeatedPtrField<Element>::ClearedCount() const {
1215 return RepeatedPtrFieldBase::ClearedCount();
1216 }
1217
1218 template <typename Element>
1219 inline void RepeatedPtrField<Element>::AddCleared(Element* value) {
1220 return RepeatedPtrFieldBase::AddCleared<TypeHandler>(value);
1221 }
1222
1223 template <typename Element>
1224 inline Element* RepeatedPtrField<Element>::ReleaseCleared() {
1225 return RepeatedPtrFieldBase::ReleaseCleared<TypeHandler>();
1226 }
1227
1228 template <typename Element>
1229 inline void RepeatedPtrField<Element>::Reserve(int new_size) {
1230 return RepeatedPtrFieldBase::Reserve(new_size);
1231 }
1232
1233 template <typename Element>
1234 inline int RepeatedPtrField<Element>::Capacity() const {
1235 return RepeatedPtrFieldBase::Capacity();
1236 }
1237
1238 // -------------------------------------------------------------------
1239
1240 namespace internal {
1241
1242 // STL-like iterator implementation for RepeatedPtrField. You should not
1243 // refer to this class directly; use RepeatedPtrField<T>::iterator instead.
1244 //
1245 // The iterator for RepeatedPtrField<T>, RepeatedPtrIterator<T>, is
1246 // very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors.h,
1247 // but adds random-access operators and is modified to wrap a void** base
1248 // iterator (since RepeatedPtrField stores its array as a void* array and
1249 // casting void** to T** would violate C++ aliasing rules).
1250 //
1251 // This code based on net/proto/proto-array-internal.h by Jeffrey Yasskin
1252 // (jyasskin@google.com).
1253 template<typename Element>
1254 class RepeatedPtrIterator
1255 : public std::iterator<
1256 std::random_access_iterator_tag, Element> {
1257 public:
1258 typedef RepeatedPtrIterator<Element> iterator;
1259 typedef std::iterator<
1260 std::random_access_iterator_tag, Element> superclass;
1261
1262 // Shadow the value_type in std::iterator<> because const_iterator::value_type
1263 // needs to be T, not const T.
1264 typedef typename remove_const<Element>::type value_type;
1265
1266 // Let the compiler know that these are type names, so we don't have to
1267 // write "typename" in front of them everywhere.
1268 typedef typename superclass::reference reference;
1269 typedef typename superclass::pointer pointer;
1270 typedef typename superclass::difference_type difference_type;
1271
1272 RepeatedPtrIterator() : it_(NULL) {}
1273 explicit RepeatedPtrIterator(void* const* it) : it_(it) {}
1274
1275 // Allow "upcasting" from RepeatedPtrIterator<T**> to
1276 // RepeatedPtrIterator<const T*const*>.
1277 template<typename OtherElement>
1278 RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other)
1279 : it_(other.it_) {
1280 // Force a compiler error if the other type is not convertible to ours.
1281 if (false) {
1282 implicit_cast<Element*, OtherElement*>(0);
1283 }
1284 }
1285
1286 // dereferenceable
1287 reference operator*() const { return *reinterpret_cast<Element*>(*it_); }
1288 pointer operator->() const { return &(operator*()); }
1289
1290 // {inc,dec}rementable
1291 iterator& operator++() { ++it_; return *this; }
1292 iterator operator++(int) { return iterator(it_++); }
1293 iterator& operator--() { --it_; return *this; }
1294 iterator operator--(int) { return iterator(it_--); }
1295
1296 // equality_comparable
1297 bool operator==(const iterator& x) const { return it_ == x.it_; }
1298 bool operator!=(const iterator& x) const { return it_ != x.it_; }
1299
1300 // less_than_comparable
1301 bool operator<(const iterator& x) const { return it_ < x.it_; }
1302 bool operator<=(const iterator& x) const { return it_ <= x.it_; }
1303 bool operator>(const iterator& x) const { return it_ > x.it_; }
1304 bool operator>=(const iterator& x) const { return it_ >= x.it_; }
1305
1306 // addable, subtractable
1307 iterator& operator+=(difference_type d) {
1308 it_ += d;
1309 return *this;
1310 }
1311 friend iterator operator+(iterator it, difference_type d) {
1312 it += d;
1313 return it;
1314 }
1315 friend iterator operator+(difference_type d, iterator it) {
1316 it += d;
1317 return it;
1318 }
1319 iterator& operator-=(difference_type d) {
1320 it_ -= d;
1321 return *this;
1322 }
1323 friend iterator operator-(iterator it, difference_type d) {
1324 it -= d;
1325 return it;
1326 }
1327
1328 // indexable
1329 reference operator[](difference_type d) const { return *(*this + d); }
1330
1331 // random access iterator
1332 difference_type operator-(const iterator& x) const { return it_ - x.it_; }
1333
1334 private:
1335 template<typename OtherElement>
1336 friend class RepeatedPtrIterator;
1337
1338 // The internal iterator.
1339 void* const* it_;
1340 };
1341
1342 // Provide an iterator that operates on pointers to the underlying objects
1343 // rather than the objects themselves as RepeatedPtrIterator does.
1344 // Consider using this when working with stl algorithms that change
1345 // the array.
1346 // The VoidPtr template parameter holds the type-agnostic pointer value
1347 // referenced by the iterator. It should either be "void *" for a mutable
1348 // iterator, or "const void *" for a constant iterator.
1349 template<typename Element, typename VoidPtr>
1350 class RepeatedPtrOverPtrsIterator
1351 : public std::iterator<std::random_access_iterator_tag, Element*> {
1352 public:
1353 typedef RepeatedPtrOverPtrsIterator<Element, VoidPtr> iterator;
1354 typedef std::iterator<
1355 std::random_access_iterator_tag, Element*> superclass;
1356
1357 // Shadow the value_type in std::iterator<> because const_iterator::value_type
1358 // needs to be T, not const T.
1359 typedef typename remove_const<Element*>::type value_type;
1360
1361 // Let the compiler know that these are type names, so we don't have to
1362 // write "typename" in front of them everywhere.
1363 typedef typename superclass::reference reference;
1364 typedef typename superclass::pointer pointer;
1365 typedef typename superclass::difference_type difference_type;
1366
1367 RepeatedPtrOverPtrsIterator() : it_(NULL) {}
1368 explicit RepeatedPtrOverPtrsIterator(VoidPtr* it) : it_(it) {}
1369
1370 // dereferenceable
1371 reference operator*() const { return *reinterpret_cast<Element**>(it_); }
1372 pointer operator->() const { return &(operator*()); }
1373
1374 // {inc,dec}rementable
1375 iterator& operator++() { ++it_; return *this; }
1376 iterator operator++(int) { return iterator(it_++); }
1377 iterator& operator--() { --it_; return *this; }
1378 iterator operator--(int) { return iterator(it_--); }
1379
1380 // equality_comparable
1381 bool operator==(const iterator& x) const { return it_ == x.it_; }
1382 bool operator!=(const iterator& x) const { return it_ != x.it_; }
1383
1384 // less_than_comparable
1385 bool operator<(const iterator& x) const { return it_ < x.it_; }
1386 bool operator<=(const iterator& x) const { return it_ <= x.it_; }
1387 bool operator>(const iterator& x) const { return it_ > x.it_; }
1388 bool operator>=(const iterator& x) const { return it_ >= x.it_; }
1389
1390 // addable, subtractable
1391 iterator& operator+=(difference_type d) {
1392 it_ += d;
1393 return *this;
1394 }
1395 friend iterator operator+(iterator it, difference_type d) {
1396 it += d;
1397 return it;
1398 }
1399 friend iterator operator+(difference_type d, iterator it) {
1400 it += d;
1401 return it;
1402 }
1403 iterator& operator-=(difference_type d) {
1404 it_ -= d;
1405 return *this;
1406 }
1407 friend iterator operator-(iterator it, difference_type d) {
1408 it -= d;
1409 return it;
1410 }
1411
1412 // indexable
1413 reference operator[](difference_type d) const { return *(*this + d); }
1414
1415 // random access iterator
1416 difference_type operator-(const iterator& x) const { return it_ - x.it_; }
1417
1418 private:
1419 template<typename OtherElement>
1420 friend class RepeatedPtrIterator;
1421
1422 // The internal iterator.
1423 VoidPtr* it_;
1424 };
1425
1426 } // namespace internal
1427
1428 template <typename Element>
1429 inline typename RepeatedPtrField<Element>::iterator
1430 RepeatedPtrField<Element>::begin() {
1431 return iterator(raw_data());
1432 }
1433 template <typename Element>
1434 inline typename RepeatedPtrField<Element>::const_iterator
1435 RepeatedPtrField<Element>::begin() const {
1436 return iterator(raw_data());
1437 }
1438 template <typename Element>
1439 inline typename RepeatedPtrField<Element>::iterator
1440 RepeatedPtrField<Element>::end() {
1441 return iterator(raw_data() + size());
1442 }
1443 template <typename Element>
1444 inline typename RepeatedPtrField<Element>::const_iterator
1445 RepeatedPtrField<Element>::end() const {
1446 return iterator(raw_data() + size());
1447 }
1448
1449 template <typename Element>
1450 inline typename RepeatedPtrField<Element>::pointer_iterator
1451 RepeatedPtrField<Element>::pointer_begin() {
1452 return pointer_iterator(raw_mutable_data());
1453 }
1454 template <typename Element>
1455 inline typename RepeatedPtrField<Element>::const_pointer_iterator
1456 RepeatedPtrField<Element>::pointer_begin() const {
1457 return const_pointer_iterator(const_cast<const void**>(raw_mutable_data()));
1458 }
1459 template <typename Element>
1460 inline typename RepeatedPtrField<Element>::pointer_iterator
1461 RepeatedPtrField<Element>::pointer_end() {
1462 return pointer_iterator(raw_mutable_data() + size());
1463 }
1464 template <typename Element>
1465 inline typename RepeatedPtrField<Element>::const_pointer_iterator
1466 RepeatedPtrField<Element>::pointer_end() const {
1467 return const_pointer_iterator(
1468 const_cast<const void**>(raw_mutable_data() + size()));
1469 }
1470
1471
1472 // Iterators and helper functions that follow the spirit of the STL
1473 // std::back_insert_iterator and std::back_inserter but are tailor-made
1474 // for RepeatedField and RepatedPtrField. Typical usage would be:
1475 //
1476 // std::copy(some_sequence.begin(), some_sequence.end(),
1477 // google::protobuf::RepeatedFieldBackInserter(proto.mutable_sequence()));
1478 //
1479 // Ported by johannes from util/gtl/proto-array-iterators.h
1480
1481 namespace internal {
1482 // A back inserter for RepeatedField objects.
1483 template<typename T> class RepeatedFieldBackInsertIterator
1484 : public std::iterator<std::output_iterator_tag, T> {
1485 public:
1486 explicit RepeatedFieldBackInsertIterator(
1487 RepeatedField<T>* const mutable_field)
1488 : field_(mutable_field) {
1489 }
1490 RepeatedFieldBackInsertIterator<T>& operator=(const T& value) {
1491 field_->Add(value);
1492 return *this;
1493 }
1494 RepeatedFieldBackInsertIterator<T>& operator*() {
1495 return *this;
1496 }
1497 RepeatedFieldBackInsertIterator<T>& operator++() {
1498 return *this;
1499 }
1500 RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) {
1501 return *this;
1502 }
1503
1504 private:
1505 RepeatedField<T>* field_;
1506 };
1507
1508 // A back inserter for RepeatedPtrField objects.
1509 template<typename T> class RepeatedPtrFieldBackInsertIterator
1510 : public std::iterator<std::output_iterator_tag, T> {
1511 public:
1512 RepeatedPtrFieldBackInsertIterator(
1513 RepeatedPtrField<T>* const mutable_field)
1514 : field_(mutable_field) {
1515 }
1516 RepeatedPtrFieldBackInsertIterator<T>& operator=(const T& value) {
1517 *field_->Add() = value;
1518 return *this;
1519 }
1520 RepeatedPtrFieldBackInsertIterator<T>& operator=(
1521 const T* const ptr_to_value) {
1522 *field_->Add() = *ptr_to_value;
1523 return *this;
1524 }
1525 RepeatedPtrFieldBackInsertIterator<T>& operator*() {
1526 return *this;
1527 }
1528 RepeatedPtrFieldBackInsertIterator<T>& operator++() {
1529 return *this;
1530 }
1531 RepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) {
1532 return *this;
1533 }
1534
1535 private:
1536 RepeatedPtrField<T>* field_;
1537 };
1538
1539 // A back inserter for RepeatedPtrFields that inserts by transfering ownership
1540 // of a pointer.
1541 template<typename T> class AllocatedRepeatedPtrFieldBackInsertIterator
1542 : public std::iterator<std::output_iterator_tag, T> {
1543 public:
1544 explicit AllocatedRepeatedPtrFieldBackInsertIterator(
1545 RepeatedPtrField<T>* const mutable_field)
1546 : field_(mutable_field) {
1547 }
1548 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator=(
1549 T* const ptr_to_value) {
1550 field_->AddAllocated(ptr_to_value);
1551 return *this;
1552 }
1553 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator*() {
1554 return *this;
1555 }
1556 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++() {
1557 return *this;
1558 }
1559 AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++(
1560 int /* unused */) {
1561 return *this;
1562 }
1563
1564 private:
1565 RepeatedPtrField<T>* field_;
1566 };
1567 } // namespace internal
1568
1569 // Provides a back insert iterator for RepeatedField instances,
1570 // similar to std::back_inserter().
1571 template<typename T> internal::RepeatedFieldBackInsertIterator<T>
1572 RepeatedFieldBackInserter(RepeatedField<T>* const mutable_field) {
1573 return internal::RepeatedFieldBackInsertIterator<T>(mutable_field);
1574 }
1575
1576 // Provides a back insert iterator for RepeatedPtrField instances,
1577 // similar to std::back_inserter().
1578 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
1579 RepeatedPtrFieldBackInserter(RepeatedPtrField<T>* const mutable_field) {
1580 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
1581 }
1582
1583 // Special back insert iterator for RepeatedPtrField instances, just in
1584 // case someone wants to write generic template code that can access both
1585 // RepeatedFields and RepeatedPtrFields using a common name.
1586 template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T>
1587 RepeatedFieldBackInserter(RepeatedPtrField<T>* const mutable_field) {
1588 return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field);
1589 }
1590
1591 // Provides a back insert iterator for RepeatedPtrField instances
1592 // similar to std::back_inserter() which transfers the ownership while
1593 // copying elements.
1594 template<typename T> internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>
1595 AllocatedRepeatedPtrFieldBackInserter(
1596 RepeatedPtrField<T>* const mutable_field) {
1597 return internal::AllocatedRepeatedPtrFieldBackInsertIterator<T>(
1598 mutable_field);
1599 }
1600
1601 } // namespace protobuf
1602
1603 } // namespace google
1604 #endif // GOOGLE_PROTOBUF_REPEATED_FIELD_H__
1605