diff options
| -rw-r--r-- | lib/btrfs/btrfsvol/chunk.go | 4 | ||||
| -rw-r--r-- | lib/btrfs/btrfsvol/lvm.go | 8 | ||||
| -rw-r--r-- | lib/btrfsprogs/btrfsinspect/rebuildmappings/blockgroups.go | 7 | ||||
| -rw-r--r-- | lib/containers/ordered.go | 4 | ||||
| -rw-r--r-- | lib/containers/set.go | 57 |
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) |