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