A Discrete-Event Network Simulator
API
ns3::HeapScheduler Class Reference

a binary heap event scheduler More...

#include "heap-scheduler.h"

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

Public Member Functions

 HeapScheduler ()
 Constructor. More...
 
virtual ~HeapScheduler ()
 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<>
Ptr< ObjectGetObject () const
 Specialization of () for objects of type ns3::Object. More...
 
template<typename T >
Ptr< T > GetObject (TypeId tid) const
 Get a pointer to the requested aggregated Object by TypeId. More...
 
template<>
Ptr< ObjectGetObject (TypeId tid) const
 Specialization of (TypeId tid) for objects of type ns3::Object. More...
 
template<typename T >
Ptr< T > GetObject (void) const
 Get a pointer to the requested aggregated Object. 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[[maybe_unused]])
 Copy constructor. More...
 
uint32_t GetReferenceCount (void) const
 Get the reference count of the object. More...
 
SimpleRefCountoperator= ([[maybe_unused]] 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::vector< Scheduler::EventBinaryHeap
 Event list type: vector of Events, managed as a heap. More...
 

Private Member Functions

void BottomUp (void)
 Percolate a newly inserted Last item to its proper position. More...
 
void Exch (std::size_t a, std::size_t b)
 Swap two items. More...
 
bool IsBottom (std::size_t id) const
 Test if an index is at the bottom of the heap. More...
 
bool IsLessStrictly (std::size_t a, std::size_t b) const
 Compare (less than) two items. More...
 
bool IsRoot (std::size_t id) const
 Test if an index is the root. More...
 
std::size_t Last (void) const
 Return the index of the last element. More...
 
std::size_t LeftChild (std::size_t id) const
 Get the left child of a given entry. More...
 
std::size_t Parent (std::size_t id) const
 Get the parent index of a given entry. More...
 
std::size_t RightChild (std::size_t id) const
 Get the right child index of a given entry. More...
 
std::size_t Root (void) const
 Get the root index of the heap. More...
 
std::size_t Sibling (std::size_t id) const
 Get the next sibling of a given entry. More...
 
std::size_t Smallest (std::size_t a, std::size_t b) const
 Minimum of two items. More...
 
void TopDown (std::size_t start)
 Percolate a deletion bubble down the heap. More...
 

Private Attributes

BinaryHeap m_heap
 The event list. 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 binary heap event scheduler

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, implemented on a std::vector. This implementation does not make use of any of the heap functions from the STL. 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.
Time Complexity
Operation Amortized Time Reason
Insert() Logarithmic Heapify
IsEmpty() Constant Explicit queue size
PeekNext() Constant Heap kept sorted
Remove() Logarithmic Search, heapify
RemoveNext() Logarithmic Heapify
Memory Complexity
Category Memory Reason
Overhead 3 x sizeof (*)
(24 bytes)
std::vector
Per Event 0 Events stored in std::vector directly


No Attributes are defined for this type.
No TraceSources are defined for this type.
Size of this type is 56 bytes (on a 64-bit architecture).

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

Member Typedef Documentation

◆ BinaryHeap

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

Event list type: vector of Events, managed as a heap.

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

Constructor & Destructor Documentation

◆ HeapScheduler()

ns3::HeapScheduler::HeapScheduler ( )

Constructor.

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

References m_heap, and NS_LOG_FUNCTION.

◆ ~HeapScheduler()

ns3::HeapScheduler::~HeapScheduler ( )
virtual

Destructor.

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

References NS_LOG_FUNCTION.

Member Function Documentation

◆ BottomUp()

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

Percolate a newly inserted Last item to its proper position.

Definition at line 153 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:

◆ Exch()

void ns3::HeapScheduler::Exch ( std::size_t  a,
std::size_t  b 
)
inlineprivate

Swap two items.

Parameters
[in]aThe first item.
[in]bThe second item.

Definition at line 121 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:

◆ GetTypeId()

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

Register this type.

Returns
The object TypeId.

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

References ns3::TypeId::SetParent().

+ Here is the call graph for this function:

◆ Insert()

void ns3::HeapScheduler::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 202 of file heap-scheduler.cc.

References BottomUp(), m_heap, and NS_LOG_FUNCTION.

+ Here is the call graph for this function:

◆ IsBottom()

bool ns3::HeapScheduler::IsBottom ( std::size_t  id) const
inlineprivate

Test if an index is at the bottom of the heap.

Parameters
[in]idThe index to test.
Returns
true if the index is at the bottom.

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

References m_heap, and NS_LOG_FUNCTION.

Referenced by TopDown().

+ Here is the caller graph for this function:

◆ IsEmpty()

bool ns3::HeapScheduler::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 146 of file heap-scheduler.cc.

References m_heap, and NS_LOG_FUNCTION.

◆ IsLessStrictly()

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

Compare (less than) two items.

Parameters
[in]aThe first item.
[in]bThe second item.
Returns
true if a < b

Definition at line 132 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:

◆ IsRoot()

bool ns3::HeapScheduler::IsRoot ( std::size_t  id) const
inlineprivate

Test if an index is the root.

Parameters
[in]idThe index to test.
Returns
true if the id is the root.

Definition at line 99 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:

◆ Last()

std::size_t ns3::HeapScheduler::Last ( void  ) const
private

Return the index of the last element.

Returns
The last index.

Definition at line 106 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:

◆ LeftChild()

std::size_t ns3::HeapScheduler::LeftChild ( std::size_t  id) const
inlineprivate

Get the left child of a given entry.

Parameters
[in]idThe parent index.
Returns
The index of the left (first) child.

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

References NS_LOG_FUNCTION.

Referenced by TopDown().

+ Here is the caller graph for this function:

◆ Parent()

std::size_t ns3::HeapScheduler::Parent ( std::size_t  id) const
inlineprivate

Get the parent index of a given entry.

Parameters
[in]idThe child index.
Returns
The index of the parent of id.

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

References NS_LOG_FUNCTION.

Referenced by BottomUp().

+ Here is the caller graph for this function:

◆ PeekNext()

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

References m_heap, NS_LOG_FUNCTION, and Root().

+ Here is the call graph for this function:

◆ Remove()

void ns3::HeapScheduler::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 228 of file heap-scheduler.cc.

References Exch(), ns3::Scheduler::Event::impl, ns3::Scheduler::Event::key, Last(), m_heap, ns3::Scheduler::EventKey::m_uid, NS_ASSERT, NS_LOG_FUNCTION, and TopDown().

+ Here is the call graph for this function:

◆ RemoveNext()

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

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

+ Here is the call graph for this function:

◆ RightChild()

std::size_t ns3::HeapScheduler::RightChild ( std::size_t  id) const
inlineprivate

Get the right child index of a given entry.

Parameters
[in]idThe parent index.
Returns
The index of the right (second) child.

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

References NS_LOG_FUNCTION.

Referenced by TopDown().

+ Here is the caller graph for this function:

◆ Root()

std::size_t ns3::HeapScheduler::Root ( void  ) const
inlineprivate

Get the root index of the heap.

Returns
The root index.

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

References NS_LOG_FUNCTION.

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

+ Here is the caller graph for this function:

◆ Sibling()

std::size_t ns3::HeapScheduler::Sibling ( std::size_t  id) const
private

Get the next sibling of a given entry.

Parameters
[in]idThe starting index.
Returns
The next sibling of id.

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

References NS_LOG_FUNCTION.

◆ Smallest()

std::size_t ns3::HeapScheduler::Smallest ( std::size_t  a,
std::size_t  b 
) const
inlineprivate

Minimum of two items.

Parameters
[in]aThe first item.
[in]bThe second item.
Returns
The smaller of the two items.

Definition at line 139 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:

◆ TopDown()

void ns3::HeapScheduler::TopDown ( std::size_t  start)
private

Percolate a deletion bubble down the heap.

Parameters
[in]startStarting entry.

Definition at line 166 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

◆ m_heap

BinaryHeap ns3::HeapScheduler::m_heap
private

The event list.

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

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


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