Lines Matching defs:hash
18 // PersistentMap is a persistent map datastructure based on hash trees (a binary
19 // tree using the bits of a hash value as addresses). The map is a conceptually
22 // exactly the keys that are not the default value. The hash values should have
32 // TODO(turbofan): Implement an O(1) equality check based on hash consing or
34 template <class Key, class Value, class Hasher = base::hash<Key>>
45 // Access hash bits starting from the high bits and compare them according to
46 // their unsigned value. This way, the order in the hash tree is compatible
47 // with numeric hash comparisons.
60 // the hash tree.
92 // hash value and key. It produces exactly the key-value pairs where the value
121 // Find the {FocusedTree} that contains a key-value pair with key hash {hash}.
122 const FocusedTree* FindHash(HashValue hash) const;
124 // Find the {FocusedTree} that contains a key-value pair with key hash {hash}.
127 // with a matching hash prefix. Note that {length} is the length of the found
129 const FocusedTree* FindHash(HashValue hash,
157 // This structure represents a hash tree with one focused path to a specific
158 // leaf. For the focused leaf, it stores key, value and key hash. The path is
159 // defined by the hash bits of the focused leaf. In a traditional tree
163 // similar to the stack used when doing DFS traversal of a tree. The hash of
179 // Out-of-line storage for hash collisions.
203 explicit HashValue(size_t hash) : bits_(static_cast<uint32_t>(hash)) {}
412 PersistentMap<Key, Value, Hasher>::FindHash(HashValue hash) const {
415 while (tree && hash != tree->key_hash) {
416 while ((hash ^ tree->key_hash)[level] == 0) {
428 HashValue hash, std::array<const FocusedTree*, kHashBits>* path,
432 while (tree && hash != tree->key_hash) {
434 while ((hash ^ tree->key_hash)[level] == 0) {