From 40ee551715c3a784ea6132dbf604b0e665ca2def Mon Sep 17 00:00:00 2001 From: temporal Date: Thu, 10 Jul 2008 02:12:20 +0000 Subject: Initial checkin. --- src/google/protobuf/repeated_field.h | 782 +++++++++++++++++++++++++++++++++++ 1 file changed, 782 insertions(+) create mode 100644 src/google/protobuf/repeated_field.h (limited to 'src/google/protobuf/repeated_field.h') diff --git a/src/google/protobuf/repeated_field.h b/src/google/protobuf/repeated_field.h new file mode 100644 index 00000000..3368e8b7 --- /dev/null +++ b/src/google/protobuf/repeated_field.h @@ -0,0 +1,782 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2008 Google Inc. +// http://code.google.com/p/protobuf/ +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// Author: kenton@google.com (Kenton Varda) +// Based on original Protocol Buffers design by +// Sanjay Ghemawat, Jeff Dean, and others. +// +// RepeatedField and RepeatedPtrField are used by generated protocol message +// classes to manipulate repeated fields. These classes are very similar to +// STL's vector, but include a number of optimizations found to be useful +// specifically in the case of Protocol Buffers. RepeatedPtrField is +// particularly different from STL vector as it manages ownership of the +// pointers that it contains. +// +// Typically, clients should not need to access RepeatedField objects directly, +// but should instead use the accessor functions generated automatically by the +// protocol compiler. + +#ifndef GOOGLE_PROTOBUF_REPEATED_FIELD_H__ +#define GOOGLE_PROTOBUF_REPEATED_FIELD_H__ + +#include +#include +#include +#include + + +namespace google { +namespace protobuf { + +namespace internal { + +// DO NOT USE GenericRepeatedField; it should be considered a private detail +// of RepeatedField/RepeatedPtrField that may be removed in the future. +// GeneratedMessageReflection needs to manipulate repeated fields in a +// generic way, so we have them implement this interface. This should ONLY +// be used by GeneratedMessageReflection. This would normally be very bad +// design but GeneratedMessageReflection is a big efficiency hack anyway. +// +// TODO(kenton): Implement something like Jeff's ProtoVoidPtrArray change. +// Then, get rid of GenericRepeatedField. +class LIBPROTOBUF_EXPORT GenericRepeatedField { + public: + inline GenericRepeatedField() {} + virtual ~GenericRepeatedField(); + + private: + // We only want GeneratedMessageReflection to see and use these, so we + // make them private. Yes, it is valid C++ for a subclass to implement + // a virtual method which is private in the superclass. Crazy, huh? + friend class GeneratedMessageReflection; + + virtual const void* GenericGet(int index) const = 0; + virtual void* GenericMutable(int index) = 0; + virtual void* GenericAdd() = 0; + virtual void GenericClear() = 0; + virtual int GenericSize() const = 0; + + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(GenericRepeatedField); +}; + +} // 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, +// set-by-index, and add accessors that are generated for all repeated fields. +template +class RepeatedField : public internal::GenericRepeatedField { + public: + RepeatedField(); + ~RepeatedField(); + + int size() const; + + Element Get(int index) const; + Element* Mutable(int index); + void Set(int index, Element value); + void Add(Element value); + // 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(); + void Clear(); + void MergeFrom(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. + void Reserve(int new_size); + + // Gets the underlying array. This pointer is possibly invalidated by + // any add or remove operation. + Element* mutable_data(); + const Element* data() const; + + // Swap entire contents with "other". + void Swap(RepeatedField* other); + + // STL-like iterator support + typedef Element* iterator; + typedef const Element* const_iterator; + + iterator begin(); + const_iterator begin() const; + iterator end(); + const_iterator end() const; + + private: // See GenericRepeatedField for why this is private. + // implements GenericRepeatedField --------------------------------- + const void* GenericGet(int index) const; + void* GenericMutable(int index); + void* GenericAdd(); + void GenericClear(); + int GenericSize() const; + + private: + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedField); + + static const int kInitialSize = 4; + + Element* elements_; + int current_size_; + int total_size_; + + Element initial_space_[kInitialSize]; +}; + +namespace internal { +template class RepeatedPtrIterator; +} // namespace internal + +// RepeatedPtrField is like RepeatedField, but used for repeated strings or +// Messages. +template +class RepeatedPtrField : public internal::GenericRepeatedField { + public: + RepeatedPtrField(); + + // This constructor is only defined for RepeatedPtrField. + // When a RepeatedPtrField is created using this constructor, + // prototype->New() will be called to allocate new elements, rather than + // just using the "new" operator. This is useful for the implementation + // of DynamicMessage, but is not used by normal generated messages. + explicit RepeatedPtrField(const Message* prototype); + + ~RepeatedPtrField(); + + // Returns the prototype if one was passed to the constructor. + const Message* prototype() 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. + void Clear(); + void MergeFrom(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 + // array is grown, it will always be at least doubled in size. + void Reserve(int new_size); + + // Gets the underlying array. This pointer is possibly invalidated by + // any add or remove operation. + Element** mutable_data(); + const Element* const* data() const; + + // Swap entire contents with "other". + void Swap(RepeatedPtrField* other); + + // STL-like iterator support + typedef internal::RepeatedPtrIterator iterator; + typedef internal::RepeatedPtrIterator const_iterator; + + iterator begin(); + const_iterator begin() const; + iterator end(); + const_iterator end() const; + + // Advanced memory management -------------------------------------- + // 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. + // Requires: size() > 0 + Element* ReleaseLast(); + + // 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. + + // Get the number of cleared objects that are currently being kept + // around for reuse. + int ClearedCount(); + // Add an element to the pool of cleared objects, passing ownership to + // the RepeatedPtrField. The element must be cleared prior to calling + // this method. + void AddCleared(Element* value); + // Remove a single element from the cleared pool and return it, passing + // ownership to the caller. The element is guaranteed to be cleared. + // Requires: ClearedCount() > 0 + Element* ReleaseCleared(); + + private: // See GenericRepeatedField for why this is private. + // implements GenericRepeatedField --------------------------------- + const void* GenericGet(int index) const; + void* GenericMutable(int index); + void* GenericAdd(); + void GenericClear(); + int GenericSize() const; + + private: + GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(RepeatedPtrField); + + static const int kInitialSize = 4; + + // prototype_ is used for RepeatedPtrField only (see constructor). + const Message* prototype_; + + Element** elements_; + int current_size_; + int allocated_size_; + int total_size_; + + Element* initial_space_[kInitialSize]; + + Element* NewElement(); +}; + +// implementation ==================================================== + +template +inline RepeatedField::RepeatedField() + : elements_(initial_space_), + current_size_(0), + total_size_(kInitialSize) { +} + +template +RepeatedField::~RepeatedField() { + if (elements_ != initial_space_) { + delete [] elements_; + } +} + +template +inline int RepeatedField::size() const { + return current_size_; +} + + +template +inline Element RepeatedField::Get(int index) const { + GOOGLE_DCHECK_LT(index, size()); + return elements_[index]; +} + +template +inline Element* RepeatedField::Mutable(int index) { + GOOGLE_DCHECK_LT(index, size()); + return elements_ + index; +} + +template +inline void RepeatedField::Set(int index, Element value) { + GOOGLE_DCHECK_LT(index, size()); + elements_[index] = value; +} + +template +inline void RepeatedField::Add(Element value) { + if (current_size_ == total_size_) Reserve(total_size_ + 1); + elements_[current_size_++] = value; +} + +template +inline void RepeatedField::RemoveLast() { + GOOGLE_DCHECK_GT(current_size_, 0); + --current_size_; +} + +template +inline void RepeatedField::Clear() { + current_size_ = 0; +} + +template +void RepeatedField::MergeFrom(const RepeatedField& other) { + Reserve(current_size_ + other.current_size_); + memcpy(elements_ + current_size_, other.elements_, + sizeof(Element) * other.current_size_); + current_size_ += other.current_size_; +} + +template +inline Element* RepeatedField::mutable_data() { + return elements_; +} + +template +inline const Element* RepeatedField::data() const { + return elements_; +} + + +template +void RepeatedField::Swap(RepeatedField* other) { + 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]; + memcpy(swap_initial_space, initial_space_, sizeof(initial_space_)); + + elements_ = other->elements_; + current_size_ = other->current_size_; + total_size_ = other->total_size_; + memcpy(initial_space_, other->initial_space_, sizeof(initial_space_)); + + other->elements_ = swap_elements; + other->current_size_ = swap_current_size; + other->total_size_ = swap_total_size; + memcpy(other->initial_space_, swap_initial_space, sizeof(swap_initial_space)); + + if (elements_ == other->initial_space_) { + elements_ = initial_space_; + } + if (other->elements_ == initial_space_) { + other->elements_ = other->initial_space_; + } +} + +template +inline typename RepeatedField::iterator +RepeatedField::begin() { + return elements_; +} +template +inline typename RepeatedField::const_iterator +RepeatedField::begin() const { + return elements_; +} +template +inline typename RepeatedField::iterator +RepeatedField::end() { + return elements_ + current_size_; +} +template +inline typename RepeatedField::const_iterator +RepeatedField::end() const { + return elements_ + current_size_; +} + + +template +const void* RepeatedField::GenericGet(int index) const { + GOOGLE_DCHECK_LT(index, size()); + return elements_ + index; +} + +template +void* RepeatedField::GenericMutable(int index) { + return Mutable(index); +} + +template +void* RepeatedField::GenericAdd() { + Add(Element()); + return Mutable(current_size_ - 1); +} + +template +void RepeatedField::GenericClear() { + Clear(); +} + +template +int RepeatedField::GenericSize() const { + return size(); +} + +template +inline void RepeatedField::Reserve(int new_size) { + if (total_size_ >= new_size) return; + + Element* old_elements = elements_; + total_size_ = max(total_size_ * 2, new_size); + elements_ = new Element[total_size_]; + memcpy(elements_, old_elements, current_size_ * sizeof(elements_[0])); + if (old_elements != initial_space_) { + delete [] old_elements; + } +} + +// ------------------------------------------------------------------- + +template +inline RepeatedPtrField::RepeatedPtrField() + : prototype_(NULL), + elements_(initial_space_), + current_size_(0), + allocated_size_(0), + total_size_(kInitialSize) { +} + +template <> +inline RepeatedPtrField::RepeatedPtrField(const Message* prototype) + : prototype_(prototype), + elements_(initial_space_), + current_size_(0), + allocated_size_(0), + total_size_(kInitialSize) { +} + +template +RepeatedPtrField::~RepeatedPtrField() { + for (int i = 0; i < allocated_size_; i++) { + delete elements_[i]; + } + if (elements_ != initial_space_) { + delete [] elements_; + } +} + +template <> +inline const Message* RepeatedPtrField::prototype() const { + return prototype_; +} + + +template +inline int RepeatedPtrField::size() const { + return current_size_; +} + + +template +inline const Element& RepeatedPtrField::Get(int index) const { + GOOGLE_DCHECK_LT(index, size()); + return *elements_[index]; +} + +template +inline Element* RepeatedPtrField::Mutable(int index) { + GOOGLE_DCHECK_LT(index, size()); + return elements_[index]; +} + +template +inline Element* RepeatedPtrField::Add() { + if (current_size_ < allocated_size_) return elements_[current_size_++]; + if (allocated_size_ == total_size_) Reserve(total_size_ + 1); + ++allocated_size_; + return elements_[current_size_++] = NewElement(); +} + +template +inline void RepeatedPtrField::RemoveLast() { + GOOGLE_DCHECK_GT(current_size_, 0); + elements_[--current_size_]->Clear(); +} + +template <> +inline void RepeatedPtrField::RemoveLast() { + GOOGLE_DCHECK_GT(current_size_, 0); + elements_[--current_size_]->clear(); +} + +template +void RepeatedPtrField::Clear() { + for (int i = 0; i < current_size_; i++) { + elements_[i]->Clear(); + } + current_size_ = 0; +} + +// Specialization defined in repeated_field.cc. +template <> +void LIBPROTOBUF_EXPORT RepeatedPtrField::Clear(); + +template +void RepeatedPtrField::MergeFrom(const RepeatedPtrField& other) { + Reserve(current_size_ + other.current_size_); + for (int i = 0; i < other.current_size_; i++) { + Add()->MergeFrom(other.Get(i)); + } +} + +template <> +inline void RepeatedPtrField::MergeFrom(const RepeatedPtrField& other) { + Reserve(current_size_ + other.current_size_); + for (int i = 0; i < other.current_size_; i++) { + Add()->assign(other.Get(i)); + } +} + + +template +inline Element** RepeatedPtrField::mutable_data() { + return elements_; +} + +template +inline const Element* const* RepeatedPtrField::data() const { + return elements_; +} + + +template +void RepeatedPtrField::Swap(RepeatedPtrField* other) { + Element** swap_elements = elements_; + int swap_current_size = current_size_; + int swap_allocated_size = allocated_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]; + memcpy(swap_initial_space, initial_space_, sizeof(initial_space_)); + + elements_ = other->elements_; + current_size_ = other->current_size_; + allocated_size_ = other->allocated_size_; + total_size_ = other->total_size_; + memcpy(initial_space_, other->initial_space_, sizeof(initial_space_)); + + other->elements_ = swap_elements; + other->current_size_ = swap_current_size; + other->allocated_size_ = swap_allocated_size; + other->total_size_ = swap_total_size; + memcpy(other->initial_space_, swap_initial_space, sizeof(swap_initial_space)); + + if (elements_ == other->initial_space_) { + elements_ = initial_space_; + } + if (other->elements_ == initial_space_) { + other->elements_ = other->initial_space_; + } +} + + +template +inline void RepeatedPtrField::AddAllocated(Element* value) { + if (allocated_size_ == total_size_) Reserve(total_size_ + 1); + // We don't care about the order of cleared elements, so if there's one + // in the way, just move it to the back of the array. + if (current_size_ < allocated_size_) { + elements_[allocated_size_] = elements_[current_size_]; + } + ++allocated_size_; + elements_[current_size_++] = value; +} + +template +inline Element* RepeatedPtrField::ReleaseLast() { + GOOGLE_DCHECK_GT(current_size_, 0); + Element* result = elements_[--current_size_]; + --allocated_size_; + if (current_size_ < allocated_size_) { + // There are cleared elements on the end; replace the removed element + // with the last allocated element. + elements_[current_size_] = elements_[allocated_size_]; + } + return result; +} + + +template +inline int RepeatedPtrField::ClearedCount() { + return allocated_size_ - current_size_; +} + +template +inline void RepeatedPtrField::AddCleared(Element* value) { + if (allocated_size_ == total_size_) Reserve(total_size_ + 1); + elements_[allocated_size_++] = value; +} + +template +inline Element* RepeatedPtrField::ReleaseCleared() { + GOOGLE_DCHECK_GT(allocated_size_, current_size_); + return elements_[--allocated_size_]; +} + + +template +const void* RepeatedPtrField::GenericGet(int index) const { + return &Get(index); +} + +template +void* RepeatedPtrField::GenericMutable(int index) { + return Mutable(index); +} + +template +void* RepeatedPtrField::GenericAdd() { + return Add(); +} + +template +void RepeatedPtrField::GenericClear() { + Clear(); +} + +template +int RepeatedPtrField::GenericSize() const { + return size(); +} + + +template +inline void RepeatedPtrField::Reserve(int new_size) { + if (total_size_ >= new_size) return; + + Element** old_elements = elements_; + total_size_ = max(total_size_ * 2, new_size); + elements_ = new Element*[total_size_]; + memcpy(elements_, old_elements, allocated_size_ * sizeof(elements_[0])); + if (old_elements != initial_space_) { + delete [] old_elements; + } +} + +template +inline Element* RepeatedPtrField::NewElement() { + return new Element; +} + +// RepeatedPtrField is alowed but requires a prototype since Message +// is abstract. +template <> +inline Message* RepeatedPtrField::NewElement() { + return prototype_->New(); +} + +// ------------------------------------------------------------------- + +namespace internal { + +// STL-like iterator implementation for RepeatedPtrField. You should not +// 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, +// but adds random-access operators and is slightly more specialized +// for using T** as its base type. I didn't re-use the other class to +// avoid an extra dependency. +// +// This code stolen from net/proto/proto-array-internal.h by Jeffrey Yasskin +// (jyasskin@google.com). +template +class RepeatedPtrIterator + : public std::iterator< + std::random_access_iterator_tag, + typename internal::remove_pointer< + typename internal::remove_pointer::type>::type> { + public: + typedef RepeatedPtrIterator iterator; + typedef typename iterator::reference reference; + typedef typename iterator::pointer pointer; + typedef typename iterator::difference_type difference_type; + + RepeatedPtrIterator() : it_(NULL) {} + explicit RepeatedPtrIterator(const It& it) : it_(it) {} + + // Allow "upcasting" from RepeatedPtrIterator to + // RepeatedPtrIterator. + template + RepeatedPtrIterator(const RepeatedPtrIterator& other) + : it_(other.base()) {} + + // Provide access to the wrapped iterator. + const It& base() const { return it_; } + + // dereferenceable + reference operator*() const { return **it_; } + pointer operator->() const { return &(operator*()); } + + // {inc,dec}rementable + iterator& operator++() { ++it_; return *this; } + iterator operator++(int) { return iterator(it_++); } + iterator& operator--() { --it_; return *this; } + iterator operator--(int) { return iterator(it_--); } + + // equality_comparable + bool operator==(const iterator& x) const { return it_ == x.it_; } + bool operator!=(const iterator& x) const { return it_ != x.it_; } + + // less_than_comparable + bool operator<(const iterator& x) const { return it_ < x.it_; } + bool operator<=(const iterator& x) const { return it_ <= x.it_; } + bool operator>(const iterator& x) const { return it_ > x.it_; } + bool operator>=(const iterator& x) const { return it_ >= x.it_; } + + // addable, subtractable + iterator& operator+=(difference_type d) { + it_ += d; + return *this; + } + friend iterator operator+(iterator it, difference_type d) { + it += d; + return it; + } + friend iterator operator+(difference_type d, iterator it) { + it += d; + return it; + } + iterator& operator-=(difference_type d) { + it_ -= d; + return *this; + } + friend iterator operator-(iterator it, difference_type d) { + it -= d; + return it; + } + + // indexable + reference operator[](difference_type d) const { return *(*this + d); } + + // random access iterator + difference_type operator-(const iterator& x) const { return it_ - x.it_; } + + private: + // The internal iterator. + It it_; +}; + +} // namespace internal + +template +inline typename RepeatedPtrField::iterator +RepeatedPtrField::begin() { + return iterator(elements_); +} +template +inline typename RepeatedPtrField::const_iterator +RepeatedPtrField::begin() const { + return iterator(elements_); +} +template +inline typename RepeatedPtrField::iterator +RepeatedPtrField::end() { + return iterator(elements_ + current_size_); +} +template +inline typename RepeatedPtrField::const_iterator +RepeatedPtrField::end() const { + return iterator(elements_ + current_size_); +} + +} // namespace protobuf + +} // namespace google +#endif // GOOGLE_PROTOBUF_REPEATED_FIELD_H__ -- cgit v1.2.3