A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
calendar-scheduler.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2009 INRIA
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
7 * Author: Alexander Krotov <krotov@iitp.ru>
8 */
9
10#include "calendar-scheduler.h"
11
12#include "assert.h"
13#include "boolean.h"
14#include "event-impl.h"
15#include "log.h"
16#include "type-id.h"
17
18#include <list>
19#include <string>
20#include <utility>
21
22/**
23 * \file
24 * \ingroup scheduler
25 * ns3::CalendarScheduler class implementation.
26 */
27
28namespace ns3
29{
30
31NS_LOG_COMPONENT_DEFINE("CalendarScheduler");
32
33NS_OBJECT_ENSURE_REGISTERED(CalendarScheduler);
34
35TypeId
37{
38 static TypeId tid = TypeId("ns3::CalendarScheduler")
40 .SetGroupName("Core")
41 .AddConstructor<CalendarScheduler>()
42 .AddAttribute("Reverse",
43 "Store events in reverse chronological order",
45 BooleanValue(false),
48 return tid;
49}
50
52{
53 NS_LOG_FUNCTION(this);
54 Init(2, 1, 0);
55 m_qSize = 0;
56}
57
59{
60 NS_LOG_FUNCTION(this);
61 delete[] m_buckets;
62 m_buckets = nullptr;
63}
64
65void
67{
68 NS_LOG_FUNCTION(this << reverse);
69 m_reverse = reverse;
70
71 if (m_reverse)
72 {
73 NextEvent = [](Bucket& bucket) -> Scheduler::Event& { return bucket.back(); };
74 Order = [](const EventKey& a, const EventKey& b) -> bool { return a > b; };
75 Pop = [](Bucket& bucket) -> void { bucket.pop_back(); };
76 }
77 else
78 {
79 NextEvent = [](Bucket& bucket) -> Scheduler::Event& { return bucket.front(); };
80 Order = [](const EventKey& a, const EventKey& b) -> bool { return a < b; };
81 Pop = [](Bucket& bucket) -> void { bucket.pop_front(); };
82 }
83}
84
85void
86CalendarScheduler::Init(uint32_t nBuckets, uint64_t width, uint64_t startPrio)
87{
88 NS_LOG_FUNCTION(this << nBuckets << width << startPrio);
89 m_buckets = new Bucket[nBuckets];
90 m_nBuckets = nBuckets;
91 m_width = width;
92 m_lastPrio = startPrio;
93 m_lastBucket = Hash(startPrio);
94 m_bucketTop = (startPrio / width + 1) * width;
95}
96
97void
99{
100 NS_LOG_FUNCTION(this);
101
102 std::cout << "nBuckets=" << m_nBuckets << ", width=" << m_width << std::endl;
103 std::cout << "Bucket Distribution ";
104 for (uint32_t i = 0; i < m_nBuckets; i++)
105 {
106 std::cout << m_buckets[i].size() << " ";
107 }
108 std::cout << std::endl;
109}
110
112CalendarScheduler::Hash(uint64_t ts) const
113{
114 NS_LOG_FUNCTION(this);
115
116 uint32_t bucket = (ts / m_width) % m_nBuckets;
117 return bucket;
118}
119
120void
122{
123 NS_LOG_FUNCTION(this << ev.key.m_ts << ev.key.m_uid);
124 // calculate bucket index.
125 uint32_t bucket = Hash(ev.key.m_ts);
126 NS_LOG_LOGIC("insert in bucket=" << bucket);
127
128 // insert in bucket list.
129 auto end = m_buckets[bucket].end();
130 for (auto i = m_buckets[bucket].begin(); i != end; ++i)
131 {
132 if (Order(ev.key, i->key))
133 {
134 m_buckets[bucket].insert(i, ev);
135 return;
136 }
137 }
138 m_buckets[bucket].push_back(ev);
139}
140
141void
143{
144 NS_LOG_FUNCTION(this << &ev);
145 DoInsert(ev);
146 m_qSize++;
147 ResizeUp();
148}
149
150bool
152{
153 NS_LOG_FUNCTION(this);
154 return m_qSize == 0;
155}
156
159{
160 NS_LOG_FUNCTION(this);
161 NS_ASSERT(!IsEmpty());
163 uint64_t bucketTop = m_bucketTop;
164 Scheduler::Event minEvent;
165 minEvent.impl = nullptr;
166 minEvent.key.m_ts = UINT64_MAX;
167 minEvent.key.m_uid = UINT32_MAX;
168 minEvent.key.m_context = 0;
169 do
170 {
171 if (!m_buckets[i].empty())
172 {
174 if (next.key.m_ts < bucketTop)
175 {
176 return next;
177 }
178 if (next.key < minEvent.key)
179 {
180 minEvent = next;
181 }
182 }
183 i++;
184 i %= m_nBuckets;
185 bucketTop += m_width;
186 } while (i != m_lastBucket);
187
188 return minEvent;
189}
190
193{
194 NS_LOG_FUNCTION(this);
195
197 uint64_t bucketTop = m_bucketTop;
198 int32_t minBucket = -1;
199 Scheduler::EventKey minKey;
200 NS_ASSERT(!IsEmpty());
201 minKey.m_ts = uint64_t(-int64_t(1));
202 minKey.m_uid = 0;
203 minKey.m_context = 0xffffffff;
204 do
205 {
206 if (!m_buckets[i].empty())
207 {
209 if (next.key.m_ts < bucketTop)
210 {
211 m_lastBucket = i;
212 m_lastPrio = next.key.m_ts;
213 m_bucketTop = bucketTop;
214 Pop(m_buckets[i]);
215 return next;
216 }
217 if (next.key < minKey)
218 {
219 minKey = next.key;
220 minBucket = i;
221 }
222 }
223 i++;
224 i %= m_nBuckets;
225 bucketTop += m_width;
226 } while (i != m_lastBucket);
227
228 m_lastPrio = minKey.m_ts;
229 m_lastBucket = Hash(minKey.m_ts);
230 m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;
231 Scheduler::Event next = NextEvent(m_buckets[minBucket]);
232 Pop(m_buckets[minBucket]);
233
234 return next;
235}
236
239{
241 NS_ASSERT(!IsEmpty());
242
244 NS_LOG_LOGIC("remove ts=" << ev.key.m_ts << ", key=" << ev.key.m_uid
245 << ", from bucket=" << m_lastBucket);
246 m_qSize--;
247 ResizeDown();
248 return ev;
249}
250
251void
253{
254 NS_LOG_FUNCTION(this << &ev);
255 NS_ASSERT(!IsEmpty());
256 // bucket index of event
257 uint32_t bucket = Hash(ev.key.m_ts);
258
259 auto end = m_buckets[bucket].end();
260 for (auto i = m_buckets[bucket].begin(); i != end; ++i)
261 {
262 if (i->key.m_uid == ev.key.m_uid)
263 {
264 NS_ASSERT(ev.impl == i->impl);
265 m_buckets[bucket].erase(i);
266
267 m_qSize--;
268 ResizeDown();
269 return;
270 }
271 }
272 NS_ASSERT(false);
273}
274
275void
277{
278 NS_LOG_FUNCTION(this);
279
280 if (m_qSize > m_nBuckets * 2 && m_nBuckets < 32768)
281 {
282 Resize(m_nBuckets * 2);
283 }
284}
285
286void
288{
289 NS_LOG_FUNCTION(this);
290
291 if (m_qSize < m_nBuckets / 2)
292 {
293 Resize(m_nBuckets / 2);
294 }
295}
296
297uint64_t
299{
300 NS_LOG_FUNCTION(this);
301
302 if (m_qSize < 2)
303 {
304 return 1;
305 }
306 uint32_t nSamples;
307 if (m_qSize <= 5)
308 {
309 nSamples = m_qSize;
310 }
311 else
312 {
313 nSamples = 5 + m_qSize / 10;
314 }
315 if (nSamples > 25)
316 {
317 nSamples = 25;
318 }
319
320 // we gather the first nSamples from the queue
321 std::list<Scheduler::Event> samples;
322 // save state
323 uint32_t lastBucket = m_lastBucket;
324 uint64_t bucketTop = m_bucketTop;
325 uint64_t lastPrio = m_lastPrio;
326
327 // gather requested events
328 for (uint32_t i = 0; i < nSamples; i++)
329 {
330 samples.push_back(DoRemoveNext());
331 }
332 // put them back
333 for (auto i = samples.begin(); i != samples.end(); ++i)
334 {
335 DoInsert(*i);
336 }
337
338 // restore state.
339 m_lastBucket = lastBucket;
340 m_bucketTop = bucketTop;
341 m_lastPrio = lastPrio;
342
343 // finally calculate inter-time average over samples.
344 uint64_t totalSeparation = 0;
345 auto end = samples.end();
346 auto cur = samples.begin();
347 auto next = cur;
348 next++;
349 while (next != end)
350 {
351 totalSeparation += next->key.m_ts - cur->key.m_ts;
352 cur++;
353 next++;
354 }
355 uint64_t twiceAvg = totalSeparation / (nSamples - 1) * 2;
356 totalSeparation = 0;
357 cur = samples.begin();
358 next = cur;
359 next++;
360 while (next != end)
361 {
362 uint64_t diff = next->key.m_ts - cur->key.m_ts;
363 if (diff <= twiceAvg)
364 {
365 totalSeparation += diff;
366 }
367 cur++;
368 next++;
369 }
370
371 totalSeparation *= 3;
372 totalSeparation = std::max(totalSeparation, (uint64_t)1);
373 return totalSeparation;
374}
375
376void
377CalendarScheduler::DoResize(uint32_t newSize, uint64_t newWidth)
378{
379 NS_LOG_FUNCTION(this << newSize << newWidth);
380
381 Bucket* oldBuckets = m_buckets;
382 uint32_t oldNBuckets = m_nBuckets;
383 Init(newSize, newWidth, m_lastPrio);
384
385 for (uint32_t i = 0; i < oldNBuckets; i++)
386 {
387 auto end = oldBuckets[i].end();
388 for (auto j = oldBuckets[i].begin(); j != end; ++j)
389 {
390 DoInsert(*j);
391 }
392 }
393 delete[] oldBuckets;
394}
395
396void
398{
399 NS_LOG_FUNCTION(this << newSize);
400
401 // PrintInfo ();
402 uint64_t newWidth = CalculateNewWidth();
403 DoResize(newSize, newWidth);
404}
405
406} // namespace ns3
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
ns3::BooleanValue attribute value declarations.
ns3::CalendarScheduler class declaration.
a calendar queue event scheduler
bool m_reverse
Bucket ordering.
uint64_t CalculateNewWidth()
Compute the new bucket size, based on up to the first 25 entries.
uint32_t m_nBuckets
Number of buckets in the array.
bool(* Order)(const EventKey &newEvent, const EventKey &it)
Ordering function to identify the insertion point, according to m_reverse.
void PrintInfo()
Print the configuration and bucket size distribution.
uint32_t m_qSize
Number of events in queue.
Scheduler::Event &(* NextEvent)(Bucket &bucket)
Get the next event from the bucket, according to m_reverse.
void Remove(const Scheduler::Event &ev) override
Remove a specific event from the event list.
void Init(uint32_t nBuckets, uint64_t width, uint64_t startPrio)
Initialize the calendar queue.
void ResizeDown()
Halve the number of buckets if necessary.
uint32_t Hash(uint64_t key) const
Hash the dimensionless time to a bucket.
void Insert(const Scheduler::Event &ev) override
Insert a new Event in the schedule.
void DoInsert(const Scheduler::Event &ev)
Insert a new event in to the correct bucket.
uint64_t m_bucketTop
Priority at the top of the bucket from which last event was dequeued.
std::list< Scheduler::Event > Bucket
Calendar bucket type: a list of Events.
~CalendarScheduler() override
Destructor.
void DoResize(uint32_t newSize, uint64_t newWidth)
Resize the number of buckets and width.
Scheduler::Event PeekNext() const override
Get a pointer to the next event.
Scheduler::Event RemoveNext() override
Remove the earliest event from the event list.
Scheduler::Event DoRemoveNext()
Remove the earliest event.
uint32_t m_lastBucket
Bucket index from which the last event was dequeued.
void SetReverse(bool reverse)
Set the insertion order.
void Resize(uint32_t newSize)
Resize to a new number of buckets, with automatically computed width.
bool IsEmpty() const override
Test if the schedule is empty.
uint64_t m_lastPrio
The priority of the last event removed.
uint64_t m_width
Duration of a bucket, in dimensionless time units.
void ResizeUp()
Double the number of buckets if necessary.
Bucket * m_buckets
Array of buckets.
void(* Pop)(Bucket &)
Pop the next event from the bucket, according to m_reverse.
static TypeId GetTypeId()
Register this type.
Maintain the event list.
Definition scheduler.h:146
a unique identifier for an interface.
Definition type-id.h:48
@ ATTR_CONSTRUCT
The attribute can be written at construction-time.
Definition type-id.h:55
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_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition log.h:271
#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
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< const AttributeChecker > MakeBooleanChecker()
Definition boolean.cc:113
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Definition boolean.h:70
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
Structure for sorting and comparing Events.
Definition scheduler.h:159
uint32_t m_context
Event context.
Definition scheduler.h:162
uint64_t m_ts
Event time stamp.
Definition scheduler.h:160
uint32_t m_uid
Event unique id.
Definition scheduler.h:161
ns3::TypeId declaration; inline and template implementations.