summaryrefslogtreecommitdiff
path: root/lib/btrfs/btrfstree/btree_tree.go
diff options
context:
space:
mode:
Diffstat (limited to 'lib/btrfs/btrfstree/btree_tree.go')
-rw-r--r--lib/btrfs/btrfstree/btree_tree.go184
1 files changed, 91 insertions, 93 deletions
diff --git a/lib/btrfs/btrfstree/btree_tree.go b/lib/btrfs/btrfstree/btree_tree.go
index 1e3c789..7561314 100644
--- a/lib/btrfs/btrfstree/btree_tree.go
+++ b/lib/btrfs/btrfstree/btree_tree.go
@@ -15,8 +15,6 @@ import (
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem"
"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsprim"
- "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
- "git.lukeshu.com/btrfs-progs-ng/lib/diskio"
"git.lukeshu.com/btrfs-progs-ng/lib/slices"
)
@@ -72,7 +70,7 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
}
}
node, err := fs.ReadNode(path)
- defer FreeNodeRef(node)
+ defer node.Free()
if ctx.Err() != nil {
return
}
@@ -97,17 +95,17 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
return
}
if node != nil {
- for i, item := range node.Data.BodyInterior {
+ for i, item := range node.BodyInterior {
toMaxKey := path.Node(-1).ToMaxKey
- if i+1 < len(node.Data.BodyInterior) {
- toMaxKey = node.Data.BodyInterior[i+1].Key.Mm()
+ if i+1 < len(node.BodyInterior) {
+ toMaxKey = node.BodyInterior[i+1].Key.Mm()
}
itemPath := append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ FromTree: node.Head.Owner,
FromItemSlot: i,
ToNodeAddr: item.BlockPtr,
ToNodeGeneration: item.Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
+ ToNodeLevel: node.Head.Level - 1,
ToKey: item.Key,
ToMaxKey: toMaxKey,
})
@@ -129,9 +127,9 @@ func (fs TreeOperatorImpl) treeWalk(ctx context.Context, path TreePath, errHandl
}
}
}
- for i, item := range node.Data.BodyLeaf {
+ for i, item := range node.BodyLeaf {
itemPath := append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ FromTree: node.Head.Owner,
FromItemSlot: i,
ToKey: item.Key,
ToMaxKey: item.Key,
@@ -169,7 +167,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) {
+func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key, uint32) int) (TreePath, *Node, error) {
path := TreePath{{
FromTree: treeRoot.TreeID,
FromItemSlot: -1,
@@ -184,15 +182,15 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
}
node, err := fs.ReadNode(path)
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
switch {
- case node.Data.Head.Level > 0:
+ case node.Head.Level > 0:
// interior node
- // Search for the right-most node.Data.BodyInterior item for which
+ // Search for the right-most node.BodyInterior item for which
// `fn(item.Key) >= 0`.
//
// + + + + 0 - - - -
@@ -200,31 +198,31 @@ 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.BodyInterior, func(kp KeyPointer) int {
+ lastGood, ok := slices.SearchHighest(node.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 {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, ErrNoItem
}
toMaxKey := path.Node(-1).ToMaxKey
- if lastGood+1 < len(node.Data.BodyInterior) {
- toMaxKey = node.Data.BodyInterior[lastGood+1].Key.Mm()
+ if lastGood+1 < len(node.BodyInterior) {
+ toMaxKey = node.BodyInterior[lastGood+1].Key.Mm()
}
path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ FromTree: node.Head.Owner,
FromItemSlot: lastGood,
- ToNodeAddr: node.Data.BodyInterior[lastGood].BlockPtr,
- ToNodeGeneration: node.Data.BodyInterior[lastGood].Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
- ToKey: node.Data.BodyInterior[lastGood].Key,
+ ToNodeAddr: node.BodyInterior[lastGood].BlockPtr,
+ ToNodeGeneration: node.BodyInterior[lastGood].Generation,
+ ToNodeLevel: node.Head.Level - 1,
+ ToKey: node.BodyInterior[lastGood].Key,
ToMaxKey: toMaxKey,
})
- FreeNodeRef(node)
+ node.Free()
default:
// leaf node
- // Search for a member of node.Data.BodyLeaf for which
+ // Search for a member of node.BodyLeaf for which
// `fn(item.Head.Key) == 0`.
//
// + + + + 0 - - - -
@@ -234,25 +232,25 @@ func (fs TreeOperatorImpl) treeSearch(treeRoot TreeRoot, fn func(btrfsprim.Key,
// is returned.
//
// Implement this search as a binary search.
- slot, ok := slices.Search(node.Data.BodyLeaf, func(item Item) int {
+ slot, ok := slices.Search(node.BodyLeaf, func(item Item) int {
return fn(item.Key, item.BodySize)
})
if !ok {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, ErrNoItem
}
path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ FromTree: node.Head.Owner,
FromItemSlot: slot,
- ToKey: node.Data.BodyLeaf[slot].Key,
- ToMaxKey: node.Data.BodyLeaf[slot].Key,
+ ToKey: node.BodyLeaf[slot].Key,
+ ToMaxKey: node.BodyLeaf[slot].Key,
})
return path, node, nil
}
}
}
-func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) prev(path TreePath, node *Node) (TreePath, *Node, error) {
var err error
path = path.DeepCopy()
@@ -266,139 +264,139 @@ func (fs TreeOperatorImpl) prev(path TreePath, node *diskio.Ref[btrfsvol.Logical
// go left
path.Node(-1).FromItemSlot--
if path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
+ path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
}
}
// go down
for path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-1).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-1).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path)
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
}
- if node.Data.Head.Level > 0 {
+ if node.Head.Level > 0 {
path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
- 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,
- ToKey: node.Data.BodyInterior[len(node.Data.BodyInterior)-1].Key,
+ FromTree: node.Head.Owner,
+ FromItemSlot: len(node.BodyInterior) - 1,
+ ToNodeAddr: node.BodyInterior[len(node.BodyInterior)-1].BlockPtr,
+ ToNodeGeneration: node.BodyInterior[len(node.BodyInterior)-1].Generation,
+ ToNodeLevel: node.Head.Level - 1,
+ ToKey: node.BodyInterior[len(node.BodyInterior)-1].Key,
ToMaxKey: path.Node(-1).ToMaxKey,
})
} else {
path = append(path, TreePathElem{
- 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,
+ FromTree: node.Head.Owner,
+ FromItemSlot: len(node.BodyLeaf) - 1,
+ ToKey: node.BodyLeaf[len(node.BodyLeaf)-1].Key,
+ ToMaxKey: node.BodyLeaf[len(node.BodyLeaf)-1].Key,
})
}
}
// return
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
}
return path, node, nil
}
-func (fs TreeOperatorImpl) next(path TreePath, node *diskio.Ref[btrfsvol.LogicalAddr, Node]) (TreePath, *diskio.Ref[btrfsvol.LogicalAddr, Node], error) {
+func (fs TreeOperatorImpl) next(path TreePath, node *Node) (TreePath, *Node, error) {
var err error
path = path.DeepCopy()
// go up
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-2).ToNodeLevel = node.Data.Head.Level
+ path.Node(-2).ToNodeLevel = node.Head.Level
}
- for path.Node(-1).FromItemSlot+1 >= int(node.Data.Head.NumItems) {
+ for path.Node(-1).FromItemSlot+1 >= int(node.Head.NumItems) {
path = path.Parent()
if len(path) == 1 {
return nil, nil, nil
}
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-2).ToNodeLevel = node.Data.Head.Level
+ path.Node(-2).ToNodeLevel = node.Head.Level
}
}
// go right
path.Node(-1).FromItemSlot++
if path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-1).ToNodeAddr = node.Data.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
+ path.Node(-1).ToNodeAddr = node.BodyInterior[path.Node(-1).FromItemSlot].BlockPtr
}
}
// go down
for path.Node(-1).ToNodeAddr != 0 {
- if node.Addr != path.Node(-1).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-1).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path)
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
- path.Node(-1).ToNodeLevel = node.Data.Head.Level
+ path.Node(-1).ToNodeLevel = node.Head.Level
}
- if node.Data.Head.Level > 0 {
+ if node.Head.Level > 0 {
toMaxKey := path.Node(-1).ToMaxKey
- if len(node.Data.BodyInterior) > 1 {
- toMaxKey = node.Data.BodyInterior[1].Key.Mm()
+ if len(node.BodyInterior) > 1 {
+ toMaxKey = node.BodyInterior[1].Key.Mm()
}
path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ FromTree: node.Head.Owner,
FromItemSlot: 0,
- ToNodeAddr: node.Data.BodyInterior[0].BlockPtr,
- ToNodeGeneration: node.Data.BodyInterior[0].Generation,
- ToNodeLevel: node.Data.Head.Level - 1,
- ToKey: node.Data.BodyInterior[0].Key,
+ ToNodeAddr: node.BodyInterior[0].BlockPtr,
+ ToNodeGeneration: node.BodyInterior[0].Generation,
+ ToNodeLevel: node.Head.Level - 1,
+ ToKey: node.BodyInterior[0].Key,
ToMaxKey: toMaxKey,
})
} else {
path = append(path, TreePathElem{
- FromTree: node.Data.Head.Owner,
+ FromTree: node.Head.Owner,
FromItemSlot: 0,
- ToKey: node.Data.BodyInterior[0].Key,
- ToMaxKey: node.Data.BodyInterior[0].Key,
+ ToKey: node.BodyInterior[0].Key,
+ ToMaxKey: node.BodyInterior[0].Key,
})
}
}
// return
- if node.Addr != path.Node(-2).ToNodeAddr {
- FreeNodeRef(node)
+ if node.Head.Addr != path.Node(-2).ToNodeAddr {
+ node.Free()
node, err = fs.ReadNode(path.Parent())
if err != nil {
- FreeNodeRef(node)
+ node.Free()
return nil, nil, err
}
}
@@ -419,9 +417,9 @@ func (fs TreeOperatorImpl) TreeSearch(treeID btrfsprim.ObjID, searcher TreeSearc
if err != nil {
return Item{}, fmt.Errorf("item with %s: %w", searcher, err)
}
- item := node.Data.BodyLeaf[path.Node(-1).FromItemSlot]
+ item := node.BodyLeaf[path.Node(-1).FromItemSlot]
item.Body = item.Body.CloneItem()
- FreeNodeRef(node)
+ node.Free()
return item, nil
}
@@ -444,7 +442,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
if err != nil {
return nil, fmt.Errorf("items with %s: %w", searcher, err)
}
- middleItem := middleNode.Data.BodyLeaf[middlePath.Node(-1).FromItemSlot]
+ middleItem := middleNode.BodyLeaf[middlePath.Node(-1).FromItemSlot]
ret := []Item{middleItem}
var errs derror.MultiError
@@ -458,7 +456,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
if len(prevPath) == 0 {
break
}
- prevItem := prevNode.Data.BodyLeaf[prevPath.Node(-1).FromItemSlot]
+ prevItem := prevNode.BodyLeaf[prevPath.Node(-1).FromItemSlot]
if searcher.Search(prevItem.Key, prevItem.BodySize) != 0 {
break
}
@@ -467,11 +465,11 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
ret = append(ret, item)
}
slices.Reverse(ret)
- if prevNode.Addr != middlePath.Node(-1).ToNodeAddr {
- FreeNodeRef(prevNode)
+ if prevNode.Head.Addr != middlePath.Node(-1).ToNodeAddr {
+ prevNode.Free()
middleNode, err = fs.ReadNode(middlePath)
if err != nil {
- FreeNodeRef(middleNode)
+ middleNode.Free()
return nil, fmt.Errorf("items with %s: %w", searcher, err)
}
}
@@ -485,7 +483,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
if len(nextPath) == 0 {
break
}
- nextItem := nextNode.Data.BodyLeaf[nextPath.Node(-1).FromItemSlot]
+ nextItem := nextNode.BodyLeaf[nextPath.Node(-1).FromItemSlot]
if searcher.Search(nextItem.Key, nextItem.BodySize) != 0 {
break
}
@@ -493,7 +491,7 @@ func (fs TreeOperatorImpl) TreeSearchAll(treeID btrfsprim.ObjID, searcher TreeSe
item.Body = item.Body.CloneItem()
ret = append(ret, item)
}
- FreeNodeRef(nextNode)
+ nextNode.Free()
if errs != nil {
err = errs
}
generated by cgit v1.1-4-g5e80 at 2024-06-02 12:19:15 +0000