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 
34 namespace ns3 {
35 
36 NS_LOG_COMPONENT_DEFINE ("HeapScheduler");
37 
38 NS_OBJECT_ENSURE_REGISTERED (HeapScheduler);
39 
40 TypeId
42 {
43  static TypeId tid = TypeId ("ns3::HeapScheduler")
44  .SetParent<Scheduler> ()
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 
66 std::size_t
67 HeapScheduler::Parent (std::size_t id) const
68 {
69  NS_LOG_FUNCTION (this << id);
70  return id / 2;
71 }
72 std::size_t
73 HeapScheduler::Sibling (std::size_t id) const
74 {
75  NS_LOG_FUNCTION (this << id);
76  return id + 1;
77 }
78 std::size_t
79 HeapScheduler::LeftChild (std::size_t id) const
80 {
81  NS_LOG_FUNCTION (this << id);
82  return id * 2;
83 }
84 std::size_t
85 HeapScheduler::RightChild (std::size_t id) const
86 {
87  NS_LOG_FUNCTION (this << id);
88  return id * 2 + 1;
89 }
90 
91 std::size_t
92 HeapScheduler::Root (void) const
93 {
94  NS_LOG_FUNCTION (this);
95  return 1;
96 }
97 
98 bool
99 HeapScheduler::IsRoot (std::size_t id) const
100 {
101  NS_LOG_FUNCTION (this << id);
102  return (id == Root ()) ? true : false;
103 }
104 
105 std::size_t
107 {
108  NS_LOG_FUNCTION (this);
109  return m_heap.size () - 1;
110 }
111 
112 
113 bool
114 HeapScheduler::IsBottom (std::size_t id) const
115 {
116  NS_LOG_FUNCTION (this << id);
117  return (id >= m_heap.size ()) ? true : false;
118 }
119 
120 void
121 HeapScheduler::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 
131 bool
132 HeapScheduler::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 
138 std::size_t
139 HeapScheduler::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 
145 bool
147 {
148  NS_LOG_FUNCTION (this);
149  return (m_heap.size () == 1) ? true : false;
150 }
151 
152 void
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 
165 void
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 
201 void
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 
227 void
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 
virtual Scheduler::Event PeekNext(void) const
Get a pointer to the next event.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
virtual ~HeapScheduler()
Destructor.
ns3::EventImpl declarations.
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
std::size_t Last(void) const
Return the index of the last element.
ns3::HeapScheduler declaration.
bool IsRoot(std::size_t id) const
Test if an index is the root.
std::size_t Parent(std::size_t id) const
Get the parent index of a given entry.
virtual Scheduler::Event RemoveNext(void)
Remove the earliest event from the event list.
def start()
Definition: core.py:1844
EventImpl * impl
Pointer to the event implementation.
Definition: scheduler.h:94
#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:202
std::size_t Sibling(std::size_t id) const
Get the next sibling of a given entry.
static TypeId GetTypeId(void)
Register this type.
bool IsLessStrictly(std::size_t a, std::size_t b) const
Compare (less than) two items.
make Callback use a separate empty type
Definition: empty.h:33
a binary heap event scheduler
EventKey key
Key for sorting and ordering Events.
Definition: scheduler.h:95
uint32_t m_uid
Event unique id.
Definition: scheduler.h:82
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
Maintain the event list.
Definition: scheduler.h:66
virtual void Insert(const Scheduler::Event &ev)
Insert a new Event in the schedule.
std::size_t RightChild(std::size_t id) const
Get the right child index of a given entry.
std::size_t LeftChild(std::size_t id) const
Get the left child of a given entry.
BinaryHeap m_heap
The event list.
Scheduler event.
Definition: scheduler.h:92
void Exch(std::size_t a, std::size_t b)
Swap two items.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
HeapScheduler()
Constructor.
std::size_t Root(void) const
Get the root index of the heap.
virtual bool IsEmpty(void) const
Test if the schedule is empty.
bool IsBottom(std::size_t id) const
Test if an index is at the bottom of the heap.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:270
virtual void Remove(const Scheduler::Event &ev)
Remove a specific event from the event list.
void BottomUp(void)
Percolate a newly inserted Last item to its proper position.
std::size_t Smallest(std::size_t a, std::size_t b) const
Minimum of two items.
Debug message logging.
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:915
void TopDown(std::size_t start)
Percolate a deletion bubble down the heap.