root / src / sim / cmessageheap.cc @ e26d3d25
History  View  Annotate  Download (7.95 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 
inline bool operator > (cMessage& a, cMessage& b) 
41 
{ 
42 
return a.getArrivalTime() > b.getArrivalTime() ? true : 
43 
a.getArrivalTime() < b.getArrivalTime() ? false :

44 
(a.getSchedulingPriority() > b.getSchedulingPriority()) ? true :

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

46 
a.getInsertOrder() > b.getInsertOrder(); 
47 
} 
48  
49 
inline bool operator <= (cMessage& a, cMessage& b) 
50 
{ 
51 
return !(a>b);

52 
} 
53  
54  
55 
static int qsort_cmp_msgs(const void *p1, const void *p2) 
56 
{ 
57 
cMessage *m1 = *(cMessage **)p1; 
58 
cMessage *m2 = *(cMessage **)p2; 
59  
60 
if (m1>getArrivalTime() < m2>getArrivalTime())

61 
return 1; 
62 
if (m1>getArrivalTime() > m2>getArrivalTime())

63 
return 1; 
64  
65 
int dpri = m1>getSchedulingPriority()  m2>getSchedulingPriority();

66 
if (dpri) return dpri; 
67  
68 
return (m1>getInsertOrder() < m2>getInsertOrder()) ? 1 : 1; 
69 
} 
70  
71 
//

72  
73 
cMessageHeap::cMessageHeap(const char *name, int siz) : cOwnedObject(name, false) 
74 
{ 
75 
insertcntr = 0L;

76  
77 
AO_store(&n, 0);

78 
size = siz; 
79 
h = new cMessage *[size+1]; // +1 is necessary because h[0] is not used 
80  
81 
/* cbsize = 4; // must be power of 2!

82 
cb = new cMessage *[cbsize];

83 
cbhead = cbtail = 0;*/

84 
} 
85  
86 
cMessageHeap::cMessageHeap(const cMessageHeap& heap) : cOwnedObject()

87 
{ 
88 
h=NULL; AO_store(&n, 0); 
89 
setName(heap.getName()); 
90 
operator=(heap);

91 
} 
92  
93 
cMessageHeap::~cMessageHeap() 
94 
{ 
95 
clear(); 
96 
delete [] h;

97 
//delete [] cb;

98 
} 
99  
100 
std::string cMessageHeap::info() const 
101 
{ 
102 
if (isEmpty())

103 
return std::string("empty"); 
104 
std::stringstream out; 
105 
out << "length=" << getLength();

106 
return out.str();

107 
} 
108  
109 
void cMessageHeap::forEachChild(cVisitor *v)

110 
{ 
111 
sort(); 
112  
113 
/* for (int i=cbhead; i!=cbtail; CBINC(i))

114 
v>visit(cb[i]);

115 
*/

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

118 
v>visit(h[i]); 
119 
} 
120  
121 
void cMessageHeap::clear()

122 
{ 
123 
/* for (int i=cbhead; i!=cbtail; CBINC(i))

124 
dropAndDelete(cb[i]);

125 
cbhead = cbtail = 0;

126 
*/

127 
for (int i=1; i<=(int)AO_load(&n); i++) 
128 
dropAndDelete(h[i]); 
129 
AO_store(&n, 0);

130 
} 
131  
132 
cMessageHeap& cMessageHeap::operator=(const cMessageHeap& heap) 
133 
{ 
134 
if (this==&heap) return *this; 
135  
136 
clear(); 
137  
138 
cOwnedObject::operator=(heap);

139  
140 
// copy heap

141 
AO_store(&n, (int)AO_load(&(heap.n)));

142 
size = heap.size; 
143 
delete [] h;

144 
h = new cMessage *[size+1]; 
145 
for (int i=1; i<=(int)AO_load(&n); i++) 
146 
take( h[i]=(cMessage *)heap.h[i]>dup() ); 
147  
148 
/* // copy circular buffer

149 
cbhead = heap.cbhead;

150 
cbtail = heap.cbtail;

151 
cbsize = heap.cbsize;

152 
delete [] cb;

153 
cb = new cMessage *[cbsize];

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

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

156 
*/

157 
return *this; 
158 
} 
159  
160 
cMessage *cMessageHeap::peek(int m)

161 
{ 
162 
if (m < 0) 
163 
return NULL; 
164 
/*

165 
// first few elements map into the circular buffer

166 
int cblen = cblength();

167 
if (m < cblen)

168 
return cbget(m);

169 
m = cblen;

170 
*/

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

172 
if (m >= (int)AO_load(&n)) 
173 
return NULL; 
174 
return h[m+1]; 
175 
} 
176  
177 
void cMessageHeap::sort()

178 
{ 
179 
qsort(h+1,(int)AO_load(&n),sizeof(cMessage *),qsort_cmp_msgs); 
180 
for (int i=1; i<=(int)AO_load(&n); i++) 
181 
h[i]>heapindex=i; 
182 
} 
183  
184 
void cMessageHeap::insert(cMessage *event)

185 
{ 
186 
take(event); 
187  
188 
/* if (event>getArrivalTime()==simTime() && event>getSchedulingPriority()==0)

189 
{

190 
// scheduled for *now*  use circular buffer

191 
cb[cbtail] = event;

192 
event>heapindex = CBHEAPINDEX(cbtail);

193 
CBINC(cbtail);

194 
if (cbtail==cbhead)

195 
{

196 
// reallocate

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

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

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

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

201 
delete [] cb;

202 
cb = newcb;

203 
cbhead = 0;

204 
cbtail = cbsize;

205 
cbsize = newsize;

206 
}

207 
}

208 
else

209 
{*/

210 
// use heap

211 
int i,j;

212  
213 
event>insertordr = insertcntr++; 
214  
215 
if ((int)AO_fetch_and_add1(&n)+1 > size) 
216 
{ 
217 
size *= 2;

218 
cMessage **hnew = new cMessage *[size+1]; 
219 
for (i=1; i<=(int)AO_load(&n)1; i++) 
220 
hnew[i]=h[i]; 
221 
delete [] h;

222 
h = hnew; 
223 
} 
224  
225 
for (j=(int)AO_load(&n); j>1; j=i) 
226 
{ 
227 
i = j>>1;

228 
if (*h[i] <= *event) // direction 
229 
break;

230  
231 
(h[j]=h[i])>heapindex=j; 
232 
} 
233 
(h[j]=event)>heapindex=j; 
234 
//}

235 
} 
236  
237 
void cMessageHeap::shiftup(int from) 
238 
{ 
239 
// restores heap structure (in a subheap)

240 
int i,j;

241 
cMessage *temp; 
242  
243 
i = from; 
244 
while ((j=i<<1) <= (int)AO_load(&n)) 
245 
{ 
246 
if (j<(int)AO_load(&n) && (*h[j] > *h[j+1])) //direction 
247 
j++; 
248 
if (*h[i] > *h[j]) //is change necessary? 
249 
{ 
250 
temp=h[j]; 
251 
(h[j]=h[i])>heapindex=j; 
252 
(h[i]=temp)>heapindex=i; 
253 
i=j; 
254 
} 
255 
else

256 
break;

257 
} 
258 
} 
259  
260 
cMessage *cMessageHeap::peekFirst() const

261 
{ 
262 
return /*cbhead!=cbtail ? cb[cbhead] : */(int)AO_load(&n)!=0 ? h[1] : NULL; 
263 
} 
264  
265 
cMessage *cMessageHeap::removeFirst() 
266 
{ 
267 
/* if (cbhead != cbtail)

268 
{

269 
// remove head element from circular buffer

270 
cMessage *event = cb[cbhead];

271 
CBINC(cbhead);

272 
drop(event);

273 
event>heapindex=1;

274 
return event;

275 
}

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

279 
cMessage *event = h[1];

280 
(h[1]=h[(int)AO_fetch_and_sub1(&n)])>heapindex=1; 
281 
shiftup(); 
282 
drop(event); 
283 
event>heapindex=1;

284 
return event;

285 
} 
286 
return NULL; 
287 
} 
288  
289 
cMessage *cMessageHeap::remove(cMessage *event) 
290 
{ 
291 
// make sure it is really on the heap

292 
if (event>heapindex==1) 
293 
return NULL; 
294  
295 
/*if (event>heapindex<0)

296 
{

297 
// event is in the circular buffer

298 
int i = event>heapindex2;

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

300 

301 
// remove

302 
int iminus1 = i; CBINC(i);

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

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

305 
cbtail = (cbtail1)&(cbsize1);

306 
}

307 
else

308 
{*/

309 
// event is on the heap

310  
311 
// sanity check:

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

313  
314 
// last element will be used to fill the hole

315 
int father, out = event>heapindex;

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

317 
while ((father=out>>1)!=0 && *h[father] > *fill) 
318 
{ 
319 
(h[out]=h[father])>heapindex=out; // father is moved down

320 
out=father; 
321 
} 
322 
(h[out]=fill)>heapindex=out; 
323 
shiftup(out); 
324 
//}

325  
326 
drop(event); 
327 
event>heapindex=1;

328 
return event;

329 
} 
330 