root / src / sim / ctaskheap.cc @ fbe00e73
History  View  Annotate  Download (6.69 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: ending time 
54 
a.getTend() < b.getTend() ? false : // TODO: Is this still correct 
55 
// (considering Parent Start Times?)

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

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

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

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

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

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

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

86 
//=== cTaskHeap  member functions

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

91 
n = 0;

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

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

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

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

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

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

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

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

136 
} 
137  
138 
void cTaskHeap::clearNoDelete()

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

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

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

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

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

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

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

180 
{ 
181 
int i,j;

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

186 
{ 
187 
size *= 2;

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

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

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

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

209 
int i,j;

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

225 
break;

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

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

239 
cMessage *event = h[1];

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

243 
return event;

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

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

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

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

258 
int father, out = event>taskindex;

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

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

268 
return event;

269 
} 
270 