a calendar queue event scheduler More...
#include <calendar-scheduler.h>
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... | |
![]() | |
virtual | ~Scheduler ()=0 |
![]() | |
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... | |
![]() | |
SimpleRefCount () | |
Constructor. More... | |
SimpleRefCount (const SimpleRefCount &o) | |
Copy constructor. More... | |
uint32_t | GetReferenceCount (void) const |
Get the reference count of the object. More... | |
SimpleRefCount & | operator= (const SimpleRefCount &o) |
Assignment. More... | |
void | Ref (void) const |
Increment the reference count. More... | |
void | Unref (void) const |
Decrement the reference count. More... | |
![]() | |
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 TypeId | GetTypeId (void) |
![]() | |
static TypeId | GetTypeId (void) |
Register this type. More... | |
![]() | |
static void | Cleanup (void) |
Noop. More... | |
![]() | |
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 | |
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 | |
![]() | |
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... | |
![]() | |
void | ConstructSelf (const AttributeConstructionList &attributes) |
virtual void | NotifyConstructionCompleted (void) |
This method is invoked once all member attributes have been initialized. More... | |
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.
|
private |
Definition at line 75 of file calendar-scheduler.h.
ns3::CalendarScheduler::CalendarScheduler | ( | ) |
Definition at line 47 of file calendar-scheduler.cc.
References Init(), m_qSize, and NS_LOG_FUNCTION.
|
virtual |
Definition at line 53 of file calendar-scheduler.cc.
References m_buckets, and NS_LOG_FUNCTION.
|
private |
Definition at line 273 of file calendar-scheduler.cc.
References DoInsert(), DoRemoveNext(), m_bucketTop, m_lastBucket, m_lastPrio, m_qSize, and NS_LOG_FUNCTION.
Referenced by Resize().
|
private |
Definition at line 95 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().
|
private |
Definition at line 165 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, NS_ASSERT, and NS_LOG_FUNCTION.
Referenced by CalculateNewWidth(), and RemoveNext().
|
private |
Definition at line 352 of file calendar-scheduler.cc.
References DoInsert(), Init(), m_buckets, m_lastPrio, m_nBuckets, and NS_LOG_FUNCTION.
Referenced by Resize().
|
static |
Definition at line 38 of file calendar-scheduler.cc.
References ns3::TypeId::SetParent().
|
inlineprivate |
Definition at line 86 of file calendar-scheduler.cc.
References m_nBuckets, m_width, and NS_LOG_FUNCTION.
Referenced by DoInsert(), DoRemoveNext(), Init(), and Remove().
|
private |
Definition at line 60 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().
|
virtual |
ev | event to store in the event list |
Implements ns3::Scheduler.
Definition at line 116 of file calendar-scheduler.cc.
References DoInsert(), m_qSize, NS_LOG_FUNCTION, and ResizeUp().
|
virtual |
Implements ns3::Scheduler.
Definition at line 124 of file calendar-scheduler.cc.
References m_qSize, and NS_LOG_FUNCTION.
Referenced by DoRemoveNext(), PeekNext(), Remove(), and RemoveNext().
|
virtual |
This method cannot be invoked if the list is empty.
Implements ns3::Scheduler.
Definition at line 130 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.
|
private |
Definition at line 73 of file calendar-scheduler.cc.
References m_buckets, m_nBuckets, m_width, and NS_LOG_FUNCTION.
|
virtual |
ev | the event to remove |
This methods cannot be invoked if the list is empty.
Implements ns3::Scheduler.
Definition at line 227 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().
|
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 212 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().
|
private |
Definition at line 371 of file calendar-scheduler.cc.
References CalculateNewWidth(), DoResize(), and NS_LOG_FUNCTION.
Referenced by ResizeDown(), and ResizeUp().
|
private |
Definition at line 262 of file calendar-scheduler.cc.
References m_nBuckets, m_qSize, NS_LOG_FUNCTION, and Resize().
Referenced by Remove(), and RemoveNext().
|
private |
Definition at line 251 of file calendar-scheduler.cc.
References m_nBuckets, m_qSize, NS_LOG_FUNCTION, and Resize().
Referenced by Insert().
|
private |
Definition at line 76 of file calendar-scheduler.h.
Referenced by DoInsert(), DoRemoveNext(), DoResize(), Init(), PeekNext(), PrintInfo(), Remove(), and ~CalendarScheduler().
|
private |
Definition at line 84 of file calendar-scheduler.h.
Referenced by CalculateNewWidth(), DoRemoveNext(), Init(), PeekNext(), and RemoveNext().
|
private |
Definition at line 82 of file calendar-scheduler.h.
Referenced by CalculateNewWidth(), DoRemoveNext(), Init(), PeekNext(), and RemoveNext().
|
private |
Definition at line 86 of file calendar-scheduler.h.
Referenced by CalculateNewWidth(), DoRemoveNext(), DoResize(), and Init().
|
private |
Definition at line 78 of file calendar-scheduler.h.
Referenced by DoRemoveNext(), DoResize(), Hash(), Init(), PeekNext(), PrintInfo(), ResizeDown(), and ResizeUp().
|
private |
Definition at line 88 of file calendar-scheduler.h.
Referenced by CalculateNewWidth(), CalendarScheduler(), Insert(), IsEmpty(), Remove(), RemoveNext(), ResizeDown(), and ResizeUp().
|
private |
Definition at line 80 of file calendar-scheduler.h.
Referenced by DoRemoveNext(), Hash(), Init(), PeekNext(), and PrintInfo().