openmpi  3.1.6
About: Open MPI is a high performance Message Passing Interface (MPI) library project combining technologies and resources from several other projects (FT-MPI, LA-MPI, LAM/MPI, and PACX-MPI) in order to build the best MPI library available. 3.x series.
  Fossies Dox: openmpi-3.1.6.tar.bz2  ("unofficial" and yet experimental doxygen-generated source code documentation)  

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