From b55a20fa2c669b181f47ea9219b8e74d1263da19 Mon Sep 17 00:00:00 2001 From: "xiaofeng@google.com" Date: Sat, 22 Sep 2012 02:40:50 +0000 Subject: Down-integrate from internal branch --- src/google/protobuf/repeated_field.h | 339 ++++++++++++++++++++++++++++++----- 1 file changed, 293 insertions(+), 46 deletions(-) (limited to 'src/google/protobuf/repeated_field.h') diff --git a/src/google/protobuf/repeated_field.h b/src/google/protobuf/repeated_field.h index aed4ce9f..f0032e7d 100644 --- a/src/google/protobuf/repeated_field.h +++ b/src/google/protobuf/repeated_field.h @@ -46,24 +46,35 @@ #ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__ #define GOOGLE_PROTOBUF_REPEATED_FIELD_H__ +#include #include #include #include +#include +#include #include namespace google { +namespace upb { +namespace proto2_bridge_opensource { +class FieldAccessor; +} // namespace protobuf_bridge_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); } // 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, @@ -73,6 +84,8 @@ class RepeatedField { public: RepeatedField(); RepeatedField(const RepeatedField& other); + template + RepeatedField(Iter begin, const Iter& end); ~RepeatedField(); RepeatedField& operator=(const RepeatedField& other); @@ -85,12 +98,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); @@ -121,25 +136,49 @@ class RepeatedField { 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_reverse_iterator; + typedef std::reverse_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 = 4; + static const int kInitialSize = 0; + + // This cannot be the last attribute defined if kInitialSize is 0 or + // the checks elements_ != initial_space_ to delete are not valid. + Element initial_space_[kInitialSize]; 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. @@ -151,7 +190,21 @@ class RepeatedField { namespace internal { template class RepeatedPtrIterator; -template class RepeatedPtrOverPtrsIterator; +template 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 ::value> +struct ElementCopier { + void operator()(Element to[], const Element from[], int array_size); +}; + } // namespace internal namespace internal { @@ -186,6 +239,10 @@ 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 FieldAccessor + // needs to be able to modify a RepeatedPtrFieldBase directly. + friend class LIBPROTOBUF_EXPORT upb::proto2_bridge_opensource::FieldAccessor; + RepeatedPtrFieldBase(); // Must be called from destructor. @@ -209,6 +266,14 @@ class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { template 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); int Capacity() const; @@ -250,15 +315,17 @@ class LIBPROTOBUF_EXPORT RepeatedPtrFieldBase { private: GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrFieldBase); - static const int kInitialSize = 4; + static const int kInitialSize = 0; + + // This cannot be the last attribute defined if kInitialSize is 0 or + // the checks elements_ != initial_space_ to delete are not valid. + void* initial_space_[kInitialSize]; void** elements_; int current_size_; int allocated_size_; int total_size_; - void* initial_space_[kInitialSize]; - template static inline typename TypeHandler::Type* cast(void* element) { return reinterpret_cast(element); @@ -280,6 +347,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 <> @@ -288,6 +356,25 @@ inline void GenericTypeHandler::Merge( to->CheckTypeAndMergeFrom(from); } +template <> +inline const MessageLite& GenericTypeHandler::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::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 @@ -303,6 +390,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::kEmptyString; + } }; class StringTypeHandler : public StringTypeHandlerBase { @@ -322,6 +412,8 @@ class RepeatedPtrField : public internal::RepeatedPtrFieldBase { public: RepeatedPtrField(); RepeatedPtrField(const RepeatedPtrField& other); + template + RepeatedPtrField(Iter begin, const Iter& end); ~RepeatedPtrField(); RepeatedPtrField& operator=(const RepeatedPtrField& other); @@ -331,7 +423,16 @@ class RepeatedPtrField : public internal::RepeatedPtrFieldBase { 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); @@ -358,42 +459,78 @@ class RepeatedPtrField : public internal::RepeatedPtrFieldBase { typedef internal::RepeatedPtrIterator iterator; typedef internal::RepeatedPtrIterator 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_reverse_iterator; + typedef std::reverse_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 pointer_iterator; + typedef internal::RepeatedPtrOverPtrsIterator + pointer_iterator; + typedef internal::RepeatedPtrOverPtrsIterator + 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; // 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. @@ -433,6 +570,17 @@ inline RepeatedField::RepeatedField(const RepeatedField& other) CopyFrom(other); } +template +template +inline RepeatedField::RepeatedField(Iter begin, const Iter& end) + : elements_(initial_space_), + current_size_(0), + total_size_(kInitialSize) { + for (; begin != end; ++begin) { + Add(*begin); + } +} + template RepeatedField::~RepeatedField() { if (elements_ != initial_space_) { @@ -443,7 +591,8 @@ RepeatedField::~RepeatedField() { template inline RepeatedField& RepeatedField::operator=(const RepeatedField& other) { - CopyFrom(other); + if (this != &other) + CopyFrom(other); return *this; } @@ -505,6 +654,27 @@ inline void RepeatedField::RemoveLast() { --current_size_; } +template +void RepeatedField::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 inline void RepeatedField::Clear() { current_size_ = 0; @@ -536,6 +706,7 @@ inline const Element* RepeatedField::data() const { template void RepeatedField::Swap(RepeatedField* other) { + if (this == other) return; Element* swap_elements = elements_; int swap_current_size = current_size_; int swap_total_size = total_size_; @@ -593,14 +764,15 @@ inline int RepeatedField::SpaceUsedExcludingSelf() const { return (elements_ != initial_space_) ? 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 void RepeatedField::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_) { @@ -617,15 +789,32 @@ inline void RepeatedField::Truncate(int new_size) { template inline void RepeatedField::MoveArray( Element to[], Element from[], int array_size) { - memcpy(to, from, array_size * sizeof(Element)); + CopyArray(to, from, array_size); } template inline void RepeatedField::CopyArray( Element to[], const Element from[], int array_size) { - memcpy(to, from, array_size * sizeof(Element)); + internal::ElementCopier()(to, from, array_size); } +namespace internal { + +template +void ElementCopier::operator()( + Element to[], const Element from[], int array_size) { + std::copy(from, from + array_size, to); +} + +template +struct ElementCopier { + void operator()(Element to[], const Element from[], int array_size) { + memcpy(to, from, array_size * sizeof(Element)); + } +}; + +} // namespace internal + // ------------------------------------------------------------------- @@ -652,7 +841,6 @@ inline int RepeatedPtrFieldBase::size() const { return current_size_; } - template inline const typename TypeHandler::Type& RepeatedPtrFieldBase::Get(int index) const { @@ -660,6 +848,7 @@ RepeatedPtrFieldBase::Get(int index) const { return *cast(elements_[index]); } + template inline typename TypeHandler::Type* RepeatedPtrFieldBase::Mutable(int index) { @@ -798,7 +987,6 @@ inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseLast() { return result; } - inline int RepeatedPtrFieldBase::ClearedCount() const { return allocated_size_ - current_size_; } @@ -822,11 +1010,13 @@ inline typename TypeHandler::Type* RepeatedPtrFieldBase::ReleaseCleared() { template class RepeatedPtrField::TypeHandler - : public internal::GenericTypeHandler {}; + : public internal::GenericTypeHandler { +}; template <> class RepeatedPtrField::TypeHandler - : public internal::StringTypeHandler {}; + : public internal::StringTypeHandler { +}; template @@ -838,6 +1028,15 @@ inline RepeatedPtrField::RepeatedPtrField( CopyFrom(other); } +template +template +inline RepeatedPtrField::RepeatedPtrField( + Iter begin, const Iter& end) { + for (; begin != end; ++begin) { + *Add() = *begin; + } +} + template RepeatedPtrField::~RepeatedPtrField() { Destroy(); @@ -846,7 +1045,8 @@ RepeatedPtrField::~RepeatedPtrField() { template inline RepeatedPtrField& RepeatedPtrField::operator=( const RepeatedPtrField& other) { - CopyFrom(other); + if (this != &other) + CopyFrom(other); return *this; } @@ -860,6 +1060,7 @@ inline const Element& RepeatedPtrField::Get(int index) const { return RepeatedPtrFieldBase::Get(index); } + template inline Element* RepeatedPtrField::Mutable(int index) { return RepeatedPtrFieldBase::Mutable(index); @@ -875,6 +1076,33 @@ inline void RepeatedPtrField::RemoveLast() { RepeatedPtrFieldBase::RemoveLast(); } +template +inline void RepeatedPtrField::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(start + i); + ExtractSubrange(start, num, NULL); +} + +template +inline void RepeatedPtrField::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(i + start); + } + CloseGap(start, num); + } +} + template inline void RepeatedPtrField::Clear() { RepeatedPtrFieldBase::Clear(); @@ -961,7 +1189,7 @@ namespace internal { // refer to this class directly; use RepeatedPtrField::iterator instead. // // The iterator for RepeatedPtrField, RepeatedPtrIterator, is -// very similar to iterator_ptr in util/gtl/iterator_adaptors-inl.h, +// very similar to iterator_ptr 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). @@ -1057,11 +1285,14 @@ class RepeatedPtrIterator // rather than the objects themselves as RepeatedPtrIterator does. // Consider using this when working with stl algorithms that change // the array. -template +// 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 class RepeatedPtrOverPtrsIterator : public std::iterator { public: - typedef RepeatedPtrOverPtrsIterator iterator; + typedef RepeatedPtrOverPtrsIterator iterator; typedef std::iterator< std::random_access_iterator_tag, Element*> superclass; @@ -1072,7 +1303,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(it_); } @@ -1127,10 +1358,9 @@ class RepeatedPtrOverPtrsIterator friend class RepeatedPtrIterator; // The internal iterator. - void** it_; + VoidPtr* it_; }; - } // namespace internal template @@ -1160,10 +1390,21 @@ RepeatedPtrField::pointer_begin() { return pointer_iterator(raw_mutable_data()); } template +inline typename RepeatedPtrField::const_pointer_iterator +RepeatedPtrField::pointer_begin() const { + return const_pointer_iterator(const_cast(raw_mutable_data())); +} +template inline typename RepeatedPtrField::pointer_iterator RepeatedPtrField::pointer_end() { return pointer_iterator(raw_mutable_data() + size()); } +template +inline typename RepeatedPtrField::const_pointer_iterator +RepeatedPtrField::pointer_end() const { + return const_pointer_iterator( + const_cast(raw_mutable_data() + size())); +} // Iterators and helper functions that follow the spirit of the STL @@ -1173,7 +1414,7 @@ RepeatedPtrField::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. @@ -1194,7 +1435,7 @@ template class RepeatedFieldBackInsertIterator RepeatedFieldBackInsertIterator& operator++() { return *this; } - RepeatedFieldBackInsertIterator& operator++(int ignores_parameter) { + RepeatedFieldBackInsertIterator& operator++(int /* unused */) { return *this; } @@ -1225,7 +1466,7 @@ template class RepeatedPtrFieldBackInsertIterator RepeatedPtrFieldBackInsertIterator& operator++() { return *this; } - RepeatedPtrFieldBackInsertIterator& operator++(int ignores_parameter) { + RepeatedPtrFieldBackInsertIterator& operator++(int /* unused */) { return *this; } @@ -1254,7 +1495,7 @@ template class AllocatedRepeatedPtrFieldBackInsertIterator return *this; } AllocatedRepeatedPtrFieldBackInsertIterator& operator++( - int ignores_parameter) { + int /* unused */) { return *this; } @@ -1264,16 +1505,22 @@ template class AllocatedRepeatedPtrFieldBackInsertIterator } // 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 internal::RepeatedFieldBackInsertIterator RepeatedFieldBackInserter(RepeatedField* const mutable_field) { return internal::RepeatedFieldBackInsertIterator(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 internal::RepeatedPtrFieldBackInsertIterator +RepeatedPtrFieldBackInserter(RepeatedPtrField* const mutable_field) { + return internal::RepeatedPtrFieldBackInsertIterator(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 internal::RepeatedPtrFieldBackInsertIterator RepeatedFieldBackInserter(RepeatedPtrField* const mutable_field) { return internal::RepeatedPtrFieldBackInsertIterator(mutable_field); -- cgit v1.2.3