qsort.c 1.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172
  1. /*
  2. * Code adapted from uClibc-0.9.30.3
  3. *
  4. * It is therefore covered by the GNU LESSER GENERAL PUBLIC LICENSE
  5. * Version 2.1, February 1999
  6. *
  7. * Wolfgang Denk <wd@denx.de>
  8. */
  9. /* This code is derived from a public domain shell sort routine by
  10. * Ray Gardner and found in Bob Stout's snippets collection. The
  11. * original code is included below in an #if 0/#endif block.
  12. *
  13. * I modified it to avoid the possibility of overflow in the wgap
  14. * calculation, as well as to reduce the generated code size with
  15. * bcc and gcc. */
  16. #include <linux/types.h>
  17. #include <common.h>
  18. #include <exports.h>
  19. #include <sort.h>
  20. void qsort(void *base,
  21. size_t nel,
  22. size_t width,
  23. int (*comp)(const void *, const void *))
  24. {
  25. size_t wgap, i, j, k;
  26. char tmp;
  27. if ((nel > 1) && (width > 0)) {
  28. assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
  29. wgap = 0;
  30. do {
  31. wgap = 3 * wgap + 1;
  32. } while (wgap < (nel-1)/3);
  33. /* From the above, we know that either wgap == 1 < nel or */
  34. /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */
  35. wgap *= width; /* So this can not overflow if wnel doesn't. */
  36. nel *= width; /* Convert nel to 'wnel' */
  37. do {
  38. i = wgap;
  39. do {
  40. j = i;
  41. do {
  42. register char *a;
  43. register char *b;
  44. j -= wgap;
  45. a = j + ((char *)base);
  46. b = a + wgap;
  47. if ((*comp)(a, b) <= 0) {
  48. break;
  49. }
  50. k = width;
  51. do {
  52. tmp = *a;
  53. *a++ = *b;
  54. *b++ = tmp;
  55. } while (--k);
  56. } while (j >= wgap);
  57. i += width;
  58. } while (i < nel);
  59. wgap = (wgap - width)/3;
  60. } while (wgap);
  61. }
  62. }
  63. int strcmp_compar(const void *p1, const void *p2)
  64. {
  65. return strcmp(*(const char **)p1, *(const char **)p2);
  66. }