qsort.c 1.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
  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 <exports.h>
  18. #if 0
  19. #include <assert.h>
  20. #else
  21. #define assert(arg)
  22. #endif
  23. void qsort(void *base,
  24. size_t nel,
  25. size_t width,
  26. int (*comp)(const void *, const void *))
  27. {
  28. size_t wgap, i, j, k;
  29. char tmp;
  30. if ((nel > 1) && (width > 0)) {
  31. assert(nel <= ((size_t)(-1)) / width); /* check for overflow */
  32. wgap = 0;
  33. do {
  34. wgap = 3 * wgap + 1;
  35. } while (wgap < (nel-1)/3);
  36. /* From the above, we know that either wgap == 1 < nel or */
  37. /* ((wgap-1)/3 < (int) ((nel-1)/3) <= (nel-1)/3 ==> wgap < nel. */
  38. wgap *= width; /* So this can not overflow if wnel doesn't. */
  39. nel *= width; /* Convert nel to 'wnel' */
  40. do {
  41. i = wgap;
  42. do {
  43. j = i;
  44. do {
  45. register char *a;
  46. register char *b;
  47. j -= wgap;
  48. a = j + ((char *)base);
  49. b = a + wgap;
  50. if ((*comp)(a, b) <= 0) {
  51. break;
  52. }
  53. k = width;
  54. do {
  55. tmp = *a;
  56. *a++ = *b;
  57. *b++ = tmp;
  58. } while (--k);
  59. } while (j >= wgap);
  60. i += width;
  61. } while (i < nel);
  62. wgap = (wgap - width)/3;
  63. } while (wgap);
  64. }
  65. }
  66. int strcmp_compar(const void *p1, const void *p2)
  67. {
  68. return strcmp(*(const char **)p1, *(const char **)p2);
  69. }