THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

74 lines
1.5KB

  1. #include "cache.h"
  2. #include "mergesort.h"
  3. struct mergesort_sublist {
  4. void *ptr;
  5. unsigned long len;
  6. };
  7. static void *get_nth_next(void *list, unsigned long n,
  8. void *(*get_next_fn)(const void *))
  9. {
  10. while (n-- && list)
  11. list = get_next_fn(list);
  12. return list;
  13. }
  14. static void *pop_item(struct mergesort_sublist *l,
  15. void *(*get_next_fn)(const void *))
  16. {
  17. void *p = l->ptr;
  18. l->ptr = get_next_fn(l->ptr);
  19. l->len = l->ptr ? (l->len - 1) : 0;
  20. return p;
  21. }
  22. void *llist_mergesort(void *list,
  23. void *(*get_next_fn)(const void *),
  24. void (*set_next_fn)(void *, void *),
  25. int (*compare_fn)(const void *, const void *))
  26. {
  27. unsigned long l;
  28. if (!list)
  29. return NULL;
  30. for (l = 1; ; l *= 2) {
  31. void *curr;
  32. struct mergesort_sublist p, q;
  33. p.ptr = list;
  34. q.ptr = get_nth_next(p.ptr, l, get_next_fn);
  35. if (!q.ptr)
  36. break;
  37. p.len = q.len = l;
  38. if (compare_fn(p.ptr, q.ptr) > 0)
  39. list = curr = pop_item(&q, get_next_fn);
  40. else
  41. list = curr = pop_item(&p, get_next_fn);
  42. while (p.ptr) {
  43. while (p.len || q.len) {
  44. void *prev = curr;
  45. if (!p.len)
  46. curr = pop_item(&q, get_next_fn);
  47. else if (!q.len)
  48. curr = pop_item(&p, get_next_fn);
  49. else if (compare_fn(p.ptr, q.ptr) > 0)
  50. curr = pop_item(&q, get_next_fn);
  51. else
  52. curr = pop_item(&p, get_next_fn);
  53. set_next_fn(prev, curr);
  54. }
  55. p.ptr = q.ptr;
  56. p.len = l;
  57. q.ptr = get_nth_next(p.ptr, l, get_next_fn);
  58. q.len = q.ptr ? l : 0;
  59. }
  60. set_next_fn(curr, NULL);
  61. }
  62. return list;
  63. }