Function PQueueInit

OTHER/METIS/pqueue.c:23–74

* This function initializes the data structures of the priority queue **************************************************************************/

* 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);
  }

}


/*************************************************************************