A Discrete-Event Network Simulator
API
Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
ns3::CalendarScheduler Class Reference

a calendar queue event scheduler More...

#include "calendar-scheduler.h"

+ Inheritance diagram for ns3::CalendarScheduler:

Public Member Functions

 CalendarScheduler ()
 Constructor. More...
 
virtual ~CalendarScheduler ()
 Destructor. More...
 
virtual void Insert (const Scheduler::Event &ev)
 Insert a new Event in the schedule. More...
 
virtual bool IsEmpty (void) const
 Test if the schedule is empty. More...
 
virtual Scheduler::Event PeekNext (void) const
 Get a pointer to the next event. More...
 
virtual void Remove (const Scheduler::Event &ev)
 Remove a specific event from the event list. More...
 
virtual Scheduler::Event RemoveNext (void)
 Remove the earliest event from the event list. More...
 
- Public Member Functions inherited from ns3::Scheduler
virtual ~Scheduler ()=0
 Destructor. More...
 
- Public Member Functions inherited from ns3::Object
 Object ()
 Constructor. More...
 
virtual ~Object ()
 Destructor. More...
 
void AggregateObject (Ptr< Object > other)
 Aggregate two Objects together. More...
 
void Dispose (void)
 Dispose of this Object. More...
 
AggregateIterator GetAggregateIterator (void) const
 Get an iterator to the Objects aggregated to this one. More...
 
virtual TypeId GetInstanceTypeId (void) const
 Get the most derived TypeId for this Object. More...
 
template<typename T >
Ptr< T > GetObject (void) const
 Get a pointer to the requested aggregated Object. More...
 
template<typename T >
Ptr< T > GetObject (TypeId tid) const
 Get a pointer to the requested aggregated Object by TypeId. More...
 
void Initialize (void)
 Invoke DoInitialize on all Objects aggregated to this one. More...
 
bool IsInitialized (void) const
 Check if the object has been initialized. More...
 
- Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
 SimpleRefCount ()
 Default 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 operator. 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
 Get the value of an attribute, raising fatal errors if unsuccessful. More...
 
bool GetAttributeFailSafe (std::string name, AttributeValue &value) const
 Get the value of an attribute without raising erros. More...
 
void SetAttribute (std::string name, const AttributeValue &value)
 Set a single attribute, raising fatal errors if unsuccessful. More...
 
bool SetAttributeFailSafe (std::string name, const AttributeValue &value)
 Set a single attribute without raising errors. More...
 
bool TraceConnect (std::string name, std::string context, const CallbackBase &cb)
 Connect a TraceSource to a Callback with a context. More...
 
bool TraceConnectWithoutContext (std::string name, const CallbackBase &cb)
 Connect a TraceSource to a Callback without a context. More...
 
bool TraceDisconnect (std::string name, std::string context, const CallbackBase &cb)
 Disconnect from a TraceSource a Callback previously connected with a context. More...
 
bool TraceDisconnectWithoutContext (std::string name, const CallbackBase &cb)
 Disconnect from a TraceSource a Callback previously connected without a context. More...
 

Static Public Member Functions

static TypeId GetTypeId (void)
 Register this type. More...
 
- Static Public Member Functions inherited from ns3::Scheduler
static TypeId GetTypeId (void)
 Register this type. More...
 
- Static Public Member Functions inherited from ns3::Object
static TypeId GetTypeId (void)
 Register this type. More...
 
- Static Public Member Functions inherited from ns3::ObjectBase
static TypeId GetTypeId (void)
 Get the type ID. More...
 

Private Types

typedef std::list< Scheduler::EventBucket
 Calendar bucket type: a list of Events. More...
 

Private Member Functions

uint64_t CalculateNewWidth (void)
 Compute the new bucket size, based on up to the first 25 entries. More...
 
void DoInsert (const Scheduler::Event &ev)
 Insert a new event in to the correct bucket. More...
 
Scheduler::Event DoRemoveNext (void)
 Remove the earliest event. More...
 
void DoResize (uint32_t newSize, uint64_t newWidth)
 Resize the number of buckets and width. More...
 
uint32_t Hash (uint64_t key) const
 Hash the dimensionless time to a bucket. More...
 
void Init (uint32_t nBuckets, uint64_t width, uint64_t startPrio)
 Initialize the calendar queue. More...
 
void PrintInfo (void)
 Print the configuration and bucket size distribution. More...
 
void Resize (uint32_t newSize)
 Resize to a new number of buckets, with automatically computed width. More...
 
void ResizeDown (void)
 Halve the number of buckets if necessary. More...
 
void ResizeUp (void)
 Double the number of buckets if necessary. More...
 

Private Attributes

Bucketm_buckets
 Array of buckets. More...
 
uint64_t m_bucketTop
 Priority at the top of the bucket from which last event was dequeued. More...
 
uint32_t m_lastBucket
 Bucket index from which the last event was dequeued. More...
 
uint64_t m_lastPrio
 The priority of the last event removed. More...
 
uint32_t m_nBuckets
 Number of buckets in the array. More...
 
uint32_t m_qSize
 Number of events in queue. More...
 
uint64_t m_width
 Duration of a bucket, in dimensionless time units. More...
 

Additional Inherited Members

- Protected Member Functions inherited from ns3::Object
 Object (const Object &o)
 Copy an Object. More...
 
virtual void DoDispose (void)
 Destructor implementation. More...
 
virtual void DoInitialize (void)
 Initialize() implementation. More...
 
virtual void NotifyNewAggregate (void)
 Notify all Objects aggregated to this one of a new Object being aggregated. More...
 
- Protected Member Functions inherited from ns3::ObjectBase
void ConstructSelf (const AttributeConstructionList &attributes)
 Complete construction of ObjectBase; invoked by derived classes. More...
 
virtual void NotifyConstructionCompleted (void)
 Notifier called once the ObjectBase is fully constructed. More...
 

Detailed Description

a calendar queue event scheduler


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.
Size of this type is 88 bytes (on a 64-bit architecture).

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

Member Typedef Documentation

◆ Bucket

Calendar bucket type: a list of Events.

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

Constructor & Destructor Documentation

◆ CalendarScheduler()

ns3::CalendarScheduler::CalendarScheduler ( )

Constructor.

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

References Init(), m_qSize, and NS_LOG_FUNCTION.

◆ ~CalendarScheduler()

ns3::CalendarScheduler::~CalendarScheduler ( )
virtual

Destructor.

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

References m_buckets, and NS_LOG_FUNCTION.

Member Function Documentation

◆ CalculateNewWidth()

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

Compute the new bucket size, based on up to the first 25 entries.

Returns
The new width.

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

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

Referenced by Resize().

◆ DoInsert()

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

Insert a new event in to the correct bucket.

Parameters
[in]evThe new Event.

Definition at line 100 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().

◆ DoRemoveNext()

Scheduler::Event ns3::CalendarScheduler::DoRemoveNext ( void  )
private

◆ DoResize()

void ns3::CalendarScheduler::DoResize ( uint32_t  newSize,
uint64_t  newWidth 
)
private

Resize the number of buckets and width.

Parameters
[in]newSizeThe number of buckets.
[in]newWidthThe size of the new buckets.

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

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

Referenced by Resize().

◆ GetTypeId()

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

Register this type.

Returns
The object TypeId.

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

References ns3::TypeId::SetParent().

◆ Hash()

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

Hash the dimensionless time to a bucket.

Parameters
[in]keyThe dimensionless time.
Returns
The bucket index.

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

References m_nBuckets, m_width, and NS_LOG_FUNCTION.

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

◆ Init()

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

Initialize the calendar queue.

Parameters
[in]nBucketsThe number of buckets.
[in]widthThe bucket size, in dimensionless time units.
[in]startPrioThe starting time.

Definition at line 65 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().

◆ Insert()

void ns3::CalendarScheduler::Insert ( const Scheduler::Event ev)
virtual

Insert a new Event in the schedule.

Parameters
[in]evEvent to store in the event list

Implements ns3::Scheduler.

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

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

◆ IsEmpty()

bool ns3::CalendarScheduler::IsEmpty ( void  ) const
virtual

Test if the schedule is empty.

Returns
true if the event list is empty and false otherwise.

Implements ns3::Scheduler.

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

References m_qSize, and NS_LOG_FUNCTION.

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

◆ PeekNext()

Scheduler::Event ns3::CalendarScheduler::PeekNext ( void  ) const
virtual

Get a pointer to the next event.

This method cannot be invoked if the list is empty.

Returns
A pointer to the next earliest event. The caller takes ownership of the returned pointer.

Implements ns3::Scheduler.

Definition at line 135 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.

◆ PrintInfo()

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

Print the configuration and bucket size distribution.

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

References m_buckets, m_nBuckets, m_width, and NS_LOG_FUNCTION.

◆ Remove()

void ns3::CalendarScheduler::Remove ( const Scheduler::Event ev)
virtual

Remove a specific event from the event list.

This method cannot be invoked if the list is empty.

Parameters
[in]evThe event to remove

Implements ns3::Scheduler.

Definition at line 232 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().

◆ RemoveNext()

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

Remove the earliest event from the event list.

This method cannot be invoked if the list is empty.

Returns
The Event.

Implements ns3::Scheduler.

Definition at line 217 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().

◆ Resize()

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

Resize to a new number of buckets, with automatically computed width.

Parameters
[in]newSizeThe new number of buckets.

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

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

Referenced by ResizeDown(), and ResizeUp().

◆ ResizeDown()

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

Halve the number of buckets if necessary.

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

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

Referenced by Remove(), and RemoveNext().

◆ ResizeUp()

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

Double the number of buckets if necessary.

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

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

Referenced by Insert().

Member Data Documentation

◆ m_buckets

Bucket* ns3::CalendarScheduler::m_buckets
private

Array of buckets.

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

Referenced by DoInsert(), DoRemoveNext(), DoResize(), Init(), PeekNext(), PrintInfo(), Remove(), and ~CalendarScheduler().

◆ m_bucketTop

uint64_t ns3::CalendarScheduler::m_bucketTop
private

Priority at the top of the bucket from which last event was dequeued.

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

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

◆ m_lastBucket

uint32_t ns3::CalendarScheduler::m_lastBucket
private

Bucket index from which the last event was dequeued.

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

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

◆ m_lastPrio

uint64_t ns3::CalendarScheduler::m_lastPrio
private

The priority of the last event removed.

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

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

◆ m_nBuckets

uint32_t ns3::CalendarScheduler::m_nBuckets
private

Number of buckets in the array.

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

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

◆ m_qSize

uint32_t ns3::CalendarScheduler::m_qSize
private

Number of events in queue.

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

Referenced by CalculateNewWidth(), CalendarScheduler(), Insert(), IsEmpty(), Remove(), RemoveNext(), ResizeDown(), and ResizeUp().

◆ m_width

uint64_t ns3::CalendarScheduler::m_width
private

Duration of a bucket, in dimensionless time units.

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

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


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