blob: 6e633a11338f3d55981992cdb6cca9ce443f0ab1 [file] [log] [blame]
Mark Tomlinson10d3ac32015-07-01 16:38:29 +12001/*
2 * This file is copyright 2001 Simon Tatham.
3 * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
4 *
5 * Original code can be found at:
6 * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
7 *
8 * SPDX-License-Identifier: MIT
9 */
10
11#include <common.h>
12#include "jffs2_private.h"
13
14int sort_list(struct b_list *list)
15{
16 struct b_node *p, *q, *e, **tail;
17 int k, psize, qsize;
18
19 if (!list->listHead)
20 return 0;
21
22 for (k = 1; k < list->listCount; k *= 2) {
23 tail = &list->listHead;
24 for (p = q = list->listHead; p; p = q) {
25 /* step 'k' places from p; */
26 for (psize = 0; q && psize < k; psize++)
27 q = q->next;
28 qsize = k;
29
30 /* two lists, merge them. */
31 while (psize || (qsize && q)) {
32 /* merge the next element */
33 if (psize == 0 ||
34 ((qsize && q) &&
35 list->listCompare(p, q))) {
36 /* p is empty, or p > q, so q next */
37 e = q;
38 q = q->next;
39 qsize--;
40 } else {
41 e = p;
42 p = p->next;
43 psize--;
44 }
45 e->next = NULL; /* break accidental loops. */
46 *tail = e;
47 tail = &e->next;
48 }
49 }
50 }
51 return 0;
52}