simplify the implementation
authorMathieu Lacage <mathieu.lacage@sophia.inria.fr>
Fri, 09 Jan 2009 07:51:17 +0100
changeset 4052 62bed1686d48
parent 4051 3df44c5a1ec1
child 4053 f983d157bbff
simplify the implementation
src/simulator/calendar-scheduler.cc
src/simulator/calendar-scheduler.h
--- a/src/simulator/calendar-scheduler.cc	Thu Jan 08 16:23:33 2009 +0100
+++ b/src/simulator/calendar-scheduler.cc	Fri Jan 09 07:51:17 2009 +0100
@@ -30,65 +30,24 @@
 
 NS_LOG_COMPONENT_DEFINE ("CalendarScheduler");
 
-class Calendar 
+CalendarScheduler::CalendarScheduler ()
 {
-public:
-  Calendar ();
-  ~Calendar ();
-
-  Calendar *CreateResized (uint32_t nBuckets, 
-                           uint64_t newWidth) const;
-
-  void InsertAll (const Calendar *calendar);
-  void Insert (const Scheduler::Event &ev);
-  Scheduler::Event PeekNext (void) const;
-  Scheduler::Event RemoveNext (void);
-  void Remove (const Scheduler::Event &ev);
-  uint32_t GetNBuckets (void) const;
-  std::list<Scheduler::Event> PeekNext (uint32_t n) const;
-
-  void PrintBucketDistribution (void);
-
-private:
-  Calendar &operator = (const Calendar &o);
-  Calendar (const Calendar &o);
-  Calendar (uint32_t nBuckets, 
-            uint64_t width,
-            uint64_t startPrio);
-  void Init (uint32_t nBuckets, 
-             uint64_t width,
-             uint64_t startPrio);
-  inline uint32_t Hash (uint64_t key) const;
-
-  typedef std::list<Scheduler::Event> Bucket;
-  Bucket *m_buckets;
-  uint32_t m_nBuckets;
-  // duration of a bucket
-  uint64_t m_width;
-  // bucket index from which the last event was dequeued
-  uint32_t m_lastBucket;
-  // priority at the top of the bucket from which last event was dequeued
-  uint64_t m_bucketTop;
-  // the priority of the last event removed.
-  uint64_t m_lastPrio;
-};
-
-Calendar::Calendar ()
+  NS_LOG_FUNCTION (this);
+  Init (2, 1, 0);
+  m_qSize = 0;
+}
+CalendarScheduler::~CalendarScheduler ()
 {
-  Init (2, 1, 0);
-}
-Calendar::Calendar (uint32_t nBuckets, 
-                    uint64_t width,
-                    uint64_t startPrio)
-{
-  NS_ASSERT (width > 0);
-  Init (nBuckets, width, startPrio);
+  NS_LOG_FUNCTION (this);
+  delete [] m_buckets;
+  m_buckets = 0;
 }
 void
-Calendar::Init (uint32_t nBuckets, 
-                uint64_t width,
-                uint64_t startPrio)
+CalendarScheduler::Init (uint32_t nBuckets, 
+                         uint64_t width,
+                         uint64_t startPrio)
 {
+  NS_LOG_FUNCTION (this << nBuckets << width << startPrio);
   m_buckets = new Bucket [nBuckets];
   m_nBuckets = nBuckets;
   m_width = width;
@@ -96,53 +55,31 @@
   m_lastBucket = Hash (startPrio);
   m_bucketTop = (startPrio / width + 1) * width;
 }
-Calendar::~Calendar ()
-{
-  delete [] m_buckets;
-  m_buckets = 0;
-}
-Calendar *
-Calendar::CreateResized (uint32_t nBuckets, 
-                         uint64_t newWidth) const
+void
+CalendarScheduler::PrintInfo (void)
 {
-  Calendar *calendar = new Calendar (nBuckets, newWidth, m_lastPrio);
-  for (uint32_t i = 0; i < m_nBuckets; i++)
-    {
-      Bucket::iterator end = m_buckets[i].end ();
-      for (Bucket::iterator j = m_buckets[i].begin (); j != end; ++j) 
-        {
-          calendar->Insert (*j);
-        }
-    }
-  return calendar;
-}
-
-void
-Calendar::PrintBucketDistribution (void)
-{
+  std::cout << "nBuckets=" << m_nBuckets << ", width=" << m_width<< std::endl;
+  std::cout << "Bucket Distribution ";
   for (uint32_t i = 0; i < m_nBuckets; i++)
     {
       std::cout << m_buckets[i].size () << " ";
     }
   std::cout << std::endl;
 }
-uint32_t 
-Calendar::GetNBuckets (void) const
-{
-  return m_nBuckets;
-}
 uint32_t
-Calendar::Hash (uint64_t ts) const
+CalendarScheduler::Hash (uint64_t ts) const
 {
   uint32_t bucket = (ts / m_width) % m_nBuckets;
   return bucket;
 }
+
 void
-Calendar::Insert (const Scheduler::Event &ev)
+CalendarScheduler::DoInsert (const Event &ev)
 {
   NS_LOG_FUNCTION (this << ev.key.m_ts << ev.key.m_uid);
   // calculate bucket index.
   uint32_t bucket = Hash (ev.key.m_ts);
+  NS_LOG_LOGIC ("insert in bucket=" << bucket);
 
   // insert in bucket list.
   Bucket::iterator end = m_buckets[bucket].end ();
@@ -155,42 +92,25 @@
         }
     }
   m_buckets[bucket].push_back (ev);
-  NS_LOG_LOGIC ("insert in bucket=" << bucket);
-}
-std::list<Scheduler::Event>
-Calendar::PeekNext (uint32_t n) const
-{
-  // save state
-  uint32_t lastBucket = m_lastBucket;
-  uint64_t bucketTop = m_bucketTop;
-  uint64_t lastPrio = m_lastPrio;
- 
-  Calendar *self = const_cast<Calendar *> (this); 
-  std::list<Scheduler::Event> events;
-  // gather requested events
-  for (uint32_t i = 0; i < n; i++)
-    {
-      events.push_back (self->RemoveNext ());
-    }
-  // put them back
-  for (std::list<Scheduler::Event>::const_iterator i = events.begin (); i != events.end (); ++i)
-    {
-      self->Insert (*i);
-    }
-
-  // restore state.
-  self->m_lastBucket = lastBucket;
-  self->m_bucketTop = bucketTop;
-  self->m_lastPrio = lastPrio;
-
-  // return copy of requested events.
-  return events;
 }
 
+void
+CalendarScheduler::Insert (const Event &ev)
+{
+  DoInsert (ev);
+  m_qSize++;
+  ResizeUp ();
+}
+bool 
+CalendarScheduler::IsEmpty (void) const
+{
+  return m_qSize == 0;
+}
 Scheduler::Event
-Calendar::PeekNext (void) const
+CalendarScheduler::PeekNext (void) const
 {
   NS_LOG_FUNCTION (this << m_lastBucket << m_bucketTop);
+  NS_ASSERT (!IsEmpty ());
   uint32_t i = m_lastBucket;
   uint64_t bucketTop = m_bucketTop;
   Scheduler::Event minEvent = {0, {~0, ~0}};
@@ -216,9 +136,8 @@
 }
 
 Scheduler::Event
-Calendar::RemoveNext (void)
+CalendarScheduler::DoRemoveNext (void)
 {
-  NS_LOG_FUNCTION (this << m_lastBucket << m_bucketTop);
   uint32_t i = m_lastBucket;
   uint64_t bucketTop = m_bucketTop;
   Scheduler::Event minEvent = {0, {~0, ~0}};
@@ -232,7 +151,6 @@
             m_lastPrio = next.key.m_ts;
             m_bucketTop = bucketTop;
             m_buckets[i].pop_front ();
-            NS_LOG_LOGIC ("remove ts=" << next.key.m_ts << ", key=" << next.key.m_uid << ", from bucket=" << i);
             return next;
           }
         if (next.key < minEvent.key)
@@ -250,14 +168,28 @@
   m_bucketTop = (minEvent.key.m_ts / m_width + 1) * m_width;
   m_buckets[m_lastBucket].pop_front ();
 
-  NS_LOG_LOGIC ("remove ts=" << minEvent.key.m_ts << ", key=" << minEvent.key.m_uid << ", from bucket=" << m_lastBucket);
-
   return minEvent;
 }
 
+Scheduler::Event
+CalendarScheduler::RemoveNext (void)
+{
+  NS_LOG_FUNCTION (this << m_lastBucket << m_bucketTop);
+  NS_ASSERT (!IsEmpty ());
+
+  Scheduler::Event ev = DoRemoveNext ();
+  NS_LOG_LOGIC ("remove ts=" << ev.key.m_ts << 
+                ", key=" << ev.key.m_uid << 
+                ", from bucket=" << m_lastBucket);
+  m_qSize--;
+  ResizeDown ();
+  return ev;
+}
+
 void
-Calendar::Remove (const Scheduler::Event &ev)
+CalendarScheduler::Remove (const Event &ev)
 {
+  NS_ASSERT (!IsEmpty ());
   // bucket index of event
   uint32_t bucket = Hash (ev.key.m_ts);
 
@@ -268,79 +200,30 @@
         {
           NS_ASSERT (ev.impl == i->impl);
           m_buckets[bucket].erase (i);
+
+          m_qSize--;
+          ResizeDown ();
           return;
         }
     }
   NS_ASSERT (false);
 }
 
-
-CalendarScheduler::CalendarScheduler ()
-{
-  NS_LOG_FUNCTION (this);
-  m_calendar = new Calendar ();
-  m_qSize = 0;
-}
-CalendarScheduler::~CalendarScheduler ()
-{
-  NS_LOG_FUNCTION (this);
-  delete m_calendar;
-  m_calendar = 0;
-}
-
-void
-CalendarScheduler::Insert (const Event &ev)
-{
-  m_calendar->Insert (ev);
-  m_qSize++;
-  ResizeUp ();
-}
-bool 
-CalendarScheduler::IsEmpty (void) const
-{
-  return m_qSize == 0;
-}
-Scheduler::Event
-CalendarScheduler::PeekNext (void) const
-{
-  NS_ASSERT (!IsEmpty ());
-  return m_calendar->PeekNext ();
-}
-
-Scheduler::Event
-CalendarScheduler::RemoveNext (void)
-{
-  NS_ASSERT (!IsEmpty ());
-  Scheduler::Event ev = m_calendar->RemoveNext ();
-  m_qSize--;
-  ResizeDown ();
-
-  return ev;
-}
-
-void
-CalendarScheduler::Remove (const Event &ev)
-{
-  NS_ASSERT (!IsEmpty ());
-  m_calendar->Remove (ev);
-  m_qSize--;
-  ResizeDown ();
-}
-
 void 
 CalendarScheduler::ResizeUp (void)
 {
-  if (m_qSize > m_calendar->GetNBuckets () * 2)
+  if (m_qSize > m_nBuckets * 2 && 
+      m_nBuckets < 32768)
     {
-      Resize (m_calendar->GetNBuckets () * 2);
+      Resize (m_nBuckets * 2);
     }
 }
 void 
 CalendarScheduler::ResizeDown (void)
 {
-  if (m_qSize < m_calendar->GetNBuckets () / 2)
+  if (m_qSize < m_nBuckets / 2)
     {
-      Resize (m_calendar->GetNBuckets () / 2);
+      Resize (m_nBuckets / 2);
     }
 }
 
@@ -365,8 +248,31 @@
       nSamples = 25;
     }
 
-  std::list<Scheduler::Event> samples = m_calendar->PeekNext (nSamples);
-  
+  // we gather the first nSamples from the queue
+  std::list<Scheduler::Event> samples;
+  // save state
+  uint32_t lastBucket = m_lastBucket;
+  uint64_t bucketTop = m_bucketTop;
+  uint64_t lastPrio = m_lastPrio;
+ 
+  // gather requested events
+  for (uint32_t i = 0; i < nSamples; i++)
+    {
+      samples.push_back (DoRemoveNext ());
+    }
+  // put them back
+  for (std::list<Scheduler::Event>::const_iterator i = samples.begin (); 
+       i != samples.end (); ++i)
+    {
+      DoInsert (*i);
+    }
+
+  // restore state.
+  m_lastBucket = lastBucket;
+  m_bucketTop = bucketTop;
+  m_lastPrio = lastPrio;
+
+  // finally calculate inter-time average over samples.
   uint64_t totalSeparation = 0;
   std::list<Scheduler::Event>::const_iterator end = samples.end ();
   std::list<Scheduler::Event>::const_iterator cur = samples.begin ();
@@ -398,19 +304,30 @@
   totalSeparation = std::max (totalSeparation, (uint64_t)1);
   return totalSeparation;
 }
+void
+CalendarScheduler::DoResize (uint32_t newSize, uint32_t newWidth)
+{
+  Bucket *oldBuckets = m_buckets;
+  uint32_t oldNBuckets = m_nBuckets;
+  Init (newSize, newWidth, m_lastPrio);
 
+  for (uint32_t i = 0; i < oldNBuckets; i++)
+    {
+      Bucket::iterator end = oldBuckets[i].end ();
+      for (Bucket::iterator j = oldBuckets[i].begin (); j != end; ++j) 
+        {
+          DoInsert (*j);
+        }
+    }
+}
 void 
 CalendarScheduler::Resize (uint32_t newSize)
 {
   NS_LOG_FUNCTION (this << newSize);
 
-  m_calendar->PrintBucketDistribution ();
-
+  //PrintInfo ();
   uint32_t newWidth = CalculateNewWidth ();  
-  Calendar *calendar = m_calendar->CreateResized (newSize, newWidth);
-
-  delete m_calendar;
-  m_calendar = calendar;
+  DoResize (newSize, newWidth);
 }
 
 } // namespace ns3
--- a/src/simulator/calendar-scheduler.h	Thu Jan 08 16:23:33 2009 +0100
+++ b/src/simulator/calendar-scheduler.h	Fri Jan 09 07:51:17 2009 +0100
@@ -23,11 +23,11 @@
 
 #include "scheduler.h"
 #include <stdint.h>
+#include <list>
 
 namespace ns3 {
 
 class EventImpl;
-class Calendar;
 
 /**
  * \ingroup scheduler
@@ -49,8 +49,28 @@
   void ResizeDown (void);
   void Resize (uint32_t newSize);
   uint32_t CalculateNewWidth (void);
+  void Init (uint32_t nBuckets, 
+             uint64_t width,
+             uint64_t startPrio);
+  inline uint32_t Hash (uint64_t key) const;
+  void PrintInfo (void);
+  void DoResize (uint32_t newSize, uint32_t newWidth);
+  Scheduler::Event DoRemoveNext (void);
+  void DoInsert (const Event &ev);
 
-  Calendar *m_calendar;
+  typedef std::list<Scheduler::Event> Bucket;
+  Bucket *m_buckets;
+  // number of buckets in array
+  uint32_t m_nBuckets;
+  // duration of a bucket
+  uint64_t m_width;
+  // bucket index from which the last event was dequeued
+  uint32_t m_lastBucket;
+  // priority at the top of the bucket from which last event was dequeued
+  uint64_t m_bucketTop;
+  // the priority of the last event removed
+  uint64_t m_lastPrio;
+  // number of events in queue
   uint32_t m_qSize;
 };