class KeyMapBase

template <typename Key>

class KeyMapBase

Defined at line 724 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

KeyMapBase is a chaining hash map.

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 number of buckets is a power of two.

2. 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.

3. Mutations to a map do not invalidate the map's iterators, pointers to

elements, or references to elements.

4. Except for erase(iterator), any non-const method can reorder iterators.

Protected Methods

Key * GetKey (NodeBase * node)

Defined at line 744 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

size_type EraseImpl (Arena * arena, map_index_t b, KeyNode * node, bool do_destroy)

Defined at line 748 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

size_type EraseImpl (Arena * arena, typename TS::ViewType k)

Defined at line 782 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

NodeAndBucket FindHelper (typename TS::ViewType k)

Defined at line 790 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

bool InsertOrReplaceNode (Arena * arena, KeyNode * node)

Insert the given node.

If the key is a duplicate, it inserts the new node and deletes the old one.

Defined at line 803 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

void InsertOrReplaceNodes (Arena * arena, KeyNode * list, map_index_t count)

Insert the given nodes.

On duplicates we discard the previous values.

Defined at line 823 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

void InsertUnique (map_index_t b, KeyNode * node)

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.

Requires count(*KeyPtrFromNodePtr(node)) == 0 and that b is the correct

bucket. num_elements_ is not modified.

Defined at line 871 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

size_type CalculateHiCutoff (size_type num_buckets)

Have it a separate function for testing.

Defined at line 892 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

size_type CalculateCapacityForSize (size_type size)

For a particular size, calculate the lowest capacity `cap` where

`size

<

= CalculateHiCutoff(cap)`.

Defined at line 905 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

void AssertLoadFactor ()

Defined at line 922 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

bool ResizeIfLoadIsOutOfRange (Arena * arena, size_type new_size)

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.

Defined at line 934 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

void ResizeIfLoadIsOutOfRangeForMultiInsert (Arena * arena, size_type new_size)

Defined at line 970 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

void MergeIntoEmpty (Arena * arena, NodeBase * head, size_t num_nodes)

Interpret `head` as a linked list and insert all the nodes into `this`.

REQUIRES: this->empty()

REQUIRES: the input nodes have unique keys

Defined at line 981 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

void Resize (Arena * arena, map_index_t new_num_buckets)

Resize to the given number of buckets.

Defined at line 1001 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

map_index_t BucketNumber (typename TS::ViewType k)

Defined at line 1065 of file ../../third_party/protobuf/src/src/google/protobuf/map.h

Records

Friends

template <typename Key>
class RustMapHelper
template <typename Key>
class MapBenchmarkPeer
template <typename Key>
class MapTestPeer
template <typename Key>
class TcParser
template <typename Key>
class MapFieldBase
template <typename Key>
class UntypedMapBase