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 <[email protected]> --- 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
