aboutsummaryrefslogtreecommitdiffstats
path: root/src/google/protobuf/repeated_field.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/google/protobuf/repeated_field.h')
-rw-r--r--src/google/protobuf/repeated_field.h547
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);