Squashed 'third_party/protobuf/' content from commit e35e248
Change-Id: I6cbe123d09fe50fdcad0e51466665daeee7433c7
git-subtree-dir: third_party/protobuf
git-subtree-split: e35e24800fb8d694bdeea5fd63dc7d1b14d68723
diff --git a/src/google/protobuf/stubs/map_util.h b/src/google/protobuf/stubs/map_util.h
new file mode 100644
index 0000000..4cccbbe
--- /dev/null
+++ b/src/google/protobuf/stubs/map_util.h
@@ -0,0 +1,769 @@
+// Protocol Buffers - Google's data interchange format
+// Copyright 2014 Google Inc. All rights reserved.
+// 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
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// from google3/util/gtl/map_util.h
+// Author: Anton Carver
+
+#ifndef GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__
+#define GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__
+
+#include <stddef.h>
+#include <iterator>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <google/protobuf/stubs/common.h>
+
+namespace google {
+namespace protobuf {
+namespace internal {
+// Local implementation of RemoveConst to avoid including base/type_traits.h.
+template <class T> struct RemoveConst { typedef T type; };
+template <class T> struct RemoveConst<const T> : RemoveConst<T> {};
+} // namespace internal
+
+//
+// Find*()
+//
+
+// Returns a const reference to the value associated with the given key if it
+// exists. Crashes otherwise.
+//
+// This is intended as a replacement for operator[] as an rvalue (for reading)
+// when the key is guaranteed to exist.
+//
+// operator[] for lookup is discouraged for several reasons:
+// * It has a side-effect of inserting missing keys
+// * It is not thread-safe (even when it is not inserting, it can still
+// choose to resize the underlying storage)
+// * It invalidates iterators (when it chooses to resize)
+// * It default constructs a value object even if it doesn't need to
+//
+// This version assumes the key is printable, and includes it in the fatal log
+// message.
+template <class Collection>
+const typename Collection::value_type::second_type&
+FindOrDie(const Collection& collection,
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::const_iterator it = collection.find(key);
+ GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key;
+ return it->second;
+}
+
+// Same as above, but returns a non-const reference.
+template <class Collection>
+typename Collection::value_type::second_type&
+FindOrDie(Collection& collection, // NOLINT
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::iterator it = collection.find(key);
+ GOOGLE_CHECK(it != collection.end()) << "Map key not found: " << key;
+ return it->second;
+}
+
+// Same as FindOrDie above, but doesn't log the key on failure.
+template <class Collection>
+const typename Collection::value_type::second_type&
+FindOrDieNoPrint(const Collection& collection,
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::const_iterator it = collection.find(key);
+ GOOGLE_CHECK(it != collection.end()) << "Map key not found";
+ return it->second;
+}
+
+// Same as above, but returns a non-const reference.
+template <class Collection>
+typename Collection::value_type::second_type&
+FindOrDieNoPrint(Collection& collection, // NOLINT
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::iterator it = collection.find(key);
+ GOOGLE_CHECK(it != collection.end()) << "Map key not found";
+ return it->second;
+}
+
+// Returns a const reference to the value associated with the given key if it
+// exists, otherwise returns a const reference to the provided default value.
+//
+// WARNING: If a temporary object is passed as the default "value,"
+// this function will return a reference to that temporary object,
+// which will be destroyed at the end of the statement. A common
+// example: if you have a map with string values, and you pass a char*
+// as the default "value," either use the returned value immediately
+// or store it in a string (not string&).
+// Details: http://go/findwithdefault
+template <class Collection>
+const typename Collection::value_type::second_type&
+FindWithDefault(const Collection& collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& value) {
+ typename Collection::const_iterator it = collection.find(key);
+ if (it == collection.end()) {
+ return value;
+ }
+ return it->second;
+}
+
+// Returns a pointer to the const value associated with the given key if it
+// exists, or NULL otherwise.
+template <class Collection>
+const typename Collection::value_type::second_type*
+FindOrNull(const Collection& collection,
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::const_iterator it = collection.find(key);
+ if (it == collection.end()) {
+ return 0;
+ }
+ return &it->second;
+}
+
+// Same as above but returns a pointer to the non-const value.
+template <class Collection>
+typename Collection::value_type::second_type*
+FindOrNull(Collection& collection, // NOLINT
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::iterator it = collection.find(key);
+ if (it == collection.end()) {
+ return 0;
+ }
+ return &it->second;
+}
+
+// Returns the pointer value associated with the given key. If none is found,
+// NULL is returned. The function is designed to be used with a map of keys to
+// pointers.
+//
+// This function does not distinguish between a missing key and a key mapped
+// to a NULL value.
+template <class Collection>
+typename Collection::value_type::second_type
+FindPtrOrNull(const Collection& collection,
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::const_iterator it = collection.find(key);
+ if (it == collection.end()) {
+ return typename Collection::value_type::second_type();
+ }
+ return it->second;
+}
+
+// Same as above, except takes non-const reference to collection.
+//
+// This function is needed for containers that propagate constness to the
+// pointee, such as boost::ptr_map.
+template <class Collection>
+typename Collection::value_type::second_type
+FindPtrOrNull(Collection& collection, // NOLINT
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::iterator it = collection.find(key);
+ if (it == collection.end()) {
+ return typename Collection::value_type::second_type();
+ }
+ return it->second;
+}
+
+// Finds the pointer value associated with the given key in a map whose values
+// are linked_ptrs. Returns NULL if key is not found.
+template <class Collection>
+typename Collection::value_type::second_type::element_type*
+FindLinkedPtrOrNull(const Collection& collection,
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::const_iterator it = collection.find(key);
+ if (it == collection.end()) {
+ return 0;
+ }
+ // Since linked_ptr::get() is a const member returning a non const,
+ // we do not need a version of this function taking a non const collection.
+ return it->second.get();
+}
+
+// Same as above, but dies if the key is not found.
+template <class Collection>
+typename Collection::value_type::second_type::element_type&
+FindLinkedPtrOrDie(const Collection& collection,
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::const_iterator it = collection.find(key);
+ CHECK(it != collection.end()) << "key not found: " << key;
+ // Since linked_ptr::operator*() is a const member returning a non const,
+ // we do not need a version of this function taking a non const collection.
+ return *it->second;
+}
+
+// Finds the value associated with the given key and copies it to *value (if not
+// NULL). Returns false if the key was not found, true otherwise.
+template <class Collection, class Key, class Value>
+bool FindCopy(const Collection& collection,
+ const Key& key,
+ Value* const value) {
+ typename Collection::const_iterator it = collection.find(key);
+ if (it == collection.end()) {
+ return false;
+ }
+ if (value) {
+ *value = it->second;
+ }
+ return true;
+}
+
+//
+// Contains*()
+//
+
+// Returns true if and only if the given collection contains the given key.
+template <class Collection, class Key>
+bool ContainsKey(const Collection& collection, const Key& key) {
+ return collection.find(key) != collection.end();
+}
+
+// Returns true if and only if the given collection contains the given key-value
+// pair.
+template <class Collection, class Key, class Value>
+bool ContainsKeyValuePair(const Collection& collection,
+ const Key& key,
+ const Value& value) {
+ typedef typename Collection::const_iterator const_iterator;
+ std::pair<const_iterator, const_iterator> range = collection.equal_range(key);
+ for (const_iterator it = range.first; it != range.second; ++it) {
+ if (it->second == value) {
+ return true;
+ }
+ }
+ return false;
+}
+
+//
+// Insert*()
+//
+
+// Inserts the given key-value pair into the collection. Returns true if and
+// only if the key from the given pair didn't previously exist. Otherwise, the
+// value in the map is replaced with the value from the given pair.
+template <class Collection>
+bool InsertOrUpdate(Collection* const collection,
+ const typename Collection::value_type& vt) {
+ std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
+ if (!ret.second) {
+ // update
+ ret.first->second = vt.second;
+ return false;
+ }
+ return true;
+}
+
+// Same as above, except that the key and value are passed separately.
+template <class Collection>
+bool InsertOrUpdate(Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& value) {
+ return InsertOrUpdate(
+ collection, typename Collection::value_type(key, value));
+}
+
+// Inserts/updates all the key-value pairs from the range defined by the
+// iterators "first" and "last" into the given collection.
+template <class Collection, class InputIterator>
+void InsertOrUpdateMany(Collection* const collection,
+ InputIterator first, InputIterator last) {
+ for (; first != last; ++first) {
+ InsertOrUpdate(collection, *first);
+ }
+}
+
+// Change the value associated with a particular key in a map or hash_map
+// of the form map<Key, Value*> which owns the objects pointed to by the
+// value pointers. If there was an existing value for the key, it is deleted.
+// True indicates an insert took place, false indicates an update + delete.
+template <class Collection>
+bool InsertAndDeleteExisting(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& value) {
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(key, value));
+ if (!ret.second) {
+ delete ret.first->second;
+ ret.first->second = value;
+ return false;
+ }
+ return true;
+}
+
+// Inserts the given key and value into the given collection if and only if the
+// given key did NOT already exist in the collection. If the key previously
+// existed in the collection, the value is not changed. Returns true if the
+// key-value pair was inserted; returns false if the key was already present.
+template <class Collection>
+bool InsertIfNotPresent(Collection* const collection,
+ const typename Collection::value_type& vt) {
+ return collection->insert(vt).second;
+}
+
+// Same as above except the key and value are passed separately.
+template <class Collection>
+bool InsertIfNotPresent(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& value) {
+ return InsertIfNotPresent(
+ collection, typename Collection::value_type(key, value));
+}
+
+// Same as above except dies if the key already exists in the collection.
+template <class Collection>
+void InsertOrDie(Collection* const collection,
+ const typename Collection::value_type& value) {
+ CHECK(InsertIfNotPresent(collection, value)) << "duplicate value: " << value;
+}
+
+// Same as above except doesn't log the value on error.
+template <class Collection>
+void InsertOrDieNoPrint(Collection* const collection,
+ const typename Collection::value_type& value) {
+ CHECK(InsertIfNotPresent(collection, value)) << "duplicate value.";
+}
+
+// Inserts the key-value pair into the collection. Dies if key was already
+// present.
+template <class Collection>
+void InsertOrDie(Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& data) {
+ GOOGLE_CHECK(InsertIfNotPresent(collection, key, data))
+ << "duplicate key: " << key;
+}
+
+// Same as above except doesn't log the key on error.
+template <class Collection>
+void InsertOrDieNoPrint(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& data) {
+ GOOGLE_CHECK(InsertIfNotPresent(collection, key, data)) << "duplicate key.";
+}
+
+// Inserts a new key and default-initialized value. Dies if the key was already
+// present. Returns a reference to the value. Example usage:
+//
+// map<int, SomeProto> m;
+// SomeProto& proto = InsertKeyOrDie(&m, 3);
+// proto.set_field("foo");
+template <class Collection>
+typename Collection::value_type::second_type& InsertKeyOrDie(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key) {
+ typedef typename Collection::value_type value_type;
+ std::pair<typename Collection::iterator, bool> res =
+ collection->insert(value_type(key, typename value_type::second_type()));
+ GOOGLE_CHECK(res.second) << "duplicate key: " << key;
+ return res.first->second;
+}
+
+//
+// Lookup*()
+//
+
+// Looks up a given key and value pair in a collection and inserts the key-value
+// pair if it's not already present. Returns a reference to the value associated
+// with the key.
+template <class Collection>
+typename Collection::value_type::second_type&
+LookupOrInsert(Collection* const collection,
+ const typename Collection::value_type& vt) {
+ return collection->insert(vt).first->second;
+}
+
+// Same as above except the key-value are passed separately.
+template <class Collection>
+typename Collection::value_type::second_type&
+LookupOrInsert(Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& value) {
+ return LookupOrInsert(
+ collection, typename Collection::value_type(key, value));
+}
+
+// Counts the number of equivalent elements in the given "sequence", and stores
+// the results in "count_map" with element as the key and count as the value.
+//
+// Example:
+// vector<string> v = {"a", "b", "c", "a", "b"};
+// map<string, int> m;
+// AddTokenCounts(v, 1, &m);
+// assert(m["a"] == 2);
+// assert(m["b"] == 2);
+// assert(m["c"] == 1);
+template <typename Sequence, typename Collection>
+void AddTokenCounts(
+ const Sequence& sequence,
+ const typename Collection::value_type::second_type& increment,
+ Collection* const count_map) {
+ for (typename Sequence::const_iterator it = sequence.begin();
+ it != sequence.end(); ++it) {
+ typename Collection::value_type::second_type& value =
+ LookupOrInsert(count_map, *it,
+ typename Collection::value_type::second_type());
+ value += increment;
+ }
+}
+
+// Returns a reference to the value associated with key. If not found, a value
+// is default constructed on the heap and added to the map.
+//
+// This function is useful for containers of the form map<Key, Value*>, where
+// inserting a new key, value pair involves constructing a new heap-allocated
+// Value, and storing a pointer to that in the collection.
+template <class Collection>
+typename Collection::value_type::second_type&
+LookupOrInsertNew(Collection* const collection,
+ const typename Collection::value_type::first_type& key) {
+ typedef typename std::iterator_traits<
+ typename Collection::value_type::second_type>::value_type Element;
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(
+ key,
+ static_cast<typename Collection::value_type::second_type>(NULL)));
+ if (ret.second) {
+ ret.first->second = new Element();
+ }
+ return ret.first->second;
+}
+
+// Same as above but constructs the value using the single-argument constructor
+// and the given "arg".
+template <class Collection, class Arg>
+typename Collection::value_type::second_type&
+LookupOrInsertNew(Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const Arg& arg) {
+ typedef typename std::iterator_traits<
+ typename Collection::value_type::second_type>::value_type Element;
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(
+ key,
+ static_cast<typename Collection::value_type::second_type>(NULL)));
+ if (ret.second) {
+ ret.first->second = new Element(arg);
+ }
+ return ret.first->second;
+}
+
+// Lookup of linked/shared pointers is used in two scenarios:
+//
+// Use LookupOrInsertNewLinkedPtr if the container owns the elements.
+// In this case it is fine working with the raw pointer as long as it is
+// guaranteed that no other thread can delete/update an accessed element.
+// A mutex will need to lock the container operation as well as the use
+// of the returned elements. Finding an element may be performed using
+// FindLinkedPtr*().
+//
+// Use LookupOrInsertNewSharedPtr if the container does not own the elements
+// for their whole lifetime. This is typically the case when a reader allows
+// parallel updates to the container. In this case a Mutex only needs to lock
+// container operations, but all element operations must be performed on the
+// shared pointer. Finding an element must be performed using FindPtr*() and
+// cannot be done with FindLinkedPtr*() even though it compiles.
+
+// Lookup a key in a map or hash_map whose values are linked_ptrs. If it is
+// missing, set collection[key].reset(new Value::element_type) and return that.
+// Value::element_type must be default constructable.
+template <class Collection>
+typename Collection::value_type::second_type::element_type*
+LookupOrInsertNewLinkedPtr(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key) {
+ typedef typename Collection::value_type::second_type Value;
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(key, Value()));
+ if (ret.second) {
+ ret.first->second.reset(new typename Value::element_type);
+ }
+ return ret.first->second.get();
+}
+
+// A variant of LookupOrInsertNewLinkedPtr where the value is constructed using
+// a single-parameter constructor. Note: the constructor argument is computed
+// even if it will not be used, so only values cheap to compute should be passed
+// here. On the other hand it does not matter how expensive the construction of
+// the actual stored value is, as that only occurs if necessary.
+template <class Collection, class Arg>
+typename Collection::value_type::second_type::element_type*
+LookupOrInsertNewLinkedPtr(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const Arg& arg) {
+ typedef typename Collection::value_type::second_type Value;
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(key, Value()));
+ if (ret.second) {
+ ret.first->second.reset(new typename Value::element_type(arg));
+ }
+ return ret.first->second.get();
+}
+
+// Lookup a key in a map or hash_map whose values are shared_ptrs. If it is
+// missing, set collection[key].reset(new Value::element_type). Unlike
+// LookupOrInsertNewLinkedPtr, this function returns the shared_ptr instead of
+// the raw pointer. Value::element_type must be default constructable.
+template <class Collection>
+typename Collection::value_type::second_type&
+LookupOrInsertNewSharedPtr(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key) {
+ typedef typename Collection::value_type::second_type SharedPtr;
+ typedef typename Collection::value_type::second_type::element_type Element;
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(key, SharedPtr()));
+ if (ret.second) {
+ ret.first->second.reset(new Element());
+ }
+ return ret.first->second;
+}
+
+// A variant of LookupOrInsertNewSharedPtr where the value is constructed using
+// a single-parameter constructor. Note: the constructor argument is computed
+// even if it will not be used, so only values cheap to compute should be passed
+// here. On the other hand it does not matter how expensive the construction of
+// the actual stored value is, as that only occurs if necessary.
+template <class Collection, class Arg>
+typename Collection::value_type::second_type&
+LookupOrInsertNewSharedPtr(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const Arg& arg) {
+ typedef typename Collection::value_type::second_type SharedPtr;
+ typedef typename Collection::value_type::second_type::element_type Element;
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(key, SharedPtr()));
+ if (ret.second) {
+ ret.first->second.reset(new Element(arg));
+ }
+ return ret.first->second;
+}
+
+//
+// Misc Utility Functions
+//
+
+// Updates the value associated with the given key. If the key was not already
+// present, then the key-value pair are inserted and "previous" is unchanged. If
+// the key was already present, the value is updated and "*previous" will
+// contain a copy of the old value.
+//
+// InsertOrReturnExisting has complementary behavior that returns the
+// address of an already existing value, rather than updating it.
+template <class Collection>
+bool UpdateReturnCopy(Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& value,
+ typename Collection::value_type::second_type* previous) {
+ std::pair<typename Collection::iterator, bool> ret =
+ collection->insert(typename Collection::value_type(key, value));
+ if (!ret.second) {
+ // update
+ if (previous) {
+ *previous = ret.first->second;
+ }
+ ret.first->second = value;
+ return true;
+ }
+ return false;
+}
+
+// Same as above except that the key and value are passed as a pair.
+template <class Collection>
+bool UpdateReturnCopy(Collection* const collection,
+ const typename Collection::value_type& vt,
+ typename Collection::value_type::second_type* previous) {
+ std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
+ if (!ret.second) {
+ // update
+ if (previous) {
+ *previous = ret.first->second;
+ }
+ ret.first->second = vt.second;
+ return true;
+ }
+ return false;
+}
+
+// Tries to insert the given key-value pair into the collection. Returns NULL if
+// the insert succeeds. Otherwise, returns a pointer to the existing value.
+//
+// This complements UpdateReturnCopy in that it allows to update only after
+// verifying the old value and still insert quickly without having to look up
+// twice. Unlike UpdateReturnCopy this also does not come with the issue of an
+// undefined previous* in case new data was inserted.
+template <class Collection>
+typename Collection::value_type::second_type* const
+InsertOrReturnExisting(Collection* const collection,
+ const typename Collection::value_type& vt) {
+ std::pair<typename Collection::iterator, bool> ret = collection->insert(vt);
+ if (ret.second) {
+ return NULL; // Inserted, no existing previous value.
+ } else {
+ return &ret.first->second; // Return address of already existing value.
+ }
+}
+
+// Same as above, except for explicit key and data.
+template <class Collection>
+typename Collection::value_type::second_type* const
+InsertOrReturnExisting(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key,
+ const typename Collection::value_type::second_type& data) {
+ return InsertOrReturnExisting(collection,
+ typename Collection::value_type(key, data));
+}
+
+// Erases the collection item identified by the given key, and returns the value
+// associated with that key. It is assumed that the value (i.e., the
+// mapped_type) is a pointer. Returns NULL if the key was not found in the
+// collection.
+//
+// Examples:
+// map<string, MyType*> my_map;
+//
+// One line cleanup:
+// delete EraseKeyReturnValuePtr(&my_map, "abc");
+//
+// Use returned value:
+// scoped_ptr<MyType> value_ptr(EraseKeyReturnValuePtr(&my_map, "abc"));
+// if (value_ptr.get())
+// value_ptr->DoSomething();
+//
+template <class Collection>
+typename Collection::value_type::second_type EraseKeyReturnValuePtr(
+ Collection* const collection,
+ const typename Collection::value_type::first_type& key) {
+ typename Collection::iterator it = collection->find(key);
+ if (it == collection->end()) {
+ return NULL;
+ }
+ typename Collection::value_type::second_type v = it->second;
+ collection->erase(it);
+ return v;
+}
+
+// Inserts all the keys from map_container into key_container, which must
+// support insert(MapContainer::key_type).
+//
+// Note: any initial contents of the key_container are not cleared.
+template <class MapContainer, class KeyContainer>
+void InsertKeysFromMap(const MapContainer& map_container,
+ KeyContainer* key_container) {
+ GOOGLE_CHECK(key_container != NULL);
+ for (typename MapContainer::const_iterator it = map_container.begin();
+ it != map_container.end(); ++it) {
+ key_container->insert(it->first);
+ }
+}
+
+// Appends all the keys from map_container into key_container, which must
+// support push_back(MapContainer::key_type).
+//
+// Note: any initial contents of the key_container are not cleared.
+template <class MapContainer, class KeyContainer>
+void AppendKeysFromMap(const MapContainer& map_container,
+ KeyContainer* key_container) {
+ GOOGLE_CHECK(key_container != NULL);
+ for (typename MapContainer::const_iterator it = map_container.begin();
+ it != map_container.end(); ++it) {
+ key_container->push_back(it->first);
+ }
+}
+
+// A more specialized overload of AppendKeysFromMap to optimize reallocations
+// for the common case in which we're appending keys to a vector and hence can
+// (and sometimes should) call reserve() first.
+//
+// (It would be possible to play SFINAE games to call reserve() for any
+// container that supports it, but this seems to get us 99% of what we need
+// without the complexity of a SFINAE-based solution.)
+template <class MapContainer, class KeyType>
+void AppendKeysFromMap(const MapContainer& map_container,
+ vector<KeyType>* key_container) {
+ GOOGLE_CHECK(key_container != NULL);
+ // We now have the opportunity to call reserve(). Calling reserve() every
+ // time is a bad idea for some use cases: libstdc++'s implementation of
+ // vector<>::reserve() resizes the vector's backing store to exactly the
+ // given size (unless it's already at least that big). Because of this,
+ // the use case that involves appending a lot of small maps (total size
+ // N) one by one to a vector would be O(N^2). But never calling reserve()
+ // loses the opportunity to improve the use case of adding from a large
+ // map to an empty vector (this improves performance by up to 33%). A
+ // number of heuristics are possible; see the discussion in
+ // cl/34081696. Here we use the simplest one.
+ if (key_container->empty()) {
+ key_container->reserve(map_container.size());
+ }
+ for (typename MapContainer::const_iterator it = map_container.begin();
+ it != map_container.end(); ++it) {
+ key_container->push_back(it->first);
+ }
+}
+
+// Inserts all the values from map_container into value_container, which must
+// support push_back(MapContainer::mapped_type).
+//
+// Note: any initial contents of the value_container are not cleared.
+template <class MapContainer, class ValueContainer>
+void AppendValuesFromMap(const MapContainer& map_container,
+ ValueContainer* value_container) {
+ GOOGLE_CHECK(value_container != NULL);
+ for (typename MapContainer::const_iterator it = map_container.begin();
+ it != map_container.end(); ++it) {
+ value_container->push_back(it->second);
+ }
+}
+
+// A more specialized overload of AppendValuesFromMap to optimize reallocations
+// for the common case in which we're appending values to a vector and hence
+// can (and sometimes should) call reserve() first.
+//
+// (It would be possible to play SFINAE games to call reserve() for any
+// container that supports it, but this seems to get us 99% of what we need
+// without the complexity of a SFINAE-based solution.)
+template <class MapContainer, class ValueType>
+void AppendValuesFromMap(const MapContainer& map_container,
+ vector<ValueType>* value_container) {
+ GOOGLE_CHECK(value_container != NULL);
+ // See AppendKeysFromMap for why this is done.
+ if (value_container->empty()) {
+ value_container->reserve(map_container.size());
+ }
+ for (typename MapContainer::const_iterator it = map_container.begin();
+ it != map_container.end(); ++it) {
+ value_container->push_back(it->second);
+ }
+}
+
+} // namespace protobuf
+} // namespace google
+
+#endif // GOOGLE_PROTOBUF_STUBS_MAP_UTIL_H__