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
A Candidate Queue used in routing calculations.
static bool CompareSPFVertex(const SPFVertex *v1, const SPFVertex *v2)
return true if v1 < v2
void Clear(void)
Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Ve...
void Push(SPFVertex *vNew)
Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme.
bool Empty(void) const
Test the Candidate Queue to determine if it is empty.
SPFVertex * Pop(void)
Pop the Shortest Path First Vertex pointer at the top of the queue.
std::list< SPFVertex * > CandidateList_t
container of SPFVertex pointers
virtual ~CandidateQueue()
Destroy an SPF Candidate Queue and release any resources held by the contents.
uint32_t Size(void) const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.
CandidateList_t m_candidates
SPFVertex candidates.
SPFVertex * Top(void) const
Return the Shortest Path First Vertex pointer at the top of the queue.
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
void Reorder(void)
Reorders the Candidate Queue according to the priority scheme.
CandidateQueue()
Create an empty SPF Candidate Queue.
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:41
Vertex used in shortest path first (SPF) computations.
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(void) const
Get the Vertex Type field of a SPFVertex object.
uint32_t GetDistanceFromRoot(void) const
Get the distance from the root vertex to "this" SPFVertex object.
Ipv4Address GetVertexId(void) const
Get the Vertex ID field of a SPFVertex object.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
Definition: log.h:289
#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:139
#define list