Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * myqsort.c
00005  * 
00006  * This file contains a fast idxtype increasing qsort algorithm.
00007  * Addopted from TeX
00008  * 
00009  * Started 10/18/96
00010  * George
00011  * 
00012  * $Id$
00013  */
00014 
00015 #include <metis.h>                      /* only for type declarations */
00016 
00017 #define         THRESH          1       /* threshold for insertion */
00018 #define         MTHRESH         6       /* threshold for median */
00019 
00020 
00021 
00022 
00023 static void siqst(idxtype *, idxtype *);
00024 static void iiqst(int *, int *);
00025 static void keyiqst(KeyValueType *, KeyValueType *);
00026 static void keyvaliqst(KeyValueType *, KeyValueType *);
00027 
00028 
00029 /*************************************************************************
00030 * Entry point of idxtype increasing sort
00031 **************************************************************************/
00032 void iidxsort(int n, idxtype *base)
00033 {
00034   register idxtype *i;
00035   register idxtype *j;
00036   register idxtype *lo;
00037   register idxtype *hi;
00038   register idxtype *min;
00039   register idxtype c;
00040   idxtype *max;
00041 
00042   if (n <= 1)
00043     return;
00044 
00045   max = base + n;
00046 
00047   if (n >= THRESH) {
00048     siqst(base, max);
00049     hi = base + THRESH;
00050   }
00051   else 
00052     hi = max;
00053 
00054   for (j = lo = base; lo++ < hi;) {
00055     if (*j > *lo)
00056       j = lo;
00057   }
00058   if (j != base) { /* swap j into place */
00059     c = *base;
00060     *base = *j;
00061     *j = c;
00062   }
00063 
00064   for (min = base; (hi = min += 1) < max;) {
00065     while (*(--hi) > *min);
00066     if ((hi += 1) != min) {
00067       for (lo = min + 1; --lo >= min;) {
00068         c = *lo;
00069         for (i = j = lo; (j -= 1) >= hi; i = j)
00070            *i = *j;
00071         *i = c;
00072       }
00073     }
00074   }
00075 }
00076 
00077 static void siqst(idxtype *base, idxtype *max)
00078 {
00079   register idxtype *i;
00080   register idxtype *j;
00081   register idxtype *jj;
00082   register idxtype *mid;
00083   register int ii;
00084   register idxtype c;
00085   idxtype *tmp;
00086   int lo;
00087   int hi;
00088 
00089   lo = max - base;              /* number of elements as idxtype */
00090   do {
00091     mid = base + ((unsigned) lo>>1);
00092     if (lo >= MTHRESH) {
00093       j = (*base > *mid ? base : mid);
00094       tmp = max - 1;
00095       if (*j > *tmp) {
00096         j = (j == base ? mid : base); /* switch to first loser */
00097         if (*j < *tmp)
00098           j = tmp;
00099       }
00100 
00101       if (j != mid) {  /* SWAP */ 
00102         c = *mid;
00103         *mid = *j;
00104         *j = c;
00105       }
00106     }
00107 
00108     /* Semi-standard quicksort partitioning/swapping */
00109     for (i = base, j = max - 1;;) {
00110       while (i < mid && *i <= *mid)
00111         i++;
00112       while (j > mid) {
00113         if (*mid <= *j) {
00114           j--;
00115           continue;
00116         }
00117         tmp = i + 1;    /* value of i after swap */
00118         if (i == mid)   /* j <-> mid, new mid is j */
00119           mid = jj = j;
00120         else            /* i <-> j */
00121           jj = j--;
00122         goto swap;
00123       }
00124 
00125       if (i == mid) 
00126         break;
00127       else {            /* i <-> mid, new mid is i */
00128         jj = mid;
00129         tmp = mid = i;  /* value of i after swap */
00130         j--;
00131       }
00132 swap:
00133       c = *i;
00134       *i = *jj;
00135       *jj = c;
00136       i = tmp;
00137     }
00138 
00139     i = (j = mid) + 1;
00140     if ((lo = j - base) <= (hi = max - i)) {
00141       if (lo >= THRESH)
00142         siqst(base, j);
00143       base = i;
00144       lo = hi;
00145     }
00146     else {
00147       if (hi >= THRESH)
00148         siqst(i, max);
00149       max = j;
00150     }
00151   } while (lo >= THRESH);
00152 }
00153 
00154 
00155 
00156 
00157 
00158 /*************************************************************************
00159 * Entry point of int increasing sort
00160 **************************************************************************/
00161 void iintsort(int n, int *base)
00162 {
00163   register int *i;
00164   register int *j;
00165   register int *lo;
00166   register int *hi;
00167   register int *min;
00168   register int c;
00169   int *max;
00170 
00171   if (n <= 1)
00172     return;
00173 
00174   max = base + n;
00175 
00176   if (n >= THRESH) {
00177     iiqst(base, max);
00178     hi = base + THRESH;
00179   }
00180   else 
00181     hi = max;
00182 
00183   for (j = lo = base; lo++ < hi;) {
00184     if (*j > *lo)
00185       j = lo;
00186   }
00187   if (j != base) { /* swap j into place */
00188     c = *base;
00189     *base = *j;
00190     *j = c;
00191   }
00192 
00193   for (min = base; (hi = min += 1) < max;) {
00194     while (*(--hi) > *min);
00195     if ((hi += 1) != min) {
00196       for (lo = min + 1; --lo >= min;) {
00197         c = *lo;
00198         for (i = j = lo; (j -= 1) >= hi; i = j)
00199            *i = *j;
00200         *i = c;
00201       }
00202     }
00203   }
00204 }
00205 
00206 
00207 static void iiqst(int *base, int *max)
00208 {
00209   register int *i;
00210   register int *j;
00211   register int *jj;
00212   register int *mid;
00213   register int ii;
00214   register int c;
00215   int *tmp;
00216   int lo;
00217   int hi;
00218 
00219   lo = max - base;              /* number of elements as ints */
00220   do {
00221     mid = base + ((unsigned) lo>>1);
00222     if (lo >= MTHRESH) {
00223       j = (*base > *mid ? base : mid);
00224       tmp = max - 1;
00225       if (*j > *tmp) {
00226         j = (j == base ? mid : base); /* switch to first loser */
00227         if (*j < *tmp)
00228           j = tmp;
00229       }
00230 
00231       if (j != mid) {  /* SWAP */ 
00232         c = *mid;
00233         *mid = *j;
00234         *j = c;
00235       }
00236     }
00237 
00238     /* Semi-standard quicksort partitioning/swapping */
00239     for (i = base, j = max - 1;;) {
00240       while (i < mid && *i <= *mid)
00241         i++;
00242       while (j > mid) {
00243         if (*mid <= *j) {
00244           j--;
00245           continue;
00246         }
00247         tmp = i + 1;    /* value of i after swap */
00248         if (i == mid)   /* j <-> mid, new mid is j */
00249           mid = jj = j;
00250         else            /* i <-> j */
00251           jj = j--;
00252         goto swap;
00253       }
00254 
00255       if (i == mid) 
00256         break;
00257       else {            /* i <-> mid, new mid is i */
00258         jj = mid;
00259         tmp = mid = i;  /* value of i after swap */
00260         j--;
00261       }
00262 swap:
00263       c = *i;
00264       *i = *jj;
00265       *jj = c;
00266       i = tmp;
00267     }
00268 
00269     i = (j = mid) + 1;
00270     if ((lo = j - base) <= (hi = max - i)) {
00271       if (lo >= THRESH)
00272         iiqst(base, j);
00273       base = i;
00274       lo = hi;
00275     }
00276     else {
00277       if (hi >= THRESH)
00278         iiqst(i, max);
00279       max = j;
00280     }
00281   } while (lo >= THRESH);
00282 }
00283 
00284 
00285 
00286 
00287 
00288 /*************************************************************************
00289 * Entry point of KeyVal increasing sort, ONLY key part
00290 **************************************************************************/
00291 void ikeysort(int n, KeyValueType *base)
00292 {
00293   register KeyValueType *i;
00294   register KeyValueType *j;
00295   register KeyValueType *lo;
00296   register KeyValueType *hi;
00297   register KeyValueType *min;
00298   register KeyValueType c;
00299   KeyValueType *max;
00300 
00301   if (n <= 1)
00302     return;
00303 
00304   max = base + n;
00305 
00306   if (n >= THRESH) {
00307     keyiqst(base, max);
00308     hi = base + THRESH;
00309   }
00310   else 
00311     hi = max;
00312 
00313   for (j = lo = base; lo++ < hi;) {
00314     if (j->key > lo->key)
00315       j = lo;
00316   }
00317   if (j != base) { /* swap j into place */
00318     c = *base;
00319     *base = *j;
00320     *j = c;
00321   }
00322 
00323   for (min = base; (hi = min += 1) < max;) {
00324     while ((--hi)->key > min->key);
00325     if ((hi += 1) != min) {
00326       for (lo = min + 1; --lo >= min;) {
00327         c = *lo;
00328         for (i = j = lo; (j -= 1) >= hi; i = j)
00329            *i = *j;
00330         *i = c;
00331       }
00332     }
00333   }
00334 
00335   /* Sanity check */
00336   { 
00337     int i;
00338     for (i=0; i<n-1; i++)
00339       if (base[i].key > base[i+1].key)
00340         printf("Something went wrong!\n");
00341   }
00342 }
00343 
00344 
00345 static void keyiqst(KeyValueType *base, KeyValueType *max)
00346 {
00347   register KeyValueType *i;
00348   register KeyValueType *j;
00349   register KeyValueType *jj;
00350   register KeyValueType *mid;
00351   register KeyValueType c;
00352   KeyValueType *tmp;
00353   int lo;
00354   int hi;
00355 
00356   lo = (max - base)>>1;         /* number of elements as KeyValueType */
00357   do {
00358     mid = base + ((unsigned) lo>>1);
00359     if (lo >= MTHRESH) {
00360       j = (base->key > mid->key ? base : mid);
00361       tmp = max - 1;
00362       if (j->key > tmp->key) {
00363         j = (j == base ? mid : base); /* switch to first loser */
00364         if (j->key < tmp->key)
00365           j = tmp;
00366       }
00367 
00368       if (j != mid) {  /* SWAP */ 
00369         c = *mid;
00370         *mid = *j;
00371         *j = c;
00372       }
00373     }
00374 
00375     /* Semi-standard quicksort partitioning/swapping */
00376     for (i = base, j = max - 1;;) {
00377       while (i < mid && i->key <= mid->key)
00378         i++;
00379       while (j > mid) {
00380         if (mid->key <= j->key) {
00381           j--;
00382           continue;
00383         }
00384         tmp = i + 1;    /* value of i after swap */
00385         if (i == mid)   /* j <-> mid, new mid is j */
00386           mid = jj = j;
00387         else            /* i <-> j */
00388           jj = j--;
00389         goto swap;
00390       }
00391 
00392       if (i == mid) 
00393         break;
00394       else {            /* i <-> mid, new mid is i */
00395         jj = mid;
00396         tmp = mid = i;  /* value of i after swap */
00397         j--;
00398       }
00399 swap:
00400       c = *i;
00401       *i = *jj;
00402       *jj = c;
00403       i = tmp;
00404     }
00405 
00406     i = (j = mid) + 1;
00407     if ((lo = (j - base)>>1) <= (hi = (max - i)>>1)) {
00408       if (lo >= THRESH)
00409         keyiqst(base, j);
00410       base = i;
00411       lo = hi;
00412     }
00413     else {
00414       if (hi >= THRESH)
00415         keyiqst(i, max);
00416       max = j;
00417     }
00418   } while (lo >= THRESH);
00419 }
00420 
00421 
00422 
00423 
00424 /*************************************************************************
00425 * Entry point of KeyVal increasing sort, BOTH key and val part
00426 **************************************************************************/
00427 void ikeyvalsort(int n, KeyValueType *base)
00428 {
00429   register KeyValueType *i;
00430   register KeyValueType *j;
00431   register KeyValueType *lo;
00432   register KeyValueType *hi;
00433   register KeyValueType *min;
00434   register KeyValueType c;
00435   KeyValueType *max;
00436 
00437   if (n <= 1)
00438     return;
00439 
00440   max = base + n;
00441 
00442   if (n >= THRESH) {
00443     keyvaliqst(base, max);
00444     hi = base + THRESH;
00445   }
00446   else 
00447     hi = max;
00448 
00449   for (j = lo = base; lo++ < hi;) {
00450     if ((j->key > lo->key) || (j->key == lo->key && j->val > lo->val))
00451       j = lo;
00452   }
00453   if (j != base) { /* swap j into place */
00454     c = *base;
00455     *base = *j;
00456     *j = c;
00457   }
00458 
00459   for (min = base; (hi = min += 1) < max;) {
00460     while ((--hi)->key > min->key || (hi->key == min->key && hi->val > min->val));
00461     if ((hi += 1) != min) {
00462       for (lo = min + 1; --lo >= min;) {
00463         c = *lo;
00464         for (i = j = lo; (j -= 1) >= hi; i = j)
00465            *i = *j;
00466         *i = c;
00467       }
00468     }
00469   }
00470 }
00471 
00472 
00473 static void keyvaliqst(KeyValueType *base, KeyValueType *max)
00474 {
00475   register KeyValueType *i;
00476   register KeyValueType *j;
00477   register KeyValueType *jj;
00478   register KeyValueType *mid;
00479   register KeyValueType c;
00480   KeyValueType *tmp;
00481   int lo;
00482   int hi;
00483 
00484   lo = (max - base)>>1;         /* number of elements as KeyValueType */
00485   do {
00486     mid = base + ((unsigned) lo>>1);
00487     if (lo >= MTHRESH) {
00488       j = (base->key > mid->key || (base->key == mid->key && base->val > mid->val) ? base : mid);
00489       tmp = max - 1;
00490       if (j->key > tmp->key || (j->key == tmp->key && j->val > tmp->val)) {
00491         j = (j == base ? mid : base); /* switch to first loser */
00492         if (j->key < tmp->key || (j->key == tmp->key && j->val < tmp->val))
00493           j = tmp;
00494       }
00495 
00496       if (j != mid) {  /* SWAP */ 
00497         c = *mid;
00498         *mid = *j;
00499         *j = c;
00500       }
00501     }
00502 
00503     /* Semi-standard quicksort partitioning/swapping */
00504     for (i = base, j = max - 1;;) {
00505       while (i < mid && (i->key < mid->key || (i->key == mid->key && i->val <= mid->val)))
00506         i++;
00507       while (j > mid) {
00508         if (mid->key < j->key || (mid->key == j->key && mid->val <= j->val)) {
00509           j--;
00510           continue;
00511         }
00512         tmp = i + 1;    /* value of i after swap */
00513         if (i == mid)   /* j <-> mid, new mid is j */
00514           mid = jj = j;
00515         else            /* i <-> j */
00516           jj = j--;
00517         goto swap;
00518       }
00519 
00520       if (i == mid) 
00521         break;
00522       else {            /* i <-> mid, new mid is i */
00523         jj = mid;
00524         tmp = mid = i;  /* value of i after swap */
00525         j--;
00526       }
00527 swap:
00528       c = *i;
00529       *i = *jj;
00530       *jj = c;
00531       i = tmp;
00532     }
00533 
00534     i = (j = mid) + 1;
00535     if ((lo = (j - base)>>1) <= (hi = (max - i)>>1)) {
00536       if (lo >= THRESH)
00537         keyvaliqst(base, j);
00538       base = i;
00539       lo = hi;
00540     }
00541     else {
00542       if (hi >= THRESH)
00543         keyvaliqst(i, max);
00544       max = j;
00545     }
00546   } while (lo >= THRESH);
00547 }
libs/ck-libs/parmetis/METISLib/myqsort.c
