Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * pqueue.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 <metis.h>
00018 
00019 
00020 /*************************************************************************
00021 * This function initializes the data structures of the priority queue
00022 **************************************************************************/
00023 void PQueueInit(CtrlType *ctrl, PQueueType *queue, int maxnodes, int maxgain)
00024 {
00025   int i, j, ncore;
00026 
00027   queue->nnodes = 0;
00028   queue->maxnodes = maxnodes;
00029 
00030   queue->buckets = NULL;
00031   queue->nodes = NULL;
00032   queue->heap = NULL;
00033   queue->locator = NULL;
00034 
00035   if (maxgain > PLUS_GAINSPAN || maxnodes < 500)
00036     queue->type = 2;
00037   else
00038     queue->type = 1;
00039 
00040   if (queue->type == 1) {
00041     queue->pgainspan = amin(PLUS_GAINSPAN, maxgain);
00042     queue->ngainspan = amin(NEG_GAINSPAN, maxgain);
00043 
00044     j = queue->ngainspan+queue->pgainspan+1;
00045 
00046     ncore = 2 + (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes + (sizeof(ListNodeType *)/sizeof(idxtype))*j;
00047 
00048     if (WspaceAvail(ctrl) > ncore) {
00049       queue->nodes = (ListNodeType *)idxwspacemalloc(ctrl, (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes);
00050       queue->buckets = (ListNodeType **)idxwspacemalloc(ctrl, (sizeof(ListNodeType *)/sizeof(idxtype))*j);
00051       queue->mustfree = 0;
00052     }
00053     else { /* Not enough memory in the wspace, allocate it */
00054       queue->nodes = (ListNodeType *)idxmalloc((sizeof(ListNodeType)/sizeof(idxtype))*maxnodes, "PQueueInit: queue->nodes");
00055       queue->buckets = (ListNodeType **)idxmalloc((sizeof(ListNodeType *)/sizeof(idxtype))*j, "PQueueInit: queue->buckets");
00056       queue->mustfree = 1;
00057     }
00058 
00059     for (i=0; i<maxnodes; i++) 
00060       queue->nodes[i].id = i;
00061 
00062     for (i=0; i<j; i++)
00063       queue->buckets[i] = NULL;
00064 
00065     queue->buckets += queue->ngainspan;  /* Advance buckets by the ngainspan proper indexing */
00066     queue->maxgain = -queue->ngainspan;
00067   }
00068   else {
00069     queue->heap = (KeyValueType *)idxwspacemalloc(ctrl, (sizeof(KeyValueType)/sizeof(idxtype))*maxnodes);
00070     queue->locator = idxwspacemalloc(ctrl, maxnodes);
00071     idxset(maxnodes, -1, queue->locator);
00072   }
00073 
00074 }
00075 
00076 
00077 /*************************************************************************
00078 * This function resets the buckets
00079 **************************************************************************/
00080 void PQueueReset(PQueueType *queue)
00081 {
00082   int i, j;
00083   queue->nnodes = 0;
00084 
00085   if (queue->type == 1) {
00086     queue->maxgain = -queue->ngainspan;
00087 
00088     j = queue->ngainspan+queue->pgainspan+1;
00089     queue->buckets -= queue->ngainspan;  
00090     for (i=0; i<j; i++)
00091       queue->buckets[i] = NULL;
00092     queue->buckets += queue->ngainspan;  
00093   }
00094   else {
00095     idxset(queue->maxnodes, -1, queue->locator);
00096   }
00097 
00098 }
00099 
00100 
00101 /*************************************************************************
00102 * This function frees the buckets
00103 **************************************************************************/
00104 void PQueueFree(CtrlType *ctrl, PQueueType *queue)
00105 {
00106 
00107   if (queue->type == 1) {
00108     if (queue->mustfree) {
00109       queue->buckets -= queue->ngainspan;  
00110       GKfree(&queue->nodes, &queue->buckets, LTERM);
00111     } 
00112     else {
00113       idxwspacefree(ctrl, sizeof(ListNodeType *)*(queue->ngainspan+queue->pgainspan+1)/sizeof(idxtype));
00114       idxwspacefree(ctrl, sizeof(ListNodeType)*queue->maxnodes/sizeof(idxtype));
00115     }
00116   }
00117   else {
00118     idxwspacefree(ctrl, sizeof(KeyValueType)*queue->maxnodes/sizeof(idxtype));
00119     idxwspacefree(ctrl, queue->maxnodes);
00120   }
00121 
00122   queue->maxnodes = 0;
00123 }
00124 
00125 
00126 /*************************************************************************
00127 * This function returns the number of nodes in the queue
00128 **************************************************************************/
00129 int PQueueGetSize(PQueueType *queue)
00130 {
00131   return queue->nnodes;
00132 }
00133 
00134 
00135 /*************************************************************************
00136 * This function adds a node of certain gain into a partition
00137 **************************************************************************/
00138 int PQueueInsert(PQueueType *queue, int node, int gain)
00139 {
00140   int i, j, k;
00141   idxtype *locator;
00142   ListNodeType *newnode;
00143   KeyValueType *heap;
00144 
00145   if (queue->type == 1) {
00146     ASSERT(gain >= -queue->ngainspan && gain <= queue->pgainspan);
00147 
00148     /* Allocate and add the node */
00149     queue->nnodes++;
00150     newnode = queue->nodes + node;
00151 
00152     /* Attach this node in the doubly-linked list */
00153     newnode->next = queue->buckets[gain];
00154     newnode->prev = NULL;
00155     if (newnode->next != NULL)
00156       newnode->next->prev = newnode;
00157     queue->buckets[gain] = newnode;
00158 
00159     if (queue->maxgain < gain)
00160       queue->maxgain = gain;
00161   }
00162   else {
00163     ASSERT(CheckHeap(queue));
00164 
00165     heap = queue->heap;
00166     locator = queue->locator;
00167 
00168     ASSERT(locator[node] == -1);
00169 
00170     i = queue->nnodes++;
00171     while (i > 0) {
00172       j = (i-1)/2;
00173       if (heap[j].key < gain) {
00174         heap[i] = heap[j];
00175         locator[heap[i].val] = i;
00176         i = j;
00177       }
00178       else 
00179         break;
00180     }
00181     ASSERT(i >= 0);
00182     heap[i].key = gain;
00183     heap[i].val = node;
00184     locator[node] = i;
00185 
00186     ASSERT(CheckHeap(queue));
00187   }
00188 
00189   return 0;
00190 }
00191 
00192 
00193 /*************************************************************************
00194 * This function deletes a node from a partition and reinserts it with
00195 * an updated gain
00196 **************************************************************************/
00197 int PQueueDelete(PQueueType *queue, int node, int gain)
00198 {
00199   int i, j, newgain, oldgain;
00200   idxtype *locator;
00201   ListNodeType *newnode, **buckets;
00202   KeyValueType *heap;
00203 
00204   if (queue->type == 1) {
00205     ASSERT(gain >= -queue->ngainspan && gain <= queue->pgainspan);
00206     ASSERT(queue->nnodes > 0);
00207 
00208     buckets = queue->buckets;
00209     queue->nnodes--;
00210     newnode = queue->nodes+node;
00211 
00212     /* Remove newnode from the doubly-linked list */
00213     if (newnode->prev != NULL)
00214       newnode->prev->next = newnode->next;
00215     else
00216       buckets[gain] = newnode->next;
00217     if (newnode->next != NULL)
00218       newnode->next->prev = newnode->prev;
00219 
00220     if (buckets[gain] == NULL && gain == queue->maxgain) {
00221       if (queue->nnodes == 0) 
00222         queue->maxgain = -queue->ngainspan;
00223       else 
00224         for (; buckets[queue->maxgain]==NULL; queue->maxgain--);
00225     }
00226   }
00227   else { /* Heap Priority Queue */
00228     heap = queue->heap;
00229     locator = queue->locator;
00230 
00231     ASSERT(locator[node] != -1);
00232     ASSERT(heap[locator[node]].val == node);
00233 
00234     ASSERT(CheckHeap(queue));
00235 
00236     i = locator[node];
00237     locator[node] = -1;
00238 
00239     if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {
00240       node = heap[queue->nnodes].val;
00241       newgain = heap[queue->nnodes].key;
00242       oldgain = heap[i].key;
00243 
00244       if (oldgain < newgain) { /* Filter-up */
00245         while (i > 0) {
00246           j = (i-1)>>1;
00247           if (heap[j].key < newgain) {
00248             heap[i] = heap[j];
00249             locator[heap[i].val] = i;
00250             i = j;
00251           }
00252           else 
00253             break;
00254         }
00255       }
00256       else { /* Filter down */
00257         while ((j=2*i+1) < queue->nnodes) {
00258           if (heap[j].key > newgain) {
00259             if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
00260               j = j+1;
00261             heap[i] = heap[j];
00262             locator[heap[i].val] = i;
00263             i = j;
00264           }
00265           else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
00266             j = j+1;
00267             heap[i] = heap[j];
00268             locator[heap[i].val] = i;
00269             i = j;
00270           }
00271           else
00272             break;
00273         }
00274       }
00275 
00276       heap[i].key = newgain;
00277       heap[i].val = node;
00278       locator[node] = i;
00279     }
00280 
00281     ASSERT(CheckHeap(queue));
00282   }
00283 
00284   return 0;
00285 }
00286 
00287 
00288 
00289 /*************************************************************************
00290 * This function deletes a node from a partition and reinserts it with
00291 * an updated gain
00292 **************************************************************************/
00293 int PQueueUpdate(PQueueType *queue, int node, int oldgain, int newgain)
00294 {
00295   int i, j;
00296   idxtype *locator;
00297   ListNodeType *newnode;
00298   KeyValueType *heap;
00299 
00300   if (oldgain == newgain) 
00301     return 0;
00302 
00303   if (queue->type == 1) {
00304     /* First delete the node and then insert it */
00305     PQueueDelete(queue, node, oldgain);
00306     return PQueueInsert(queue, node, newgain);
00307   }
00308   else { /* Heap Priority Queue */
00309     heap = queue->heap;
00310     locator = queue->locator;
00311 
00312     ASSERT(locator[node] != -1);
00313     ASSERT(heap[locator[node]].val == node);
00314     ASSERT(heap[locator[node]].key == oldgain);
00315     ASSERT(CheckHeap(queue));
00316 
00317     i = locator[node];
00318 
00319     if (oldgain < newgain) { /* Filter-up */
00320       while (i > 0) {
00321         j = (i-1)>>1;
00322         if (heap[j].key < newgain) {
00323           heap[i] = heap[j];
00324           locator[heap[i].val] = i;
00325           i = j;
00326         }
00327         else 
00328           break;
00329       }
00330     }
00331     else { /* Filter down */
00332       while ((j=2*i+1) < queue->nnodes) {
00333         if (heap[j].key > newgain) {
00334           if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
00335             j = j+1;
00336           heap[i] = heap[j];
00337           locator[heap[i].val] = i;
00338           i = j;
00339         }
00340         else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
00341           j = j+1;
00342           heap[i] = heap[j];
00343           locator[heap[i].val] = i;
00344           i = j;
00345         }
00346         else
00347           break;
00348       }
00349     }
00350 
00351     heap[i].key = newgain;
00352     heap[i].val = node;
00353     locator[node] = i;
00354 
00355     ASSERT(CheckHeap(queue));
00356   }
00357 
00358   return 0;
00359 }
00360 
00361 
00362 
00363 /*************************************************************************
00364 * This function deletes a node from a partition and reinserts it with
00365 * an updated gain
00366 **************************************************************************/
00367 void PQueueUpdateUp(PQueueType *queue, int node, int oldgain, int newgain)
00368 {
00369   int i, j;
00370   idxtype *locator;
00371   ListNodeType *newnode, **buckets;
00372   KeyValueType *heap;
00373 
00374   if (oldgain == newgain) 
00375     return;
00376 
00377   if (queue->type == 1) {
00378     ASSERT(oldgain >= -queue->ngainspan && oldgain <= queue->pgainspan);
00379     ASSERT(newgain >= -queue->ngainspan && newgain <= queue->pgainspan);
00380     ASSERT(queue->nnodes > 0);
00381 
00382     buckets = queue->buckets;
00383     newnode = queue->nodes+node;
00384 
00385     /* First delete the node */
00386     if (newnode->prev != NULL)
00387       newnode->prev->next = newnode->next;
00388     else
00389       buckets[oldgain] = newnode->next;
00390     if (newnode->next != NULL)
00391       newnode->next->prev = newnode->prev;
00392 
00393     /* Attach this node in the doubly-linked list */
00394     newnode->next = buckets[newgain];
00395     newnode->prev = NULL;
00396     if (newnode->next != NULL)
00397       newnode->next->prev = newnode;
00398     buckets[newgain] = newnode;
00399 
00400     if (queue->maxgain < newgain)
00401       queue->maxgain = newgain;
00402   }
00403   else { /* Heap Priority Queue */
00404     heap = queue->heap;
00405     locator = queue->locator;
00406 
00407     ASSERT(locator[node] != -1);
00408     ASSERT(heap[locator[node]].val == node);
00409     ASSERT(heap[locator[node]].key == oldgain);
00410     ASSERT(CheckHeap(queue));
00411 
00412 
00413     /* Here we are just filtering up since the newgain is greater than the oldgain */
00414     i = locator[node];
00415     while (i > 0) {
00416       j = (i-1)>>1;
00417       if (heap[j].key < newgain) {
00418         heap[i] = heap[j];
00419         locator[heap[i].val] = i;
00420         i = j;
00421       }
00422       else 
00423         break;
00424     }
00425 
00426     heap[i].key = newgain;
00427     heap[i].val = node;
00428     locator[node] = i;
00429 
00430     ASSERT(CheckHeap(queue));
00431   }
00432 
00433 }
00434 
00435 
00436 /*************************************************************************
00437 * This function returns the vertex with the largest gain from a partition
00438 * and removes the node from the bucket list
00439 **************************************************************************/
00440 int PQueueGetMax(PQueueType *queue)
00441 {
00442   int vtx, i, j, gain, node;
00443   idxtype *locator;
00444   ListNodeType *tptr;
00445   KeyValueType *heap;
00446 
00447   if (queue->nnodes == 0)
00448     return -1;
00449 
00450   queue->nnodes--;
00451 
00452   if (queue->type == 1) {
00453     tptr = queue->buckets[queue->maxgain];
00454     queue->buckets[queue->maxgain] = tptr->next;
00455     if (tptr->next != NULL) {
00456       tptr->next->prev = NULL;
00457     }
00458     else {
00459       if (queue->nnodes == 0) {
00460         queue->maxgain = -queue->ngainspan;
00461       }
00462       else 
00463         for (; queue->buckets[queue->maxgain]==NULL; queue->maxgain--);
00464     }
00465 
00466     return tptr->id;
00467   }
00468   else {
00469     heap = queue->heap;
00470     locator = queue->locator;
00471 
00472     vtx = heap[0].val;
00473     locator[vtx] = -1;
00474 
00475     if ((i = queue->nnodes) > 0) {
00476       gain = heap[i].key;
00477       node = heap[i].val;
00478       i = 0;
00479       while ((j=2*i+1) < queue->nnodes) {
00480         if (heap[j].key > gain) {
00481           if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
00482             j = j+1;
00483           heap[i] = heap[j];
00484           locator[heap[i].val] = i;
00485           i = j;
00486         }
00487         else if (j+1 < queue->nnodes && heap[j+1].key > gain) {
00488           j = j+1;
00489           heap[i] = heap[j];
00490           locator[heap[i].val] = i;
00491           i = j;
00492         }
00493         else
00494           break;
00495       }
00496 
00497       heap[i].key = gain;
00498       heap[i].val = node;
00499       locator[node] = i;
00500     }
00501 
00502     ASSERT(CheckHeap(queue));
00503     return vtx;
00504   }
00505 }
00506       
00507 
00508 /*************************************************************************
00509 * This function returns the vertex with the largest gain from a partition
00510 **************************************************************************/
00511 int PQueueSeeMax(PQueueType *queue)
00512 {
00513   int vtx;
00514 
00515   if (queue->nnodes == 0)
00516     return -1;
00517 
00518   if (queue->type == 1) 
00519     vtx = queue->buckets[queue->maxgain]->id;
00520   else
00521     vtx = queue->heap[0].val;
00522 
00523   return vtx;
00524 }
00525       
00526 
00527 /*************************************************************************
00528 * This function returns the vertex with the largest gain from a partition
00529 **************************************************************************/
00530 int PQueueGetKey(PQueueType *queue)
00531 {
00532   int key;
00533 
00534   if (queue->nnodes == 0)
00535     return -1;
00536 
00537   if (queue->type == 1) 
00538     key = queue->maxgain;
00539   else
00540     key = queue->heap[0].key;
00541 
00542   return key;
00543 }
00544       
00545 
00546 
00547 
00548 /*************************************************************************
00549 * This functions checks the consistency of the heap
00550 **************************************************************************/
00551 int CheckHeap(PQueueType *queue)
00552 {
00553   int i, j, nnodes;
00554   idxtype *locator;
00555   KeyValueType *heap;
00556 
00557   heap = queue->heap;
00558   locator = queue->locator;
00559   nnodes = queue->nnodes;
00560 
00561   if (nnodes == 0)
00562     return 1;
00563 
00564   ASSERT(locator[heap[0].val] == 0);
00565   for (i=1; i<nnodes; i++) {
00566     ASSERTP(locator[heap[i].val] == i, ("%d %d %d %d\n", nnodes, i, heap[i].val, locator[heap[i].val])); 
00567     ASSERTP(heap[i].key <= heap[(i-1)/2].key, ("%d %d %d %d %d\n", i, (i-1)/2, nnodes, heap[i].key, heap[(i-1)/2].key));
00568   }
00569   for (i=1; i<nnodes; i++)
00570     ASSERT(heap[i].key <= heap[0].key);
00571 
00572   for (j=i=0; i<queue->maxnodes; i++) {
00573     if (locator[i] != -1)
00574       j++;
00575   }
00576   ASSERTP(j == nnodes, ("%d %d\n", j, nnodes));
00577 
00578   return 1;
00579 }
libs/ck-libs/parmetis/METISLib/pqueue.c
