51 |
51 |
52 namespace ns3 { |
52 namespace ns3 { |
53 |
53 |
54 SchedulerHeap::SchedulerHeap () |
54 SchedulerHeap::SchedulerHeap () |
55 { |
55 { |
56 // we purposedly waste an item at the start of |
56 // we purposedly waste an item at the start of |
57 // the array to make sure the indexes in the |
57 // the array to make sure the indexes in the |
58 // array start at one. |
58 // array start at one. |
59 Scheduler::EventKey emptyKey = {0,0}; |
59 Scheduler::EventKey emptyKey = {0,0}; |
60 m_heap.push_back (std::make_pair (static_cast<EventImpl *>(0), emptyKey)); |
60 m_heap.push_back (std::make_pair (static_cast<EventImpl *>(0), emptyKey)); |
61 } |
61 } |
62 |
62 |
63 SchedulerHeap::~SchedulerHeap () |
63 SchedulerHeap::~SchedulerHeap () |
64 {} |
64 {} |
65 |
65 |
66 void |
66 void |
67 SchedulerHeap::StoreInEvent (EventImpl *ev, uint32_t index) const |
67 SchedulerHeap::StoreInEvent (EventImpl *ev, uint32_t index) const |
68 { |
68 { |
69 long tmp = index; |
69 long tmp = index; |
70 ev->SetInternalIterator ((void *)tmp); |
70 ev->SetInternalIterator ((void *)tmp); |
71 } |
71 } |
72 uint32_t |
72 uint32_t |
73 SchedulerHeap::GetFromEvent (EventImpl *ev) const |
73 SchedulerHeap::GetFromEvent (EventImpl *ev) const |
74 { |
74 { |
75 long tmp = (long)ev->GetInternalIterator (); |
75 long tmp = (long)ev->GetInternalIterator (); |
76 return (uint32_t)tmp; |
76 return (uint32_t)tmp; |
77 } |
77 } |
78 uint32_t |
78 uint32_t |
79 SchedulerHeap::Parent (uint32_t id) const |
79 SchedulerHeap::Parent (uint32_t id) const |
80 { |
80 { |
81 return id / 2; |
81 return id / 2; |
82 } |
82 } |
83 uint32_t |
83 uint32_t |
84 SchedulerHeap::Sibling (uint32_t id) const |
84 SchedulerHeap::Sibling (uint32_t id) const |
85 { |
85 { |
86 return id + 1; |
86 return id + 1; |
87 } |
87 } |
88 uint32_t |
88 uint32_t |
89 SchedulerHeap::LeftChild (uint32_t id) const |
89 SchedulerHeap::LeftChild (uint32_t id) const |
90 { |
90 { |
91 return id * 2; |
91 return id * 2; |
92 } |
92 } |
93 uint32_t |
93 uint32_t |
94 SchedulerHeap::RightChild (uint32_t id) const |
94 SchedulerHeap::RightChild (uint32_t id) const |
95 { |
95 { |
96 return id * 2 + 1; |
96 return id * 2 + 1; |
97 } |
97 } |
98 |
98 |
99 uint32_t |
99 uint32_t |
100 SchedulerHeap::Root (void) const |
100 SchedulerHeap::Root (void) const |
101 { |
101 { |
102 return 1; |
102 return 1; |
103 } |
103 } |
104 |
104 |
105 bool |
105 bool |
106 SchedulerHeap::IsRoot (uint32_t id) const |
106 SchedulerHeap::IsRoot (uint32_t id) const |
107 { |
107 { |
108 return (id == Root ())?true:false; |
108 return (id == Root ())?true:false; |
109 } |
109 } |
110 |
110 |
111 uint32_t |
111 uint32_t |
112 SchedulerHeap::Last (void) const |
112 SchedulerHeap::Last (void) const |
113 { |
113 { |
114 return m_heap.size () - 1; |
114 return m_heap.size () - 1; |
115 } |
115 } |
116 |
116 |
117 |
117 |
118 bool |
118 bool |
119 SchedulerHeap::IsBottom (uint32_t id) const |
119 SchedulerHeap::IsBottom (uint32_t id) const |
120 { |
120 { |
121 return (id >= m_heap.size ())?true:false; |
121 return (id >= m_heap.size ())?true:false; |
122 } |
122 } |
123 |
123 |
124 void |
124 void |
125 SchedulerHeap::Exch (uint32_t a, uint32_t b) |
125 SchedulerHeap::Exch (uint32_t a, uint32_t b) |
126 { |
126 { |
127 assert (b < m_heap.size () && a < m_heap.size ()); |
127 assert (b < m_heap.size () && a < m_heap.size ()); |
128 TRACE ("Exch " << a << ", " << b); |
128 TRACE ("Exch " << a << ", " << b); |
129 std::pair<EventImpl*, Scheduler::EventKey> tmp (m_heap[a]); |
129 std::pair<EventImpl*, Scheduler::EventKey> tmp (m_heap[a]); |
130 m_heap[a] = m_heap[b]; |
130 m_heap[a] = m_heap[b]; |
131 m_heap[b] = tmp; |
131 m_heap[b] = tmp; |
132 StoreInEvent (m_heap[a].first, a); |
132 StoreInEvent (m_heap[a].first, a); |
133 StoreInEvent (m_heap[b].first, b); |
133 StoreInEvent (m_heap[b].first, b); |
134 } |
134 } |
135 |
135 |
136 bool |
136 bool |
137 SchedulerHeap::IsLess (uint32_t a, uint32_t b) |
137 SchedulerHeap::IsLess (uint32_t a, uint32_t b) |
138 { |
138 { |
139 Scheduler::EventKeyCompare compare; |
139 Scheduler::EventKeyCompare compare; |
140 return compare (m_heap[a].second, m_heap[b].second); |
140 return compare (m_heap[a].second, m_heap[b].second); |
141 } |
141 } |
142 |
142 |
143 uint32_t |
143 uint32_t |
144 SchedulerHeap::Smallest (uint32_t a, uint32_t b) |
144 SchedulerHeap::Smallest (uint32_t a, uint32_t b) |
145 { |
145 { |
146 return IsLess (a,b)?a:b; |
146 return IsLess (a,b)?a:b; |
147 } |
147 } |
148 |
148 |
149 bool |
149 bool |
150 SchedulerHeap::RealIsEmpty (void) const |
150 SchedulerHeap::RealIsEmpty (void) const |
151 { |
151 { |
152 return (m_heap.size () == 1)?true:false; |
152 return (m_heap.size () == 1)?true:false; |
153 } |
153 } |
154 |
154 |
155 void |
155 void |
156 SchedulerHeap::BottomUp (void) |
156 SchedulerHeap::BottomUp (void) |
157 { |
157 { |
158 uint32_t index = Last (); |
158 uint32_t index = Last (); |
159 while (!IsRoot (index) && |
159 while (!IsRoot (index) && |
160 IsLess (index, Parent (index))) |
160 IsLess (index, Parent (index))) |
161 { |
161 { |
162 Exch(index, Parent (index)); |
162 Exch(index, Parent (index)); |
163 index = Parent (index); |
163 index = Parent (index); |
164 } |
164 } |
165 } |
165 } |
166 |
166 |
167 void |
167 void |
168 SchedulerHeap::TopDown (void) |
168 SchedulerHeap::TopDown (void) |
169 { |
169 { |
170 uint32_t index = Root (); |
170 uint32_t index = Root (); |
171 uint32_t right = RightChild (index); |
171 uint32_t right = RightChild (index); |
172 while (!IsBottom (right)) |
172 while (!IsBottom (right)) |
173 { |
173 { |
174 uint32_t left = LeftChild (index); |
174 uint32_t left = LeftChild (index); |
175 uint32_t tmp = Smallest (left, right); |
175 uint32_t tmp = Smallest (left, right); |
176 if (IsLess (index, tmp)) |
176 if (IsLess (index, tmp)) |
177 { |
177 { |
178 return; |
178 return; |
179 } |
179 } |
180 Exch (index, tmp); |
180 Exch (index, tmp); |
181 index = tmp; |
181 index = tmp; |
182 right = RightChild (index); |
182 right = RightChild (index); |
183 } |
183 } |
184 if (IsBottom (index)) |
184 if (IsBottom (index)) |
185 { |
185 { |
186 return; |
186 return; |
187 } |
187 } |
188 assert (!IsBottom (index)); |
188 assert (!IsBottom (index)); |
189 uint32_t left = LeftChild (index); |
189 uint32_t left = LeftChild (index); |
190 if (IsBottom (left)) |
190 if (IsBottom (left)) |
191 { |
191 { |
192 return; |
192 return; |
193 } |
193 } |
194 if (IsLess (index, left)) |
194 if (IsLess (index, left)) |
195 { |
195 { |
196 return; |
196 return; |
197 } |
197 } |
198 Exch (index, left); |
198 Exch (index, left); |
199 } |
199 } |
200 |
200 |
201 |
201 |
202 EventId |
202 EventId |
203 SchedulerHeap::RealInsert (EventImpl *event, Scheduler::EventKey key) |
203 SchedulerHeap::RealInsert (EventImpl *event, Scheduler::EventKey key) |
204 { |
204 { |
205 m_heap.push_back (std::make_pair (event, key)); |
205 m_heap.push_back (std::make_pair (event, key)); |
206 BottomUp (); |
206 BottomUp (); |
207 StoreInEvent (event, Last ()); |
207 StoreInEvent (event, Last ()); |
208 return EventId (event, key.m_ns, key.m_uid); |
208 return EventId (event, key.m_ns, key.m_uid); |
209 } |
209 } |
210 |
210 |
211 EventImpl * |
211 EventImpl * |
212 SchedulerHeap::RealPeekNext (void) const |
212 SchedulerHeap::RealPeekNext (void) const |
213 { |
213 { |
214 return m_heap[Root ()].first; |
214 return m_heap[Root ()].first; |
215 } |
215 } |
216 Scheduler::EventKey |
216 Scheduler::EventKey |
217 SchedulerHeap::RealPeekNextKey (void) const |
217 SchedulerHeap::RealPeekNextKey (void) const |
218 { |
218 { |
219 return m_heap[Root ()].second; |
219 return m_heap[Root ()].second; |
220 } |
220 } |
221 void |
221 void |
222 SchedulerHeap::RealRemoveNext (void) |
222 SchedulerHeap::RealRemoveNext (void) |
223 { |
223 { |
224 Exch (Root (), Last ()); |
224 Exch (Root (), Last ()); |
225 m_heap.pop_back (); |
225 m_heap.pop_back (); |
226 TopDown (); |
226 TopDown (); |
227 } |
227 } |
228 |
228 |
229 |
229 |
230 EventImpl * |
230 EventImpl * |
231 SchedulerHeap::RealRemove (EventId id, Scheduler::EventKey *key) |
231 SchedulerHeap::RealRemove (EventId id, Scheduler::EventKey *key) |
232 { |
232 { |
233 EventImpl *ev = id.GetEventImpl (); |
233 EventImpl *ev = id.GetEventImpl (); |
234 uint32_t i = GetFromEvent (ev); |
234 uint32_t i = GetFromEvent (ev); |
235 *key = m_heap[i].second; |
235 *key = m_heap[i].second; |
236 Exch (i, Last ()); |
236 Exch (i, Last ()); |
237 m_heap.pop_back (); |
237 m_heap.pop_back (); |
238 TopDown (); |
238 TopDown (); |
239 return ev; |
239 return ev; |
240 } |
240 } |
241 |
241 |
242 bool |
242 bool |
243 SchedulerHeap::RealIsValid (EventId id) |
243 SchedulerHeap::RealIsValid (EventId id) |
244 { |
244 { |
245 EventImpl *ev = id.GetEventImpl (); |
245 EventImpl *ev = id.GetEventImpl (); |
246 uint32_t i = GetFromEvent (ev); |
246 uint32_t i = GetFromEvent (ev); |
247 Scheduler::EventKey key = m_heap[i].second; |
247 Scheduler::EventKey key = m_heap[i].second; |
248 return (key.m_ns == id.GetNs () && |
248 return (key.m_ns == id.GetNs () && |
249 key.m_uid == id.GetUid ()); |
249 key.m_uid == id.GetUid ()); |
250 } |
250 } |
251 }; // namespace ns3 |
251 }; // namespace ns3 |