From 952b677bf7f10da93673e3671f764c54c454bbfe Mon Sep 17 00:00:00 2001
From: Luke Shumaker <lukeshu@lukeshu.com>
Date: Wed, 13 Jul 2022 20:41:10 -0600
Subject: Move ordered.go to lib/containers

Something about this trips a stack overflow in golangci-lint, so upgrade
golangci-lint to a commit that fixes this.
---
 lib/containers/ordered.go     | 41 +++++++++++++++++++++++++++++++++++++++++
 lib/containers/rbtree.go      |  2 +-
 lib/containers/rbtree_test.go | 18 ++++++++----------
 3 files changed, 50 insertions(+), 11 deletions(-)
 create mode 100644 lib/containers/ordered.go

(limited to 'lib/containers')

diff --git a/lib/containers/ordered.go b/lib/containers/ordered.go
new file mode 100644
index 0000000..c5a3ec5
--- /dev/null
+++ b/lib/containers/ordered.go
@@ -0,0 +1,41 @@
+// Copyright (C) 2022  Luke Shumaker <lukeshu@lukeshu.com>
+//
+// SPDX-License-Identifier: GPL-2.0-or-later
+
+package containers
+
+import (
+	"golang.org/x/exp/constraints"
+)
+
+func CmpUint[T constraints.Unsigned](a, b T) int {
+	switch {
+	case a < b:
+		return -1
+	case a == b:
+		return 0
+	default:
+		return 1
+	}
+}
+
+type Ordered[T interface{ Cmp(T) int }] interface {
+	Cmp(T) int
+}
+
+type NativeOrdered[T constraints.Ordered] struct {
+	Val T
+}
+
+func (a NativeOrdered[T]) Cmp(b NativeOrdered[T]) int {
+	switch {
+	case a.Val < b.Val:
+		return -1
+	case a.Val > b.Val:
+		return 1
+	default:
+		return 0
+	}
+}
+
+var _ Ordered[NativeOrdered[int]] = NativeOrdered[int]{}
diff --git a/lib/containers/rbtree.go b/lib/containers/rbtree.go
index 6bffc02..64a679e 100644
--- a/lib/containers/rbtree.go
+++ b/lib/containers/rbtree.go
@@ -33,7 +33,7 @@ func (node *RBNode[V]) getColor() Color {
 	return node.Color
 }
 
-type RBTree[K util.Ordered[K], V any] struct {
+type RBTree[K Ordered[K], V any] struct {
 	KeyFn func(V) K
 	root  *RBNode[V]
 }
diff --git a/lib/containers/rbtree_test.go b/lib/containers/rbtree_test.go
index 3360bc0..65cc78d 100644
--- a/lib/containers/rbtree_test.go
+++ b/lib/containers/rbtree_test.go
@@ -13,8 +13,6 @@ import (
 
 	"github.com/stretchr/testify/require"
 	"golang.org/x/exp/constraints"
-
-	"git.lukeshu.com/btrfs-progs-ng/lib/util"
 )
 
 func (t *RBTree[K, V]) ASCIIArt() string {
@@ -51,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[util.NativeOrdered[K], V]) {
+func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *RBTree[NativeOrdered[K], V]) {
 	// 1. Every node is either red or black
 
 	// 2. The root is black.
@@ -101,7 +99,7 @@ func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]s
 	expectedOrder := make([]K, 0, len(expectedSet))
 	for k := range expectedSet {
 		expectedOrder = append(expectedOrder, k)
-		node := tree.Lookup(util.NativeOrdered[K]{Val: k})
+		node := tree.Lookup(NativeOrdered[K]{Val: k})
 		require.NotNil(t, tree, node)
 		require.Equal(t, k, tree.KeyFn(node.Value).Val)
 	}
@@ -139,9 +137,9 @@ func FuzzRBTree(f *testing.F) {
 	})
 
 	f.Fuzz(func(t *testing.T, dat []uint8) {
-		tree := &RBTree[util.NativeOrdered[uint8], uint8]{
-			KeyFn: func(x uint8) util.NativeOrdered[uint8] {
-				return util.NativeOrdered[uint8]{Val: x}
+		tree := &RBTree[NativeOrdered[uint8], uint8]{
+			KeyFn: func(x uint8) NativeOrdered[uint8] {
+				return NativeOrdered[uint8]{Val: x}
 			},
 		}
 		set := make(map[uint8]struct{})
@@ -155,15 +153,15 @@ func FuzzRBTree(f *testing.F) {
 				tree.Insert(val)
 				set[val] = struct{}{}
 				t.Logf("\n%s\n", tree.ASCIIArt())
-				node := tree.Lookup(util.NativeOrdered[uint8]{Val: val})
+				node := tree.Lookup(NativeOrdered[uint8]{Val: val})
 				require.NotNil(t, node)
 				require.Equal(t, val, node.Value)
 			} else {
 				t.Logf("Delete(%v)", val)
-				tree.Delete(util.NativeOrdered[uint8]{Val: val})
+				tree.Delete(NativeOrdered[uint8]{Val: val})
 				delete(set, val)
 				t.Logf("\n%s\n", tree.ASCIIArt())
-				require.Nil(t, tree.Lookup(util.NativeOrdered[uint8]{Val: val}))
+				require.Nil(t, tree.Lookup(NativeOrdered[uint8]{Val: val}))
 			}
 			checkRBTree(t, set, tree)
 		}
-- 
cgit v1.2.3-2-g168b