A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
calendar-scheduler.cc
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  */
20 
21 #include "calendar-scheduler.h"
22 #include "event-impl.h"
23 #include <utility>
24 #include <string>
25 #include <list>
26 #include "assert.h"
27 #include "log.h"
28 
29 namespace ns3 {
30 
31 NS_LOG_COMPONENT_DEFINE ("CalendarScheduler");
32 
33 NS_OBJECT_ENSURE_REGISTERED (CalendarScheduler);
34 
35 TypeId
36 CalendarScheduler::GetTypeId (void)
37 {
38  static TypeId tid = TypeId ("ns3::CalendarScheduler")
39  .SetParent<Scheduler> ()
40  .AddConstructor<CalendarScheduler> ()
41  ;
42  return tid;
43 }
44 
45 CalendarScheduler::CalendarScheduler ()
46 {
47  NS_LOG_FUNCTION (this);
48  Init (2, 1, 0);
49  m_qSize = 0;
50 }
51 CalendarScheduler::~CalendarScheduler ()
52 {
53  NS_LOG_FUNCTION (this);
54  delete [] m_buckets;
55  m_buckets = 0;
56 }
57 void
58 CalendarScheduler::Init (uint32_t nBuckets,
59  uint64_t width,
60  uint64_t startPrio)
61 {
62  NS_LOG_FUNCTION (this << nBuckets << width << startPrio);
63  m_buckets = new Bucket [nBuckets];
64  m_nBuckets = nBuckets;
65  m_width = width;
66  m_lastPrio = startPrio;
67  m_lastBucket = Hash (startPrio);
68  m_bucketTop = (startPrio / width + 1) * width;
69 }
70 void
71 CalendarScheduler::PrintInfo (void)
72 {
73  NS_LOG_FUNCTION (this);
74 
75  std::cout << "nBuckets=" << m_nBuckets << ", width=" << m_width << std::endl;
76  std::cout << "Bucket Distribution ";
77  for (uint32_t i = 0; i < m_nBuckets; i++)
78  {
79  std::cout << m_buckets[i].size () << " ";
80  }
81  std::cout << std::endl;
82 }
83 uint32_t
84 CalendarScheduler::Hash (uint64_t ts) const
85 {
86  NS_LOG_FUNCTION (this);
87 
88  uint32_t bucket = (ts / m_width) % m_nBuckets;
89  return bucket;
90 }
91 
92 void
93 CalendarScheduler::DoInsert (const Event &ev)
94 {
95  NS_LOG_FUNCTION (this << ev.key.m_ts << ev.key.m_uid);
96  // calculate bucket index.
97  uint32_t bucket = Hash (ev.key.m_ts);
98  NS_LOG_LOGIC ("insert in bucket=" << bucket);
99 
100  // insert in bucket list.
101  Bucket::iterator end = m_buckets[bucket].end ();
102  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
103  {
104  if (ev.key < i->key)
105  {
106  m_buckets[bucket].insert (i, ev);
107  return;
108  }
109  }
110  m_buckets[bucket].push_back (ev);
111 }
112 
113 void
115 {
116  NS_LOG_FUNCTION (this << &ev);
117  DoInsert (ev);
118  m_qSize++;
119  ResizeUp ();
120 }
121 bool
123 {
124  NS_LOG_FUNCTION (this);
125  return m_qSize == 0;
126 }
129 {
130  NS_LOG_FUNCTION (this);
131  NS_ASSERT (!IsEmpty ());
132  uint32_t i = m_lastBucket;
133  uint64_t bucketTop = m_bucketTop;
134  Scheduler::Event minEvent = { static_cast<uint64_t>(0), { static_cast<uint32_t>(~0), static_cast<uint32_t>(~0)}};
135  do
136  {
137  if (!m_buckets[i].empty ())
138  {
139  Scheduler::Event next = m_buckets[i].front ();
140  if (next.key.m_ts < bucketTop)
141  {
142  return next;
143  }
144  if (next.key < minEvent.key)
145  {
146  minEvent = next;
147  }
148  }
149  i++;
150  i %= m_nBuckets;
151  bucketTop += m_width;
152  }
153  while (i != m_lastBucket);
154 
155  return minEvent;
156 }
157 
159 CalendarScheduler::DoRemoveNext (void)
160 {
161  NS_LOG_FUNCTION (this);
162 
163  uint32_t i = m_lastBucket;
164  uint64_t bucketTop = m_bucketTop;
165  int32_t minBucket = -1;
166  Scheduler::EventKey minKey;
167  NS_ASSERT(!IsEmpty());
168  minKey.m_ts = uint64_t(-int64_t(1));
169  minKey.m_uid = 0;
170  minKey.m_context = 0xffffffff;
171  do
172  {
173  if (!m_buckets[i].empty ())
174  {
175  Scheduler::Event next = m_buckets[i].front ();
176  if (next.key.m_ts < bucketTop)
177  {
178  m_lastBucket = i;
179  m_lastPrio = next.key.m_ts;
180  m_bucketTop = bucketTop;
181  m_buckets[i].pop_front ();
182  return next;
183  }
184  if (next.key < minKey)
185  {
186  minKey = next.key;
187  minBucket = i;
188  }
189  }
190  i++;
191  i %= m_nBuckets;
192  bucketTop += m_width;
193  }
194  while (i != m_lastBucket);
195 
196  m_lastPrio = minKey.m_ts;
197  m_lastBucket = Hash (minKey.m_ts);
198  m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;
199  Scheduler::Event next = m_buckets[minBucket].front();
200  m_buckets[minBucket].pop_front ();
201 
202  return next;
203 }
204 
205 Scheduler::Event
207 {
208  NS_LOG_FUNCTION (this << m_lastBucket << m_bucketTop);
209  NS_ASSERT (!IsEmpty ());
210 
211  Scheduler::Event ev = DoRemoveNext ();
212  NS_LOG_LOGIC ("remove ts=" << ev.key.m_ts <<
213  ", key=" << ev.key.m_uid <<
214  ", from bucket=" << m_lastBucket);
215  m_qSize--;
216  ResizeDown ();
217  return ev;
218 }
219 
220 void
222 {
223  NS_LOG_FUNCTION (this << &ev);
224  NS_ASSERT (!IsEmpty ());
225  // bucket index of event
226  uint32_t bucket = Hash (ev.key.m_ts);
227 
228  Bucket::iterator end = m_buckets[bucket].end ();
229  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
230  {
231  if (i->key.m_uid == ev.key.m_uid)
232  {
233  NS_ASSERT (ev.impl == i->impl);
234  m_buckets[bucket].erase (i);
235 
236  m_qSize--;
237  ResizeDown ();
238  return;
239  }
240  }
241  NS_ASSERT (false);
242 }
243 
244 void
245 CalendarScheduler::ResizeUp (void)
246 {
247  NS_LOG_FUNCTION (this);
248 
249  if (m_qSize > m_nBuckets * 2
250  && m_nBuckets < 32768)
251  {
252  Resize (m_nBuckets * 2);
253  }
254 }
255 void
256 CalendarScheduler::ResizeDown (void)
257 {
258  NS_LOG_FUNCTION (this);
259 
260  if (m_qSize < m_nBuckets / 2)
261  {
262  Resize (m_nBuckets / 2);
263  }
264 }
265 
266 uint32_t
267 CalendarScheduler::CalculateNewWidth (void)
268 {
269  NS_LOG_FUNCTION (this);
270 
271  if (m_qSize < 2)
272  {
273  return 1;
274  }
275  uint32_t nSamples;
276  if (m_qSize <= 5)
277  {
278  nSamples = m_qSize;
279  }
280  else
281  {
282  nSamples = 5 + m_qSize / 10;
283  }
284  if (nSamples > 25)
285  {
286  nSamples = 25;
287  }
288 
289  // we gather the first nSamples from the queue
290  std::list<Scheduler::Event> samples;
291  // save state
292  uint32_t lastBucket = m_lastBucket;
293  uint64_t bucketTop = m_bucketTop;
294  uint64_t lastPrio = m_lastPrio;
295 
296  // gather requested events
297  for (uint32_t i = 0; i < nSamples; i++)
298  {
299  samples.push_back (DoRemoveNext ());
300  }
301  // put them back
302  for (std::list<Scheduler::Event>::const_iterator i = samples.begin ();
303  i != samples.end (); ++i)
304  {
305  DoInsert (*i);
306  }
307 
308  // restore state.
309  m_lastBucket = lastBucket;
310  m_bucketTop = bucketTop;
311  m_lastPrio = lastPrio;
312 
313  // finally calculate inter-time average over samples.
314  uint64_t totalSeparation = 0;
315  std::list<Scheduler::Event>::const_iterator end = samples.end ();
316  std::list<Scheduler::Event>::const_iterator cur = samples.begin ();
317  std::list<Scheduler::Event>::const_iterator next = cur;
318  next++;
319  while (next != end)
320  {
321  totalSeparation += next->key.m_ts - cur->key.m_ts;
322  cur++;
323  next++;
324  }
325  uint64_t twiceAvg = totalSeparation / (nSamples - 1) * 2;
326  totalSeparation = 0;
327  cur = samples.begin ();
328  next = cur;
329  next++;
330  while (next != end)
331  {
332  uint64_t diff = next->key.m_ts - cur->key.m_ts;
333  if (diff <= twiceAvg)
334  {
335  totalSeparation += diff;
336  }
337  cur++;
338  next++;
339  }
340 
341  totalSeparation *= 3;
342  totalSeparation = std::max (totalSeparation, (uint64_t)1);
343  return totalSeparation;
344 }
345 void
346 CalendarScheduler::DoResize (uint32_t newSize, uint32_t newWidth)
347 {
348  NS_LOG_FUNCTION (this << newSize << newWidth);
349 
350  Bucket *oldBuckets = m_buckets;
351  uint32_t oldNBuckets = m_nBuckets;
352  Init (newSize, newWidth, m_lastPrio);
353 
354  for (uint32_t i = 0; i < oldNBuckets; i++)
355  {
356  Bucket::iterator end = oldBuckets[i].end ();
357  for (Bucket::iterator j = oldBuckets[i].begin (); j != end; ++j)
358  {
359  DoInsert (*j);
360  }
361  }
362  delete [] oldBuckets;
363 }
364 void
365 CalendarScheduler::Resize (uint32_t newSize)
366 {
367  NS_LOG_FUNCTION (this << newSize);
368 
369  // PrintInfo ();
370  uint32_t newWidth = CalculateNewWidth ();
371  DoResize (newSize, newWidth);
372 }
373 
374 } // namespace ns3
#define NS_LOG_FUNCTION(parameters)
Definition: log.h:311
#define NS_ASSERT(condition)
Definition: assert.h:64
#define NS_LOG_COMPONENT_DEFINE(name)
Definition: log.h:122
virtual Event PeekNext(void) const
virtual bool IsEmpty(void) const
make Callback use a separate empty type
Definition: empty.h:8
virtual void Remove(const Event &ev)
#define NS_LOG_LOGIC(msg)
Definition: log.h:334
virtual Event RemoveNext(void)
virtual void Insert(const Event &ev)