third_party/protobuf: Update to HEAD (83d681ee2c)

third_party/protobuf/src/google/protobuf/map.h

 // Protocol Buffers - Google's data interchange format
 // Copyright 2008 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.
@@ skipping 10 matching lines @@
 // 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.
 
+// This file defines the map container and its helpers to support protobuf maps.
+//
+// The Map and MapIterator types are provided by this header file.
+// Please avoid using other types defined here, unless they are public
+// types within Map or MapIterator, such as Map::value_type.
+
 #ifndef GOOGLE_PROTOBUF_MAP_H__
 #define GOOGLE_PROTOBUF_MAP_H__
 
 #include <google/protobuf/stubs/hash.h>
 #include <iterator>
 #include <limits>  // To support Visual Studio 2008
 #include <set>
 #include <utility>
 
 #include <google/protobuf/stubs/common.h>
 #include <google/protobuf/arena.h>
 #include <google/protobuf/generated_enum_util.h>
 #include <google/protobuf/map_type_handler.h>
 #include <google/protobuf/message.h>
 #include <google/protobuf/descriptor.h>
 #if __cpp_exceptions && LANG_CXX11
 #include <random>
 #endif
 
 namespace google {
 namespace protobuf {
 
-// The Map and MapIterator types are provided by this header file.
-// Please avoid using other types defined here, unless they are public
-// types within Map or MapIterator, such as Map::value_type.
 template <typename Key, typename T>
 class Map;
 
 class MapIterator;
 
 template <typename Enum> struct is_proto_enum;
 
 namespace internal {
 template <typename Key, typename T,
           WireFormatLite::FieldType key_wire_type,
@@ skipping 447 matching lines @@
   typedef MapPair<Key, T> value_type;
 
   typedef value_type* pointer;
   typedef const value_type* const_pointer;
   typedef value_type& reference;
   typedef const value_type& const_reference;
 
   typedef size_t size_type;
   typedef hash<Key> hasher;
 
-  Map(bool old_style = true)
+  explicit Map(bool old_style = false)
       : arena_(NULL),
         default_enum_value_(0),
         old_style_(old_style) {
     Init();
   }
-  explicit Map(Arena* arena, bool old_style = true)
+  explicit Map(Arena* arena, bool old_style = false)
       : arena_(arena),
         default_enum_value_(0),
         old_style_(old_style) {
     Init();
   }
   Map(const Map& other)
       : arena_(NULL),
         default_enum_value_(other.default_enum_value_),
         old_style_(other.old_style_) {
     Init();
     insert(other.begin(), other.end());
   }
   template <class InputIt>
-  Map(const InputIt& first, const InputIt& last, bool old_style = true)
+  Map(const InputIt& first, const InputIt& last, bool old_style = false)
       : arena_(NULL),
         default_enum_value_(0),
         old_style_(old_style) {
     Init();
     insert(first, last);
   }
 
   ~Map() {
     clear();
     if (arena_ == NULL) {
       if (old_style_)
         delete deprecated_elements_;
       else
         delete elements_;
     }
   }
 
  private:
   void Init() {
     if (old_style_)
       deprecated_elements_ = Arena::Create<DeprecatedInnerMap>(
-          arena_, 0, hasher(), equal_to<Key>(),
+          arena_, 0, hasher(), std::equal_to<Key>(),
           MapAllocator<std::pair<const Key, MapPair<Key, T>*> >(arena_));
     else
       elements_ =
           Arena::Create<InnerMap>(arena_, 0, hasher(), Allocator(arena_));
   }
 
   // re-implement std::allocator to use arena allocator for memory allocation.
   // Used for google::protobuf::Map implementation. Users should not use this class
   // directly.
   template <typename U>
   class MapAllocator {
    public:
     typedef U value_type;
     typedef value_type* pointer;
     typedef const value_type* const_pointer;
     typedef value_type& reference;
     typedef const value_type& const_reference;
     typedef size_t size_type;
     typedef ptrdiff_t difference_type;
 
     MapAllocator() : arena_(NULL) {}
     explicit MapAllocator(Arena* arena) : arena_(arena) {}
     template <typename X>
     MapAllocator(const MapAllocator<X>& allocator)
-        : arena_(allocator.arena_) {}
+        : arena_(allocator.arena()) {}
 
     pointer allocate(size_type n, const_pointer hint = 0) {
       // If arena is not given, malloc needs to be called which doesn't
       // construct element object.
       if (arena_ == NULL) {
-        return reinterpret_cast<pointer>(malloc(n * sizeof(value_type)));
+        return static_cast<pointer>(::operator new(n * sizeof(value_type)));
       } else {
         return reinterpret_cast<pointer>(
             Arena::CreateArray<uint8>(arena_, n * sizeof(value_type)));
       }
     }
 
     void deallocate(pointer p, size_type n) {
       if (arena_ == NULL) {
-        free(p);
+#if defined(__GXX_DELETE_WITH_SIZE__) || defined(__cpp_sized_deallocation)
+        ::operator delete(p, n * sizeof(value_type));
+#else
+        ::operator delete(p);
+#endif
       }
     }
 
 #if __cplusplus >= 201103L && !defined(GOOGLE_PROTOBUF_OS_APPLE) && \
     !defined(GOOGLE_PROTOBUF_OS_NACL) &&                            \
-    !defined(GOOGLE_PROTOBUF_OS_ANDROID) &&                         \
     !defined(GOOGLE_PROTOBUF_OS_EMSCRIPTEN)
     template<class NodeType, class... Args>
     void construct(NodeType* p, Args&&... args) {
       // Clang 3.6 doesn't compile static casting to void* directly. (Issue
       // #1266) According C++ standard 5.2.9/1: "The static_cast operator shall
       // not cast away constness". So first the maybe const pointer is casted to
       // const void* and after the const void* is const casted.
       new (const_cast<void*>(static_cast<const void*>(p)))
           NodeType(std::forward<Args>(args)...);
     }
@@ skipping 18 matching lines @@
       return arena_ == other.arena_;
     }
 
     template <typename X>
     bool operator!=(const MapAllocator<X>& other) const {
       return arena_ != other.arena_;
     }
 
     // To support Visual Studio 2008
     size_type max_size() const {
-      return std::numeric_limits<size_type>::max();
+      // parentheses around (std::...:max) prevents macro warning of max()
+      return (std::numeric_limits<size_type>::max)();
+    }
+
+    // To support gcc-4.4, which does not properly
+    // support templated friend classes
+    Arena* arena() const {
+      return arena_;
     }
 
    private:
     typedef void DestructorSkippable_;
     Arena* const arena_;
-
-    template <typename X>
-    friend class MapAllocator;
   };
 
   // InnerMap's key type is Key and its value type is value_type*.  We use a
   // custom class here and for Node, below, to ensure that k_ is at offset 0,
   // allowing safe conversion from pointer to Node to pointer to Key, and vice
   // versa when appropriate.
   class KeyValuePair {
    public:
     KeyValuePair(const Key& k, value_type* v) : k_(k), v_(v) {}
 
@@ skipping 398 matching lines @@
         } else {
           // Insert into a pre-existing list.  This case cannot modify
           // index_of_first_non_null_, so we skip the code to update it.
           return InsertUniqueInList(b, node);
         }
       } else {
         // Insert into a pre-existing tree.  This case cannot modify
         // index_of_first_non_null_, so we skip the code to update it.
         return InsertUniqueInTree(b, node);
       }
+      // parentheses around (std::min) prevents macro expansion of min(...)
       index_of_first_non_null_ =
-          std::min(index_of_first_non_null_, result.bucket_index_);
+          (std::min)(index_of_first_non_null_, result.bucket_index_);
       return result;
     }
 
     // Helper for InsertUnique.  Handles the case where bucket b is a
     // not-too-long linked list.
     iterator InsertUniqueInList(size_type b, Node* node) {
       node->next = static_cast<Node*>(table_[b]);
       table_[b] = static_cast<void*>(node);
       return iterator(node, this, b);
     }
@@ skipping 151 matching lines @@
         Node* next = node->next;
         node->next = NULL;
         node = next;
       }
       return count;
     }
 
     // Return whether table_[b] is a linked list that seems awfully long.
     // Requires table_[b] to point to a non-empty linked list.
     bool TableEntryIsTooLong(size_type b) {
-      const int kMaxLength = 8;
+      const size_type kMaxLength = 8;
       size_type count = 0;
       Node* node = static_cast<Node*>(table_[b]);
       do {
         ++count;
         node = node->next;
       } while (node != NULL);
       // Invariant: no linked list ever is more than kMaxLength in length.
       GOOGLE_DCHECK_LE(count, kMaxLength);
       return count >= kMaxLength;
     }
@@ skipping 77 matching lines @@
 
     size_type num_elements_;
     size_type num_buckets_;
     size_type seed_;
     size_type index_of_first_non_null_;
     void** table_;  // an array with num_buckets_ entries
     Allocator alloc_;
     GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(InnerMap);
   };  // end of class InnerMap
 
-  typedef hash_map<Key, value_type*, hash<Key>, equal_to<Key>,
+  typedef hash_map<Key, value_type*, hash<Key>, std::equal_to<Key>,
                    MapAllocator<std::pair<const Key, MapPair<Key, T>*> > >
       DeprecatedInnerMap;
 
  public:
   // Iterators
   class iterator_base {
    public:
     // We support "old style" and "new style" iterators for now. This is
     // temporary.  Also, for "iterator()" we have an unknown category.
     // TODO(gpike): get rid of this.
@@ skipping 252 matching lines @@
 
   // Assign
   Map& operator=(const Map& other) {
     if (this != &other) {
       clear();
       insert(other.begin(), other.end());
     }
     return *this;
   }
 
+  void swap(Map& other) {
+    if (arena_ == other.arena_ && old_style_ == other.old_style_) {
+      std::swap(default_enum_value_, other.default_enum_value_);
+      if (old_style_) {
+        std::swap(deprecated_elements_, other.deprecated_elements_);
+      } else {
+        std::swap(elements_, other.elements_);
+      }
+    } else {
+      // TODO(zuguang): optimize this. The temporary copy can be allocated
+      // in the same arena as the other message, and the "other = copy" can
+      // be replaced with the fast-path swap above.
+      Map copy = *this;
+      *this = other;
+      other = copy;
+    }
+  }
+
   // Access to hasher.  Currently this returns a copy, but it may
   // be modified to return a const reference in the future.
   hasher hash_function() const {
     return old_style_ ? deprecated_elements_->hash_function()
                       : elements_->hash_function();
   }
 
  private:
   // Set default enum value only for proto2 map field whose value is enum type.
   void SetDefaultEnumValue(int default_enum_value) {
@@ skipping 81 matching lines @@
   }
   bool
   operator()(const google::protobuf::MapKey& map_key1,
              const google::protobuf::MapKey& map_key2) const {
     return map_key1 < map_key2;
   }
 };
 GOOGLE_PROTOBUF_HASH_NAMESPACE_DECLARATION_END
 
 #endif  // GOOGLE_PROTOBUF_MAP_H__