A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
ns3::CalendarScheduler Class Reference

a calendar queue event scheduler More...

#include <calendar-scheduler.h>

+ Inheritance diagram for ns3::CalendarScheduler:
+ Collaboration diagram for ns3::CalendarScheduler:

Public Member Functions

 CalendarScheduler ()
 
virtual ~CalendarScheduler ()
 
virtual void Insert (const Event &ev)
 
virtual bool IsEmpty (void) const
 
virtual Event PeekNext (void) const
 
virtual void Remove (const Event &ev)
 
virtual Event RemoveNext (void)
 This method cannot be invoked if the list is empty. More...
 
- Public Member Functions inherited from ns3::Scheduler
virtual ~Scheduler ()=0
 
- Public Member Functions inherited from ns3::Object
 Object ()
 
virtual ~Object ()
 
void AggregateObject (Ptr< Object > other)
 
void Dispose (void)
 Run the DoDispose methods of this object and all the objects aggregated to it. More...
 
AggregateIterator GetAggregateIterator (void) const
 
virtual TypeId GetInstanceTypeId (void) const
 
template<typename T >
Ptr< T > GetObject (void) const
 
template<typename T >
Ptr< T > GetObject (TypeId tid) const
 
void Initialize (void)
 This method calls the virtual DoInitialize method on all the objects aggregated to this object. More...
 
- Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
 SimpleRefCount ()
 Constructor. More...
 
 SimpleRefCount (const SimpleRefCount &o)
 Copy constructor. More...
 
uint32_t GetReferenceCount (void) const
 Get the reference count of the object. More...
 
SimpleRefCountoperator= (const SimpleRefCount &o)
 Assignment. More...
 
void Ref (void) const
 Increment the reference count. More...
 
void Unref (void) const
 Decrement the reference count. More...
 
- Public Member Functions inherited from ns3::ObjectBase
virtual ~ObjectBase ()
 Virtual destructor. More...
 
void GetAttribute (std::string name, AttributeValue &value) const
 
bool GetAttributeFailSafe (std::string name, AttributeValue &attribute) const
 
void SetAttribute (std::string name, const AttributeValue &value)
 
bool SetAttributeFailSafe (std::string name, const AttributeValue &value)
 
bool TraceConnect (std::string name, std::string context, const CallbackBase &cb)
 
bool TraceConnectWithoutContext (std::string name, const CallbackBase &cb)
 
bool TraceDisconnect (std::string name, std::string context, const CallbackBase &cb)
 
bool TraceDisconnectWithoutContext (std::string name, const CallbackBase &cb)
 

Static Public Member Functions

static TypeId GetTypeId (void)
 
- Static Public Member Functions inherited from ns3::Scheduler
static TypeId GetTypeId (void)
 
- Static Public Member Functions inherited from ns3::Object
static TypeId GetTypeId (void)
 Register this type. More...
 
- Static Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
static void Cleanup (void)
 Noop. More...
 
- Static Public Member Functions inherited from ns3::ObjectBase
static TypeId GetTypeId (void)
 Get the type ID. More...
 

Private Types

typedef std::list
< Scheduler::Event
Bucket
 

Private Member Functions

uint32_t CalculateNewWidth (void)
 
void DoInsert (const Event &ev)
 
Scheduler::Event DoRemoveNext (void)
 
void DoResize (uint32_t newSize, uint32_t newWidth)
 
uint32_t Hash (uint64_t key) const
 
void Init (uint32_t nBuckets, uint64_t width, uint64_t startPrio)
 
void PrintInfo (void)
 
void Resize (uint32_t newSize)
 
void ResizeDown (void)
 
void ResizeUp (void)
 

Private Attributes

Bucketm_buckets
 
uint64_t m_bucketTop
 
uint32_t m_lastBucket
 
uint64_t m_lastPrio
 
uint32_t m_nBuckets
 
uint32_t m_qSize
 
uint64_t m_width
 

Additional Inherited Members

- Protected Member Functions inherited from ns3::Object
 Object (const Object &o)
 
virtual void DoDispose (void)
 This method is called by Object::Dispose or by the object's destructor, whichever comes first. More...
 
virtual void DoInitialize (void)
 This method is called only once by Object::Initialize. More...
 
virtual void NotifyNewAggregate (void)
 This method is invoked whenever two sets of objects are aggregated together. More...
 
- Protected Member Functions inherited from ns3::ObjectBase
void ConstructSelf (const AttributeConstructionList &attributes)
 
virtual void NotifyConstructionCompleted (void)
 This method is invoked once all member attributes have been initialized. More...
 

Detailed Description

a calendar queue event scheduler

Doxygen introspection did not find any typical Config paths.

This event scheduler is a direct implementation of the algorithm known as a calendar queue. first published in 1988 in "Calendar Queues: A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem" by Randy Brown. There are many refinements published later but this class implements the original algorithm (to the best of my knowledge).

Note: This queue is much slower than I expected (much slower than the std::map queue) and this seems to be because the original resizing policy is horribly bad. This is most likely the reason why there have been so many variations published which all slightly tweak the resizing heuristics to obtain a better distribution of events across buckets.


No Attributes are defined for this type.
No TraceSources are defined for this type.

Definition at line 47 of file calendar-scheduler.h.

Member Typedef Documentation

Constructor & Destructor Documentation

ns3::CalendarScheduler::CalendarScheduler ( )

Definition at line 45 of file calendar-scheduler.cc.

References Init(), m_qSize, and NS_LOG_FUNCTION.

+ Here is the call graph for this function:

ns3::CalendarScheduler::~CalendarScheduler ( )
virtual

Definition at line 51 of file calendar-scheduler.cc.

References m_buckets, and NS_LOG_FUNCTION.

Member Function Documentation

uint32_t ns3::CalendarScheduler::CalculateNewWidth ( void  )
private

Definition at line 271 of file calendar-scheduler.cc.

References DoInsert(), DoRemoveNext(), m_bucketTop, m_lastBucket, m_lastPrio, m_qSize, and NS_LOG_FUNCTION.

Referenced by Resize().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ns3::CalendarScheduler::DoInsert ( const Event ev)
private

Definition at line 93 of file calendar-scheduler.cc.

References Hash(), ns3::Scheduler::Event::key, m_buckets, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, NS_LOG_FUNCTION, and NS_LOG_LOGIC.

Referenced by CalculateNewWidth(), DoResize(), and Insert().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Scheduler::Event ns3::CalendarScheduler::DoRemoveNext ( void  )
private
void ns3::CalendarScheduler::DoResize ( uint32_t  newSize,
uint32_t  newWidth 
)
private

Definition at line 350 of file calendar-scheduler.cc.

References DoInsert(), Init(), m_buckets, m_lastPrio, m_nBuckets, and NS_LOG_FUNCTION.

Referenced by Resize().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

TypeId ns3::CalendarScheduler::GetTypeId ( void  )
static

Definition at line 36 of file calendar-scheduler.cc.

References ns3::TypeId::SetParent().

+ Here is the call graph for this function:

uint32_t ns3::CalendarScheduler::Hash ( uint64_t  key) const
inlineprivate

Definition at line 84 of file calendar-scheduler.cc.

References m_nBuckets, m_width, and NS_LOG_FUNCTION.

Referenced by DoInsert(), DoRemoveNext(), Init(), and Remove().

+ Here is the caller graph for this function:

void ns3::CalendarScheduler::Init ( uint32_t  nBuckets,
uint64_t  width,
uint64_t  startPrio 
)
private

Definition at line 58 of file calendar-scheduler.cc.

References Hash(), m_buckets, m_bucketTop, m_lastBucket, m_lastPrio, m_nBuckets, m_width, and NS_LOG_FUNCTION.

Referenced by CalendarScheduler(), and DoResize().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ns3::CalendarScheduler::Insert ( const Event ev)
virtual
Parameters
evevent to store in the event list

Implements ns3::Scheduler.

Definition at line 114 of file calendar-scheduler.cc.

References DoInsert(), m_qSize, NS_LOG_FUNCTION, and ResizeUp().

+ Here is the call graph for this function:

bool ns3::CalendarScheduler::IsEmpty ( void  ) const
virtual
Returns
true if the event list is empty and false otherwise.

Implements ns3::Scheduler.

Definition at line 122 of file calendar-scheduler.cc.

References m_qSize, and NS_LOG_FUNCTION.

Referenced by DoRemoveNext(), PeekNext(), Remove(), and RemoveNext().

+ Here is the caller graph for this function:

Scheduler::Event ns3::CalendarScheduler::PeekNext ( void  ) const
virtual
Returns
a pointer to the next earliest event. The caller takes ownership of the returned pointer.

This method cannot be invoked if the list is empty.

Implements ns3::Scheduler.

Definition at line 128 of file calendar-scheduler.cc.

References ns3::Scheduler::Event::impl, IsEmpty(), ns3::Scheduler::Event::key, m_buckets, m_bucketTop, ns3::Scheduler::EventKey::m_context, m_lastBucket, m_nBuckets, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, m_width, NS_ASSERT, and NS_LOG_FUNCTION.

+ Here is the call graph for this function:

void ns3::CalendarScheduler::PrintInfo ( void  )
private

Definition at line 71 of file calendar-scheduler.cc.

References m_buckets, m_nBuckets, m_width, and NS_LOG_FUNCTION.

void ns3::CalendarScheduler::Remove ( const Event ev)
virtual
Parameters
evthe event to remove

This methods cannot be invoked if the list is empty.

Implements ns3::Scheduler.

Definition at line 225 of file calendar-scheduler.cc.

References Hash(), ns3::Scheduler::Event::impl, IsEmpty(), ns3::Scheduler::Event::key, m_buckets, m_qSize, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, NS_ASSERT, NS_LOG_FUNCTION, and ResizeDown().

+ Here is the call graph for this function:

Scheduler::Event ns3::CalendarScheduler::RemoveNext ( void  )
virtual

This method cannot be invoked if the list is empty.

Remove the next earliest event from the event list.

Implements ns3::Scheduler.

Definition at line 210 of file calendar-scheduler.cc.

References DoRemoveNext(), IsEmpty(), ns3::Scheduler::Event::key, m_bucketTop, m_lastBucket, m_qSize, ns3::Scheduler::EventKey::m_ts, ns3::Scheduler::EventKey::m_uid, NS_ASSERT, NS_LOG_FUNCTION, NS_LOG_LOGIC, and ResizeDown().

+ Here is the call graph for this function:

void ns3::CalendarScheduler::Resize ( uint32_t  newSize)
private

Definition at line 369 of file calendar-scheduler.cc.

References CalculateNewWidth(), DoResize(), and NS_LOG_FUNCTION.

Referenced by ResizeDown(), and ResizeUp().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ns3::CalendarScheduler::ResizeDown ( void  )
private

Definition at line 260 of file calendar-scheduler.cc.

References m_nBuckets, m_qSize, NS_LOG_FUNCTION, and Resize().

Referenced by Remove(), and RemoveNext().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ns3::CalendarScheduler::ResizeUp ( void  )
private

Definition at line 249 of file calendar-scheduler.cc.

References m_nBuckets, m_qSize, NS_LOG_FUNCTION, and Resize().

Referenced by Insert().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

Bucket* ns3::CalendarScheduler::m_buckets
private
uint64_t ns3::CalendarScheduler::m_bucketTop
private

Definition at line 84 of file calendar-scheduler.h.

Referenced by CalculateNewWidth(), DoRemoveNext(), Init(), PeekNext(), and RemoveNext().

uint32_t ns3::CalendarScheduler::m_lastBucket
private

Definition at line 82 of file calendar-scheduler.h.

Referenced by CalculateNewWidth(), DoRemoveNext(), Init(), PeekNext(), and RemoveNext().

uint64_t ns3::CalendarScheduler::m_lastPrio
private

Definition at line 86 of file calendar-scheduler.h.

Referenced by CalculateNewWidth(), DoRemoveNext(), DoResize(), and Init().

uint32_t ns3::CalendarScheduler::m_nBuckets
private
uint32_t ns3::CalendarScheduler::m_qSize
private
uint64_t ns3::CalendarScheduler::m_width
private

Definition at line 80 of file calendar-scheduler.h.

Referenced by DoRemoveNext(), Hash(), Init(), PeekNext(), and PrintInfo().


The documentation for this class was generated from the following files: