diff options
Diffstat (limited to 'src/google/protobuf/repeated_field.h')
-rw-r--r-- | src/google/protobuf/repeated_field.h | 547 |
1 files changed, 96 insertions, 451 deletions
diff --git a/src/google/protobuf/repeated_field.h b/src/google/protobuf/repeated_field.h index 5005183..defdefe 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. -// https://developers.google.com/protocol-buffers/ +// http://code.google.com/p/protobuf/ // // Redistribution and use in source and binary forms, with or without // modification, are permitted provided that the following conditions are @@ -46,55 +46,24 @@ #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 { -static const int kMinRepeatedFieldAllocationSize = 4; - -// A utility function for logging that doesn't need any template types. -void LogIndexOutOfBounds(int index, int size); +// We need this (from generated_message_reflection.cc). +LIBPROTOBUF_EXPORT int StringSpaceUsedExcludingSelf(const string& str); -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, @@ -103,14 +72,8 @@ 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; @@ -119,17 +82,14 @@ 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. @@ -142,11 +102,6 @@ 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(); @@ -161,46 +116,27 @@ 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: - static const int kInitialSize = 0; + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedField); + + static const int kInitialSize = 4; 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. @@ -212,21 +148,7 @@ class RepeatedField { namespace internal { template <typename It> class RepeatedPtrIterator; -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); -}; - +template <typename It> class RepeatedPtrOverPtrsIterator; } // namespace internal namespace internal { @@ -261,17 +183,12 @@ 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> @@ -286,16 +203,6 @@ 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); @@ -336,13 +243,17 @@ class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { typename TypeHandler::Type* ReleaseCleared(); private: - static const int kInitialSize = 0; + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase); + + static const int kInitialSize = 4; 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); @@ -351,8 +262,6 @@ 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> @@ -366,7 +275,6 @@ class GenericTypeHandler { to->MergeFrom(from); } static int SpaceUsed(const GenericType& value) { return value.SpaceUsed(); } - static const Type& default_instance() { return Type::default_instance(); } }; template <> @@ -375,25 +283,6 @@ 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 @@ -409,9 +298,6 @@ 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 { @@ -430,32 +316,17 @@ 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); + ~RepeatedPtrField(); - bool empty() const; int size() const; const Element& Get(int index) const; Element* Mutable(int index); Element* Add(); - - // 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 RemoveLast(); // Remove the last element in the array. 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 @@ -478,79 +349,47 @@ 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, void*> - pointer_iterator; - typedef internal::RepeatedPtrOverPtrsIterator<const Element, const void*> - const_pointer_iterator; + typedef internal::RepeatedPtrOverPtrsIterator<Element> 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 sometimes + // When hardcore memory management becomes necessary -- as it often // 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. // - // Hardcore programs may choose to manipulate these cleared objects - // to better optimize memory management using the following routines. + // Really, extremely hardcore programs may actually want to manipulate + // these objects to better-optimize memory management. These methods + // allow that. // Get the number of cleared objects that are currently being kept // around for reuse. @@ -571,60 +410,25 @@ 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_(NULL), + : elements_(initial_space_), current_size_(0), total_size_(kInitialSize) { } template <typename Element> -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; + if (elements_ != initial_space_) { + delete [] elements_; + } } template <typename Element> @@ -649,33 +453,20 @@ 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; } @@ -699,46 +490,15 @@ 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) { - 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); + Reserve(current_size_ + other.current_size_); + CopyArray(elements_ + current_size_, other.elements_, other.current_size_); + current_size_ += other.current_size_; } template <typename Element> @@ -754,24 +514,35 @@ 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) { - using std::swap; // enable ADL with fallback - swap(elements_[index1], elements_[index2]); + std::swap(elements_[index1], elements_[index2]); } template <typename Element> @@ -797,21 +568,20 @@ RepeatedField<Element>::end() const { template <typename Element> inline int RepeatedField<Element>::SpaceUsedExcludingSelf() const { - return (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0; + return (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0; } -// Avoid inlining of Reserve(): new, copy, and delete[] lead to a significant +// Avoid inlining of Reserve(): new, memcpy, 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(google::protobuf::internal::kMinRepeatedFieldAllocationSize, - max(total_size_ * 2, new_size)); + total_size_ = max(total_size_ * 2, new_size); elements_ = new Element[total_size_]; - if (old_elements != NULL) { - MoveArray(elements_, old_elements, current_size_); + MoveArray(elements_, old_elements, current_size_); + if (old_elements != initial_space_) { delete [] old_elements; } } @@ -824,40 +594,23 @@ inline void RepeatedField<Element>::Truncate(int new_size) { template <typename Element> inline void RepeatedField<Element>::MoveArray( - Element to[], Element from[], int array_size) { - CopyArray(to, from, array_size); + Element to[], Element from[], int size) { + memcpy(to, from, size * sizeof(Element)); } template <typename Element> inline void RepeatedField<Element>::CopyArray( - Element to[], const Element from[], int array_size) { - internal::ElementCopier<Element>()(to, from, array_size); + Element to[], const Element from[], int size) { + memcpy(to, from, size * sizeof(Element)); } -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_(NULL), + : elements_(initial_space_), current_size_(0), allocated_size_(0), total_size_(kInitialSize) { @@ -868,30 +621,26 @@ void RepeatedPtrFieldBase::Destroy() { for (int i = 0; i < allocated_size_; i++) { TypeHandler::Delete(cast<TypeHandler>(elements_[i])); } - delete [] elements_; -} - -inline bool RepeatedPtrFieldBase::empty() const { - return current_size_ == 0; + if (elements_ != initial_space_) { + delete [] elements_; + } } 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]); } @@ -902,8 +651,8 @@ inline typename TypeHandler::Type* RepeatedPtrFieldBase::Add() { return cast<TypeHandler>(elements_[current_size_++]); } if (allocated_size_ == total_size_) Reserve(total_size_ + 1); - typename TypeHandler::Type* result = TypeHandler::New(); ++allocated_size_; + typename TypeHandler::Type* result = TypeHandler::New(); elements_[current_size_++] = result; return result; } @@ -924,20 +673,12 @@ 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.template Get<TypeHandler>(i), Add<TypeHandler>()); + TypeHandler::Merge(other.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_; } @@ -966,14 +707,13 @@ RepeatedPtrFieldBase::data() const { } inline void RepeatedPtrFieldBase::SwapElements(int index1, int index2) { - using std::swap; // enable ADL with fallback - swap(elements_[index1], elements_[index2]); + std::swap(elements_[index1], elements_[index2]); } template <typename TypeHandler> inline int RepeatedPtrFieldBase::SpaceUsedExcludingSelf() const { int allocated_bytes = - (elements_ != NULL) ? total_size_ * sizeof(elements_[0]) : 0; + (elements_ != initial_space_) ? total_size_ * sizeof(elements_[0]) : 0; for (int i = 0; i < allocated_size_; ++i) { allocated_bytes += TypeHandler::SpaceUsed(*cast<TypeHandler>(elements_[i])); } @@ -1030,6 +770,7 @@ inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() { return result; } + inline int RepeatedPtrFieldBase::ClearedCount() const { return allocated_size_ - current_size_; } @@ -1053,57 +794,22 @@ 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(); } @@ -1113,7 +819,6 @@ 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); @@ -1130,33 +835,6 @@ 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>(); } @@ -1168,12 +846,6 @@ 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>(); } @@ -1242,7 +914,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.h, +// very similar to iterator_ptr<T**> in util/gtl/iterator_adaptors-inl.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). @@ -1258,10 +930,6 @@ 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; @@ -1276,7 +944,7 @@ class RepeatedPtrIterator template<typename OtherElement> RepeatedPtrIterator(const RepeatedPtrIterator<OtherElement>& other) : it_(other.it_) { - // Force a compiler error if the other type is not convertible to ours. + // Force a compiler error if the other type is not convertable to ours. if (false) { implicit_cast<Element*, OtherElement*>(0); } @@ -1342,21 +1010,14 @@ class RepeatedPtrIterator // rather than the objects themselves as RepeatedPtrIterator does. // Consider using this when working with stl algorithms that change // the array. -// 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> +template<typename Element> class RepeatedPtrOverPtrsIterator : public std::iterator<std::random_access_iterator_tag, Element*> { public: - typedef RepeatedPtrOverPtrsIterator<Element, VoidPtr> iterator; + typedef RepeatedPtrOverPtrsIterator<Element> 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; @@ -1364,7 +1025,7 @@ class RepeatedPtrOverPtrsIterator typedef typename superclass::difference_type difference_type; RepeatedPtrOverPtrsIterator() : it_(NULL) {} - explicit RepeatedPtrOverPtrsIterator(VoidPtr* it) : it_(it) {} + explicit RepeatedPtrOverPtrsIterator(void** it) : it_(it) {} // dereferenceable reference operator*() const { return *reinterpret_cast<Element**>(it_); } @@ -1419,9 +1080,10 @@ class RepeatedPtrOverPtrsIterator friend class RepeatedPtrIterator; // The internal iterator. - VoidPtr* it_; + void** it_; }; + } // namespace internal template <typename Element> @@ -1451,21 +1113,10 @@ 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 @@ -1475,7 +1126,7 @@ RepeatedPtrField<Element>::pointer_end() const { // std::copy(some_sequence.begin(), some_sequence.end(), // google::protobuf::RepeatedFieldBackInserter(proto.mutable_sequence())); // -// Ported by johannes from util/gtl/proto-array-iterators.h +// Ported by johannes from util/gtl/proto-array-iterators-inl.h namespace internal { // A back inserter for RepeatedField objects. @@ -1496,12 +1147,12 @@ template<typename T> class RepeatedFieldBackInsertIterator RepeatedFieldBackInsertIterator<T>& operator++() { return *this; } - RepeatedFieldBackInsertIterator<T>& operator++(int /* unused */) { + RepeatedFieldBackInsertIterator<T>& operator++(int ignores_parameter) { return *this; } private: - RepeatedField<T>* field_; + RepeatedField<T>* const field_; }; // A back inserter for RepeatedPtrField objects. @@ -1527,12 +1178,12 @@ template<typename T> class RepeatedPtrFieldBackInsertIterator RepeatedPtrFieldBackInsertIterator<T>& operator++() { return *this; } - RepeatedPtrFieldBackInsertIterator<T>& operator++(int /* unused */) { + RepeatedPtrFieldBackInsertIterator<T>& operator++(int ignores_parameter) { return *this; } private: - RepeatedPtrField<T>* field_; + RepeatedPtrField<T>* const field_; }; // A back inserter for RepeatedPtrFields that inserts by transfering ownership @@ -1556,32 +1207,26 @@ template<typename T> class AllocatedRepeatedPtrFieldBackInsertIterator return *this; } AllocatedRepeatedPtrFieldBackInsertIterator<T>& operator++( - int /* unused */) { + int ignores_parameter) { return *this; } private: - RepeatedPtrField<T>* field_; + RepeatedPtrField<T>* const field_; }; } // namespace internal // Provides a back insert iterator for RepeatedField instances, -// similar to std::back_inserter(). +// similar to std::back_inserter(). Note the identically named +// function for RepeatedPtrField instances. 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(). -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. +// similar to std::back_inserter(). Note the identically named +// function for RepeatedField instances. template<typename T> internal::RepeatedPtrFieldBackInsertIterator<T> RepeatedFieldBackInserter(RepeatedPtrField<T>* const mutable_field) { return internal::RepeatedPtrFieldBackInsertIterator<T>(mutable_field); |