[PATCH] erofs-utils: lib: introduce the merge sort algorithm for dentries

[Hongzhen Luo]

Currently, malloc(), qsort() and free() are used to sort the dentries
in the directory. This patch reuses the existing `dir->i_subdirs` list and
the merge sort to achieve the same objective. This may avoid the potential
performance degradation when using malloc() and free().

Signed-off-by: Hongzhen Luo <hongzhen at linux.alibaba.com>
---
 lib/inode.c | 111 +++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 96 insertions(+), 15 deletions(-)

diff --git a/lib/inode.c b/lib/inode.c
index 128c051..2283fc0 100644
--- a/lib/inode.c
+++ b/lib/inode.c
@@ -234,27 +234,108 @@ int erofs_init_empty_dir(struct erofs_inode *dir)
 	return 0;
 }
 
+/* given list p and q that are two circles, return a merged circle */
+static struct list_head *erofs_subdirs_merge(struct list_head *p,
+					     struct list_head *q)
+{
+	struct list_head *cur, *ret = NULL;
+	struct erofs_dentry *d1, *d2;
+
+	if (p)
+		p->prev->next = NULL;
+	if (q)
+		q->prev->next = NULL;
+
+	while (p || q) {
+		d1 = d2 = NULL;
+		if (p)
+			d1 = container_of(p, struct erofs_dentry, d_child);
+		if (q)
+			d2 = container_of(q, struct erofs_dentry, d_child);
+		if (d1 && d2) {
+			if (comp_subdir(&d1, &d2) < 0) {
+				cur = p;
+				p = p->next;
+			} else {
+				cur = q;
+				q = q->next;
+			}
+		} else if (d1) {
+			cur = p;
+			p = p->next;
+		} else {
+			cur = q;
+			q = q->next;
+		}
+		if (!ret) {
+			ret = cur;
+			init_list_head(ret);
+		} else
+			list_add_tail(cur, ret);
+	}
+	return ret;
+}
+
+static struct list_head *erofs_subdirs_sort(struct list_head *lst,
+					    unsigned int nr_subdirs)
+{
+	struct list_head *p, *q;
+	int i;
+
+	if (!lst || !nr_subdirs) {
+		erofs_err("invalid lst or nr_subdirs");
+		return NULL;
+	}
+	if (nr_subdirs == 1) {
+		init_list_head(lst);
+		return lst;
+	}
+	p = lst;
+	for (i = 0; i < nr_subdirs / 2 - 1; i ++) {
+		p = p->next;
+	}
+	q = p->next;
+
+	/* split into two circles */
+	q->prev = lst->prev;
+	lst->prev->next = q;
+	lst->prev = p;
+	p->next = lst;
+
+	p = erofs_subdirs_sort(p, nr_subdirs / 2);
+	q = erofs_subdirs_sort(q, nr_subdirs - nr_subdirs / 2);
+	return erofs_subdirs_merge(p, q);
+}
+
+static void erofs_sort_subdirs_list(struct list_head *head,
+				    unsigned int nr_subdirs)
+{
+	struct list_head *lst;
+
+	if (!head || nr_subdirs < 2) {
+		erofs_err("nr_subdirs should >= 2");
+		return;
+	}
+	lst = erofs_subdirs_sort(head->next, nr_subdirs);
+	if (!lst) {
+		erofs_err("fail to sort subdirs");
+		return;
+	}
+	/* attach the head to the sorted list */
+	lst->prev->next = head;
+	head->prev = lst->prev;
+	lst->prev = head;
+	head->next = lst;
+}
+
 static int erofs_prepare_dir_file(struct erofs_inode *dir,
 				  unsigned int nr_subdirs)
 {
 	struct erofs_sb_info *sbi = dir->sbi;
-	struct erofs_dentry *d, *n, **sorted_d;
-	unsigned int i;
+	struct erofs_dentry *d;
 	unsigned int d_size = 0;
 
-	sorted_d = malloc(nr_subdirs * sizeof(d));
-	if (!sorted_d)
-		return -ENOMEM;
-	i = 0;
-	list_for_each_entry_safe(d, n, &dir->i_subdirs, d_child) {
-		list_del(&d->d_child);
-		sorted_d[i++] = d;
-	}
-	DBG_BUGON(i != nr_subdirs);
-	qsort(sorted_d, nr_subdirs, sizeof(d), comp_subdir);
-	for (i = 0; i < nr_subdirs; i++)
-		list_add_tail(&sorted_d[i]->d_child, &dir->i_subdirs);
-	free(sorted_d);
+	erofs_sort_subdirs_list(&dir->i_subdirs, nr_subdirs);
 
 	/* let's calculate dir size */
 	list_for_each_entry(d, &dir->i_subdirs, d_child) {
-- 
2.43.5