diff options
author | Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz> | 2015-07-01 04:38:29 (GMT) |
---|---|---|
committer | Tom Rini <trini@konsulko.com> | 2015-08-13 00:47:32 (GMT) |
commit | 10d3ac346f54ab9526cd352239a5906ee2b92fee (patch) | |
tree | c3dc2f4c0df60a876aba4de9b962bd84d6b570e5 /fs/jffs2/jffs2_1pass.c | |
parent | 54a883840be500cbcda4903118dd571e4532e83f (diff) | |
download | u-boot-fsl-qoriq-10d3ac346f54ab9526cd352239a5906ee2b92fee.tar.xz |
JFFS2: Use merge sort when parsing filesystem
When building the file system the existing code does an insertion into
a linked list. It attempts to speed this up by keeping a pointer to
where the last entry was inserted but it's still slow.
Now the nodes are just inserted into the list without searching
through for the correct place. This unsorted list is then sorted once
using mergesort after all the entries have been added to the list.
This speeds up the scanning of the flash file system considerably.
Signed-off-by: Mark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
Diffstat (limited to 'fs/jffs2/jffs2_1pass.c')
-rw-r--r-- | fs/jffs2/jffs2_1pass.c | 47 |
1 files changed, 12 insertions, 35 deletions
diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c index 4325792..64f5542 100644 --- a/fs/jffs2/jffs2_1pass.c +++ b/fs/jffs2/jffs2_1pass.c @@ -545,49 +545,19 @@ static struct b_node * insert_node(struct b_list *list, u32 offset) { struct b_node *new; -#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS - struct b_node *b, *prev; -#endif if (!(new = add_node(list))) { putstr("add_node failed!\r\n"); return NULL; } new->offset = offset; + new->next = NULL; -#ifdef CONFIG_SYS_JFFS2_SORT_FRAGMENTS - if (list->listTail != NULL && list->listCompare(new, list->listTail)) - prev = list->listTail; - else if (list->listLast != NULL && list->listCompare(new, list->listLast)) - prev = list->listLast; + if (list->listTail != NULL) + list->listTail->next = new; else - prev = NULL; - - for (b = (prev ? prev->next : list->listHead); - b != NULL && list->listCompare(new, b); - prev = b, b = b->next) { - list->listLoops++; - } - if (b != NULL) - list->listLast = prev; - - if (b != NULL) { - new->next = b; - if (prev != NULL) - prev->next = new; - else - list->listHead = new; - } else -#endif - { - new->next = (struct b_node *) NULL; - if (list->listTail != NULL) { - list->listTail->next = new; - list->listTail = new; - } else { - list->listTail = list->listHead = new; - } - } + list->listHead = new; + list->listTail = new; return new; } @@ -1800,6 +1770,13 @@ jffs2_1pass_build_lists(struct part_info * part) } free(buf); +#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS) + /* + * Sort the lists. + */ + sort_list(&pL->frag); + sort_list(&pL->dir); +#endif putstr("\b\b done.\r\n"); /* close off the dots */ /* We don't care if malloc failed - then each read operation will |