JFFS2: Use merge sort when parsing filesystem

[karo-tx-uboot.git] / fs / jffs2 / mergesort.c

diff --git a/fs/jffs2/mergesort.c b/fs/jffs2/mergesort.c
new file mode 100644 (file)
index 0000000..6e633a1
--- /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;
+}