A Discrete-Event Network Simulator
API
candidate-queue.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright 2007 University of Washington
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  */
18 
19 #include <algorithm>
20 #include <iostream>
21 #include "ns3/log.h"
22 #include "ns3/assert.h"
23 #include "candidate-queue.h"
25 
26 namespace ns3 {
27 
28 NS_LOG_COMPONENT_DEFINE ("CandidateQueue");
29 
37 std::ostream&
38 operator<< (std::ostream& os, const SPFVertex::VertexType& t)
39 {
40  switch (t)
41  {
42  case SPFVertex::VertexRouter: os << "router"; break;
43  case SPFVertex::VertexNetwork: os << "network"; break;
44  default: os << "unknown"; break;
45  };
46  return os;
47 }
48 
49 std::ostream&
50 operator<< (std::ostream& os, const CandidateQueue& q)
51 {
52  typedef CandidateQueue::CandidateList_t List_t;
53  typedef List_t::const_iterator CIter_t;
55 
56  os << "*** CandidateQueue Begin (<id, distance, LSA-type>) ***" << std::endl;
57  for (CIter_t iter = list.begin (); iter != list.end (); iter++)
58  {
59  os << "<"
60  << (*iter)->GetVertexId () << ", "
61  << (*iter)->GetDistanceFromRoot () << ", "
62  << (*iter)->GetVertexType () << ">" << std::endl;
63  }
64  os << "*** CandidateQueue End ***";
65  return os;
66 }
67 
69  : m_candidates ()
70 {
71  NS_LOG_FUNCTION (this);
72 }
73 
75 {
76  NS_LOG_FUNCTION (this);
77  Clear ();
78 }
79 
80 void
82 {
83  NS_LOG_FUNCTION (this);
84  while (!m_candidates.empty ())
85  {
86  SPFVertex *p = Pop ();
87  delete p;
88  p = 0;
89  }
90 }
91 
92 void
94 {
95  NS_LOG_FUNCTION (this << vNew);
96 
97  CandidateList_t::iterator i = std::upper_bound (
98  m_candidates.begin (), m_candidates.end (), vNew,
100  );
101  m_candidates.insert (i, vNew);
102 }
103 
104 SPFVertex *
106 {
107  NS_LOG_FUNCTION (this);
108  if (m_candidates.empty ())
109  {
110  return 0;
111  }
112 
113  SPFVertex *v = m_candidates.front ();
114  m_candidates.pop_front ();
115  return v;
116 }
117 
118 SPFVertex *
120 {
121  NS_LOG_FUNCTION (this);
122  if (m_candidates.empty ())
123  {
124  return 0;
125  }
126 
127  return m_candidates.front ();
128 }
129 
130 bool
132 {
133  NS_LOG_FUNCTION (this);
134  return m_candidates.empty ();
135 }
136 
137 uint32_t
139 {
140  NS_LOG_FUNCTION (this);
141  return m_candidates.size ();
142 }
143 
144 SPFVertex *
146 {
147  NS_LOG_FUNCTION (this);
148  CandidateList_t::const_iterator i = m_candidates.begin ();
149 
150  for (; i != m_candidates.end (); i++)
151  {
152  SPFVertex *v = *i;
153  if (v->GetVertexId () == addr)
154  {
155  return v;
156  }
157  }
158 
159  return 0;
160 }
161 
162 void
164 {
165  NS_LOG_FUNCTION (this);
166 
168  NS_LOG_LOGIC ("After reordering the CandidateQueue");
169  NS_LOG_LOGIC (*this);
170 }
171 
172 /*
173  * In this implementation, SPFVertex follows the ordering where
174  * a vertex is ranked first if its GetDistanceFromRoot () is smaller;
175  * In case of a tie, NetworkLSA is always ranked before RouterLSA.
176  *
177  * This ordering is necessary for implementing ECMP
178  */
179 bool
181 {
182  NS_LOG_FUNCTION (&v1 << &v2);
183 
184  bool result = false;
185  if (v1->GetDistanceFromRoot () < v2->GetDistanceFromRoot ())
186  {
187  result = true;
188  }
189  else if (v1->GetDistanceFromRoot () == v2->GetDistanceFromRoot ())
190  {
193  {
194  result = true;
195  }
196  }
197  return result;
198 }
199 
200 } // namespace ns3
NS_LOG_COMPONENT_DEFINE
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
ns3::CandidateQueue::Push
void Push(SPFVertex *vNew)
Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme.
Definition: candidate-queue.cc:93
ns3::CandidateQueue
A Candidate Queue used in routing calculations.
Definition: candidate-queue.h:52
ns3::CandidateQueue::m_candidates
CandidateList_t m_candidates
SPFVertex candidates.
Definition: candidate-queue.h:188
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::SPFVertex::GetVertexId
Ipv4Address GetVertexId(void) const
Get the Vertex ID field of a SPFVertex object.
Definition: global-route-manager-impl.cc:198
ns3::SPFVertex::VertexRouter
@ VertexRouter
Vertex representing a router in the topology.
Definition: global-route-manager-impl.h:80
ns3::Ipv4Address
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:41
ns3::CandidateQueue::Empty
bool Empty(void) const
Test the Candidate Queue to determine if it is empty.
Definition: candidate-queue.cc:131
ns3::CandidateQueue::Size
uint32_t Size(void) const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.
Definition: candidate-queue.cc:138
ns3::SPFVertex::GetDistanceFromRoot
uint32_t GetDistanceFromRoot(void) const
Get the distance from the root vertex to "this" SPFVertex object.
Definition: global-route-manager-impl.cc:226
ns3::CandidateQueue::Find
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
Definition: candidate-queue.cc:145
ns3::CandidateQueue::CandidateList_t
std::list< SPFVertex * > CandidateList_t
container of SPFVertex pointers
Definition: candidate-queue.h:187
ns3::SPFVertex::GetVertexType
VertexType GetVertexType(void) const
Get the Vertex Type field of a SPFVertex object.
Definition: global-route-manager-impl.cc:184
ns3::SPFVertex::VertexNetwork
@ VertexNetwork
Vertex representing a network in the topology.
Definition: global-route-manager-impl.h:81
ns3::CandidateQueue::Clear
void Clear(void)
Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Ve...
Definition: candidate-queue.cc:81
ns3::CandidateQueue::Pop
SPFVertex * Pop(void)
Pop the Shortest Path First Vertex pointer at the top of the queue.
Definition: candidate-queue.cc:105
ns3::CandidateQueue::Top
SPFVertex * Top(void) const
Return the Shortest Path First Vertex pointer at the top of the queue.
Definition: candidate-queue.cc:119
ns3::CandidateQueue::CandidateQueue
CandidateQueue()
Create an empty SPF Candidate Queue.
Definition: candidate-queue.cc:68
list
#define list
Definition: openflow-interface.h:47
ns3::CandidateQueue::CompareSPFVertex
static bool CompareSPFVertex(const SPFVertex *v1, const SPFVertex *v2)
return true if v1 < v2
Definition: candidate-queue.cc:180
NS_LOG_LOGIC
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
test-ns3.result
result
Definition: test-ns3.py:576
candidate-queue.h
ns3::CandidateQueue::~CandidateQueue
virtual ~CandidateQueue()
Destroy an SPF Candidate Queue and release any resources held by the contents.
Definition: candidate-queue.cc:74
ns3::CandidateQueue::Reorder
void Reorder(void)
Reorders the Candidate Queue according to the priority scheme.
Definition: candidate-queue.cc:163
NS_LOG_FUNCTION
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Definition: log-macros-enabled.h:244
global-route-manager-impl.h
ns3::SPFVertex::VertexType
VertexType
Enumeration of the possible types of SPFVertex objects.
Definition: global-route-manager-impl.h:78
ns3::operator<<
std::ostream & operator<<(std::ostream &os, const Angles &a)
Definition: angles.cc:137
ns3::SPFVertex
Vertex used in shortest path first (SPF) computations.
Definition: global-route-manager-impl.h:69