21 #include "calendar-scheduler.h"
22 #include "event-impl.h"
33 NS_OBJECT_ENSURE_REGISTERED (CalendarScheduler);
36 CalendarScheduler::GetTypeId (
void)
38 static TypeId tid = TypeId (
"ns3::CalendarScheduler")
39 .SetParent<Scheduler> ()
40 .AddConstructor<CalendarScheduler> ()
45 CalendarScheduler::CalendarScheduler ()
51 CalendarScheduler::~CalendarScheduler ()
58 CalendarScheduler::Init (uint32_t nBuckets,
63 m_buckets =
new Bucket [nBuckets];
64 m_nBuckets = nBuckets;
66 m_lastPrio = startPrio;
67 m_lastBucket = Hash (startPrio);
68 m_bucketTop = (startPrio / width + 1) * width;
71 CalendarScheduler::PrintInfo (
void)
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++)
79 std::cout << m_buckets[i].size () <<
" ";
81 std::cout << std::endl;
84 CalendarScheduler::Hash (uint64_t ts)
const
88 uint32_t bucket = (ts / m_width) % m_nBuckets;
93 CalendarScheduler::DoInsert (
const Event &ev)
97 uint32_t bucket = Hash (ev.key.m_ts);
101 Bucket::iterator end = m_buckets[bucket].end ();
102 for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
106 m_buckets[bucket].insert (i, ev);
110 m_buckets[bucket].push_back (ev);
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)}};
137 if (!m_buckets[i].
empty ())
140 if (next.key.m_ts < bucketTop)
144 if (next.key < minEvent.key)
151 bucketTop += m_width;
153 while (i != m_lastBucket);
159 CalendarScheduler::DoRemoveNext (
void)
163 uint32_t i = m_lastBucket;
164 uint64_t bucketTop = m_bucketTop;
165 int32_t minBucket = -1;
168 minKey.m_ts = uint64_t(-int64_t(1));
170 minKey.m_context = 0xffffffff;
173 if (!m_buckets[i].
empty ())
176 if (next.key.m_ts < bucketTop)
179 m_lastPrio = next.key.m_ts;
180 m_bucketTop = bucketTop;
181 m_buckets[i].pop_front ();
184 if (next.key < minKey)
192 bucketTop += m_width;
194 while (i != m_lastBucket);
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 ();
213 ", key=" << ev.key.m_uid <<
214 ", from bucket=" << m_lastBucket);
226 uint32_t bucket = Hash (ev.key.m_ts);
228 Bucket::iterator end = m_buckets[bucket].end ();
229 for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
231 if (i->key.m_uid == ev.key.m_uid)
234 m_buckets[bucket].erase (i);
245 CalendarScheduler::ResizeUp (
void)
249 if (m_qSize > m_nBuckets * 2
250 && m_nBuckets < 32768)
252 Resize (m_nBuckets * 2);
256 CalendarScheduler::ResizeDown (
void)
260 if (m_qSize < m_nBuckets / 2)
262 Resize (m_nBuckets / 2);
267 CalendarScheduler::CalculateNewWidth (
void)
282 nSamples = 5 + m_qSize / 10;
290 std::list<Scheduler::Event> samples;
292 uint32_t lastBucket = m_lastBucket;
293 uint64_t bucketTop = m_bucketTop;
294 uint64_t lastPrio = m_lastPrio;
297 for (uint32_t i = 0; i < nSamples; i++)
299 samples.push_back (DoRemoveNext ());
302 for (std::list<Scheduler::Event>::const_iterator i = samples.begin ();
303 i != samples.end (); ++i)
309 m_lastBucket = lastBucket;
310 m_bucketTop = bucketTop;
311 m_lastPrio = lastPrio;
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;
321 totalSeparation += next->key.m_ts - cur->key.m_ts;
325 uint64_t twiceAvg = totalSeparation / (nSamples - 1) * 2;
327 cur = samples.begin ();
332 uint64_t diff = next->key.m_ts - cur->key.m_ts;
333 if (diff <= twiceAvg)
335 totalSeparation += diff;
341 totalSeparation *= 3;
342 totalSeparation = std::max (totalSeparation, (uint64_t)1);
343 return totalSeparation;
346 CalendarScheduler::DoResize (uint32_t newSize, uint32_t newWidth)
350 Bucket *oldBuckets = m_buckets;
351 uint32_t oldNBuckets = m_nBuckets;
352 Init (newSize, newWidth, m_lastPrio);
354 for (uint32_t i = 0; i < oldNBuckets; i++)
356 Bucket::iterator end = oldBuckets[i].end ();
357 for (Bucket::iterator j = oldBuckets[i].begin (); j != end; ++j)
362 delete [] oldBuckets;
365 CalendarScheduler::Resize (uint32_t newSize)
370 uint32_t newWidth = CalculateNewWidth ();
371 DoResize (newSize, newWidth);
#define NS_LOG_FUNCTION(parameters)
#define NS_ASSERT(condition)
#define NS_LOG_COMPONENT_DEFINE(name)
virtual Event PeekNext(void) const
virtual bool IsEmpty(void) const
make Callback use a separate empty type
virtual void Remove(const Event &ev)
#define NS_LOG_LOGIC(msg)
virtual Event RemoveNext(void)
virtual void Insert(const Event &ev)