A Discrete-Event Network Simulator
API
heap-scheduler.cc
Go to the documentation of this file.
1/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/*
3 * Copyright (c) 2006 INRIA
4 * Copyright (c) 2005 Mathieu Lacage
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 as
8 * published by the Free Software Foundation;
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 *
19 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
20 *
21 */
22
23#include "heap-scheduler.h"
24#include "event-impl.h"
25#include "assert.h"
26#include "log.h"
27
34namespace ns3 {
35
36NS_LOG_COMPONENT_DEFINE ("HeapScheduler");
37
38NS_OBJECT_ENSURE_REGISTERED (HeapScheduler);
39
40TypeId
42{
43 static TypeId tid = TypeId ("ns3::HeapScheduler")
45 .SetGroupName ("Core")
46 .AddConstructor<HeapScheduler> ()
47 ;
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 = { 0,{ 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}
72std::size_t
73HeapScheduler::Sibling (std::size_t id) const
74{
75 NS_LOG_FUNCTION (this << id);
76 return id + 1;
77}
78std::size_t
79HeapScheduler::LeftChild (std::size_t id) const
80{
81 NS_LOG_FUNCTION (this << id);
82 return id * 2;
83}
84std::size_t
85HeapScheduler::RightChild (std::size_t id) const
86{
87 NS_LOG_FUNCTION (this << id);
88 return id * 2 + 1;
89}
90
91std::size_t
93{
94 NS_LOG_FUNCTION (this);
95 return 1;
96}
97
98bool
99HeapScheduler::IsRoot (std::size_t id) const
100{
101 NS_LOG_FUNCTION (this << id);
102 return (id == Root ());
103}
104
105std::size_t
107{
108 NS_LOG_FUNCTION (this);
109 return m_heap.size () - 1;
110}
111
112
113bool
114HeapScheduler::IsBottom (std::size_t id) const
115{
116 NS_LOG_FUNCTION (this << id);
117 return (id >= m_heap.size ());
118}
119
120void
121HeapScheduler::Exch (std::size_t a, std::size_t b)
122{
123 NS_LOG_FUNCTION (this << a << b);
124 NS_ASSERT (b < m_heap.size () && a < m_heap.size ());
125 NS_LOG_DEBUG ("Exch " << a << ", " << b);
126 Event tmp (m_heap[a]);
127 m_heap[a] = m_heap[b];
128 m_heap[b] = tmp;
129}
130
131bool
132HeapScheduler::IsLessStrictly (std::size_t a, std::size_t b) const
133{
134 NS_LOG_FUNCTION (this << a << b);
135 return m_heap[a] < m_heap[b];
136}
137
138std::size_t
139HeapScheduler::Smallest (std::size_t a, std::size_t b) const
140{
141 NS_LOG_FUNCTION (this << a << b);
142 return IsLessStrictly (a,b) ? a : b;
143}
144
145bool
147{
148 NS_LOG_FUNCTION (this);
149 return (m_heap.size () == 1);
150}
151
152void
154{
155 NS_LOG_FUNCTION (this);
156 std::size_t index = Last ();
157 while (!IsRoot (index)
158 && IsLessStrictly (index, Parent (index)))
159 {
160 Exch (index, Parent (index));
161 index = Parent (index);
162 }
163}
164
165void
167{
168 NS_LOG_FUNCTION (this << start);
169 std::size_t index = start;
170 std::size_t right = RightChild (index);
171 while (!IsBottom (right))
172 {
173 std::size_t left = LeftChild (index);
174 std::size_t tmp = Smallest (left, right);
175 if (IsLessStrictly (index, tmp))
176 {
177 return;
178 }
179 Exch (index, tmp);
180 index = tmp;
181 right = RightChild (index);
182 }
183 if (IsBottom (index))
184 {
185 return;
186 }
187 NS_ASSERT (!IsBottom (index));
188 std::size_t left = LeftChild (index);
189 if (IsBottom (left))
190 {
191 return;
192 }
193 if (IsLessStrictly (index, left))
194 {
195 return;
196 }
197 Exch (index, left);
198}
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}
217{
218 NS_LOG_FUNCTION (this);
219 Event next = m_heap[Root ()];
220 Exch (Root (), Last ());
221 m_heap.pop_back ();
222 TopDown (Root ());
223 return next;
224}
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
247
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
a binary heap event scheduler
void TopDown(std::size_t start)
Percolate a deletion bubble down the heap.
bool IsLessStrictly(std::size_t a, std::size_t b) const
Compare (less than) two items.
HeapScheduler()
Constructor.
static TypeId GetTypeId(void)
Register this type.
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.
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.
virtual ~HeapScheduler()
Destructor.
virtual void Remove(const Scheduler::Event &ev)
Remove a specific event from the event list.
bool IsBottom(std::size_t id) const
Test if an index is at the bottom of the heap.
std::size_t Root(void) const
Get the root index of the heap.
virtual Scheduler::Event RemoveNext(void)
Remove the earliest event from the event list.
std::size_t LeftChild(std::size_t id) const
Get the left child of a given entry.
virtual bool IsEmpty(void) const
Test if the schedule is empty.
virtual void Insert(const Scheduler::Event &ev)
Insert a new Event in the schedule.
virtual Scheduler::Event PeekNext(void) const
Get a pointer to the next event.
void BottomUp(void)
Percolate a newly inserted Last item to its proper position.
std::size_t Last(void) const
Return the index of the last element.
Maintain the event list.
Definition: scheduler.h:156
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
make Callback use a separate empty type
Definition: empty.h:34
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:67
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
#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:45
ns3::HeapScheduler declaration.
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
def start()
Definition: core.py:1852
Scheduler event.
Definition: scheduler.h:182
EventKey key
Key for sorting and ordering Events.
Definition: scheduler.h:184
EventImpl * impl
Pointer to the event implementation.
Definition: scheduler.h:183
uint32_t m_uid
Event unique id.
Definition: scheduler.h:171