A Discrete-Event Network Simulator
Home
Tutorials ▼
English
Portuguese
Docs ▼
Wiki
Manual
Models
Develop ▼
API
Bugs
API
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Friends
Macros
Groups
Pages
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
28
NS_LOG_COMPONENT_DEFINE
(
"HeapScheduler"
);
29
30
namespace
ns3 {
31
32
NS_OBJECT_ENSURE_REGISTERED
(HeapScheduler);
33
34
TypeId
35
HeapScheduler::GetTypeId
(
void
)
36
{
37
static
TypeId
tid =
TypeId
(
"ns3::HeapScheduler"
)
38
.
SetParent
<
Scheduler
> ()
39
.AddConstructor<HeapScheduler> ()
40
;
41
return
tid;
42
}
43
44
HeapScheduler::HeapScheduler
()
45
{
46
NS_LOG_FUNCTION
(
this
);
47
// we purposedly waste an item at the start of
48
// the array to make sure the indexes in the
49
// array start at one.
50
Scheduler::Event
empty
= { 0,{ 0,0}};
51
m_heap
.push_back (empty);
52
}
53
54
HeapScheduler::~HeapScheduler
()
55
{
56
NS_LOG_FUNCTION
(
this
);
57
}
58
59
uint32_t
60
HeapScheduler::Parent
(uint32_t
id
)
const
61
{
62
NS_LOG_FUNCTION
(
this
<<
id
);
63
return
id
/ 2;
64
}
65
uint32_t
66
HeapScheduler::Sibling
(uint32_t
id
)
const
67
{
68
NS_LOG_FUNCTION
(
this
<<
id
);
69
return
id
+ 1;
70
}
71
uint32_t
72
HeapScheduler::LeftChild
(uint32_t
id
)
const
73
{
74
NS_LOG_FUNCTION
(
this
<<
id
);
75
return
id
* 2;
76
}
77
uint32_t
78
HeapScheduler::RightChild
(uint32_t
id
)
const
79
{
80
NS_LOG_FUNCTION
(
this
<<
id
);
81
return
id
* 2 + 1;
82
}
83
84
uint32_t
85
HeapScheduler::Root
(
void
)
const
86
{
87
NS_LOG_FUNCTION
(
this
);
88
return
1;
89
}
90
91
bool
92
HeapScheduler::IsRoot
(uint32_t
id
)
const
93
{
94
NS_LOG_FUNCTION
(
this
<<
id
);
95
return
(
id
==
Root
()) ?
true
:
false
;
96
}
97
98
uint32_t
99
HeapScheduler::Last
(
void
)
const
100
{
101
NS_LOG_FUNCTION
(
this
);
102
return
m_heap
.size () - 1;
103
}
104
105
106
bool
107
HeapScheduler::IsBottom
(uint32_t
id
)
const
108
{
109
NS_LOG_FUNCTION
(
this
<<
id
);
110
return
(
id
>=
m_heap
.size ()) ?
true
:
false
;
111
}
112
113
void
114
HeapScheduler::Exch
(uint32_t a, uint32_t b)
115
{
116
NS_LOG_FUNCTION
(
this
<< a << b);
117
NS_ASSERT
(b <
m_heap
.size () && a <
m_heap
.size ());
118
NS_LOG_DEBUG
(
"Exch "
<< a <<
", "
<< b);
119
Event tmp (
m_heap
[a]);
120
m_heap
[a] =
m_heap
[b];
121
m_heap
[b] = tmp;
122
}
123
124
bool
125
HeapScheduler::IsLessStrictly
(uint32_t a, uint32_t b)
const
126
{
127
NS_LOG_FUNCTION
(
this
<< a << b);
128
return
m_heap
[a] <
m_heap
[b];
129
}
130
131
uint32_t
132
HeapScheduler::Smallest
(uint32_t a, uint32_t b)
const
133
{
134
NS_LOG_FUNCTION
(
this
<< a << b);
135
return
IsLessStrictly
(a,b) ? a : b;
136
}
137
138
bool
139
HeapScheduler::IsEmpty
(
void
)
const
140
{
141
NS_LOG_FUNCTION
(
this
);
142
return
(
m_heap
.size () == 1) ?
true
:
false
;
143
}
144
145
void
146
HeapScheduler::BottomUp
(
void
)
147
{
148
NS_LOG_FUNCTION
(
this
);
149
uint32_t index =
Last
();
150
while
(!
IsRoot
(index)
151
&&
IsLessStrictly
(index,
Parent
(index)))
152
{
153
Exch
(index,
Parent
(index));
154
index =
Parent
(index);
155
}
156
}
157
158
void
159
HeapScheduler::TopDown
(uint32_t
start
)
160
{
161
NS_LOG_FUNCTION
(
this
<< start);
162
uint32_t index =
start
;
163
uint32_t right =
RightChild
(index);
164
while
(!
IsBottom
(right))
165
{
166
uint32_t left =
LeftChild
(index);
167
uint32_t tmp =
Smallest
(left, right);
168
if
(
IsLessStrictly
(index, tmp))
169
{
170
return
;
171
}
172
Exch
(index, tmp);
173
index = tmp;
174
right =
RightChild
(index);
175
}
176
if
(
IsBottom
(index))
177
{
178
return
;
179
}
180
NS_ASSERT
(!
IsBottom
(index));
181
uint32_t left =
LeftChild
(index);
182
if
(
IsBottom
(left))
183
{
184
return
;
185
}
186
if
(
IsLessStrictly
(index, left))
187
{
188
return
;
189
}
190
Exch
(index, left);
191
}
192
193
194
void
195
HeapScheduler::Insert
(
const
Event &ev)
196
{
197
NS_LOG_FUNCTION
(
this
<< &ev);
198
m_heap
.push_back (ev);
199
BottomUp
();
200
}
201
202
Scheduler::Event
203
HeapScheduler::PeekNext
(
void
)
const
204
{
205
NS_LOG_FUNCTION
(
this
);
206
return
m_heap
[
Root
()];
207
}
208
Scheduler::Event
209
HeapScheduler::RemoveNext
(
void
)
210
{
211
NS_LOG_FUNCTION
(
this
);
212
Event next =
m_heap
[
Root
()];
213
Exch
(
Root
(),
Last
());
214
m_heap
.pop_back ();
215
TopDown
(
Root
());
216
return
next;
217
}
218
219
220
void
221
HeapScheduler::Remove
(
const
Event &ev)
222
{
223
NS_LOG_FUNCTION
(
this
<< &ev);
224
uint32_t uid = ev.key.m_uid;
225
for
(uint32_t i = 1; i <
m_heap
.size (); i++)
226
{
227
if
(uid ==
m_heap
[i].key.m_uid)
228
{
229
NS_ASSERT
(
m_heap
[i].impl == ev.impl);
230
Exch
(i,
Last
());
231
m_heap
.pop_back ();
232
TopDown
(i);
233
return
;
234
}
235
}
236
NS_ASSERT
(
false
);
237
}
238
239
}
// namespace ns3
240
NS_LOG_FUNCTION
#define NS_LOG_FUNCTION(parameters)
Definition:
log.h:311
ns3::HeapScheduler::Sibling
uint32_t Sibling(uint32_t id) const
Definition:
heap-scheduler.cc:66
ns3::HeapScheduler::~HeapScheduler
virtual ~HeapScheduler()
Definition:
heap-scheduler.cc:54
event-impl.h
heap-scheduler.h
ns3::HeapScheduler::Insert
virtual void Insert(const Event &ev)
Definition:
heap-scheduler.cc:195
ns3::HeapScheduler::TopDown
void TopDown(uint32_t start)
Definition:
heap-scheduler.cc:159
ns3::HeapScheduler::RemoveNext
virtual Event RemoveNext(void)
Definition:
heap-scheduler.cc:209
ns3::HeapScheduler::IsLessStrictly
bool IsLessStrictly(uint32_t a, uint32_t b) const
Definition:
heap-scheduler.cc:125
NS_ASSERT
#define NS_ASSERT(condition)
Definition:
assert.h:64
NS_LOG_COMPONENT_DEFINE
#define NS_LOG_COMPONENT_DEFINE(name)
Definition:
log.h:122
visualizer.core.start
def start
Definition:
core.py:1482
ns3::HeapScheduler::PeekNext
virtual Event PeekNext(void) const
Definition:
heap-scheduler.cc:203
ns3::HeapScheduler::GetTypeId
static TypeId GetTypeId(void)
Definition:
heap-scheduler.cc:35
ns3::HeapScheduler::IsRoot
bool IsRoot(uint32_t id) const
Definition:
heap-scheduler.cc:92
ns3::HeapScheduler::Remove
virtual void Remove(const Event &ev)
Definition:
heap-scheduler.cc:221
ns3::HeapScheduler::Exch
void Exch(uint32_t a, uint32_t b)
Definition:
heap-scheduler.cc:114
ns3::HeapScheduler::RightChild
uint32_t RightChild(uint32_t id) const
Definition:
heap-scheduler.cc:78
ns3::empty
make Callback use a separate empty type
Definition:
empty.h:8
assert.h
ns3::NS_OBJECT_ENSURE_REGISTERED
NS_OBJECT_ENSURE_REGISTERED(AntennaModel)
ns3::HeapScheduler::Smallest
uint32_t Smallest(uint32_t a, uint32_t b) const
Definition:
heap-scheduler.cc:132
ns3::Scheduler
Maintain the event list.
Definition:
scheduler.h:57
ns3::HeapScheduler::m_heap
BinaryHeap m_heap
Definition:
heap-scheduler.h:80
ns3::Scheduler::Event
Definition:
scheduler.h:70
ns3::HeapScheduler::HeapScheduler
HeapScheduler()
Definition:
heap-scheduler.cc:44
ns3::HeapScheduler::IsBottom
bool IsBottom(uint32_t id) const
Definition:
heap-scheduler.cc:107
NS_LOG_DEBUG
#define NS_LOG_DEBUG(msg)
Definition:
log.h:255
ns3::HeapScheduler::Last
uint32_t Last(void) const
Definition:
heap-scheduler.cc:99
ns3::HeapScheduler::BottomUp
void BottomUp(void)
Definition:
heap-scheduler.cc:146
ns3::HeapScheduler::IsEmpty
virtual bool IsEmpty(void) const
Definition:
heap-scheduler.cc:139
ns3::HeapScheduler::Parent
uint32_t Parent(uint32_t id) const
Definition:
heap-scheduler.cc:60
log.h
ns3::TypeId
a unique identifier for an interface.
Definition:
type-id.h:49
ns3::TypeId::SetParent
TypeId SetParent(TypeId tid)
Definition:
type-id.cc:610
ns3::HeapScheduler::Root
uint32_t Root(void) const
Definition:
heap-scheduler.cc:85
ns3::HeapScheduler::LeftChild
uint32_t LeftChild(uint32_t id) const
Definition:
heap-scheduler.cc:72
src
core
model
heap-scheduler.cc
Generated on Sat Nov 16 2013 12:55:23 for ns-3 by
1.8.5