A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
heap-scheduler.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2006 INRIA
3 * Copyright (c) 2005 Mathieu Lacage
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation;
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 *
18 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19 *
20 */
21
22#include "heap-scheduler.h"
23
24#include "assert.h"
25#include "event-impl.h"
26#include "log.h"
27
34namespace ns3
35{
36
37NS_LOG_COMPONENT_DEFINE("HeapScheduler");
38
39NS_OBJECT_ENSURE_REGISTERED(HeapScheduler);
40
41TypeId
43{
44 static TypeId tid = TypeId("ns3::HeapScheduler")
46 .SetGroupName("Core")
47 .AddConstructor<HeapScheduler>();
48 return tid;
49}
50
52{
53 NS_LOG_FUNCTION(this);
54 // we purposely waste an item at the start of
55 // the array to make sure the indexes in the
56 // array start at one.
57 Scheduler::Event empty = {nullptr, {0, 0}};
58 m_heap.push_back(empty);
59}
60
62{
63 NS_LOG_FUNCTION(this);
64}
65
66std::size_t
67HeapScheduler::Parent(std::size_t id) const
68{
69 NS_LOG_FUNCTION(this << id);
70 return id / 2;
71}
72
73std::size_t
74HeapScheduler::Sibling(std::size_t id) const
75{
76 NS_LOG_FUNCTION(this << id);
77 return id + 1;
78}
79
80std::size_t
81HeapScheduler::LeftChild(std::size_t id) const
82{
83 NS_LOG_FUNCTION(this << id);
84 return id * 2;
85}
86
87std::size_t
88HeapScheduler::RightChild(std::size_t id) const
89{
90 NS_LOG_FUNCTION(this << id);
91 return id * 2 + 1;
92}
93
94std::size_t
96{
97 NS_LOG_FUNCTION(this);
98 return 1;
99}
100
101bool
102HeapScheduler::IsRoot(std::size_t id) const
103{
104 NS_LOG_FUNCTION(this << id);
105 return (id == Root());
106}
107
108std::size_t
110{
111 NS_LOG_FUNCTION(this);
112 return m_heap.size() - 1;
113}
114
115bool
116HeapScheduler::IsBottom(std::size_t id) const
117{
118 NS_LOG_FUNCTION(this << id);
119 return (id >= m_heap.size());
120}
121
122void
123HeapScheduler::Exch(std::size_t a, std::size_t b)
124{
125 NS_LOG_FUNCTION(this << a << b);
126 NS_ASSERT(b < m_heap.size() && a < m_heap.size());
127 NS_LOG_DEBUG("Exch " << a << ", " << b);
128 Event tmp(m_heap[a]);
129 m_heap[a] = m_heap[b];
130 m_heap[b] = tmp;
131}
132
133bool
134HeapScheduler::IsLessStrictly(std::size_t a, std::size_t b) const
135{
136 NS_LOG_FUNCTION(this << a << b);
137 return m_heap[a] < m_heap[b];
138}
139
140std::size_t
141HeapScheduler::Smallest(std::size_t a, std::size_t b) const
142{
143 NS_LOG_FUNCTION(this << a << b);
144 return IsLessStrictly(a, b) ? a : b;
145}
146
147bool
149{
150 NS_LOG_FUNCTION(this);
151 return (m_heap.size() == 1);
152}
153
154void
156{
157 NS_LOG_FUNCTION(this);
158 std::size_t index = Last();
159 while (!IsRoot(index) && IsLessStrictly(index, Parent(index)))
160 {
161 Exch(index, Parent(index));
162 index = Parent(index);
163 }
164}
165
166void
167HeapScheduler::TopDown(std::size_t start)
168{
169 NS_LOG_FUNCTION(this << start);
170 std::size_t index = start;
171 std::size_t right = RightChild(index);
172 while (!IsBottom(right))
173 {
174 std::size_t left = LeftChild(index);
175 std::size_t tmp = Smallest(left, right);
176 if (IsLessStrictly(index, tmp))
177 {
178 return;
179 }
180 Exch(index, tmp);
181 index = tmp;
182 right = RightChild(index);
183 }
184 if (IsBottom(index))
185 {
186 return;
187 }
188 NS_ASSERT(!IsBottom(index));
189 std::size_t left = LeftChild(index);
190 if (IsBottom(left))
191 {
192 return;
193 }
194 if (IsLessStrictly(index, left))
195 {
196 return;
197 }
198 Exch(index, left);
199}
200
201void
203{
204 NS_LOG_FUNCTION(this << &ev);
205 m_heap.push_back(ev);
206 BottomUp();
207}
208
211{
212 NS_LOG_FUNCTION(this);
213 return m_heap[Root()];
214}
215
218{
219 NS_LOG_FUNCTION(this);
220 Event next = m_heap[Root()];
221 Exch(Root(), Last());
222 m_heap.pop_back();
223 TopDown(Root());
224 return next;
225}
226
227void
229{
230 NS_LOG_FUNCTION(this << &ev);
231 std::size_t uid = ev.key.m_uid;
232 for (std::size_t i = 1; i < m_heap.size(); i++)
233 {
234 if (uid == m_heap[i].key.m_uid)
235 {
236 NS_ASSERT(m_heap[i].impl == ev.impl);
237 Exch(i, Last());
238 m_heap.pop_back();
239 TopDown(i);
240 return;
241 }
242 }
243 NS_ASSERT(false);
244}
245
246} // namespace ns3
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
a binary heap event scheduler
std::size_t Root() const
Get the root index of the heap.
void TopDown(std::size_t start)
Percolate a deletion bubble down the heap.
void Insert(const Scheduler::Event &ev) override
Insert a new Event in the schedule.
~HeapScheduler() override
Destructor.
static TypeId GetTypeId()
Register this type.
Scheduler::Event RemoveNext() override
Remove the earliest event from the event list.
bool IsLessStrictly(std::size_t a, std::size_t b) const
Compare (less than) two items.
HeapScheduler()
Constructor.
std::size_t RightChild(std::size_t id) const
Get the right child index of a given entry.
BinaryHeap m_heap
The event list.
bool IsRoot(std::size_t id) const
Test if an index is the root.
Scheduler::Event PeekNext() const override
Get a pointer to the next event.
void Remove(const Scheduler::Event &ev) override
Remove a specific event from the event list.
void Exch(std::size_t a, std::size_t b)
Swap two items.
std::size_t Smallest(std::size_t a, std::size_t b) const
Minimum of two items.
std::size_t Sibling(std::size_t id) const
Get the next sibling of a given entry.
std::size_t Parent(std::size_t id) const
Get the parent index of a given entry.
bool IsBottom(std::size_t id) const
Test if an index is at the bottom of the heap.
std::size_t LeftChild(std::size_t id) const
Get the left child of a given entry.
void BottomUp()
Percolate a newly inserted Last item to its proper position.
std::size_t Last() const
Return the index of the last element.
bool IsEmpty() const override
Test if the schedule is empty.
Maintain the event list.
Definition: scheduler.h:157
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:936
ns3::EventImpl declarations.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
Definition: assert.h:66
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:268
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:46
ns3::HeapScheduler declaration.
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Scheduler event.
Definition: scheduler.h:184
EventKey key
Key for sorting and ordering Events.
Definition: scheduler.h:186
EventImpl * impl
Pointer to the event implementation.
Definition: scheduler.h:185
uint32_t m_uid
Event unique id.
Definition: scheduler.h:172