Merge branch 'lukeshu/containers'

6 files changed, 61 insertions, 51 deletions

diff --git a/lib/btrfsprogs/btrfsinspect/print_addrspace.go b/lib/btrfsprogs/btrfsinspect/print_addrspace.go
index a8b992e..e85e055 100644
--- a/lib/btrfsprogs/btrfsinspect/print_addrspace.go
+++ b/lib/btrfsprogs/btrfsinspect/print_addrspace.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
 //
 // SPDX-License-Identifier: GPL-2.0-or-later
 
@@ -46,7 +46,7 @@ func PrintLogicalSpace(out io.Writer, fs *btrfs.FS) {
 func PrintPhysicalSpace(out io.Writer, fs *btrfs.FS) {
 	mappings := fs.LV.Mappings()
 	sort.Slice(mappings, func(i, j int) bool {
-		return mappings[i].PAddr.Cmp(mappings[j].PAddr) < 0
+		return mappings[i].PAddr.Compare(mappings[j].PAddr) < 0
 	})
 
 	var prevDev btrfsvol.DeviceID = 0
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
index 6b75d84..4724c12 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/fuzzymatchsums.go
@@ -26,7 +26,7 @@ type fuzzyRecord struct {
 	N     int
 }
 
-func (a fuzzyRecord) Cmp(b fuzzyRecord) int {
+func (a fuzzyRecord) Compare(b fuzzyRecord) int {
 	switch {
 	case a.N < b.N:
 		return -1
@@ -148,12 +148,12 @@ func (l *lowestN[T]) Insert(v T) {
 	switch {
 	case len(l.Dat) < l.N:
 		l.Dat = append(l.Dat, v)
-	case v.Cmp(l.Dat[0]) < 0:
+	case v.Compare(l.Dat[0]) < 0:
 		l.Dat[0] = v
 	default:
 		return
 	}
 	sort.Slice(l.Dat, func(i, j int) bool {
-		return l.Dat[i].Cmp(l.Dat[j]) < 0
+		return l.Dat[i].Compare(l.Dat[j]) < 0
 	})
 }
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
index 69d14c7..7c02d05 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/logicalsums.go
@@ -53,11 +53,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 	// "AAAAAAA" shouldn't be present, and if we just discard "BBBBBBBB"
 	// because it conflicts with "CCCCCCC", then we would erroneously
 	// include "AAAAAAA".
-	addrspace := &containers.RBTree[containers.NativeOrdered[btrfsvol.LogicalAddr], btrfsinspect.SysExtentCSum]{
-		KeyFn: func(item btrfsinspect.SysExtentCSum) containers.NativeOrdered[btrfsvol.LogicalAddr] {
-			return containers.NativeOrdered[btrfsvol.LogicalAddr]{Val: item.Sums.Addr}
-		},
-	}
+	addrspace := new(containers.RBTree[btrfsinspect.SysExtentCSum])
 	for _, newRecord := range records {
 		for {
 			conflict := addrspace.Search(func(oldRecord btrfsinspect.SysExtentCSum) int {
@@ -85,7 +81,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 			}
 			if oldRecord.Generation < newRecord.Generation {
 				// Newer generation wins.
-				addrspace.Delete(containers.NativeOrdered[btrfsvol.LogicalAddr]{Val: oldRecord.Sums.Addr})
+				addrspace.Delete(conflict)
 				// loop around to check for more conflicts
 				continue
 			}
@@ -142,7 +138,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 					},
 				},
 			}
-			addrspace.Delete(containers.NativeOrdered[btrfsvol.LogicalAddr]{Val: oldRecord.Sums.Addr})
+			addrspace.Delete(conflict)
 			newRecord = unionRecord
 			// loop around to check for more conflicts
 		}
@@ -152,7 +148,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 	var flattened SumRunWithGaps[btrfsvol.LogicalAddr]
 	var curAddr btrfsvol.LogicalAddr
 	var curSums strings.Builder
-	_ = addrspace.Walk(func(node *containers.RBNode[btrfsinspect.SysExtentCSum]) error {
+	addrspace.Range(func(node *containers.RBNode[btrfsinspect.SysExtentCSum]) bool {
 		curEnd := curAddr + (btrfsvol.LogicalAddr(curSums.Len()/sumSize) * btrfssum.BlockSize)
 		if node.Value.Sums.Addr != curEnd {
 			if curSums.Len() > 0 {
@@ -166,7 +162,7 @@ func ExtractLogicalSums(ctx context.Context, scanResults btrfsinspect.ScanDevice
 			curSums.Reset()
 		}
 		curSums.WriteString(string(node.Value.Sums.Sums))
-		return nil
+		return true
 	})
 	if curSums.Len() > 0 {
 		flattened.Runs = append(flattened.Runs, btrfssum.SumRun[btrfsvol.LogicalAddr]{
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go
index 0806a63..da22fbf 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/physicalsums.go
@@ -1,4 +1,4 @@
-// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+// Copyright (C) 2022-2023  Luke Shumaker <lukeshu@lukeshu.com>
 //
 // SPDX-License-Identifier: GPL-2.0-or-later
 
@@ -34,7 +34,7 @@ func ListUnmappedPhysicalRegions(fs *btrfs.FS) map[btrfsvol.DeviceID][]PhysicalR
 	pos := make(map[btrfsvol.DeviceID]btrfsvol.PhysicalAddr)
 	mappings := fs.LV.Mappings()
 	sort.Slice(mappings, func(i, j int) bool {
-		return mappings[i].PAddr.Cmp(mappings[j].PAddr) < 0
+		return mappings[i].PAddr.Compare(mappings[j].PAddr) < 0
 	})
 	for _, mapping := range mappings {
 		if pos[mapping.PAddr.Dev] < mapping.PAddr.Addr {
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
index ebca2bd..bd29278 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/rebuild.go
@@ -36,11 +36,11 @@ type keyAndTree struct {
 	TreeID btrfsprim.ObjID
 }
 
-func (a keyAndTree) Cmp(b keyAndTree) int {
-	if d := containers.NativeCmp(a.TreeID, b.TreeID); d != 0 {
+func (a keyAndTree) Compare(b keyAndTree) int {
+	if d := containers.NativeCompare(a.TreeID, b.TreeID); d != 0 {
 		return d
 	}
-	return a.Key.Cmp(b.Key)
+	return a.Key.Compare(b.Key)
 }
 
 func (o keyAndTree) String() string {
@@ -155,7 +155,7 @@ func (o *rebuilder) Rebuild(_ctx context.Context) error {
 			itemQueue := maps.Keys(o.itemQueue)
 			o.itemQueue = make(containers.Set[keyAndTree])
 			sort.Slice(itemQueue, func(i, j int) bool {
-				return itemQueue[i].Cmp(itemQueue[j]) < 0
+				return itemQueue[i].Compare(itemQueue[j]) < 0
 			})
 			var progress itemStats
 			progress.D = len(itemQueue)
@@ -596,7 +596,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, wantKey s
 	}
 	if key, _, ok := o.rebuilt.Tree(ctx, treeID).Items(ctx).Search(func(key btrfsprim.Key, _ keyio.ItemPtr) int {
 		key.Offset = 0
-		return tgt.Cmp(key)
+		return tgt.Compare(key)
 	}); ok {
 		return key, true
 	}
@@ -608,7 +608,7 @@ func (o *rebuilder) _want(ctx context.Context, treeID btrfsprim.ObjID, wantKey s
 	}
 	wants := make(containers.Set[btrfsvol.LogicalAddr])
 	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
-		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) },
+		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Compare(k) },
 		func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
 			wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
 			return true
@@ -649,7 +649,7 @@ func (o *rebuilder) _wantOff(ctx context.Context, treeID btrfsprim.ObjID, wantKe
 	}
 	wants := make(containers.Set[btrfsvol.LogicalAddr])
 	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
-		func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Cmp(k) },
+		func(k btrfsprim.Key, _ keyio.ItemPtr) int { return tgt.Compare(k) },
 		func(_ btrfsprim.Key, v keyio.ItemPtr) bool {
 			wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
 			return true
@@ -674,7 +674,7 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, wantK
 	o.rebuilt.Tree(ctx, treeID).Items(ctx).Subrange(
 		func(key btrfsprim.Key, _ keyio.ItemPtr) int {
 			key.Offset = 0
-			return tgt.Cmp(key)
+			return tgt.Compare(key)
 		},
 		func(_ btrfsprim.Key, itemPtr keyio.ItemPtr) bool {
 			if fn(itemPtr) {
@@ -693,7 +693,7 @@ func (o *rebuilder) _wantFunc(ctx context.Context, treeID btrfsprim.ObjID, wantK
 	}
 	wants := make(containers.Set[btrfsvol.LogicalAddr])
 	o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx).Subrange(
-		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Cmp(k) },
+		func(k btrfsprim.Key, _ keyio.ItemPtr) int { k.Offset = 0; return tgt.Compare(k) },
 		func(k btrfsprim.Key, v keyio.ItemPtr) bool {
 			if fn(v) {
 				wants.InsertFrom(o.rebuilt.Tree(ctx, treeID).LeafToRoots(ctx, v.Node))
@@ -735,9 +735,9 @@ func (o *rebuilder) _walkRange(
 	items.Subrange(
 		func(runKey btrfsprim.Key, _ keyio.ItemPtr) int {
 			switch {
-			case min.Cmp(runKey) < 0:
+			case min.Compare(runKey) < 0:
 				return 1
-			case max.Cmp(runKey) > 0:
+			case max.Compare(runKey) > 0:
 				return -1
 			default:
 				return 0
@@ -770,6 +770,16 @@ func (o *rebuilder) _walkRange(
 		})
 }
 
+type gap struct {
+	// range is [Beg,End)
+	Beg, End uint64
+}
+
+// Compare implements containers.Ordered.
+func (a gap) Compare(b gap) int {
+	return containers.NativeCompare(a.Beg, b.Beg)
+}
+
 func (o *rebuilder) _wantRange(
 	ctx context.Context,
 	treeID btrfsprim.ObjID, objID btrfsprim.ObjID, typ btrfsprim.ItemType,
@@ -787,15 +797,7 @@ func (o *rebuilder) _wantRange(
 	//
 	// Start with a gap of the whole range, then subtract each run
 	// from it.
-	type gap struct {
-		// range is [Beg,End)
-		Beg, End uint64
-	}
-	gaps := &containers.RBTree[containers.NativeOrdered[uint64], gap]{
-		KeyFn: func(gap gap) containers.NativeOrdered[uint64] {
-			return containers.NativeOrdered[uint64]{Val: gap.Beg}
-		},
-	}
+	gaps := new(containers.RBTree[gap])
 	gaps.Insert(gap{
 		Beg: beg,
 		End: end,
@@ -805,23 +807,29 @@ func (o *rebuilder) _wantRange(
 		o.rebuilt.Tree(ctx, treeID).Items(ctx),
 		treeID, objID, typ, beg, end,
 		func(runKey btrfsprim.Key, _ keyio.ItemPtr, runBeg, runEnd uint64) {
-			overlappingGaps := gaps.SearchRange(func(gap gap) int {
-				switch {
-				case gap.End <= runBeg:
-					return 1
-				case runEnd <= gap.Beg:
-					return -1
-				default:
-					return 0
-				}
-			})
+			var overlappingGaps []*containers.RBNode[gap]
+			gaps.Subrange(
+				func(gap gap) int {
+					switch {
+					case gap.End <= runBeg:
+						return 1
+					case runEnd <= gap.Beg:
+						return -1
+					default:
+						return 0
+					}
+				},
+				func(node *containers.RBNode[gap]) bool {
+					overlappingGaps = append(overlappingGaps, node)
+					return true
+				})
 			if len(overlappingGaps) == 0 {
 				return
 			}
-			gapsBeg := overlappingGaps[0].Beg
-			gapsEnd := overlappingGaps[len(overlappingGaps)-1].End
+			gapsBeg := overlappingGaps[0].Value.Beg
+			gapsEnd := overlappingGaps[len(overlappingGaps)-1].Value.End
 			for _, gap := range overlappingGaps {
-				gaps.Delete(containers.NativeOrdered[uint64]{Val: gap.Beg})
+				gaps.Delete(gap)
 			}
 			if gapsBeg < runBeg {
 				gaps.Insert(gap{
@@ -842,7 +850,7 @@ func (o *rebuilder) _wantRange(
 		return
 	}
 	potentialItems := o.rebuilt.Tree(ctx, treeID).PotentialItems(ctx)
-	_ = gaps.Walk(func(rbNode *containers.RBNode[gap]) error {
+	gaps.Range(func(rbNode *containers.RBNode[gap]) bool {
 		gap := rbNode.Value
 		last := gap.Beg
 		o._walkRange(
@@ -874,7 +882,7 @@ func (o *rebuilder) _wantRange(
 				o.wantAugment(wantCtx, treeID, wantKey, nil)
 			}
 		}
-		return nil
+		return true
 	})
 }
 
diff --git a/lib/btrfsprogs/btrfsinspect/scandevices.go b/lib/btrfsprogs/btrfsinspect/scandevices.go
index 7668a83..9b8360c 100644
--- a/lib/btrfsprogs/btrfsinspect/scandevices.go
+++ b/lib/btrfsprogs/btrfsinspect/scandevices.go
@@ -22,6 +22,7 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfssum"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfstree"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/textui"
 )
 
@@ -79,6 +80,11 @@ type SysExtentCSum struct {
 	Sums       btrfsitem.ExtentCSum
 }
 
+// Compare implements containers.Ordered.
+func (a SysExtentCSum) Compare(b SysExtentCSum) int {
+	return containers.NativeCompare(a.Sums.Addr, b.Sums.Addr)
+}
+
 type scanStats struct {
 	textui.Portion[btrfsvol.PhysicalAddr]