1 // SPDX-License-Identifier: MIT
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
8  */
9 
10 #include <common.h>
11 #include "jffs2_private.h"
12 
sort_list(struct b_list * list)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 }
52