root / src / sim / cmessageheap.cc @ 3e97003d
History  View  Annotate  Download (9.28 KB)
1 
//=========================================================================


2 
// CMSGHEAP.CC  part of

3 
//

4 
// OMNeT++/OMNEST

5 
// Discrete System Simulation in C++

6 
//

7 
// Member functions of

8 
// cMessageHeap : 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 
//

13 
//=========================================================================

14  
15 
/**

16 
Copyright (C) 19922008 Andras Varga

17 
Copyright (C) 20062008 OpenSim Ltd.

18 

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

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

21 
**/

22  
23 
#include <stdio.h> // sprintf 
24 
#include <string.h> // strlen 
25 
#include <stdlib.h> // qsort 
26 
#include <sstream> 
27 
#include "globals.h" 
28 
#include "cmessage.h" 
29 
#include "cmessageheap.h" 
30  
31 
USING_NAMESPACE 
32  
33 
Register_Class(cMessageHeap); 
34  
35  
36 
#define CBHEAPINDEX(i) (2(i)) 
37 
#define CBINC(i) ((i)=((i)+1)&(cbsize1)) 
38  
39  
40 
/* original comparison operator

41 
inline bool operator > (cMessage& a, cMessage& b)

42 
{

43 
return a.getArrivalTime() > b.getArrivalTime() ? true : // 1. criterion: starting time

44 
a.getArrivalTime() < b.getArrivalTime() ? false :

45 
(a.getSchedulingPriority() > b.getSchedulingPriority()) ? true : // 2. criterion: priority

46 
(a.getSchedulingPriority() < b.getSchedulingPriority()) ? false :

47 
a.getInsertOrder() > b.getInsertOrder(); // 3. criterion: insert order > not valid in parallel context anymore

48 
}

49 
*/

50  
51 
inline bool operator > (cMessage& a, cMessage& b) 
52 
{ 
53 
return a.getArrivalTime() > b.getArrivalTime() ? true : // 1. criterion: starting time 
54 
a.getArrivalTime() < b.getArrivalTime() ? 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.getInsertOrder() > b.getInsertOrder(); // 6. criterion: final tie breaker (needed during init)

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

69 
} 
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 
if (m1>getArrivalTime() < m2>getArrivalTime())

78 
return 1; 
79 
if (m1>getArrivalTime() > m2>getArrivalTime())

80 
return 1; 
81  
82 
int dpri = m1>getSchedulingPriority()  m2>getSchedulingPriority();

83 
if (dpri) return dpri; 
84  
85 
return (m1>getInsertOrder() < m2>getInsertOrder()) ? 1 : 1; 
86 
} 
87  
88 
//

89  
90 
cMessageHeap::cMessageHeap(const char *name, int siz) : cOwnedObject(name, false) 
91 
{ 
92 
insertcntr = 0L;

93  
94 
AO_store(&n, 0);

95 
size = siz; 
96 
h = new cMessage *[size+1]; // +1 is necessary because h[0] is not used 
97  
98 
/* cbsize = 4; // must be power of 2!

99 
cb = new cMessage *[cbsize];

100 
cbhead = cbtail = 0;*/

101 
} 
102  
103 
cMessageHeap::cMessageHeap(const cMessageHeap& heap) : cOwnedObject()

104 
{ 
105 
h=NULL; AO_store(&n, 0); 
106 
setName(heap.getName()); 
107 
operator=(heap);

108 
} 
109  
110 
cMessageHeap::~cMessageHeap() 
111 
{ 
112 
clear(); 
113 
delete [] h;

114 
//delete [] cb;

115 
} 
116  
117 
std::string cMessageHeap::info() const 
118 
{ 
119 
if (isEmpty())

120 
return std::string("empty"); 
121 
std::stringstream out; 
122 
out << "length=" << getLength();

123 
return out.str();

124 
} 
125  
126 
void cMessageHeap::forEachChild(cVisitor *v)

127 
{ 
128 
sort(); 
129  
130 
/* for (int i=cbhead; i!=cbtail; CBINC(i))

131 
v>visit(cb[i]);

132 
*/

133 
for (int i=1; i<=(int)AO_load(&n); i++) 
134 
if (h[i])

135 
v>visit(h[i]); 
136 
} 
137  
138 
void cMessageHeap::clear()

139 
{ 
140 
/* for (int i=cbhead; i!=cbtail; CBINC(i))

141 
dropAndDelete(cb[i]);

142 
cbhead = cbtail = 0;

143 
*/

144 
for (int i=1; i<=(int)AO_load(&n); i++) 
145 
dropAndDelete(h[i]); 
146 
AO_store(&n, 0);

147 
} 
148  
149 
cMessageHeap& cMessageHeap::operator=(const cMessageHeap& heap) 
150 
{ 
151 
if (this==&heap) return *this; 
152  
153 
clear(); 
154  
155 
cOwnedObject::operator=(heap);

156  
157 
// copy heap

158 
AO_store(&n, (int)AO_load((AO_t*)&(heap.n)));

159 
size = heap.size; 
160 
delete [] h;

161 
h = new cMessage *[size+1]; 
162 
for (int i=1; i<=(int)AO_load(&n); i++) 
163 
take( h[i]=(cMessage *)heap.h[i]>dup() ); 
164  
165 
/* // copy circular buffer

166 
cbhead = heap.cbhead;

167 
cbtail = heap.cbtail;

168 
cbsize = heap.cbsize;

169 
delete [] cb;

170 
cb = new cMessage *[cbsize];

171 
for (int i=cbhead; i!=cbtail; CBINC(i))

172 
take( cb[i]=(cMessage *)heap.cb[i]>dup() );

173 
*/

174 
return *this; 
175 
} 
176  
177 
cMessage *cMessageHeap::peek(int m)

178 
{ 
179 
if (m < 0) 
180 
return NULL; 
181 
/*

182 
// first few elements map into the circular buffer

183 
int cblen = cblength();

184 
if (m < cblen)

185 
return cbget(m);

186 
m = cblen;

187 
*/

188 
// map the rest to h[1]..h[n] (h[] is 1based)

189 
if (m >= (int)AO_load(&n)) 
190 
return NULL; 
191 
return h[m+1]; 
192 
} 
193  
194 
void cMessageHeap::sort()

195 
{ 
196 
qsort(h+1,(int)AO_load(&n),sizeof(cMessage *),qsort_cmp_msgs); 
197 
for (int i=1; i<=(int)AO_load(&n); i++) 
198 
h[i]>heapindex=i; 
199 
} 
200  
201 
void cMessageHeap::insert(cMessage *event)

202 
{ 
203 
take(event); 
204  
205 
/* if (event>getArrivalTime()==simTime() && event>getSchedulingPriority()==0)

206 
{

207 
// scheduled for *now*  use circular buffer

208 
cb[cbtail] = event;

209 
event>heapindex = CBHEAPINDEX(cbtail);

210 
CBINC(cbtail);

211 
if (cbtail==cbhead)

212 
{

213 
// reallocate

214 
int newsize = 2*cbsize; // cbsize MUST be power of 2

215 
cMessage **newcb = new cMessage*[newsize];

216 
for (int i=0; i<cbsize; i++)

217 
(newcb[i] = cb[(cbhead+i)&(cbsize1)])>heapindex = CBHEAPINDEX(i);

218 
delete [] cb;

219 
cb = newcb;

220 
cbhead = 0;

221 
cbtail = cbsize;

222 
cbsize = newsize;

223 
}

224 
}

225 
else

226 
{*/

227 
// use heap

228 
int i,j;

229  
230 
event>insertordr = insertcntr++; 
231  
232 
if ((int)AO_fetch_and_add1(&n)+1 > size) 
233 
{ 
234 
size *= 2;

235 
cMessage **hnew = new cMessage *[size+1]; 
236 
for (i=1; i<=(int)AO_load(&n)1; i++) 
237 
hnew[i]=h[i]; 
238 
delete [] h;

239 
h = hnew; 
240 
} 
241  
242 
for (j=(int)AO_load(&n); j>1; j=i) 
243 
{ 
244 
i = j>>1;

245 
if (*h[i] <= *event) // direction 
246 
break;

247  
248 
(h[j]=h[i])>heapindex=j; 
249 
} 
250 
(h[j]=event)>heapindex=j; 
251 
//}

252 
} 
253  
254 
void cMessageHeap::shiftup(int from) 
255 
{ 
256 
// restores heap structure (in a subheap)

257 
int i,j;

258 
cMessage *temp; 
259  
260 
i = from; 
261 
while ((j=i<<1) <= (int)AO_load(&n)) 
262 
{ 
263 
if (j<(int)AO_load(&n) && (*h[j] > *h[j+1])) //direction 
264 
j++; 
265 
if (*h[i] > *h[j]) //is change necessary? 
266 
{ 
267 
temp=h[j]; 
268 
(h[j]=h[i])>heapindex=j; 
269 
(h[i]=temp)>heapindex=i; 
270 
i=j; 
271 
} 
272 
else

273 
break;

274 
} 
275 
} 
276  
277 
cMessage *cMessageHeap::peekFirst() const

278 
{ 
279 
return /*cbhead!=cbtail ? cb[cbhead] : */(int)AO_load((AO_t*)&n)!=0 ? h[1] : NULL; 
280 
} 
281  
282 
cMessage *cMessageHeap::removeFirst() 
283 
{ 
284 
/* if (cbhead != cbtail)

285 
{

286 
// remove head element from circular buffer

287 
cMessage *event = cb[cbhead];

288 
CBINC(cbhead);

289 
drop(event);

290 
event>heapindex=1;

291 
return event;

292 
}

293 
else */if ((int)AO_load(&n)>0) 
294 
{ 
295 
// heap: first is taken out and replaced by the last one

296 
cMessage *event = h[1];

297 
(h[1]=h[(int)AO_fetch_and_sub1(&n)])>heapindex=1; 
298 
shiftup(); 
299 
drop(event); 
300 
event>heapindex=1;

301 
return event;

302 
} 
303 
return NULL; 
304 
} 
305  
306 
cMessage *cMessageHeap::remove(cMessage *event) 
307 
{ 
308 
// make sure it is really on the heap

309 
if (event>heapindex==1) 
310 
return NULL; 
311  
312 
/*if (event>heapindex<0)

313 
{

314 
// event is in the circular buffer

315 
int i = event>heapindex2;

316 
ASSERT(cb[i]==event); // sanity check

317 

318 
// remove

319 
int iminus1 = i; CBINC(i);

320 
for (; i!=cbtail; iminus1=i, CBINC(i))

321 
(cb[iminus1] = cb[i])>heapindex = CBHEAPINDEX(iminus1);

322 
cbtail = (cbtail1)&(cbsize1);

323 
}

324 
else

325 
{*/

326 
// event is on the heap

327  
328 
// sanity check:

329 
// ASSERT(h[event>heapindex]==event);

330  
331 
// last element will be used to fill the hole

332 
int father, out = event>heapindex;

333 
cMessage *fill = h[(int)AO_fetch_and_sub1(&n)];

334 
while ((father=out>>1)!=0 && *h[father] > *fill) 
335 
{ 
336 
(h[out]=h[father])>heapindex=out; // father is moved down

337 
out=father; 
338 
} 
339 
(h[out]=fill)>heapindex=out; 
340 
shiftup(out); 
341 
//}

342  
343 
drop(event); 
344 
event>heapindex=1;

345 
return event;

346 
} 
347 