From 135adfcd6a0593218daec2657603f61ae49c6130 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 1 Mar 2023 08:33:26 -0700 Subject: btrfstree: Fix comments --- lib/btrfs/btrfstree/btree_tree.go | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) (limited to 'lib/btrfs/btrfstree/btree_tree.go') diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index b01312f..a39a795 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -37,7 +37,7 @@ type TreeOperator interface { // 002 (read node) // 003 .Node() (or .BadNode()) // for item in node.items: - // if btrfsprim: + // if internal: // 004 .PreKeyPointer() // 005 (recurse) // 006 .PostKeyPointer() @@ -68,7 +68,7 @@ type TreeWalkHandler struct { Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - // Callbacks for items on btrfsprim nodes + // Callbacks for items on internal nodes PreKeyPointer func(TreePath, KeyPointer) error PostKeyPointer func(TreePath, KeyPointer) error // Callbacks for items on leaf nodes @@ -96,7 +96,7 @@ type TreeOperatorImpl struct { NodeSource } -// TreeWalk implements the 'Trees' interface. +// TreeWalk implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, errHandle func(*TreeError), cbs TreeWalkHandler) { sb, err := fs.Superblock() if err != nil { @@ -110,8 +110,8 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, fs.RawTreeWalk(ctx, *rootInfo, errHandle, cbs) } -// TreeWalk is a utility method to help with implementing the 'Trees'. -// interface. +// RawTreeWalk is a utility method to help with implementing the +// 'TreeOperator' interface. func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { path := TreePath{{ FromTree: rootInfo.TreeID, @@ -261,7 +261,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } if node.Data.Head.Level > 0 { - // btrfsprim node + // internal node // Search for the right-most node.Data.BodyInternal item for which // `fn(item.Key) >= 0`. @@ -476,7 +476,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical return path, node, nil } -// TreeSearch implements the 'Trees' interface. +// TreeSearch implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) (Item, error) { sb, err := fs.Superblock() if err != nil { @@ -503,7 +503,7 @@ func KeySearch(fn func(btrfsprim.Key) int) func(btrfsprim.Key, uint32) int { } } -// TreeLookup implements the 'Trees' interface. +// TreeLookup implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) (Item, error) { item, err := fs.TreeSearch(treeID, KeySearch(key.Compare)) if err != nil { @@ -512,7 +512,7 @@ func (fs TreeOperatorImpl) TreeLookup(treeID btrfsprim.ObjID, key btrfsprim.Key) return item, err } -// TreeSearchAll implements the 'Trees' interface. +// TreeSearchAll implements the 'TreeOperator' interface. func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfsprim.Key, uint32) int) ([]Item, error) { sb, err := fs.Superblock() if err != nil { -- cgit v1.2.3-2-g168b From 7349ff1a01b29eae7f7e769fe44548f09c253d2b Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Thu, 2 Mar 2023 17:25:49 -0700 Subject: tree-wide: Have "interior" rather than "internal" be the antonym of "leaf" Because "internal" has a meaning in the Go world, and it's confusing. --- lib/btrfs/btrfstree/btree_tree.go | 52 +++++++++++++++++++-------------------- 1 file changed, 26 insertions(+), 26 deletions(-) (limited to 'lib/btrfs/btrfstree/btree_tree.go') diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index a39a795..f88dd44 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -37,7 +37,7 @@ type TreeOperator interface { // 002 (read node) // 003 .Node() (or .BadNode()) // for item in node.items: - // if internal: + // if interior: // 004 .PreKeyPointer() // 005 (recurse) // 006 .PostKeyPointer() @@ -68,7 +68,7 @@ type TreeWalkHandler struct { Node func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error BadNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) error PostNode func(TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node]) error - // Callbacks for items on internal nodes + // Callbacks for items on interior nodes PreKeyPointer func(TreePath, KeyPointer) error PostKeyPointer func(TreePath, KeyPointer) error // Callbacks for items on leaf nodes @@ -169,10 +169,10 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl return } if node != nil { - for i, item := range node.Data.BodyInternal { + for i, item := range node.Data.BodyInterior { toMaxKey := path.Node(-1).ToMaxKey - if i+1 < len(node.Data.BodyInternal) { - toMaxKey = node.Data.BodyInternal[i+1].Key.Mm() + if i+1 < len(node.Data.BodyInterior) { + toMaxKey = node.Data.BodyInterior[i+1].Key.Mm() } itemPath := append(path, TreePathElem{ FromTree: node.Data.Head.Owner, @@ -261,9 +261,9 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } if node.Data.Head.Level > 0 { - // internal node + // interior node - // Search for the right-most node.Data.BodyInternal item for which + // Search for the right-most node.Data.BodyInterior item for which // `fn(item.Key) >= 0`. // // + + + + 0 - - - - @@ -271,7 +271,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, // There may or may not be a value that returns '0'. // // i.e. find the highest value that isn't too high. - lastGood, ok := slices.SearchHighest(node.Data.BodyInternal, func(kp KeyPointer) int { + lastGood, ok := slices.SearchHighest(node.Data.BodyInterior, func(kp KeyPointer) int { return slices.Min(fn(kp.Key, math.MaxUint32), 0) // don't return >0; a key can't be "too low" }) if !ok { @@ -279,16 +279,16 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, return nil, nil, iofs.ErrNotExist } toMaxKey := path.Node(-1).ToMaxKey - if lastGood+1 < len(node.Data.BodyInternal) { - toMaxKey = node.Data.BodyInternal[lastGood+1].Key.Mm() + if lastGood+1 < len(node.Data.BodyInterior) { + toMaxKey = node.Data.BodyInterior[lastGood+1].Key.Mm() } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: lastGood, - ToNodeAddr: node.Data.BodyInternal[lastGood].BlockPtr, - ToNodeGeneration: node.Data.BodyInternal[lastGood].Generation, + ToNodeAddr: node.Data.BodyInterior[lastGood].BlockPtr, + ToNodeGeneration: node.Data.BodyInterior[lastGood].Generation, ToNodeLevel: node.Data.Head.Level - 1, - ToKey: node.Data.BodyInternal[lastGood].Key, + ToKey: node.Data.BodyInterior[lastGood].Key, ToMaxKey: toMaxKey, }) FreeNodeRef(node) @@ -344,7 +344,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr } } // go down @@ -360,11 +360,11 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical if node.Data.Head.Level > 0 { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyInternal) - 1, - ToNodeAddr: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].BlockPtr, - ToNodeGeneration: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Generation, + FromItemIdx: len(node.Data.BodyInterior) - 1, + ToNodeAddr: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].BlockPtr, + ToNodeGeneration: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Generation, ToNodeLevel: node.Data.Head.Level - 1, - ToKey: node.Data.BodyInternal[len(node.Data.BodyInternal)-1].Key, + ToKey: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Key, ToMaxKey: path.Node(-1).ToMaxKey, }) } else { @@ -427,7 +427,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInternal[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr } } // go down @@ -443,24 +443,24 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } if node.Data.Head.Level > 0 { toMaxKey := path.Node(-1).ToMaxKey - if len(node.Data.BodyInternal) > 1 { - toMaxKey = node.Data.BodyInternal[1].Key.Mm() + if len(node.Data.BodyInterior) > 1 { + toMaxKey = node.Data.BodyInterior[1].Key.Mm() } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: 0, - ToNodeAddr: node.Data.BodyInternal[0].BlockPtr, - ToNodeGeneration: node.Data.BodyInternal[0].Generation, + ToNodeAddr: node.Data.BodyInterior[0].BlockPtr, + ToNodeGeneration: node.Data.BodyInterior[0].Generation, ToNodeLevel: node.Data.Head.Level - 1, - ToKey: node.Data.BodyInternal[0].Key, + ToKey: node.Data.BodyInterior[0].Key, ToMaxKey: toMaxKey, }) } else { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, FromItemIdx: 0, - ToKey: node.Data.BodyInternal[0].Key, - ToMaxKey: node.Data.BodyInternal[0].Key, + ToKey: node.Data.BodyInterior[0].Key, + ToMaxKey: node.Data.BodyInterior[0].Key, }) } } -- cgit v1.2.3-2-g168b From 2c2d616b8650dd01818bd29e11e7b06ae2de5891 Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Sat, 4 Mar 2023 09:51:34 -0700 Subject: tree-wide: Refer to item "slots" rather than "indexes" --- lib/btrfs/btrfstree/btree_tree.go | 66 +++++++++++++++++++-------------------- 1 file changed, 33 insertions(+), 33 deletions(-) (limited to 'lib/btrfs/btrfstree/btree_tree.go') diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go index f88dd44..e75eb0b 100644 --- a/lib/btrfs/btrfstree/btree_tree.go +++ b/lib/btrfs/btrfstree/btree_tree.go @@ -115,7 +115,7 @@ func (fs TreeOperatorImpl) TreeWalk(ctx context.Context, treeID btrfsprim.ObjID, func (fs TreeOperatorImpl) RawTreeWalk(ctx context.Context, rootInfo TreeRoot, errHandle func(*TreeError), cbs TreeWalkHandler) { path := TreePath{{ FromTree: rootInfo.TreeID, - FromItemIdx: -1, + FromItemSlot: -1, ToNodeAddr: rootInfo.RootNode, ToNodeGeneration: rootInfo.Generation, ToNodeLevel: rootInfo.Level, @@ -176,7 +176,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl } itemPath := append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: i, + FromItemSlot: i, ToNodeAddr: item.BlockPtr, ToNodeGeneration: item.Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -203,10 +203,10 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl } for i, item := range node.Data.BodyLeaf { itemPath := append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: i, - ToKey: item.Key, - ToMaxKey: item.Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: i, + ToKey: item.Key, + ToMaxKey: item.Key, }) if errBody, isErr := item.Body.(*btrfsitem.Error); isErr { if cbs.BadItem == nil { @@ -244,7 +244,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) { path := TreePath{{ FromTree: treeRoot.TreeID, - FromItemIdx: -1, + FromItemSlot: -1, ToNodeAddr: treeRoot.RootNode, ToNodeGeneration: treeRoot.Generation, ToNodeLevel: treeRoot.Level, @@ -284,7 +284,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: lastGood, + FromItemSlot: lastGood, ToNodeAddr: node.Data.BodyInterior[lastGood].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[lastGood].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -305,7 +305,7 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, // is returned. // // Implement this search as a binary search. - idx, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { + slot, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int { return fn(item.Key, item.BodySize) }) if !ok { @@ -313,10 +313,10 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, return nil, nil, iofs.ErrNotExist } path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: idx, - ToKey: node.Data.BodyLeaf[idx].Key, - ToMaxKey: node.Data.BodyLeaf[idx].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: slot, + ToKey: node.Data.BodyLeaf[slot].Key, + ToMaxKey: node.Data.BodyLeaf[slot].Key, }) return path, node, nil } @@ -328,14 +328,14 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical path = path.DeepCopy() // go up - for path.Node(-1).FromItemIdx < 1 { + for path.Node(-1).FromItemSlot < 1 { path = path.Parent() if len(path) == 0 { return nil, nil, nil } } // go left - path.Node(-1).FromItemIdx-- + path.Node(-1).FromItemSlot-- if path.Node(-1).ToNodeAddr != 0 { if node.Addr != path.Node(-2).ToNodeAddr { FreeNodeRef(node) @@ -344,7 +344,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr } } // go down @@ -360,7 +360,7 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical if node.Data.Head.Level > 0 { path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyInterior) - 1, + FromItemSlot: len(node.Data.BodyInterior) - 1, ToNodeAddr: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -369,10 +369,10 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical }) } else { path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: len(node.Data.BodyLeaf) - 1, - ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, - ToMaxKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: len(node.Data.BodyLeaf) - 1, + ToKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, + ToMaxKey: node.Data.BodyLeaf[len(node.Data.BodyLeaf)-1].Key, }) } } @@ -402,7 +402,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } path.Node(-2).ToNodeLevel = node.Data.Head.Level } - for path.Node(-1).FromItemIdx+1 >= int(node.Data.Head.NumItems) { + for path.Node(-1).FromItemSlot+1 >= int(node.Data.Head.NumItems) { path = path.Parent() if len(path) == 1 { return nil, nil, nil @@ -418,7 +418,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } } // go right - path.Node(-1).FromItemIdx++ + path.Node(-1).FromItemSlot++ if path.Node(-1).ToNodeAddr != 0 { if node.Addr != path.Node(-2).ToNodeAddr { FreeNodeRef(node) @@ -427,7 +427,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical FreeNodeRef(node) return nil, nil, err } - path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemIdx].BlockPtr + path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr } } // go down @@ -448,7 +448,7 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical } path = append(path, TreePathElem{ FromTree: node.Data.Head.Owner, - FromItemIdx: 0, + FromItemSlot: 0, ToNodeAddr: node.Data.BodyInterior[0].BlockPtr, ToNodeGeneration: node.Data.BodyInterior[0].Generation, ToNodeLevel: node.Data.Head.Level - 1, @@ -457,10 +457,10 @@ func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.Logical }) } else { path = append(path, TreePathElem{ - FromTree: node.Data.Head.Owner, - FromItemIdx: 0, - ToKey: node.Data.BodyInterior[0].Key, - ToMaxKey: node.Data.BodyInterior[0].Key, + FromTree: node.Data.Head.Owner, + FromItemSlot: 0, + ToKey: node.Data.BodyInterior[0].Key, + ToMaxKey: node.Data.BodyInterior[0].Key, }) } } @@ -490,7 +490,7 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, fn func(btrfsprim. if err != nil { return Item{}, err } - item := node.Data.BodyLeaf[path.Node(-1).FromItemIdx] + item := node.Data.BodyLeaf[path.Node(-1).FromItemSlot] item.Body = item.Body.CloneItem() FreeNodeRef(node) return item, nil @@ -526,7 +526,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if err != nil { return nil, err } - middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemIdx] + middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemSlot] ret := []Item{middleItem} var errs derror.MultiError @@ -540,7 +540,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if len(prevPath) == 0 { break } - prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemIdx] + prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemSlot] if fn(prevItem.Key, prevItem.BodySize) != 0 { break } @@ -567,7 +567,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, fn func(btrfspr if len(nextPath) == 0 { break } - nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemIdx] + nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemSlot] if fn(nextItem.Key, nextItem.BodySize) != 0 { break } -- cgit v1.2.3-2-g168b