Charm++: Charm Source Code Documentation

00001 
00011 #ifndef _GK_MKPQUEUE_H
00012 #define _GK_MKPQUEUE_H
00013 
00014 
00015 #define GK_MKPQUEUE(FPRFX, PQT, KVT, KT, VT, KVMALLOC, KMAX, KEY_LT)\
00016 /*************************************************************************/\
00017 \
00018 /**************************************************************************/\
00019 PQT *FPRFX ## Create(size_t maxnodes)\
00020 {\
00021   PQT *queue; \
00022 \
00023   queue = (PQT *)gk_malloc(sizeof(PQT), "gk_pqCreate: queue");\
00024   FPRFX ## Init(queue, maxnodes);\
00025 \
00026   return queue;\
00027 }\
00028 \
00029 \
00030 /*************************************************************************/\
00031 \
00032 /**************************************************************************/\
00033 void FPRFX ## Init(PQT *queue, size_t maxnodes)\
00034 {\
00035   queue->nnodes = 0;\
00036   queue->maxnodes = maxnodes;\
00037 \
00038   queue->heap    = KVMALLOC(maxnodes, "gk_PQInit: heap");\
00039   queue->locator = gk_idxsmalloc(maxnodes, -1, "gk_PQInit: locator");\
00040 }\
00041 \
00042 \
00043 /*************************************************************************/\
00044 \
00045 /**************************************************************************/\
00046 void FPRFX ## Reset(PQT *queue)\
00047 {\
00048   gk_idx_t i;\
00049   gk_idx_t *locator=queue->locator;\
00050   KVT *heap=queue->heap;\
00051 \
00052   for (i=queue->nnodes-1; i>=0; i--)\
00053     locator[heap[i].val] = -1;\
00054   queue->nnodes = 0;\
00055 }\
00056 \
00057 \
00058 /*************************************************************************/\
00059 \
00060 /**************************************************************************/\
00061 void FPRFX ## Free(PQT *queue)\
00062 {\
00063   if (queue == NULL) return;\
00064   gk_free((void **)&queue->heap, &queue->locator, LTERM);\
00065   queue->maxnodes = 0;\
00066 }\
00067 \
00068 \
00069 /*************************************************************************/\
00070 \
00072 /**************************************************************************/\
00073 void FPRFX ## Destroy(PQT *queue)\
00074 {\
00075   if (queue == NULL) return;\
00076   FPRFX ## Free(queue);\
00077   gk_free((void **)&queue, LTERM);\
00078 }\
00079 \
00080 \
00081 /*************************************************************************/\
00082 \
00083 /**************************************************************************/\
00084 size_t FPRFX ## Length(PQT *queue)\
00085 {\
00086   return queue->nnodes;\
00087 }\
00088 \
00089 \
00090 /*************************************************************************/\
00091 \
00092 /**************************************************************************/\
00093 int FPRFX ## Insert(PQT *queue, VT node, KT key)\
00094 {\
00095   gk_idx_t i, j;\
00096   gk_idx_t *locator=queue->locator;\
00097   KVT *heap=queue->heap;\
00098 \
00099   ASSERT2(FPRFX ## CheckHeap(queue));\
00100 \
00101   ASSERT(locator[node] == -1);\
00102 \
00103   i = queue->nnodes++;\
00104   while (i > 0) {\
00105     j = (i-1)>>1;\
00106     if (KEY_LT(key, heap[j].key)) {\
00107       heap[i] = heap[j];\
00108       locator[heap[i].val] = i;\
00109       i = j;\
00110     }\
00111     else\
00112       break;\
00113   }\
00114   ASSERT(i >= 0);\
00115   heap[i].key   = key;\
00116   heap[i].val   = node;\
00117   locator[node] = i;\
00118 \
00119   ASSERT2(FPRFX ## CheckHeap(queue));\
00120 \
00121   return 0;\
00122 }\
00123 \
00124 \
00125 /*************************************************************************/\
00126 \
00127 /**************************************************************************/\
00128 int FPRFX ## Delete(PQT *queue, VT node)\
00129 {\
00130   gk_idx_t i, j, nnodes;\
00131   KT newkey, oldkey;\
00132   gk_idx_t *locator=queue->locator;\
00133   KVT *heap=queue->heap;\
00134 \
00135   ASSERT(locator[node] != -1);\
00136   ASSERT(heap[locator[node]].val == node);\
00137 \
00138   ASSERT2(FPRFX ## CheckHeap(queue));\
00139 \
00140   i = locator[node];\
00141   locator[node] = -1;\
00142 \
00143   if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {\
00144     node   = heap[queue->nnodes].val;\
00145     newkey = heap[queue->nnodes].key;\
00146     oldkey = heap[i].key;\
00147 \
00148     if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
00149       while (i > 0) {\
00150         j = (i-1)>>1;\
00151         if (KEY_LT(newkey, heap[j].key)) {\
00152           heap[i] = heap[j];\
00153           locator[heap[i].val] = i;\
00154           i = j;\
00155         }\
00156         else\
00157           break;\
00158       }\
00159     }\
00160     else { /* Filter down */\
00161       nnodes = queue->nnodes;\
00162       while ((j=(i<<1)+1) < nnodes) {\
00163         if (KEY_LT(heap[j].key, newkey)) {\
00164           if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
00165             j++;\
00166           heap[i] = heap[j];\
00167           locator[heap[i].val] = i;\
00168           i = j;\
00169         }\
00170         else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
00171           j++;\
00172           heap[i] = heap[j];\
00173           locator[heap[i].val] = i;\
00174           i = j;\
00175         }\
00176         else\
00177           break;\
00178       }\
00179     }\
00180 \
00181     heap[i].key   = newkey;\
00182     heap[i].val   = node;\
00183     locator[node] = i;\
00184   }\
00185 \
00186   ASSERT2(FPRFX ## CheckHeap(queue));\
00187 \
00188   return 0;\
00189 }\
00190 \
00191 \
00192 /*************************************************************************/\
00193  \
00194 /**************************************************************************/\
00195 void FPRFX ## Update(PQT *queue, VT node, KT newkey)\
00196 {\
00197   gk_idx_t i, j, nnodes;\
00198   KT oldkey;\
00199   gk_idx_t *locator=queue->locator;\
00200   KVT *heap=queue->heap;\
00201 \
00202   oldkey = heap[locator[node]].key;\
00203 \
00204   ASSERT(locator[node] != -1);\
00205   ASSERT(heap[locator[node]].val == node);\
00206   ASSERT2(FPRFX ## CheckHeap(queue));\
00207 \
00208   i = locator[node];\
00209 \
00210   if (KEY_LT(newkey, oldkey)) { /* Filter-up */\
00211     while (i > 0) {\
00212       j = (i-1)>>1;\
00213       if (KEY_LT(newkey, heap[j].key)) {\
00214         heap[i] = heap[j];\
00215         locator[heap[i].val] = i;\
00216         i = j;\
00217       }\
00218       else\
00219         break;\
00220     }\
00221   }\
00222   else { /* Filter down */\
00223     nnodes = queue->nnodes;\
00224     while ((j=(i<<1)+1) < nnodes) {\
00225       if (KEY_LT(heap[j].key, newkey)) {\
00226         if (j+1 < nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
00227           j++;\
00228         heap[i] = heap[j];\
00229         locator[heap[i].val] = i;\
00230         i = j;\
00231       }\
00232       else if (j+1 < nnodes && KEY_LT(heap[j+1].key, newkey)) {\
00233         j++;\
00234         heap[i] = heap[j];\
00235         locator[heap[i].val] = i;\
00236         i = j;\
00237       }\
00238       else\
00239         break;\
00240     }\
00241   }\
00242 \
00243   heap[i].key   = newkey;\
00244   heap[i].val   = node;\
00245   locator[node] = i;\
00246 \
00247   ASSERT2(FPRFX ## CheckHeap(queue));\
00248 \
00249   return;\
00250 }\
00251 \
00252 \
00253 /*************************************************************************/\
00254 \
00256 /**************************************************************************/\
00257 VT FPRFX ## GetTop(PQT *queue)\
00258 {\
00259   gk_idx_t i, j;\
00260   gk_idx_t *locator;\
00261   KVT *heap;\
00262   VT vtx, node;\
00263   KT key;\
00264 \
00265   ASSERT2(FPRFX ## CheckHeap(queue));\
00266 \
00267   if (queue->nnodes == 0)\
00268     return -1;\
00269 \
00270   queue->nnodes--;\
00271 \
00272   heap    = queue->heap;\
00273   locator = queue->locator;\
00274 \
00275   vtx = heap[0].val;\
00276   locator[vtx] = -1;\
00277 \
00278   if ((i = queue->nnodes) > 0) {\
00279     key  = heap[i].key;\
00280     node = heap[i].val;\
00281     i = 0;\
00282     while ((j=2*i+1) < queue->nnodes) {\
00283       if (KEY_LT(heap[j].key, key)) {\
00284         if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, heap[j].key))\
00285           j = j+1;\
00286         heap[i] = heap[j];\
00287         locator[heap[i].val] = i;\
00288         i = j;\
00289       }\
00290       else if (j+1 < queue->nnodes && KEY_LT(heap[j+1].key, key)) {\
00291         j = j+1;\
00292         heap[i] = heap[j];\
00293         locator[heap[i].val] = i;\
00294         i = j;\
00295       }\
00296       else\
00297         break;\
00298     }\
00299 \
00300     heap[i].key   = key;\
00301     heap[i].val   = node;\
00302     locator[node] = i;\
00303   }\
00304 \
00305   ASSERT2(FPRFX ## CheckHeap(queue));\
00306   return vtx;\
00307 }\
00308 \
00309 \
00310 /*************************************************************************/\
00311 \
00313 /**************************************************************************/\
00314 VT FPRFX ## SeeTopVal(PQT *queue)\
00315 {\
00316   return (queue->nnodes == 0 ? -1 : queue->heap[0].val);\
00317 }\
00318 \
00319 \
00320 /*************************************************************************/\
00321 \
00323 /**************************************************************************/\
00324 KT FPRFX ## SeeTopKey(PQT *queue)\
00325 {\
00326   return (queue->nnodes == 0 ? KMAX : queue->heap[0].key);\
00327 }\
00328 \
00329 \
00330 /*************************************************************************/\
00331 \
00332 /**************************************************************************/\
00333 KT FPRFX ## SeeKey(PQT *queue, VT node)\
00334 {\
00335   gk_idx_t *locator;\
00336   KVT *heap;\
00337 \
00338   heap    = queue->heap;\
00339   locator = queue->locator;\
00340 \
00341   return heap[locator[node]].key;\
00342 }\
00343 \
00344 \
00345 /*************************************************************************/\
00346 \
00349 /**************************************************************************/\
00350 /*\
00351 VT FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts)\
00352 {\
00353   gk_idx_t i;\
00354 \
00355   if (queue->nnodes == 0)\
00356     return -1;\
00357 \
00358   if (maxwgt <= 1000)\
00359     return FPRFX ## SeeTopVal(queue);\
00360 \
00361   for (i=0; i<queue->nnodes; i++) {\
00362     if (queue->heap[i].key > 0) {\
00363       if (wgts[queue->heap[i].val] <= maxwgt)\
00364         return queue->heap[i].val;\
00365     }\
00366     else {\
00367       if (queue->heap[i/2].key <= 0)\
00368         break;\
00369     }\
00370   }\
00371 \
00372   return queue->heap[0].val;\
00373 \
00374 }\
00375 */\
00376 \
00377 \
00378 /*************************************************************************/\
00379 \
00380 /**************************************************************************/\
00381 int FPRFX ## CheckHeap(PQT *queue)\
00382 {\
00383   gk_idx_t i, j;\
00384   size_t nnodes;\
00385   gk_idx_t *locator;\
00386   KVT *heap;\
00387 \
00388   heap    = queue->heap;\
00389   locator = queue->locator;\
00390   nnodes  = queue->nnodes;\
00391 \
00392   if (nnodes == 0)\
00393     return 1;\
00394 \
00395   ASSERT(locator[heap[0].val] == 0);\
00396   for (i=1; i<nnodes; i++) {\
00397     ASSERT(locator[heap[i].val] == i);\
00398     ASSERT(!KEY_LT(heap[i].key, heap[(i-1)/2].key));\
00399   }\
00400   for (i=1; i<nnodes; i++)\
00401     ASSERT(!KEY_LT(heap[i].key, heap[0].key));\
00402 \
00403   for (j=i=0; i<queue->maxnodes; i++) {\
00404     if (locator[i] != -1)\
00405       j++;\
00406   }\
00407   ASSERTP(j == nnodes, ("%jd %jd\n", (intmax_t)j, (intmax_t)nnodes));\
00408 \
00409   return 1;\
00410 }\
00411 
00412 
00413 #define GK_MKPQUEUE_PROTO(FPRFX, PQT, KT, VT)\
00414   PQT *  FPRFX ## Create(size_t maxnodes);\
00415   void   FPRFX ## Init(PQT *queue, size_t maxnodes);\
00416   void   FPRFX ## Reset(PQT *queue);\
00417   void   FPRFX ## Free(PQT *queue);\
00418   void   FPRFX ## Destroy(PQT *queue);\
00419   size_t FPRFX ## Length(PQT *queue);\
00420   int    FPRFX ## Insert(PQT *queue, VT node, KT key);\
00421   int    FPRFX ## Delete(PQT *queue, VT node);\
00422   void   FPRFX ## Update(PQT *queue, VT node, KT newkey);\
00423   VT     FPRFX ## GetTop(PQT *queue);\
00424   VT     FPRFX ## SeeTopVal(PQT *queue);\
00425   KT     FPRFX ## SeeTopKey(PQT *queue);\
00426   KT     FPRFX ## SeeKey(PQT *queue, VT node);\
00427   VT     FPRFX ## SeeConstraintTop(PQT *queue, KT maxwgt, KT *wgts);\
00428   int    FPRFX ## CheckHeap(PQT *queue);\
00429 
00430 
00431 /* This is how these macros are used
00432 GK_MKPQUEUE(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t, gk_dkvmalloc, DBL_MAX)
00433 GK_MKPQUEUE_PROTO(gk_dkvPQ, gk_dkvPQ_t, double, gk_idx_t)
00434 */
00435 
00436 
00437 #endif
libs/ck-libs/metis/GKlib/gk_mkpqueue.h
