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 45 of file heap-scheduler.cc.

References m_heap, and NS_LOG_FUNCTION.

ns3::HeapScheduler::~HeapScheduler ( )
virtual

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

References NS_LOG_FUNCTION.

Member Function Documentation

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

Definition at line 147 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 115 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 36 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 196 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 108 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 140 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 126 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 93 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 100 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 73 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 61 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 204 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 222 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 210 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 79 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 86 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 67 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 133 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 160 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: