persistent-map.h | Explore in Territory

// Copyright 2017 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_PERSISTENT_MAP_H_
#define V8_COMPILER_PERSISTENT_MAP_H_

#include <array>
#include <tuple>

#include "src/base/functional.h"
#include "src/zone/zone-containers.h"

namespace v8 {
namespace internal {
namespace compiler {

// A fast and possibly incomplete equality check. If it returns false, the
// values are certainly not equal, otherwise we do not know. The template is
// intended to be specialized for types with expensive equality checks.
template <class T>
struct may_be_unequal { … };

// PersistentMap is a persistent map datastructure based on hash trees (a binary
// tree using the bits of a hash value as addresses). The map is a conceptually
// infinite: All keys are initially mapped to a default value, values are
// deleted by overwriting them with the default value. The iterators produce
// exactly the keys that are not the default value. The hash values should have
// high variance in their high bits, so dense integers are a bad choice.
// Complexity:
// - Copy and assignment: O(1)
// - access: O(log n)
// - update: O(log n) time and space
// - iteration: amortized O(1) per step
// - Zip: O(n)
// - equality check: O(n)
// TODO(turbofan): Cache map transitions to avoid re-allocation of the same map.
// TODO(turbofan): Implement an O(1) equality check based on hash consing or
//              something similar.
template <class Key, class Value, class Hasher = base::hash<Key>>
class PersistentMap {
 public:
  using key_type = Key;
  using mapped_type = Value;
  using value_type = std::pair<Key, Value>;

 private:
  static constexpr size_t kHashBits = 32;
  enum Bit : int { kLeft = 0, kRight = 1 };

  // Access hash bits starting from the high bits and compare them according to
  // their unsigned value. This way, the order in the hash tree is compatible
  // with numeric hash comparisons.
  class HashValue;

  struct KeyValue : std::pair<Key, Value> {
    const Key& key() const { return this->first; }
    const Value& value() const { return this->second; }
    using std::pair<Key, Value>::pair;
  };

  struct FocusedTree;

  friend struct may_be_unequal<PersistentMap<Key, Value, Hasher>>;

 public:
  // Depth of the last added element. This is a cheap estimate for the size of
  // the hash tree.
  size_t last_depth() const { … }

  const Value& Get(const Key& key) const { … }

  // Add or overwrite an existing key-value pair.
  void Set(Key key, Value value);
  // Modify an entry in-place, avoiding repeated search.
  // `F` is a functional that expects a `Value*` parameter to modify it.
  template <class F>
  void Modify(Key key, F f);

  bool operator==(const PersistentMap& other) const { … }

  bool operator!=(const PersistentMap& other) const { … }

  // The iterator produces key-value pairs in the lexicographical order of
  // hash value and key. It produces exactly the key-value pairs where the value
  // is not the default value.
  class iterator;

  iterator begin() const { … }
  iterator end() const { … }

  // Iterator to traverse two maps in lockstep, producing matching value pairs
  // for each key where at least one value is different from the respective
  // default.
  class double_iterator;

  // An iterable to iterate over the two maps in lockstep.
  struct ZipIterable {
    PersistentMap a;
    PersistentMap b;
    double_iterator begin() { return double_iterator(a.begin(), b.begin()); }
    double_iterator end() { return double_iterator(a.end(), b.end()); }
  };

  ZipIterable Zip(const PersistentMap& other) const { … }

  explicit PersistentMap(Zone* zone, Value def_value = Value())
      : … { … }

 private:
  // Find the {FocusedTree} that contains a key-value pair with key hash {hash}.
  const FocusedTree* FindHash(HashValue hash) const;

  // Find the {FocusedTree} that contains a key-value pair with key hash {hash}.
  // Output the path to this {FocusedTree} and its length. If no such
  // {FocusedTree} exists, return {nullptr} and output the path to the last node
  // with a matching hash prefix. Note that {length} is the length of the found
  // path and may be less than the length of the found {FocusedTree}.
  const FocusedTree* FindHash(HashValue hash,
                              std::array<const FocusedTree*, kHashBits>* path,
                              int* length) const;

  // Load value from the leaf node on the focused path of {tree}.
  const Value& GetFocusedValue(const FocusedTree* tree, const Key& key) const;

  // Return the {FocusedTree} representing the left (bit==kLeft) or right
  // (bit==kRight) child of the node on the path of {tree} at tree level
  // {level}.
  static const FocusedTree* GetChild(const FocusedTree* tree, int level,
                                     Bit bit);

  // Find the leftmost path in the tree, starting at the node at tree level
  // {level} on the path of {start}. Output the level of the leaf to {level} and
  // the path to {path}.
  static const FocusedTree* FindLeftmost(
      const FocusedTree* start, int* level,
      std::array<const FocusedTree*, kHashBits>* path);

  PersistentMap(const FocusedTree* tree, Zone* zone, Value def_value)
      : … { … }

  const FocusedTree* tree_;
  Value def_value_;
  Zone* zone_;
};

may_be_unequal<PersistentMap<Key, Value, Hasher>>;

// This structure represents a hash tree with one focused path to a specific
// leaf. For the focused leaf, it stores key, value and key hash. The path is
// defined by the hash bits of the focused leaf. In a traditional tree
// datastructure, the nodes of a path form a linked list with the values being
// the pointers outside of this path. Instead of storing all of these nodes,
// we store an array of the pointers pointing outside of the path. This is
// similar to the stack used when doing DFS traversal of a tree. The hash of
// the leaf is used to know if the pointers point to the left or the
// right of the path. As there is no explicit representation of a tree node,
// this structure also represents all the nodes on its path. The intended node
// depends on the tree depth, which is always clear from the referencing
// context. So the pointer to a {FocusedTree} stored in the
// {PersistentMap.tree_} always references the root, while a pointer from a
// focused node of another {FocusedTree} always references to one tree level
// lower than before.
template <class Key, class Value, class Hasher>
struct PersistentMap<Key, Value, Hasher>::FocusedTree { … };

template <class Key, class Value, class Hasher>
class PersistentMap<Key, Value, Hasher>::HashValue { … };

template <class Key, class Value, class Hasher>
class PersistentMap<Key, Value, Hasher>::iterator { … };

template <class Key, class Value, class Hasher>
class PersistentMap<Key, Value, Hasher>::double_iterator { … };

template <class Key, class Value, class Hasher>
void PersistentMap<Key, Value, Hasher>::Set(Key key, Value new_value) { … }

template <class Key, class Value, class Hasher>
template <class F>
void PersistentMap<Key, Value, Hasher>::Modify(Key key, F f) { … }

template <class Key, class Value, class Hasher>
const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
PersistentMap<Key, Value, Hasher>::FindHash(HashValue hash) const { … }

template <class Key, class Value, class Hasher>
const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
PersistentMap<Key, Value, Hasher>::FindHash(
    HashValue hash, std::array<const FocusedTree*, kHashBits>* path,
    int* length) const { … }

template <class Key, class Value, class Hasher>
const Value& PersistentMap<Key, Value, Hasher>::GetFocusedValue(
    const FocusedTree* tree, const Key& key) const { … }

template <class Key, class Value, class Hasher>
const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
PersistentMap<Key, Value, Hasher>::GetChild(const FocusedTree* tree, int level,
                                            Bit bit) { … }

template <class Key, class Value, class Hasher>
const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
PersistentMap<Key, Value, Hasher>::FindLeftmost(
    const FocusedTree* start, int* level,
    std::array<const FocusedTree*, kHashBits>* path) { … }

template <class Key, class Value, class Hasher>
std::ostream& operator<<(std::ostream& os,
                         const PersistentMap<Key, Value, Hasher>& map) { … }

}  // namespace compiler
}  // namespace internal
}  // namespace v8

#endif  // V8_COMPILER_PERSISTENT_MAP_H_
chromium/v8/src/compiler/persistent-map.h
