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>

1 files changed, 127 insertions, 0 deletions

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)
+			}
+		})
+	}
+}