root/ompi/mca/topo/treematch/treematch/PriorityQueue.c

DEFINITIONS

1. compFunc
2. PQ_init
3. PQ_exit
4. PQ_free
5. PQ_isEmpty
6. PQ_insertElement
7. PQ_deleteElement
8. PQ_insert
9. PQ_delete
10. PQ_findMaxElement
11. PQ_deleteMaxElement
12. PQ_findMaxKey
13. PQ_deleteMax
14. PQ_increaseElementKey
15. PQ_decreaseElementKey
16. PQ_adjustElementKey
17. PQ_increaseKey
18. PQ_decreaseKey
19. PQ_adjustKey

   1 #include <stdlib.h>
   2 #include "PriorityQueue.h"
   3 
   4 /*
   5   This comparison function is used to sort elements in key descending order.
   6 */
   7 int compfunc(const FiboNode * const, const FiboNode * const);
   8 
   9 
  10 
  11 static int compFunc(const FiboNode * const node1, const FiboNode * const node2)
  12 {
  13   return 
  14     ( ( ((QueueElement*)(node1))->key > ((QueueElement*)(node2))->key ) ? -1 : 1); 
  15 }
  16 
  17 int PQ_init(PriorityQueue * const q, int size)
  18 {
  19   int i;
  20   q->size = size;
  21   q->elements = malloc(sizeof(QueueElement *) * size);
  22   for(i=0; i < size; i++)
  23     q->elements[i]=NULL;
  24   return fiboTreeInit((FiboTree *)q, compFunc);
  25 }
  26 
  27 void PQ_exit(PriorityQueue * const q)
  28 {
  29   
  30   int i;
  31   for(i = 0; i < q->size; i++)
  32     {
  33       if(q->elements[i] != NULL)
  34         free(q->elements[i]);
  35     }
  36   if(q->elements != NULL)
  37     free(q->elements);
  38   fiboTreeExit((FiboTree *)q);
  39 }
  40 void PQ_free(PriorityQueue * const q)
  41 {
  42   int i;
  43   for(i = 0; i < q->size; i++)
  44     {
  45       if(q->elements[i] != NULL)
  46         free(q->elements[i]);
  47     }
  48   fiboTreeFree((FiboTree *)q);
  49 }
  50 
  51 int PQ_isEmpty(PriorityQueue * const q)
  52 {
  53   FiboTree * tree = (FiboTree *)q;
  54 /* if the tree root is linked to itself then the tree is empty */
  55   if(&(tree->rootdat) == (tree->rootdat.linkdat.nextptr)) 
  56     return 1;
  57   return 0;
  58 }
  59 
  60 void PQ_insertElement(PriorityQueue * const q, QueueElement * const e)
  61 {
  62   if(e->value >= 0 && e->value < q->size)
  63     {
  64       fiboTreeAdd((FiboTree *)q, (FiboNode *)(e));
  65       q->elements[e->value] = e;
  66       e->isInQueue = 1;
  67     }
  68 }
  69 void PQ_deleteElement(PriorityQueue * const q, QueueElement * const e)
  70 {
  71   fiboTreeDel((FiboTree *)q, (FiboNode *)(e));
  72   q->elements[e->value] = NULL;
  73   e->isInQueue = 0;
  74 }
  75 
  76 void PQ_insert(PriorityQueue * const q, int val, double key)
  77 {
  78   if( val >= 0 && val < q->size)
  79     {
  80       QueueElement * e = malloc(sizeof(QueueElement));
  81       e->value = val;
  82       e->key = key;
  83       PQ_insertElement(q, e);
  84     }
  85 }
  86 
  87 void PQ_delete(PriorityQueue * const q, int val)
  88 {
  89   QueueElement * e = q->elements[val];
  90   PQ_deleteElement(q, e);
  91   free(e);
  92 }
  93 
  94 QueueElement * PQ_findMaxElement(PriorityQueue * const q)
  95 {
  96   QueueElement * e = (QueueElement *)(fiboTreeMin((FiboTree *)q));
  97   return e;
  98 }
  99 QueueElement * PQ_deleteMaxElement(PriorityQueue * const q)
 100 {
 101   QueueElement * e = (QueueElement *)(fiboTreeMin((FiboTree *)q));
 102   if(e != NULL)
 103     {
 104       PQ_deleteElement(q, e);
 105     }
 106   return e;
 107 }
 108 
 109 double PQ_findMaxKey(PriorityQueue * const q)
 110 {
 111   QueueElement * e = PQ_findMaxElement(q);
 112   if(e!=NULL)
 113     return e->key;
 114   return 0;
 115 }
 116 
 117 int PQ_deleteMax(PriorityQueue * const q)
 118 {
 119   QueueElement * e = PQ_deleteMaxElement(q);
 120   int res = -1;
 121   if(e != NULL)
 122     res = e->value;
 123   free(e);
 124   return res;
 125 }
 126 
 127 void PQ_increaseElementKey(PriorityQueue * const q, QueueElement * const e, double i)
 128 {
 129   if(e->isInQueue)
 130     {
 131       PQ_deleteElement(q, e);
 132       e->key += i;
 133       PQ_insertElement(q, e);
 134     }
 135 }
 136 void PQ_decreaseElementKey(PriorityQueue * const q, QueueElement * const e, double i)
 137 {
 138   if(e->isInQueue)
 139     {
 140       PQ_deleteElement(q, e);
 141       e->key -= i;
 142       PQ_insertElement(q, e);
 143     }
 144 }
 145 void PQ_adjustElementKey(PriorityQueue * const q, QueueElement * const e, double i)
 146 {
 147   if(e->isInQueue)
 148     {    
 149       PQ_deleteElement(q, e);
 150       e->key = i;
 151       PQ_insertElement(q, e);
 152     }
 153 }
 154 
 155 void PQ_increaseKey(PriorityQueue * const q, int val, double i)
 156 {
 157   QueueElement * e = q->elements[val];
 158   if(e != NULL)
 159     PQ_increaseElementKey(q, e, i);
 160 }
 161 
 162 void PQ_decreaseKey(PriorityQueue * const q, int val, double i)
 163 {
 164   QueueElement * e = q->elements[val];
 165   if(e != NULL)
 166     PQ_decreaseElementKey(q, e, i);
 167 }
 168 
 169 void PQ_adjustKey(PriorityQueue * const q, int val, double i)
 170 {
 171   QueueElement * e = q->elements[val];
 172   if(e != NULL)
 173     PQ_adjustElementKey(q, e, i);
 174 }