blob: fca77aa651149fc80da4cd2405308f3f633134c6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
// SPDX-License-Identifier: MIT
/*
* 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
*/
#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;
}
|
