Try to uniformly use containers.Set

13 files changed, 69 insertions, 46 deletions

diff --git a/cmd/btrfs-rec/inspect_lstrees.go b/cmd/btrfs-rec/inspect_lstrees.go
index a0f4ff3..f97eb2b 100644
--- a/cmd/btrfs-rec/inspect_lstrees.go
+++ b/cmd/btrfs-rec/inspect_lstrees.go
@@ -64,7 +64,7 @@ func init() {
 				fmt.Fprintf(table, "        total items\t% *s\n", numWidth, strconv.Itoa(totalItems))
 				table.Flush()
 			}
-			visitedNodes := make(map[btrfsvol.LogicalAddr]struct{})
+			visitedNodes := make(containers.Set[btrfsvol.LogicalAddr])
 			btrfsutil.WalkAllTrees(cmd.Context(), fs, btrfsutil.WalkAllTreesHandler{
 				PreTree: func(name string, treeID btrfsprim.ObjID) {
 					treeErrCnt = 0
@@ -76,7 +76,7 @@ func init() {
 				},
 				TreeWalkHandler: btrfstree.TreeWalkHandler{
 					Node: func(_ btrfstree.TreePath, ref *diskio.Ref[btrfsvol.LogicalAddr, btrfstree.Node]) error {
-						visitedNodes[ref.Addr] = struct{}{}
+						visitedNodes.Insert(ref.Addr)
 						return nil
 					},
 					Item: func(_ btrfstree.TreePath, item btrfstree.Item) error {
@@ -102,10 +102,10 @@ func init() {
 				sb, _ := fs.Superblock()
 				for _, devResults := range scanResults {
 					for laddr := range devResults.FoundNodes {
-						if _, visited := visitedNodes[laddr]; visited {
+						if visitedNodes.Has(laddr) {
 							continue
 						}
-						visitedNodes[laddr] = struct{}{}
+						visitedNodes.Insert(laddr)
 						node, err := btrfstree.ReadNode[btrfsvol.LogicalAddr](fs, *sb, laddr, btrfstree.NodeExpectations{
 							LAddr: containers.Optional[btrfsvol.LogicalAddr]{OK: true, Val: laddr},
 						})
diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go
index 8003466..e12e53e 100644
--- a/lib/btrfs/btrfsvol/lvm.go
+++ b/lib/btrfs/btrfsvol/lvm.go
@@ -256,6 +256,8 @@ func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping {
 	return ret
 }
 
+// paddrs isn't a containers.Set because QualifiedPhysicalAddr is not
+// an ordered type.
 func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[QualifiedPhysicalAddr]struct{}, maxlen AddrDelta) {
 	node := lv.logical2physical.Search(func(chunk chunkMapping) int {
 		return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk)
diff --git a/lib/btrfs/io4_fs.go b/lib/btrfs/io4_fs.go
index 8751078..82d4c87 100644
--- a/lib/btrfs/io4_fs.go
+++ b/lib/btrfs/io4_fs.go
@@ -248,13 +248,13 @@ func (ret *Dir) populate() {
 			panic(fmt.Errorf("TODO: handle item type %v", item.Key.ItemType))
 		}
 	}
-	entriesWithIndexes := make(map[string]struct{})
+	entriesWithIndexes := make(containers.Set[string])
 	nextIndex := uint64(2)
 	for index, entry := range ret.ChildrenByIndex {
 		if index+1 > nextIndex {
 			nextIndex = index + 1
 		}
-		entriesWithIndexes[string(entry.Name)] = struct{}{}
+		entriesWithIndexes.Insert(string(entry.Name))
 		if other, exists := ret.ChildrenByName[string(entry.Name)]; !exists {
 			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-name direntry for %q", entry.Name))
 			ret.ChildrenByName[string(entry.Name)] = entry
@@ -264,7 +264,7 @@ func (ret *Dir) populate() {
 		}
 	}
 	for _, name := range maps.SortedKeys(ret.ChildrenByName) {
-		if _, exists := entriesWithIndexes[name]; !exists {
+		if !entriesWithIndexes.Has(name) {
 			ret.Errs = append(ret.Errs, fmt.Errorf("missing by-index direntry for %q", name))
 			ret.ChildrenByIndex[nextIndex] = ret.ChildrenByName[name]
 			nextIndex++
diff --git a/lib/btrfsprogs/btrfsinspect/mount.go b/lib/btrfsprogs/btrfsinspect/mount.go
index 5905034..6cf6317 100644
--- a/lib/btrfsprogs/btrfsinspect/mount.go
+++ b/lib/btrfsprogs/btrfsinspect/mount.go
@@ -112,7 +112,7 @@ type subvolume struct {
 	fileHandles containers.SyncMap[fuseops.HandleID, *fileState]
 
 	subvolMu sync.Mutex
-	subvols  map[string]struct{}
+	subvols  containers.Set[string]
 	grp      *dgroup.Group
 }
 
@@ -176,11 +176,11 @@ func (sv *subvolume) LoadDir(inode btrfsprim.ObjID) (val *btrfs.Dir, err error)
 					continue
 				}
 				if sv.subvols == nil {
-					sv.subvols = make(map[string]struct{})
+					sv.subvols = make(containers.Set[string])
 				}
 				subMountpoint := filepath.Join(abspath, string(entry.Name))
-				if _, alreadyMounted := sv.subvols[subMountpoint]; !alreadyMounted {
-					sv.subvols[subMountpoint] = struct{}{}
+				if !sv.subvols.Has(subMountpoint) {
+					sv.subvols.Insert(subMountpoint)
 					workerName := fmt.Sprintf("%d-%s", val.Inode, filepath.Base(subMountpoint))
 					sv.grp.Go(workerName, func(ctx context.Context) error {
 						subSv := &subvolume{
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
index 91fecbc..a638f7c 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
@@ -21,7 +21,7 @@ type BlockGroup struct {
 
 func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) {
 	// Dedup
-	bgsSet := make(map[BlockGroup]struct{})
+	bgsSet := make(map[BlockGroup]struct{}) // Can't use containers.Set because BlockGroup isn't ordered
 	for _, devResults := range scanResults {
 		for _, bg := range devResults.FoundBlockGroups {
 			bgsSet[BlockGroup{
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go
index 4122b21..9a2bd89 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s1_uuidmap.go
@@ -25,18 +25,18 @@ type uuidMap struct {
 	UUID2ObjID map[btrfsprim.UUID]btrfsprim.ObjID
 	TreeParent map[btrfsprim.ObjID]btrfsprim.UUID
 
-	SeenTrees map[btrfsprim.ObjID]struct{}
+	SeenTrees containers.Set[btrfsprim.ObjID]
 }
 
-func (m uuidMap) missingRootItems() map[btrfsprim.ObjID]struct{} {
-	missing := make(map[btrfsprim.ObjID]struct{})
+func (m uuidMap) missingRootItems() containers.Set[btrfsprim.ObjID] {
+	missing := make(containers.Set[btrfsprim.ObjID])
 	for treeID := range m.SeenTrees {
 		if _, ok := m.ObjID2UUID[treeID]; !ok && treeID != btrfsprim.ROOT_TREE_OBJECTID {
-			missing[treeID] = struct{}{}
+			missing.Insert(treeID)
 			continue
 		}
 		if _, ok := m.TreeParent[treeID]; !ok && treeID >= btrfsprim.FIRST_FREE_OBJECTID && treeID <= btrfsprim.LAST_FREE_OBJECTID {
-			missing[treeID] = struct{}{}
+			missing.Insert(treeID)
 		}
 	}
 	return missing
@@ -163,7 +163,7 @@ func buildUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sc
 		UUID2ObjID: make(map[btrfsprim.UUID]btrfsprim.ObjID),
 		TreeParent: make(map[btrfsprim.ObjID]btrfsprim.UUID),
 
-		SeenTrees: make(map[btrfsprim.ObjID]struct{}),
+		SeenTrees: make(containers.Set[btrfsprim.ObjID]),
 	}
 
 	progress()
@@ -199,7 +199,7 @@ func buildUUIDMap(ctx context.Context, fs *btrfs.FS, scanResults btrfsinspect.Sc
 					}
 				}
 			}
-			ret.SeenTrees[nodeRef.Data.Head.Owner] = struct{}{}
+			ret.SeenTrees.Insert(nodeRef.Data.Head.Owner)
 			done++
 			progress()
 		}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go
index 9274a89..6adddc3 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s2_classify.go
@@ -32,7 +32,7 @@ type badNode struct {
 //  2. the list of bad nodes (in no particular order)
 //  3. tree ancestors thing
 func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDevicesResult) (
-	orphanedNodes map[btrfsvol.LogicalAddr]struct{},
+	orphanedNodes containers.Set[btrfsvol.LogicalAddr],
 	badNodes []badNode,
 	treeAncestors map[btrfsprim.ObjID]containers.Set[btrfsprim.ObjID],
 	err error,
@@ -41,7 +41,7 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev
 
 	lastPct := -1
 	total := countNodes(scanResults)
-	visitedNodes := make(map[btrfsvol.LogicalAddr]struct{})
+	visitedNodes := make(containers.Set[btrfsvol.LogicalAddr])
 	progress := func() {
 		done := len(visitedNodes)
 		pct := int(100 * float64(done) / float64(total))
@@ -64,7 +64,7 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev
 			return err
 		}
 		addr := path.Node(-1).ToNodeAddr
-		visitedNodes[addr] = struct{}{}
+		visitedNodes.Insert(addr)
 		if potentialRoot != 0 {
 			// lost node
 			if addr != potentialRoot {
@@ -84,7 +84,7 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev
 	walkHandler := btrfstree.TreeWalkHandler{
 		PreNode: func(path btrfstree.TreePath) error {
 			addr := path.Node(-1).ToNodeAddr
-			if _, alreadyVisited := visitedNodes[addr]; alreadyVisited {
+			if visitedNodes.Has(addr) {
 				// Can happen because of COW subvolumes;
 				// this is really a DAG not a tree.
 				return iofs.SkipDir
@@ -109,11 +109,11 @@ func classifyNodes(ctx context.Context, fs _FS, scanResults btrfsinspect.ScanDev
 
 	// Start with 'orphanedRoots' as a complete set of all orphaned nodes, and then delete
 	// non-root entries from it.
-	orphanedNodes = make(map[btrfsvol.LogicalAddr]struct{})
+	orphanedNodes = make(containers.Set[btrfsvol.LogicalAddr])
 	for _, devResults := range scanResults {
 		for laddr := range devResults.FoundNodes {
-			if _, attached := visitedNodes[laddr]; !attached {
-				orphanedNodes[laddr] = struct{}{}
+			if !visitedNodes.Has(laddr) {
+				orphanedNodes.Insert(laddr)
 			}
 		}
 	}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
index 5655eb6..7b43d28 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit.go
@@ -105,10 +105,14 @@ func reInitBrokenNodes(ctx context.Context, fs _FS, badNodes []badNode) (map[btr
 
 		min, max := spanOfTreePath(fs, path)
 		node := RebuiltNode{
-			Errs:    containers.Set[string]{badNode.Err: struct{}{}},
-			MinKey:  min,
-			MaxKey:  max,
-			InTrees: containers.Set[btrfsprim.ObjID]{path.Node(-1).FromTree: struct{}{}},
+			Errs: containers.NewSet[string](
+				badNode.Err,
+			),
+			MinKey: min,
+			MaxKey: max,
+			InTrees: containers.NewSet[btrfsprim.ObjID](
+				path.Node(-1).FromTree,
+			),
 			Node: btrfstree.Node{
 				Size:         sb.NodeSize,
 				ChecksumType: sb.ChecksumType,
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go
index b361606..badfdfc 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s3_reinit_test.go
@@ -21,14 +21,14 @@ import (
 func TestEncodeRebuiltNodes(t *testing.T) {
 	dat := map[btrfsvol.LogicalAddr]*rebuildnodes.RebuiltNode{
 		100007133184: {
-			Errs: containers.Set[string]{
-				"btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025": struct{}{},
-			},
+			Errs: containers.NewSet[string](
+				"btrfs.ReadNode: node@0x0000001748e3c000: expected generation\u003c=6596014 but claims to be generation=6596025",
+			),
 			MinKey: btrfsprim.Key{},
 			MaxKey: btrfsprim.Key{},
-			InTrees: containers.Set[btrfsprim.ObjID]{
-				257: struct{}{},
-			},
+			InTrees: containers.NewSet[btrfsprim.ObjID](
+				257,
+			),
 			Node: btrfstree.Node{},
 		},
 	}
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go
index 45fcc23..ef7d284 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/s4_reattach.go
@@ -31,7 +31,7 @@ func (a RebuiltNode) ContainsWholeRegion(min, max btrfsprim.Key) int {
 	}
 }
 
-func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.LogicalAddr]struct{}, rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error {
+func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes containers.Set[btrfsvol.LogicalAddr], rebuiltNodes map[btrfsvol.LogicalAddr]*RebuiltNode) error {
 	dlog.Info(ctx, "Attaching orphaned nodes to rebuilt nodes...")
 
 	sb, err := fs.Superblock()
@@ -91,12 +91,12 @@ func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.Logic
 		trees := make(containers.Set[btrfsprim.ObjID])
 		tree := foundRef.Data.Head.Owner
 		for {
-			trees[tree] = struct{}{}
+			trees.Insert(tree)
 			var ok bool
 			tree, ok = fs.ParentTree(tree)
 			if !ok {
 				// error; accept anything
-				trees[0] = struct{}{}
+				trees.Insert(0)
 				break
 			}
 			if tree == 0 {
@@ -113,7 +113,7 @@ func reAttachNodes(ctx context.Context, fs _FS, orphanedNodes map[btrfsvol.Logic
 				if parent.Node.Head.Generation < foundRef.Data.Head.Generation {
 					continue
 				}
-				if !trees.HasIntersection(parent.InTrees) {
+				if !trees.HasAny(parent.InTrees) {
 					continue
 				}
 				parent.BodyInternal = append(parent.BodyInternal, btrfstree.KeyPointer{
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
index ffb07c3..38742a0 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildnodes/visualizenodes.go
@@ -119,10 +119,10 @@ func VisualizeNodes(ctx context.Context, out io.Writer, fs *btrfs.FS, nodeScanRe
 		edges.Insert(edge.String())
 
 		// Return
-		if _, alreadyVisited := visitedNodes[addr]; alreadyVisited {
+		if visitedNodes.Has(addr) {
 			return iofs.SkipDir
 		}
-		visitedNodes[addr] = struct{}{}
+		visitedNodes.Insert(addr)
 		return err
 	}
 
diff --git a/lib/containers/rbtree_test.go b/lib/containers/rbtree_test.go
index 65cc78d..9841d26 100644
--- a/lib/containers/rbtree_test.go
+++ b/lib/containers/rbtree_test.go
@@ -49,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[NativeOrdered[K], V]) {
+func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet Set[K], tree *RBTree[NativeOrdered[K], V]) {
 	// 1. Every node is either red or black
 
 	// 2. The root is black.
@@ -142,7 +142,7 @@ func FuzzRBTree(f *testing.F) {
 				return NativeOrdered[uint8]{Val: x}
 			},
 		}
-		set := make(map[uint8]struct{})
+		set := make(Set[uint8])
 		checkRBTree(t, set, tree)
 		t.Logf("\n%s\n", tree.ASCIIArt())
 		for _, b := range dat {
@@ -151,7 +151,7 @@ func FuzzRBTree(f *testing.F) {
 			if ins {
 				t.Logf("Insert(%v)", val)
 				tree.Insert(val)
-				set[val] = struct{}{}
+				set.Insert(val)
 				t.Logf("\n%s\n", tree.ASCIIArt())
 				node := tree.Lookup(NativeOrdered[uint8]{Val: val})
 				require.NotNil(t, node)
diff --git a/lib/containers/set.go b/lib/containers/set.go
index 42e5ad2..1c525ca 100644
--- a/lib/containers/set.go
+++ b/lib/containers/set.go
@@ -13,6 +13,10 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
+// Set[T] is an unordered set of T.
+//
+// Despite Set[T] being unordered, T is required to be an ordered type
+// in order that a Set[T] have a deterministic JSON representation.
 type Set[T constraints.Ordered] map[T]struct{}
 
 var (
@@ -45,6 +49,14 @@ func (o *Set[T]) DecodeJSON(r io.RuneScanner) error {
 	})
 }
 
+func NewSet[T constraints.Ordered](values ...T) Set[T] {
+	ret := make(Set[T], len(values))
+	for _, value := range values {
+		ret.Insert(value)
+	}
+	return ret
+}
+
 func (o Set[T]) Insert(v T) {
 	o[v] = struct{}{}
 }
@@ -79,7 +91,12 @@ func (o Set[T]) TakeOne() T {
 	return zero
 }
 
-func (small Set[T]) HasIntersection(big Set[T]) bool {
+func (o Set[T]) Has(v T) bool {
+	_, has := o[v]
+	return has
+}
+
+func (small Set[T]) HasAny(big Set[T]) bool {
 	if len(big) < len(small) {
 		small, big = big, small
 	}