Move lib/rbtree to lib/containers

6 files changed, 64 insertions, 64 deletions

diff --git a/lib/btrfs/btrfsvol/lvm.go b/lib/btrfs/btrfsvol/lvm.go
index ca46ad3..351cbe5 100644
--- a/lib/btrfs/btrfsvol/lvm.go
+++ b/lib/btrfs/btrfsvol/lvm.go
@@ -10,7 +10,7 @@ import (
 	"os"
 	"reflect"
 
-	"git.lukeshu.com/btrfs-progs-ng/lib/rbtree"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/util"
 )
 
@@ -19,8 +19,8 @@ type LogicalVolume[PhysicalVolume util.File[PhysicalAddr]] struct {
 
 	id2pv map[DeviceID]PhysicalVolume
 
-	logical2physical *rbtree.Tree[util.NativeOrdered[LogicalAddr], chunkMapping]
-	physical2logical map[DeviceID]*rbtree.Tree[util.NativeOrdered[PhysicalAddr], devextMapping]
+	logical2physical *containers.RBTree[util.NativeOrdered[LogicalAddr], chunkMapping]
+	physical2logical map[DeviceID]*containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]
 }
 
 var _ util.File[LogicalAddr] = (*LogicalVolume[util.File[PhysicalAddr]])(nil)
@@ -30,18 +30,18 @@ func (lv *LogicalVolume[PhysicalVolume]) init() {
 		lv.id2pv = make(map[DeviceID]PhysicalVolume)
 	}
 	if lv.logical2physical == nil {
-		lv.logical2physical = &rbtree.Tree[util.NativeOrdered[LogicalAddr], chunkMapping]{
+		lv.logical2physical = &containers.RBTree[util.NativeOrdered[LogicalAddr], chunkMapping]{
 			KeyFn: func(chunk chunkMapping) util.NativeOrdered[LogicalAddr] {
 				return util.NativeOrdered[LogicalAddr]{Val: chunk.LAddr}
 			},
 		}
 	}
 	if lv.physical2logical == nil {
-		lv.physical2logical = make(map[DeviceID]*rbtree.Tree[util.NativeOrdered[PhysicalAddr], devextMapping], len(lv.id2pv))
+		lv.physical2logical = make(map[DeviceID]*containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping], len(lv.id2pv))
 	}
 	for devid := range lv.id2pv {
 		if _, ok := lv.physical2logical[devid]; !ok {
-			lv.physical2logical[devid] = &rbtree.Tree[util.NativeOrdered[PhysicalAddr], devextMapping]{
+			lv.physical2logical[devid] = &containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]{
 				KeyFn: func(ext devextMapping) util.NativeOrdered[PhysicalAddr] {
 					return util.NativeOrdered[PhysicalAddr]{Val: ext.PAddr}
 				},
@@ -74,7 +74,7 @@ func (lv *LogicalVolume[PhysicalVolume]) AddPhysicalVolume(id DeviceID, dev Phys
 			lv, dev.Name(), other.Name(), id)
 	}
 	lv.id2pv[id] = dev
-	lv.physical2logical[id] = &rbtree.Tree[util.NativeOrdered[PhysicalAddr], devextMapping]{
+	lv.physical2logical[id] = &containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]{
 		KeyFn: func(ext devextMapping) util.NativeOrdered[PhysicalAddr] {
 			return util.NativeOrdered[PhysicalAddr]{Val: ext.PAddr}
 		},
@@ -173,8 +173,8 @@ func (lv *LogicalVolume[PhysicalVolume]) AddMapping(m Mapping) error {
 }
 
 func (lv *LogicalVolume[PhysicalVolume]) fsck() error {
-	physical2logical := make(map[DeviceID]*rbtree.Tree[util.NativeOrdered[PhysicalAddr], devextMapping])
-	if err := lv.logical2physical.Walk(func(node *rbtree.Node[chunkMapping]) error {
+	physical2logical := make(map[DeviceID]*containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping])
+	if err := lv.logical2physical.Walk(func(node *containers.RBNode[chunkMapping]) error {
 		chunk := node.Value
 		for _, stripe := range chunk.PAddrs {
 			if _, devOK := lv.id2pv[stripe.Dev]; !devOK {
@@ -182,7 +182,7 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error {
 					lv, stripe.Dev)
 			}
 			if _, exists := physical2logical[stripe.Dev]; !exists {
-				physical2logical[stripe.Dev] = &rbtree.Tree[util.NativeOrdered[PhysicalAddr], devextMapping]{
+				physical2logical[stripe.Dev] = &containers.RBTree[util.NativeOrdered[PhysicalAddr], devextMapping]{
 					KeyFn: func(ext devextMapping) util.NativeOrdered[PhysicalAddr] {
 						return util.NativeOrdered[PhysicalAddr]{Val: ext.PAddr}
 					},
@@ -216,7 +216,7 @@ func (lv *LogicalVolume[PhysicalVolume]) fsck() error {
 
 func (lv *LogicalVolume[PhysicalVolume]) Mappings() []Mapping {
 	var ret []Mapping
-	_ = lv.logical2physical.Walk(func(node *rbtree.Node[chunkMapping]) error {
+	_ = lv.logical2physical.Walk(func(node *containers.RBNode[chunkMapping]) error {
 		chunk := node.Value
 		var flags *BlockGroupFlags
 		if chunk.Flags != nil {
diff --git a/lib/btrfsprogs/btrfsutil/broken_btree.go b/lib/btrfsprogs/btrfsutil/broken_btree.go
index 2835b35..d2dc81c 100644
--- a/lib/btrfsprogs/btrfsutil/broken_btree.go
+++ b/lib/btrfsprogs/btrfsutil/broken_btree.go
@@ -14,7 +14,7 @@ import (
 
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs"
 	"git.lukeshu.com/btrfs-progs-ng/lib/btrfs/btrfsvol"
-	"git.lukeshu.com/btrfs-progs-ng/lib/rbtree"
+	"git.lukeshu.com/btrfs-progs-ng/lib/containers"
 	"git.lukeshu.com/btrfs-progs-ng/lib/util"
 )
 
@@ -24,7 +24,7 @@ type indexItem struct {
 }
 
 type cachedIndex struct {
-	Index *rbtree.Tree[btrfs.Key, indexItem]
+	Index *containers.RBTree[btrfs.Key, indexItem]
 	Err   error
 }
 
@@ -67,7 +67,7 @@ func NewBrokenTrees(ctx context.Context, inner *btrfs.FS) btrfs.Trees {
 	}
 }
 
-func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) (*rbtree.Tree[btrfs.Key, indexItem], error) {
+func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) (*containers.RBTree[btrfs.Key, indexItem], error) {
 	var treeRoot *btrfs.TreeRoot
 	var err error
 	if treeID == btrfs.ROOT_TREE_OBJECTID {
@@ -92,7 +92,7 @@ func (bt *brokenTrees) treeIndex(treeID btrfs.ObjID) (*rbtree.Tree[btrfs.Key, in
 	if err != nil {
 		cacheEntry.Err = err
 	} else {
-		cacheEntry.Index = &rbtree.Tree[btrfs.Key, indexItem]{
+		cacheEntry.Index = &containers.RBTree[btrfs.Key, indexItem]{
 			KeyFn: func(item indexItem) btrfs.Key {
 				return item.Key
 			},
@@ -196,7 +196,7 @@ func (bt *brokenTrees) TreeWalk(ctx context.Context, treeID btrfs.ObjID, errHand
 		return
 	}
 	var node *util.Ref[btrfsvol.LogicalAddr, btrfs.Node]
-	_ = index.Walk(func(indexItem *rbtree.Node[indexItem]) error {
+	_ = index.Walk(func(indexItem *containers.RBNode[indexItem]) error {
 		if ctx.Err() != nil {
 			return ctx.Err()
 		}
diff --git a/lib/rbtree/rbtree.go b/lib/containers/rbtree.go
index 25f3b1c..6bffc02 100644
--- a/lib/rbtree/rbtree.go
+++ b/lib/containers/rbtree.go
@@ -2,7 +2,7 @@
 //
 // SPDX-License-Identifier: GPL-2.0-or-later
 
-package rbtree
+package containers
 
 import (
 	"fmt"
@@ -18,31 +18,31 @@ const (
 	Red   = Color(true)
 )
 
-type Node[V any] struct {
-	Parent, Left, Right *Node[V]
+type RBNode[V any] struct {
+	Parent, Left, Right *RBNode[V]
 
 	Color Color
 
 	Value V
 }
 
-func (node *Node[V]) getColor() Color {
+func (node *RBNode[V]) getColor() Color {
 	if node == nil {
 		return Black
 	}
 	return node.Color
 }
 
-type Tree[K util.Ordered[K], V any] struct {
+type RBTree[K util.Ordered[K], V any] struct {
 	KeyFn func(V) K
-	root  *Node[V]
+	root  *RBNode[V]
 }
 
-func (t *Tree[K, V]) Walk(fn func(*Node[V]) error) error {
+func (t *RBTree[K, V]) Walk(fn func(*RBNode[V]) error) error {
 	return t.root.walk(fn)
 }
 
-func (node *Node[V]) walk(fn func(*Node[V]) error) error {
+func (node *RBNode[V]) walk(fn func(*RBNode[V]) error) error {
 	if node == nil {
 		return nil
 	}
@@ -78,13 +78,13 @@ func (node *Node[V]) walk(fn func(*Node[V]) error) error {
 //
 // Search is good for advanced lookup, like when a range of values is
 // acceptable.  For simple exact-value lookup, use Lookup.
-func (t *Tree[K, V]) Search(fn func(V) int) *Node[V] {
+func (t *RBTree[K, V]) Search(fn func(V) int) *RBNode[V] {
 	ret, _ := t.root.search(fn)
 	return ret
 }
 
-func (node *Node[V]) search(fn func(V) int) (exact, nearest *Node[V]) {
-	var prev *Node[V]
+func (node *RBNode[V]) search(fn func(V) int) (exact, nearest *RBNode[V]) {
+	var prev *RBNode[V]
 	for {
 		if node == nil {
 			return nil, prev
@@ -102,7 +102,7 @@ func (node *Node[V]) search(fn func(V) int) (exact, nearest *Node[V]) {
 	}
 }
 
-func (t *Tree[K, V]) exactKey(key K) func(V) int {
+func (t *RBTree[K, V]) exactKey(key K) func(V) int {
 	return func(val V) int {
 		valKey := t.KeyFn(val)
 		return key.Cmp(valKey)
@@ -111,17 +111,17 @@ func (t *Tree[K, V]) exactKey(key K) func(V) int {
 
 // Lookup looks up the value for an exact key.  If no such value
 // exists, nil is returned.
-func (t *Tree[K, V]) Lookup(key K) *Node[V] {
+func (t *RBTree[K, V]) Lookup(key K) *RBNode[V] {
 	return t.Search(t.exactKey(key))
 }
 
 // Min returns the minimum value stored in the tree, or nil if the
 // tree is empty.
-func (t *Tree[K, V]) Min() *Node[V] {
+func (t *RBTree[K, V]) Min() *RBNode[V] {
 	return t.root.min()
 }
 
-func (node *Node[V]) min() *Node[V] {
+func (node *RBNode[V]) min() *RBNode[V] {
 	if node == nil {
 		return nil
 	}
@@ -135,11 +135,11 @@ func (node *Node[V]) min() *Node[V] {
 
 // Max returns the maximum value stored in the tree, or nil if the
 // tree is empty.
-func (t *Tree[K, V]) Max() *Node[V] {
+func (t *RBTree[K, V]) Max() *RBNode[V] {
 	return t.root.max()
 }
 
-func (node *Node[V]) max() *Node[V] {
+func (node *RBNode[V]) max() *RBNode[V] {
 	if node == nil {
 		return nil
 	}
@@ -151,11 +151,11 @@ func (node *Node[V]) max() *Node[V] {
 	}
 }
 
-func (t *Tree[K, V]) Next(cur *Node[V]) *Node[V] {
+func (t *RBTree[K, V]) Next(cur *RBNode[V]) *RBNode[V] {
 	return cur.next()
 }
 
-func (cur *Node[V]) next() *Node[V] {
+func (cur *RBNode[V]) next() *RBNode[V] {
 	if cur.Right != nil {
 		return cur.Right.min()
 	}
@@ -166,11 +166,11 @@ func (cur *Node[V]) next() *Node[V] {
 	return parent
 }
 
-func (t *Tree[K, V]) Prev(cur *Node[V]) *Node[V] {
+func (t *RBTree[K, V]) Prev(cur *RBNode[V]) *RBNode[V] {
 	return cur.prev()
 }
 
-func (cur *Node[V]) prev() *Node[V] {
+func (cur *RBNode[V]) prev() *RBNode[V] {
 	if cur.Left != nil {
 		return cur.Left.max()
 	}
@@ -183,7 +183,7 @@ func (cur *Node[V]) prev() *Node[V] {
 
 // SearchRange is like Search, but returns all nodes that match the
 // function; assuming that they are contiguous.
-func (t *Tree[K, V]) SearchRange(fn func(V) int) []V {
+func (t *RBTree[K, V]) SearchRange(fn func(V) int) []V {
 	middle := t.Search(fn)
 	if middle == nil {
 		return nil
@@ -199,7 +199,7 @@ func (t *Tree[K, V]) SearchRange(fn func(V) int) []V {
 	return ret
 }
 
-func (t *Tree[K, V]) Equal(u *Tree[K, V]) bool {
+func (t *RBTree[K, V]) Equal(u *RBTree[K, V]) bool {
 	if (t == nil) != (u == nil) {
 		return false
 	}
@@ -208,13 +208,13 @@ func (t *Tree[K, V]) Equal(u *Tree[K, V]) bool {
 	}
 
 	var tSlice []V
-	_ = t.Walk(func(node *Node[V]) error {
+	_ = t.Walk(func(node *RBNode[V]) error {
 		tSlice = append(tSlice, node.Value)
 		return nil
 	})
 
 	var uSlice []V
-	_ = u.Walk(func(node *Node[V]) error {
+	_ = u.Walk(func(node *RBNode[V]) error {
 		uSlice = append(uSlice, node.Value)
 		return nil
 	})
@@ -222,7 +222,7 @@ func (t *Tree[K, V]) Equal(u *Tree[K, V]) bool {
 	return reflect.DeepEqual(tSlice, uSlice)
 }
 
-func (t *Tree[K, V]) parentChild(node *Node[V]) **Node[V] {
+func (t *RBTree[K, V]) parentChild(node *RBNode[V]) **RBNode[V] {
 	switch {
 	case node.Parent == nil:
 		return &t.root
@@ -235,7 +235,7 @@ func (t *Tree[K, V]) parentChild(node *Node[V]) **Node[V] {
 	}
 }
 
-func (t *Tree[K, V]) leftRotate(x *Node[V]) {
+func (t *RBTree[K, V]) leftRotate(x *RBNode[V]) {
 	//        p                        p
 	//        |                        |
 	//      +---+                    +---+
@@ -268,7 +268,7 @@ func (t *Tree[K, V]) leftRotate(x *Node[V]) {
 	x.Right = b
 }
 
-func (t *Tree[K, V]) rightRotate(y *Node[V]) {
+func (t *RBTree[K, V]) rightRotate(y *RBNode[V]) {
 	//           |                |
 	//         +---+            +---+
 	//         | y |            | x |
@@ -300,7 +300,7 @@ func (t *Tree[K, V]) rightRotate(y *Node[V]) {
 	y.Left = b
 }
 
-func (t *Tree[K, V]) Insert(val V) {
+func (t *RBTree[K, V]) Insert(val V) {
 	// Naive-insert
 
 	key := t.KeyFn(val)
@@ -310,7 +310,7 @@ func (t *Tree[K, V]) Insert(val V) {
 		return
 	}
 
-	node := &Node[V]{
+	node := &RBNode[V]{
 		Color:  Red,
 		Parent: parent,
 		Value:  val,
@@ -366,14 +366,14 @@ func (t *Tree[K, V]) Insert(val V) {
 	t.root.Color = Black
 }
 
-func (t *Tree[K, V]) transplant(old, new *Node[V]) {
+func (t *RBTree[K, V]) transplant(old, new *RBNode[V]) {
 	*t.parentChild(old) = new
 	if new != nil {
 		new.Parent = old.Parent
 	}
 }
 
-func (t *Tree[K, V]) Delete(key K) {
+func (t *RBTree[K, V]) Delete(key K) {
 	nodeToDelete := t.Lookup(key)
 	if nodeToDelete == nil {
 		return
@@ -382,8 +382,8 @@ func (t *Tree[K, V]) Delete(key K) {
 	// This is closely based on the algorithm presented in CLRS
 	// 3e.
 
-	var nodeToRebalance *Node[V]
-	var nodeToRebalanceParent *Node[V] // in case 'nodeToRebalance' is nil, which it can be
+	var nodeToRebalance *RBNode[V]
+	var nodeToRebalanceParent *RBNode[V] // in case 'nodeToRebalance' is nil, which it can be
 	needsRebalance := nodeToDelete.Color == Black
 
 	switch {
diff --git a/lib/rbtree/rbtree_test.go b/lib/containers/rbtree_test.go
index e6007e1..3360bc0 100644
--- a/lib/rbtree/rbtree_test.go
+++ b/lib/containers/rbtree_test.go
@@ -2,7 +2,7 @@
 //
 // SPDX-License-Identifier: GPL-2.0-or-later
 
-package rbtree
+package containers
 
 import (
 	"fmt"
@@ -17,13 +17,13 @@ import (
 	"git.lukeshu.com/btrfs-progs-ng/lib/util"
 )
 
-func (t *Tree[K, V]) ASCIIArt() string {
+func (t *RBTree[K, V]) ASCIIArt() string {
 	var out strings.Builder
 	t.root.asciiArt(&out, "", "", "")
 	return out.String()
 }
 
-func (node *Node[V]) String() string {
+func (node *RBNode[V]) String() string {
 	switch {
 	case node == nil:
 		return "nil"
@@ -34,7 +34,7 @@ func (node *Node[V]) String() string {
 	}
 }
 
-func (node *Node[V]) asciiArt(w io.Writer, u, m, l string) {
+func (node *RBNode[V]) asciiArt(w io.Writer, u, m, l string) {
 	if node == nil {
 		fmt.Fprintf(w, "%snil\n", m)
 		return
@@ -51,7 +51,7 @@ func (node *Node[V]) asciiArt(w io.Writer, u, m, l string) {
 	node.Left.asciiArt(w, l+"  |  ", l+"  `--", l+"     ")
 }
 
-func checkTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *Tree[util.NativeOrdered[K], V]) {
+func checkRBTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]struct{}, tree *RBTree[util.NativeOrdered[K], V]) {
 	// 1. Every node is either red or black
 
 	// 2. The root is black.
@@ -60,7 +60,7 @@ func checkTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]str
 	// 3. Every nil is black.
 
 	// 4. If a node is red, then both its children are black.
-	require.NoError(t, tree.Walk(func(node *Node[V]) error {
+	require.NoError(t, tree.Walk(func(node *RBNode[V]) error {
 		if node.getColor() == Red {
 			require.Equal(t, Black, node.Left.getColor())
 			require.Equal(t, Black, node.Right.getColor())
@@ -71,8 +71,8 @@ func checkTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]str
 	// 5. For each node, all simple paths from the node to
 	//    descendent leaves contain the same number of black
 	//    nodes.
-	var walkCnt func(node *Node[V], cnt int, leafFn func(int))
-	walkCnt = func(node *Node[V], cnt int, leafFn func(int)) {
+	var walkCnt func(node *RBNode[V], cnt int, leafFn func(int))
+	walkCnt = func(node *RBNode[V], cnt int, leafFn func(int)) {
 		if node.getColor() == Black {
 			cnt++
 		}
@@ -83,7 +83,7 @@ func checkTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]str
 		walkCnt(node.Left, cnt, leafFn)
 		walkCnt(node.Right, cnt, leafFn)
 	}
-	require.NoError(t, tree.Walk(func(node *Node[V]) error {
+	require.NoError(t, tree.Walk(func(node *RBNode[V]) error {
 		var cnts []int
 		walkCnt(node, 0, func(cnt int) {
 			cnts = append(cnts, cnt)
@@ -109,14 +109,14 @@ func checkTree[K constraints.Ordered, V any](t *testing.T, expectedSet map[K]str
 		return expectedOrder[i] < expectedOrder[j]
 	})
 	actOrder := make([]K, 0, len(expectedSet))
-	require.NoError(t, tree.Walk(func(node *Node[V]) error {
+	require.NoError(t, tree.Walk(func(node *RBNode[V]) error {
 		actOrder = append(actOrder, tree.KeyFn(node.Value).Val)
 		return nil
 	}))
 	require.Equal(t, expectedOrder, actOrder)
 }
 
-func FuzzTree(f *testing.F) {
+func FuzzRBTree(f *testing.F) {
 	Ins := uint8(0b0100_0000)
 	Del := uint8(0)
 
@@ -139,13 +139,13 @@ func FuzzTree(f *testing.F) {
 	})
 
 	f.Fuzz(func(t *testing.T, dat []uint8) {
-		tree := &Tree[util.NativeOrdered[uint8], uint8]{
+		tree := &RBTree[util.NativeOrdered[uint8], uint8]{
 			KeyFn: func(x uint8) util.NativeOrdered[uint8] {
 				return util.NativeOrdered[uint8]{Val: x}
 			},
 		}
 		set := make(map[uint8]struct{})
-		checkTree(t, set, tree)
+		checkRBTree(t, set, tree)
 		t.Logf("\n%s\n", tree.ASCIIArt())
 		for _, b := range dat {
 			ins := (b & 0b0100_0000) != 0
@@ -165,7 +165,7 @@ func FuzzTree(f *testing.F) {
 				t.Logf("\n%s\n", tree.ASCIIArt())
 				require.Nil(t, tree.Lookup(util.NativeOrdered[uint8]{Val: val}))
 			}
-			checkTree(t, set, tree)
+			checkRBTree(t, set, tree)
 		}
 	})
 }
diff --git a/lib/rbtree/testdata/fuzz/FuzzTree/be408ce7760bc8ced841300ea7e6bac1a1e9505b1535810083d18db95d86f489 b/lib/containers/testdata/fuzz/FuzzTree/be408ce7760bc8ced841300ea7e6bac1a1e9505b1535810083d18db95d86f489
index 40318c6..40318c6 100644
--- a/lib/rbtree/testdata/fuzz/FuzzTree/be408ce7760bc8ced841300ea7e6bac1a1e9505b1535810083d18db95d86f489
+++ b/lib/containers/testdata/fuzz/FuzzTree/be408ce7760bc8ced841300ea7e6bac1a1e9505b1535810083d18db95d86f489
diff --git a/lib/rbtree/testdata/fuzz/FuzzTree/f9e6421dacf921f7bb25d402bffbfdce114baad0b1c8b9a9189b5a97fda27e41 b/lib/containers/testdata/fuzz/FuzzTree/f9e6421dacf921f7bb25d402bffbfdce114baad0b1c8b9a9189b5a97fda27e41
index 238e44f..238e44f 100644
--- a/lib/rbtree/testdata/fuzz/FuzzTree/f9e6421dacf921f7bb25d402bffbfdce114baad0b1c8b9a9189b5a97fda27e41
+++ b/lib/containers/testdata/fuzz/FuzzTree/f9e6421dacf921f7bb25d402bffbfdce114baad0b1c8b9a9189b5a97fda27e41