diff options
Diffstat (limited to 'lib/btrfsprogs/btrfsutil/skinny_paths.go')
-rw-r--r-- | lib/btrfsprogs/btrfsutil/skinny_paths.go | 106 |
1 files changed, 106 insertions, 0 deletions
diff --git a/lib/btrfsprogs/btrfsutil/skinny_paths.go b/lib/btrfsprogs/btrfsutil/skinny_paths.go new file mode 100644 index 0000000..7721137 --- /dev/null +++ b/lib/btrfsprogs/btrfsutil/skinny_paths.go @@ -0,0 +1,106 @@ +// Copyright (C) 2022 Luke Shumaker <lukeshu@lukeshu.com> +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package btrfsutil + +import ( + "fmt" + + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree" + "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" +) + +func maybeSet[K, V comparable](name string, m map[K]V, k K, v V) { + if other, conflict := m[k]; conflict && other != v { + panic(fmt.Errorf("conflict: %s %v can't have both %v and %v", name, k, other, v)) + } + m[k] = v +} + +type skinnyKP struct { + src, dst btrfsvol.LogicalAddr +} + +type skinnyItem struct { + node btrfsvol.LogicalAddr + item int +} + +type SkinnyPathArena struct { + fatKPs map[skinnyKP]btrfstree.TreePathElem + fatItems map[skinnyItem]btrfstree.TreePathElem +} + +type SkinnyPath struct { + Nodes []btrfsvol.LogicalAddr + Item int +} + +func (a *SkinnyPathArena) init() { + if a.fatKPs == nil { + a.fatKPs = make(map[skinnyKP]btrfstree.TreePathElem) + a.fatItems = make(map[skinnyItem]btrfstree.TreePathElem) + } +} + +func (a *SkinnyPathArena) Deflate(fat btrfstree.TreePath) SkinnyPath { + a.init() + + var ret SkinnyPath + ret.Item = -1 + + var prevNode btrfsvol.LogicalAddr + for _, elem := range fat { + if elem.ToNodeAddr > 0 { + maybeSet("SkinnyPathArena.fatKPs", a.fatKPs, skinnyKP{ + src: prevNode, + dst: elem.ToNodeAddr, + }, elem) + ret.Nodes = append(ret.Nodes, elem.ToNodeAddr) + } else { + maybeSet("SkinnyPathArena.fatItems", a.fatItems, skinnyItem{ + node: prevNode, + item: elem.FromItemIdx, + }, elem) + ret.Item = elem.FromItemIdx + } + prevNode = elem.ToNodeAddr + } + + return ret +} + +func (a *SkinnyPathArena) Inflate(skinny SkinnyPath) btrfstree.TreePath { + a.init() + + var ret btrfstree.TreePath + + var prevNode btrfsvol.LogicalAddr + for _, node := range skinny.Nodes { + elem, ok := a.fatKPs[skinnyKP{ + src: prevNode, + dst: node, + }] + if !ok { + panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for %v->%v", + prevNode, node)) + } + ret = append(ret, elem) + prevNode = node + } + + if skinny.Item >= 0 { + elem, ok := a.fatItems[skinnyItem{ + node: prevNode, + item: skinny.Item, + }] + if !ok { + panic(fmt.Errorf("SkinnyPathArena.Inflate: no stored TreePathElem for %v[%d]", + prevNode, skinny.Item)) + } + ret = append(ret, elem) + } + + return ret +} |