From 4cf96270f135fb31411d933ab4b686fe4e4900cf Mon Sep 17 00:00:00 2001
From: Koni Marti <koni.marti@gmail.com>
Date: Wed, 2 Nov 2022 22:26:51 +0100
Subject: threads: fix ordered insert of sibling nodes

Fix the ordered insert for multiple siblings when using client-side
threading. When there are more than two siblings already in the list,
the third element will not be inserted in proper order.

Add tests and better documention for the insert node functions.

Fixes: 5eac8d60 ("thread: add method to append new node")
Signed-off-by: Koni Marti <koni.marti@gmail.com>
Acked-by: Tim Culverhouse <tim@timculverhouse.com>
---
 worker/types/thread_test.go | 127 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 127 insertions(+)

(limited to 'worker/types/thread_test.go')

diff --git a/worker/types/thread_test.go b/worker/types/thread_test.go
index b3c39322..669803d8 100644
--- a/worker/types/thread_test.go
+++ b/worker/types/thread_test.go
@@ -103,3 +103,130 @@ func TestNewWalk(t *testing.T) {
 		return nil
 	})
 }
+
+func uidSeq(tree *Thread) string {
+	var seq []string
+	tree.Walk(func(t *Thread, _ int, _ error) error {
+		seq = append(seq, fmt.Sprintf("%d", t.Uid))
+		return nil
+	})
+	return strings.Join(seq, ".")
+}
+
+func TestThread_AddChild(t *testing.T) {
+	tests := []struct {
+		name string
+		seq  []int
+		want string
+	}{
+		{
+			name: "ascending",
+			seq:  []int{1, 2, 3, 4, 5, 6},
+			want: "0.1.2.3.4.5.6",
+		},
+		{
+			name: "descending",
+			seq:  []int{6, 5, 4, 3, 2, 1},
+			want: "0.6.5.4.3.2.1",
+		},
+	}
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			tree := &Thread{Uid: 0}
+			for _, i := range test.seq {
+				tree.AddChild(&Thread{Uid: uint32(i)})
+			}
+			if got := uidSeq(tree); got != test.want {
+				t.Errorf("got: %s, but wanted: %s", got,
+					test.want)
+			}
+		})
+	}
+}
+
+func TestThread_OrderedInsert(t *testing.T) {
+	tests := []struct {
+		name string
+		seq  []int
+		want string
+	}{
+		{
+			name: "ascending",
+			seq:  []int{1, 2, 3, 4, 5, 6},
+			want: "0.1.2.3.4.5.6",
+		},
+		{
+			name: "descending",
+			seq:  []int{6, 5, 4, 3, 2, 1},
+			want: "0.1.2.3.4.5.6",
+		},
+		{
+			name: "mixed",
+			seq:  []int{2, 1, 6, 3, 4, 5},
+			want: "0.1.2.3.4.5.6",
+		},
+	}
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			tree := &Thread{Uid: 0}
+			for _, i := range test.seq {
+				tree.OrderedInsert(&Thread{Uid: uint32(i)})
+			}
+			if got := uidSeq(tree); got != test.want {
+				t.Errorf("got: %s, but wanted: %s", got,
+					test.want)
+			}
+		})
+	}
+}
+
+func TestThread_InsertCmd(t *testing.T) {
+	tests := []struct {
+		name string
+		seq  []int
+		want string
+	}{
+		{
+			name: "ascending",
+			seq:  []int{1, 2, 3, 4, 5, 6},
+			want: "0.6.4.2.1.3.5",
+		},
+		{
+			name: "descending",
+			seq:  []int{6, 5, 4, 3, 2, 1},
+			want: "0.6.4.2.1.3.5",
+		},
+		{
+			name: "mixed",
+			seq:  []int{2, 1, 6, 3, 4, 5},
+			want: "0.6.4.2.1.3.5",
+		},
+	}
+	sortMap := map[uint32]int{
+		uint32(6): 1,
+		uint32(4): 2,
+		uint32(2): 3,
+		uint32(1): 4,
+		uint32(3): 5,
+		uint32(5): 6,
+	}
+
+	// bigger compares the new child with the next node and returns true if
+	// the child node is bigger and false otherwise.
+	bigger := func(newNode, nextChild *Thread) bool {
+		return sortMap[newNode.Uid] > sortMap[nextChild.Uid]
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			tree := &Thread{Uid: 0}
+			for _, i := range test.seq {
+				tree.InsertCmp(&Thread{Uid: uint32(i)}, bigger)
+			}
+			if got := uidSeq(tree); got != test.want {
+				t.Errorf("got: %s, but wanted: %s", got,
+					test.want)
+			}
+		})
+	}
+}
-- 
cgit