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