## root / src / sim / ctaskheap.cc @ 3e29b8a0

History | View | Annotate | Download (6.69 KB)

1 | 01873262 | Georg Kunz | ```
//=========================================================================
``` |
---|---|---|---|

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. 273-274)
``` |
||

12 | ```
// Georg Kunz
``` |
||

13 | ```
//
``` |
||

14 | ```
//=========================================================================
``` |
||

15 | |||

16 | ```
/*--------------------------------------------------------------*
``` |
||

17 | ```
Copyright (C) 1992-2005 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 | 5668c48e | Georg Kunz | ```
/*
``` |

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

44 | 01873262 | Georg Kunz | ```
{
``` |

45 | 5668c48e | Georg Kunz | ```
return (a.getTend() > b.getTend()) ? 1 :
``` |

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

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

48 | 01873262 | Georg Kunz | ```
}
``` |

49 | 5668c48e | Georg Kunz | ```
*/
``` |

50 | 01873262 | Georg Kunz | |

51 | 5668c48e | Georg Kunz | static inline bool operator > (cMessage& a, cMessage& b) |

52 | 01873262 | Georg Kunz | { |

53 | b9e9c37a | Simon Tenbusch | 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 | 5668c48e | Georg Kunz | 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 | 01873262 | Georg Kunz | } |

66 | |||

67 | 5668c48e | Georg Kunz | static inline bool operator <= (cMessage& a, cMessage& b) |

68 | { |
||

69 | ```
return !(a>b);
``` |
||

70 | } |
||

71 | 01873262 | Georg Kunz | |

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 | 5668c48e | Georg Kunz | return (m1->getTaskInsertOrder() < m2->getTaskInsertOrder()) ? -1 : 1; |

82 | 01873262 | Georg Kunz | } |

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..n-1 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<=n-1; 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 sub-heap)
``` |
||

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 | } |