diff options
Diffstat (limited to 'src/google/protobuf/repeated_field.h')
| -rw-r--r-- | src/google/protobuf/repeated_field.h | 547 |
1 files changed, 451 insertions, 96 deletions
diff --git a/src/google/protobuf/repeated_field.h b/src/google/protobuf/repeated_field.h index defdefe..5005183 100644 --- a/src/google/protobuf/repeated_field.h +++ b/src/google/protobuf/repeated_field.h @@ -1,6 +1,6 @@ // Protocol Buffers - Google's data interchange format // Copyright 2008 Google Inc. All rights reserved. -// http://code.google.com/p/protobuf/ +// https://developers.google.com/protocol-buffers/ // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are @@ -46,24 +46,55 @@ #ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__ #define GOOGLE_PROTOBUF_REPEATED_FIELD_H__ +#ifdef _MSC_VER +// This is required for min/max on VS2013 only. +#include <algorithm> +#endif + #include <string> #include <iterator> #include <google/protobuf/stubs/common.h> +#include <google/protobuf/stubs/type_traits.h> +#include <google/protobuf/generated_message_util.h> #include <google/protobuf/message_lite.h> namespace google { +namespace upb { +namespace google_opensource { +class GMR_Handlers; +} // namespace google_opensource +} // namespace upb + namespace protobuf { class Message; namespace internal { -// We need this (from generated_message_reflection.cc). -LIBPROTOBUF_EXPORT int StringSpaceUsedExcludingSelf(const string& str); +static const int kMinRepeatedFieldAllocationSize = 4; + +// A utility function for logging that doesn't need any template types. +void LogIndexOutOfBounds(int index, int size); +template <typename Iter> +inline int CalculateReserve(Iter begin, Iter end, std::forward_iterator_tag) { + return std::distance(begin, end); +} + +template <typename Iter> +inline int CalculateReserve(Iter begin, Iter end, std::input_iterator_tag) { + return -1; +} + +template <typename Iter> +inline int CalculateReserve(Iter begin, Iter end) { + typedef typename std::iterator_traits<Iter>::iterator_category Category; + return CalculateReserve(begin, end, Category()); +} } // namespace internal + // RepeatedField is used to represent repeated fields of a primitive type (in // other words, everything except strings and nested Messages). Most users will // not ever use a RepeatedField directly; they will use the get-by-index, @@ -72,8 +103,14 @@ template <typename Element> class RepeatedField { public: RepeatedField(); + RepeatedField(const RepeatedField& other); + template <typename Iter> + RepeatedField(Iter begin, const Iter& end); ~RepeatedField(); + RepeatedField& operator=(const RepeatedField& other); + + bool empty() const; int size() const; const Element& Get(int index) const; @@ -82,14 +119,17 @@ class RepeatedField { void Add(const Element& value); Element* Add(); // Remove the last element in the array. - // We don't provide a way to remove any element other than the last - // because it invites inefficient use, such as O(n^2) filtering loops - // that should have been O(n). If you want to remove an element other - // than the last, the best way to do it is to re-arrange the elements - // so that the one you want removed is at the end, then call RemoveLast(). void RemoveLast(); + + // Extract elements with indices in "[start .. start+num-1]". + // Copy them into "elements[0 .. num-1]" if "elements" is not NULL. + // Caution: implementation also moves elements with indices [start+num ..]. + // Calling this routine inside a loop can cause quadratic behavior. + void ExtractSubrange(int start, int num, Element* elements); + void Clear(); void MergeFrom(const RepeatedField& other); + void CopyFrom(const RepeatedField& other); // Reserve space to expand the field to at least the given size. If the // array is grown, it will always be at least doubled in size. @@ -102,6 +142,11 @@ class RepeatedField { Element* AddAlreadyReserved(); int Capacity() const; + // Like STL resize. Uses value to fill appended elements. + // Like Truncate() if new_size <= size(), otherwise this is + // O(new_size - size()). + void Resize(int new_size, const Element& value); + // Gets the underlying array. This pointer is possibly invalidated by // any add or remove operation. Element* mutable_data(); @@ -116,27 +161,46 @@ class RepeatedField { // STL-like iterator support typedef Element* iterator; typedef const Element* const_iterator; + typedef Element value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef int size_type; + typedef ptrdiff_t difference_type; iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; + // Reverse iterator support + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + reverse_iterator rbegin() { + return reverse_iterator(end()); + } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + reverse_iterator rend() { + return reverse_iterator(begin()); + } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + // Returns the number of bytes used by the repeated field, excluding // sizeof(*this) int SpaceUsedExcludingSelf() const; private: - GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedField); - - static const int kInitialSize = 4; + static const int kInitialSize = 0; Element* elements_; int current_size_; int total_size_; - Element initial_space_[kInitialSize]; - // Move the contents of |from| into |to|, possibly clobbering |from| in the // process. For primitive types this is just a memcpy(), but it could be // specialized for non-primitive types to, say, swap each element instead. @@ -148,7 +212,21 @@ class RepeatedField { namespace internal { template <typename It> class RepeatedPtrIterator; -template <typename It> class RepeatedPtrOverPtrsIterator; +template <typename It, typename VoidPtr> class RepeatedPtrOverPtrsIterator; +} // namespace internal + +namespace internal { + +// This is a helper template to copy an array of elements effeciently when they +// have a trivial copy constructor, and correctly otherwise. This really +// shouldn't be necessary, but our compiler doesn't optimize std::copy very +// effectively. +template <typename Element, + bool HasTrivialCopy = has_trivial_copy<Element>::value> +struct ElementCopier { + void operator()(Element to[], const Element from[], int array_size); +}; + } // namespace internal namespace internal { @@ -183,12 +261,17 @@ class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { // use of AddFromCleared(), which is not part of the public interface. friend class ExtensionSet; + // To parse directly into a proto2 generated class, the upb class GMR_Handlers + // needs to be able to modify a RepeatedPtrFieldBase directly. + friend class LIBPROTOBUF_EXPORT upb::google_opensource::GMR_Handlers; + RepeatedPtrFieldBase(); // Must be called from destructor. template <typename TypeHandler> void Destroy(); + bool empty() const; int size() const; template <typename TypeHandler> @@ -203,6 +286,16 @@ class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { void Clear(); template <typename TypeHandler> void MergeFrom(const RepeatedPtrFieldBase& other); + template <typename TypeHandler> + void CopyFrom(const RepeatedPtrFieldBase& other); + + void CloseGap(int start, int num) { + // Close up a gap of "num" elements starting at offset "start". + for (int i = start + num; i < allocated_size_; ++i) + elements_[i - num] = elements_[i]; + current_size_ -= num; + allocated_size_ -= num; + } void Reserve(int new_size); @@ -243,17 +336,13 @@ class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { typename TypeHandler::Type* ReleaseCleared(); private: - GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase); - - static const int kInitialSize = 4; + static const int kInitialSize = 0; void** elements_; int current_size_; int allocated_size_; int total_size_; - void* initial_space_[kInitialSize]; - template <typename TypeHandler> static inline typename TypeHandler::Type* cast(void* element) { return reinterpret_cast<typename TypeHandler::Type*>(element); @@ -262,6 +351,8 @@ class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { static inline const typename TypeHandler::Type* cast(const void* element) { return reinterpret_cast<const typename TypeHandler::Type*>(element); } + + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase); }; template <typename GenericType> @@ -275,6 +366,7 @@ class GenericTypeHandler { to->MergeFrom(from); } static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); } + static const Type& default_instance() { return Type::default_instance(); } }; template <> @@ -283,6 +375,25 @@ inline void GenericTypeHandler<MessageLite>::Merge( to->CheckTypeAndMergeFrom(from); } +template <> +inline const MessageLite& GenericTypeHandler<MessageLite>::default_instance() { + // Yes, the behavior of the code is undefined, but this function is only + // called when we're already deep into the world of undefined, because the + // caller called Get(index) out of bounds. + MessageLite* null = NULL; + return *null; +} + +template <> +inline const Message& GenericTypeHandler<Message>::default_instance() { + // Yes, the behavior of the code is undefined, but this function is only + // called when we're already deep into the world of undefined, because the + // caller called Get(index) out of bounds. + Message* null = NULL; + return *null; +} + + // HACK: If a class is declared as DLL-exported in MSVC, it insists on // generating copies of all its methods -- even inline ones -- to include // in the DLL. But SpaceUsed() calls StringSpaceUsedExcludingSelf() which @@ -298,6 +409,9 @@ class LIBPROTOBUF_EXPORT StringTypeHandlerBase { static void Delete(string* value); static void Clear(string* value) { value->clear(); } static void Merge(const string& from, string* to) { *to = from; } + static const Type& default_instance() { + return ::google::protobuf::internal::GetEmptyString(); + } }; class StringTypeHandler : public StringTypeHandlerBase { @@ -316,17 +430,32 @@ template <typename Element> class RepeatedPtrField : public internal::RepeatedPtrFieldBase { public: RepeatedPtrField(); - + RepeatedPtrField(const RepeatedPtrField& other); + template <typename Iter> + RepeatedPtrField(Iter begin, const Iter& end); ~RepeatedPtrField(); + RepeatedPtrField& operator=(const RepeatedPtrField& other); + + bool empty() const; int size() const; const Element& Get(int index) const; Element* Mutable(int index); Element* Add(); - void RemoveLast(); // Remove the last element in the array. + + // Remove the last element in the array. + // Ownership of the element is retained by the array. + void RemoveLast(); + + // Delete elements with indices in the range [start .. start+num-1]. + // Caution: implementation moves all elements with indices [start+num .. ]. + // Calling this routine inside a loop can cause quadratic behavior. + void DeleteSubrange(int start, int num); + void Clear(); void MergeFrom(const RepeatedPtrField& other); + void CopyFrom(const RepeatedPtrField& other); // Reserve space to expand the field to at least the given size. This only // resizes the pointer array; it doesn't allocate any objects. If the @@ -349,47 +478,79 @@ class RepeatedPtrField : public internal::RepeatedPtrFieldBase { // STL-like iterator support typedef internal::RepeatedPtrIterator<Element> iterator; typedef internal::RepeatedPtrIterator<const Element> const_iterator; + typedef Element value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef value_type* pointer; + typedef const value_type* const_pointer; + typedef int size_type; + typedef ptrdiff_t difference_type; iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; + // Reverse iterator support + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + reverse_iterator rbegin() { + return reverse_iterator(end()); + } + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + reverse_iterator rend() { + return reverse_iterator(begin()); + } + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + // Custom STL-like iterator that iterates over and returns the underlying // pointers to Element rather than Element itself. - typedef internal::RepeatedPtrOverPtrsIterator<Element> pointer_iterator; + typedef internal::RepeatedPtrOverPtrsIterator<Element, void*> + pointer_iterator; + typedef internal::RepeatedPtrOverPtrsIterator<const Element, const void*> + const_pointer_iterator; pointer_iterator pointer_begin(); + const_pointer_iterator pointer_begin() const; pointer_iterator pointer_end(); + const_pointer_iterator pointer_end() const; // Returns (an estimate of) the number of bytes used by the repeated field, // excluding sizeof(*this). int SpaceUsedExcludingSelf() const; - // The spaced used just by the pointer array, not counting the objects pointed - // at. Returns zero if the array is inlined (i.e. initial_space_ is being - // used). - int SpaceUsedByArray() const; - // Advanced memory management -------------------------------------- - // When hardcore memory management becomes necessary -- as it often + // When hardcore memory management becomes necessary -- as it sometimes // does here at Google -- the following methods may be useful. // Add an already-allocated object, passing ownership to the // RepeatedPtrField. void AddAllocated(Element* value); - // Remove the last element and return it, passing ownership to the - // caller. + // Remove the last element and return it, passing ownership to the caller. // Requires: size() > 0 Element* ReleaseLast(); + // Extract elements with indices in the range "[start .. start+num-1]". + // The caller assumes ownership of the extracted elements and is responsible + // for deleting them when they are no longer needed. + // If "elements" is non-NULL, then pointers to the extracted elements + // are stored in "elements[0 .. num-1]" for the convenience of the caller. + // If "elements" is NULL, then the caller must use some other mechanism + // to perform any further operations (like deletion) on these elements. + // Caution: implementation also moves elements with indices [start+num ..]. + // Calling this routine inside a loop can cause quadratic behavior. + void ExtractSubrange(int start, int num, Element** elements); + // When elements are removed by calls to RemoveLast() or Clear(), they // are not actually freed. Instead, they are cleared and kept so that // they can be reused later. This can save lots of CPU time when // repeatedly reusing a protocol message for similar purposes. // - // Really, extremely hardcore programs may actually want to manipulate - // these objects to better-optimize memory management. These methods - // allow that. + // Hardcore programs may choose to manipulate these cleared objects + // to better optimize memory management using the following routines. // Get the number of cleared objects that are currently being kept // around for reuse. @@ -410,28 +571,63 @@ class RepeatedPtrField : public internal::RepeatedPtrFieldBase { // methods on RepeatedPtrFieldBase. class TypeHandler; - - private: - GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrField); }; // implementation ==================================================== template <typename Element> inline RepeatedField<Element>::RepeatedField() - : elements_(initial_space_), + : elements_(NULL), current_size_(0), total_size_(kInitialSize) { } template <typename Element> -RepeatedField<Element>::~RepeatedField() { - if (elements_ != initial_space_) { - delete [] elements_; +inline RepeatedField<Element>::RepeatedField(const RepeatedField& other) + : elements_(NULL), + current_size_(0), + total_size_(kInitialSize) { + CopyFrom(other); +} + +template <typename Element> +template <typename Iter> +inline RepeatedField<Element>::RepeatedField(Iter begin, const Iter& end) + : elements_(NULL), + current_size_(0), + total_size_(kInitialSize) { + int reserve = internal::CalculateReserve(begin, end); + if (reserve != -1) { + Reserve(reserve); + for (; begin != end; ++begin) { + AddAlreadyReserved(*begin); + } + } else { + for (; begin != end; ++begin) { + Add(*begin); + } } } template <typename Element> +RepeatedField<Element>::~RepeatedField() { + delete [] elements_; +} + +template <typename Element> +inline RepeatedField<Element>& +RepeatedField<Element>::operator=(const RepeatedField& other) { + if (this != &other) + CopyFrom(other); + return *this; +} + +template <typename Element> +inline bool RepeatedField<Element>::empty() const { + return current_size_ == 0; +} + +template <typename Element> inline int RepeatedField<Element>::size() const { return current_size_; } @@ -453,20 +649,33 @@ inline Element* RepeatedField<Element>::AddAlreadyReserved() { return &elements_[current_size_++]; } +template<typename Element> +inline void RepeatedField<Element>::Resize(int new_size, const Element& value) { + GOOGLE_DCHECK_GE(new_size, 0); + if (new_size > size()) { + Reserve(new_size); + std::fill(&elements_[current_size_], &elements_[new_size], value); + } + current_size_ = new_size; +} + template <typename Element> inline const Element& RepeatedField<Element>::Get(int index) const { + GOOGLE_DCHECK_GE(index, 0); GOOGLE_DCHECK_LT(index, size()); return elements_[index]; } template <typename Element> inline Element* RepeatedField<Element>::Mutable(int index) { + GOOGLE_DCHECK_GE(index, 0); GOOGLE_DCHECK_LT(index, size()); return elements_ + index; } template <typename Element> inline void RepeatedField<Element>::Set(int index, const Element& value) { + GOOGLE_DCHECK_GE(index, 0); GOOGLE_DCHECK_LT(index, size()); elements_[index] = value; } @@ -490,15 +699,46 @@ inline void RepeatedField<Element>::RemoveLast() { } template <typename Element> +void RepeatedField<Element>::ExtractSubrange( + int start, int num, Element* elements) { + GOOGLE_DCHECK_GE(start, 0); + GOOGLE_DCHECK_GE(num, 0); + GOOGLE_DCHECK_LE(start + num, this->size()); + + // Save the values of the removed elements if requested. + if (elements != NULL) { + for (int i = 0; i < num; ++i) + elements[i] = this->Get(i + start); + } + + // Slide remaining elements down to fill the gap. + if (num > 0) { + for (int i = start + num; i < this->size(); ++i) + this->Set(i - num, this->Get(i)); + this->Truncate(this->size() - num); + } +} + +template <typename Element> inline void RepeatedField<Element>::Clear() { current_size_ = 0; } template <typename Element> inline void RepeatedField<Element>::MergeFrom(const RepeatedField& other) { - Reserve(current_size_ + other.current_size_); - CopyArray(elements_ + current_size_, other.elements_, other.current_size_); - current_size_ += other.current_size_; + GOOGLE_CHECK_NE(&other, this); + if (other.current_size_ != 0) { + Reserve(current_size_ + other.current_size_); + CopyArray(elements_ + current_size_, other.elements_, other.current_size_); + current_size_ += other.current_size_; + } +} + +template <typename Element> +inline void RepeatedField<Element>::CopyFrom(const RepeatedField& other) { + if (&other == this) return; + Clear(); + MergeFrom(other); } template <typename Element> @@ -514,35 +754,24 @@ inline const Element* RepeatedField<Element>::data() const { template <typename Element> void RepeatedField<Element>::Swap(RepeatedField* other) { + if (this == other) return; Element* swap_elements = elements_; int swap_current_size = current_size_; int swap_total_size = total_size_; - // We may not be using initial_space_ but it's not worth checking. Just - // copy it anyway. - Element swap_initial_space[kInitialSize]; - MoveArray(swap_initial_space, initial_space_, kInitialSize); elements_ = other->elements_; current_size_ = other->current_size_; total_size_ = other->total_size_; - MoveArray(initial_space_, other->initial_space_, kInitialSize); other->elements_ = swap_elements; other->current_size_ = swap_current_size; other->total_size_ = swap_total_size; - MoveArray(other->initial_space_, swap_initial_space, kInitialSize); - - if (elements_ == other->initial_space_) { - elements_ = initial_space_; - } - if (other->elements_ == initial_space_) { - other->elements_ = other->initial_space_; - } } template <typename Element> void RepeatedField<Element>::SwapElements(int index1, int index2) { - std::swap(elements_[index1], elements_[index2]); + using std::swap; // enable ADL with fallback + swap(elements_[index1], elements_[index2]); } template <typename Element> @@ -568,20 +797,21 @@ RepeatedField<Element>::end() const { template <typename Element> inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const { - return (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0; + return (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0; } -// Avoid inlining of Reserve(): new, memcpy, and delete[] lead to a significant +// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant // amount of code bloat. template <typename Element> void RepeatedField<Element>::Reserve(int new_size) { if (total_size_ >= new_size) return; Element* old_elements = elements_; - total_size_ = max(total_size_ * 2, new_size); + total_size_ = max(google::protobuf::internal::kMinRepeatedFieldAllocationSize, + max(total_size_ * 2, new_size)); elements_ = new Element[total_size_]; - MoveArray(elements_, old_elements, current_size_); - if (old_elements != initial_space_) { + if (old_elements != NULL) { + MoveArray(elements_, old_elements, current_size_); delete [] old_elements; } } @@ -594,23 +824,40 @@ inline void RepeatedField<Element>::Truncate(int new_size) { template <typename Element> inline void RepeatedField<Element>::MoveArray( - Element to[], Element from[], int size) { - memcpy(to, from, size * sizeof(Element)); + Element to[], Element from[], int array_size) { + CopyArray(to, from, array_size); } template <typename Element> inline void RepeatedField<Element>::CopyArray( - Element to[], const Element from[], int size) { - memcpy(to, from, size * sizeof(Element)); + Element to[], const Element from[], int array_size) { + internal::ElementCopier<Element>()(to, from, array_size); } +namespace internal { + +template <typename Element, bool HasTrivialCopy> +void ElementCopier<Element, HasTrivialCopy>::operator()( + Element to[], const Element from[], int array_size) { + std::copy(from, from + array_size, to); +} + +template <typename Element> +struct ElementCopier<Element, true> { + void operator()(Element to[], const Element from[], int array_size) { + memcpy(to, from, array_size * sizeof(Element)); + } +}; + +} // namespace internal + // ------------------------------------------------------------------- namespace internal { inline RepeatedPtrFieldBase::RepeatedPtrFieldBase() - : elements_(initial_space_), + : elements_(NULL), current_size_(0), allocated_size_(0), total_size_(kInitialSize) { @@ -621,26 +868,30 @@ void RepeatedPtrFieldBase::Destroy() { for (int i = 0; i < allocated_size_; i++) { TypeHandler::Delete(cast<TypeHandler>(elements_[i])); } - if (elements_ != initial_space_) { - delete [] elements_; - } + delete [] elements_; +} + +inline bool RepeatedPtrFieldBase::empty() const { + return current_size_ == 0; } inline int RepeatedPtrFieldBase::size() const { return current_size_; } - template <typename TypeHandler> inline const typename TypeHandler::Type& RepeatedPtrFieldBase::Get(int index) const { + GOOGLE_DCHECK_GE(index, 0); GOOGLE_DCHECK_LT(index, size()); return *cast<TypeHandler>(elements_[index]); } + template <typename TypeHandler> inline typename TypeHandler::Type* RepeatedPtrFieldBase::Mutable(int index) { + GOOGLE_DCHECK_GE(index, 0); GOOGLE_DCHECK_LT(index, size()); return cast<TypeHandler>(elements_[index]); } @@ -651,8 +902,8 @@ inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() { return cast<TypeHandler>(elements_[current_size_++]); } if (allocated_size_ == total_size_) Reserve(total_size_ + 1); - ++allocated_size_; typename TypeHandler::Type* result = TypeHandler::New(); + ++allocated_size_; elements_[current_size_++] = result; return result; } @@ -673,12 +924,20 @@ void RepeatedPtrFieldBase::Clear() { template <typename TypeHandler> inline void RepeatedPtrFieldBase::MergeFrom(const RepeatedPtrFieldBase& other) { + GOOGLE_CHECK_NE(&other, this); Reserve(current_size_ + other.current_size_); for (int i = 0; i < other.current_size_; i++) { - TypeHandler::Merge(other.Get<TypeHandler>(i), Add<TypeHandler>()); + TypeHandler::Merge(other.template Get<TypeHandler>(i), Add<TypeHandler>()); } } +template <typename TypeHandler> +inline void RepeatedPtrFieldBase::CopyFrom(const RepeatedPtrFieldBase& other) { + if (&other == this) return; + RepeatedPtrFieldBase::Clear<TypeHandler>(); + RepeatedPtrFieldBase::MergeFrom<TypeHandler>(other); +} + inline int RepeatedPtrFieldBase::Capacity() const { return total_size_; } @@ -707,13 +966,14 @@ RepeatedPtrFieldBase::data() const { } inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) { - std::swap(elements_[index1], elements_[index2]); + using std::swap; // enable ADL with fallback + swap(elements_[index1], elements_[index2]); } template <typename TypeHandler> inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const { int allocated_bytes = - (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0; + (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0; for (int i = 0; i < allocated_size_; ++i) { allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i])); } @@ -770,7 +1030,6 @@ inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() { return result; } - inline int RepeatedPtrFieldBase::ClearedCount() const { return allocated_size_ - current_size_; } @@ -794,22 +1053,57 @@ inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() { template <typename Element> class RepeatedPtrField<Element>::TypeHandler - : public internal::GenericTypeHandler<Element> {}; + : public internal::GenericTypeHandler<Element> { +}; template <> class RepeatedPtrField<string>::TypeHandler - : public internal::StringTypeHandler {}; + : public internal::StringTypeHandler { +}; template <typename Element> inline RepeatedPtrField<Element>::RepeatedPtrField() {} template <typename Element> +inline RepeatedPtrField<Element>::RepeatedPtrField( + const RepeatedPtrField& other) + : RepeatedPtrFieldBase() { + CopyFrom(other); +} + +template <typename Element> +template <typename Iter> +inline RepeatedPtrField<Element>::RepeatedPtrField( + Iter begin, const Iter& end) { + int reserve = internal::CalculateReserve(begin, end); + if (reserve != -1) { + Reserve(reserve); + } + for (; begin != end; ++begin) { + *Add() = *begin; + } +} + +template <typename Element> RepeatedPtrField<Element>::~RepeatedPtrField() { Destroy<TypeHandler>(); } template <typename Element> +inline RepeatedPtrField<Element>& RepeatedPtrField<Element>::operator=( + const RepeatedPtrField& other) { + if (this != &other) + CopyFrom(other); + return *this; +} + +template <typename Element> +inline bool RepeatedPtrField<Element>::empty() const { + return RepeatedPtrFieldBase::empty(); +} + +template <typename Element> inline int RepeatedPtrField<Element>::size() const { return RepeatedPtrFieldBase::size(); } @@ -819,6 +1113,7 @@ inline const Element& RepeatedPtrField<Element>::Get(int index) const { return RepeatedPtrFieldBase::Get<TypeHandler>(index); } + template <typename Element> inline Element* RepeatedPtrField<Element>::Mutable(int index) { return RepeatedPtrFieldBase::Mutable<TypeHandler>(index); @@ -835,6 +1130,33 @@ inline void RepeatedPtrField<Element>::RemoveLast() { } template <typename Element> +inline void RepeatedPtrField<Element>::DeleteSubrange(int start, int num) { + GOOGLE_DCHECK_GE(start, 0); + GOOGLE_DCHECK_GE(num, 0); + GOOGLE_DCHECK_LE(start + num, size()); + for (int i = 0; i < num; ++i) + delete RepeatedPtrFieldBase::Mutable<TypeHandler>(start + i); + ExtractSubrange(start, num, NULL); +} + +template <typename Element> +inline void RepeatedPtrField<Element>::ExtractSubrange( + int start, int num, Element** elements) { + GOOGLE_DCHECK_GE(start, 0); + GOOGLE_DCHECK_GE(num, 0); + GOOGLE_DCHECK_LE(start + num, size()); + + if (num > 0) { + // Save the values of the removed elements if requested. + if (elements != NULL) { + for (int i = 0; i < num; ++i) + elements[i] = RepeatedPtrFieldBase::Mutable<TypeHandler>(i + start); + } + CloseGap(start, num); + } +} + +template <typename Element> inline void RepeatedPtrField<Element>::Clear() { RepeatedPtrFieldBase::Clear<TypeHandler>(); } @@ -846,6 +1168,12 @@ inline void RepeatedPtrField<Element>::MergeFrom( } template <typename Element> +inline void RepeatedPtrField<Element>::CopyFrom( + const RepeatedPtrField& other) { + RepeatedPtrFieldBase::CopyFrom<TypeHandler>(other); +} + +template <typename Element> inline Element** RepeatedPtrField<Element>::mutable_data() { return RepeatedPtrFieldBase::mutable_data<TypeHandler>(); } @@ -914,7 +1242,7 @@ namespace internal { // refer to this class directly; use RepeatedPtrField<T>::iterator instead. // // The iterator for RepeatedPtrField<T>, RepeatedPtrIterator<T>, is -// very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors-inl.h, +// very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors.h, // but adds random-access operators and is modified to wrap a void** base // iterator (since RepeatedPtrField stores its array as a void* array and // casting void** to T** would violate C++ aliasing rules). @@ -930,6 +1258,10 @@ class RepeatedPtrIterator typedef std::iterator< std::random_access_iterator_tag, Element> superclass; + // Shadow the value_type in std::iterator<> because const_iterator::value_type + // needs to be T, not const T. + typedef typename remove_const<Element>::type value_type; + // Let the compiler know that these are type names, so we don't have to // write "typename" in front of them everywhere. typedef typename superclass::reference reference; @@ -944,7 +1276,7 @@ class RepeatedPtrIterator template<typename OtherElement> RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other) : it_(other.it_) { - // Force a compiler error if the other type is not convertable to ours. + // Force a compiler error if the other type is not convertible to ours. if (false) { implicit_cast<Element*, OtherElement*>(0); } @@ -1010,14 +1342,21 @@ class RepeatedPtrIterator // rather than the objects themselves as RepeatedPtrIterator does. // Consider using this when working with stl algorithms that change // the array. -template<typename Element> +// The VoidPtr template parameter holds the type-agnostic pointer value +// referenced by the iterator. It should either be "void *" for a mutable +// iterator, or "const void *" for a constant iterator. +template<typename Element, typename VoidPtr> class RepeatedPtrOverPtrsIterator : public std::iterator<std::random_access_iterator_tag, Element*> { public: - typedef RepeatedPtrOverPtrsIterator<Element> iterator; + typedef RepeatedPtrOverPtrsIterator<Element, VoidPtr> iterator; typedef std::iterator< std::random_access_iterator_tag, Element*> superclass; + // Shadow the value_type in std::iterator<> because const_iterator::value_type + // needs to be T, not const T. + typedef typename remove_const<Element*>::type value_type; + // Let the compiler know that these are type names, so we don't have to // write "typename" in front of them everywhere. typedef typename superclass::reference reference; @@ -1025,7 +1364,7 @@ class RepeatedPtrOverPtrsIterator typedef typename superclass::difference_type difference_type; RepeatedPtrOverPtrsIterator() : it_(NULL) {} - explicit RepeatedPtrOverPtrsIterator(void** it) : it_(it) {} + explicit RepeatedPtrOverPtrsIterator(VoidPtr* it) : it_(it) {} // dereferenceable reference operator*() const { return *reinterpret_cast<Element**>(it_); } @@ -1080,10 +1419,9 @@ class RepeatedPtrOverPtrsIterator friend class RepeatedPtrIterator; // The internal iterator. - void** it_; + VoidPtr* it_; }; - } // namespace internal template <typename Element> @@ -1113,10 +1451,21 @@ RepeatedPtrField<Element>::pointer_begin() { return pointer_iterator(raw_mutable_data()); } template <typename Element> +inline typename RepeatedPtrField<Element>::const_pointer_iterator +RepeatedPtrField<Element>::pointer_begin() const { + return const_pointer_iterator(const_cast<const void**>(raw_mutable_data())); +} +template <typename Element> inline typename RepeatedPtrField<Element>::pointer_iterator RepeatedPtrField<Element>::pointer_end() { return pointer_iterator(raw_mutable_data() + size()); } +template <typename Element> +inline typename RepeatedPtrField<Element>::const_pointer_iterator +RepeatedPtrField<Element>::pointer_end() const { + return const_pointer_iterator( + const_cast<const void**>(raw_mutable_data() + size())); +} // Iterators and helper functions that follow the spirit of the STL @@ -1126,7 +1475,7 @@ RepeatedPtrField<Element>::pointer_end() { // std::copy(some_sequence.begin(), some_sequence.end(), // google::protobuf::RepeatedFieldBackInserter(proto.mutable_sequence())); // -// Ported by johannes from util/gtl/proto-array-iterators-inl.h +// Ported by johannes from util/gtl/proto-array-iterators.h namespace internal { // A back inserter for RepeatedField objects. @@ -1147,12 +1496,12 @@ template<typename T> class RepeatedFieldBackInsertIterator RepeatedFieldBackInsertIterator<T>& operator++() { return *this; } - RepeatedFieldBackInsertIterator<T>& operator++(int ignores_parameter) { + RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) { return *this; } private: - RepeatedField<T>* const field_; + RepeatedField<T>* field_; }; // A back inserter for RepeatedPtrField objects. @@ -1178,12 +1527,12 @@ template<typename T> class RepeatedPtrFieldBackInsertIterator RepeatedPtrFieldBackInsertIterator<T>& operator++() { return *this; } - RepeatedPtrFieldBackInsertIterator<T>& operator++(int ignores_parameter) { + RepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) { return *this; } private: - RepeatedPtrField<T>* const field_; + RepeatedPtrField<T>* field_; }; // A back inserter for RepeatedPtrFields that inserts by transfering ownership @@ -1207,26 +1556,32 @@ template<typename T> class AllocatedRepeatedPtrFieldBackInsertIterator return *this; } AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++( - int ignores_parameter) { + int /* unused */) { return *this; } private: - RepeatedPtrField<T>* const field_; + RepeatedPtrField<T>* field_; }; } // namespace internal // Provides a back insert iterator for RepeatedField instances, -// similar to std::back_inserter(). Note the identically named -// function for RepeatedPtrField instances. +// similar to std::back_inserter(). template<typename T> internal::RepeatedFieldBackInsertIterator<T> RepeatedFieldBackInserter(RepeatedField<T>* const mutable_field) { return internal::RepeatedFieldBackInsertIterator<T>(mutable_field); } // Provides a back insert iterator for RepeatedPtrField instances, -// similar to std::back_inserter(). Note the identically named -// function for RepeatedField instances. +// similar to std::back_inserter(). +template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> +RepeatedPtrFieldBackInserter(RepeatedPtrField<T>* const mutable_field) { + return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field); +} + +// Special back insert iterator for RepeatedPtrField instances, just in +// case someone wants to write generic template code that can access both +// RepeatedFields and RepeatedPtrFields using a common name. template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> RepeatedFieldBackInserter(RepeatedPtrField<T>* const mutable_field) { return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field); |