A Discrete-Event Network Simulator
Home
Tutorials ▼
English
Documentation ▼
Installation
Manual
Models
Contributing
Wiki
Development ▼
API Docs
Issue Tracker
Merge Requests
API
Loading...
Searching...
No Matches
candidate-queue.h
Go to the documentation of this file.
1
/*
2
* Copyright 2007 University of Washington
3
*
4
* This program is free software; you can redistribute it and/or modify
5
* it under the terms of the GNU General Public License version 2 as
6
* published by the Free Software Foundation;
7
*
8
* This program is distributed in the hope that it will be useful,
9
* but WITHOUT ANY WARRANTY; without even the implied warranty of
10
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
* GNU General Public License for more details.
12
*
13
* You should have received a copy of the GNU General Public License
14
* along with this program; if not, write to the Free Software
15
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
*
17
* Author: Craig Dowell (craigdo@ee.washington.edu)
18
*/
19
20
#ifndef CANDIDATE_QUEUE_H
21
#define CANDIDATE_QUEUE_H
22
23
#include "ns3/ipv4-address.h"
24
25
#include <list>
26
#include <stdint.h>
27
28
namespace
ns3
29
{
30
31
class
SPFVertex;
32
33
/**
34
* \ingroup globalrouting
35
*
36
* \brief A Candidate Queue used in routing calculations.
37
*
38
* The CandidateQueue is used in the OSPF shortest path computations. It
39
* is a priority queue used to store candidates for the shortest path to a
40
* given network.
41
*
42
* The queue holds Shortest Path First Vertex pointers and orders them
43
* according to the lowest value of the field m_distanceFromRoot. Remaining
44
* vertices are ordered according to increasing distance. This implements a
45
* priority queue.
46
*
47
* Although a STL priority_queue almost does what we want, the requirement
48
* for a Find () operation, the dynamic nature of the data and the derived
49
* requirement for a Reorder () operation led us to implement this simple
50
* enhanced priority queue.
51
*/
52
class
CandidateQueue
53
{
54
public
:
55
/**
56
* @brief Create an empty SPF Candidate Queue.
57
*
58
* @see SPFVertex
59
*/
60
CandidateQueue
();
61
62
/**
63
* @brief Destroy an SPF Candidate Queue and release any resources held
64
* by the contents.
65
*
66
* @see SPFVertex
67
*/
68
virtual
~CandidateQueue
();
69
70
// Delete copy constructor and assignment operator to avoid misuse
71
CandidateQueue
(
const
CandidateQueue
&) =
delete
;
72
CandidateQueue
&
operator=
(
const
CandidateQueue
&) =
delete
;
73
74
/**
75
* @brief Empty the Candidate Queue and release all of the resources
76
* associated with the Shortest Path First Vertex pointers in the queue.
77
*
78
* @see SPFVertex
79
*/
80
void
Clear
();
81
82
/**
83
* @brief Push a Shortest Path First Vertex pointer onto the queue according
84
* to the priority scheme.
85
*
86
* On completion, the top of the queue will hold the Shortest Path First
87
* Vertex pointer that points to a vertex having lowest value of the field
88
* m_distanceFromRoot. Remaining vertices are ordered according to
89
* increasing distance.
90
*
91
* @see SPFVertex
92
* @param vNew The Shortest Path First Vertex to add to the queue.
93
*/
94
void
Push
(
SPFVertex
* vNew);
95
96
/**
97
* @brief Pop the Shortest Path First Vertex pointer at the top of the queue.
98
*
99
* The caller is given the responsibility for releasing the resources
100
* associated with the vertex.
101
*
102
* @see SPFVertex
103
* @see Top ()
104
* @returns The Shortest Path First Vertex pointer at the top of the queue.
105
*/
106
SPFVertex
*
Pop
();
107
108
/**
109
* @brief Return the Shortest Path First Vertex pointer at the top of the
110
* queue.
111
*
112
* This method does not pop the SPFVertex* off of the queue, it simply
113
* returns the pointer.
114
*
115
* @see SPFVertex
116
* @see Pop ()
117
* @returns The Shortest Path First Vertex pointer at the top of the queue.
118
*/
119
SPFVertex
*
Top
()
const
;
120
121
/**
122
* @brief Test the Candidate Queue to determine if it is empty.
123
*
124
* @returns True if the queue is empty, false otherwise.
125
*/
126
bool
Empty
()
const
;
127
128
/**
129
* @brief Return the number of Shortest Path First Vertex pointers presently
130
* stored in the Candidate Queue.
131
*
132
* @see SPFVertex
133
* @returns The number of SPFVertex* pointers in the Candidate Queue.
134
*/
135
uint32_t
Size
()
const
;
136
137
/**
138
* @brief Searches the Candidate Queue for a Shortest Path First Vertex
139
* pointer that points to a vertex having the given IP address.
140
*
141
* @see SPFVertex
142
* @param addr The IP address to search for.
143
* @returns The SPFVertex* pointer corresponding to the given IP address.
144
*/
145
SPFVertex
*
Find
(
const
Ipv4Address
addr)
const
;
146
147
/**
148
* @brief Reorders the Candidate Queue according to the priority scheme.
149
*
150
* On completion, the top of the queue will hold the Shortest Path First
151
* Vertex pointer that points to a vertex having lowest value of the field
152
* m_distanceFromRoot. Remaining vertices are ordered according to
153
* increasing distance.
154
*
155
* This method is provided in case the values of m_distanceFromRoot change
156
* during the routing calculations.
157
*
158
* @see SPFVertex
159
*/
160
void
Reorder
();
161
162
private
:
163
/**
164
* \brief return true if v1 < v2
165
*
166
* SPFVertexes are added into the queue according to the ordering
167
* defined by this method. If v1 should be popped before v2, this
168
* method return true; false otherwise
169
*
170
* \param v1 first operand
171
* \param v2 second operand
172
* \return True if v1 should be popped before v2; false otherwise
173
*/
174
static
bool
CompareSPFVertex
(
const
SPFVertex
* v1,
const
SPFVertex
* v2);
175
176
typedef
std::list<SPFVertex*>
CandidateList_t
;
//!< container of SPFVertex pointers
177
CandidateList_t
m_candidates
;
//!< SPFVertex candidates
178
179
/**
180
* \brief Stream insertion operator.
181
*
182
* \param os the reference to the output stream
183
* \param q the CandidateQueue
184
* \returns the reference to the output stream
185
*/
186
friend
std::ostream&
operator<<
(std::ostream& os,
const
CandidateQueue
& q);
187
};
188
189
}
// namespace ns3
190
191
#endif
/* CANDIDATE_QUEUE_H */
ns3::CandidateQueue
A Candidate Queue used in routing calculations.
Definition:
candidate-queue.h:53
ns3::CandidateQueue::CompareSPFVertex
static bool CompareSPFVertex(const SPFVertex *v1, const SPFVertex *v2)
return true if v1 < v2
Definition:
candidate-queue.cc:185
ns3::CandidateQueue::operator<<
friend std::ostream & operator<<(std::ostream &os, const CandidateQueue &q)
Stream insertion operator.
Definition:
candidate-queue.cc:59
ns3::CandidateQueue::Pop
SPFVertex * Pop()
Pop the Shortest Path First Vertex pointer at the top of the queue.
Definition:
candidate-queue.cc:110
ns3::CandidateQueue::CandidateQueue
CandidateQueue(const CandidateQueue &)=delete
ns3::CandidateQueue::Top
SPFVertex * Top() const
Return the Shortest Path First Vertex pointer at the top of the queue.
Definition:
candidate-queue.cc:124
ns3::CandidateQueue::Size
uint32_t Size() const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.
Definition:
candidate-queue.cc:143
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:98
ns3::CandidateQueue::Reorder
void Reorder()
Reorders the Candidate Queue according to the priority scheme.
Definition:
candidate-queue.cc:168
ns3::CandidateQueue::operator=
CandidateQueue & operator=(const CandidateQueue &)=delete
ns3::CandidateQueue::CandidateList_t
std::list< SPFVertex * > CandidateList_t
container of SPFVertex pointers
Definition:
candidate-queue.h:176
ns3::CandidateQueue::~CandidateQueue
virtual ~CandidateQueue()
Destroy an SPF Candidate Queue and release any resources held by the contents.
Definition:
candidate-queue.cc:79
ns3::CandidateQueue::m_candidates
CandidateList_t m_candidates
SPFVertex candidates.
Definition:
candidate-queue.h:177
ns3::CandidateQueue::Clear
void Clear()
Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Ve...
Definition:
candidate-queue.cc:86
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:150
ns3::CandidateQueue::CandidateQueue
CandidateQueue()
Create an empty SPF Candidate Queue.
Definition:
candidate-queue.cc:73
ns3::CandidateQueue::Empty
bool Empty() const
Test the Candidate Queue to determine if it is empty.
Definition:
candidate-queue.cc:136
ns3::Ipv4Address
Ipv4 addresses are stored in host order in this class.
Definition:
ipv4-address.h:42
ns3::SPFVertex
Vertex used in shortest path first (SPF) computations.
Definition:
global-route-manager-impl.h:71
uint32_t
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
src
internet
model
candidate-queue.h
Generated on Tue May 28 2024 23:35:40 for ns-3 by
1.9.6