// 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 {
|
|
// 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(tebbi): Cache map transitions to avoid re-allocation of the same map.
|
// TODO(tebbi): 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;
|
|
public:
|
// Depth of the last added element. This is a cheap estimate for the size of
|
// the hash tree.
|
size_t last_depth() const {
|
if (tree_) {
|
return tree_->length;
|
} else {
|
return 0;
|
}
|
}
|
|
const Value& Get(const Key& key) const {
|
HashValue key_hash = HashValue(Hasher()(key));
|
const FocusedTree* tree = FindHash(key_hash);
|
return GetFocusedValue(tree, key);
|
}
|
|
// Add or overwrite an existing key-value pair.
|
void Set(Key key, Value value);
|
|
bool operator==(const PersistentMap& other) const {
|
if (tree_ == other.tree_) return true;
|
if (def_value_ != other.def_value_) return false;
|
for (const std::tuple<Key, Value, Value>& triple : Zip(other)) {
|
if (std::get<1>(triple) != std::get<2>(triple)) return false;
|
}
|
return true;
|
}
|
|
bool operator!=(const PersistentMap& other) const {
|
return !(*this == other);
|
}
|
|
// 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 {
|
if (!tree_) return end();
|
return iterator::begin(tree_, def_value_);
|
}
|
iterator end() const { return iterator::end(def_value_); }
|
|
// 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 { return {*this, other}; }
|
|
explicit PersistentMap(Zone* zone, Value def_value = Value())
|
: PersistentMap(nullptr, zone, def_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)
|
: tree_(tree), def_value_(def_value), zone_(zone) {}
|
|
const FocusedTree* tree_;
|
Value def_value_;
|
Zone* zone_;
|
};
|
|
// 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 {
|
KeyValue key_value;
|
// The depth of the focused path, that is, the number of pointers stored in
|
// this structure.
|
int8_t length;
|
HashValue key_hash;
|
// Out-of-line storage for hash collisions.
|
const ZoneMap<Key, Value>* more;
|
using more_iterator = typename ZoneMap<Key, Value>::const_iterator;
|
// {path_array} has to be the last member: To store an array inline, we
|
// over-allocate memory for this structure and access memory beyond
|
// {path_array}. This corresponds to a flexible array member as defined in
|
// C99.
|
const FocusedTree* path_array[1];
|
const FocusedTree*& path(int i) {
|
DCHECK(i < length);
|
return reinterpret_cast<const FocusedTree**>(
|
reinterpret_cast<byte*>(this) + offsetof(FocusedTree, path_array))[i];
|
}
|
const FocusedTree* path(int i) const {
|
DCHECK(i < length);
|
return reinterpret_cast<const FocusedTree* const*>(
|
reinterpret_cast<const byte*>(this) +
|
offsetof(FocusedTree, path_array))[i];
|
}
|
};
|
|
template <class Key, class Value, class Hasher>
|
class PersistentMap<Key, Value, Hasher>::HashValue {
|
public:
|
explicit HashValue(size_t hash) : bits_(static_cast<uint32_t>(hash)) {}
|
|
Bit operator[](int pos) const {
|
DCHECK_LT(pos, kHashBits);
|
return bits_ & (static_cast<decltype(bits_)>(1) << (kHashBits - pos - 1))
|
? kRight
|
: kLeft;
|
}
|
|
bool operator<(HashValue other) const { return bits_ < other.bits_; }
|
bool operator==(HashValue other) const { return bits_ == other.bits_; }
|
bool operator!=(HashValue other) const { return bits_ != other.bits_; }
|
HashValue operator^(HashValue other) const {
|
return HashValue(bits_ ^ other.bits_);
|
}
|
|
private:
|
static_assert(sizeof(uint32_t) * 8 == kHashBits, "wrong type for bits_");
|
uint32_t bits_;
|
};
|
|
template <class Key, class Value, class Hasher>
|
class PersistentMap<Key, Value, Hasher>::iterator {
|
public:
|
const value_type operator*() const {
|
if (current_->more) {
|
return *more_iter_;
|
} else {
|
return current_->key_value;
|
}
|
}
|
|
iterator& operator++() {
|
do {
|
if (!current_) {
|
// Iterator is past the end.
|
return *this;
|
}
|
if (current_->more) {
|
DCHECK(more_iter_ != current_->more->end());
|
++more_iter_;
|
if (more_iter_ != current_->more->end()) return *this;
|
}
|
if (level_ == 0) {
|
*this = end(def_value_);
|
return *this;
|
}
|
--level_;
|
while (current_->key_hash[level_] == kRight || path_[level_] == nullptr) {
|
if (level_ == 0) {
|
*this = end(def_value_);
|
return *this;
|
}
|
--level_;
|
}
|
const FocusedTree* first_right_alternative = path_[level_];
|
level_++;
|
current_ = FindLeftmost(first_right_alternative, &level_, &path_);
|
if (current_->more) {
|
more_iter_ = current_->more->begin();
|
}
|
} while (!((**this).second != def_value()));
|
return *this;
|
}
|
|
bool operator==(const iterator& other) const {
|
if (is_end()) return other.is_end();
|
if (other.is_end()) return false;
|
if (current_->key_hash != other.current_->key_hash) {
|
return false;
|
} else {
|
return (**this).first == (*other).first;
|
}
|
}
|
bool operator!=(const iterator& other) const { return !(*this == other); }
|
|
bool operator<(const iterator& other) const {
|
if (is_end()) return false;
|
if (other.is_end()) return true;
|
if (current_->key_hash == other.current_->key_hash) {
|
return (**this).first < (*other).first;
|
} else {
|
return current_->key_hash < other.current_->key_hash;
|
}
|
}
|
|
bool is_end() const { return current_ == nullptr; }
|
|
const Value& def_value() { return def_value_; }
|
|
static iterator begin(const FocusedTree* tree, Value def_value) {
|
iterator i(def_value);
|
i.current_ = FindLeftmost(tree, &i.level_, &i.path_);
|
if (i.current_->more) {
|
i.more_iter_ = i.current_->more->begin();
|
}
|
// Skip entries with default value. PersistentMap iterators must never point
|
// to a default value.
|
while (!i.is_end() && !((*i).second != def_value)) ++i;
|
return i;
|
}
|
|
static iterator end(Value def_value) { return iterator(def_value); }
|
|
private:
|
int level_;
|
typename FocusedTree::more_iterator more_iter_;
|
const FocusedTree* current_;
|
std::array<const FocusedTree*, kHashBits> path_;
|
Value def_value_;
|
|
explicit iterator(Value def_value)
|
: level_(0), current_(nullptr), def_value_(def_value) {}
|
};
|
|
template <class Key, class Value, class Hasher>
|
class PersistentMap<Key, Value, Hasher>::double_iterator {
|
public:
|
std::tuple<Key, Value, Value> operator*() {
|
if (first_current_) {
|
auto pair = *first_;
|
return std::make_tuple(
|
pair.first, pair.second,
|
second_current_ ? (*second_).second : second_.def_value());
|
} else {
|
DCHECK(second_current_);
|
auto pair = *second_;
|
return std::make_tuple(pair.first, first_.def_value(), pair.second);
|
}
|
}
|
|
double_iterator& operator++() {
|
#ifdef DEBUG
|
iterator old_first = first_;
|
iterator old_second = second_;
|
#endif
|
if (first_current_) {
|
++first_;
|
DCHECK(old_first < first_);
|
}
|
if (second_current_) {
|
++second_;
|
DCHECK(old_second < second_);
|
}
|
return *this = double_iterator(first_, second_);
|
}
|
|
double_iterator(iterator first, iterator second)
|
: first_(first), second_(second) {
|
if (first_ == second_) {
|
first_current_ = second_current_ = true;
|
} else if (first_ < second_) {
|
first_current_ = true;
|
second_current_ = false;
|
} else {
|
DCHECK(second_ < first_);
|
first_current_ = false;
|
second_current_ = true;
|
}
|
}
|
|
bool operator!=(const double_iterator& other) {
|
return first_ != other.first_ || second_ != other.second_;
|
}
|
|
bool is_end() const { return first_.is_end() && second_.is_end(); }
|
|
private:
|
iterator first_;
|
iterator second_;
|
bool first_current_;
|
bool second_current_;
|
};
|
|
template <class Key, class Value, class Hasher>
|
void PersistentMap<Key, Value, Hasher>::Set(Key key, Value value) {
|
HashValue key_hash = HashValue(Hasher()(key));
|
std::array<const FocusedTree*, kHashBits> path;
|
int length = 0;
|
const FocusedTree* old = FindHash(key_hash, &path, &length);
|
ZoneMap<Key, Value>* more = nullptr;
|
if (!(GetFocusedValue(old, key) != value)) return;
|
if (old && !(old->more == nullptr && old->key_value.key() == key)) {
|
more = new (zone_->New(sizeof(*more))) ZoneMap<Key, Value>(zone_);
|
if (old->more) {
|
*more = *old->more;
|
} else {
|
(*more)[old->key_value.key()] = old->key_value.value();
|
}
|
(*more)[key] = value;
|
}
|
FocusedTree* tree =
|
new (zone_->New(sizeof(FocusedTree) +
|
std::max(0, length - 1) * sizeof(const FocusedTree*)))
|
FocusedTree{KeyValue(std::move(key), std::move(value)),
|
static_cast<int8_t>(length),
|
key_hash,
|
more,
|
{}};
|
for (int i = 0; i < length; ++i) {
|
tree->path(i) = path[i];
|
}
|
*this = PersistentMap(tree, zone_, def_value_);
|
}
|
|
template <class Key, class Value, class Hasher>
|
const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
|
PersistentMap<Key, Value, Hasher>::FindHash(HashValue hash) const {
|
const FocusedTree* tree = tree_;
|
int level = 0;
|
while (tree && hash != tree->key_hash) {
|
while ((hash ^ tree->key_hash)[level] == 0) {
|
++level;
|
}
|
tree = level < tree->length ? tree->path(level) : nullptr;
|
++level;
|
}
|
return tree;
|
}
|
|
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 {
|
const FocusedTree* tree = tree_;
|
int level = 0;
|
while (tree && hash != tree->key_hash) {
|
int map_length = tree->length;
|
while ((hash ^ tree->key_hash)[level] == 0) {
|
(*path)[level] = level < map_length ? tree->path(level) : nullptr;
|
++level;
|
}
|
(*path)[level] = tree;
|
tree = level < tree->length ? tree->path(level) : nullptr;
|
++level;
|
}
|
if (tree) {
|
while (level < tree->length) {
|
(*path)[level] = tree->path(level);
|
++level;
|
}
|
}
|
*length = level;
|
return tree;
|
}
|
|
template <class Key, class Value, class Hasher>
|
const Value& PersistentMap<Key, Value, Hasher>::GetFocusedValue(
|
const FocusedTree* tree, const Key& key) const {
|
if (!tree) {
|
return def_value_;
|
}
|
if (tree->more) {
|
auto it = tree->more->find(key);
|
if (it == tree->more->end())
|
return def_value_;
|
else
|
return it->second;
|
} else {
|
if (key == tree->key_value.key()) {
|
return tree->key_value.value();
|
} else {
|
return def_value_;
|
}
|
}
|
}
|
|
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) {
|
if (tree->key_hash[level] == bit) {
|
return tree;
|
} else if (level < tree->length) {
|
return tree->path(level);
|
} else {
|
return nullptr;
|
}
|
}
|
|
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) {
|
const FocusedTree* current = start;
|
while (*level < current->length) {
|
if (const FocusedTree* child = GetChild(current, *level, kLeft)) {
|
(*path)[*level] = GetChild(current, *level, kRight);
|
current = child;
|
++*level;
|
} else if (const FocusedTree* child = GetChild(current, *level, kRight)) {
|
(*path)[*level] = GetChild(current, *level, kLeft);
|
current = child;
|
++*level;
|
} else {
|
UNREACHABLE();
|
}
|
}
|
return current;
|
}
|
|
template <class Key, class Value, class Hasher>
|
std::ostream& operator<<(std::ostream& os,
|
const PersistentMap<Key, Value, Hasher>& map) {
|
os << "{";
|
bool first = true;
|
for (auto pair : map) {
|
if (!first) os << ", ";
|
first = false;
|
os << pair.first << ": " << pair.second;
|
}
|
return os << "}";
|
}
|
|
} // namespace compiler
|
} // namespace internal
|
} // namespace v8
|
|
#endif // V8_COMPILER_PERSISTENT_MAP_H_
|
