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.

63 lines
1.2KB

  1. #include "git-compat-util.h"
  2. /*
  3. * A merge sort implementation, simplified from the qsort implementation
  4. * by Mike Haertel, which is a part of the GNU C Library.
  5. */
  6. static void msort_with_tmp(void *b, size_t n, size_t s,
  7. int (*cmp)(const void *, const void *),
  8. char *t)
  9. {
  10. char *tmp;
  11. char *b1, *b2;
  12. size_t n1, n2;
  13. if (n <= 1)
  14. return;
  15. n1 = n / 2;
  16. n2 = n - n1;
  17. b1 = b;
  18. b2 = (char *)b + (n1 * s);
  19. msort_with_tmp(b1, n1, s, cmp, t);
  20. msort_with_tmp(b2, n2, s, cmp, t);
  21. tmp = t;
  22. while (n1 > 0 && n2 > 0) {
  23. if (cmp(b1, b2) <= 0) {
  24. memcpy(tmp, b1, s);
  25. tmp += s;
  26. b1 += s;
  27. --n1;
  28. } else {
  29. memcpy(tmp, b2, s);
  30. tmp += s;
  31. b2 += s;
  32. --n2;
  33. }
  34. }
  35. if (n1 > 0)
  36. memcpy(tmp, b1, n1 * s);
  37. memcpy(b, t, (n - n2) * s);
  38. }
  39. void git_stable_qsort(void *b, size_t n, size_t s,
  40. int (*cmp)(const void *, const void *))
  41. {
  42. const size_t size = st_mult(n, s);
  43. char buf[1024];
  44. if (size < sizeof(buf)) {
  45. /* The temporary array fits on the small on-stack buffer. */
  46. msort_with_tmp(b, n, s, cmp, buf);
  47. } else {
  48. /* It's somewhat large, so malloc it. */
  49. char *tmp = xmalloc(size);
  50. msort_with_tmp(b, n, s, cmp, tmp);
  51. free(tmp);
  52. }
  53. }