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 * SPDX-License-Identifier: GPL-2.0-only
6 *
7 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
8 *
9 */
10
11#include "heap-scheduler.h"
12
13#include "assert.h"
14#include "event-impl.h"
15#include "log.h"
16
17/**
18 * \file
19 * \ingroup scheduler
20 * Implementation of ns3::HeapScheduler class.
21 */
22
23namespace ns3
24{
25
26NS_LOG_COMPONENT_DEFINE("HeapScheduler");
27
28NS_OBJECT_ENSURE_REGISTERED(HeapScheduler);
29
30TypeId
32{
33 static TypeId tid = TypeId("ns3::HeapScheduler")
35 .SetGroupName("Core")
36 .AddConstructor<HeapScheduler>();
37 return tid;
38}
39
41{
42 NS_LOG_FUNCTION(this);
43 // we purposely waste an item at the start of
44 // the array to make sure the indexes in the
45 // array start at one.
46 Scheduler::Event empty = {nullptr, {0, 0}};
47 m_heap.push_back(empty);
48}
49
54
55std::size_t
56HeapScheduler::Parent(std::size_t id) const
57{
58 NS_LOG_FUNCTION(this << id);
59 return id / 2;
60}
61
62std::size_t
63HeapScheduler::Sibling(std::size_t id) const
64{
65 NS_LOG_FUNCTION(this << id);
66 return id + 1;
67}
68
69std::size_t
70HeapScheduler::LeftChild(std::size_t id) const
71{
72 NS_LOG_FUNCTION(this << id);
73 return id * 2;
74}
75
76std::size_t
77HeapScheduler::RightChild(std::size_t id) const
78{
79 NS_LOG_FUNCTION(this << id);
80 return id * 2 + 1;
81}
82
83std::size_t
85{
86 NS_LOG_FUNCTION(this);
87 return 1;
88}
89
90bool
91HeapScheduler::IsRoot(std::size_t id) const
92{
93 NS_LOG_FUNCTION(this << id);
94 return (id == Root());
95}
96
97std::size_t
99{
100 NS_LOG_FUNCTION(this);
101 return m_heap.size() - 1;
102}
103
104bool
105HeapScheduler::IsBottom(std::size_t id) const
106{
107 NS_LOG_FUNCTION(this << id);
108 return (id >= m_heap.size());
109}
110
111void
112HeapScheduler::Exch(std::size_t a, std::size_t b)
113{
114 NS_LOG_FUNCTION(this << a << b);
115 NS_ASSERT(b < m_heap.size() && a < m_heap.size());
116 NS_LOG_DEBUG("Exch " << a << ", " << b);
117 Event tmp(m_heap[a]);
118 m_heap[a] = m_heap[b];
119 m_heap[b] = tmp;
120}
121
122bool
123HeapScheduler::IsLessStrictly(std::size_t a, std::size_t b) const
124{
125 NS_LOG_FUNCTION(this << a << b);
126 return m_heap[a] < m_heap[b];
127}
128
129std::size_t
130HeapScheduler::Smallest(std::size_t a, std::size_t b) const
131{
132 NS_LOG_FUNCTION(this << a << b);
133 return IsLessStrictly(a, b) ? a : b;
134}
135
136bool
138{
139 NS_LOG_FUNCTION(this);
140 return (m_heap.size() == 1);
141}
142
143void
145{
146 NS_LOG_FUNCTION(this);
147 std::size_t index = Last();
148 while (!IsRoot(index) && IsLessStrictly(index, Parent(index)))
149 {
150 Exch(index, Parent(index));
151 index = Parent(index);
152 }
153}
154
155void
156HeapScheduler::TopDown(std::size_t start)
157{
158 NS_LOG_FUNCTION(this << start);
159 std::size_t index = start;
160 std::size_t right = RightChild(index);
161 while (!IsBottom(right))
162 {
163 std::size_t left = LeftChild(index);
164 std::size_t tmp = Smallest(left, right);
165 if (IsLessStrictly(index, tmp))
166 {
167 return;
168 }
169 Exch(index, tmp);
170 index = tmp;
171 right = RightChild(index);
172 }
173 if (IsBottom(index))
174 {
175 return;
176 }
177 NS_ASSERT(!IsBottom(index));
178 std::size_t left = LeftChild(index);
179 if (IsBottom(left))
180 {
181 return;
182 }
183 if (IsLessStrictly(index, left))
184 {
185 return;
186 }
187 Exch(index, left);
188}
189
190void
192{
193 NS_LOG_FUNCTION(this << &ev);
194 m_heap.push_back(ev);
195 BottomUp();
196}
197
200{
201 NS_LOG_FUNCTION(this);
202 return m_heap[Root()];
203}
204
207{
208 NS_LOG_FUNCTION(this);
209 Event next = m_heap[Root()];
210 Exch(Root(), Last());
211 m_heap.pop_back();
212 TopDown(Root());
213 return next;
214}
215
216void
218{
219 NS_LOG_FUNCTION(this << &ev);
220 std::size_t uid = ev.key.m_uid;
221 for (std::size_t i = 1; i < m_heap.size(); i++)
222 {
223 if (uid == m_heap[i].key.m_uid)
224 {
225 NS_ASSERT(m_heap[i].impl == ev.impl);
226 Exch(i, Last());
227 m_heap.pop_back();
228 TopDown(i);
229 return;
230 }
231 }
232 NS_ASSERT(false);
233}
234
235} // 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:146
a unique identifier for an interface.
Definition type-id.h:48
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition type-id.cc:1001
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:55
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition log.h:257
#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:35
ns3::HeapScheduler declaration.
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Scheduler event.
Definition scheduler.h:173
EventKey key
Key for sorting and ordering Events.
Definition scheduler.h:175
EventImpl * impl
Pointer to the event implementation.
Definition scheduler.h:174
uint32_t m_uid
Event unique id.
Definition scheduler.h:161