Charm++: Charm Source Code Documentation

00001 
00011 #include <GKlib.h>
00012 
00013 /* Byte-wise swap two items of size SIZE. */
00014 #define QSSWAP(a, b, stmp) do { stmp = (a); (a) = (b); (b) = stmp; } while (0)
00015 
00016 
00017 /******************************************************************************/
00019 /*******************************************************************************/
00020 int gk_dfkvkselect(size_t n, int topk, gk_fkv_t *cand)
00021 {
00022   int i, j, lo, hi, mid;
00023   gk_fkv_t stmp;
00024   float pivot;
00025 
00026   if (n <= topk)
00027     return n; /* return if the array has fewer elements than we want */
00028 
00029   for (lo=0, hi=n-1; lo < hi;) {
00030     mid = lo + ((hi-lo) >> 1);
00031 
00032     /* select the median */
00033     if (cand[lo].key < cand[mid].key)
00034       mid = lo;
00035     if (cand[hi].key > cand[mid].key)
00036       mid = hi;
00037     else 
00038       goto jump_over;
00039     if (cand[lo].key < cand[mid].key)
00040       mid = lo;
00041 
00042 jump_over:
00043     QSSWAP(cand[mid], cand[hi], stmp);
00044     pivot = cand[hi].key;
00045 
00046     /* the partitioning algorithm */
00047     for (i=lo-1, j=lo; j<hi; j++) {
00048       if (cand[j].key >= pivot) {
00049         i++;
00050         QSSWAP(cand[i], cand[j], stmp);
00051       }
00052     }
00053     i++;
00054     QSSWAP(cand[i], cand[hi], stmp);
00055 
00056 
00057     if (i > topk) 
00058       hi = i-1;
00059     else if (i < topk)
00060       lo = i+1;
00061     else
00062       break;
00063   }
00064 
00065 /*
00066   if (cand[lo].key < cand[hi].key)
00067     printf("Hmm Error: %d %d %d %f %f\n", i, lo, hi, cand[lo].key, cand[hi].key);
00068 
00069 
00070   for (i=topk; i<n; i++) {
00071     for (j=0; j<topk; j++)
00072       if (cand[i].key > cand[j].key)
00073         printf("Hmm Error: %d %d %f %f %d %d\n", i, j, cand[i].key, cand[j].key, lo, hi);
00074   }
00075 */
00076 
00077   return topk;
00078 }
00079 
00080 
00081 /******************************************************************************/
00083 /*******************************************************************************/
00084 int gk_ifkvkselect(size_t n, int topk, gk_fkv_t *cand)
00085 {
00086   int i, j, lo, hi, mid;
00087   gk_fkv_t stmp;
00088   float pivot;
00089 
00090   if (n <= topk)
00091     return n; /* return if the array has fewer elements than we want */
00092 
00093   for (lo=0, hi=n-1; lo < hi;) {
00094     mid = lo + ((hi-lo) >> 1);
00095 
00096     /* select the median */
00097     if (cand[lo].key > cand[mid].key)
00098       mid = lo;
00099     if (cand[hi].key < cand[mid].key)
00100       mid = hi;
00101     else 
00102       goto jump_over;
00103     if (cand[lo].key > cand[mid].key)
00104       mid = lo;
00105 
00106 jump_over:
00107     QSSWAP(cand[mid], cand[hi], stmp);
00108     pivot = cand[hi].key;
00109 
00110     /* the partitioning algorithm */
00111     for (i=lo-1, j=lo; j<hi; j++) {
00112       if (cand[j].key <= pivot) {
00113         i++;
00114         QSSWAP(cand[i], cand[j], stmp);
00115       }
00116     }
00117     i++;
00118     QSSWAP(cand[i], cand[hi], stmp);
00119 
00120 
00121     if (i > topk) 
00122       hi = i-1;
00123     else if (i < topk)
00124       lo = i+1;
00125     else
00126       break;
00127   }
00128 
00129 /*
00130   if (cand[lo].key > cand[hi].key)
00131     printf("Hmm Error: %d %d %d %f %f\n", i, lo, hi, cand[lo].key, cand[hi].key);
00132 
00133 
00134   for (i=topk; i<n; i++) {
00135     for (j=0; j<topk; j++)
00136       if (cand[i].key < cand[j].key)
00137         printf("Hmm Error: %d %d %f %f %d %d\n", i, j, cand[i].key, cand[j].key, lo, hi);
00138   }
00139 */
00140 
00141   return topk;
00142 }
libs/ck-libs/metis/GKlib/fkvkselect.c
