qsort.c 1.7 KB

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