template <typename Key>

class KeyMapBase

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

KeyMapBase 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 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. The trees' payload type is pointer to linked-list node. Tree-converting

a bucket doesn't copy Key-Value pairs.

4. Once we've tree-converted a bucket, it is never converted back unless the

bucket is completely emptied out. Note that the items a tree contains may

wind up assigned to trees or lists upon a rehash.

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

elements, or references to elements.

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

7. Uses VariantKey when using the Tree representation, which holds all

possible key types as a variant value.

Public Methods

hasher hash_function ()

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

Protected Methods

void erase_no_destroy (map_index_t b, KeyNode * node)

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

NodeAndBucket FindHelper (typename TS::ViewType k, TreeIterator * it)

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

KeyNode * InsertOrReplaceNode (KeyNode * node)

Insert the given node.

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

Gives ownership to the caller.

If the key is unique, it returns `nullptr`.

Defined at line 994 of file ../../third_party/protobuf/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 1013 of file ../../third_party/protobuf/src/google/protobuf/map.h

VariantKey NodeToVariantKey (NodeBase * node)

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

size_type CalculateHiCutoff (size_type num_buckets)

Have it a separate function for testing.

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

bool ResizeIfLoadIsOutOfRange (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 1056 of file ../../third_party/protobuf/src/google/protobuf/map.h

void Resize (map_index_t new_num_buckets)

Resize to the given number of buckets.

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

void TransferList (KeyNode * node)

Transfer all nodes in the list `node` into `this`.

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

map_index_t BucketNumber (typename TS::ViewType k)

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

bool revalidate_if_necessary (map_index_t & bucket_index, KeyNode * node, TreeIterator * it)

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

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

Friends

template <typename Key>

class RustMapHelper

template <typename Key>

class MapBenchmarkPeer

template <typename Key>

class MapTestPeer

template <typename Key>

class TcParser