move dumb map and sort operations to util/generic.go

Also, the optimization of reversing the node list in pass1 isn't relevant
anymore now that I'm using rbtrees

4 files changed, 32 insertions, 26 deletions

diff --git a/cmd/btrfs-fsck/pass1.go b/cmd/btrfs-fsck/pass1.go
index 2cb58bf..6812c73 100644
--- a/cmd/btrfs-fsck/pass1.go
+++ b/cmd/btrfs-fsck/pass1.go
@@ -125,16 +125,7 @@ func (found pass1ScanOneDevResult) AddToLV(fs *btrfs.FS, dev *btrfs.Device) {
 	// nodes will be subsumed by other things.)
 	//
 	// Sort them so that progress numbers are predictable.
-	laddrs := make([]btrfsvol.LogicalAddr, 0, len(found.FoundNodes))
-	for laddr := range found.FoundNodes {
-		laddrs = append(laddrs, laddr)
-	}
-	sort.Slice(laddrs, func(i, j int) bool {
-		// And sort them in reverse order to keep insertions
-		// fast.
-		return laddrs[i] > laddrs[j]
-	})
-	for _, laddr := range laddrs {
+	for _, laddr := range util.SortedMapKeys(found.FoundNodes) {
 		for _, paddr := range found.FoundNodes[laddr] {
 			if err := fs.LV.AddMapping(btrfsvol.Mapping{
 				LAddr: laddr,
@@ -164,15 +155,19 @@ func (found pass1ScanOneDevResult) AddToLV(fs *btrfs.FS, dev *btrfs.Device) {
 		Size  btrfsvol.AddrDelta
 		Flags btrfsvol.BlockGroupFlags
 	}
-	blockgroups := make(map[blockgroup]struct{})
+	bgsSet := make(map[blockgroup]struct{})
 	for _, bg := range found.FoundBlockGroups {
-		blockgroups[blockgroup{
+		bgsSet[blockgroup{
 			LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID),
 			Size:  btrfsvol.AddrDelta(bg.Key.Offset),
 			Flags: bg.BG.Flags,
 		}] = struct{}{}
 	}
-	for bg := range blockgroups {
+	bgsOrdered := util.MapKeys(bgsSet)
+	sort.Slice(bgsOrdered, func(i, j int) bool {
+		return bgsOrdered[i].LAddr < bgsOrdered[j].LAddr
+	})
+	for _, bg := range bgsOrdered {
 		otherLAddr, otherPAddr := fs.LV.ResolveAny(bg.LAddr, bg.Size)
 		if otherLAddr < 0 || otherPAddr.Addr < 0 {
 			fmt.Printf("Pass 1: ... error: could not pair blockgroup laddr=%v (size=%v flags=%v) with a mapping\n",
diff --git a/cmd/btrfs-fsck/pass2.go b/cmd/btrfs-fsck/pass2.go
index d496d13..acea740 100644
--- a/cmd/btrfs-fsck/pass2.go
+++ b/cmd/btrfs-fsck/pass2.go
@@ -3,7 +3,6 @@ package main
 import (
 	"fmt"
 	iofs "io/fs"
-	"sort"
 
 	"lukeshu.com/btrfs-tools/pkg/btrfs"
 	"lukeshu.com/btrfs-tools/pkg/btrfsmisc"
@@ -53,14 +52,7 @@ func pass2(fs *btrfs.FS, foundNodes map[btrfs.LogicalAddr]struct{}) {
 		}
 	}
 
-	var orphanedRootsOrdered []btrfs.LogicalAddr
-	for root := range orphanedRoots {
-		orphanedRootsOrdered = append(orphanedRootsOrdered, root)
-	}
-	sort.Slice(orphanedRootsOrdered, func(i, j int) bool {
-		return orphanedRootsOrdered[i] < orphanedRootsOrdered[j]
-	})
-	for _, node := range orphanedRootsOrdered {
+	for _, node := range util.SortedMapKeys(orphanedRoots) {
 		fmt.Printf("Pass 2: orphaned root: %v\n", node)
 	}
 }
diff --git a/pkg/btrfs/btrfsvol/chunk.go b/pkg/btrfs/btrfsvol/chunk.go
index 146193d..8e5c4db 100644
--- a/pkg/btrfs/btrfsvol/chunk.go
+++ b/pkg/btrfs/btrfsvol/chunk.go
@@ -74,10 +74,7 @@ func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) {
 			}] = struct{}{}
 		}
 	}
-	ret.PAddrs = make([]QualifiedPhysicalAddr, 0, len(paddrs))
-	for paddr := range paddrs {
-		ret.PAddrs = append(ret.PAddrs, paddr)
-	}
+	ret.PAddrs = util.MapKeys(paddrs)
 	sort.Slice(ret.PAddrs, func(i, j int) bool {
 		return ret.PAddrs[i].Cmp(ret.PAddrs[j]) < 0
 	})
diff --git a/pkg/util/generic.go b/pkg/util/generic.go
index 6474ea5..70fed5b 100644
--- a/pkg/util/generic.go
+++ b/pkg/util/generic.go
@@ -1,6 +1,8 @@
 package util
 
 import (
+	"sort"
+
 	"golang.org/x/exp/constraints"
 )
 
@@ -55,3 +57,23 @@ func Min[T constraints.Ordered](a, b T) T {
 	}
 	return b
 }
+
+func MapKeys[K comparable, V any](m map[K]V) []K {
+	ret := make([]K, 0, len(m))
+	for k := range m {
+		ret = append(ret, k)
+	}
+	return ret
+}
+
+func SortSlice[T constraints.Ordered](slice []T) {
+	sort.Slice(slice, func(i, j int) bool {
+		return slice[i] < slice[j]
+	})
+}
+
+func SortedMapKeys[K constraints.Ordered, V any](m map[K]V) []K {
+	ret := MapKeys(m)
+	SortSlice(ret)
+	return ret
+}