A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
candidate-queue.cc
Go to the documentation of this file.
1/*
2 * Copyright 2007 University of Washington
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 */
6
7#include "candidate-queue.h"
8
10
11#include "ns3/assert.h"
12#include "ns3/log.h"
13
14#include <algorithm>
15#include <iostream>
16
17namespace ns3
18{
19
20NS_LOG_COMPONENT_DEFINE("CandidateQueue");
21
22/**
23 * \brief Stream insertion operator.
24 *
25 * \param os the reference to the output stream
26 * \param t the SPFVertex type
27 * \returns the reference to the output stream
28 */
29std::ostream&
30operator<<(std::ostream& os, const SPFVertex::VertexType& t)
31{
32 switch (t)
33 {
35 os << "router";
36 break;
38 os << "network";
39 break;
40 default:
41 os << "unknown";
42 break;
43 };
44 return os;
45}
46
47std::ostream&
48operator<<(std::ostream& os, const CandidateQueue& q)
49{
51
52 os << "*** CandidateQueue Begin (<id, distance, LSA-type>) ***" << std::endl;
53 for (auto iter = list.begin(); iter != list.end(); iter++)
54 {
55 os << "<" << (*iter)->GetVertexId() << ", " << (*iter)->GetDistanceFromRoot() << ", "
56 << (*iter)->GetVertexType() << ">" << std::endl;
57 }
58 os << "*** CandidateQueue End ***";
59 return os;
60}
61
63 : m_candidates()
64{
65 NS_LOG_FUNCTION(this);
66}
67
73
74void
76{
77 NS_LOG_FUNCTION(this);
78 while (!m_candidates.empty())
79 {
80 SPFVertex* p = Pop();
81 delete p;
82 p = nullptr;
83 }
84}
85
86void
88{
89 NS_LOG_FUNCTION(this << vNew);
90
91 auto i = std::upper_bound(m_candidates.begin(),
92 m_candidates.end(),
93 vNew,
95 m_candidates.insert(i, vNew);
96}
97
100{
101 NS_LOG_FUNCTION(this);
102 if (m_candidates.empty())
103 {
104 return nullptr;
105 }
106
107 SPFVertex* v = m_candidates.front();
108 m_candidates.pop_front();
109 return v;
110}
111
114{
115 NS_LOG_FUNCTION(this);
116 if (m_candidates.empty())
117 {
118 return nullptr;
119 }
120
121 return m_candidates.front();
122}
123
124bool
126{
127 NS_LOG_FUNCTION(this);
128 return m_candidates.empty();
129}
130
133{
134 NS_LOG_FUNCTION(this);
135 return m_candidates.size();
136}
137
140{
141 NS_LOG_FUNCTION(this);
142 auto i = m_candidates.begin();
143
144 for (; i != m_candidates.end(); i++)
145 {
146 SPFVertex* v = *i;
147 if (v->GetVertexId() == addr)
148 {
149 return v;
150 }
151 }
152
153 return nullptr;
154}
155
156void
158{
159 NS_LOG_FUNCTION(this);
160
162 NS_LOG_LOGIC("After reordering the CandidateQueue");
163 NS_LOG_LOGIC(*this);
164}
165
166/*
167 * In this implementation, SPFVertex follows the ordering where
168 * a vertex is ranked first if its GetDistanceFromRoot () is smaller;
169 * In case of a tie, NetworkLSA is always ranked before RouterLSA.
170 *
171 * This ordering is necessary for implementing ECMP
172 */
173bool
175{
176 NS_LOG_FUNCTION(&v1 << &v2);
177
178 bool result = false;
180 {
181 result = true;
182 }
183 else if (v1->GetDistanceFromRoot() == v2->GetDistanceFromRoot())
184 {
187 {
188 result = true;
189 }
190 }
191 return result;
192}
193
194} // namespace ns3
A Candidate Queue used in routing calculations.
static bool CompareSPFVertex(const SPFVertex *v1, const SPFVertex *v2)
return true if v1 < v2
SPFVertex * Pop()
Pop the Shortest Path First Vertex pointer at the top of the queue.
SPFVertex * Top() const
Return the Shortest Path First Vertex pointer at the top of the queue.
uint32_t Size() const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.
void Push(SPFVertex *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.
std::list< SPFVertex * > CandidateList_t
container of SPFVertex pointers
virtual ~CandidateQueue()
Destroy an SPF Candidate Queue and release any resources held by the contents.
CandidateList_t m_candidates
SPFVertex candidates.
void Clear()
Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Ve...
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
CandidateQueue()
Create an empty SPF Candidate Queue.
bool Empty() const
Test the Candidate Queue to determine if it is empty.
Ipv4 addresses are stored in host order in this class.
Vertex used in shortest path first (SPF) computations.
Ipv4Address GetVertexId() const
Get the Vertex ID field of a SPFVertex object.
VertexType
Enumeration of the possible types of SPFVertex objects.
@ VertexNetwork
Vertex representing a network in the topology.
@ VertexRouter
Vertex representing a router in the topology.
VertexType GetVertexType() const
Get the Vertex Type field of a SPFVertex object.
uint32_t GetDistanceFromRoot() const
Get the distance from the root vertex to "this" SPFVertex object.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition log.h:271
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::ostream & operator<<(std::ostream &os, const Angles &a)
Definition angles.cc:148