FM / protobuf

/usr/include/google/protobuf

Name	Size	Mode	Actions
io/	-	0755	rm
stubs/	-	0755	rm
util/	-	0755	rm
any.h	6181	0644	edit dl rm
any.pb.h	17726	0644	edit dl rm
any.proto	5878	0644	edit dl rm
api.pb.h	64196	0644	edit dl rm
api.proto	7734	0644	edit dl rm
arena.h	31329	0644	edit dl rm
arenastring.h	14674	0644	edit dl rm
arena_impl.h	14316	0644	edit dl rm
descriptor.h	96357	0644	edit dl rm
descriptor.pb.h	587894	0644	edit dl rm
descriptor.proto	37986	0644	edit dl rm
descriptor_database.h	19379	0644	edit dl rm
duration.pb.h	9865	0644	edit dl rm
duration.proto	4888	0644	edit dl rm
dynamic_message.h	9986	0644	edit dl rm
empty.pb.h	7683	0644	edit dl rm
empty.proto	2422	0644	edit dl rm
extension_set.h	78461	0644	edit dl rm
extension_set_inl.h	12756	0644	edit dl rm
field_mask.pb.h	11825	0644	edit dl rm
field_mask.proto	8192	0644	edit dl rm
generated_enum_reflection.h	3954	0644	edit dl rm
generated_enum_util.h	3266	0644	edit dl rm
generated_message_reflection.h	12880	0644	edit dl rm
generated_message_table_driven.h	12610	0644	edit dl rm
generated_message_util.h	9560	0644	edit dl rm
has_bits.h	3528	0644	edit dl rm
implicit_weak_message.h	7014	0644	edit dl rm
inlined_string_field.h	9332	0644	edit dl rm
map.h	46287	0644	edit dl rm
map_entry.h	7276	0644	edit dl rm
map_entry_lite.h	26016	0644	edit dl rm
map_field.h	31208	0644	edit dl rm
map_field_inl.h	14512	0644	edit dl rm
map_field_lite.h	7559	0644	edit dl rm
map_type_handler.h	39082	0644	edit dl rm
message.h	61613	0644	edit dl rm
message_lite.h	25964	0644	edit dl rm
metadata.h	1857	0644	edit dl rm
metadata_lite.h	8260	0644	edit dl rm
parse_context.h	29812	0644	edit dl rm
port.h	2050	0644	edit dl rm
port_def.inc	17039	0644	edit dl rm
port_undef.inc	3498	0644	edit dl rm
reflection.h	22717	0644	edit dl rm
reflection_ops.h	3686	0644	edit dl rm
repeated_field.h	101032	0644	edit dl rm
service.h	13159	0644	edit dl rm
source_context.pb.h	12740	0644	edit dl rm
source_context.proto	2352	0644	edit dl rm
struct.pb.h	43629	0644	edit dl rm
struct.proto	3780	0644	edit dl rm
text_format.h	28948	0644	edit dl rm
timestamp.pb.h	9928	0644	edit dl rm
timestamp.proto	6200	0644	edit dl rm
type.pb.h	105722	0644	edit dl rm
type.proto	6129	0644	edit dl rm
unknown_field_set.h	14401	0644	edit dl rm
wire_format.h	17660	0644	edit dl rm
wire_format_lite.h	84033	0644	edit dl rm
wrappers.pb.h	61421	0644	edit dl rm
wrappers.proto	4035	0644	edit dl rm

Edit: /usr/include/google/protobuf/map.h (46287B)

// 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.
//     * 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.

// 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 <initializer_list>
#include <iterator>
#include <limits>  // To support Visual Studio 2008
#include <set>
#include <type_traits>
#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/stubs/hash.h>

#ifdef SWIG
#error "You cannot SWIG proto headers"
#endif

#include <google/protobuf/port_def.inc>

namespace google {
namespace protobuf {

template <typename Key, typename T>
class Map;

class MapIterator;

template <typename Enum>
struct is_proto_enum;

namespace internal {
template <typename Derived, typename Key, typename T,
          WireFormatLite::FieldType key_wire_type,
          WireFormatLite::FieldType value_wire_type, int default_enum_value>
class MapFieldLite;

template <typename Derived, typename Key, typename T,
          WireFormatLite::FieldType key_wire_type,
          WireFormatLite::FieldType value_wire_type, int default_enum_value>
class MapField;

template <typename Key, typename T>
class TypeDefinedMapFieldBase;

class DynamicMapField;

class GeneratedMessageReflection;

// re-implement std::allocator to use arena allocator for memory allocation.
// Used for Map implementation. Users should not use this class
// directly.
template <typename U>
class MapAllocator {
 public:
  using value_type = U;
  using pointer = value_type*;
  using const_pointer = const value_type*;
  using reference = value_type&;
  using const_reference = const value_type&;
  using size_type = size_t;
  using difference_type = ptrdiff_t;

MapAllocator() : arena_(nullptr) {}
  explicit MapAllocator(Arena* arena) : arena_(arena) {}
  template <typename X>
  MapAllocator(const MapAllocator<X>& allocator)  // NOLINT(runtime/explicit)
      : arena_(allocator.arena()) {}

pointer allocate(size_type n, const void* /* hint */ = nullptr) {
    // If arena is not given, malloc needs to be called which doesn't
    // construct element object.
    if (arena_ == nullptr) {
      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_ == nullptr) {
#if defined(__GXX_DELETE_WITH_SIZE__) || defined(__cpp_sized_deallocation)
      ::operator delete(p, n * sizeof(value_type));
#else
      (void)n;
      ::operator delete(p);
#endif
    }
  }

#if __cplusplus >= 201103L && !defined(GOOGLE_PROTOBUF_OS_APPLE) && \
    !defined(GOOGLE_PROTOBUF_OS_NACL) &&                            \
    !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)...);
  }

template <class NodeType>
  void destroy(NodeType* p) {
    p->~NodeType();
  }
#else
  void construct(pointer p, const_reference t) { new (p) value_type(t); }

void destroy(pointer p) { p->~value_type(); }
#endif

template <typename X>
  struct rebind {
    using other = MapAllocator<X>;
  };

template <typename X>
  bool operator==(const MapAllocator<X>& other) const {
    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 {
    // 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:
  using DestructorSkippable_ = void;
  Arena* const arena_;
};

template <typename Key>
struct DerefCompare {
  bool operator()(const Key* n0, const Key* n1) const { return *n0 < *n1; }
};

// This class is used to get trivially destructible views of std::string and
// MapKey, which are the only non-trivially destructible allowed key types.
template <typename Key>
class KeyView {
 public:
  KeyView(const Key& key) : key_(&key) {}  // NOLINT(runtime/explicit)

const Key& get() const { return *key_; }
  // Allows implicit conversions to `const Key&`, which allows us to use the
  // hasher defined for Key.
  operator const Key&() const { return get(); }  // NOLINT(runtime/explicit)

bool operator==(const KeyView& other) const { return get() == other.get(); }
  bool operator==(const Key& other) const { return get() == other; }
  bool operator<(const KeyView& other) const { return get() < other.get(); }
  bool operator<(const Key& other) const { return get() < other; }

private:
  const Key* key_;
};

// Allows the InnerMap type to support skippable destruction.
template <typename Key>
struct GetTrivialKey {
  using type =
      typename std::conditional<std::is_trivially_destructible<Key>::value, Key,
                                KeyView<Key>>::type;
};

}  // namespace internal

// This is the class for Map's internal value_type. Instead of using
// std::pair as value_type, we use this class which provides us more control of
// its process of construction and destruction.
template <typename Key, typename T>
struct MapPair {
  using first_type = const Key;
  using second_type = T;

MapPair(const Key& other_first, const T& other_second)
      : first(other_first), second(other_second) {}
  explicit MapPair(const Key& other_first) : first(other_first), second() {}
  MapPair(const MapPair& other) : first(other.first), second(other.second) {}

~MapPair() {}

// Implicitly convertible to std::pair of compatible types.
  template <typename T1, typename T2>
  operator std::pair<T1, T2>() const {  // NOLINT(runtime/explicit)
    return std::pair<T1, T2>(first, second);
  }

const Key first;
  T second;

private:
  friend class Arena;
  friend class Map<Key, T>;
};

// Map is an associative container type used to store protobuf map
// fields.  Each Map instance may or may not use a different hash function, a
// different iteration order, and so on.  E.g., please don't examine
// implementation details to decide if the following would work:
//  Map<int, int> m0, m1;
//  m0[0] = m1[0] = m0[1] = m1[1] = 0;
//  assert(m0.begin()->first == m1.begin()->first);  // Bug!
//
// Map's interface is similar to std::unordered_map, except that Map is not
// designed to play well with exceptions.
template <typename Key, typename T>
class Map {
 public:
  using key_type = Key;
  using mapped_type = T;
  using value_type = MapPair<Key, T>;

using pointer = value_type*;
  using const_pointer = const value_type*;
  using reference = value_type&;
  using const_reference = const value_type&;

using size_type = size_t;
  using hasher = hash<Key>;

Map() : arena_(nullptr), default_enum_value_(0) { Init(); }
  explicit Map(Arena* arena) : arena_(arena), default_enum_value_(0) { Init(); }

Map(const Map& other)
      : arena_(nullptr), default_enum_value_(other.default_enum_value_) {
    Init();
    insert(other.begin(), other.end());
  }

Map(Map&& other) noexcept : Map() {
    if (other.arena_) {
      *this = other;
    } else {
      swap(other);
    }
  }
  Map& operator=(Map&& other) noexcept {
    if (this != &other) {
      if (arena_ != other.arena_) {
        *this = other;
      } else {
        swap(other);
      }
    }
    return *this;
  }

template <class InputIt>
  Map(const InputIt& first, const InputIt& last)
      : arena_(nullptr), default_enum_value_(0) {
    Init();
    insert(first, last);
  }

~Map() {
    clear();
    if (arena_ == nullptr) {
      delete elements_;
    }
  }

private:
  void Init() { elements_ = Arena::CreateMessage<InnerMap>(arena_, 0u); }

// InnerMap's key type is TrivialKey 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 TrivialKey,
  // and vice versa when appropriate.  We use GetTrivialKey to adapt Key to
  // be a trivially destructible view if Key is not already trivially
  // destructible.  This view points into the Key inside v_ once it's
  // initialized.
  using TrivialKey = typename internal::GetTrivialKey<Key>::type;
  class KeyValuePair {
   public:
    KeyValuePair(const TrivialKey& k, value_type* v) : k_(k), v_(v) {}

const TrivialKey& key() const { return k_; }
    TrivialKey& key() { return k_; }
    value_type* value() const { return v_; }
    value_type*& value() { return v_; }

private:
    TrivialKey k_;
    value_type* v_;
  };

using Allocator = internal::MapAllocator<KeyValuePair>;

// InnerMap is a generic hash-based map.  It doesn't contain any
  // protocol-buffer-specific logic.  It is a chaining hash map with the
  // additional feature that some buckets can be converted to use an ordered
  // container.  This ensures O(lg n) bounds on find, insert, and erase, while
  // avoiding the overheads of ordered containers most of the time.
  //
  // The implementation doesn't need the full generality of unordered_map,
  // and it doesn't have it.  More bells and whistles can be added as needed.
  // Some implementation details:
  // 1. The hash function has type hasher and the equality function
  //    equal_to<Key>.  We inherit from hasher to save space
  //    (empty-base-class optimization).
  // 2. The number of buckets is a power of two.
  // 3. Buckets are converted to trees in pairs: if we convert bucket b then
  //    buckets b and b^1 will share a tree.  Invariant: buckets b and b^1 have
  //    the same non-null value iff they are sharing a tree.  (An alternative
  //    implementation strategy would be to have a tag bit per bucket.)
  // 4. As is typical for hash_map and such, the Keys and Values are always
  //    stored in linked list nodes.  Pointers to elements are never invalidated
  //    until the element is deleted.
  // 5. The trees' payload type is pointer to linked-list node.  Tree-converting
  //    a bucket doesn't copy Key-Value pairs.
  // 6. Once we've tree-converted a bucket, it is never converted back. However,
  //    the items a tree contains may wind up assigned to trees or lists upon a
  //    rehash.
  // 7. The code requires no C++ features from C++14 or later.
  // 8. Mutations to a map do not invalidate the map's iterators, pointers to
  //    elements, or references to elements.
  // 9. Except for erase(iterator), any non-const method can reorder iterators.
  // 10. InnerMap's key is TrivialKey, which is either Key, if Key is trivially
  //    destructible, or a trivially destructible view of Key otherwise. This
  //    allows InnerMap's destructor to be skipped when InnerMap is
  //    arena-allocated.
  class InnerMap : private hasher {
   public:
    using Value = value_type*;

explicit InnerMap(size_type n) : InnerMap(nullptr, n) {}
    InnerMap(Arena* arena, size_type n)
        : hasher(),
          num_elements_(0),
          seed_(Seed()),
          table_(nullptr),
          alloc_(arena) {
      n = TableSize(n);
      table_ = CreateEmptyTable(n);
      num_buckets_ = index_of_first_non_null_ = n;
      static_assert(
          std::is_trivially_destructible<KeyValuePair>::value,
          "We require KeyValuePair to be trivially destructible so that we can "
          "skip InnerMap's destructor when it's arena allocated.");
    }

~InnerMap() {
      if (table_ != nullptr) {
        clear();
        Dealloc<void*>(table_, num_buckets_);
      }
    }

private:
    enum { kMinTableSize = 8 };

// Linked-list nodes, as one would expect for a chaining hash table.
    struct Node {
      KeyValuePair kv;
      Node* next;
    };

// This is safe only if the given pointer is known to point to a Key that is
    // part of a Node.
    static Node* NodePtrFromKeyPtr(TrivialKey* k) {
      return reinterpret_cast<Node*>(k);
    }

static TrivialKey* KeyPtrFromNodePtr(Node* node) { return &node->kv.key(); }

// Trees.  The payload type is pointer to Key, so that we can query the tree
    // with Keys that are not in any particular data structure.  When we insert,
    // though, the pointer is always pointing to a Key that is inside a Node.
    using KeyPtrAllocator =
        typename Allocator::template rebind<TrivialKey*>::other;
    using Tree = std::set<TrivialKey*, internal::DerefCompare<TrivialKey>,
                          KeyPtrAllocator>;
    using TreeIterator = typename Tree::iterator;

// iterator and const_iterator are instantiations of iterator_base.
    template <typename KeyValueType>
    class iterator_base {
     public:
      using reference = KeyValueType&;
      using pointer = KeyValueType*;

// Invariants:
      // node_ is always correct. This is handy because the most common
      // operations are operator* and operator-> and they only use node_.
      // When node_ is set to a non-null value, all the other non-const fields
      // are updated to be correct also, but those fields can become stale
      // if the underlying map is modified.  When those fields are needed they
      // are rechecked, and updated if necessary.
      iterator_base() : node_(nullptr), m_(nullptr), bucket_index_(0) {}

explicit iterator_base(const InnerMap* m) : m_(m) {
        SearchFrom(m->index_of_first_non_null_);
      }

// Any iterator_base can convert to any other.  This is overkill, and we
      // rely on the enclosing class to use it wisely.  The standard "iterator
      // can convert to const_iterator" is OK but the reverse direction is not.
      template <typename U>
      explicit iterator_base(const iterator_base<U>& it)
          : node_(it.node_), m_(it.m_), bucket_index_(it.bucket_index_) {}

iterator_base(Node* n, const InnerMap* m, size_type index)
          : node_(n), m_(m), bucket_index_(index) {}

iterator_base(TreeIterator tree_it, const InnerMap* m, size_type index)
          : node_(NodePtrFromKeyPtr(*tree_it)), m_(m), bucket_index_(index) {
        // Invariant: iterators that use buckets with trees have an even
        // bucket_index_.
        GOOGLE_DCHECK_EQ(bucket_index_ % 2, 0u);
      }

// Advance through buckets, looking for the first that isn't empty.
      // If nothing non-empty is found then leave node_ == nullptr.
      void SearchFrom(size_type start_bucket) {
        GOOGLE_DCHECK(m_->index_of_first_non_null_ == m_->num_buckets_ ||
               m_->table_[m_->index_of_first_non_null_] != nullptr);
        node_ = nullptr;
        for (bucket_index_ = start_bucket; bucket_index_ < m_->num_buckets_;
             bucket_index_++) {
          if (m_->TableEntryIsNonEmptyList(bucket_index_)) {
            node_ = static_cast<Node*>(m_->table_[bucket_index_]);
            break;
          } else if (m_->TableEntryIsTree(bucket_index_)) {
            Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]);
            GOOGLE_DCHECK(!tree->empty());
            node_ = NodePtrFromKeyPtr(*tree->begin());
            break;
          }
        }
      }

reference operator*() const { return node_->kv; }
      pointer operator->() const { return &(operator*()); }

friend bool operator==(const iterator_base& a, const iterator_base& b) {
        return a.node_ == b.node_;
      }
      friend bool operator!=(const iterator_base& a, const iterator_base& b) {
        return a.node_ != b.node_;
      }

iterator_base& operator++() {
        if (node_->next == nullptr) {
          TreeIterator tree_it;
          const bool is_list = revalidate_if_necessary(&tree_it);
          if (is_list) {
            SearchFrom(bucket_index_ + 1);
          } else {
            GOOGLE_DCHECK_EQ(bucket_index_ & 1, 0u);
            Tree* tree = static_cast<Tree*>(m_->table_[bucket_index_]);
            if (++tree_it == tree->end()) {
              SearchFrom(bucket_index_ + 2);
            } else {
              node_ = NodePtrFromKeyPtr(*tree_it);
            }
          }
        } else {
          node_ = node_->next;
        }
        return *this;
      }

iterator_base operator++(int /* unused */) {
        iterator_base tmp = *this;
        ++*this;
        return tmp;
      }

// Assumes node_ and m_ are correct and non-null, but other fields may be
      // stale.  Fix them as needed.  Then return true iff node_ points to a
      // Node in a list.  If false is returned then *it is modified to be
      // a valid iterator for node_.
      bool revalidate_if_necessary(TreeIterator* it) {
        GOOGLE_DCHECK(node_ != nullptr && m_ != nullptr);
        // Force bucket_index_ to be in range.
        bucket_index_ &= (m_->num_buckets_ - 1);
        // Common case: the bucket we think is relevant points to node_.
        if (m_->table_[bucket_index_] == static_cast<void*>(node_)) return true;
        // Less common: the bucket is a linked list with node_ somewhere in it,
        // but not at the head.
        if (m_->TableEntryIsNonEmptyList(bucket_index_)) {
          Node* l = static_cast<Node*>(m_->table_[bucket_index_]);
          while ((l = l->next) != nullptr) {
            if (l == node_) {
              return true;
            }
          }
        }
        // Well, bucket_index_ still might be correct, but probably
        // not.  Revalidate just to be sure.  This case is rare enough that we
        // don't worry about potential optimizations, such as having a custom
        // find-like method that compares Node* instead of TrivialKey.
        iterator_base i(m_->find(*KeyPtrFromNodePtr(node_), it));
        bucket_index_ = i.bucket_index_;
        return m_->TableEntryIsList(bucket_index_);
      }

Node* node_;
      const InnerMap* m_;
      size_type bucket_index_;
    };

public:
    using iterator = iterator_base<KeyValuePair>;
    using const_iterator = iterator_base<const KeyValuePair>;

iterator begin() { return iterator(this); }
    iterator end() { return iterator(); }
    const_iterator begin() const { return const_iterator(this); }
    const_iterator end() const { return const_iterator(); }

void clear() {
      for (size_type b = 0; b < num_buckets_; b++) {
        if (TableEntryIsNonEmptyList(b)) {
          Node* node = static_cast<Node*>(table_[b]);
          table_[b] = nullptr;
          do {
            Node* next = node->next;
            DestroyNode(node);
            node = next;
          } while (node != nullptr);
        } else if (TableEntryIsTree(b)) {
          Tree* tree = static_cast<Tree*>(table_[b]);
          GOOGLE_DCHECK(table_[b] == table_[b + 1] && (b & 1) == 0);
          table_[b] = table_[b + 1] = nullptr;
          typename Tree::iterator tree_it = tree->begin();
          do {
            Node* node = NodePtrFromKeyPtr(*tree_it);
            typename Tree::iterator next = tree_it;
            ++next;
            tree->erase(tree_it);
            DestroyNode(node);
            tree_it = next;
          } while (tree_it != tree->end());
          DestroyTree(tree);
          b++;
        }
      }
      num_elements_ = 0;
      index_of_first_non_null_ = num_buckets_;
    }

const hasher& hash_function() const { return *this; }

static size_type max_size() {
      return static_cast<size_type>(1) << (sizeof(void**) >= 8 ? 60 : 28);
    }
    size_type size() const { return num_elements_; }
    bool empty() const { return size() == 0; }

iterator find(const TrivialKey& k) { return iterator(FindHelper(k).first); }
    const_iterator find(const TrivialKey& k) const { return find(k, nullptr); }
    bool contains(const TrivialKey& k) const { return find(k) != end(); }

// In traditional C++ style, this performs "insert if not present."
    std::pair<iterator, bool> insert(const KeyValuePair& kv) {
      std::pair<const_iterator, size_type> p = FindHelper(kv.key());
      // Case 1: key was already present.
      if (p.first.node_ != nullptr)
        return std::make_pair(iterator(p.first), false);
      // Case 2: insert.
      if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) {
        p = FindHelper(kv.key());
      }
      const size_type b = p.second;  // bucket number
      Node* node = Alloc<Node>(1);
      alloc_.construct(&node->kv, kv);
      iterator result = InsertUnique(b, node);
      ++num_elements_;
      return std::make_pair(result, true);
    }

// The same, but if an insertion is necessary then the value portion of the
    // inserted key-value pair is left uninitialized.
    std::pair<iterator, bool> insert(const TrivialKey& k) {
      std::pair<const_iterator, size_type> p = FindHelper(k);
      // Case 1: key was already present.
      if (p.first.node_ != nullptr)
        return std::make_pair(iterator(p.first), false);
      // Case 2: insert.
      if (ResizeIfLoadIsOutOfRange(num_elements_ + 1)) {
        p = FindHelper(k);
      }
      const size_type b = p.second;  // bucket number
      Node* node = Alloc<Node>(1);
      using KeyAllocator =
          typename Allocator::template rebind<TrivialKey>::other;
      KeyAllocator(alloc_).construct(&node->kv.key(), k);
      iterator result = InsertUnique(b, node);
      ++num_elements_;
      return std::make_pair(result, true);
    }

// Returns iterator so that outer map can update the TrivialKey to point to
    // the Key inside value_type in case TrivialKey is a view type.
    iterator operator[](const TrivialKey& k) {
      KeyValuePair kv(k, Value());
      return insert(kv).first;
    }

void erase(iterator it) {
      GOOGLE_DCHECK_EQ(it.m_, this);
      typename Tree::iterator tree_it;
      const bool is_list = it.revalidate_if_necessary(&tree_it);
      size_type b = it.bucket_index_;
      Node* const item = it.node_;
      if (is_list) {
        GOOGLE_DCHECK(TableEntryIsNonEmptyList(b));
        Node* head = static_cast<Node*>(table_[b]);
        head = EraseFromLinkedList(item, head);
        table_[b] = static_cast<void*>(head);
      } else {
        GOOGLE_DCHECK(TableEntryIsTree(b));
        Tree* tree = static_cast<Tree*>(table_[b]);
        tree->erase(*tree_it);
        if (tree->empty()) {
          // Force b to be the minimum of b and b ^ 1.  This is important
          // only because we want index_of_first_non_null_ to be correct.
          b &= ~static_cast<size_type>(1);
          DestroyTree(tree);
          table_[b] = table_[b + 1] = nullptr;
        }
      }
      DestroyNode(item);
      --num_elements_;
      if (PROTOBUF_PREDICT_FALSE(b == index_of_first_non_null_)) {
        while (index_of_first_non_null_ < num_buckets_ &&
               table_[index_of_first_non_null_] == nullptr) {
          ++index_of_first_non_null_;
        }
      }
    }

private:
    const_iterator find(const TrivialKey& k, TreeIterator* it) const {
      return FindHelper(k, it).first;
    }
    std::pair<const_iterator, size_type> FindHelper(const TrivialKey& k) const {
      return FindHelper(k, nullptr);
    }
    std::pair<const_iterator, size_type> FindHelper(const TrivialKey& k,
                                                    TreeIterator* it) const {
      size_type b = BucketNumber(k);
      if (TableEntryIsNonEmptyList(b)) {
        Node* node = static_cast<Node*>(table_[b]);
        do {
          if (IsMatch(*KeyPtrFromNodePtr(node), k)) {
            return std::make_pair(const_iterator(node, this, b), b);
          } else {
            node = node->next;
          }
        } while (node != nullptr);
      } else if (TableEntryIsTree(b)) {
        GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]);
        b &= ~static_cast<size_t>(1);
        Tree* tree = static_cast<Tree*>(table_[b]);
        TrivialKey* key = const_cast<TrivialKey*>(&k);
        typename Tree::iterator tree_it = tree->find(key);
        if (tree_it != tree->end()) {
          if (it != nullptr) *it = tree_it;
          return std::make_pair(const_iterator(tree_it, this, b), b);
        }
      }
      return std::make_pair(end(), b);
    }

// Insert the given Node in bucket b.  If that would make bucket b too big,
    // and bucket b is not a tree, create a tree for buckets b and b^1 to share.
    // Requires count(*KeyPtrFromNodePtr(node)) == 0 and that b is the correct
    // bucket.  num_elements_ is not modified.
    iterator InsertUnique(size_type b, Node* node) {
      GOOGLE_DCHECK(index_of_first_non_null_ == num_buckets_ ||
             table_[index_of_first_non_null_] != nullptr);
      // In practice, the code that led to this point may have already
      // determined whether we are inserting into an empty list, a short list,
      // or whatever.  But it's probably cheap enough to recompute that here;
      // it's likely that we're inserting into an empty or short list.
      iterator result;
      GOOGLE_DCHECK(find(*KeyPtrFromNodePtr(node)) == end());
      if (TableEntryIsEmpty(b)) {
        result = InsertUniqueInList(b, node);
      } else if (TableEntryIsNonEmptyList(b)) {
        if (PROTOBUF_PREDICT_FALSE(TableEntryIsTooLong(b))) {
          TreeConvert(b);
          result = InsertUniqueInTree(b, node);
          GOOGLE_DCHECK_EQ(result.bucket_index_, b & ~static_cast<size_type>(1));
        } 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_);
      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);
    }

// Helper for InsertUnique.  Handles the case where bucket b points to a
    // Tree.
    iterator InsertUniqueInTree(size_type b, Node* node) {
      GOOGLE_DCHECK_EQ(table_[b], table_[b ^ 1]);
      // Maintain the invariant that node->next is null for all Nodes in Trees.
      node->next = nullptr;
      return iterator(
          static_cast<Tree*>(table_[b])->insert(KeyPtrFromNodePtr(node)).first,
          this, b & ~static_cast<size_t>(1));
    }

// Returns whether it did resize.  Currently this is only used when
    // num_elements_ increases, though it could be used in other situations.
    // It checks for load too low as well as load too high: because any number
    // of erases can occur between inserts, the load could be as low as 0 here.
    // Resizing to a lower size is not always helpful, but failing to do so can
    // destroy the expected big-O bounds for some operations. By having the
    // policy that sometimes we resize down as well as up, clients can easily
    // keep O(size()) = O(number of buckets) if they want that.
    bool ResizeIfLoadIsOutOfRange(size_type new_size) {
      const size_type kMaxMapLoadTimes16 = 12;  // controls RAM vs CPU tradeoff
      const size_type hi_cutoff = num_buckets_ * kMaxMapLoadTimes16 / 16;
      const size_type lo_cutoff = hi_cutoff / 4;
      // We don't care how many elements are in trees.  If a lot are,
      // we may resize even though there are many empty buckets.  In
      // practice, this seems fine.
      if (PROTOBUF_PREDICT_FALSE(new_size >= hi_cutoff)) {
        if (num_buckets_ <= max_size() / 2) {
          Resize(num_buckets_ * 2);
          return true;
        }
      } else if (PROTOBUF_PREDICT_FALSE(new_size <= lo_cutoff &&
                                        num_buckets_ > kMinTableSize)) {
        size_type lg2_of_size_reduction_factor = 1;
        // It's possible we want to shrink a lot here... size() could even be 0.
        // So, estimate how much to shrink by making sure we don't shrink so
        // much that we would need to grow the table after a few inserts.
        const size_type hypothetical_size = new_size * 5 / 4 + 1;
        while ((hypothetical_size << lg2_of_size_reduction_factor) <
               hi_cutoff) {
          ++lg2_of_size_reduction_factor;
        }
        size_type new_num_buckets = std::max<size_type>(
            kMinTableSize, num_buckets_ >> lg2_of_size_reduction_factor);
        if (new_num_buckets != num_buckets_) {
          Resize(new_num_buckets);
          return true;
        }
      }
      return false;
    }

// Resize to the given number of buckets.
    void Resize(size_t new_num_buckets) {
      GOOGLE_DCHECK_GE(new_num_buckets, kMinTableSize);
      void** const old_table = table_;
      const size_type old_table_size = num_buckets_;
      num_buckets_ = new_num_buckets;
      table_ = CreateEmptyTable(num_buckets_);
      const size_type start = index_of_first_non_null_;
      index_of_first_non_null_ = num_buckets_;
      for (size_type i = start; i < old_table_size; i++) {
        if (TableEntryIsNonEmptyList(old_table, i)) {
          TransferList(old_table, i);
        } else if (TableEntryIsTree(old_table, i)) {
          TransferTree(old_table, i++);
        }
      }
      Dealloc<void*>(old_table, old_table_size);
    }

void TransferList(void* const* table, size_type index) {
      Node* node = static_cast<Node*>(table[index]);
      do {
        Node* next = node->next;
        InsertUnique(BucketNumber(*KeyPtrFromNodePtr(node)), node);
        node = next;
      } while (node != nullptr);
    }

void TransferTree(void* const* table, size_type index) {
      Tree* tree = static_cast<Tree*>(table[index]);
      typename Tree::iterator tree_it = tree->begin();
      do {
        Node* node = NodePtrFromKeyPtr(*tree_it);
        InsertUnique(BucketNumber(**tree_it), node);
      } while (++tree_it != tree->end());
      DestroyTree(tree);
    }

Node* EraseFromLinkedList(Node* item, Node* head) {
      if (head == item) {
        return head->next;
      } else {
        head->next = EraseFromLinkedList(item, head->next);
        return head;
      }
    }

bool TableEntryIsEmpty(size_type b) const {
      return TableEntryIsEmpty(table_, b);
    }
    bool TableEntryIsNonEmptyList(size_type b) const {
      return TableEntryIsNonEmptyList(table_, b);
    }
    bool TableEntryIsTree(size_type b) const {
      return TableEntryIsTree(table_, b);
    }
    bool TableEntryIsList(size_type b) const {
      return TableEntryIsList(table_, b);
    }
    static bool TableEntryIsEmpty(void* const* table, size_type b) {
      return table[b] == nullptr;
    }
    static bool TableEntryIsNonEmptyList(void* const* table, size_type b) {
      return table[b] != nullptr && table[b] != table[b ^ 1];
    }
    static bool TableEntryIsTree(void* const* table, size_type b) {
      return !TableEntryIsEmpty(table, b) &&
             !TableEntryIsNonEmptyList(table, b);
    }
    static bool TableEntryIsList(void* const* table, size_type b) {
      return !TableEntryIsTree(table, b);
    }

void TreeConvert(size_type b) {
      GOOGLE_DCHECK(!TableEntryIsTree(b) && !TableEntryIsTree(b ^ 1));
      typename Allocator::template rebind<Tree>::other tree_allocator(alloc_);
      Tree* tree = tree_allocator.allocate(1);
      // We want to use the three-arg form of construct, if it exists, but we
      // create a temporary and use the two-arg construct that's known to exist.
      // It's clunky, but the compiler should be able to generate more-or-less
      // the same code.
      tree_allocator.construct(
          tree, Tree(typename Tree::key_compare(), KeyPtrAllocator(alloc_)));
      // Now the tree is ready to use.
      size_type count = CopyListToTree(b, tree) + CopyListToTree(b ^ 1, tree);
      GOOGLE_DCHECK_EQ(count, tree->size());
      table_[b] = table_[b ^ 1] = static_cast<void*>(tree);
    }

// Copy a linked list in the given bucket to a tree.
    // Returns the number of things it copied.
    size_type CopyListToTree(size_type b, Tree* tree) {
      size_type count = 0;
      Node* node = static_cast<Node*>(table_[b]);
      while (node != nullptr) {
        tree->insert(KeyPtrFromNodePtr(node));
        ++count;
        Node* next = node->next;
        node->next = nullptr;
        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 size_type kMaxLength = 8;
      size_type count = 0;
      Node* node = static_cast<Node*>(table_[b]);
      do {
        ++count;
        node = node->next;
      } while (node != nullptr);
      // Invariant: no linked list ever is more than kMaxLength in length.
      GOOGLE_DCHECK_LE(count, kMaxLength);
      return count >= kMaxLength;
    }

size_type BucketNumber(const TrivialKey& k) const {
      size_type h = hash_function()(k);
      return (h + seed_) & (num_buckets_ - 1);
    }

bool IsMatch(const TrivialKey& k0, const TrivialKey& k1) const {
      return k0 == k1;
    }

// Return a power of two no less than max(kMinTableSize, n).
    // Assumes either n < kMinTableSize or n is a power of two.
    size_type TableSize(size_type n) {
      return n < static_cast<size_type>(kMinTableSize)
                 ? static_cast<size_type>(kMinTableSize)
                 : n;
    }

// Use alloc_ to allocate an array of n objects of type U.
    template <typename U>
    U* Alloc(size_type n) {
      using alloc_type = typename Allocator::template rebind<U>::other;
      return alloc_type(alloc_).allocate(n);
    }

// Use alloc_ to deallocate an array of n objects of type U.
    template <typename U>
    void Dealloc(U* t, size_type n) {
      using alloc_type = typename Allocator::template rebind<U>::other;
      alloc_type(alloc_).deallocate(t, n);
    }

void DestroyNode(Node* node) {
      alloc_.destroy(&node->kv);
      Dealloc<Node>(node, 1);
    }

void DestroyTree(Tree* tree) {
      typename Allocator::template rebind<Tree>::other tree_allocator(alloc_);
      tree_allocator.destroy(tree);
      tree_allocator.deallocate(tree, 1);
    }

void** CreateEmptyTable(size_type n) {
      GOOGLE_DCHECK(n >= kMinTableSize);
      GOOGLE_DCHECK_EQ(n & (n - 1), 0);
      void** result = Alloc<void*>(n);
      memset(result, 0, n * sizeof(result[0]));
      return result;
    }

// Return a randomish value.
    size_type Seed() const {
      size_type s = static_cast<size_type>(reinterpret_cast<uintptr_t>(this));
#if defined(__x86_64__) && defined(__GNUC__) && \
    !defined(GOOGLE_PROTOBUF_NO_RDTSC)
      uint32 hi, lo;
      asm("rdtsc" : "=a"(lo), "=d"(hi));
      s += ((static_cast<uint64>(hi) << 32) | lo);
#endif
      return s;
    }

friend class Arena;
    using InternalArenaConstructable_ = void;
    using DestructorSkippable_ = void;

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

public:
  // Iterators
  class const_iterator {
    using InnerIt = typename InnerMap::const_iterator;

public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = typename Map::value_type;
    using difference_type = ptrdiff_t;
    using pointer = const value_type*;
    using reference = const value_type&;

const_iterator() {}
    explicit const_iterator(const InnerIt& it) : it_(it) {}

const_reference operator*() const { return *it_->value(); }
    const_pointer operator->() const { return &(operator*()); }

const_iterator& operator++() {
      ++it_;
      return *this;
    }
    const_iterator operator++(int) { return const_iterator(it_++); }

friend bool operator==(const const_iterator& a, const const_iterator& b) {
      return a.it_ == b.it_;
    }
    friend bool operator!=(const const_iterator& a, const const_iterator& b) {
      return !(a == b);
    }

private:
    InnerIt it_;
  };

class iterator {
    using InnerIt = typename InnerMap::iterator;

public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = typename Map::value_type;
    using difference_type = ptrdiff_t;
    using pointer = value_type*;
    using reference = value_type&;

iterator() {}
    explicit iterator(const InnerIt& it) : it_(it) {}

reference operator*() const { return *it_->value(); }
    pointer operator->() const { return &(operator*()); }

iterator& operator++() {
      ++it_;
      return *this;
    }
    iterator operator++(int) { return iterator(it_++); }

// Allow implicit conversion to const_iterator.
    operator const_iterator() const {  // NOLINT(runtime/explicit)
      return const_iterator(typename InnerMap::const_iterator(it_));
    }

friend bool operator==(const iterator& a, const iterator& b) {
      return a.it_ == b.it_;
    }
    friend bool operator!=(const iterator& a, const iterator& b) {
      return !(a == b);
    }

private:
    friend class Map;

InnerIt it_;
  };

iterator begin() { return iterator(elements_->begin()); }
  iterator end() { return iterator(elements_->end()); }
  const_iterator begin() const {
    return const_iterator(iterator(elements_->begin()));
  }
  const_iterator end() const {
    return const_iterator(iterator(elements_->end()));
  }
  const_iterator cbegin() const { return begin(); }
  const_iterator cend() const { return end(); }

// Capacity
  size_type size() const { return elements_->size(); }
  bool empty() const { return size() == 0; }

// Element access
  T& operator[](const key_type& key) {
    typename InnerMap::iterator it = (*elements_)[key];
    value_type** value = &it->value();
    if (*value == nullptr) {
      *value = CreateValueTypeInternal(key);
      // We need to update the key in case it's a view type.
      it->key() = (*value)->first;
      internal::MapValueInitializer<is_proto_enum<T>::value, T>::Initialize(
          (*value)->second, default_enum_value_);
    }
    return (*value)->second;
  }
  const T& at(const key_type& key) const {
    const_iterator it = find(key);
    GOOGLE_CHECK(it != end()) << "key not found: " << key;
    return it->second;
  }
  T& at(const key_type& key) {
    iterator it = find(key);
    GOOGLE_CHECK(it != end()) << "key not found: " << key;
    return it->second;
  }

// Lookup
  size_type count(const key_type& key) const {
    const_iterator it = find(key);
    GOOGLE_DCHECK(it == end() || key == it->first);
    return it == end() ? 0 : 1;
  }
  const_iterator find(const key_type& key) const {
    return const_iterator(iterator(elements_->find(key)));
  }
  iterator find(const key_type& key) { return iterator(elements_->find(key)); }
  bool contains(const Key& key) const { return elements_->contains(key); }
  std::pair<const_iterator, const_iterator> equal_range(
      const key_type& key) const {
    const_iterator it = find(key);
    if (it == end()) {
      return std::pair<const_iterator, const_iterator>(it, it);
    } else {
      const_iterator begin = it++;
      return std::pair<const_iterator, const_iterator>(begin, it);
    }
  }
  std::pair<iterator, iterator> equal_range(const key_type& key) {
    iterator it = find(key);
    if (it == end()) {
      return std::pair<iterator, iterator>(it, it);
    } else {
      iterator begin = it++;
      return std::pair<iterator, iterator>(begin, it);
    }
  }

// insert
  std::pair<iterator, bool> insert(const value_type& value) {
    std::pair<typename InnerMap::iterator, bool> p =
        elements_->insert(value.first);
    if (p.second) {
      p.first->value() = CreateValueTypeInternal(value);
      // We need to update the key in case it's a view type.
      p.first->key() = p.first->value()->first;
    }
    return std::pair<iterator, bool>(iterator(p.first), p.second);
  }
  template <class InputIt>
  void insert(InputIt first, InputIt last) {
    for (InputIt it = first; it != last; ++it) {
      iterator exist_it = find(it->first);
      if (exist_it == end()) {
        operator[](it->first) = it->second;
      }
    }
  }
  void insert(std::initializer_list<value_type> values) {
    insert(values.begin(), values.end());
  }

// Erase and clear
  size_type erase(const key_type& key) {
    iterator it = find(key);
    if (it == end()) {
      return 0;
    } else {
      erase(it);
      return 1;
    }
  }
  iterator erase(iterator pos) {
    value_type* value = pos.operator->();
    iterator i = pos++;
    elements_->erase(i.it_);
    // Note: we need to delete the value after erasing from the inner map
    // because the inner map's key may be a view of the value's key.
    if (arena_ == nullptr) delete value;
    return pos;
  }
  void erase(iterator first, iterator last) {
    while (first != last) {
      first = erase(first);
    }
  }
  void clear() { erase(begin(), end()); }

// 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_) {
      std::swap(default_enum_value_, other.default_enum_value_);
      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 elements_->hash_function(); }

private:
  // Set default enum value only for proto2 map field whose value is enum type.
  void SetDefaultEnumValue(int default_enum_value) {
    default_enum_value_ = default_enum_value;
  }

value_type* CreateValueTypeInternal(const Key& key) {
    if (arena_ == nullptr) {
      return new value_type(key);
    } else {
      value_type* value = reinterpret_cast<value_type*>(
          Arena::CreateArray<uint8>(arena_, sizeof(value_type)));
      Arena::CreateInArenaStorage(const_cast<Key*>(&value->first), arena_, key);
      Arena::CreateInArenaStorage(&value->second, arena_);
      return value;
    }
  }

value_type* CreateValueTypeInternal(const value_type& value) {
    if (arena_ == nullptr) {
      return new value_type(value);
    } else {
      value_type* p = reinterpret_cast<value_type*>(
          Arena::CreateArray<uint8>(arena_, sizeof(value_type)));
      Arena::CreateInArenaStorage(const_cast<Key*>(&p->first), arena_,
                                  value.first);
      Arena::CreateInArenaStorage(&p->second, arena_);
      p->second = value.second;
      return p;
    }
  }

Arena* arena_;
  int default_enum_value_;
  InnerMap* elements_;

friend class Arena;
  using InternalArenaConstructable_ = void;
  using DestructorSkippable_ = void;
  template <typename Derived, typename K, typename V,
            internal::WireFormatLite::FieldType key_wire_type,
            internal::WireFormatLite::FieldType value_wire_type,
            int default_enum_value>
  friend class internal::MapFieldLite;
};

}  // namespace protobuf
}  // namespace google

#include <google/protobuf/port_undef.inc>

#endif  // GOOGLE_PROTOBUF_MAP_H__

cmd: