Lines Matching refs:tree
19 // tree using the bits of a hash value as addresses). The map is a conceptually
46 // their unsigned value. This way, the order in the hash tree is compatible
60 // the hash tree.
71 const FocusedTree* tree = FindHash(key_hash);
72 return GetFocusedValue(tree, key);
133 // Load value from the leaf node on the focused path of {tree}.
134 const Value& GetFocusedValue(const FocusedTree* tree, const Key& key) const;
137 // (bit==kRight) child of the node on the path of {tree} at tree level
139 static const FocusedTree* GetChild(const FocusedTree* tree, int level,
142 // Find the leftmost path in the tree, starting at the node at tree level
149 PersistentMap(const FocusedTree* tree, Zone* zone, Value def_value)
150 : tree_(tree), def_value_(def_value), zone_(zone) {}
157 // This structure represents a hash tree with one focused path to a specific
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
165 // right of the path. As there is no explicit representation of a tree node,
167 // depends on the tree depth, which is always clear from the referencing
170 // focused node of another {FocusedTree} always references to one tree level
293 static iterator begin(const FocusedTree* tree, Value def_value) {
295 i.current_ = FindLeftmost(tree, &i.level_, &i.path_);
398 FocusedTree* tree = new (zone_->Allocate<FocusedTree>(size))
405 tree->path(i) = path[i];
407 *this = PersistentMap(tree, zone_, def_value_);
413 const FocusedTree* tree = tree_;
415 while (tree && hash != tree->key_hash) {
416 while ((hash ^ tree->key_hash)[level] == 0) {
419 tree = level < tree->length ? tree->path(level) : nullptr;
422 return tree;
430 const FocusedTree* tree = tree_;
432 while (tree && hash != tree->key_hash) {
433 int map_length = tree->length;
434 while ((hash ^ tree->key_hash)[level] == 0) {
435 (*path)[level] = level < map_length ? tree->path(level) : nullptr;
438 (*path)[level] = tree;
439 tree = level < tree->length ? tree->path(level) : nullptr;
442 if (tree) {
443 while (level < tree->length) {
444 (*path)[level] = tree->path(level);
449 return tree;
454 const FocusedTree* tree, const Key& key) const {
455 if (!tree) {
458 if (tree->more) {
459 auto it = tree->more->find(key);
460 if (it == tree->more->end())
465 if (key == tree->key_value.key()) {
466 return tree->key_value.value();
475 PersistentMap<Key, Value, Hasher>::GetChild(const FocusedTree* tree, int level,
477 if (tree->key_hash[level] == bit) {
478 return tree;
479 } else if (level < tree->length) {
480 return tree->path(level);