Back to index

plt-scheme  4.2.1
my_qsort.c
Go to the documentation of this file.
00001 
00002 #if defined(sun) || defined(__sun) || defined(__sun__)
00003 /* Long ago, I became convinced that Sun's qsort() was broken.
00004    Probably it isn't any more, but I'm still more comfortable
00005    avoiding it. */
00006 
00007 #define MAXSTACK 100
00008 
00009 static void exchange(void *a, void *b, size_t size) {
00010     size_t i;
00011     int *ai = (int *) a;
00012     int *bi = (int *) b;
00013     char *ac;
00014     char *bc;
00015 
00016     /******************
00017      *  exchange a,b  *
00018      ******************/
00019 
00020     for (i = sizeof(int); i <= size; i += sizeof(int)) {
00021         int t = *ai;
00022         *ai++ = *bi;
00023         *bi++ = t;
00024     }
00025     ac = (char *) ai;
00026     bc = (char *) bi;
00027     for (i = i - sizeof(int) + 1; i <= size; i++) {
00028         char t = *ac;
00029         *ac++ = *bc;
00030         *bc++ = t;
00031     }
00032 }
00033 
00034 static void my_qsort(void *base, size_t nmemb, size_t size,
00035                    int (*compar)(const void *, const void *)) {
00036     void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
00037     int sp;
00038     unsigned int offset;
00039 
00040     /********************
00041      *  ANSI-C qsort()  *
00042      ********************/
00043 
00044     lbStack[0] = (char *)base;
00045     ubStack[0] = (char *)base + (nmemb-1)*size;
00046     for (sp = 0; sp >= 0; sp--) {
00047         char *lb, *ub, *m;
00048         char *P, *i, *j;
00049 
00050         lb = lbStack[sp];
00051         ub = ubStack[sp];
00052 
00053         while (lb < ub) {
00054 
00055             /* select pivot and exchange with 1st element */
00056             offset = (ub - lb) >> 1;
00057             P = lb + offset - offset % size;
00058             exchange (lb, P, size);
00059 
00060             /* partition into two segments */
00061             i = lb + size;
00062             j = ub;
00063             while (1) {
00064                 while (i < j && compar(lb, i) > 0) i += size;
00065                 while (j >= i && compar(j, lb) > 0) j -= size;
00066                 if (i >= j) break;
00067                 exchange (i, j, size);
00068                 j -= size;
00069                 i += size;
00070             }
00071 
00072             /* pivot belongs in A[j] */
00073             exchange (lb, j, size);
00074             m = j;
00075 
00076             /* keep processing smallest segment, and stack largest */
00077             if (m - lb <= ub - m) {
00078                 if (m + size < ub) {
00079                     lbStack[sp] = m + size;
00080                     ubStack[sp++] = ub;
00081                 }
00082                 ub = m - size;
00083             } else {
00084                 if (m - size > lb) {
00085                     lbStack[sp] = lb; 
00086                     ubStack[sp++] = m - size;
00087                 }
00088                 lb = m + size;
00089             }
00090         }
00091     }
00092 }
00093 
00094 #else
00095 # define my_qsort qsort
00096 #endif