/*
   * This file is copyright 2001 Simon Tatham.
   * Rewritten from original source 2006 by Dan Merillat for use in u-boot.
   *
   * Original code can be found at:
   * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
   *
   * SPDX-License-Identifier:	MIT
   */
  
  #include <common.h>
  #include "jffs2_private.h"
  
  int sort_list(struct b_list *list)
  {
  	struct b_node *p, *q, *e, **tail;
  	int k, psize, qsize;
  
  	if (!list->listHead)
  		return 0;
  
  	for (k = 1; k < list->listCount; k *= 2) {
  		tail = &list->listHead;
  		for (p = q = list->listHead; p; p = q) {
  			/* step 'k' places from p; */
  			for (psize = 0; q && psize < k; psize++)
  				q = q->next;
  			qsize = k;
  
  			/* two lists, merge them. */
  			while (psize || (qsize && q)) {
  				/* merge the next element */
  				if (psize == 0 ||
  				    ((qsize && q) &&
  				     list->listCompare(p, q))) {
  					/* p is empty, or p > q, so q next */
  					e = q;
  					q = q->next;
  					qsize--;
  				} else {
  					e = p;
  					p = p->next;
  					psize--;
  				}
  				e->next = NULL; /* break accidental loops. */
  				*tail = e;
  				tail = &e->next;
  			}
  		}
  	}
  	return 0;
  }