root / src / sim / ctaskheap.cc @ 5668c48e
History  View  Annotate  Download (6.5 KB)
1 
//=========================================================================


2 
// CTASKHEAP.CC  part of

3 
//

4 
// OMNeT++/OMNEST

5 
// Discrete System Simulation in C++

6 
//

7 
// Member functions of

8 
// cTaskHeap : future event set, implemented as heap

9 
//

10 
// Author: Andras Varga, based on the code from Gabor Lencse

11 
// (the original is taken from G. H. Gonnet's book pp. 273274)

12 
// Georg Kunz

13 
//

14 
//=========================================================================

15  
16 
/**

17 
Copyright (C) 19922005 Andras Varga

18 
Copyright (C) 2009 Georg Kunz

19 

20 
This file is distributed WITHOUT ANY WARRANTY. See the file

21 
`license' for details on this and other legal matters.

22 

23 
Note: This class is used in the parallel task queue.

24 
Its implementation has been freed from the ownership

25 
management code and implements a EDF scheduling policy.

26 

27 
**/

28  
29 
#include <stdio.h> // sprintf 
30 
#include <string.h> // strlen 
31 
#include <stdlib.h> // qsort 
32 
#include <sstream> 
33 
#include "regmacros.h" 
34 
#include "ctaskheap.h" 
35 
#include "cmessage.h" 
36  
37 
//=== Registration

38 
Register_Class(cTaskHeap); 
39  
40 
//==========================================================================

41  
42 
/*

43 
static inline bool operator > (cMessage& a, cMessage& b)

44 
{

45 
return (a.getTend() > b.getTend()) ? 1 :

46 
(a.getTend() < b.getTend()) ? 0 :

47 
a.getTaskInsertOrder() > b.getTaskInsertOrder();

48 
}

49 
*/

50  
51 
static inline bool operator > (cMessage& a, cMessage& b) 
52 
{ 
53 
return a.getTend() > b.getTend() ? true : // 1. criterion: starting time 
54 
a.getTend() < b.getTend() ? false :

55 
a.getSchedulingPriority() > b.getSchedulingPriority() ? true : // 2. criterion: priority 
56 
a.getSchedulingPriority() < b.getSchedulingPriority() ? false :

57 
a.getParentStartTime() > b.getParentStartTime() ? true : // 3. criterion: parent starting time 
58 
a.getParentStartTime() < b.getParentStartTime() ? false :

59 
a.getParentExecutionOrderId() > b.getParentExecutionOrderId() ? true : // 4. criterion: parent execution order 
60 
a.getParentExecutionOrderId() < b.getParentExecutionOrderId() ? false :

61 
a.getSchedulingOrderId() > b.getSchedulingOrderId() ? true : // 5. criterion: scheduling order 
62 
a.getSchedulingOrderId() < b.getSchedulingOrderId() ? false :

63 
a.getTaskInsertOrder() > b.getTaskInsertOrder(); // 6. criterion: final tie breaker (needed during init)

64 
} 
65  
66 
static inline bool operator <= (cMessage& a, cMessage& b) 
67 
{ 
68 
return !(a>b);

69 
} 
70  
71 
static int qsort_cmp_msgs(const void *p1, const void *p2) 
72 
{ 
73 
cMessage *m1 = *(cMessage **)p1; 
74 
cMessage *m2 = *(cMessage **)p2; 
75  
76 
simtime_t dt = m1>getTend()  m2>getTend(); 
77 
if (dt<0) return 1; 
78 
else if (dt>0) return 1; 
79  
80 
return (m1>getTaskInsertOrder() < m2>getTaskInsertOrder()) ? 1 : 1; 
81 
} 
82  
83  
84 
//==========================================================================

85 
//=== cTaskHeap  member functions

86  
87 
cTaskHeap::cTaskHeap(const char *name, int siz) : cOwnedObject(name) 
88 
{ 
89 
insertcntr = 0L;

90 
n = 0;

91 
size = siz; 
92 
h = new cMessage *[size+1]; // +1 is necessary because h[0] is not used 
93 
} 
94  
95 
cTaskHeap::cTaskHeap(const cTaskHeap& heap) : cOwnedObject()

96 
{ 
97 
h=NULL; n=0; 
98 
setName( heap.getName() ); 
99 
operator=(heap);

100 
} 
101  
102 
cTaskHeap::~cTaskHeap() 
103 
{ 
104 
clear(); 
105 
delete [] h;

106 
} 
107  
108 
std::string cTaskHeap::info() const 
109 
{ 
110 
if (n==0) 
111 
return std::string("empty"); 
112 
std::stringstream out; 
113 
out << "length=" << n << " Tmin=" << h[1]>getArrivalTime().str(); 
114 
return out.str();

115 
} 
116  
117 
void cTaskHeap::forEachChild(cVisitor *v)

118 
{ 
119 
sort(); 
120  
121 
for (int i=1; i<=n; i++) 
122 
if (h[i])

123 
v>visit(h[i]); 
124 
} 
125  
126 
void cTaskHeap::clear()

127 
{ 
128 
for (int i=1; i<=n; i++) 
129 
{ 
130  
131 
ignoreOwnerAndDelete(h[i]); 
132  
133 
} 
134 
n=0;

135 
} 
136  
137 
void cTaskHeap::clearNoDelete()

138 
{ 
139 
for (int i=1; i<=n; i++) 
140 
{ 
141 
getFirst(); 
142 
} 
143 
n=0;

144 
} 
145  
146 
cTaskHeap& cTaskHeap::operator=(const cTaskHeap& heap) 
147 
{ 
148 
if (this==&heap) return *this; 
149  
150 
clear(); 
151  
152 
cObject::operator=(heap);

153  
154 
n = heap.n; 
155 
size = heap.size; 
156 
delete [] h;

157 
h = new cMessage *[size+1]; 
158  
159 
for (int i=1; i<=n; i++) 
160 
h[i]=(cMessage *)heap.h[i]>dup(); 
161 
return *this; 
162 
} 
163  
164 
cMessage *cTaskHeap::peek(int m)

165 
{ 
166 
// map 0..n1 index range to heap's internal 1..n indices

167 
if (m<0  m>=n) 
168 
return NULL; 
169 
return h[m+1]; 
170 
} 
171  
172 
void cTaskHeap::sort()

173 
{ 
174 
qsort(h+1,n,sizeof(cMessage *),qsort_cmp_msgs); 
175 
for (int i=1; i<=n; i++) h[i]>taskindex=i; 
176 
} 
177  
178 
void cTaskHeap::insert(cMessage *event)

179 
{ 
180 
int i,j;

181  
182 
event>taskinsertordr = insertcntr++; 
183  
184 
if (++n > size)

185 
{ 
186 
size *= 2;

187 
cMessage **hnew = new cMessage *[size+1]; 
188 
for (i=1; i<=n1; i++) 
189 
hnew[i]=h[i]; 
190 
delete [] h;

191 
h = hnew; 
192 
} 
193  
194 
for (j=n; j>1; j=i) 
195 
{ 
196 
i=j/2;

197 
if (*h[i] <= *event) //direction 
198 
break;

199  
200 
(h[j]=h[i])>taskindex=j; 
201 
} 
202 
(h[j]=event)>taskindex=j; 
203 
} 
204  
205 
void cTaskHeap::shiftup(int from) 
206 
{ 
207 
// restores heap structure (in a subheap)

208 
int i,j;

209 
cMessage *temp; 
210  
211 
i=from; 
212 
while ((j=2*i) <= n) 
213 
{ 
214 
if (j<n && (*h[j] > *h[j+1])) //direction 
215 
j++; 
216 
if (*h[i] > *h[j]) //is change necessary? 
217 
{ 
218 
temp=h[j]; 
219 
(h[j]=h[i])>taskindex=j; 
220 
(h[i]=temp)>taskindex=i; 
221 
i=j; 
222 
} 
223 
else

224 
break;

225 
} 
226 
} 
227  
228 
cMessage *cTaskHeap::peekFirst() const

229 
{ 
230 
return n==0 ? NULL : h[1]; 
231 
} 
232  
233 
cMessage *cTaskHeap::getFirst() 
234 
{ 
235 
if (n>0) 
236 
{ 
237 
// first is taken out and replaced by the last one

238 
cMessage *event = h[1];

239 
(h[1]=h[n])>taskindex=1; 
240 
shiftup(); 
241 
event>taskindex=1;

242 
return event;

243 
} 
244 
return NULL; 
245 
} 
246  
247 
cMessage *cTaskHeap::get(cMessage *event) 
248 
{ 
249 
// make sure it is really on the heap

250 
if (event>taskindex==1) 
251 
return NULL; 
252  
253 
// sanity check:

254 
// assert(h[event>taskindex]==event);

255  
256 
// last element will be used to fill the hole

257 
int father, out = event>taskindex;

258 
cMessage *fill = h[n]; 
259 
while ((father=out/2)!=0 && *h[father] > *fill) 
260 
{ 
261 
(h[out]=h[father])>taskindex=out; // father is moved down

262 
out=father; 
263 
} 
264 
(h[out]=fill)>taskindex=out; 
265 
shiftup(out); 
266 
event>taskindex=1;

267 
return event;

268 
} 
269 