JFFS2: Use merge sort when parsing filesystem
authorMark Tomlinson <mark.tomlinson@alliedtelesis.co.nz>
Wed, 1 Jul 2015 04:38:29 +0000 (16:38 +1200)
committerLothar Waßmann <LW@KARO-electronics.de>
Thu, 10 Sep 2015 06:24:12 +0000 (08:24 +0200)
commitb4639a2a67362b973a2fff3c611343b6310fc4e5
tree6ac561bcdd7071469a72c48ec7c9982f4dd94b27
parenta7faad418f87aa1e6d6c1ec96b894b52b231491b
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>
fs/jffs2/Makefile
fs/jffs2/jffs2_1pass.c
fs/jffs2/jffs2_private.h
fs/jffs2/mergesort.c [new file with mode: 0644]