qsort.c 1.6 KB

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