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>

2 files changed, 139 insertions, 4 deletions

diff --git a/worker/types/thread.go b/worker/types/thread.go
index 4bcd843a..bfe3edc7 100644
--- a/worker/types/thread.go
+++ b/worker/types/thread.go
@@ -19,21 +19,29 @@ type Thread struct {
 	Deleted bool // if this flag is set the message was deleted
 }
 
+// AddChild appends the child node at the end of the existing children of t.
 func (t *Thread) AddChild(child *Thread) {
-	t.InsertCmp(child, func(child, iter *Thread) bool { return true })
+	t.InsertCmp(child, func(_, _ *Thread) bool { return true })
 }
 
+// OrderedInsert inserts the child node in ascending order among the existing
+// children based on their respective UIDs.
 func (t *Thread) OrderedInsert(child *Thread) {
 	t.InsertCmp(child, func(child, iter *Thread) bool { return child.Uid > iter.Uid })
 }
 
-func (t *Thread) InsertCmp(child *Thread, cmp func(*Thread, *Thread) bool) {
+// InsertCmp inserts child as a child node into t in ascending order. The
+// ascending order is determined by the bigger function that compares the child
+// with the existing children. It should return true when the child is bigger
+// than the other, and false otherwise.
+func (t *Thread) InsertCmp(child *Thread, bigger func(*Thread, *Thread) bool) {
 	if t.FirstChild == nil {
 		t.FirstChild = child
 	} else {
-		start := &Thread{Uid: t.FirstChild.Uid, NextSibling: t.FirstChild}
+		start := &Thread{NextSibling: t.FirstChild}
 		var iter *Thread
-		for iter = start; iter.NextSibling != nil && cmp(child, iter); iter = iter.NextSibling {
+		for iter = start; iter.NextSibling != nil &&
+			bigger(child, iter.NextSibling); iter = iter.NextSibling {
 		}
 		child.NextSibling = iter.NextSibling
 		iter.NextSibling = child
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)
+			}
+		})
+	}
+}