containers.Set: Don't use constraints.Ordered

5 files changed, 62 insertions, 18 deletions

diff --git a/lib/btrfs/btrfsvol/chunk.go b/lib/btrfs/btrfsvol/chunk.go
index 8a2d439..5f1baa8 100644
--- a/lib/btrfs/btrfsvol/chunk.go
+++ b/lib/btrfs/btrfsvol/chunk.go
@@ -70,11 +70,11 @@ func (a chunkMapping) union(rest ...chunkMapping) (chunkMapping, error) {
 		}
 	}
 	// figure out the physical stripes (.PAddrs)
-	paddrs := make(map[QualifiedPhysicalAddr]struct{})
+	paddrs := make(containers.Set[QualifiedPhysicalAddr])
 	for _, chunk := range chunks {
 		offsetWithinRet := chunk.LAddr.Sub(ret.LAddr)
 		for _, stripe := range chunk.PAddrs {
-			paddrs[stripe.Add(-offsetWithinRet)] = struct{}{}
+			paddrs.Insert(stripe.Add(-offsetWithinRet))
 		}
 	}
 	ret.PAddrs = maps.Keys(paddrs)
diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go
index e12e53e..c7551fc 100644
--- a/lib/btrfs/btrfsvol/lvm.go
+++ b/lib/btrfs/btrfsvol/lvm.go
@@ -256,9 +256,7 @@ 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) {
+func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs containers.Set[QualifiedPhysicalAddr], maxlen AddrDelta) {
 	node := lv.logical2physical.Search(func(chunk chunkMapping) int {
 		return chunkMapping{LAddr: laddr, Size: 1}.cmpRange(chunk)
 	})
@@ -269,10 +267,10 @@ func (lv *LogicalVolume[PhysicalVolume]) Resolve(laddr LogicalAddr) (paddrs map[
 	chunk := node.Value
 
 	offsetWithinChunk := laddr.Sub(chunk.LAddr)
-	paddrs = make(map[QualifiedPhysicalAddr]struct{})
+	paddrs = make(containers.Set[QualifiedPhysicalAddr])
 	maxlen = chunk.Size - offsetWithinChunk
 	for _, stripe := range chunk.PAddrs {
-		paddrs[stripe.Add(offsetWithinChunk)] = struct{}{}
+		paddrs.Insert(stripe.Add(offsetWithinChunk))
 	}
 
 	return paddrs, maxlen
diff --git a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
index a638f7c..0e2d5a0 100644
--- a/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
+++ b/lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go
@@ -10,6 +10,7 @@ import (
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfsprogs/btrfsinspect"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/maps"
 )
 
@@ -21,14 +22,14 @@ type BlockGroup struct {
 
 func DedupBlockGroups(scanResults btrfsinspect.ScanDevicesResult) (map[btrfsvol.LogicalAddr]BlockGroup, error) {
 	// Dedup
-	bgsSet := make(map[BlockGroup]struct{}) // Can't use containers.Set because BlockGroup isn't ordered
+	bgsSet := make(containers.Set[BlockGroup])
 	for _, devResults := range scanResults {
 		for _, bg := range devResults.FoundBlockGroups {
-			bgsSet[BlockGroup{
+			bgsSet.Insert(BlockGroup{
 				LAddr: btrfsvol.LogicalAddr(bg.Key.ObjectID),
 				Size:  btrfsvol.AddrDelta(bg.Key.Offset),
 				Flags: bg.BG.Flags,
-			}] = struct{}{}
+			})
 		}
 	}
 
diff --git a/lib/containers/ordered.go b/lib/containers/ordered.go
index 038edf8..d918149 100644
--- a/lib/containers/ordered.go
+++ b/lib/containers/ordered.go
@@ -8,10 +8,12 @@ import (
 	"golang.org/x/exp/constraints"
 )
 
-type Ordered[T interface{ Cmp(T) int }] interface {
+type _Ordered[T any] interface {
 	Cmp(T) int
 }
 
+type Ordered[T _Ordered[T]] _Ordered[T]
+
 type NativeOrdered[T constraints.Ordered] struct {
 	Val T
 }
diff --git a/lib/containers/set.go b/lib/containers/set.go
index 1c525ca..d3f8ca7 100644
--- a/lib/containers/set.go
+++ b/lib/containers/set.go
@@ -5,27 +5,70 @@
 package containers
 
 import (
+	"fmt"
 	"io"
+	"sort"
 
 	"git.lukeshu.com/go/lowmemjson"
-	"golang.org/x/exp/constraints"
 
 	"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{}
+type Set[T comparable] map[T]struct{}
 
 var (
 	_ lowmemjson.Encodable = Set[int]{}
 	_ lowmemjson.Decodable = (*Set[int])(nil)
 )
 
+func cast[T any](x any) T { return x.(T) }
+
 func (o Set[T]) EncodeJSON(w io.Writer) error {
-	return lowmemjson.Encode(w, maps.SortedKeys(o))
+	var less func(a, b T) bool
+	var zero T
+	switch (any(zero)).(type) {
+	case _Ordered[T]:
+		less = func(a, b T) bool { return cast[_Ordered[T]](a).Cmp(b) < 0 }
+	// This is the constraints.Ordered list
+	case string:
+		less = func(a, b T) bool { return cast[string](a) < cast[string](b) }
+	case int:
+		less = func(a, b T) bool { return cast[int](a) < cast[int](b) }
+	case int8:
+		less = func(a, b T) bool { return cast[int8](a) < cast[int8](b) }
+	case int16:
+		less = func(a, b T) bool { return cast[int16](a) < cast[int16](b) }
+	case int32:
+		less = func(a, b T) bool { return cast[int32](a) < cast[int32](b) }
+	case int64:
+		less = func(a, b T) bool { return cast[int64](a) < cast[int64](b) }
+	case uint:
+		less = func(a, b T) bool { return cast[uint](a) < cast[uint](b) }
+	case uint8:
+		less = func(a, b T) bool { return cast[uint8](a) < cast[uint8](b) }
+	case uint16:
+		less = func(a, b T) bool { return cast[uint16](a) < cast[uint16](b) }
+	case uint32:
+		less = func(a, b T) bool { return cast[uint32](a) < cast[uint32](b) }
+	case uint64:
+		less = func(a, b T) bool { return cast[uint64](a) < cast[uint64](b) }
+	case uintptr:
+		less = func(a, b T) bool { return cast[uintptr](a) < cast[uintptr](b) }
+	case float32:
+		less = func(a, b T) bool { return cast[float32](a) < cast[float32](b) }
+	case float64:
+		less = func(a, b T) bool { return cast[float64](a) < cast[float64](b) }
+	default:
+		less = func(a, b T) bool { return fmt.Sprint(a) < fmt.Sprint(b) }
+	}
+
+	keys := maps.Keys(o)
+	sort.Slice(keys, func(i, j int) bool {
+		return less(keys[i], keys[j])
+	})
+
+	return lowmemjson.Encode(w, keys)
 }
 
 func (o *Set[T]) DecodeJSON(r io.RuneScanner) error {
@@ -49,7 +92,7 @@ func (o *Set[T]) DecodeJSON(r io.RuneScanner) error {
 	})
 }
 
-func NewSet[T constraints.Ordered](values ...T) Set[T] {
+func NewSet[T comparable](values ...T) Set[T] {
 	ret := make(Set[T], len(values))
 	for _, value := range values {
 		ret.Insert(value)