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

#include "candidate-queue.h"

Collaboration diagram for ns3::CandidateQueue< T >:

Public Member Functions
	CandidateQueue ()
	Create an empty SPF Candidate Queue.
	CandidateQueue (const CandidateQueue &)=delete
virtual	~CandidateQueue ()
	Destroy an SPF Candidate Queue and release any resources held by the contents.
void	Clear ()
	Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Vertex pointers in the queue.
bool	Empty () const
	Test the Candidate Queue to determine if it is empty.
SPFVertex< T > *	Find (const IpAddress addr) const
	Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having the given IP address.
CandidateQueue &	operator= (const CandidateQueue &)=delete
SPFVertex< T > *	Pop ()
	Pop the Shortest Path First Vertex pointer at the top of the queue.
void	Push (SPFVertex< T > *vNew)
	Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme.
void	Reorder ()
	Reorders the Candidate Queue according to the priority scheme.
uint32_t	Size () const
	Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.
SPFVertex< T > *	Top () const
	Return the Shortest Path First Vertex pointer at the top of the queue.

Private Types
typedef std::list< SPFVertex< T > * >	CandidateList_t
	container of SPFVertex pointers
using	Ip = typename std::conditional_t<IsIpv4, Ipv4, Ipv6>
	Alias for Ipv4 and Ipv6 classes.
using	IpAddress = typename std::conditional_t<IsIpv4, Ipv4Address, Ipv6Address>
	Alias for Ipv4Address and Ipv6Address classes.
using	IpManager = typename std::conditional_t<IsIpv4, Ipv4Manager, Ipv6Manager>
	Alias for Ipv4Manager and Ipv6Manager classes.

Static Private Member Functions
static bool	CompareSPFVertex (const SPFVertex< T > v1, const SPFVertex< T > v2)
	return true if v1 < v2

Private Attributes
CandidateList_t	m_candidates
	SPFVertex candidates.

Static Private Attributes
static constexpr bool	IsIpv4 = std::is_same_v<Ipv4Manager, T>
	Alias for determining whether the parent is Ipv4RoutingProtocol or Ipv6RoutingProtocol.

Friends
std::ostream &	operator<< (std::ostream &os, const CandidateQueue &q)
	Stream insertion operator.

Detailed Description

template<typename T>
class ns3::CandidateQueue< T >

A Candidate Queue used in routing calculations.

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 53 of file candidate-queue.h.

Member Typedef Documentation

◆ CandidateList_t

template<typename T>

typedef std::list<SPFVertex<T>*> ns3::CandidateQueue< T >::CandidateList_t

private

container of SPFVertex pointers

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

◆ Ip

template<typename T>

using ns3::CandidateQueue< T >::Ip = typename std::conditional_t<IsIpv4, Ipv4, Ipv6>

private

Alias for Ipv4 and Ipv6 classes.

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

◆ IpAddress

template<typename T>

using ns3::CandidateQueue< T >::IpAddress = typename std::conditional_t<IsIpv4, Ipv4Address, Ipv6Address>

private

Alias for Ipv4Address and Ipv6Address classes.

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

◆ IpManager

template<typename T>

using ns3::CandidateQueue< T >::IpManager = typename std::conditional_t<IsIpv4, Ipv4Manager, Ipv6Manager>

private

Alias for Ipv4Manager and Ipv6Manager classes.

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

Constructor & Destructor Documentation

◆ CandidateQueue() [1/2]

template<typename T>

ns3::CandidateQueue< T >::CandidateQueue ( )

Create an empty SPF Candidate Queue.

See also: SPFVertex

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

References m_candidates, and NS_LOG_FUNCTION.

Referenced by CandidateQueue(), operator<<, and operator=().

Here is the caller graph for this function:

◆ ~CandidateQueue()

template<typename T>

ns3::CandidateQueue< T >::~CandidateQueue ( )

virtual

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

See also: SPFVertex

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

References Clear(), and NS_LOG_FUNCTION.

Here is the call graph for this function:

◆ CandidateQueue() [2/2]

template<typename T>

ns3::CandidateQueue< T >::CandidateQueue ( const CandidateQueue< T > & )

delete

References CandidateQueue().

Here is the call graph for this function:

Member Function Documentation

◆ Clear()

template<typename T>

void ns3::CandidateQueue< T >::Clear ( )

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 80 of file candidate-queue.cc.

References m_candidates, NS_LOG_FUNCTION, and Pop().

Referenced by ~CandidateQueue().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CompareSPFVertex()

template<typename T>

bool ns3::CandidateQueue< T >::CompareSPFVertex	(	const SPFVertex< T > *	v1,
		const SPFVertex< T > *	v2 )

staticprivate

return true if v1 < v2

SPFVertex items 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

Parameters

v1	first operand
v2	second operand

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

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

References ns3::SPFVertex< T >::GetDistanceFromRoot(), ns3::SPFVertex< T >::GetVertexType(), NS_LOG_FUNCTION, result, ns3::SPFVertex< T >::VertexNetwork, and ns3::SPFVertex< T >::VertexRouter.

Referenced by Push(), and Reorder().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Empty()

template<typename T>

bool ns3::CandidateQueue< T >::Empty ( ) const

Test the Candidate Queue to determine if it is empty.

Returns: True if the queue is empty, false otherwise.

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

References m_candidates, and NS_LOG_FUNCTION.

◆ Find()

template<typename T>

SPFVertex< T > * ns3::CandidateQueue< T >::Find ( const IpAddress 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

addr	The IP address to search for.

Returns: The SPFVertex* pointer corresponding to the given IP address.

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

References m_candidates, NS_LOG_FUNCTION, and v.

Referenced by ns3::GlobalRouteManagerImpl< T >::SPFNext().

Here is the caller graph for this function:

◆ operator=()

template<typename T>

CandidateQueue & ns3::CandidateQueue< T >::operator= ( const CandidateQueue< T > & )

delete

References CandidateQueue().

Here is the call graph for this function:

◆ Pop()

template<typename T>

SPFVertex< T > * ns3::CandidateQueue< T >::Pop ( )

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 106 of file candidate-queue.cc.

References m_candidates, NS_LOG_FUNCTION, and v.

Referenced by Clear(), and ns3::GlobalRouteManagerImpl< T >::SPFCalculate().

Here is the caller graph for this function:

◆ Push()

template<typename T>

void ns3::CandidateQueue< T >::Push ( SPFVertex< T > * 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

vNew	The Shortest Path First Vertex to add to the queue.

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

References CompareSPFVertex(), m_candidates, and NS_LOG_FUNCTION.

Referenced by ns3::GlobalRouteManagerImpl< T >::SPFNext().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Reorder()

template<typename T>

void ns3::CandidateQueue< T >::Reorder ( )

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 169 of file candidate-queue.cc.

References CompareSPFVertex(), m_candidates, NS_LOG_FUNCTION, and NS_LOG_LOGIC.

Referenced by ns3::GlobalRouteManagerImpl< T >::SPFNext().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Size()

template<typename T>

uint32_t ns3::CandidateQueue< T >::Size ( ) 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 142 of file candidate-queue.cc.

References m_candidates, and NS_LOG_FUNCTION.

Referenced by ns3::GlobalRouteManagerImpl< T >::SPFCalculate().

Here is the caller graph for this function:

◆ Top()

template<typename T>

SPFVertex< T > * ns3::CandidateQueue< T >::Top ( ) 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 121 of file candidate-queue.cc.

References m_candidates, and NS_LOG_FUNCTION.

◆ operator<<

template<typename T>

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

friend

Stream insertion operator.

Parameters

os	the reference to the output stream
q	the CandidateQueue

Returns: the reference to the output stream

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

References CandidateQueue(), list, and q.

Member Data Documentation

◆ IsIpv4

template<typename T>

bool ns3::CandidateQueue< T >::IsIpv4 = std::is_same_v<Ipv4Manager, T>

staticconstexprprivate

Alias for determining whether the parent is Ipv4RoutingProtocol or Ipv6RoutingProtocol.

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

◆ m_candidates

template<typename T>

CandidateList_t ns3::CandidateQueue< T >::m_candidates

private

SPFVertex candidates.

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

Referenced by CandidateQueue(), Clear(), Empty(), Find(), Pop(), Push(), Reorder(), Size(), and Top().

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

src/internet/model/candidate-queue.h
src/internet/model/candidate-queue.cc

Public Member Functions

Private Types

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ CandidateList_t

◆ Ip

◆ IpAddress

◆ IpManager

Constructor & Destructor Documentation

◆ CandidateQueue() [1/2]

◆ ~CandidateQueue()

◆ CandidateQueue() [2/2]

Member Function Documentation

◆ Clear()

◆ CompareSPFVertex()

◆ Empty()

◆ Find()

◆ operator=()

◆ Pop()

◆ Push()

◆ Reorder()

◆ Size()

◆ Top()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ IsIpv4

◆ m_candidates