A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
ns3::HeapScheduler Class Reference
Scheduler and Events

a binary heap event scheduler More...

#include <heap-scheduler.h>

+ Inheritance diagram for ns3::HeapScheduler:
+ Collaboration diagram for ns3::HeapScheduler:

Public Member Functions

 HeapScheduler ()
 
virtual ~HeapScheduler ()
 
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
 
virtual void Insert (const Event &ev)=0
 
virtual void Remove (const Event &ev)=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...
 
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...
 
- 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::vector< Event > BinaryHeap
 

Private Member Functions

void BottomUp (void)
 
void Exch (uint32_t a, uint32_t b)
 
bool IsBottom (uint32_t id) const
 
bool IsLessStrictly (uint32_t a, uint32_t b) const
 
bool IsRoot (uint32_t id) const
 
uint32_t Last (void) const
 
uint32_t LeftChild (uint32_t id) const
 
uint32_t Parent (uint32_t id) const
 
uint32_t RightChild (uint32_t id) const
 
uint32_t Root (void) const
 
uint32_t Sibling (uint32_t id) const
 
uint32_t Smallest (uint32_t a, uint32_t b) const
 
void TopDown (uint32_t start)
 

Private Attributes

BinaryHeap m_heap
 

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 binary heap event scheduler

Doxygen introspection did not find any typical Config paths.

This code started as a c++ translation of a java-based code written in 2005 to implement a heap sort. So, this binary heap is really a pretty straightforward implementation of the classic data structure. Not much to say about it.

What is smart about this code ?

  • it does not use the index 0 in the array to avoid having to convert C-style array indexes (which start at zero) and heap-style indexes (which start at 1). This is why all indexes start at 1, and that the index of the root is 1.
  • It uses a slightly non-standard while loop for top-down heapify to move one if statement out of the loop.


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

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

Member Typedef Documentation

typedef std::vector<Event> ns3::HeapScheduler::BinaryHeap
private

Definition at line 62 of file heap-scheduler.h.

Constructor & Destructor Documentation

ns3::HeapScheduler::HeapScheduler ( )

Definition at line 44 of file heap-scheduler.cc.

References m_heap, and NS_LOG_FUNCTION.

ns3::HeapScheduler::~HeapScheduler ( )
virtual

Definition at line 54 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.

Member Function Documentation

void ns3::HeapScheduler::BottomUp ( void  )
private

Definition at line 146 of file heap-scheduler.cc.

References Exch(), IsLessStrictly(), IsRoot(), Last(), NS_LOG_FUNCTION, and Parent().

Referenced by Insert().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ns3::HeapScheduler::Exch ( uint32_t  a,
uint32_t  b 
)
inlineprivate

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

References m_heap, NS_ASSERT, NS_LOG_DEBUG, and NS_LOG_FUNCTION.

Referenced by BottomUp(), Remove(), RemoveNext(), and TopDown().

+ Here is the caller graph for this function:

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

Definition at line 35 of file heap-scheduler.cc.

References ns3::TypeId::SetParent().

+ Here is the call graph for this function:

void ns3::HeapScheduler::Insert ( const Event &  ev)
virtual

Definition at line 195 of file heap-scheduler.cc.

References BottomUp(), m_heap, and NS_LOG_FUNCTION.

+ Here is the call graph for this function:

bool ns3::HeapScheduler::IsBottom ( uint32_t  id) const
inlineprivate

Definition at line 107 of file heap-scheduler.cc.

References m_heap, and NS_LOG_FUNCTION.

Referenced by TopDown().

+ Here is the caller graph for this function:

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

Implements ns3::Scheduler.

Definition at line 139 of file heap-scheduler.cc.

References m_heap, and NS_LOG_FUNCTION.

bool ns3::HeapScheduler::IsLessStrictly ( uint32_t  a,
uint32_t  b 
) const
inlineprivate

Definition at line 125 of file heap-scheduler.cc.

References m_heap, and NS_LOG_FUNCTION.

Referenced by BottomUp(), Smallest(), and TopDown().

+ Here is the caller graph for this function:

bool ns3::HeapScheduler::IsRoot ( uint32_t  id) const
inlineprivate

Definition at line 92 of file heap-scheduler.cc.

References NS_LOG_FUNCTION, and Root().

Referenced by BottomUp().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Last ( void  ) const
private

Definition at line 99 of file heap-scheduler.cc.

References m_heap, and NS_LOG_FUNCTION.

Referenced by BottomUp(), Remove(), and RemoveNext().

+ Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::LeftChild ( uint32_t  id) const
inlineprivate

Definition at line 72 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.

Referenced by TopDown().

+ Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Parent ( uint32_t  id) const
inlineprivate

Definition at line 60 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.

Referenced by BottomUp().

+ Here is the caller graph for this function:

Scheduler::Event ns3::HeapScheduler::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 203 of file heap-scheduler.cc.

References m_heap, NS_LOG_FUNCTION, and Root().

+ Here is the call graph for this function:

void ns3::HeapScheduler::Remove ( const Event &  ev)
virtual

Definition at line 221 of file heap-scheduler.cc.

References Exch(), Last(), m_heap, NS_ASSERT, NS_LOG_FUNCTION, and TopDown().

+ Here is the call graph for this function:

Scheduler::Event ns3::HeapScheduler::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 209 of file heap-scheduler.cc.

References Exch(), Last(), m_heap, NS_LOG_FUNCTION, Root(), and TopDown().

+ Here is the call graph for this function:

uint32_t ns3::HeapScheduler::RightChild ( uint32_t  id) const
inlineprivate

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

References NS_LOG_FUNCTION.

Referenced by TopDown().

+ Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Root ( void  ) const
inlineprivate

Definition at line 85 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.

Referenced by IsRoot(), PeekNext(), and RemoveNext().

+ Here is the caller graph for this function:

uint32_t ns3::HeapScheduler::Sibling ( uint32_t  id) const
private

Definition at line 66 of file heap-scheduler.cc.

References NS_LOG_FUNCTION.

uint32_t ns3::HeapScheduler::Smallest ( uint32_t  a,
uint32_t  b 
) const
inlineprivate

Definition at line 132 of file heap-scheduler.cc.

References IsLessStrictly(), and NS_LOG_FUNCTION.

Referenced by TopDown().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void ns3::HeapScheduler::TopDown ( uint32_t  start)
private

Definition at line 159 of file heap-scheduler.cc.

References Exch(), IsBottom(), IsLessStrictly(), LeftChild(), NS_ASSERT, NS_LOG_FUNCTION, RightChild(), Smallest(), and visualizer.core::start().

Referenced by Remove(), and RemoveNext().

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Member Data Documentation

BinaryHeap ns3::HeapScheduler::m_heap
private

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

Referenced by Exch(), HeapScheduler(), Insert(), IsBottom(), IsEmpty(), IsLessStrictly(), Last(), PeekNext(), Remove(), and RemoveNext().

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