--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/simulator/heap-scheduler.cc Tue Apr 15 10:09:42 2008 -0700
@@ -0,0 +1,263 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2006 INRIA
+ * Copyright (c) 2005 Mathieu Lacage
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ *
+ * This code started as a c++ translation of a java-based code written in 2005
+ * to implement a heap sort. Which explains the "Copyright Mathieu Lacage" at the
+ * top of this file.
+ *
+ * What is smart about this code ?
+ * - it does not use the index 0 in the array to avoid having to convert
+ * C-style array indexes (which start at zero) and heap-style indexes
+ * (which start at 1). This is why _all_ indexes start at 1, and that
+ * the index of the root is 1.
+ * - It uses a slightly non-standard while loop for top-down heapify
+ * to move one if statement out of the loop.
+ */
+
+#include "heap-scheduler.h"
+#include "event-impl.h"
+#include "ns3/assert.h"
+
+#include <string>
+#define noTRACE_HEAP 1
+
+#ifdef TRACE_HEAP
+#include <iostream>
+# define TRACE(x) \
+std::cout << "HEAP TRACE " << x << std::endl;
+#else /* TRACE_HEAP */
+# define TRACE(format,...)
+#endif /* TRACE_HEAP */
+
+
+
+
+namespace ns3 {
+
+
+HeapScheduler::HeapScheduler ()
+{
+ // we purposedly waste an item at the start of
+ // the array to make sure the indexes in the
+ // array start at one.
+ Scheduler::EventKey emptyKey = {0,0};
+ m_heap.push_back (std::make_pair (static_cast<EventImpl *>(0), emptyKey));
+}
+
+HeapScheduler::~HeapScheduler ()
+{}
+
+uint32_t
+HeapScheduler::Parent (uint32_t id) const
+{
+ return id / 2;
+}
+uint32_t
+HeapScheduler::Sibling (uint32_t id) const
+{
+ return id + 1;
+}
+uint32_t
+HeapScheduler::LeftChild (uint32_t id) const
+{
+ return id * 2;
+}
+uint32_t
+HeapScheduler::RightChild (uint32_t id) const
+{
+ return id * 2 + 1;
+}
+
+uint32_t
+HeapScheduler::Root (void) const
+{
+ return 1;
+}
+
+bool
+HeapScheduler::IsRoot (uint32_t id) const
+{
+ return (id == Root ())?true:false;
+}
+
+uint32_t
+HeapScheduler::Last (void) const
+{
+ return m_heap.size () - 1;
+}
+
+
+bool
+HeapScheduler::IsBottom (uint32_t id) const
+{
+ return (id >= m_heap.size ())?true:false;
+}
+
+void
+HeapScheduler::Exch (uint32_t a, uint32_t b)
+{
+ NS_ASSERT (b < m_heap.size () && a < m_heap.size ());
+ TRACE ("Exch " << a << ", " << b);
+ std::pair<EventImpl*, Scheduler::EventKey> tmp (m_heap[a]);
+ m_heap[a] = m_heap[b];
+ m_heap[b] = tmp;
+}
+
+bool
+HeapScheduler::IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
+{
+ if (a->m_ts < b->m_ts)
+ {
+ return true;
+ }
+ else if (a->m_ts > b->m_ts)
+ {
+ return false;
+ }
+ else if (a->m_uid < b->m_uid)
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+}
+
+bool
+HeapScheduler::IsLessStrictly (uint32_t a, uint32_t b) const
+{
+ return IsLowerStrictly (&m_heap[a].second, &m_heap[b].second);
+}
+
+uint32_t
+HeapScheduler::Smallest (uint32_t a, uint32_t b) const
+{
+ return IsLessStrictly (a,b)?a:b;
+}
+
+bool
+HeapScheduler::IsEmpty (void) const
+{
+ return (m_heap.size () == 1)?true:false;
+}
+
+void
+HeapScheduler::BottomUp (void)
+{
+ uint32_t index = Last ();
+ while (!IsRoot (index) &&
+ IsLessStrictly (index, Parent (index)))
+ {
+ Exch(index, Parent (index));
+ index = Parent (index);
+ }
+}
+
+void
+HeapScheduler::TopDown (uint32_t start)
+{
+ uint32_t index = start;
+ uint32_t right = RightChild (index);
+ while (!IsBottom (right))
+ {
+ uint32_t left = LeftChild (index);
+ uint32_t tmp = Smallest (left, right);
+ if (IsLessStrictly (index, tmp))
+ {
+ return;
+ }
+ Exch (index, tmp);
+ index = tmp;
+ right = RightChild (index);
+ }
+ if (IsBottom (index))
+ {
+ return;
+ }
+ NS_ASSERT (!IsBottom (index));
+ uint32_t left = LeftChild (index);
+ if (IsBottom (left))
+ {
+ return;
+ }
+ if (IsLessStrictly (index, left))
+ {
+ return;
+ }
+ Exch (index, left);
+}
+
+
+void
+HeapScheduler::Insert (const EventId &id)
+{
+ // acquire single ref
+ EventImpl *event = id.PeekEventImpl ();
+ event->Ref ();
+ Scheduler::EventKey key;
+ key.m_ts = id.GetTs ();
+ key.m_uid = id.GetUid ();
+ m_heap.push_back (std::make_pair (event, key));
+ BottomUp ();
+}
+
+EventId
+HeapScheduler::PeekNext (void) const
+{
+ std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
+ return EventId (next.first, next.second.m_ts, next.second.m_uid);
+}
+EventId
+HeapScheduler::RemoveNext (void)
+{
+ std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
+ Exch (Root (), Last ());
+ m_heap.pop_back ();
+ TopDown (Root ());
+ return EventId (Ptr<EventImpl> (next.first, false), next.second.m_ts, next.second.m_uid);
+}
+
+
+bool
+HeapScheduler::Remove (const EventId &id)
+{
+ uint32_t uid = id.GetUid ();
+ for (uint32_t i = 1; i < m_heap.size (); i++)
+ {
+ if (uid == m_heap[i].second.m_uid)
+ {
+ NS_ASSERT (m_heap[i].first == id.PeekEventImpl ());
+ std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[i];
+ // release single ref
+ next.first->Unref ();
+ Exch (i, Last ());
+ m_heap.pop_back ();
+ TopDown (i);
+ return true;
+ }
+ }
+ NS_ASSERT (false);
+ // quiet compiler
+ return false;
+}
+
+}; // namespace ns3
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/simulator/heap-scheduler.h Tue Apr 15 10:09:42 2008 -0700
@@ -0,0 +1,69 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2005 INRIA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ */
+
+#ifndef SCHEDULER_HEAP_H
+#define SCHEDULER_HEAP_H
+
+#include "scheduler.h"
+#include <stdint.h>
+#include <vector>
+
+namespace ns3 {
+
+class EventHolder;
+
+class HeapScheduler : public Scheduler {
+public:
+ HeapScheduler ();
+ virtual ~HeapScheduler ();
+
+ virtual void Insert (const EventId &id);
+ virtual bool IsEmpty (void) const;
+ virtual EventId PeekNext (void) const;
+ virtual EventId RemoveNext (void);
+ virtual bool Remove (const EventId &ev);
+
+private:
+ typedef std::vector<std::pair<EventImpl *, Scheduler::EventKey> > BinaryHeap;
+
+ inline uint32_t Parent (uint32_t id) const;
+ uint32_t Sibling (uint32_t id) const;
+ inline uint32_t LeftChild (uint32_t id) const;
+ inline uint32_t RightChild (uint32_t id) const;
+ inline uint32_t Root (void) const;
+ /* Return the position in the array of the last element included in it. */
+ uint32_t Last (void) const;
+ inline bool IsRoot (uint32_t id) const;
+ inline bool IsBottom (uint32_t id) const;
+ inline bool IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
+ inline bool IsLessStrictly (uint32_t a, uint32_t b) const;
+ inline uint32_t Smallest (uint32_t a, uint32_t b) const;
+
+ inline void Exch (uint32_t a, uint32_t b);
+ void BottomUp (void);
+ void TopDown (uint32_t start);
+
+ BinaryHeap m_heap;
+};
+
+}; // namespace ns3
+
+
+#endif /* SCHEDULER_HEAP_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/simulator/list-scheduler.cc Tue Apr 15 10:09:42 2008 -0700
@@ -0,0 +1,110 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2005 INRIA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ */
+
+#include "list-scheduler.h"
+#include "event-impl.h"
+#include <utility>
+#include <string>
+#include "ns3/assert.h"
+
+namespace ns3 {
+
+
+ListScheduler::ListScheduler ()
+{}
+ListScheduler::~ListScheduler ()
+{}
+
+bool
+ListScheduler::IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
+{
+ if (a->m_ts < b->m_ts)
+ {
+ return true;
+ }
+ else if (a->m_ts == b->m_ts &&
+ a->m_uid < b->m_uid)
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+}
+
+void
+ListScheduler::Insert (const EventId &id)
+{
+ Scheduler::EventKey key;
+ // acquire refcount on EventImpl
+ EventImpl *event = id.PeekEventImpl ();
+ event->Ref ();
+ key.m_ts = id.GetTs ();
+ key.m_uid = id.GetUid ();
+ for (EventsI i = m_events.begin (); i != m_events.end (); i++)
+ {
+ if (IsLower (&key, &i->second))
+ {
+ m_events.insert (i, std::make_pair (event, key));
+ return;
+ }
+ }
+ m_events.push_back (std::make_pair (event, key));
+}
+bool
+ListScheduler::IsEmpty (void) const
+{
+ return m_events.empty ();
+}
+EventId
+ListScheduler::PeekNext (void) const
+{
+ std::pair<EventImpl *, EventKey> next = m_events.front ();
+ return EventId (next.first, next.second.m_ts, next.second.m_uid);
+}
+
+EventId
+ListScheduler::RemoveNext (void)
+{
+ std::pair<EventImpl *, EventKey> next = m_events.front ();
+ m_events.pop_front ();
+ return EventId (Ptr<EventImpl> (next.first,false), next.second.m_ts, next.second.m_uid);
+}
+
+bool
+ListScheduler::Remove (const EventId &id)
+{
+ for (EventsI i = m_events.begin (); i != m_events.end (); i++)
+ {
+ if (i->second.m_uid == id.GetUid ())
+ {
+ NS_ASSERT (id.PeekEventImpl () == i->first);
+ // release single acquire ref.
+ i->first->Unref ();
+ m_events.erase (i);
+ return true;
+ }
+ }
+ NS_ASSERT (false);
+ return false;
+}
+
+}; // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/simulator/list-scheduler.h Tue Apr 15 10:09:42 2008 -0700
@@ -0,0 +1,56 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2005 INRIA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ */
+
+#ifndef SCHEDULER_LIST_H
+#define SCHEDULER_LIST_H
+
+#include "scheduler.h"
+#include "event-id.h"
+#include <list>
+#include <utility>
+#include <stdint.h>
+
+namespace ns3 {
+
+class EventImpl;
+
+class ListScheduler : public Scheduler {
+ public:
+ ListScheduler ();
+ virtual ~ListScheduler ();
+
+ virtual void Insert (const EventId &id);
+ virtual bool IsEmpty (void) const;
+ virtual EventId PeekNext (void) const;
+ virtual EventId RemoveNext (void);
+ virtual bool Remove (const EventId &ev);
+
+ private:
+ inline bool IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
+
+ typedef std::list<std::pair<EventImpl*, EventKey> > Events;
+ typedef std::list<std::pair<EventImpl*, EventKey> >::iterator EventsI;
+ Events m_events;
+};
+
+}; // namespace ns3
+
+
+#endif /* SCHEDULER_LIST_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/simulator/map-scheduler.cc Tue Apr 15 10:09:42 2008 -0700
@@ -0,0 +1,124 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2006 INRIA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ * The idea to use a std c++ map came from GTNetS
+ */
+
+#include "map-scheduler.h"
+#include "event-impl.h"
+#include "ns3/assert.h"
+#include <string>
+
+#define noTRACE_MAP 1
+
+#ifdef TRACE_MAP
+#include <iostream>
+# define TRACE(x) \
+std::cout << "MAP TRACE " << x << std::endl;
+#else /* TRACE_MAP */
+# define TRACE(format,...)
+#endif /* TRACE_MAP */
+
+
+namespace ns3 {
+
+MapScheduler::MapScheduler ()
+{}
+MapScheduler::~MapScheduler ()
+{}
+
+/* Note the invariants which this function must provide:
+ * - irreflexibility: f (x,x) is false)
+ * - antisymmetry: f(x,y) = !f(y,x)
+ * - transitivity: f(x,y) and f(y,z) => f(x,z)
+ */
+bool
+MapScheduler::EventKeyCompare::operator () (struct EventKey const&a, struct EventKey const&b)
+{
+ if (a.m_ts < b.m_ts)
+ {
+ return true;
+ }
+ else if (a.m_ts > b.m_ts)
+ {
+ return false;
+ }
+ else if (a.m_uid < b.m_uid)
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+}
+
+
+
+void
+MapScheduler::Insert (const EventId &id)
+{
+ // acquire a single ref
+ EventImpl *event = id.PeekEventImpl ();
+ event->Ref ();
+ Scheduler::EventKey key;
+ key.m_ts = id.GetTs ();
+ key.m_uid = id.GetUid ();
+ std::pair<EventMapI,bool> result;
+ result = m_list.insert (std::make_pair (key, event));
+ NS_ASSERT (result.second);
+}
+
+bool
+MapScheduler::IsEmpty (void) const
+{
+ return m_list.empty ();
+}
+
+EventId
+MapScheduler::PeekNext (void) const
+{
+ EventMapCI i = m_list.begin ();
+ NS_ASSERT (i != m_list.end ());
+
+ return EventId (i->second, i->first.m_ts, i->first.m_uid);
+}
+EventId
+MapScheduler::RemoveNext (void)
+{
+ EventMapI i = m_list.begin ();
+ std::pair<Scheduler::EventKey, EventImpl*> next = *i;
+ m_list.erase (i);
+ return EventId (Ptr<EventImpl> (next.second, false), next.first.m_ts, next.first.m_uid);
+}
+
+bool
+MapScheduler::Remove (const EventId &id)
+{
+ Scheduler::EventKey key;
+ key.m_ts = id.GetTs ();
+ key.m_uid = id.GetUid ();
+ EventMapI i = m_list.find (key);
+ NS_ASSERT (i->second == id.PeekEventImpl ());
+ // release single ref.
+ i->second->Unref ();
+ m_list.erase (i);
+ return true;
+}
+
+}; // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/simulator/map-scheduler.h Tue Apr 15 10:09:42 2008 -0700
@@ -0,0 +1,61 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2006 INRIA
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ */
+
+#ifndef SCHEDULER_MAP_H
+#define SCHEDULER_MAP_H
+
+#include "scheduler.h"
+#include <stdint.h>
+#include <map>
+#include <utility>
+
+namespace ns3 {
+
+class EventImpl;
+
+class MapScheduler : public Scheduler {
+public:
+ MapScheduler ();
+ virtual ~MapScheduler ();
+
+ virtual void Insert (const EventId &id);
+ virtual bool IsEmpty (void) const;
+ virtual EventId PeekNext (void) const;
+ virtual EventId RemoveNext (void);
+ virtual bool Remove (const EventId &ev);
+private:
+
+ class EventKeyCompare {
+ public:
+ bool operator () (struct EventKey const&a, struct EventKey const&b);
+ };
+
+ typedef std::map<Scheduler::EventKey, EventImpl*, MapScheduler::EventKeyCompare> EventMap;
+ typedef std::map<Scheduler::EventKey, EventImpl*, MapScheduler::EventKeyCompare>::iterator EventMapI;
+ typedef std::map<Scheduler::EventKey, EventImpl*, MapScheduler::EventKeyCompare>::const_iterator EventMapCI;
+
+
+ EventMap m_list;
+};
+
+}; // namespace ns3
+
+
+#endif /* SCHEDULER_MAP_H */
--- a/src/simulator/scheduler-heap.cc Tue Apr 15 09:41:58 2008 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,263 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2006 INRIA
- * Copyright (c) 2005 Mathieu Lacage
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation;
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
- *
- * This code started as a c++ translation of a java-based code written in 2005
- * to implement a heap sort. Which explains the "Copyright Mathieu Lacage" at the
- * top of this file.
- *
- * What is smart about this code ?
- * - it does not use the index 0 in the array to avoid having to convert
- * C-style array indexes (which start at zero) and heap-style indexes
- * (which start at 1). This is why _all_ indexes start at 1, and that
- * the index of the root is 1.
- * - It uses a slightly non-standard while loop for top-down heapify
- * to move one if statement out of the loop.
- */
-
-#include "scheduler-heap.h"
-#include "event-impl.h"
-#include "ns3/assert.h"
-
-#include <string>
-#define noTRACE_HEAP 1
-
-#ifdef TRACE_HEAP
-#include <iostream>
-# define TRACE(x) \
-std::cout << "HEAP TRACE " << x << std::endl;
-#else /* TRACE_HEAP */
-# define TRACE(format,...)
-#endif /* TRACE_HEAP */
-
-
-
-
-namespace ns3 {
-
-
-SchedulerHeap::SchedulerHeap ()
-{
- // we purposedly waste an item at the start of
- // the array to make sure the indexes in the
- // array start at one.
- Scheduler::EventKey emptyKey = {0,0};
- m_heap.push_back (std::make_pair (static_cast<EventImpl *>(0), emptyKey));
-}
-
-SchedulerHeap::~SchedulerHeap ()
-{}
-
-uint32_t
-SchedulerHeap::Parent (uint32_t id) const
-{
- return id / 2;
-}
-uint32_t
-SchedulerHeap::Sibling (uint32_t id) const
-{
- return id + 1;
-}
-uint32_t
-SchedulerHeap::LeftChild (uint32_t id) const
-{
- return id * 2;
-}
-uint32_t
-SchedulerHeap::RightChild (uint32_t id) const
-{
- return id * 2 + 1;
-}
-
-uint32_t
-SchedulerHeap::Root (void) const
-{
- return 1;
-}
-
-bool
-SchedulerHeap::IsRoot (uint32_t id) const
-{
- return (id == Root ())?true:false;
-}
-
-uint32_t
-SchedulerHeap::Last (void) const
-{
- return m_heap.size () - 1;
-}
-
-
-bool
-SchedulerHeap::IsBottom (uint32_t id) const
-{
- return (id >= m_heap.size ())?true:false;
-}
-
-void
-SchedulerHeap::Exch (uint32_t a, uint32_t b)
-{
- NS_ASSERT (b < m_heap.size () && a < m_heap.size ());
- TRACE ("Exch " << a << ", " << b);
- std::pair<EventImpl*, Scheduler::EventKey> tmp (m_heap[a]);
- m_heap[a] = m_heap[b];
- m_heap[b] = tmp;
-}
-
-bool
-SchedulerHeap::IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
-{
- if (a->m_ts < b->m_ts)
- {
- return true;
- }
- else if (a->m_ts > b->m_ts)
- {
- return false;
- }
- else if (a->m_uid < b->m_uid)
- {
- return true;
- }
- else
- {
- return false;
- }
-}
-
-bool
-SchedulerHeap::IsLessStrictly (uint32_t a, uint32_t b) const
-{
- return IsLowerStrictly (&m_heap[a].second, &m_heap[b].second);
-}
-
-uint32_t
-SchedulerHeap::Smallest (uint32_t a, uint32_t b) const
-{
- return IsLessStrictly (a,b)?a:b;
-}
-
-bool
-SchedulerHeap::IsEmpty (void) const
-{
- return (m_heap.size () == 1)?true:false;
-}
-
-void
-SchedulerHeap::BottomUp (void)
-{
- uint32_t index = Last ();
- while (!IsRoot (index) &&
- IsLessStrictly (index, Parent (index)))
- {
- Exch(index, Parent (index));
- index = Parent (index);
- }
-}
-
-void
-SchedulerHeap::TopDown (uint32_t start)
-{
- uint32_t index = start;
- uint32_t right = RightChild (index);
- while (!IsBottom (right))
- {
- uint32_t left = LeftChild (index);
- uint32_t tmp = Smallest (left, right);
- if (IsLessStrictly (index, tmp))
- {
- return;
- }
- Exch (index, tmp);
- index = tmp;
- right = RightChild (index);
- }
- if (IsBottom (index))
- {
- return;
- }
- NS_ASSERT (!IsBottom (index));
- uint32_t left = LeftChild (index);
- if (IsBottom (left))
- {
- return;
- }
- if (IsLessStrictly (index, left))
- {
- return;
- }
- Exch (index, left);
-}
-
-
-void
-SchedulerHeap::Insert (const EventId &id)
-{
- // acquire single ref
- EventImpl *event = id.PeekEventImpl ();
- event->Ref ();
- Scheduler::EventKey key;
- key.m_ts = id.GetTs ();
- key.m_uid = id.GetUid ();
- m_heap.push_back (std::make_pair (event, key));
- BottomUp ();
-}
-
-EventId
-SchedulerHeap::PeekNext (void) const
-{
- std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
- return EventId (next.first, next.second.m_ts, next.second.m_uid);
-}
-EventId
-SchedulerHeap::RemoveNext (void)
-{
- std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
- Exch (Root (), Last ());
- m_heap.pop_back ();
- TopDown (Root ());
- return EventId (Ptr<EventImpl> (next.first, false), next.second.m_ts, next.second.m_uid);
-}
-
-
-bool
-SchedulerHeap::Remove (const EventId &id)
-{
- uint32_t uid = id.GetUid ();
- for (uint32_t i = 1; i < m_heap.size (); i++)
- {
- if (uid == m_heap[i].second.m_uid)
- {
- NS_ASSERT (m_heap[i].first == id.PeekEventImpl ());
- std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[i];
- // release single ref
- next.first->Unref ();
- Exch (i, Last ());
- m_heap.pop_back ();
- TopDown (i);
- return true;
- }
- }
- NS_ASSERT (false);
- // quiet compiler
- return false;
-}
-
-}; // namespace ns3
-
--- a/src/simulator/scheduler-heap.h Tue Apr 15 09:41:58 2008 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,69 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2005 INRIA
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation;
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
- */
-
-#ifndef SCHEDULER_HEAP_H
-#define SCHEDULER_HEAP_H
-
-#include "scheduler.h"
-#include <stdint.h>
-#include <vector>
-
-namespace ns3 {
-
-class EventHolder;
-
-class SchedulerHeap : public Scheduler {
-public:
- SchedulerHeap ();
- virtual ~SchedulerHeap ();
-
- virtual void Insert (const EventId &id);
- virtual bool IsEmpty (void) const;
- virtual EventId PeekNext (void) const;
- virtual EventId RemoveNext (void);
- virtual bool Remove (const EventId &ev);
-
-private:
- typedef std::vector<std::pair<EventImpl *, Scheduler::EventKey> > BinaryHeap;
-
- inline uint32_t Parent (uint32_t id) const;
- uint32_t Sibling (uint32_t id) const;
- inline uint32_t LeftChild (uint32_t id) const;
- inline uint32_t RightChild (uint32_t id) const;
- inline uint32_t Root (void) const;
- /* Return the position in the array of the last element included in it. */
- uint32_t Last (void) const;
- inline bool IsRoot (uint32_t id) const;
- inline bool IsBottom (uint32_t id) const;
- inline bool IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
- inline bool IsLessStrictly (uint32_t a, uint32_t b) const;
- inline uint32_t Smallest (uint32_t a, uint32_t b) const;
-
- inline void Exch (uint32_t a, uint32_t b);
- void BottomUp (void);
- void TopDown (uint32_t start);
-
- BinaryHeap m_heap;
-};
-
-}; // namespace ns3
-
-
-#endif /* SCHEDULER_HEAP_H */
--- a/src/simulator/scheduler-list.cc Tue Apr 15 09:41:58 2008 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,110 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2005 INRIA
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation;
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
- */
-
-#include "scheduler-list.h"
-#include "event-impl.h"
-#include <utility>
-#include <string>
-#include "ns3/assert.h"
-
-namespace ns3 {
-
-
-SchedulerList::SchedulerList ()
-{}
-SchedulerList::~SchedulerList ()
-{}
-
-bool
-SchedulerList::IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
-{
- if (a->m_ts < b->m_ts)
- {
- return true;
- }
- else if (a->m_ts == b->m_ts &&
- a->m_uid < b->m_uid)
- {
- return true;
- }
- else
- {
- return false;
- }
-}
-
-void
-SchedulerList::Insert (const EventId &id)
-{
- Scheduler::EventKey key;
- // acquire refcount on EventImpl
- EventImpl *event = id.PeekEventImpl ();
- event->Ref ();
- key.m_ts = id.GetTs ();
- key.m_uid = id.GetUid ();
- for (EventsI i = m_events.begin (); i != m_events.end (); i++)
- {
- if (IsLower (&key, &i->second))
- {
- m_events.insert (i, std::make_pair (event, key));
- return;
- }
- }
- m_events.push_back (std::make_pair (event, key));
-}
-bool
-SchedulerList::IsEmpty (void) const
-{
- return m_events.empty ();
-}
-EventId
-SchedulerList::PeekNext (void) const
-{
- std::pair<EventImpl *, EventKey> next = m_events.front ();
- return EventId (next.first, next.second.m_ts, next.second.m_uid);
-}
-
-EventId
-SchedulerList::RemoveNext (void)
-{
- std::pair<EventImpl *, EventKey> next = m_events.front ();
- m_events.pop_front ();
- return EventId (Ptr<EventImpl> (next.first,false), next.second.m_ts, next.second.m_uid);
-}
-
-bool
-SchedulerList::Remove (const EventId &id)
-{
- for (EventsI i = m_events.begin (); i != m_events.end (); i++)
- {
- if (i->second.m_uid == id.GetUid ())
- {
- NS_ASSERT (id.PeekEventImpl () == i->first);
- // release single acquire ref.
- i->first->Unref ();
- m_events.erase (i);
- return true;
- }
- }
- NS_ASSERT (false);
- return false;
-}
-
-}; // namespace ns3
--- a/src/simulator/scheduler-list.h Tue Apr 15 09:41:58 2008 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,56 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2005 INRIA
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation;
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
- */
-
-#ifndef SCHEDULER_LIST_H
-#define SCHEDULER_LIST_H
-
-#include "scheduler.h"
-#include "event-id.h"
-#include <list>
-#include <utility>
-#include <stdint.h>
-
-namespace ns3 {
-
-class EventImpl;
-
-class SchedulerList : public Scheduler {
- public:
- SchedulerList ();
- virtual ~SchedulerList ();
-
- virtual void Insert (const EventId &id);
- virtual bool IsEmpty (void) const;
- virtual EventId PeekNext (void) const;
- virtual EventId RemoveNext (void);
- virtual bool Remove (const EventId &ev);
-
- private:
- inline bool IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
-
- typedef std::list<std::pair<EventImpl*, EventKey> > Events;
- typedef std::list<std::pair<EventImpl*, EventKey> >::iterator EventsI;
- Events m_events;
-};
-
-}; // namespace ns3
-
-
-#endif /* SCHEDULER_LIST_H */
--- a/src/simulator/scheduler-map.cc Tue Apr 15 09:41:58 2008 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,124 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2006 INRIA
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation;
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
- * The idea to use a std c++ map came from GTNetS
- */
-
-#include "scheduler-map.h"
-#include "event-impl.h"
-#include "ns3/assert.h"
-#include <string>
-
-#define noTRACE_MAP 1
-
-#ifdef TRACE_MAP
-#include <iostream>
-# define TRACE(x) \
-std::cout << "MAP TRACE " << x << std::endl;
-#else /* TRACE_MAP */
-# define TRACE(format,...)
-#endif /* TRACE_MAP */
-
-
-namespace ns3 {
-
-SchedulerMap::SchedulerMap ()
-{}
-SchedulerMap::~SchedulerMap ()
-{}
-
-/* Note the invariants which this function must provide:
- * - irreflexibility: f (x,x) is false)
- * - antisymmetry: f(x,y) = !f(y,x)
- * - transitivity: f(x,y) and f(y,z) => f(x,z)
- */
-bool
-SchedulerMap::EventKeyCompare::operator () (struct EventKey const&a, struct EventKey const&b)
-{
- if (a.m_ts < b.m_ts)
- {
- return true;
- }
- else if (a.m_ts > b.m_ts)
- {
- return false;
- }
- else if (a.m_uid < b.m_uid)
- {
- return true;
- }
- else
- {
- return false;
- }
-}
-
-
-
-void
-SchedulerMap::Insert (const EventId &id)
-{
- // acquire a single ref
- EventImpl *event = id.PeekEventImpl ();
- event->Ref ();
- Scheduler::EventKey key;
- key.m_ts = id.GetTs ();
- key.m_uid = id.GetUid ();
- std::pair<EventMapI,bool> result;
- result = m_list.insert (std::make_pair (key, event));
- NS_ASSERT (result.second);
-}
-
-bool
-SchedulerMap::IsEmpty (void) const
-{
- return m_list.empty ();
-}
-
-EventId
-SchedulerMap::PeekNext (void) const
-{
- EventMapCI i = m_list.begin ();
- NS_ASSERT (i != m_list.end ());
-
- return EventId (i->second, i->first.m_ts, i->first.m_uid);
-}
-EventId
-SchedulerMap::RemoveNext (void)
-{
- EventMapI i = m_list.begin ();
- std::pair<Scheduler::EventKey, EventImpl*> next = *i;
- m_list.erase (i);
- return EventId (Ptr<EventImpl> (next.second, false), next.first.m_ts, next.first.m_uid);
-}
-
-bool
-SchedulerMap::Remove (const EventId &id)
-{
- Scheduler::EventKey key;
- key.m_ts = id.GetTs ();
- key.m_uid = id.GetUid ();
- EventMapI i = m_list.find (key);
- NS_ASSERT (i->second == id.PeekEventImpl ());
- // release single ref.
- i->second->Unref ();
- m_list.erase (i);
- return true;
-}
-
-}; // namespace ns3
--- a/src/simulator/scheduler-map.h Tue Apr 15 09:41:58 2008 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,61 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2006 INRIA
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License version 2 as
- * published by the Free Software Foundation;
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
- */
-
-#ifndef SCHEDULER_MAP_H
-#define SCHEDULER_MAP_H
-
-#include "scheduler.h"
-#include <stdint.h>
-#include <map>
-#include <utility>
-
-namespace ns3 {
-
-class EventImpl;
-
-class SchedulerMap : public Scheduler {
-public:
- SchedulerMap ();
- virtual ~SchedulerMap ();
-
- virtual void Insert (const EventId &id);
- virtual bool IsEmpty (void) const;
- virtual EventId PeekNext (void) const;
- virtual EventId RemoveNext (void);
- virtual bool Remove (const EventId &ev);
-private:
-
- class EventKeyCompare {
- public:
- bool operator () (struct EventKey const&a, struct EventKey const&b);
- };
-
- typedef std::map<Scheduler::EventKey, EventImpl*, SchedulerMap::EventKeyCompare> EventMap;
- typedef std::map<Scheduler::EventKey, EventImpl*, SchedulerMap::EventKeyCompare>::iterator EventMapI;
- typedef std::map<Scheduler::EventKey, EventImpl*, SchedulerMap::EventKeyCompare>::const_iterator EventMapCI;
-
-
- EventMap m_list;
-};
-
-}; // namespace ns3
-
-
-#endif /* SCHEDULER_MAP_H */
--- a/src/simulator/simulator.cc Tue Apr 15 09:41:58 2008 -0700
+++ b/src/simulator/simulator.cc Tue Apr 15 10:09:42 2008 -0700
@@ -393,9 +393,7 @@
}; // namespace ns3
-#include "scheduler-list.h"
-#include "scheduler-heap.h"
-#include "scheduler-map.h"
+#include "map-scheduler.h"
namespace ns3 {
@@ -418,7 +416,7 @@
if (m_priv == 0)
{
m_priv = CreateObject<SimulatorPrivate> ();
- Ptr<Scheduler> scheduler = CreateObject<SchedulerMap> ();
+ Ptr<Scheduler> scheduler = CreateObject<MapScheduler> ();
m_priv->SetScheduler (scheduler);
}
TRACE_S ("priv " << m_priv);
@@ -564,6 +562,8 @@
#include "ns3/test.h"
#include "ns3/ptr.h"
+#include "list-scheduler.h"
+#include "heap-scheduler.h"
namespace ns3 {
@@ -934,19 +934,19 @@
bool result = true;
Simulator::Destroy ();
- Simulator::SetScheduler (CreateObject<SchedulerList> ());
+ Simulator::SetScheduler (CreateObject<ListScheduler> ());
if (!RunOneTest ())
{
result = false;
}
Simulator::Destroy ();
- Simulator::SetScheduler (CreateObject<SchedulerHeap> ());
+ Simulator::SetScheduler (CreateObject<HeapScheduler> ());
if (!RunOneTest ())
{
result = false;
}
Simulator::Destroy ();
- Simulator::SetScheduler (CreateObject<SchedulerMap> ());
+ Simulator::SetScheduler (CreateObject<MapScheduler> ());
if (!RunOneTest ())
{
result = false;
--- a/src/simulator/wscript Tue Apr 15 09:41:58 2008 -0700
+++ b/src/simulator/wscript Tue Apr 15 10:09:42 2008 -0700
@@ -53,9 +53,9 @@
'time.cc',
'event-id.cc',
'scheduler.cc',
- 'scheduler-list.cc',
- 'scheduler-heap.cc',
- 'scheduler-map.cc',
+ 'list-scheduler.cc',
+ 'map-scheduler.cc',
+ 'heap-scheduler.cc',
'event-impl.cc',
'simulator.cc',
'timer.cc',
@@ -71,9 +71,9 @@
'event-impl.h',
'simulator.h',
'scheduler.h',
- 'scheduler-list.h',
- 'scheduler-map.h',
- 'scheduler-heap.h',
+ 'list-scheduler.h',
+ 'map-scheduler.h',
+ 'heap-scheduler.h',
'simulation-singleton.h',
'timer.h',
'timer-impl.h',
--- a/utils/bench-simulator.cc Tue Apr 15 09:41:58 2008 -0700
+++ b/utils/bench-simulator.cc Tue Apr 15 10:09:42 2008 -0700
@@ -18,11 +18,8 @@
* Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
*/
-#include "ns3/simulator.h"
-#include "ns3/scheduler-list.h"
-#include "ns3/scheduler-map.h"
-#include "ns3/scheduler-heap.h"
-#include "ns3/system-wall-clock-ms.h"
+#include "ns3/simulator-module.h"
+#include "ns3/core-module.h"
#include <iostream>
#include <fstream>
#include <vector>
@@ -161,15 +158,15 @@
{
if (strcmp ("--list", argv[0]) == 0)
{
- Simulator::SetScheduler (CreateObject<SchedulerList> ());
+ Simulator::SetScheduler (CreateObject<ListScheduler> ());
}
else if (strcmp ("--heap", argv[0]) == 0)
{
- Simulator::SetScheduler (CreateObject<SchedulerHeap> ());
+ Simulator::SetScheduler (CreateObject<HeapScheduler> ());
}
else if (strcmp ("--map", argv[0]) == 0)
{
- Simulator::SetScheduler (CreateObject<SchedulerMap> ());
+ Simulator::SetScheduler (CreateObject<MapScheduler> ());
}
else if (strcmp ("--debug", argv[0]) == 0)
{
--- a/utils/replay-simulation.cc Tue Apr 15 09:41:58 2008 -0700
+++ b/utils/replay-simulation.cc Tue Apr 15 10:09:42 2008 -0700
@@ -18,12 +18,8 @@
* Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
*/
-#include "ns3/simulator.h"
-#include "ns3/scheduler-list.h"
-#include "ns3/scheduler-map.h"
-#include "ns3/scheduler-heap.h"
-#include "ns3/nstime.h"
-#include "ns3/system-wall-clock-ms.h"
+#include "ns3/simulator-module.h"
+#include "ns3/core-module.h"
#include <vector>
#include <deque>
#include <fstream>
@@ -317,15 +313,15 @@
{
if (is_map)
{
- Simulator::SetScheduler (CreateObject<SchedulerMap> ());
+ Simulator::SetScheduler (CreateObject<MapScheduler> ());
}
else if (is_list)
{
- Simulator::SetScheduler (CreateObject<SchedulerList> ());
+ Simulator::SetScheduler (CreateObject<ListScheduler> ());
}
else if (is_heap)
{
- Simulator::SetScheduler (CreateObject<SchedulerHeap> ());
+ Simulator::SetScheduler (CreateObject<HeapScheduler> ());
}
log.Run ();
Simulator::Destroy ();