mergesort.c 1.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
  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. #include <common.h>
  10. #include "jffs2_private.h"
  11. int sort_list(struct b_list *list)
  12. {
  13. struct b_node *p, *q, *e, **tail;
  14. int k, psize, qsize;
  15. if (!list->listHead)
  16. return 0;
  17. for (k = 1; k < list->listCount; k *= 2) {
  18. tail = &list->listHead;
  19. for (p = q = list->listHead; p; p = q) {
  20. /* step 'k' places from p; */
  21. for (psize = 0; q && psize < k; psize++)
  22. q = q->next;
  23. qsize = k;
  24. /* two lists, merge them. */
  25. while (psize || (qsize && q)) {
  26. /* merge the next element */
  27. if (psize == 0 ||
  28. ((qsize && q) &&
  29. list->listCompare(p, q))) {
  30. /* p is empty, or p > q, so q next */
  31. e = q;
  32. q = q->next;
  33. qsize--;
  34. } else {
  35. e = p;
  36. p = p->next;
  37. psize--;
  38. }
  39. e->next = NULL; /* break accidental loops. */
  40. *tail = e;
  41. tail = &e->next;
  42. }
  43. }
  44. }
  45. return 0;
  46. }