A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
ns3::CandidateQueue Class Reference

A Candidate Queue used in static routing. More...

#include <candidate-queue.h>

Public Member Functions

 CandidateQueue ()
 Create an empty SPF Candidate Queue. More...
 
virtual ~CandidateQueue ()
 
void Clear (void)
 Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Vertex pointers in the queue. More...
 
bool Empty (void) const
 Test the Candidate Queue to determine if it is empty. More...
 
SPFVertexFind (const Ipv4Address addr) const
 Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having the given IP address. More...
 
SPFVertexPop (void)
 Pop the Shortest Path First Vertex pointer at the top of the queue. More...
 
void Push (SPFVertex *vNew)
 Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme. More...
 
void Reorder (void)
 Reorders the Candidate Queue according to the priority scheme. More...
 
uint32_t Size (void) const
 Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue. More...
 
SPFVertexTop (void) const
 Return the Shortest Path First Vertex pointer at the top of the queue. More...
 

Private Types

typedef std::list< SPFVertex * > CandidateList_t
 

Private Member Functions

 CandidateQueue (CandidateQueue &sr)
 
CandidateQueueoperator= (CandidateQueue &sr)
 

Static Private Member Functions

static bool CompareSPFVertex (const SPFVertex *v1, const SPFVertex *v2)
 return true if v1 < v2 More...
 

Private Attributes

CandidateList_t m_candidates
 

Friends

std::ostream & operator<< (std::ostream &os, const CandidateQueue &q)
 

Detailed Description

A Candidate Queue used in static routing.

The CandidateQueue is used in the OSPF shortest path computations. It is a priority queue used to store candidates for the shortest path to a given network.

The queue holds Shortest Path First Vertex pointers and orders them according to the lowest value of the field m_distanceFromRoot. Remaining vertices are ordered according to increasing distance. This implements a priority queue.

Although a STL priority_queue almost does what we want, the requirement for a Find () operation, the dynamic nature of the data and the derived requirement for a Reorder () operation led us to implement this simple enhanced priority queue.

Definition at line 49 of file candidate-queue.h.

Constructor & Destructor Documentation

ns3::CandidateQueue::CandidateQueue ( )

Create an empty SPF Candidate Queue.

See Also
SPFVertex

Definition at line 61 of file candidate-queue.cc.

References NS_LOG_FUNCTION.

ns3::CandidateQueue::~CandidateQueue ( )
virtual

Destroy an SPF Candidate Queue and release any resources held by the contents.

See Also
SPFVertex

Definition at line 67 of file candidate-queue.cc.

References Clear(), and NS_LOG_FUNCTION.

ns3::CandidateQueue::CandidateQueue ( CandidateQueue sr)
private

Candidate Queue copy construction is disallowed (not implemented) to prevent the compiler from slipping in incorrect versions that don't properly deal with deep copies.

Parameters
srobject to copy

Member Function Documentation

void ns3::CandidateQueue::Clear ( void  )

Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Vertex pointers in the queue.

See Also
SPFVertex

Definition at line 74 of file candidate-queue.cc.

References NS_LOG_FUNCTION, and Pop().

Referenced by ~CandidateQueue().

bool ns3::CandidateQueue::CompareSPFVertex ( const SPFVertex v1,
const SPFVertex v2 
)
staticprivate

return true if v1 < v2

SPFVertexes are added into the queue according to the ordering defined by this method. If v1 should be popped before v2, this method return true; false otherwise

Returns
True if v1 should be popped before v2; false otherwise

Definition at line 173 of file candidate-queue.cc.

References ns3::SPFVertex::GetDistanceFromRoot(), ns3::SPFVertex::GetVertexType(), NS_LOG_FUNCTION, ns3::SPFVertex::VertexNetwork, and ns3::SPFVertex::VertexRouter.

Referenced by Push(), and Reorder().

bool ns3::CandidateQueue::Empty ( void  ) const

Test the Candidate Queue to determine if it is empty.

Returns
True if the queue is empty, false otherwise.

Definition at line 124 of file candidate-queue.cc.

References NS_LOG_FUNCTION.

SPFVertex * ns3::CandidateQueue::Find ( const Ipv4Address  addr) const

Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having the given IP address.

See Also
SPFVertex
Parameters
addrThe IP address to search for.
Returns
The SPFVertex* pointer corresponding to the given IP address.

Definition at line 138 of file candidate-queue.cc.

References ns3::SPFVertex::GetVertexId(), and NS_LOG_FUNCTION.

CandidateQueue& ns3::CandidateQueue::operator= ( CandidateQueue sr)
private

Candidate Queue assignment operator is disallowed (not implemented) to prevent the compiler from slipping in incorrect versions that don't properly deal with deep copies.

Parameters
srobject to assign
SPFVertex * ns3::CandidateQueue::Pop ( void  )

Pop the Shortest Path First Vertex pointer at the top of the queue.

The caller is given the responsibility for releasing the resources associated with the vertex.

See Also
SPFVertex
Top ()
Returns
The Shortest Path First Vertex pointer at the top of the queue.

Definition at line 98 of file candidate-queue.cc.

References NS_LOG_FUNCTION.

Referenced by Clear(), and GlobalRouteManagerImplTestCase::DoRun().

void ns3::CandidateQueue::Push ( SPFVertex vNew)

Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme.

On completion, the top of the queue will hold the Shortest Path First Vertex pointer that points to a vertex having lowest value of the field m_distanceFromRoot. Remaining vertices are ordered according to increasing distance.

See Also
SPFVertex
Parameters
vNewThe Shortest Path First Vertex to add to the queue.

Definition at line 86 of file candidate-queue.cc.

References CompareSPFVertex(), and NS_LOG_FUNCTION.

Referenced by GlobalRouteManagerImplTestCase::DoRun().

void ns3::CandidateQueue::Reorder ( void  )

Reorders the Candidate Queue according to the priority scheme.

On completion, the top of the queue will hold the Shortest Path First Vertex pointer that points to a vertex having lowest value of the field m_distanceFromRoot. Remaining vertices are ordered according to increasing distance.

This method is provided in case the values of m_distanceFromRoot change during the routing calculations.

See Also
SPFVertex

Definition at line 156 of file candidate-queue.cc.

References CompareSPFVertex(), NS_LOG_FUNCTION, and NS_LOG_LOGIC.

uint32_t ns3::CandidateQueue::Size ( void  ) const

Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.

See Also
SPFVertex
Returns
The number of SPFVertex* pointers in the Candidate Queue.

Definition at line 131 of file candidate-queue.cc.

References NS_LOG_FUNCTION.

SPFVertex * ns3::CandidateQueue::Top ( void  ) const

Return the Shortest Path First Vertex pointer at the top of the queue.

This method does not pop the SPFVertex* off of the queue, it simply returns the pointer.

See Also
SPFVertex
Pop ()
Returns
The Shortest Path First Vertex pointer at the top of the queue.

Definition at line 112 of file candidate-queue.cc.

References NS_LOG_FUNCTION.


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