Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * fpqueue.c
00005  *
00006  * This file contains functions for manipulating the bucket list
00007  * representation of the gains associated with each vertex in a graph.
00008  * These functions are used by the refinement algorithms
00009  *
00010  * Started 9/2/94
00011  * George
00012  *
00013  * $Id$
00014  *
00015  */
00016 
00017 #include <parmetislib.h>
00018 
00019 
00020 /*************************************************************************
00021 * This function initializes the data structures of the priority queue
00022 **************************************************************************/
00023 void FPQueueInit(FPQueueType *queue, int maxnodes)
00024 {
00025   queue->nnodes = 0;
00026   queue->maxnodes = maxnodes;
00027   queue->heap = NULL;
00028   queue->locator = NULL;
00029 
00030   queue->heap = (FKeyValueType *) malloc(sizeof(FKeyValueType)*maxnodes);
00031   queue->locator = (idxtype *) malloc(sizeof(idxtype)*maxnodes);
00032 
00033   idxset(maxnodes, -1, queue->locator);
00034 
00035 }
00036 
00037 
00038 /*************************************************************************
00039 * This function resets the buckets
00040 **************************************************************************/
00041 void FPQueueReset(FPQueueType *queue)
00042 {
00043   queue->nnodes = 0;
00044 
00045   idxset(queue->maxnodes, -1, queue->locator);
00046 
00047 }
00048 
00049 
00050 /*************************************************************************
00051 * This function frees the buckets
00052 **************************************************************************/
00053 void FPQueueFree(FPQueueType *queue)
00054 {
00055 
00056   free(queue->heap);
00057   free(queue->locator);
00058 
00059   queue->maxnodes = 0;
00060 }
00061 
00062 
00063 /*************************************************************************
00064 * This function returns the number of nodes in the queue
00065 **************************************************************************/
00066 int FPQueueGetSize(FPQueueType *queue)
00067 {
00068   return queue->nnodes;
00069 }
00070 
00071 
00072 /*************************************************************************
00073 * This function adds a node of certain gain into a partition
00074 **************************************************************************/
00075 int FPQueueInsert(FPQueueType *queue, int node, floattype gain)
00076 {
00077   int i, j;
00078   idxtype *locator;
00079   FKeyValueType *heap;
00080 
00081   ASSERTS(CheckHeapFloat(queue));
00082 
00083   heap = queue->heap;
00084   locator = queue->locator;
00085 
00086   ASSERTS(locator[node] == -1);
00087 
00088   i = queue->nnodes++;
00089   while (i > 0) {
00090     j = (i-1)/2;
00091     if (heap[j].key < gain) {
00092       heap[i] = heap[j];
00093       locator[heap[i].val] = i;
00094       i = j;
00095     }
00096     else 
00097       break;
00098   }
00099   ASSERTS(i >= 0);
00100   heap[i].key = gain;
00101   heap[i].val = node;
00102   locator[node] = i;
00103 
00104   ASSERTS(CheckHeapFloat(queue));
00105 
00106   return 0;
00107 }
00108 
00109 
00110 /*************************************************************************
00111 * This function deletes a node from a partition and reinserts it with
00112 * an updated gain
00113 **************************************************************************/
00114 int FPQueueDelete(FPQueueType *queue, int node)
00115 {
00116   int i, j;
00117   floattype newgain, oldgain;
00118   idxtype *locator;
00119   FKeyValueType *heap;
00120 
00121   heap = queue->heap;
00122   locator = queue->locator;
00123 
00124   ASSERTS(locator[node] != -1);
00125   ASSERTS(heap[locator[node]].val == node);
00126 
00127   ASSERTS(CheckHeapFloat(queue));
00128 
00129   i = locator[node];
00130   locator[node] = -1;
00131 
00132   if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {
00133     node = heap[queue->nnodes].val;
00134     newgain = heap[queue->nnodes].key;
00135     oldgain = heap[i].key;
00136 
00137     if (oldgain < newgain) {
00138       /* Filter-up */
00139       while (i > 0) {
00140         j = (i-1)>>1;
00141         if (heap[j].key < newgain) {
00142           heap[i] = heap[j];
00143           locator[heap[i].val] = i;
00144           i = j;
00145         }
00146         else 
00147           break;
00148       }
00149     }
00150     else {
00151       /* Filter down */
00152       while ((j=2*i+1) < queue->nnodes) {
00153         if (heap[j].key > newgain) {
00154           if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
00155             j = j+1;
00156           heap[i] = heap[j];
00157           locator[heap[i].val] = i;
00158           i = j;
00159         }
00160         else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
00161           j = j+1;
00162           heap[i] = heap[j];
00163           locator[heap[i].val] = i;
00164           i = j;
00165         }
00166         else
00167           break;
00168       }
00169     }
00170 
00171     heap[i].key = newgain;
00172     heap[i].val = node;
00173     locator[node] = i;
00174   }
00175 
00176   ASSERTS(CheckHeapFloat(queue));
00177 
00178   return 0;
00179 }
00180 
00181 
00182 
00183 /*************************************************************************
00184 * This function deletes a node from a partition and reinserts it with
00185 * an updated gain
00186 **************************************************************************/
00187 int FPQueueUpdate(FPQueueType *queue, int node, floattype oldgain, floattype newgain)
00188 {
00189   int i, j;
00190   idxtype *locator;
00191   FKeyValueType *heap;
00192 
00193   if (oldgain == newgain) 
00194     return 0;
00195 
00196   heap = queue->heap;
00197   locator = queue->locator;
00198 
00199   ASSERTS(locator[node] != -1);
00200   ASSERTS(heap[locator[node]].val == node);
00201   ASSERTS(fabs(heap[locator[node]].key - oldgain) < SMALLFLOAT);
00202   ASSERTS(CheckHeapFloat(queue));
00203 
00204   i = locator[node];
00205 
00206   if (oldgain < newgain) {
00207     /* Filter-up */
00208     while (i > 0) {
00209       j = (i-1)>>1;
00210       if (heap[j].key < newgain) {
00211         heap[i] = heap[j];
00212         locator[heap[i].val] = i;
00213         i = j;
00214       }
00215       else 
00216         break;
00217     }
00218   }
00219   else {
00220     /* Filter down */
00221     while ((j=2*i+1) < queue->nnodes) {
00222       if (heap[j].key > newgain) {
00223         if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
00224           j = j+1;
00225         heap[i] = heap[j];
00226         locator[heap[i].val] = i;
00227         i = j;
00228       }
00229       else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
00230         j = j+1;
00231         heap[i] = heap[j];
00232         locator[heap[i].val] = i;
00233         i = j;
00234       }
00235       else
00236         break;
00237     }
00238   }
00239 
00240   heap[i].key = newgain;
00241   heap[i].val = node;
00242   locator[node] = i;
00243 
00244   ASSERTS(CheckHeapFloat(queue));
00245 
00246   return 0;
00247 }
00248 
00249 
00250 
00251 /*************************************************************************
00252 * This function deletes a node from a partition and reinserts it with
00253 * an updated gain
00254 **************************************************************************/
00255 void FPQueueUpdateUp(FPQueueType *queue, int node, floattype oldgain, floattype newgain)
00256 {
00257   int i, j;
00258   idxtype *locator;
00259   FKeyValueType *heap;
00260 
00261   if (oldgain == newgain) 
00262     return;
00263 
00264   heap = queue->heap;
00265   locator = queue->locator;
00266 
00267   ASSERTS(locator[node] != -1);
00268   ASSERTS(heap[locator[node]].val == node);
00269   ASSERTS(heap[locator[node]].key == oldgain);
00270   ASSERTS(CheckHeapFloat(queue));
00271 
00272 
00273   /* Here we are just filtering up since the newgain is greater than the oldgain */
00274   i = locator[node];
00275   while (i > 0) {
00276     j = (i-1)>>1;
00277     if (heap[j].key < newgain) {
00278       heap[i] = heap[j];
00279       locator[heap[i].val] = i;
00280       i = j;
00281     }
00282     else 
00283       break;
00284   }
00285 
00286   heap[i].key = newgain;
00287   heap[i].val = node;
00288   locator[node] = i;
00289 
00290   ASSERTS(CheckHeapFloat(queue));
00291 
00292 }
00293 
00294 
00295 /*************************************************************************
00296 * This function returns the vertex with the largest gain from a partition
00297 * and removes the node from the bucket list
00298 **************************************************************************/
00299 int FPQueueGetMax(FPQueueType *queue)
00300 {
00301   int vtx, i, j, node;
00302   floattype gain;
00303   idxtype *locator;
00304   FKeyValueType *heap;
00305 
00306   if (queue->nnodes == 0)
00307     return -1;
00308 
00309   queue->nnodes--;
00310 
00311   heap = queue->heap;
00312   locator = queue->locator;
00313 
00314   vtx = heap[0].val;
00315   locator[vtx] = -1;
00316 
00317   if ((i = queue->nnodes) > 0) {
00318     gain = heap[i].key;
00319     node = heap[i].val;
00320     i = 0;
00321     while ((j=2*i+1) < queue->nnodes) {
00322       if (heap[j].key > gain) {
00323         if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
00324           j = j+1;
00325         heap[i] = heap[j];
00326         locator[heap[i].val] = i;
00327         i = j;
00328       }
00329       else if (j+1 < queue->nnodes && heap[j+1].key > gain) {
00330         j = j+1;
00331         heap[i] = heap[j];
00332         locator[heap[i].val] = i;
00333         i = j;
00334       }
00335       else
00336         break;
00337     }
00338 
00339     heap[i].key = gain;
00340     heap[i].val = node;
00341     locator[node] = i;
00342   }
00343 
00344   ASSERTS(CheckHeapFloat(queue));
00345   return vtx;
00346 }
00347       
00348 
00349 /*************************************************************************
00350 * This function returns the vertex with the largest gain from a partition
00351 **************************************************************************/
00352 int FPQueueSeeMaxVtx(FPQueueType *queue)
00353 {
00354   int vtx;
00355 
00356   if (queue->nnodes == 0)
00357     return -1;
00358 
00359   vtx = queue->heap[0].val;
00360 
00361   return vtx;
00362 }
00363       
00364 
00365 /*************************************************************************
00366 * This function returns the vertex with the largest gain from a partition
00367 **************************************************************************/
00368 floattype FPQueueSeeMaxGain(FPQueueType *queue)
00369 {
00370   floattype gain;
00371 
00372   if (queue->nnodes == 0)
00373     return 0.0;
00374 
00375   gain = queue->heap[0].key;
00376 
00377   return gain;
00378 }
00379 
00380 
00381 /*************************************************************************
00382 * This function returns the vertex with the largest gain from a partition
00383 **************************************************************************/
00384 floattype FPQueueGetKey(FPQueueType *queue)
00385 {
00386   int key;
00387 
00388   if (queue->nnodes == 0)
00389     return -1;
00390 
00391   key = queue->heap[0].key;
00392 
00393   return key;
00394 }
00395       
00396 /*************************************************************************
00397 * This function returns the number of nodes in the queue
00398 **************************************************************************/
00399 int FPQueueGetQSize(FPQueueType *queue)
00400 {
00401   return queue->nnodes;
00402 }
00403 
00404 
00405 
00406 
00407 
00408 
00409 /*************************************************************************
00410 * This functions checks the consistency of the heap
00411 **************************************************************************/
00412 int CheckHeapFloat(FPQueueType *queue)
00413 {
00414   int i, j, nnodes;
00415   idxtype *locator;
00416   FKeyValueType *heap;
00417 
00418   heap = queue->heap;
00419   locator = queue->locator;
00420   nnodes = queue->nnodes;
00421 
00422   if (nnodes == 0)
00423     return 1;
00424 
00425   ASSERTS(locator[heap[0].val] == 0);
00426   for (i=1; i<nnodes; i++) {
00427     ASSERTS(locator[heap[i].val] == i);
00428     ASSERTS(heap[i].key <= heap[(i-1)/2].key);
00429   }
00430   for (i=1; i<nnodes; i++)
00431     ASSERTS(heap[i].key <= heap[0].key);
00432 
00433   for (j=i=0; i<queue->maxnodes; i++) {
00434     if (locator[i] != -1)
00435       j++;
00436   }
00437   ASSERTS(j == nnodes);
00438 
00439   return 1;
00440 }
libs/ck-libs/parmetis/ParMETISLib/fpqueue.c
