]>
git.ipfire.org Git - thirdparty/u-boot.git/blob - fs/jffs2/mergesort.c
1 // SPDX-License-Identifier: MIT
3 * This file is copyright 2001 Simon Tatham.
4 * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
6 * Original code can be found at:
7 * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
11 #include "jffs2_private.h"
13 int sort_list(struct b_list
*list
)
15 struct b_node
*p
, *q
, *e
, **tail
;
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
++)
29 /* two lists, merge them. */
30 while (psize
|| (qsize
&& q
)) {
31 /* merge the next element */
34 list
->listCompare(p
, q
))) {
35 /* p is empty, or p > q, so q next */
44 e
->next
= NULL
; /* break accidental loops. */