spi: kirkwood: add orion-spi compatible string
[oweals/u-boot.git] / fs / jffs2 / mergesort.c
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 }