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)
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)
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	Start (void)
Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
	SimpleRefCount ()
	SimpleRefCount (const SimpleRefCount &o)
uint32_t	GetReferenceCount (void) const
SimpleRefCount &	operator= (const SimpleRefCount &o)
void	Ref (void) const
void	Unref (void) const
Public Member Functions inherited from ns3::ObjectBase
virtual	~ObjectBase ()
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)
	This method returns the TypeId associated to ns3::CalendarScheduler.

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
Bucket *	m_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)
virtual void	DoStart (void)
virtual void	NotifyNewAggregate (void)

Detailed Description

a calendar queue event scheduler

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.

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

Member Typedef Documentation

typedef std::list<Scheduler::Event> ns3::CalendarScheduler::Bucket

private

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

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 254 of file calendar-scheduler.cc.

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

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 89 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

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

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

Referenced by CalculateNewWidth(), and RemoveNext().

Here is the call graph for this function:

Here is the caller graph for this function:

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

private

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

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

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

This method returns the TypeId associated to ns3::CalendarScheduler.

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

Reimplemented from ns3::Scheduler.

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

References ns3::TypeId::SetParent().

Referenced by ns3::SimulatorTestSuite::SimulatorTestSuite().

Here is the call graph for this function:

Here is the caller graph for this function:

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

inlineprivate

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

References m_nBuckets, and m_width.

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

ev	event to store in the event list

Implements ns3::Scheduler.

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

References DoInsert(), m_qSize, 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 117 of file calendar-scheduler.cc.

References m_qSize.

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 122 of file calendar-scheduler.cc.

References IsEmpty(), ns3::Scheduler::Event::key, m_buckets, m_bucketTop, m_lastBucket, m_nBuckets, ns3::Scheduler::EventKey::m_ts, 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, and m_width.

void ns3::CalendarScheduler::Remove ( const Event & ev )

virtual

Parameters

ev	the event to remove

This methods cannot be invoked if the list is empty.

Implements ns3::Scheduler.

Definition at line 213 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, 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 198 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 348 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 245 of file calendar-scheduler.cc.

References m_nBuckets, m_qSize, 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 236 of file calendar-scheduler.cc.

References m_nBuckets, m_qSize, 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

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

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

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

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

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

uint32_t ns3::CalendarScheduler::m_qSize

private

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

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

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:

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation