yaffs_qsort.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163
  1. /*
  2. * Copyright (c) 1992, 1993
  3. * The Regents of the University of California. All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions
  7. * are met:
  8. * 1. Redistributions of source code must retain the above copyright
  9. * notice, this list of conditions and the following disclaimer.
  10. * 2. Redistributions in binary form must reproduce the above copyright
  11. * notice, this list of conditions and the following disclaimer in the
  12. * documentation and/or other materials provided with the distribution.
  13. * 3. Neither the name of the University nor the names of its contributors
  14. * may be used to endorse or promote products derived from this software
  15. * without specific prior written permission.
  16. *
  17. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27. * SUCH DAMAGE.
  28. */
  29. #include "yportenv.h"
  30. /* #include <linux/string.h> */
  31. /*
  32. * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  33. */
  34. #define swapcode(TYPE, parmi, parmj, n) do { \
  35. long i = (n) / sizeof(TYPE); \
  36. register TYPE *pi = (TYPE *) (parmi); \
  37. register TYPE *pj = (TYPE *) (parmj); \
  38. do { \
  39. register TYPE t = *pi; \
  40. *pi++ = *pj; \
  41. *pj++ = t; \
  42. } while (--i > 0); \
  43. } while (0)
  44. #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
  45. es % sizeof(long) ? 2 : es == sizeof(long) ? 0 : 1;
  46. static inline void
  47. swapfunc(char *a, char *b, int n, int swaptype)
  48. {
  49. if (swaptype <= 1)
  50. swapcode(long, a, b, n);
  51. else
  52. swapcode(char, a, b, n);
  53. }
  54. #define yswap(a, b) do { \
  55. if (swaptype == 0) { \
  56. long t = *(long *)(a); \
  57. *(long *)(a) = *(long *)(b); \
  58. *(long *)(b) = t; \
  59. } else \
  60. swapfunc(a, b, es, swaptype); \
  61. } while (0)
  62. #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
  63. static inline char *
  64. med3(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
  65. {
  66. return cmp(a, b) < 0 ?
  67. (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
  68. : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
  69. }
  70. #ifndef min
  71. #define min(a, b) (((a) < (b)) ? (a) : (b))
  72. #endif
  73. void
  74. yaffs_qsort(void *aa, size_t n, size_t es,
  75. int (*cmp)(const void *, const void *))
  76. {
  77. char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
  78. int d, r, swaptype, swap_cnt;
  79. register char *a = aa;
  80. loop: SWAPINIT(a, es);
  81. swap_cnt = 0;
  82. if (n < 7) {
  83. for (pm = (char *)a + es; pm < (char *) a + n * es; pm += es)
  84. for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
  85. pl -= es)
  86. yswap(pl, pl - es);
  87. return;
  88. }
  89. pm = (char *)a + (n / 2) * es;
  90. if (n > 7) {
  91. pl = (char *)a;
  92. pn = (char *)a + (n - 1) * es;
  93. if (n > 40) {
  94. d = (n / 8) * es;
  95. pl = med3(pl, pl + d, pl + 2 * d, cmp);
  96. pm = med3(pm - d, pm, pm + d, cmp);
  97. pn = med3(pn - 2 * d, pn - d, pn, cmp);
  98. }
  99. pm = med3(pl, pm, pn, cmp);
  100. }
  101. yswap(a, pm);
  102. pa = pb = (char *)a + es;
  103. pc = pd = (char *)a + (n - 1) * es;
  104. for (;;) {
  105. while (pb <= pc && (r = cmp(pb, a)) <= 0) {
  106. if (r == 0) {
  107. swap_cnt = 1;
  108. yswap(pa, pb);
  109. pa += es;
  110. }
  111. pb += es;
  112. }
  113. while (pb <= pc && (r = cmp(pc, a)) >= 0) {
  114. if (r == 0) {
  115. swap_cnt = 1;
  116. yswap(pc, pd);
  117. pd -= es;
  118. }
  119. pc -= es;
  120. }
  121. if (pb > pc)
  122. break;
  123. yswap(pb, pc);
  124. swap_cnt = 1;
  125. pb += es;
  126. pc -= es;
  127. }
  128. if (swap_cnt == 0) { /* Switch to insertion sort */
  129. for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
  130. for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
  131. pl -= es)
  132. yswap(pl, pl - es);
  133. return;
  134. }
  135. pn = (char *)a + n * es;
  136. r = min(pa - (char *)a, pb - pa);
  137. vecswap(a, pb - r, r);
  138. r = min((long)(pd - pc), (long)(pn - pd - es));
  139. vecswap(pb, pn - r, r);
  140. r = pb - pa;
  141. if (r > es)
  142. yaffs_qsort(a, r / es, es, cmp);
  143. r = pd - pc;
  144. if (r > es) {
  145. /* Iterate rather than recurse to save stack space */
  146. a = pn - r;
  147. n = r / es;
  148. goto loop;
  149. }
  150. /* yaffs_qsort(pn - r, r / es, es, cmp);*/
  151. }