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