layered-hash-map.h | Explore in Territory

// Copyright 2022 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_COMPILER_TURBOSHAFT_LAYERED_HASH_MAP_H_
#define V8_COMPILER_TURBOSHAFT_LAYERED_HASH_MAP_H_

#include <cstddef>
#include <iostream>
#include <limits>
#include <optional>

#include "src/base/bits.h"
#include "src/compiler/turboshaft/fast-hash.h"
#include "src/zone/zone-containers.h"

namespace v8::internal::compiler::turboshaft {

// LayeredHashMap is a hash map whose elements are groupped into layers, such
// that it's efficient to remove all of the items from the last inserted layer.
// In addition to the regular Insert/Get/Contains functions of hash maps, it
// thus provides two additional functions: StartLayer to indicate that future
// insertions are part of a new layer, and DropLastLayer to remove all of the
// items of the last layer.
//
// LayeredHashMap does not support inserting multiple values with the same key,
// and does not support updating already-inserted items in the map. If you need
// to update an existing key, you'll need to remove it (by calling DropLastLayer
// as many times as needed), and then re-insert it.
//
// The implementation uses a regular ZoneVector for the main hash table, while
// keeping a linked list of items per layer. When inserting an item in the
// LayeredHashMap, we insert it into the ZoneVector and link it to the linked
// list of the current (=latest) layer. In order to remove all of the items from
// the last layer, we iterate its linked list, and remove the items one by one
// from the ZoneVector, after which we drop the linked list alltogether.

template <class Key, class Value>
class LayeredHashMap { … };

template <class Key, class Value>
LayeredHashMap<Key, Value>::LayeredHashMap(Zone* zone,
                                           uint32_t initial_capacity)
    : … { … }

template <class Key, class Value>
void LayeredHashMap<Key, Value>::StartLayer() { … }

template <class Key, class Value>
void LayeredHashMap<Key, Value>::DropLastLayer() { … }

template <class Key, class Value>
typename LayeredHashMap<Key, Value>::Entry*
LayeredHashMap<Key, Value>::FindEntryForKey(Key key, size_t hash) { … }

template <class Key, class Value>
void LayeredHashMap<Key, Value>::InsertNewKey(Key key, Value value) { … }

template <class Key, class Value>
std::optional<Value> LayeredHashMap<Key, Value>::Get(Key key) { … }

template <class Key, class Value>
bool LayeredHashMap<Key, Value>::Contains(Key key) { … }

template <class Key, class Value>
void LayeredHashMap<Key, Value>::ResizeIfNeeded() { … }

}  // namespace v8::internal::compiler::turboshaft

#endif  // V8_COMPILER_TURBOSHAFT_LAYERED_HASH_MAP_H_
chromium/v8/src/compiler/turboshaft/layered-hash-map.h
