summaryrefslogtreecommitdiff
path: root/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/pqueue.c
diff options
context:
space:
mode:
Diffstat (limited to 'benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/pqueue.c')
-rw-r--r--benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/pqueue.c579
1 files changed, 579 insertions, 0 deletions
diff --git a/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/pqueue.c b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/pqueue.c
new file mode 100644
index 0000000..6a1986f
--- /dev/null
+++ b/benchmarks/CUDA/DG/3rdParty/ParMetis-3.1/METISLib/pqueue.c
@@ -0,0 +1,579 @@
+/*
+ * Copyright 1997, Regents of the University of Minnesota
+ *
+ * pqueue.c
+ *
+ * This file contains functions for manipulating the bucket list
+ * representation of the gains associated with each vertex in a graph.
+ * These functions are used by the refinement algorithms
+ *
+ * Started 9/2/94
+ * George
+ *
+ * $Id: pqueue.c,v 1.1 2003/07/16 15:55:16 karypis Exp $
+ *
+ */
+
+#include <metis.h>
+
+
+/*************************************************************************
+* This function initializes the data structures of the priority queue
+**************************************************************************/
+void PQueueInit(CtrlType *ctrl, PQueueType *queue, int maxnodes, int maxgain)
+{
+ int i, j, ncore;
+
+ queue->nnodes = 0;
+ queue->maxnodes = maxnodes;
+
+ queue->buckets = NULL;
+ queue->nodes = NULL;
+ queue->heap = NULL;
+ queue->locator = NULL;
+
+ if (maxgain > PLUS_GAINSPAN || maxnodes < 500)
+ queue->type = 2;
+ else
+ queue->type = 1;
+
+ if (queue->type == 1) {
+ queue->pgainspan = amin(PLUS_GAINSPAN, maxgain);
+ queue->ngainspan = amin(NEG_GAINSPAN, maxgain);
+
+ j = queue->ngainspan+queue->pgainspan+1;
+
+ ncore = 2 + (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes + (sizeof(ListNodeType *)/sizeof(idxtype))*j;
+
+ if (WspaceAvail(ctrl) > ncore) {
+ queue->nodes = (ListNodeType *)idxwspacemalloc(ctrl, (sizeof(ListNodeType)/sizeof(idxtype))*maxnodes);
+ queue->buckets = (ListNodeType **)idxwspacemalloc(ctrl, (sizeof(ListNodeType *)/sizeof(idxtype))*j);
+ queue->mustfree = 0;
+ }
+ else { /* Not enough memory in the wspace, allocate it */
+ queue->nodes = (ListNodeType *)idxmalloc((sizeof(ListNodeType)/sizeof(idxtype))*maxnodes, "PQueueInit: queue->nodes");
+ queue->buckets = (ListNodeType **)idxmalloc((sizeof(ListNodeType *)/sizeof(idxtype))*j, "PQueueInit: queue->buckets");
+ queue->mustfree = 1;
+ }
+
+ for (i=0; i<maxnodes; i++)
+ queue->nodes[i].id = i;
+
+ for (i=0; i<j; i++)
+ queue->buckets[i] = NULL;
+
+ queue->buckets += queue->ngainspan; /* Advance buckets by the ngainspan proper indexing */
+ queue->maxgain = -queue->ngainspan;
+ }
+ else {
+ queue->heap = (KeyValueType *)idxwspacemalloc(ctrl, (sizeof(KeyValueType)/sizeof(idxtype))*maxnodes);
+ queue->locator = idxwspacemalloc(ctrl, maxnodes);
+ idxset(maxnodes, -1, queue->locator);
+ }
+
+}
+
+
+/*************************************************************************
+* This function resets the buckets
+**************************************************************************/
+void PQueueReset(PQueueType *queue)
+{
+ int i, j;
+ queue->nnodes = 0;
+
+ if (queue->type == 1) {
+ queue->maxgain = -queue->ngainspan;
+
+ j = queue->ngainspan+queue->pgainspan+1;
+ queue->buckets -= queue->ngainspan;
+ for (i=0; i<j; i++)
+ queue->buckets[i] = NULL;
+ queue->buckets += queue->ngainspan;
+ }
+ else {
+ idxset(queue->maxnodes, -1, queue->locator);
+ }
+
+}
+
+
+/*************************************************************************
+* This function frees the buckets
+**************************************************************************/
+void PQueueFree(CtrlType *ctrl, PQueueType *queue)
+{
+
+ if (queue->type == 1) {
+ if (queue->mustfree) {
+ queue->buckets -= queue->ngainspan;
+ GKfree(&queue->nodes, &queue->buckets, LTERM);
+ }
+ else {
+ idxwspacefree(ctrl, sizeof(ListNodeType *)*(queue->ngainspan+queue->pgainspan+1)/sizeof(idxtype));
+ idxwspacefree(ctrl, sizeof(ListNodeType)*queue->maxnodes/sizeof(idxtype));
+ }
+ }
+ else {
+ idxwspacefree(ctrl, sizeof(KeyValueType)*queue->maxnodes/sizeof(idxtype));
+ idxwspacefree(ctrl, queue->maxnodes);
+ }
+
+ queue->maxnodes = 0;
+}
+
+
+/*************************************************************************
+* This function returns the number of nodes in the queue
+**************************************************************************/
+int PQueueGetSize(PQueueType *queue)
+{
+ return queue->nnodes;
+}
+
+
+/*************************************************************************
+* This function adds a node of certain gain into a partition
+**************************************************************************/
+int PQueueInsert(PQueueType *queue, int node, int gain)
+{
+ int i, j, k;
+ idxtype *locator;
+ ListNodeType *newnode;
+ KeyValueType *heap;
+
+ if (queue->type == 1) {
+ ASSERT(gain >= -queue->ngainspan && gain <= queue->pgainspan);
+
+ /* Allocate and add the node */
+ queue->nnodes++;
+ newnode = queue->nodes + node;
+
+ /* Attach this node in the doubly-linked list */
+ newnode->next = queue->buckets[gain];
+ newnode->prev = NULL;
+ if (newnode->next != NULL)
+ newnode->next->prev = newnode;
+ queue->buckets[gain] = newnode;
+
+ if (queue->maxgain < gain)
+ queue->maxgain = gain;
+ }
+ else {
+ ASSERT(CheckHeap(queue));
+
+ heap = queue->heap;
+ locator = queue->locator;
+
+ ASSERT(locator[node] == -1);
+
+ i = queue->nnodes++;
+ while (i > 0) {
+ j = (i-1)/2;
+ if (heap[j].key < gain) {
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else
+ break;
+ }
+ ASSERT(i >= 0);
+ heap[i].key = gain;
+ heap[i].val = node;
+ locator[node] = i;
+
+ ASSERT(CheckHeap(queue));
+ }
+
+ return 0;
+}
+
+
+/*************************************************************************
+* This function deletes a node from a partition and reinserts it with
+* an updated gain
+**************************************************************************/
+int PQueueDelete(PQueueType *queue, int node, int gain)
+{
+ int i, j, newgain, oldgain;
+ idxtype *locator;
+ ListNodeType *newnode, **buckets;
+ KeyValueType *heap;
+
+ if (queue->type == 1) {
+ ASSERT(gain >= -queue->ngainspan && gain <= queue->pgainspan);
+ ASSERT(queue->nnodes > 0);
+
+ buckets = queue->buckets;
+ queue->nnodes--;
+ newnode = queue->nodes+node;
+
+ /* Remove newnode from the doubly-linked list */
+ if (newnode->prev != NULL)
+ newnode->prev->next = newnode->next;
+ else
+ buckets[gain] = newnode->next;
+ if (newnode->next != NULL)
+ newnode->next->prev = newnode->prev;
+
+ if (buckets[gain] == NULL && gain == queue->maxgain) {
+ if (queue->nnodes == 0)
+ queue->maxgain = -queue->ngainspan;
+ else
+ for (; buckets[queue->maxgain]==NULL; queue->maxgain--);
+ }
+ }
+ else { /* Heap Priority Queue */
+ heap = queue->heap;
+ locator = queue->locator;
+
+ ASSERT(locator[node] != -1);
+ ASSERT(heap[locator[node]].val == node);
+
+ ASSERT(CheckHeap(queue));
+
+ i = locator[node];
+ locator[node] = -1;
+
+ if (--queue->nnodes > 0 && heap[queue->nnodes].val != node) {
+ node = heap[queue->nnodes].val;
+ newgain = heap[queue->nnodes].key;
+ oldgain = heap[i].key;
+
+ if (oldgain < newgain) { /* Filter-up */
+ while (i > 0) {
+ j = (i-1)>>1;
+ if (heap[j].key < newgain) {
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else
+ break;
+ }
+ }
+ else { /* Filter down */
+ while ((j=2*i+1) < queue->nnodes) {
+ if (heap[j].key > newgain) {
+ if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
+ j = j+1;
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
+ j = j+1;
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else
+ break;
+ }
+ }
+
+ heap[i].key = newgain;
+ heap[i].val = node;
+ locator[node] = i;
+ }
+
+ ASSERT(CheckHeap(queue));
+ }
+
+ return 0;
+}
+
+
+
+/*************************************************************************
+* This function deletes a node from a partition and reinserts it with
+* an updated gain
+**************************************************************************/
+int PQueueUpdate(PQueueType *queue, int node, int oldgain, int newgain)
+{
+ int i, j;
+ idxtype *locator;
+ ListNodeType *newnode;
+ KeyValueType *heap;
+
+ if (oldgain == newgain)
+ return 0;
+
+ if (queue->type == 1) {
+ /* First delete the node and then insert it */
+ PQueueDelete(queue, node, oldgain);
+ return PQueueInsert(queue, node, newgain);
+ }
+ else { /* Heap Priority Queue */
+ heap = queue->heap;
+ locator = queue->locator;
+
+ ASSERT(locator[node] != -1);
+ ASSERT(heap[locator[node]].val == node);
+ ASSERT(heap[locator[node]].key == oldgain);
+ ASSERT(CheckHeap(queue));
+
+ i = locator[node];
+
+ if (oldgain < newgain) { /* Filter-up */
+ while (i > 0) {
+ j = (i-1)>>1;
+ if (heap[j].key < newgain) {
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else
+ break;
+ }
+ }
+ else { /* Filter down */
+ while ((j=2*i+1) < queue->nnodes) {
+ if (heap[j].key > newgain) {
+ if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
+ j = j+1;
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else if (j+1 < queue->nnodes && heap[j+1].key > newgain) {
+ j = j+1;
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else
+ break;
+ }
+ }
+
+ heap[i].key = newgain;
+ heap[i].val = node;
+ locator[node] = i;
+
+ ASSERT(CheckHeap(queue));
+ }
+
+ return 0;
+}
+
+
+
+/*************************************************************************
+* This function deletes a node from a partition and reinserts it with
+* an updated gain
+**************************************************************************/
+void PQueueUpdateUp(PQueueType *queue, int node, int oldgain, int newgain)
+{
+ int i, j;
+ idxtype *locator;
+ ListNodeType *newnode, **buckets;
+ KeyValueType *heap;
+
+ if (oldgain == newgain)
+ return;
+
+ if (queue->type == 1) {
+ ASSERT(oldgain >= -queue->ngainspan && oldgain <= queue->pgainspan);
+ ASSERT(newgain >= -queue->ngainspan && newgain <= queue->pgainspan);
+ ASSERT(queue->nnodes > 0);
+
+ buckets = queue->buckets;
+ newnode = queue->nodes+node;
+
+ /* First delete the node */
+ if (newnode->prev != NULL)
+ newnode->prev->next = newnode->next;
+ else
+ buckets[oldgain] = newnode->next;
+ if (newnode->next != NULL)
+ newnode->next->prev = newnode->prev;
+
+ /* Attach this node in the doubly-linked list */
+ newnode->next = buckets[newgain];
+ newnode->prev = NULL;
+ if (newnode->next != NULL)
+ newnode->next->prev = newnode;
+ buckets[newgain] = newnode;
+
+ if (queue->maxgain < newgain)
+ queue->maxgain = newgain;
+ }
+ else { /* Heap Priority Queue */
+ heap = queue->heap;
+ locator = queue->locator;
+
+ ASSERT(locator[node] != -1);
+ ASSERT(heap[locator[node]].val == node);
+ ASSERT(heap[locator[node]].key == oldgain);
+ ASSERT(CheckHeap(queue));
+
+
+ /* Here we are just filtering up since the newgain is greater than the oldgain */
+ i = locator[node];
+ while (i > 0) {
+ j = (i-1)>>1;
+ if (heap[j].key < newgain) {
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else
+ break;
+ }
+
+ heap[i].key = newgain;
+ heap[i].val = node;
+ locator[node] = i;
+
+ ASSERT(CheckHeap(queue));
+ }
+
+}
+
+
+/*************************************************************************
+* This function returns the vertex with the largest gain from a partition
+* and removes the node from the bucket list
+**************************************************************************/
+int PQueueGetMax(PQueueType *queue)
+{
+ int vtx, i, j, gain, node;
+ idxtype *locator;
+ ListNodeType *tptr;
+ KeyValueType *heap;
+
+ if (queue->nnodes == 0)
+ return -1;
+
+ queue->nnodes--;
+
+ if (queue->type == 1) {
+ tptr = queue->buckets[queue->maxgain];
+ queue->buckets[queue->maxgain] = tptr->next;
+ if (tptr->next != NULL) {
+ tptr->next->prev = NULL;
+ }
+ else {
+ if (queue->nnodes == 0) {
+ queue->maxgain = -queue->ngainspan;
+ }
+ else
+ for (; queue->buckets[queue->maxgain]==NULL; queue->maxgain--);
+ }
+
+ return tptr->id;
+ }
+ else {
+ heap = queue->heap;
+ locator = queue->locator;
+
+ vtx = heap[0].val;
+ locator[vtx] = -1;
+
+ if ((i = queue->nnodes) > 0) {
+ gain = heap[i].key;
+ node = heap[i].val;
+ i = 0;
+ while ((j=2*i+1) < queue->nnodes) {
+ if (heap[j].key > gain) {
+ if (j+1 < queue->nnodes && heap[j+1].key > heap[j].key)
+ j = j+1;
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else if (j+1 < queue->nnodes && heap[j+1].key > gain) {
+ j = j+1;
+ heap[i] = heap[j];
+ locator[heap[i].val] = i;
+ i = j;
+ }
+ else
+ break;
+ }
+
+ heap[i].key = gain;
+ heap[i].val = node;
+ locator[node] = i;
+ }
+
+ ASSERT(CheckHeap(queue));
+ return vtx;
+ }
+}
+
+
+/*************************************************************************
+* This function returns the vertex with the largest gain from a partition
+**************************************************************************/
+int PQueueSeeMax(PQueueType *queue)
+{
+ int vtx;
+
+ if (queue->nnodes == 0)
+ return -1;
+
+ if (queue->type == 1)
+ vtx = queue->buckets[queue->maxgain]->id;
+ else
+ vtx = queue->heap[0].val;
+
+ return vtx;
+}
+
+
+/*************************************************************************
+* This function returns the vertex with the largest gain from a partition
+**************************************************************************/
+int PQueueGetKey(PQueueType *queue)
+{
+ int key;
+
+ if (queue->nnodes == 0)
+ return -1;
+
+ if (queue->type == 1)
+ key = queue->maxgain;
+ else
+ key = queue->heap[0].key;
+
+ return key;
+}
+
+
+
+
+/*************************************************************************
+* This functions checks the consistency of the heap
+**************************************************************************/
+int CheckHeap(PQueueType *queue)
+{
+ int i, j, nnodes;
+ idxtype *locator;
+ KeyValueType *heap;
+
+ heap = queue->heap;
+ locator = queue->locator;
+ nnodes = queue->nnodes;
+
+ if (nnodes == 0)
+ return 1;
+
+ ASSERT(locator[heap[0].val] == 0);
+ for (i=1; i<nnodes; i++) {
+ ASSERTP(locator[heap[i].val] == i, ("%d %d %d %d\n", nnodes, i, heap[i].val, locator[heap[i].val]));
+ 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));
+ }
+ for (i=1; i<nnodes; i++)
+ ASSERT(heap[i].key <= heap[0].key);
+
+ for (j=i=0; i<queue->maxnodes; i++) {
+ if (locator[i] != -1)
+ j++;
+ }
+ ASSERTP(j == nnodes, ("%d %d\n", j, nnodes));
+
+ return 1;
+}
generated by cgit v1.3 (git 2.53.0) at 2026-07-11 02:09:37 +0000