A Discrete-Event Network Simulator
API
calendar-scheduler.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2009 INRIA
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
19  * Author: Alexander Krotov <krotov@iitp.ru>
20  */
21 
22 #include "calendar-scheduler.h"
23 #include "event-impl.h"
24 #include "type-id.h"
25 #include "boolean.h"
26 #include <utility>
27 #include <string>
28 #include <list>
29 #include "assert.h"
30 #include "log.h"
31 
38 namespace ns3 {
39 
40 NS_LOG_COMPONENT_DEFINE ("CalendarScheduler");
41 
42 NS_OBJECT_ENSURE_REGISTERED (CalendarScheduler);
43 
44 TypeId
46 {
47  static TypeId tid = TypeId ("ns3::CalendarScheduler")
48  .SetParent<Scheduler> ()
49  .SetGroupName ("Core")
50  .AddConstructor<CalendarScheduler> ()
51  .AddAttribute ("Reverse",
52  "Store events in reverse chronological order",
54  BooleanValue (false),
57  ;
58  return tid;
59 }
60 
62 {
63  NS_LOG_FUNCTION (this);
64  Init (2, 1, 0);
65  m_qSize = 0;
66 }
68 {
69  NS_LOG_FUNCTION (this);
70  delete [] m_buckets;
71  m_buckets = 0;
72 }
73 void
75 {
76  NS_LOG_FUNCTION (this << reverse);
77  m_reverse = reverse;
78 
79  if (m_reverse)
80  {
81  NextEvent = [] (Bucket & bucket) -> Scheduler::Event &
82  {
83  return bucket.back ();
84  };
85  Order = [](const EventKey & a, const EventKey & b) -> bool
86  {
87  return a > b;
88  };
89  Pop = [] (Bucket & bucket) -> void
90  {
91  bucket.pop_back ();
92  };
93  }
94  else
95  {
96  NextEvent = [](Bucket & bucket) -> Scheduler::Event &
97  {
98  return bucket.front ();
99  };
100  Order = [](const EventKey & a, const EventKey & b) -> bool
101  {
102  return a < b;
103  };
104  Pop = [] (Bucket & bucket) -> void
105  {
106  bucket.pop_front ();
107  };
108  }
109 }
110 void
111 CalendarScheduler::Init (uint32_t nBuckets,
112  uint64_t width,
113  uint64_t startPrio)
114 {
115  NS_LOG_FUNCTION (this << nBuckets << width << startPrio);
116  m_buckets = new Bucket [nBuckets];
117  m_nBuckets = nBuckets;
118  m_width = width;
119  m_lastPrio = startPrio;
120  m_lastBucket = Hash (startPrio);
121  m_bucketTop = (startPrio / width + 1) * width;
122 }
123 void
125 {
126  NS_LOG_FUNCTION (this);
127 
128  std::cout << "nBuckets=" << m_nBuckets << ", width=" << m_width << std::endl;
129  std::cout << "Bucket Distribution ";
130  for (uint32_t i = 0; i < m_nBuckets; i++)
131  {
132  std::cout << m_buckets[i].size () << " ";
133  }
134  std::cout << std::endl;
135 }
136 uint32_t
137 CalendarScheduler::Hash (uint64_t ts) const
138 {
139  NS_LOG_FUNCTION (this);
140 
141  uint32_t bucket = (ts / m_width) % m_nBuckets;
142  return bucket;
143 }
144 
145 void
147 {
148  NS_LOG_FUNCTION (this << ev.key.m_ts << ev.key.m_uid);
149  // calculate bucket index.
150  uint32_t bucket = Hash (ev.key.m_ts);
151  NS_LOG_LOGIC ("insert in bucket=" << bucket);
152 
153  // insert in bucket list.
154  Bucket::iterator end = m_buckets[bucket].end ();
155  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
156  {
157  if (Order (ev.key, i->key) )
158  {
159  m_buckets[bucket].insert (i, ev);
160  return;
161  }
162  }
163  m_buckets[bucket].push_back (ev);
164 }
165 
166 void
168 {
169  NS_LOG_FUNCTION (this << &ev);
170  DoInsert (ev);
171  m_qSize++;
172  ResizeUp ();
173 }
174 bool
176 {
177  NS_LOG_FUNCTION (this);
178  return m_qSize == 0;
179 }
182 {
183  NS_LOG_FUNCTION (this);
184  NS_ASSERT (!IsEmpty ());
185  uint32_t i = m_lastBucket;
186  uint64_t bucketTop = m_bucketTop;
187  Scheduler::Event minEvent;
188  minEvent.impl = 0;
189  minEvent.key.m_ts = UINT64_MAX;
190  minEvent.key.m_uid = UINT32_MAX;
191  minEvent.key.m_context = 0;
192  do
193  {
194  if (!m_buckets[i].empty ())
195  {
197  if (next.key.m_ts < bucketTop)
198  {
199  return next;
200  }
201  if (next.key < minEvent.key)
202  {
203  minEvent = next;
204  }
205  }
206  i++;
207  i %= m_nBuckets;
208  bucketTop += m_width;
209  }
210  while (i != m_lastBucket);
211 
212  return minEvent;
213 }
214 
217 {
218  NS_LOG_FUNCTION (this);
219 
220  uint32_t i = m_lastBucket;
221  uint64_t bucketTop = m_bucketTop;
222  int32_t minBucket = -1;
223  Scheduler::EventKey minKey;
224  NS_ASSERT (!IsEmpty ());
225  minKey.m_ts = uint64_t (-int64_t (1));
226  minKey.m_uid = 0;
227  minKey.m_context = 0xffffffff;
228  do
229  {
230  if (!m_buckets[i].empty ())
231  {
233  if (next.key.m_ts < bucketTop)
234  {
235  m_lastBucket = i;
236  m_lastPrio = next.key.m_ts;
237  m_bucketTop = bucketTop;
238  Pop (m_buckets[i]);
239  return next;
240  }
241  if (next.key < minKey)
242  {
243  minKey = next.key;
244  minBucket = i;
245  }
246  }
247  i++;
248  i %= m_nBuckets;
249  bucketTop += m_width;
250  }
251  while (i != m_lastBucket);
252 
253  m_lastPrio = minKey.m_ts;
254  m_lastBucket = Hash (minKey.m_ts);
255  m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;
256  Scheduler::Event next = NextEvent (m_buckets[minBucket]);
257  Pop (m_buckets[minBucket]);
258 
259  return next;
260 }
261 
264 {
266  NS_ASSERT (!IsEmpty ());
267 
269  NS_LOG_LOGIC ("remove ts=" << ev.key.m_ts <<
270  ", key=" << ev.key.m_uid <<
271  ", from bucket=" << m_lastBucket);
272  m_qSize--;
273  ResizeDown ();
274  return ev;
275 }
276 
277 void
279 {
280  NS_LOG_FUNCTION (this << &ev);
281  NS_ASSERT (!IsEmpty ());
282  // bucket index of event
283  uint32_t bucket = Hash (ev.key.m_ts);
284 
285  Bucket::iterator end = m_buckets[bucket].end ();
286  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
287  {
288  if (i->key.m_uid == ev.key.m_uid)
289  {
290  NS_ASSERT (ev.impl == i->impl);
291  m_buckets[bucket].erase (i);
292 
293  m_qSize--;
294  ResizeDown ();
295  return;
296  }
297  }
298  NS_ASSERT (false);
299 }
300 
301 void
303 {
304  NS_LOG_FUNCTION (this);
305 
306  if (m_qSize > m_nBuckets * 2
307  && m_nBuckets < 32768)
308  {
309  Resize (m_nBuckets * 2);
310  }
311 }
312 void
314 {
315  NS_LOG_FUNCTION (this);
316 
317  if (m_qSize < m_nBuckets / 2)
318  {
319  Resize (m_nBuckets / 2);
320  }
321 }
322 
323 uint64_t
325 {
326  NS_LOG_FUNCTION (this);
327 
328  if (m_qSize < 2)
329  {
330  return 1;
331  }
332  uint32_t nSamples;
333  if (m_qSize <= 5)
334  {
335  nSamples = m_qSize;
336  }
337  else
338  {
339  nSamples = 5 + m_qSize / 10;
340  }
341  if (nSamples > 25)
342  {
343  nSamples = 25;
344  }
345 
346  // we gather the first nSamples from the queue
347  std::list<Scheduler::Event> samples;
348  // save state
349  uint32_t lastBucket = m_lastBucket;
350  uint64_t bucketTop = m_bucketTop;
351  uint64_t lastPrio = m_lastPrio;
352 
353  // gather requested events
354  for (uint32_t i = 0; i < nSamples; i++)
355  {
356  samples.push_back (DoRemoveNext ());
357  }
358  // put them back
359  for (std::list<Scheduler::Event>::const_iterator i = samples.begin ();
360  i != samples.end (); ++i)
361  {
362  DoInsert (*i);
363  }
364 
365  // restore state.
366  m_lastBucket = lastBucket;
367  m_bucketTop = bucketTop;
368  m_lastPrio = lastPrio;
369 
370  // finally calculate inter-time average over samples.
371  uint64_t totalSeparation = 0;
372  std::list<Scheduler::Event>::const_iterator end = samples.end ();
373  std::list<Scheduler::Event>::const_iterator cur = samples.begin ();
374  std::list<Scheduler::Event>::const_iterator next = cur;
375  next++;
376  while (next != end)
377  {
378  totalSeparation += next->key.m_ts - cur->key.m_ts;
379  cur++;
380  next++;
381  }
382  uint64_t twiceAvg = totalSeparation / (nSamples - 1) * 2;
383  totalSeparation = 0;
384  cur = samples.begin ();
385  next = cur;
386  next++;
387  while (next != end)
388  {
389  uint64_t diff = next->key.m_ts - cur->key.m_ts;
390  if (diff <= twiceAvg)
391  {
392  totalSeparation += diff;
393  }
394  cur++;
395  next++;
396  }
397 
398  totalSeparation *= 3;
399  totalSeparation = std::max (totalSeparation, (uint64_t)1);
400  return totalSeparation;
401 }
402 void
403 CalendarScheduler::DoResize (uint32_t newSize, uint64_t newWidth)
404 {
405  NS_LOG_FUNCTION (this << newSize << newWidth);
406 
407  Bucket *oldBuckets = m_buckets;
408  uint32_t oldNBuckets = m_nBuckets;
409  Init (newSize, newWidth, m_lastPrio);
410 
411  for (uint32_t i = 0; i < oldNBuckets; i++)
412  {
413  Bucket::iterator end = oldBuckets[i].end ();
414  for (Bucket::iterator j = oldBuckets[i].begin (); j != end; ++j)
415  {
416  DoInsert (*j);
417  }
418  }
419  delete [] oldBuckets;
420 }
421 void
422 CalendarScheduler::Resize (uint32_t newSize)
423 {
424  NS_LOG_FUNCTION (this << newSize);
425 
426  // PrintInfo ();
427  uint64_t newWidth = CalculateNewWidth ();
428  DoResize (newSize, newWidth);
429 }
430 
431 } // namespace ns3
#define max(a, b)
Definition: 80211b.c:43
NS_ASSERT() and NS_ASSERT_MSG() macro definitions.
ns3::BooleanValue attribute value declarations.
ns3::CalendarScheduler class declaration.
AttributeValue implementation for Boolean.
Definition: boolean.h:37
a calendar queue event scheduler
bool m_reverse
Bucket ordering.
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.
uint32_t m_qSize
Number of events in queue.
uint64_t CalculateNewWidth(void)
Compute the new bucket size, based on up to the first 25 entries.
virtual bool IsEmpty(void) const
Test if the schedule is empty.
void Init(uint32_t nBuckets, uint64_t width, uint64_t startPrio)
Initialize the calendar queue.
Scheduler::Event DoRemoveNext(void)
Remove the earliest event.
uint32_t Hash(uint64_t key) const
Hash the dimensionless time to a bucket.
void ResizeUp(void)
Double the number of buckets if necessary.
virtual Scheduler::Event PeekNext(void) const
Get a pointer to the next event.
Scheduler::Event &(* NextEvent)(Bucket &bucket)
Get the next event from the bucket, according to m_reverse.
static TypeId GetTypeId(void)
Register this type.
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.
void DoResize(uint32_t newSize, uint64_t newWidth)
Resize the number of buckets and width.
uint32_t m_lastBucket
Bucket index from which the last event was dequeued.
virtual void Insert(const Scheduler::Event &ev)
Insert a new Event in the schedule.
void SetReverse(bool reverse)
Set the insertion order.
virtual ~CalendarScheduler()
Destructor.
void Resize(uint32_t newSize)
Resize to a new number of buckets, with automatically computed width.
uint64_t m_lastPrio
The priority of the last event removed.
uint64_t m_width
Duration of a bucket, in dimensionless time units.
Bucket * m_buckets
Array of buckets.
void ResizeDown(void)
Halve the number of buckets if necessary.
virtual Scheduler::Event RemoveNext(void)
Remove the earliest event from the event list.
virtual void Remove(const Scheduler::Event &ev)
Remove a specific event from the event list.
void(* Pop)(Bucket &)
Pop the next event from the bucket, according to m_reverse.
void PrintInfo(void)
Print the configuration and bucket size distribution.
Maintain the event list.
Definition: scheduler.h:156
a unique identifier for an interface.
Definition: type-id.h:59
@ ATTR_CONSTRUCT
The attribute can be written at construction-time.
Definition: type-id.h:66
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
Ptr< const AttributeChecker > MakeBooleanChecker(void)
Definition: boolean.cc:121
Ptr< const AttributeAccessor > MakeBooleanAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition: boolean.h:85
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
#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
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
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
Structure for sorting and comparing Events.
Definition: scheduler.h:169
uint32_t m_context
Event context.
Definition: scheduler.h:172
uint64_t m_ts
Event time stamp.
Definition: scheduler.h:170
uint32_t m_uid
Event unique id.
Definition: scheduler.h:171
ns3::TypeId declaration; inline and template implementations.