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
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
SPFVertex * Pop(void)
Pop the Shortest Path First Vertex pointer at the top of the queue.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
uint32_t GetDistanceFromRoot(void) const
Get the distance from the root vertex to "this" SPFVertex object.
Vertex used in shortest path first (SPF) computations.
uint32_t Size(void) const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue...
static bool CompareSPFVertex(const SPFVertex *v1, const SPFVertex *v2)
return true if v1 < v2
A Candidate Queue used in routing calculations.
void Clear(void)
Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Ve...
Ipv4Address GetVertexId(void) const
Get the Vertex ID field of a SPFVertex object.
#define list
std::ostream & operator<<(std::ostream &os, const Angles &a)
print a struct Angles to output
Definition: angles.cc:42
void Push(SPFVertex *vNew)
Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme...
Every class exported by the ns3 library is enclosed in the ns3 namespace.
bool Empty(void) const
Test the Candidate Queue to determine if it is empty.
CandidateList_t m_candidates
SPFVertex candidates.
CandidateQueue()
Create an empty SPF Candidate Queue.
NS_LOG_LOGIC("Net device "<< nd<< " is not bridged")
Vertex representing a router in the topology.
SPFVertex * Top(void) const
Return the Shortest Path First Vertex pointer at the top of the queue.
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:40
std::list< SPFVertex * > CandidateList_t
container of SPFVertex pointers
virtual ~CandidateQueue()
Destroy an SPF Candidate Queue and release any resources held by the contents.
VertexType
Enumeration of the possible types of SPFVertex objects.
void Reorder(void)
Reorders the Candidate Queue according to the priority scheme.
Vertex representing a network in the topology.
VertexType GetVertexType(void) const
Get the Vertex Type field of a SPFVertex object.