1#include "lib_types.h" 2#include "lib_string.h" 3 4#define CHAR_BIT 8 5#define MAXSTACK (sizeof(int) * CHAR_BIT) 6 7static void qsexchange(void *a, void *b, size_t size) 8{ 9 size_t i; 10 11 /****************** 12 * exchange a,b * 13 ******************/ 14 15 /* revised to avoid new gcc warnings */ 16 int *ia, *ib; 17 char *ca, *cb; 18 19 ia = (int *)a; ib = (int *)b; 20 for (i = sizeof(int); i <= size; i += sizeof(int)) { 21 int t = *ia; 22 *(ia++) = *ib; 23 *(ib++) = t; 24 } 25 26 ca = (char *)ia; cb = (char *)ib; 27 for (i = i - sizeof(int) + 1; i <= size; i++) { 28 char t = *ca; 29 *(ca++) = *cb; 30 *(cb++) = t; 31 } 32} 33 34void qsort(void *base, size_t nmemb, size_t size, 35 int (*compar)(const void *, const void *)) 36{ 37 void *lbStack[MAXSTACK], *ubStack[MAXSTACK]; 38 int sp; 39 unsigned int offset; 40 41 /******************** 42 * ANSI-C qsort() * 43 ********************/ 44 45 lbStack[0] = (char *)base; 46 ubStack[0] = (char *)base + (nmemb-1)*size; 47 for (sp = 0; sp >= 0; sp--) { 48 char *lb, *ub, *m; 49 char *P, *i, *j; 50 51 lb = lbStack[sp]; 52 ub = ubStack[sp]; 53 54 while (lb < ub) { 55 56 /* select pivot and exchange with 1st element */ 57 offset = (ub - lb) >> 1; 58 P = lb + offset - offset % size; 59 qsexchange (lb, P, size); 60 61 /* partition into two segments */ 62 i = lb + size; 63 j = ub; 64 while (1) { 65 while (i < j && compar(lb, i) > 0) i += size; 66 while (j >= i && compar(j, lb) > 0) j -= size; 67 if (i >= j) break; 68 qsexchange (i, j, size); 69 j -= size; 70 i += size; 71 } 72 73 /* pivot belongs in A[j] */ 74 qsexchange (lb, j, size); 75 m = j; 76 77 /* keep processing smallest segment, and stack largest */ 78 if (m - lb <= ub - m) { 79 if (m + size < ub) { 80 lbStack[sp] = m + size; 81 ubStack[sp++] = ub; 82 } 83 ub = m - size; 84 } 85 else { 86 if (m - size > lb) { 87 lbStack[sp] = lb; 88 ubStack[sp++] = m - size; 89 } 90 lb = m + size; 91 } 92 } 93 } 94} 95 96