]>
Commit | Line | Data |
---|---|---|
10d3ac34 MT |
1 | /* |
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 | ||
14 | int 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 | } |