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