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