fs/jffs2/mergesort.c

   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 }