diff options
| -rw-r--r-- | fs/jffs2/Makefile | 1 | ||||
| -rw-r--r-- | fs/jffs2/jffs2_1pass.c | 47 | ||||
| -rw-r--r-- | fs/jffs2/jffs2_private.h | 4 | ||||
| -rw-r--r-- | fs/jffs2/mergesort.c | 52 |
4 files changed, 69 insertions, 35 deletions
diff --git a/fs/jffs2/Makefile b/fs/jffs2/Makefile index 4cb0600cf9..3625d748d5 100644 --- a/fs/jffs2/Makefile +++ b/fs/jffs2/Makefile @@ -10,4 +10,5 @@ obj-y += compr_rtime.o obj-y += compr_rubin.o obj-y += compr_zlib.o obj-y += jffs2_1pass.o +obj-$(CONFIG_SYS_JFFS2_SORT_FRAGMENTS) += mergesort.o obj-y += mini_inflate.o diff --git a/fs/jffs2/jffs2_1pass.c b/fs/jffs2/jffs2_1pass.c index 432579239d..64f55425df 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 diff --git a/fs/jffs2/jffs2_private.h b/fs/jffs2/jffs2_private.h index 658b325219..06b6ca2919 100644 --- a/fs/jffs2/jffs2_private.h +++ b/fs/jffs2/jffs2_private.h @@ -98,4 +98,8 @@ data_crc(struct jffs2_raw_inode *node) } } +#if defined(CONFIG_SYS_JFFS2_SORT_FRAGMENTS) +/* External merge sort. */ +int sort_list(struct b_list *list); +#endif #endif /* jffs2_private.h */ diff --git a/fs/jffs2/mergesort.c b/fs/jffs2/mergesort.c new file mode 100644 index 0000000000..6e633a1133 --- /dev/null +++ b/fs/jffs2/mergesort.c @@ -0,0 +1,52 @@ +/* + * This file is copyright 2001 Simon Tatham. + * Rewritten from original source 2006 by Dan Merillat for use in u-boot. + * + * Original code can be found at: + * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html + * + * SPDX-License-Identifier: MIT + */ + +#include <common.h> +#include "jffs2_private.h" + +int sort_list(struct b_list *list) +{ + struct b_node *p, *q, *e, **tail; + int k, psize, qsize; + + if (!list->listHead) + return 0; + + for (k = 1; k < list->listCount; k *= 2) { + tail = &list->listHead; + for (p = q = list->listHead; p; p = q) { + /* step 'k' places from p; */ + for (psize = 0; q && psize < k; psize++) + q = q->next; + qsize = k; + + /* two lists, merge them. */ + while (psize || (qsize && q)) { + /* merge the next element */ + if (psize == 0 || + ((qsize && q) && + list->listCompare(p, q))) { + /* p is empty, or p > q, so q next */ + e = q; + q = q->next; + qsize--; + } else { + e = p; + p = p->next; + psize--; + } + e->next = NULL; /* break accidental loops. */ + *tail = e; + tail = &e->next; + } + } + } + return 0; +} |
