A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
candidate-queue.cc
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"
24 #include "global-route-manager-impl.h"
25 
26 NS_LOG_COMPONENT_DEFINE ("CandidateQueue");
27 
28 namespace ns3 {
29 
30 std::ostream&
31 operator<< (std::ostream& os, const SPFVertex::VertexType& t)
32 {
33  switch (t)
34  {
35  case SPFVertex::VertexRouter: os << "router"; break;
36  case SPFVertex::VertexNetwork: os << "network"; break;
37  default: os << "unknown"; break;
38  };
39  return os;
40 }
41 
42 std::ostream&
43 operator<< (std::ostream& os, const CandidateQueue& q)
44 {
45  typedef CandidateQueue::CandidateList_t List_t;
46  typedef List_t::const_iterator CIter_t;
47  const CandidateQueue::CandidateList_t& list = q.m_candidates;
48 
49  os << "*** CandidateQueue Begin (<id, distance, LSA-type>) ***" << std::endl;
50  for (CIter_t iter = list.begin (); iter != list.end (); iter++)
51  {
52  os << "<"
53  << (*iter)->GetVertexId () << ", "
54  << (*iter)->GetDistanceFromRoot () << ", "
55  << (*iter)->GetVertexType () << ">" << std::endl;
56  }
57  os << "*** CandidateQueue End ***";
58  return os;
59 }
60 
62  : m_candidates ()
63 {
64  NS_LOG_FUNCTION (this);
65 }
66 
68 {
69  NS_LOG_FUNCTION (this);
70  Clear ();
71 }
72 
73 void
75 {
76  NS_LOG_FUNCTION (this);
77  while (!m_candidates.empty ())
78  {
79  SPFVertex *p = Pop ();
80  delete p;
81  p = 0;
82  }
83 }
84 
85 void
87 {
88  NS_LOG_FUNCTION (this << vNew);
89 
90  CandidateList_t::iterator i = std::upper_bound (
91  m_candidates.begin (), m_candidates.end (), vNew,
93  );
94  m_candidates.insert (i, vNew);
95 }
96 
97 SPFVertex *
99 {
100  NS_LOG_FUNCTION (this);
101  if (m_candidates.empty ())
102  {
103  return 0;
104  }
105 
106  SPFVertex *v = m_candidates.front ();
107  m_candidates.pop_front ();
108  return v;
109 }
110 
111 SPFVertex *
113 {
114  NS_LOG_FUNCTION (this);
115  if (m_candidates.empty ())
116  {
117  return 0;
118  }
119 
120  return m_candidates.front ();
121 }
122 
123 bool
125 {
126  NS_LOG_FUNCTION (this);
127  return m_candidates.empty ();
128 }
129 
130 uint32_t
132 {
133  NS_LOG_FUNCTION (this);
134  return m_candidates.size ();
135 }
136 
137 SPFVertex *
139 {
140  NS_LOG_FUNCTION (this);
141  CandidateList_t::const_iterator i = m_candidates.begin ();
142 
143  for (; i != m_candidates.end (); i++)
144  {
145  SPFVertex *v = *i;
146  if (v->GetVertexId () == addr)
147  {
148  return v;
149  }
150  }
151 
152  return 0;
153 }
154 
155 void
157 {
158  NS_LOG_FUNCTION (this);
159 
160  m_candidates.sort (&CandidateQueue::CompareSPFVertex);
161  NS_LOG_LOGIC ("After reordering the CandidateQueue");
162  NS_LOG_LOGIC (*this);
163 }
164 
165 /*
166  * In this implementation, SPFVertex follows the ordering where
167  * a vertex is ranked first if its GetDistanceFromRoot () is smaller;
168  * In case of a tie, NetworkLSA is always ranked before RouterLSA.
169  *
170  * This ordering is necessary for implementing ECMP
171  */
172 bool
174 {
175  NS_LOG_FUNCTION (&v1 << &v2);
176 
177  bool result = false;
178  if (v1->GetDistanceFromRoot () < v2->GetDistanceFromRoot ())
179  {
180  result = true;
181  }
182  else if (v1->GetDistanceFromRoot () == v2->GetDistanceFromRoot ())
183  {
186  {
187  result = true;
188  }
189  }
190  return result;
191 }
192 
193 } // namespace ns3
#define NS_LOG_FUNCTION(parameters)
Definition: log.h:311
SPFVertex * Pop(void)
Pop the Shortest Path First Vertex pointer at the top of the queue.
#define NS_LOG_COMPONENT_DEFINE(name)
Definition: log.h:122
SPFVertex * Top(void) const
Return the Shortest Path First Vertex pointer at the top of the queue.
Vertex used in shortest path first (SPF) computations. See RFC 2328, Section 16.
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
void Clear(void)
Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Ve...
uint32_t GetDistanceFromRoot(void) const
Get the distance from the root vertex to "this" SPFVertex object.
#define NS_LOG_LOGIC(msg)
Definition: log.h:334
std::ostream & operator<<(std::ostream &os, const Angles &a)
Definition: angles.cc:43
void Push(SPFVertex *vNew)
Push a Shortest Path First Vertex pointer onto the 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:38
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
bool Empty(void) const
Test the Candidate Queue to determine if it is empty.
VertexType GetVertexType(void) const
Get the Vertex Type field of a SPFVertex object.
VertexType
Enumeration of the possible types of SPFVertex objects.
void Reorder(void)
Reorders the Candidate Queue according to the priority scheme.
Ipv4Address GetVertexId(void) const
Get the Vertex ID field of a SPFVertex object.