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 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