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