1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/simulator/heap-scheduler.cc Tue Apr 15 10:09:42 2008 -0700
1.3 @@ -0,0 +1,263 @@
1.4 +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
1.5 +/*
1.6 + * Copyright (c) 2006 INRIA
1.7 + * Copyright (c) 2005 Mathieu Lacage
1.8 + *
1.9 + * This program is free software; you can redistribute it and/or modify
1.10 + * it under the terms of the GNU General Public License version 2 as
1.11 + * published by the Free Software Foundation;
1.12 + *
1.13 + * This program is distributed in the hope that it will be useful,
1.14 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
1.15 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1.16 + * GNU General Public License for more details.
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License
1.19 + * along with this program; if not, write to the Free Software
1.20 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
1.21 + *
1.22 + * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
1.23 + *
1.24 + * This code started as a c++ translation of a java-based code written in 2005
1.25 + * to implement a heap sort. Which explains the "Copyright Mathieu Lacage" at the
1.26 + * top of this file.
1.27 + *
1.28 + * What is smart about this code ?
1.29 + * - it does not use the index 0 in the array to avoid having to convert
1.30 + * C-style array indexes (which start at zero) and heap-style indexes
1.31 + * (which start at 1). This is why _all_ indexes start at 1, and that
1.32 + * the index of the root is 1.
1.33 + * - It uses a slightly non-standard while loop for top-down heapify
1.34 + * to move one if statement out of the loop.
1.35 + */
1.36 +
1.37 +#include "heap-scheduler.h"
1.38 +#include "event-impl.h"
1.39 +#include "ns3/assert.h"
1.40 +
1.41 +#include <string>
1.42 +#define noTRACE_HEAP 1
1.43 +
1.44 +#ifdef TRACE_HEAP
1.45 +#include <iostream>
1.46 +# define TRACE(x) \
1.47 +std::cout << "HEAP TRACE " << x << std::endl;
1.48 +#else /* TRACE_HEAP */
1.49 +# define TRACE(format,...)
1.50 +#endif /* TRACE_HEAP */
1.51 +
1.52 +
1.53 +
1.54 +
1.55 +namespace ns3 {
1.56 +
1.57 +
1.58 +HeapScheduler::HeapScheduler ()
1.59 +{
1.60 + // we purposedly waste an item at the start of
1.61 + // the array to make sure the indexes in the
1.62 + // array start at one.
1.63 + Scheduler::EventKey emptyKey = {0,0};
1.64 + m_heap.push_back (std::make_pair (static_cast<EventImpl *>(0), emptyKey));
1.65 +}
1.66 +
1.67 +HeapScheduler::~HeapScheduler ()
1.68 +{}
1.69 +
1.70 +uint32_t
1.71 +HeapScheduler::Parent (uint32_t id) const
1.72 +{
1.73 + return id / 2;
1.74 +}
1.75 +uint32_t
1.76 +HeapScheduler::Sibling (uint32_t id) const
1.77 +{
1.78 + return id + 1;
1.79 +}
1.80 +uint32_t
1.81 +HeapScheduler::LeftChild (uint32_t id) const
1.82 +{
1.83 + return id * 2;
1.84 +}
1.85 +uint32_t
1.86 +HeapScheduler::RightChild (uint32_t id) const
1.87 +{
1.88 + return id * 2 + 1;
1.89 +}
1.90 +
1.91 +uint32_t
1.92 +HeapScheduler::Root (void) const
1.93 +{
1.94 + return 1;
1.95 +}
1.96 +
1.97 +bool
1.98 +HeapScheduler::IsRoot (uint32_t id) const
1.99 +{
1.100 + return (id == Root ())?true:false;
1.101 +}
1.102 +
1.103 +uint32_t
1.104 +HeapScheduler::Last (void) const
1.105 +{
1.106 + return m_heap.size () - 1;
1.107 +}
1.108 +
1.109 +
1.110 +bool
1.111 +HeapScheduler::IsBottom (uint32_t id) const
1.112 +{
1.113 + return (id >= m_heap.size ())?true:false;
1.114 +}
1.115 +
1.116 +void
1.117 +HeapScheduler::Exch (uint32_t a, uint32_t b)
1.118 +{
1.119 + NS_ASSERT (b < m_heap.size () && a < m_heap.size ());
1.120 + TRACE ("Exch " << a << ", " << b);
1.121 + std::pair<EventImpl*, Scheduler::EventKey> tmp (m_heap[a]);
1.122 + m_heap[a] = m_heap[b];
1.123 + m_heap[b] = tmp;
1.124 +}
1.125 +
1.126 +bool
1.127 +HeapScheduler::IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
1.128 +{
1.129 + if (a->m_ts < b->m_ts)
1.130 + {
1.131 + return true;
1.132 + }
1.133 + else if (a->m_ts > b->m_ts)
1.134 + {
1.135 + return false;
1.136 + }
1.137 + else if (a->m_uid < b->m_uid)
1.138 + {
1.139 + return true;
1.140 + }
1.141 + else
1.142 + {
1.143 + return false;
1.144 + }
1.145 +}
1.146 +
1.147 +bool
1.148 +HeapScheduler::IsLessStrictly (uint32_t a, uint32_t b) const
1.149 +{
1.150 + return IsLowerStrictly (&m_heap[a].second, &m_heap[b].second);
1.151 +}
1.152 +
1.153 +uint32_t
1.154 +HeapScheduler::Smallest (uint32_t a, uint32_t b) const
1.155 +{
1.156 + return IsLessStrictly (a,b)?a:b;
1.157 +}
1.158 +
1.159 +bool
1.160 +HeapScheduler::IsEmpty (void) const
1.161 +{
1.162 + return (m_heap.size () == 1)?true:false;
1.163 +}
1.164 +
1.165 +void
1.166 +HeapScheduler::BottomUp (void)
1.167 +{
1.168 + uint32_t index = Last ();
1.169 + while (!IsRoot (index) &&
1.170 + IsLessStrictly (index, Parent (index)))
1.171 + {
1.172 + Exch(index, Parent (index));
1.173 + index = Parent (index);
1.174 + }
1.175 +}
1.176 +
1.177 +void
1.178 +HeapScheduler::TopDown (uint32_t start)
1.179 +{
1.180 + uint32_t index = start;
1.181 + uint32_t right = RightChild (index);
1.182 + while (!IsBottom (right))
1.183 + {
1.184 + uint32_t left = LeftChild (index);
1.185 + uint32_t tmp = Smallest (left, right);
1.186 + if (IsLessStrictly (index, tmp))
1.187 + {
1.188 + return;
1.189 + }
1.190 + Exch (index, tmp);
1.191 + index = tmp;
1.192 + right = RightChild (index);
1.193 + }
1.194 + if (IsBottom (index))
1.195 + {
1.196 + return;
1.197 + }
1.198 + NS_ASSERT (!IsBottom (index));
1.199 + uint32_t left = LeftChild (index);
1.200 + if (IsBottom (left))
1.201 + {
1.202 + return;
1.203 + }
1.204 + if (IsLessStrictly (index, left))
1.205 + {
1.206 + return;
1.207 + }
1.208 + Exch (index, left);
1.209 +}
1.210 +
1.211 +
1.212 +void
1.213 +HeapScheduler::Insert (const EventId &id)
1.214 +{
1.215 + // acquire single ref
1.216 + EventImpl *event = id.PeekEventImpl ();
1.217 + event->Ref ();
1.218 + Scheduler::EventKey key;
1.219 + key.m_ts = id.GetTs ();
1.220 + key.m_uid = id.GetUid ();
1.221 + m_heap.push_back (std::make_pair (event, key));
1.222 + BottomUp ();
1.223 +}
1.224 +
1.225 +EventId
1.226 +HeapScheduler::PeekNext (void) const
1.227 +{
1.228 + std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
1.229 + return EventId (next.first, next.second.m_ts, next.second.m_uid);
1.230 +}
1.231 +EventId
1.232 +HeapScheduler::RemoveNext (void)
1.233 +{
1.234 + std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
1.235 + Exch (Root (), Last ());
1.236 + m_heap.pop_back ();
1.237 + TopDown (Root ());
1.238 + return EventId (Ptr<EventImpl> (next.first, false), next.second.m_ts, next.second.m_uid);
1.239 +}
1.240 +
1.241 +
1.242 +bool
1.243 +HeapScheduler::Remove (const EventId &id)
1.244 +{
1.245 + uint32_t uid = id.GetUid ();
1.246 + for (uint32_t i = 1; i < m_heap.size (); i++)
1.247 + {
1.248 + if (uid == m_heap[i].second.m_uid)
1.249 + {
1.250 + NS_ASSERT (m_heap[i].first == id.PeekEventImpl ());
1.251 + std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[i];
1.252 + // release single ref
1.253 + next.first->Unref ();
1.254 + Exch (i, Last ());
1.255 + m_heap.pop_back ();
1.256 + TopDown (i);
1.257 + return true;
1.258 + }
1.259 + }
1.260 + NS_ASSERT (false);
1.261 + // quiet compiler
1.262 + return false;
1.263 +}
1.264 +
1.265 +}; // namespace ns3
1.266 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/simulator/heap-scheduler.h Tue Apr 15 10:09:42 2008 -0700
2.3 @@ -0,0 +1,69 @@
2.4 +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2.5 +/*
2.6 + * Copyright (c) 2005 INRIA
2.7 + *
2.8 + * This program is free software; you can redistribute it and/or modify
2.9 + * it under the terms of the GNU General Public License version 2 as
2.10 + * published by the Free Software Foundation;
2.11 + *
2.12 + * This program is distributed in the hope that it will be useful,
2.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
2.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2.15 + * GNU General Public License for more details.
2.16 + *
2.17 + * You should have received a copy of the GNU General Public License
2.18 + * along with this program; if not, write to the Free Software
2.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
2.20 + *
2.21 + * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
2.22 + */
2.23 +
2.24 +#ifndef SCHEDULER_HEAP_H
2.25 +#define SCHEDULER_HEAP_H
2.26 +
2.27 +#include "scheduler.h"
2.28 +#include <stdint.h>
2.29 +#include <vector>
2.30 +
2.31 +namespace ns3 {
2.32 +
2.33 +class EventHolder;
2.34 +
2.35 +class HeapScheduler : public Scheduler {
2.36 +public:
2.37 + HeapScheduler ();
2.38 + virtual ~HeapScheduler ();
2.39 +
2.40 + virtual void Insert (const EventId &id);
2.41 + virtual bool IsEmpty (void) const;
2.42 + virtual EventId PeekNext (void) const;
2.43 + virtual EventId RemoveNext (void);
2.44 + virtual bool Remove (const EventId &ev);
2.45 +
2.46 +private:
2.47 + typedef std::vector<std::pair<EventImpl *, Scheduler::EventKey> > BinaryHeap;
2.48 +
2.49 + inline uint32_t Parent (uint32_t id) const;
2.50 + uint32_t Sibling (uint32_t id) const;
2.51 + inline uint32_t LeftChild (uint32_t id) const;
2.52 + inline uint32_t RightChild (uint32_t id) const;
2.53 + inline uint32_t Root (void) const;
2.54 + /* Return the position in the array of the last element included in it. */
2.55 + uint32_t Last (void) const;
2.56 + inline bool IsRoot (uint32_t id) const;
2.57 + inline bool IsBottom (uint32_t id) const;
2.58 + inline bool IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
2.59 + inline bool IsLessStrictly (uint32_t a, uint32_t b) const;
2.60 + inline uint32_t Smallest (uint32_t a, uint32_t b) const;
2.61 +
2.62 + inline void Exch (uint32_t a, uint32_t b);
2.63 + void BottomUp (void);
2.64 + void TopDown (uint32_t start);
2.65 +
2.66 + BinaryHeap m_heap;
2.67 +};
2.68 +
2.69 +}; // namespace ns3
2.70 +
2.71 +
2.72 +#endif /* SCHEDULER_HEAP_H */
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/simulator/list-scheduler.cc Tue Apr 15 10:09:42 2008 -0700
3.3 @@ -0,0 +1,110 @@
3.4 +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
3.5 +/*
3.6 + * Copyright (c) 2005 INRIA
3.7 + *
3.8 + * This program is free software; you can redistribute it and/or modify
3.9 + * it under the terms of the GNU General Public License version 2 as
3.10 + * published by the Free Software Foundation;
3.11 + *
3.12 + * This program is distributed in the hope that it will be useful,
3.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
3.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3.15 + * GNU General Public License for more details.
3.16 + *
3.17 + * You should have received a copy of the GNU General Public License
3.18 + * along with this program; if not, write to the Free Software
3.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
3.20 + *
3.21 + * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
3.22 + */
3.23 +
3.24 +#include "list-scheduler.h"
3.25 +#include "event-impl.h"
3.26 +#include <utility>
3.27 +#include <string>
3.28 +#include "ns3/assert.h"
3.29 +
3.30 +namespace ns3 {
3.31 +
3.32 +
3.33 +ListScheduler::ListScheduler ()
3.34 +{}
3.35 +ListScheduler::~ListScheduler ()
3.36 +{}
3.37 +
3.38 +bool
3.39 +ListScheduler::IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
3.40 +{
3.41 + if (a->m_ts < b->m_ts)
3.42 + {
3.43 + return true;
3.44 + }
3.45 + else if (a->m_ts == b->m_ts &&
3.46 + a->m_uid < b->m_uid)
3.47 + {
3.48 + return true;
3.49 + }
3.50 + else
3.51 + {
3.52 + return false;
3.53 + }
3.54 +}
3.55 +
3.56 +void
3.57 +ListScheduler::Insert (const EventId &id)
3.58 +{
3.59 + Scheduler::EventKey key;
3.60 + // acquire refcount on EventImpl
3.61 + EventImpl *event = id.PeekEventImpl ();
3.62 + event->Ref ();
3.63 + key.m_ts = id.GetTs ();
3.64 + key.m_uid = id.GetUid ();
3.65 + for (EventsI i = m_events.begin (); i != m_events.end (); i++)
3.66 + {
3.67 + if (IsLower (&key, &i->second))
3.68 + {
3.69 + m_events.insert (i, std::make_pair (event, key));
3.70 + return;
3.71 + }
3.72 + }
3.73 + m_events.push_back (std::make_pair (event, key));
3.74 +}
3.75 +bool
3.76 +ListScheduler::IsEmpty (void) const
3.77 +{
3.78 + return m_events.empty ();
3.79 +}
3.80 +EventId
3.81 +ListScheduler::PeekNext (void) const
3.82 +{
3.83 + std::pair<EventImpl *, EventKey> next = m_events.front ();
3.84 + return EventId (next.first, next.second.m_ts, next.second.m_uid);
3.85 +}
3.86 +
3.87 +EventId
3.88 +ListScheduler::RemoveNext (void)
3.89 +{
3.90 + std::pair<EventImpl *, EventKey> next = m_events.front ();
3.91 + m_events.pop_front ();
3.92 + return EventId (Ptr<EventImpl> (next.first,false), next.second.m_ts, next.second.m_uid);
3.93 +}
3.94 +
3.95 +bool
3.96 +ListScheduler::Remove (const EventId &id)
3.97 +{
3.98 + for (EventsI i = m_events.begin (); i != m_events.end (); i++)
3.99 + {
3.100 + if (i->second.m_uid == id.GetUid ())
3.101 + {
3.102 + NS_ASSERT (id.PeekEventImpl () == i->first);
3.103 + // release single acquire ref.
3.104 + i->first->Unref ();
3.105 + m_events.erase (i);
3.106 + return true;
3.107 + }
3.108 + }
3.109 + NS_ASSERT (false);
3.110 + return false;
3.111 +}
3.112 +
3.113 +}; // namespace ns3
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/simulator/list-scheduler.h Tue Apr 15 10:09:42 2008 -0700
4.3 @@ -0,0 +1,56 @@
4.4 +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
4.5 +/*
4.6 + * Copyright (c) 2005 INRIA
4.7 + *
4.8 + * This program is free software; you can redistribute it and/or modify
4.9 + * it under the terms of the GNU General Public License version 2 as
4.10 + * published by the Free Software Foundation;
4.11 + *
4.12 + * This program is distributed in the hope that it will be useful,
4.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
4.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
4.15 + * GNU General Public License for more details.
4.16 + *
4.17 + * You should have received a copy of the GNU General Public License
4.18 + * along with this program; if not, write to the Free Software
4.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
4.20 + *
4.21 + * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
4.22 + */
4.23 +
4.24 +#ifndef SCHEDULER_LIST_H
4.25 +#define SCHEDULER_LIST_H
4.26 +
4.27 +#include "scheduler.h"
4.28 +#include "event-id.h"
4.29 +#include <list>
4.30 +#include <utility>
4.31 +#include <stdint.h>
4.32 +
4.33 +namespace ns3 {
4.34 +
4.35 +class EventImpl;
4.36 +
4.37 +class ListScheduler : public Scheduler {
4.38 + public:
4.39 + ListScheduler ();
4.40 + virtual ~ListScheduler ();
4.41 +
4.42 + virtual void Insert (const EventId &id);
4.43 + virtual bool IsEmpty (void) const;
4.44 + virtual EventId PeekNext (void) const;
4.45 + virtual EventId RemoveNext (void);
4.46 + virtual bool Remove (const EventId &ev);
4.47 +
4.48 + private:
4.49 + inline bool IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
4.50 +
4.51 + typedef std::list<std::pair<EventImpl*, EventKey> > Events;
4.52 + typedef std::list<std::pair<EventImpl*, EventKey> >::iterator EventsI;
4.53 + Events m_events;
4.54 +};
4.55 +
4.56 +}; // namespace ns3
4.57 +
4.58 +
4.59 +#endif /* SCHEDULER_LIST_H */
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/simulator/map-scheduler.cc Tue Apr 15 10:09:42 2008 -0700
5.3 @@ -0,0 +1,124 @@
5.4 +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
5.5 +/*
5.6 + * Copyright (c) 2006 INRIA
5.7 + *
5.8 + * This program is free software; you can redistribute it and/or modify
5.9 + * it under the terms of the GNU General Public License version 2 as
5.10 + * published by the Free Software Foundation;
5.11 + *
5.12 + * This program is distributed in the hope that it will be useful,
5.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
5.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
5.15 + * GNU General Public License for more details.
5.16 + *
5.17 + * You should have received a copy of the GNU General Public License
5.18 + * along with this program; if not, write to the Free Software
5.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
5.20 + *
5.21 + * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
5.22 + * The idea to use a std c++ map came from GTNetS
5.23 + */
5.24 +
5.25 +#include "map-scheduler.h"
5.26 +#include "event-impl.h"
5.27 +#include "ns3/assert.h"
5.28 +#include <string>
5.29 +
5.30 +#define noTRACE_MAP 1
5.31 +
5.32 +#ifdef TRACE_MAP
5.33 +#include <iostream>
5.34 +# define TRACE(x) \
5.35 +std::cout << "MAP TRACE " << x << std::endl;
5.36 +#else /* TRACE_MAP */
5.37 +# define TRACE(format,...)
5.38 +#endif /* TRACE_MAP */
5.39 +
5.40 +
5.41 +namespace ns3 {
5.42 +
5.43 +MapScheduler::MapScheduler ()
5.44 +{}
5.45 +MapScheduler::~MapScheduler ()
5.46 +{}
5.47 +
5.48 +/* Note the invariants which this function must provide:
5.49 + * - irreflexibility: f (x,x) is false)
5.50 + * - antisymmetry: f(x,y) = !f(y,x)
5.51 + * - transitivity: f(x,y) and f(y,z) => f(x,z)
5.52 + */
5.53 +bool
5.54 +MapScheduler::EventKeyCompare::operator () (struct EventKey const&a, struct EventKey const&b)
5.55 +{
5.56 + if (a.m_ts < b.m_ts)
5.57 + {
5.58 + return true;
5.59 + }
5.60 + else if (a.m_ts > b.m_ts)
5.61 + {
5.62 + return false;
5.63 + }
5.64 + else if (a.m_uid < b.m_uid)
5.65 + {
5.66 + return true;
5.67 + }
5.68 + else
5.69 + {
5.70 + return false;
5.71 + }
5.72 +}
5.73 +
5.74 +
5.75 +
5.76 +void
5.77 +MapScheduler::Insert (const EventId &id)
5.78 +{
5.79 + // acquire a single ref
5.80 + EventImpl *event = id.PeekEventImpl ();
5.81 + event->Ref ();
5.82 + Scheduler::EventKey key;
5.83 + key.m_ts = id.GetTs ();
5.84 + key.m_uid = id.GetUid ();
5.85 + std::pair<EventMapI,bool> result;
5.86 + result = m_list.insert (std::make_pair (key, event));
5.87 + NS_ASSERT (result.second);
5.88 +}
5.89 +
5.90 +bool
5.91 +MapScheduler::IsEmpty (void) const
5.92 +{
5.93 + return m_list.empty ();
5.94 +}
5.95 +
5.96 +EventId
5.97 +MapScheduler::PeekNext (void) const
5.98 +{
5.99 + EventMapCI i = m_list.begin ();
5.100 + NS_ASSERT (i != m_list.end ());
5.101 +
5.102 + return EventId (i->second, i->first.m_ts, i->first.m_uid);
5.103 +}
5.104 +EventId
5.105 +MapScheduler::RemoveNext (void)
5.106 +{
5.107 + EventMapI i = m_list.begin ();
5.108 + std::pair<Scheduler::EventKey, EventImpl*> next = *i;
5.109 + m_list.erase (i);
5.110 + return EventId (Ptr<EventImpl> (next.second, false), next.first.m_ts, next.first.m_uid);
5.111 +}
5.112 +
5.113 +bool
5.114 +MapScheduler::Remove (const EventId &id)
5.115 +{
5.116 + Scheduler::EventKey key;
5.117 + key.m_ts = id.GetTs ();
5.118 + key.m_uid = id.GetUid ();
5.119 + EventMapI i = m_list.find (key);
5.120 + NS_ASSERT (i->second == id.PeekEventImpl ());
5.121 + // release single ref.
5.122 + i->second->Unref ();
5.123 + m_list.erase (i);
5.124 + return true;
5.125 +}
5.126 +
5.127 +}; // namespace ns3
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
6.2 +++ b/src/simulator/map-scheduler.h Tue Apr 15 10:09:42 2008 -0700
6.3 @@ -0,0 +1,61 @@
6.4 +/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
6.5 +/*
6.6 + * Copyright (c) 2006 INRIA
6.7 + *
6.8 + * This program is free software; you can redistribute it and/or modify
6.9 + * it under the terms of the GNU General Public License version 2 as
6.10 + * published by the Free Software Foundation;
6.11 + *
6.12 + * This program is distributed in the hope that it will be useful,
6.13 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
6.14 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
6.15 + * GNU General Public License for more details.
6.16 + *
6.17 + * You should have received a copy of the GNU General Public License
6.18 + * along with this program; if not, write to the Free Software
6.19 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
6.20 + *
6.21 + * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
6.22 + */
6.23 +
6.24 +#ifndef SCHEDULER_MAP_H
6.25 +#define SCHEDULER_MAP_H
6.26 +
6.27 +#include "scheduler.h"
6.28 +#include <stdint.h>
6.29 +#include <map>
6.30 +#include <utility>
6.31 +
6.32 +namespace ns3 {
6.33 +
6.34 +class EventImpl;
6.35 +
6.36 +class MapScheduler : public Scheduler {
6.37 +public:
6.38 + MapScheduler ();
6.39 + virtual ~MapScheduler ();
6.40 +
6.41 + virtual void Insert (const EventId &id);
6.42 + virtual bool IsEmpty (void) const;
6.43 + virtual EventId PeekNext (void) const;
6.44 + virtual EventId RemoveNext (void);
6.45 + virtual bool Remove (const EventId &ev);
6.46 +private:
6.47 +
6.48 + class EventKeyCompare {
6.49 + public:
6.50 + bool operator () (struct EventKey const&a, struct EventKey const&b);
6.51 + };
6.52 +
6.53 + typedef std::map<Scheduler::EventKey, EventImpl*, MapScheduler::EventKeyCompare> EventMap;
6.54 + typedef std::map<Scheduler::EventKey, EventImpl*, MapScheduler::EventKeyCompare>::iterator EventMapI;
6.55 + typedef std::map<Scheduler::EventKey, EventImpl*, MapScheduler::EventKeyCompare>::const_iterator EventMapCI;
6.56 +
6.57 +
6.58 + EventMap m_list;
6.59 +};
6.60 +
6.61 +}; // namespace ns3
6.62 +
6.63 +
6.64 +#endif /* SCHEDULER_MAP_H */
7.1 --- a/src/simulator/scheduler-heap.cc Tue Apr 15 09:41:58 2008 -0700
7.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
7.3 @@ -1,263 +0,0 @@
7.4 -/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
7.5 -/*
7.6 - * Copyright (c) 2006 INRIA
7.7 - * Copyright (c) 2005 Mathieu Lacage
7.8 - *
7.9 - * This program is free software; you can redistribute it and/or modify
7.10 - * it under the terms of the GNU General Public License version 2 as
7.11 - * published by the Free Software Foundation;
7.12 - *
7.13 - * This program is distributed in the hope that it will be useful,
7.14 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
7.15 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
7.16 - * GNU General Public License for more details.
7.17 - *
7.18 - * You should have received a copy of the GNU General Public License
7.19 - * along with this program; if not, write to the Free Software
7.20 - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
7.21 - *
7.22 - * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
7.23 - *
7.24 - * This code started as a c++ translation of a java-based code written in 2005
7.25 - * to implement a heap sort. Which explains the "Copyright Mathieu Lacage" at the
7.26 - * top of this file.
7.27 - *
7.28 - * What is smart about this code ?
7.29 - * - it does not use the index 0 in the array to avoid having to convert
7.30 - * C-style array indexes (which start at zero) and heap-style indexes
7.31 - * (which start at 1). This is why _all_ indexes start at 1, and that
7.32 - * the index of the root is 1.
7.33 - * - It uses a slightly non-standard while loop for top-down heapify
7.34 - * to move one if statement out of the loop.
7.35 - */
7.36 -
7.37 -#include "scheduler-heap.h"
7.38 -#include "event-impl.h"
7.39 -#include "ns3/assert.h"
7.40 -
7.41 -#include <string>
7.42 -#define noTRACE_HEAP 1
7.43 -
7.44 -#ifdef TRACE_HEAP
7.45 -#include <iostream>
7.46 -# define TRACE(x) \
7.47 -std::cout << "HEAP TRACE " << x << std::endl;
7.48 -#else /* TRACE_HEAP */
7.49 -# define TRACE(format,...)
7.50 -#endif /* TRACE_HEAP */
7.51 -
7.52 -
7.53 -
7.54 -
7.55 -namespace ns3 {
7.56 -
7.57 -
7.58 -SchedulerHeap::SchedulerHeap ()
7.59 -{
7.60 - // we purposedly waste an item at the start of
7.61 - // the array to make sure the indexes in the
7.62 - // array start at one.
7.63 - Scheduler::EventKey emptyKey = {0,0};
7.64 - m_heap.push_back (std::make_pair (static_cast<EventImpl *>(0), emptyKey));
7.65 -}
7.66 -
7.67 -SchedulerHeap::~SchedulerHeap ()
7.68 -{}
7.69 -
7.70 -uint32_t
7.71 -SchedulerHeap::Parent (uint32_t id) const
7.72 -{
7.73 - return id / 2;
7.74 -}
7.75 -uint32_t
7.76 -SchedulerHeap::Sibling (uint32_t id) const
7.77 -{
7.78 - return id + 1;
7.79 -}
7.80 -uint32_t
7.81 -SchedulerHeap::LeftChild (uint32_t id) const
7.82 -{
7.83 - return id * 2;
7.84 -}
7.85 -uint32_t
7.86 -SchedulerHeap::RightChild (uint32_t id) const
7.87 -{
7.88 - return id * 2 + 1;
7.89 -}
7.90 -
7.91 -uint32_t
7.92 -SchedulerHeap::Root (void) const
7.93 -{
7.94 - return 1;
7.95 -}
7.96 -
7.97 -bool
7.98 -SchedulerHeap::IsRoot (uint32_t id) const
7.99 -{
7.100 - return (id == Root ())?true:false;
7.101 -}
7.102 -
7.103 -uint32_t
7.104 -SchedulerHeap::Last (void) const
7.105 -{
7.106 - return m_heap.size () - 1;
7.107 -}
7.108 -
7.109 -
7.110 -bool
7.111 -SchedulerHeap::IsBottom (uint32_t id) const
7.112 -{
7.113 - return (id >= m_heap.size ())?true:false;
7.114 -}
7.115 -
7.116 -void
7.117 -SchedulerHeap::Exch (uint32_t a, uint32_t b)
7.118 -{
7.119 - NS_ASSERT (b < m_heap.size () && a < m_heap.size ());
7.120 - TRACE ("Exch " << a << ", " << b);
7.121 - std::pair<EventImpl*, Scheduler::EventKey> tmp (m_heap[a]);
7.122 - m_heap[a] = m_heap[b];
7.123 - m_heap[b] = tmp;
7.124 -}
7.125 -
7.126 -bool
7.127 -SchedulerHeap::IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
7.128 -{
7.129 - if (a->m_ts < b->m_ts)
7.130 - {
7.131 - return true;
7.132 - }
7.133 - else if (a->m_ts > b->m_ts)
7.134 - {
7.135 - return false;
7.136 - }
7.137 - else if (a->m_uid < b->m_uid)
7.138 - {
7.139 - return true;
7.140 - }
7.141 - else
7.142 - {
7.143 - return false;
7.144 - }
7.145 -}
7.146 -
7.147 -bool
7.148 -SchedulerHeap::IsLessStrictly (uint32_t a, uint32_t b) const
7.149 -{
7.150 - return IsLowerStrictly (&m_heap[a].second, &m_heap[b].second);
7.151 -}
7.152 -
7.153 -uint32_t
7.154 -SchedulerHeap::Smallest (uint32_t a, uint32_t b) const
7.155 -{
7.156 - return IsLessStrictly (a,b)?a:b;
7.157 -}
7.158 -
7.159 -bool
7.160 -SchedulerHeap::IsEmpty (void) const
7.161 -{
7.162 - return (m_heap.size () == 1)?true:false;
7.163 -}
7.164 -
7.165 -void
7.166 -SchedulerHeap::BottomUp (void)
7.167 -{
7.168 - uint32_t index = Last ();
7.169 - while (!IsRoot (index) &&
7.170 - IsLessStrictly (index, Parent (index)))
7.171 - {
7.172 - Exch(index, Parent (index));
7.173 - index = Parent (index);
7.174 - }
7.175 -}
7.176 -
7.177 -void
7.178 -SchedulerHeap::TopDown (uint32_t start)
7.179 -{
7.180 - uint32_t index = start;
7.181 - uint32_t right = RightChild (index);
7.182 - while (!IsBottom (right))
7.183 - {
7.184 - uint32_t left = LeftChild (index);
7.185 - uint32_t tmp = Smallest (left, right);
7.186 - if (IsLessStrictly (index, tmp))
7.187 - {
7.188 - return;
7.189 - }
7.190 - Exch (index, tmp);
7.191 - index = tmp;
7.192 - right = RightChild (index);
7.193 - }
7.194 - if (IsBottom (index))
7.195 - {
7.196 - return;
7.197 - }
7.198 - NS_ASSERT (!IsBottom (index));
7.199 - uint32_t left = LeftChild (index);
7.200 - if (IsBottom (left))
7.201 - {
7.202 - return;
7.203 - }
7.204 - if (IsLessStrictly (index, left))
7.205 - {
7.206 - return;
7.207 - }
7.208 - Exch (index, left);
7.209 -}
7.210 -
7.211 -
7.212 -void
7.213 -SchedulerHeap::Insert (const EventId &id)
7.214 -{
7.215 - // acquire single ref
7.216 - EventImpl *event = id.PeekEventImpl ();
7.217 - event->Ref ();
7.218 - Scheduler::EventKey key;
7.219 - key.m_ts = id.GetTs ();
7.220 - key.m_uid = id.GetUid ();
7.221 - m_heap.push_back (std::make_pair (event, key));
7.222 - BottomUp ();
7.223 -}
7.224 -
7.225 -EventId
7.226 -SchedulerHeap::PeekNext (void) const
7.227 -{
7.228 - std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
7.229 - return EventId (next.first, next.second.m_ts, next.second.m_uid);
7.230 -}
7.231 -EventId
7.232 -SchedulerHeap::RemoveNext (void)
7.233 -{
7.234 - std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[Root ()];
7.235 - Exch (Root (), Last ());
7.236 - m_heap.pop_back ();
7.237 - TopDown (Root ());
7.238 - return EventId (Ptr<EventImpl> (next.first, false), next.second.m_ts, next.second.m_uid);
7.239 -}
7.240 -
7.241 -
7.242 -bool
7.243 -SchedulerHeap::Remove (const EventId &id)
7.244 -{
7.245 - uint32_t uid = id.GetUid ();
7.246 - for (uint32_t i = 1; i < m_heap.size (); i++)
7.247 - {
7.248 - if (uid == m_heap[i].second.m_uid)
7.249 - {
7.250 - NS_ASSERT (m_heap[i].first == id.PeekEventImpl ());
7.251 - std::pair<EventImpl *,Scheduler::EventKey> next = m_heap[i];
7.252 - // release single ref
7.253 - next.first->Unref ();
7.254 - Exch (i, Last ());
7.255 - m_heap.pop_back ();
7.256 - TopDown (i);
7.257 - return true;
7.258 - }
7.259 - }
7.260 - NS_ASSERT (false);
7.261 - // quiet compiler
7.262 - return false;
7.263 -}
7.264 -
7.265 -}; // namespace ns3
7.266 -
8.1 --- a/src/simulator/scheduler-heap.h Tue Apr 15 09:41:58 2008 -0700
8.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
8.3 @@ -1,69 +0,0 @@
8.4 -/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
8.5 -/*
8.6 - * Copyright (c) 2005 INRIA
8.7 - *
8.8 - * This program is free software; you can redistribute it and/or modify
8.9 - * it under the terms of the GNU General Public License version 2 as
8.10 - * published by the Free Software Foundation;
8.11 - *
8.12 - * This program is distributed in the hope that it will be useful,
8.13 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
8.14 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
8.15 - * GNU General Public License for more details.
8.16 - *
8.17 - * You should have received a copy of the GNU General Public License
8.18 - * along with this program; if not, write to the Free Software
8.19 - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
8.20 - *
8.21 - * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
8.22 - */
8.23 -
8.24 -#ifndef SCHEDULER_HEAP_H
8.25 -#define SCHEDULER_HEAP_H
8.26 -
8.27 -#include "scheduler.h"
8.28 -#include <stdint.h>
8.29 -#include <vector>
8.30 -
8.31 -namespace ns3 {
8.32 -
8.33 -class EventHolder;
8.34 -
8.35 -class SchedulerHeap : public Scheduler {
8.36 -public:
8.37 - SchedulerHeap ();
8.38 - virtual ~SchedulerHeap ();
8.39 -
8.40 - virtual void Insert (const EventId &id);
8.41 - virtual bool IsEmpty (void) const;
8.42 - virtual EventId PeekNext (void) const;
8.43 - virtual EventId RemoveNext (void);
8.44 - virtual bool Remove (const EventId &ev);
8.45 -
8.46 -private:
8.47 - typedef std::vector<std::pair<EventImpl *, Scheduler::EventKey> > BinaryHeap;
8.48 -
8.49 - inline uint32_t Parent (uint32_t id) const;
8.50 - uint32_t Sibling (uint32_t id) const;
8.51 - inline uint32_t LeftChild (uint32_t id) const;
8.52 - inline uint32_t RightChild (uint32_t id) const;
8.53 - inline uint32_t Root (void) const;
8.54 - /* Return the position in the array of the last element included in it. */
8.55 - uint32_t Last (void) const;
8.56 - inline bool IsRoot (uint32_t id) const;
8.57 - inline bool IsBottom (uint32_t id) const;
8.58 - inline bool IsLowerStrictly (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
8.59 - inline bool IsLessStrictly (uint32_t a, uint32_t b) const;
8.60 - inline uint32_t Smallest (uint32_t a, uint32_t b) const;
8.61 -
8.62 - inline void Exch (uint32_t a, uint32_t b);
8.63 - void BottomUp (void);
8.64 - void TopDown (uint32_t start);
8.65 -
8.66 - BinaryHeap m_heap;
8.67 -};
8.68 -
8.69 -}; // namespace ns3
8.70 -
8.71 -
8.72 -#endif /* SCHEDULER_HEAP_H */
9.1 --- a/src/simulator/scheduler-list.cc Tue Apr 15 09:41:58 2008 -0700
9.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
9.3 @@ -1,110 +0,0 @@
9.4 -/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
9.5 -/*
9.6 - * Copyright (c) 2005 INRIA
9.7 - *
9.8 - * This program is free software; you can redistribute it and/or modify
9.9 - * it under the terms of the GNU General Public License version 2 as
9.10 - * published by the Free Software Foundation;
9.11 - *
9.12 - * This program is distributed in the hope that it will be useful,
9.13 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
9.14 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9.15 - * GNU General Public License for more details.
9.16 - *
9.17 - * You should have received a copy of the GNU General Public License
9.18 - * along with this program; if not, write to the Free Software
9.19 - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
9.20 - *
9.21 - * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
9.22 - */
9.23 -
9.24 -#include "scheduler-list.h"
9.25 -#include "event-impl.h"
9.26 -#include <utility>
9.27 -#include <string>
9.28 -#include "ns3/assert.h"
9.29 -
9.30 -namespace ns3 {
9.31 -
9.32 -
9.33 -SchedulerList::SchedulerList ()
9.34 -{}
9.35 -SchedulerList::~SchedulerList ()
9.36 -{}
9.37 -
9.38 -bool
9.39 -SchedulerList::IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const
9.40 -{
9.41 - if (a->m_ts < b->m_ts)
9.42 - {
9.43 - return true;
9.44 - }
9.45 - else if (a->m_ts == b->m_ts &&
9.46 - a->m_uid < b->m_uid)
9.47 - {
9.48 - return true;
9.49 - }
9.50 - else
9.51 - {
9.52 - return false;
9.53 - }
9.54 -}
9.55 -
9.56 -void
9.57 -SchedulerList::Insert (const EventId &id)
9.58 -{
9.59 - Scheduler::EventKey key;
9.60 - // acquire refcount on EventImpl
9.61 - EventImpl *event = id.PeekEventImpl ();
9.62 - event->Ref ();
9.63 - key.m_ts = id.GetTs ();
9.64 - key.m_uid = id.GetUid ();
9.65 - for (EventsI i = m_events.begin (); i != m_events.end (); i++)
9.66 - {
9.67 - if (IsLower (&key, &i->second))
9.68 - {
9.69 - m_events.insert (i, std::make_pair (event, key));
9.70 - return;
9.71 - }
9.72 - }
9.73 - m_events.push_back (std::make_pair (event, key));
9.74 -}
9.75 -bool
9.76 -SchedulerList::IsEmpty (void) const
9.77 -{
9.78 - return m_events.empty ();
9.79 -}
9.80 -EventId
9.81 -SchedulerList::PeekNext (void) const
9.82 -{
9.83 - std::pair<EventImpl *, EventKey> next = m_events.front ();
9.84 - return EventId (next.first, next.second.m_ts, next.second.m_uid);
9.85 -}
9.86 -
9.87 -EventId
9.88 -SchedulerList::RemoveNext (void)
9.89 -{
9.90 - std::pair<EventImpl *, EventKey> next = m_events.front ();
9.91 - m_events.pop_front ();
9.92 - return EventId (Ptr<EventImpl> (next.first,false), next.second.m_ts, next.second.m_uid);
9.93 -}
9.94 -
9.95 -bool
9.96 -SchedulerList::Remove (const EventId &id)
9.97 -{
9.98 - for (EventsI i = m_events.begin (); i != m_events.end (); i++)
9.99 - {
9.100 - if (i->second.m_uid == id.GetUid ())
9.101 - {
9.102 - NS_ASSERT (id.PeekEventImpl () == i->first);
9.103 - // release single acquire ref.
9.104 - i->first->Unref ();
9.105 - m_events.erase (i);
9.106 - return true;
9.107 - }
9.108 - }
9.109 - NS_ASSERT (false);
9.110 - return false;
9.111 -}
9.112 -
9.113 -}; // namespace ns3
10.1 --- a/src/simulator/scheduler-list.h Tue Apr 15 09:41:58 2008 -0700
10.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
10.3 @@ -1,56 +0,0 @@
10.4 -/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
10.5 -/*
10.6 - * Copyright (c) 2005 INRIA
10.7 - *
10.8 - * This program is free software; you can redistribute it and/or modify
10.9 - * it under the terms of the GNU General Public License version 2 as
10.10 - * published by the Free Software Foundation;
10.11 - *
10.12 - * This program is distributed in the hope that it will be useful,
10.13 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
10.14 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10.15 - * GNU General Public License for more details.
10.16 - *
10.17 - * You should have received a copy of the GNU General Public License
10.18 - * along with this program; if not, write to the Free Software
10.19 - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
10.20 - *
10.21 - * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
10.22 - */
10.23 -
10.24 -#ifndef SCHEDULER_LIST_H
10.25 -#define SCHEDULER_LIST_H
10.26 -
10.27 -#include "scheduler.h"
10.28 -#include "event-id.h"
10.29 -#include <list>
10.30 -#include <utility>
10.31 -#include <stdint.h>
10.32 -
10.33 -namespace ns3 {
10.34 -
10.35 -class EventImpl;
10.36 -
10.37 -class SchedulerList : public Scheduler {
10.38 - public:
10.39 - SchedulerList ();
10.40 - virtual ~SchedulerList ();
10.41 -
10.42 - virtual void Insert (const EventId &id);
10.43 - virtual bool IsEmpty (void) const;
10.44 - virtual EventId PeekNext (void) const;
10.45 - virtual EventId RemoveNext (void);
10.46 - virtual bool Remove (const EventId &ev);
10.47 -
10.48 - private:
10.49 - inline bool IsLower (Scheduler::EventKey const*a, Scheduler::EventKey const*b) const;
10.50 -
10.51 - typedef std::list<std::pair<EventImpl*, EventKey> > Events;
10.52 - typedef std::list<std::pair<EventImpl*, EventKey> >::iterator EventsI;
10.53 - Events m_events;
10.54 -};
10.55 -
10.56 -}; // namespace ns3
10.57 -
10.58 -
10.59 -#endif /* SCHEDULER_LIST_H */
11.1 --- a/src/simulator/scheduler-map.cc Tue Apr 15 09:41:58 2008 -0700
11.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
11.3 @@ -1,124 +0,0 @@
11.4 -/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
11.5 -/*
11.6 - * Copyright (c) 2006 INRIA
11.7 - *
11.8 - * This program is free software; you can redistribute it and/or modify
11.9 - * it under the terms of the GNU General Public License version 2 as
11.10 - * published by the Free Software Foundation;
11.11 - *
11.12 - * This program is distributed in the hope that it will be useful,
11.13 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
11.14 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11.15 - * GNU General Public License for more details.
11.16 - *
11.17 - * You should have received a copy of the GNU General Public License
11.18 - * along with this program; if not, write to the Free Software
11.19 - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
11.20 - *
11.21 - * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
11.22 - * The idea to use a std c++ map came from GTNetS
11.23 - */
11.24 -
11.25 -#include "scheduler-map.h"
11.26 -#include "event-impl.h"
11.27 -#include "ns3/assert.h"
11.28 -#include <string>
11.29 -
11.30 -#define noTRACE_MAP 1
11.31 -
11.32 -#ifdef TRACE_MAP
11.33 -#include <iostream>
11.34 -# define TRACE(x) \
11.35 -std::cout << "MAP TRACE " << x << std::endl;
11.36 -#else /* TRACE_MAP */
11.37 -# define TRACE(format,...)
11.38 -#endif /* TRACE_MAP */
11.39 -
11.40 -
11.41 -namespace ns3 {
11.42 -
11.43 -SchedulerMap::SchedulerMap ()
11.44 -{}
11.45 -SchedulerMap::~SchedulerMap ()
11.46 -{}
11.47 -
11.48 -/* Note the invariants which this function must provide:
11.49 - * - irreflexibility: f (x,x) is false)
11.50 - * - antisymmetry: f(x,y) = !f(y,x)
11.51 - * - transitivity: f(x,y) and f(y,z) => f(x,z)
11.52 - */
11.53 -bool
11.54 -SchedulerMap::EventKeyCompare::operator () (struct EventKey const&a, struct EventKey const&b)
11.55 -{
11.56 - if (a.m_ts < b.m_ts)
11.57 - {
11.58 - return true;
11.59 - }
11.60 - else if (a.m_ts > b.m_ts)
11.61 - {
11.62 - return false;
11.63 - }
11.64 - else if (a.m_uid < b.m_uid)
11.65 - {
11.66 - return true;
11.67 - }
11.68 - else
11.69 - {
11.70 - return false;
11.71 - }
11.72 -}
11.73 -
11.74 -
11.75 -
11.76 -void
11.77 -SchedulerMap::Insert (const EventId &id)
11.78 -{
11.79 - // acquire a single ref
11.80 - EventImpl *event = id.PeekEventImpl ();
11.81 - event->Ref ();
11.82 - Scheduler::EventKey key;
11.83 - key.m_ts = id.GetTs ();
11.84 - key.m_uid = id.GetUid ();
11.85 - std::pair<EventMapI,bool> result;
11.86 - result = m_list.insert (std::make_pair (key, event));
11.87 - NS_ASSERT (result.second);
11.88 -}
11.89 -
11.90 -bool
11.91 -SchedulerMap::IsEmpty (void) const
11.92 -{
11.93 - return m_list.empty ();
11.94 -}
11.95 -
11.96 -EventId
11.97 -SchedulerMap::PeekNext (void) const
11.98 -{
11.99 - EventMapCI i = m_list.begin ();
11.100 - NS_ASSERT (i != m_list.end ());
11.101 -
11.102 - return EventId (i->second, i->first.m_ts, i->first.m_uid);
11.103 -}
11.104 -EventId
11.105 -SchedulerMap::RemoveNext (void)
11.106 -{
11.107 - EventMapI i = m_list.begin ();
11.108 - std::pair<Scheduler::EventKey, EventImpl*> next = *i;
11.109 - m_list.erase (i);
11.110 - return EventId (Ptr<EventImpl> (next.second, false), next.first.m_ts, next.first.m_uid);
11.111 -}
11.112 -
11.113 -bool
11.114 -SchedulerMap::Remove (const EventId &id)
11.115 -{
11.116 - Scheduler::EventKey key;
11.117 - key.m_ts = id.GetTs ();
11.118 - key.m_uid = id.GetUid ();
11.119 - EventMapI i = m_list.find (key);
11.120 - NS_ASSERT (i->second == id.PeekEventImpl ());
11.121 - // release single ref.
11.122 - i->second->Unref ();
11.123 - m_list.erase (i);
11.124 - return true;
11.125 -}
11.126 -
11.127 -}; // namespace ns3
12.1 --- a/src/simulator/scheduler-map.h Tue Apr 15 09:41:58 2008 -0700
12.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
12.3 @@ -1,61 +0,0 @@
12.4 -/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
12.5 -/*
12.6 - * Copyright (c) 2006 INRIA
12.7 - *
12.8 - * This program is free software; you can redistribute it and/or modify
12.9 - * it under the terms of the GNU General Public License version 2 as
12.10 - * published by the Free Software Foundation;
12.11 - *
12.12 - * This program is distributed in the hope that it will be useful,
12.13 - * but WITHOUT ANY WARRANTY; without even the implied warranty of
12.14 - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12.15 - * GNU General Public License for more details.
12.16 - *
12.17 - * You should have received a copy of the GNU General Public License
12.18 - * along with this program; if not, write to the Free Software
12.19 - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
12.20 - *
12.21 - * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
12.22 - */
12.23 -
12.24 -#ifndef SCHEDULER_MAP_H
12.25 -#define SCHEDULER_MAP_H
12.26 -
12.27 -#include "scheduler.h"
12.28 -#include <stdint.h>
12.29 -#include <map>
12.30 -#include <utility>
12.31 -
12.32 -namespace ns3 {
12.33 -
12.34 -class EventImpl;
12.35 -
12.36 -class SchedulerMap : public Scheduler {
12.37 -public:
12.38 - SchedulerMap ();
12.39 - virtual ~SchedulerMap ();
12.40 -
12.41 - virtual void Insert (const EventId &id);
12.42 - virtual bool IsEmpty (void) const;
12.43 - virtual EventId PeekNext (void) const;
12.44 - virtual EventId RemoveNext (void);
12.45 - virtual bool Remove (const EventId &ev);
12.46 -private:
12.47 -
12.48 - class EventKeyCompare {
12.49 - public:
12.50 - bool operator () (struct EventKey const&a, struct EventKey const&b);
12.51 - };
12.52 -
12.53 - typedef std::map<Scheduler::EventKey, EventImpl*, SchedulerMap::EventKeyCompare> EventMap;
12.54 - typedef std::map<Scheduler::EventKey, EventImpl*, SchedulerMap::EventKeyCompare>::iterator EventMapI;
12.55 - typedef std::map<Scheduler::EventKey, EventImpl*, SchedulerMap::EventKeyCompare>::const_iterator EventMapCI;
12.56 -
12.57 -
12.58 - EventMap m_list;
12.59 -};
12.60 -
12.61 -}; // namespace ns3
12.62 -
12.63 -
12.64 -#endif /* SCHEDULER_MAP_H */
13.1 --- a/src/simulator/simulator.cc Tue Apr 15 09:41:58 2008 -0700
13.2 +++ b/src/simulator/simulator.cc Tue Apr 15 10:09:42 2008 -0700
13.3 @@ -393,9 +393,7 @@
13.4 }; // namespace ns3
13.5
13.6
13.7 -#include "scheduler-list.h"
13.8 -#include "scheduler-heap.h"
13.9 -#include "scheduler-map.h"
13.10 +#include "map-scheduler.h"
13.11
13.12
13.13 namespace ns3 {
13.14 @@ -418,7 +416,7 @@
13.15 if (m_priv == 0)
13.16 {
13.17 m_priv = CreateObject<SimulatorPrivate> ();
13.18 - Ptr<Scheduler> scheduler = CreateObject<SchedulerMap> ();
13.19 + Ptr<Scheduler> scheduler = CreateObject<MapScheduler> ();
13.20 m_priv->SetScheduler (scheduler);
13.21 }
13.22 TRACE_S ("priv " << m_priv);
13.23 @@ -564,6 +562,8 @@
13.24
13.25 #include "ns3/test.h"
13.26 #include "ns3/ptr.h"
13.27 +#include "list-scheduler.h"
13.28 +#include "heap-scheduler.h"
13.29
13.30 namespace ns3 {
13.31
13.32 @@ -934,19 +934,19 @@
13.33 bool result = true;
13.34
13.35 Simulator::Destroy ();
13.36 - Simulator::SetScheduler (CreateObject<SchedulerList> ());
13.37 + Simulator::SetScheduler (CreateObject<ListScheduler> ());
13.38 if (!RunOneTest ())
13.39 {
13.40 result = false;
13.41 }
13.42 Simulator::Destroy ();
13.43 - Simulator::SetScheduler (CreateObject<SchedulerHeap> ());
13.44 + Simulator::SetScheduler (CreateObject<HeapScheduler> ());
13.45 if (!RunOneTest ())
13.46 {
13.47 result = false;
13.48 }
13.49 Simulator::Destroy ();
13.50 - Simulator::SetScheduler (CreateObject<SchedulerMap> ());
13.51 + Simulator::SetScheduler (CreateObject<MapScheduler> ());
13.52 if (!RunOneTest ())
13.53 {
13.54 result = false;
14.1 --- a/src/simulator/wscript Tue Apr 15 09:41:58 2008 -0700
14.2 +++ b/src/simulator/wscript Tue Apr 15 10:09:42 2008 -0700
14.3 @@ -53,9 +53,9 @@
14.4 'time.cc',
14.5 'event-id.cc',
14.6 'scheduler.cc',
14.7 - 'scheduler-list.cc',
14.8 - 'scheduler-heap.cc',
14.9 - 'scheduler-map.cc',
14.10 + 'list-scheduler.cc',
14.11 + 'map-scheduler.cc',
14.12 + 'heap-scheduler.cc',
14.13 'event-impl.cc',
14.14 'simulator.cc',
14.15 'timer.cc',
14.16 @@ -71,9 +71,9 @@
14.17 'event-impl.h',
14.18 'simulator.h',
14.19 'scheduler.h',
14.20 - 'scheduler-list.h',
14.21 - 'scheduler-map.h',
14.22 - 'scheduler-heap.h',
14.23 + 'list-scheduler.h',
14.24 + 'map-scheduler.h',
14.25 + 'heap-scheduler.h',
14.26 'simulation-singleton.h',
14.27 'timer.h',
14.28 'timer-impl.h',
15.1 --- a/utils/bench-simulator.cc Tue Apr 15 09:41:58 2008 -0700
15.2 +++ b/utils/bench-simulator.cc Tue Apr 15 10:09:42 2008 -0700
15.3 @@ -18,11 +18,8 @@
15.4 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
15.5 */
15.6
15.7 -#include "ns3/simulator.h"
15.8 -#include "ns3/scheduler-list.h"
15.9 -#include "ns3/scheduler-map.h"
15.10 -#include "ns3/scheduler-heap.h"
15.11 -#include "ns3/system-wall-clock-ms.h"
15.12 +#include "ns3/simulator-module.h"
15.13 +#include "ns3/core-module.h"
15.14 #include <iostream>
15.15 #include <fstream>
15.16 #include <vector>
15.17 @@ -161,15 +158,15 @@
15.18 {
15.19 if (strcmp ("--list", argv[0]) == 0)
15.20 {
15.21 - Simulator::SetScheduler (CreateObject<SchedulerList> ());
15.22 + Simulator::SetScheduler (CreateObject<ListScheduler> ());
15.23 }
15.24 else if (strcmp ("--heap", argv[0]) == 0)
15.25 {
15.26 - Simulator::SetScheduler (CreateObject<SchedulerHeap> ());
15.27 + Simulator::SetScheduler (CreateObject<HeapScheduler> ());
15.28 }
15.29 else if (strcmp ("--map", argv[0]) == 0)
15.30 {
15.31 - Simulator::SetScheduler (CreateObject<SchedulerMap> ());
15.32 + Simulator::SetScheduler (CreateObject<MapScheduler> ());
15.33 }
15.34 else if (strcmp ("--debug", argv[0]) == 0)
15.35 {
16.1 --- a/utils/replay-simulation.cc Tue Apr 15 09:41:58 2008 -0700
16.2 +++ b/utils/replay-simulation.cc Tue Apr 15 10:09:42 2008 -0700
16.3 @@ -18,12 +18,8 @@
16.4 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
16.5 */
16.6
16.7 -#include "ns3/simulator.h"
16.8 -#include "ns3/scheduler-list.h"
16.9 -#include "ns3/scheduler-map.h"
16.10 -#include "ns3/scheduler-heap.h"
16.11 -#include "ns3/nstime.h"
16.12 -#include "ns3/system-wall-clock-ms.h"
16.13 +#include "ns3/simulator-module.h"
16.14 +#include "ns3/core-module.h"
16.15 #include <vector>
16.16 #include <deque>
16.17 #include <fstream>
16.18 @@ -317,15 +313,15 @@
16.19 {
16.20 if (is_map)
16.21 {
16.22 - Simulator::SetScheduler (CreateObject<SchedulerMap> ());
16.23 + Simulator::SetScheduler (CreateObject<MapScheduler> ());
16.24 }
16.25 else if (is_list)
16.26 {
16.27 - Simulator::SetScheduler (CreateObject<SchedulerList> ());
16.28 + Simulator::SetScheduler (CreateObject<ListScheduler> ());
16.29 }
16.30 else if (is_heap)
16.31 {
16.32 - Simulator::SetScheduler (CreateObject<SchedulerHeap> ());
16.33 + Simulator::SetScheduler (CreateObject<HeapScheduler> ());
16.34 }
16.35 log.Run ();
16.36 Simulator::Destroy ();