From 952b677bf7f10da93673e3671f764c54c454bbfe Mon Sep 17 00:00:00 2001 From: Luke Shumaker Date: Wed, 13 Jul 2022 20:41:10 -0600 Subject: Move ordered.go to lib/containers Something about this trips a stack overflow in golangci-lint, so upgrade golangci-lint to a commit that fixes this. --- lib/btrfs/btrfsvol/lvm.go | 36 ++++++++++++++++++------------------ lib/btrfs/internal/misc.go | 8 ++++---- lib/btrfs/io4_fs.go | 3 ++- lib/containers/ordered.go | 41 +++++++++++++++++++++++++++++++++++++++++ lib/containers/rbtree.go | 2 +- lib/containers/rbtree_test.go | 18 ++++++++---------- lib/util/ordered.go | 41 ----------------------------------------- 7 files changed, 74 insertions(+), 75 deletions(-) create mode 100644 lib/containers/ordered.go delete mode 100644 lib/util/ordered.go (limited to 'lib') diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go index 351cbe5..62ca6d7 100644 --- a/lib/btrfs/btrfsvol/lvm.go +++ b/lib/btrfs/btrfsvol/lvm.go @@ -19,8 +19,8 @@ type LogicalVolume[PhysicalVolume util.File[PhysicalAddr]] struct { id2pv map[DeviceID]PhysicalVolume - logical2physical *containers.RBTree[util.NativeOrdered[LogicalAddr], chunkMapping] - physical2logical map[DeviceID]*containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping] + logical2physical *containers.RBTree[containers.NativeOrdered[LogicalAddr], chunkMapping] + physical2logical map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping] } var _ util.File[LogicalAddr] = (*LogicalVolume[util.File[PhysicalAddr]])(nil) @@ -30,20 +30,20 @@ func (lv *LogicalVolume[PhysicalVolume]) init() { lv.id2pv = make(map[DeviceID]PhysicalVolume) } if lv.logical2physical == nil { - lv.logical2physical = &containers.RBTree[util.NativeOrdered[LogicalAddr], chunkMapping]{ - KeyFn: func(chunk chunkMapping) util.NativeOrdered[LogicalAddr] { - return util.NativeOrdered[LogicalAddr]{Val: chunk.LAddr} + lv.logical2physical = &containers.RBTree[containers.NativeOrdered[LogicalAddr], chunkMapping]{ + KeyFn: func(chunk chunkMapping) containers.NativeOrdered[LogicalAddr] { + return containers.NativeOrdered[LogicalAddr]{Val: chunk.LAddr} }, } } if lv.physical2logical == nil { - lv.physical2logical = make(map[DeviceID]*containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping], len(lv.id2pv)) + lv.physical2logical = make(map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping], len(lv.id2pv)) } for devid := range lv.id2pv { if _, ok := lv.physical2logical[devid]; !ok { - lv.physical2logical[devid] = &containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) util.NativeOrdered[PhysicalAddr] { - return util.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} + lv.physical2logical[devid] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ + KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { + return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} }, } } @@ -74,9 +74,9 @@ func (lv *LogicalVolume[PhysicalVolume]) AddPhysicalVolume(id DeviceID, dev Phys lv, dev.Name(), other.Name(), id) } lv.id2pv[id] = dev - lv.physical2logical[id] = &containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) util.NativeOrdered[PhysicalAddr] { - return util.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} + lv.physical2logical[id] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ + KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { + return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} }, } return nil @@ -148,13 +148,13 @@ func (lv *LogicalVolume[PhysicalVolume]) AddMapping(m Mapping) error { // logical2physical for _, chunk := range logicalOverlaps { - lv.logical2physical.Delete(util.NativeOrdered[LogicalAddr]{Val: chunk.LAddr}) + lv.logical2physical.Delete(containers.NativeOrdered[LogicalAddr]{Val: chunk.LAddr}) } lv.logical2physical.Insert(newChunk) // physical2logical for _, ext := range physicalOverlaps { - lv.physical2logical[m.PAddr.Dev].Delete(util.NativeOrdered[PhysicalAddr]{Val: ext.PAddr}) + lv.physical2logical[m.PAddr.Dev].Delete(containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr}) } lv.physical2logical[m.PAddr.Dev].Insert(newExt) @@ -173,7 +173,7 @@ func (lv *LogicalVolume[PhysicalVolume]) AddMapping(m Mapping) error { } func (lv *LogicalVolume[PhysicalVolume]) fsck() error { - physical2logical := make(map[DeviceID]*containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]) + physical2logical := make(map[DeviceID]*containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]) if err := lv.logical2physical.Walk(func(node *containers.RBNode[chunkMapping]) error { chunk := node.Value for _, stripe := range chunk.PAddrs { @@ -182,9 +182,9 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error { lv, stripe.Dev) } if _, exists := physical2logical[stripe.Dev]; !exists { - physical2logical[stripe.Dev] = &containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]{ - KeyFn: func(ext devextMapping) util.NativeOrdered[PhysicalAddr] { - return util.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} + physical2logical[stripe.Dev] = &containers.RBTree[containers.NativeOrdered[PhysicalAddr], devextMapping]{ + KeyFn: func(ext devextMapping) containers.NativeOrdered[PhysicalAddr] { + return containers.NativeOrdered[PhysicalAddr]{Val: ext.PAddr} }, } } diff --git a/lib/btrfs/internal/misc.go b/lib/btrfs/internal/misc.go index 49fe2bd..eb5c287 100644 --- a/lib/btrfs/internal/misc.go +++ b/lib/btrfs/internal/misc.go @@ -9,7 +9,7 @@ import ( "time" "git.lukeshu.com/btrfs-progs-ng/lib/binstruct" - "git.lukeshu.com/btrfs-progs-ng/lib/util" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" ) type Generation uint64 @@ -26,13 +26,13 @@ func (k Key) String() string { } func (a Key) Cmp(b Key) int { - if d := util.CmpUint(a.ObjectID, b.ObjectID); d != 0 { + if d := containers.CmpUint(a.ObjectID, b.ObjectID); d != 0 { return d } - if d := util.CmpUint(a.ItemType, b.ItemType); d != 0 { + if d := containers.CmpUint(a.ItemType, b.ItemType); d != 0 { return d } - return util.CmpUint(a.Offset, b.Offset) + return containers.CmpUint(a.Offset, b.Offset) } type Time struct { diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go index 07e52bb..eaa83f7 100644 --- a/lib/btrfs/io4_fs.go +++ b/lib/btrfs/io4_fs.go @@ -16,6 +16,7 @@ import ( "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsitem" "git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol" + "git.lukeshu.com/btrfs-progs-ng/lib/containers" "git.lukeshu.com/btrfs-progs-ng/lib/util" ) @@ -133,7 +134,7 @@ func (sv *Subvolume) LoadFullInode(inode ObjID) (*FullInode, error) { }, } items, err := sv.FS.TreeSearchAll(sv.TreeID, func(key Key) int { - return util.CmpUint(inode, key.ObjectID) + return containers.CmpUint(inode, key.ObjectID) }) if err != nil { val.Errs = append(val.Errs, err) diff --git a/lib/containers/ordered.go b/lib/containers/ordered.go new file mode 100644 index 0000000..c5a3ec5 --- /dev/null +++ b/lib/containers/ordered.go @@ -0,0 +1,41 @@ +// Copyright (C) 2022 Luke Shumaker +// +// SPDX-License-Identifier: GPL-2.0-or-later + +package containers + +import ( + "golang.org/x/exp/constraints" +) + +func CmpUint[T constraints.Unsigned](a, b T) int { + switch { + case a < b: + return -1 + case a == b: + return 0 + default: + return 1 + } +} + +type Ordered[T interface{ Cmp(T) int }] interface { + Cmp(T) int +} + +type NativeOrdered[T constraints.Ordered] struct { + Val T +} + +func (a NativeOrdered[T]) Cmp(b NativeOrdered[T]) int { + switch { + case a.Val < b.Val: + return -1 + case a.Val > b.Val: + return 1 + default: + return 0 + } +} + +var _ Ordered[NativeOrdered[int]] = NativeOrdered[int]{} diff --git a/lib/containers/rbtree.go b/lib/containers/rbtree.go index 6bffc02..64a679e 100644 --- a/lib/containers/rbtree.go +++ b/lib/containers/rbtree.go @@ -33,7 +33,7 @@ func (node *RBNode[V]) getColor() Color { return node.Color } -type RBTree[K util.Ordered[K], V any] struct { +type RBTree[K Ordered[K], V any] struct { KeyFn func(V) K root *RBNode[V] } diff --git a/lib/containers/rbtree_test.go b/lib/containers/rbtree_test.go index 3360bc0..65cc78d 100644 --- a/lib/containers/rbtree_test.go +++ b/lib/containers/rbtree_test.go @@ -13,8 +13,6 @@ import ( "github.com/stretchr/testify/require" "golang.org/x/exp/constraints" - - "git.lukeshu.com/btrfs-progs-ng/lib/util" ) func (t *RBTree[K, V]) ASCIIArt() string { @@ -51,7 +49,7 @@ func (node *RBNode[V]) asciiArt(w io.Writer, u, m, l string) { node.Left.asciiArt(w, l+" | ", l+" `--", l+" ") } -func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *RBTree[util.NativeOrdered[K], V]) { +func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *RBTree[NativeOrdered[K], V]) { // 1. Every node is either red or black // 2. The root is black. @@ -101,7 +99,7 @@ func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]s expectedOrder := make([]K, 0, len(expectedSet)) for k := range expectedSet { expectedOrder = append(expectedOrder, k) - node := tree.Lookup(util.NativeOrdered[K]{Val: k}) + node := tree.Lookup(NativeOrdered[K]{Val: k}) require.NotNil(t, tree, node) require.Equal(t, k, tree.KeyFn(node.Value).Val) } @@ -139,9 +137,9 @@ func FuzzRBTree(f *testing.F) { }) f.Fuzz(func(t *testing.T, dat []uint8) { - tree := &RBTree[util.NativeOrdered[uint8], uint8]{ - KeyFn: func(x uint8) util.NativeOrdered[uint8] { - return util.NativeOrdered[uint8]{Val: x} + tree := &RBTree[NativeOrdered[uint8], uint8]{ + KeyFn: func(x uint8) NativeOrdered[uint8] { + return NativeOrdered[uint8]{Val: x} }, } set := make(map[uint8]struct{}) @@ -155,15 +153,15 @@ func FuzzRBTree(f *testing.F) { tree.Insert(val) set[val] = struct{}{} t.Logf("\n%s\n", tree.ASCIIArt()) - node := tree.Lookup(util.NativeOrdered[uint8]{Val: val}) + node := tree.Lookup(NativeOrdered[uint8]{Val: val}) require.NotNil(t, node) require.Equal(t, val, node.Value) } else { t.Logf("Delete(%v)", val) - tree.Delete(util.NativeOrdered[uint8]{Val: val}) + tree.Delete(NativeOrdered[uint8]{Val: val}) delete(set, val) t.Logf("\n%s\n", tree.ASCIIArt()) - require.Nil(t, tree.Lookup(util.NativeOrdered[uint8]{Val: val})) + require.Nil(t, tree.Lookup(NativeOrdered[uint8]{Val: val})) } checkRBTree(t, set, tree) } diff --git a/lib/util/ordered.go b/lib/util/ordered.go deleted file mode 100644 index fc5b5ee..0000000 --- a/lib/util/ordered.go +++ /dev/null @@ -1,41 +0,0 @@ -// Copyright (C) 2022 Luke Shumaker -// -// SPDX-License-Identifier: GPL-2.0-or-later - -package util - -import ( - "golang.org/x/exp/constraints" -) - -func CmpUint[T constraints.Unsigned](a, b T) int { - switch { - case a < b: - return -1 - case a == b: - return 0 - default: - return 1 - } -} - -type Ordered[T interface{ Cmp(T) int }] interface { - Cmp(T) int -} - -type NativeOrdered[T constraints.Ordered] struct { - Val T -} - -func (a NativeOrdered[T]) Cmp(b NativeOrdered[T]) int { - switch { - case a.Val < b.Val: - return -1 - case a.Val > b.Val: - return 1 - default: - return 0 - } -} - -var _ Ordered[NativeOrdered[int]] = NativeOrdered[int]{} -- cgit v1.2.3-2-g168b