Lines Matching refs:FocusedTree
56 struct FocusedTree;
71 const FocusedTree* tree = FindHash(key_hash);
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}.
125 // Output the path to this {FocusedTree} and its length. If no such
126 // {FocusedTree} exists, return {nullptr} and output the path to the last node
128 // path and may be less than the length of the found {FocusedTree}.
129 const FocusedTree* FindHash(HashValue hash,
130 std::array<const FocusedTree*, kHashBits>* path,
134 const Value& GetFocusedValue(const FocusedTree* tree, const Key& key) const;
136 // Return the {FocusedTree} representing the left (bit==kLeft) or right
139 static const FocusedTree* GetChild(const FocusedTree* tree, int level,
145 static const FocusedTree* FindLeftmost(
146 const FocusedTree* start, int* level,
147 std::array<const FocusedTree*, kHashBits>* path);
149 PersistentMap(const FocusedTree* tree, Zone* zone, Value def_value)
152 const FocusedTree* tree_;
168 // context. So the pointer to a {FocusedTree} stored in the
170 // focused node of another {FocusedTree} always references to one tree level
173 struct PersistentMap<Key, Value, Hasher>::FocusedTree {
186 const FocusedTree* path_array[1];
187 const FocusedTree*& path(int i) {
189 return reinterpret_cast<const FocusedTree**>(
190 reinterpret_cast<byte*>(this) + offsetof(FocusedTree, path_array))[i];
192 const FocusedTree* path(int i) const {
194 return reinterpret_cast<const FocusedTree* const*>(
196 offsetof(FocusedTree, path_array))[i];
258 const FocusedTree* first_right_alternative = path_[level_];
293 static iterator begin(const FocusedTree* tree, Value def_value) {
309 typename FocusedTree::more_iterator more_iter_;
310 const FocusedTree* current_;
311 std::array<const FocusedTree*, kHashBits> path_;
380 std::array<const FocusedTree*, kHashBits> path;
382 const FocusedTree* old = FindHash(key_hash, &path, &length);
396 size_t size = sizeof(FocusedTree) +
397 std::max(0, length - 1) * sizeof(const FocusedTree*);
398 FocusedTree* tree = new (zone_->Allocate<FocusedTree>(size))
399 FocusedTree{KeyValue(std::move(key), std::move(value)),
411 const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
413 const FocusedTree* tree = tree_;
426 const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
428 HashValue hash, std::array<const FocusedTree*, kHashBits>* path,
430 const FocusedTree* tree = tree_;
454 const FocusedTree* tree, const Key& key) const {
474 const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
475 PersistentMap<Key, Value, Hasher>::GetChild(const FocusedTree* tree, int level,
487 const typename PersistentMap<Key, Value, Hasher>::FocusedTree*
489 const FocusedTree* start, int* level,
490 std::array<const FocusedTree*, kHashBits>* path) {
491 const FocusedTree* current = start;
493 if (const FocusedTree* left_child = GetChild(current, *level, kLeft)) {
497 } else if (const FocusedTree* right_child =