A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
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.
 
 ~HeapScheduler () override
 Destructor.
 
void Insert (const Scheduler::Event &ev) override
 Insert a new Event in the schedule.
 
bool IsEmpty () const override
 Test if the schedule is empty.
 
Scheduler::Event PeekNext () const override
 Get a pointer to the next event.
 
void Remove (const Scheduler::Event &ev) override
 Remove a specific event from the event list.
 
Scheduler::Event RemoveNext () override
 Remove the earliest event from the event list.
 
- Public Member Functions inherited from ns3::Scheduler
 ~Scheduler () override=0
 Destructor.
 
- Public Member Functions inherited from ns3::Object
 Object ()
 Constructor.
 
 ~Object () override
 Destructor.
 
void AggregateObject (Ptr< Object > other)
 Aggregate two Objects together.
 
void Dispose ()
 Dispose of this Object.
 
AggregateIterator GetAggregateIterator () const
 Get an iterator to the Objects aggregated to this one.
 
TypeId GetInstanceTypeId () const override
 Get the most derived TypeId for this Object.
 
template<typename T >
Ptr< T > GetObject () const
 Get a pointer to the requested aggregated Object.
 
template<>
Ptr< ObjectGetObject () const
 Specialization of () for objects of type ns3::Object.
 
template<typename T >
Ptr< T > GetObject (TypeId tid) const
 Get a pointer to the requested aggregated Object by TypeId.
 
template<>
Ptr< ObjectGetObject (TypeId tid) const
 Specialization of (TypeId tid) for objects of type ns3::Object.
 
void Initialize ()
 Invoke DoInitialize on all Objects aggregated to this one.
 
bool IsInitialized () const
 Check if the object has been initialized.
 
void UnidirectionalAggregateObject (Ptr< Object > other)
 Aggregate an Object to another Object.
 
- Public Member Functions inherited from ns3::SimpleRefCount< Object, ObjectBase, ObjectDeleter >
 SimpleRefCount ()
 Default constructor.
 
 SimpleRefCount (const SimpleRefCount &o)
 Copy constructor.
 
uint32_t GetReferenceCount () const
 Get the reference count of the object.
 
SimpleRefCountoperator= (const SimpleRefCount &o)
 Assignment operator.
 
void Ref () const
 Increment the reference count.
 
void Unref () const
 Decrement the reference count.
 
- Public Member Functions inherited from ns3::ObjectBase
virtual ~ObjectBase ()
 Virtual destructor.
 
void GetAttribute (std::string name, AttributeValue &value, bool permissive=false) const
 Get the value of an attribute, raising fatal errors if unsuccessful.
 
bool GetAttributeFailSafe (std::string name, AttributeValue &value) const
 Get the value of an attribute without raising errors.
 
void SetAttribute (std::string name, const AttributeValue &value)
 Set a single attribute, raising fatal errors if unsuccessful.
 
bool SetAttributeFailSafe (std::string name, const AttributeValue &value)
 Set a single attribute without raising errors.
 
bool TraceConnect (std::string name, std::string context, const CallbackBase &cb)
 Connect a TraceSource to a Callback with a context.
 
bool TraceConnectWithoutContext (std::string name, const CallbackBase &cb)
 Connect a TraceSource to a Callback without a context.
 
bool TraceDisconnect (std::string name, std::string context, const CallbackBase &cb)
 Disconnect from a TraceSource a Callback previously connected with a context.
 
bool TraceDisconnectWithoutContext (std::string name, const CallbackBase &cb)
 Disconnect from a TraceSource a Callback previously connected without a context.
 

Static Public Member Functions

static TypeId GetTypeId ()
 Register this type.
 
- Static Public Member Functions inherited from ns3::Scheduler
static TypeId GetTypeId ()
 Register this type.
 
- Static Public Member Functions inherited from ns3::Object
static TypeId GetTypeId ()
 Register this type.
 
- Static Public Member Functions inherited from ns3::ObjectBase
static TypeId GetTypeId ()
 Get the type ID.
 

Private Types

typedef std::vector< Scheduler::EventBinaryHeap
 Event list type: vector of Events, managed as a heap.
 

Private Member Functions

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

Private Attributes

BinaryHeap m_heap
 The event list.
 

Additional Inherited Members

- Protected Member Functions inherited from ns3::Object
 Object (const Object &o)
 Copy an Object.
 
virtual void DoDispose ()
 Destructor implementation.
 
virtual void DoInitialize ()
 Initialize() implementation.
 
virtual void NotifyNewAggregate ()
 Notify all Objects aggregated to this one of a new Object being aggregated.
 
- Protected Member Functions inherited from ns3::ObjectBase
void ConstructSelf (const AttributeConstructionList &attributes)
 Complete construction of ObjectBase; invoked by derived classes.
 
virtual void NotifyConstructionCompleted ()
 Notifier called once the ObjectBase is fully constructed.
 

Detailed Description

a binary heap event scheduler

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

Definition at line 62 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 85 of file heap-scheduler.h.

Constructor & Destructor Documentation

◆ HeapScheduler()

ns3::HeapScheduler::HeapScheduler ( )

Constructor.

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

References m_heap, and NS_LOG_FUNCTION.

◆ ~HeapScheduler()

ns3::HeapScheduler::~HeapScheduler ( )
override

Destructor.

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

References NS_LOG_FUNCTION.

Member Function Documentation

◆ BottomUp()

void ns3::HeapScheduler::BottomUp ( )
private

Percolate a newly inserted Last item to its proper position.

Definition at line 144 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 112 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 ( )
static

Register this type.

Returns
The object TypeId.

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

References ns3::TypeId::SetParent().

Referenced by SimulatorTestSuite::SimulatorTestSuite().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ Insert()

void ns3::HeapScheduler::Insert ( const Scheduler::Event & ev)
overridevirtual

Insert a new Event in the schedule.

Parameters
[in]evEvent to store in the event list

Implements ns3::Scheduler.

Definition at line 191 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 105 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 ( ) const
overridevirtual

Test if the schedule is empty.

Returns
true if the event list is empty and false otherwise.

Implements ns3::Scheduler.

Definition at line 137 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 123 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 91 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 ( ) const
private

Return the index of the last element.

Returns
The last index.

Definition at line 98 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 70 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 56 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 ( ) const
overridevirtual

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 199 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)
overridevirtual

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 217 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 ( )
overridevirtual

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 206 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 77 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 ( ) const
inlineprivate

Get the root index of the heap.

Returns
The root index.

Definition at line 84 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 63 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 130 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 156 of file heap-scheduler.cc.

References Exch(), IsBottom(), IsLessStrictly(), LeftChild(), NS_ASSERT, NS_LOG_FUNCTION, RightChild(), and Smallest().

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 173 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: