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
* SPDX-License-Identifier: GPL-2.0-only
5
*
6
* Author: Craig Dowell (craigdo@ee.washington.edu)
7
*/
8
9
#ifndef CANDIDATE_QUEUE_H
10
#define CANDIDATE_QUEUE_H
11
12
#include "ns3/ipv4-address.h"
13
14
#include <list>
15
#include <stdint.h>
16
17
namespace
ns3
18
{
19
20
class
SPFVertex;
21
22
/**
23
* \ingroup globalrouting
24
*
25
* \brief A Candidate Queue used in routing calculations.
26
*
27
* The CandidateQueue is used in the OSPF shortest path computations. It
28
* is a priority queue used to store candidates for the shortest path to a
29
* given network.
30
*
31
* The queue holds Shortest Path First Vertex pointers and orders them
32
* according to the lowest value of the field m_distanceFromRoot. Remaining
33
* vertices are ordered according to increasing distance. This implements a
34
* priority queue.
35
*
36
* Although a STL priority_queue almost does what we want, the requirement
37
* for a Find () operation, the dynamic nature of the data and the derived
38
* requirement for a Reorder () operation led us to implement this simple
39
* enhanced priority queue.
40
*/
41
class
CandidateQueue
42
{
43
public
:
44
/**
45
* @brief Create an empty SPF Candidate Queue.
46
*
47
* @see SPFVertex
48
*/
49
CandidateQueue
();
50
51
/**
52
* @brief Destroy an SPF Candidate Queue and release any resources held
53
* by the contents.
54
*
55
* @see SPFVertex
56
*/
57
virtual
~CandidateQueue
();
58
59
// Delete copy constructor and assignment operator to avoid misuse
60
CandidateQueue
(
const
CandidateQueue
&) =
delete
;
61
CandidateQueue
&
operator=
(
const
CandidateQueue
&) =
delete
;
62
63
/**
64
* @brief Empty the Candidate Queue and release all of the resources
65
* associated with the Shortest Path First Vertex pointers in the queue.
66
*
67
* @see SPFVertex
68
*/
69
void
Clear
();
70
71
/**
72
* @brief Push a Shortest Path First Vertex pointer onto the queue according
73
* to the priority scheme.
74
*
75
* On completion, the top of the queue will hold the Shortest Path First
76
* Vertex pointer that points to a vertex having lowest value of the field
77
* m_distanceFromRoot. Remaining vertices are ordered according to
78
* increasing distance.
79
*
80
* @see SPFVertex
81
* @param vNew The Shortest Path First Vertex to add to the queue.
82
*/
83
void
Push
(
SPFVertex
* vNew);
84
85
/**
86
* @brief Pop the Shortest Path First Vertex pointer at the top of the queue.
87
*
88
* The caller is given the responsibility for releasing the resources
89
* associated with the vertex.
90
*
91
* @see SPFVertex
92
* @see Top ()
93
* @returns The Shortest Path First Vertex pointer at the top of the queue.
94
*/
95
SPFVertex
*
Pop
();
96
97
/**
98
* @brief Return the Shortest Path First Vertex pointer at the top of the
99
* queue.
100
*
101
* This method does not pop the SPFVertex* off of the queue, it simply
102
* returns the pointer.
103
*
104
* @see SPFVertex
105
* @see Pop ()
106
* @returns The Shortest Path First Vertex pointer at the top of the queue.
107
*/
108
SPFVertex
*
Top
()
const
;
109
110
/**
111
* @brief Test the Candidate Queue to determine if it is empty.
112
*
113
* @returns True if the queue is empty, false otherwise.
114
*/
115
bool
Empty
()
const
;
116
117
/**
118
* @brief Return the number of Shortest Path First Vertex pointers presently
119
* stored in the Candidate Queue.
120
*
121
* @see SPFVertex
122
* @returns The number of SPFVertex* pointers in the Candidate Queue.
123
*/
124
uint32_t
Size
()
const
;
125
126
/**
127
* @brief Searches the Candidate Queue for a Shortest Path First Vertex
128
* pointer that points to a vertex having the given IP address.
129
*
130
* @see SPFVertex
131
* @param addr The IP address to search for.
132
* @returns The SPFVertex* pointer corresponding to the given IP address.
133
*/
134
SPFVertex
*
Find
(
const
Ipv4Address
addr)
const
;
135
136
/**
137
* @brief Reorders the Candidate Queue according to the priority scheme.
138
*
139
* On completion, the top of the queue will hold the Shortest Path First
140
* Vertex pointer that points to a vertex having lowest value of the field
141
* m_distanceFromRoot. Remaining vertices are ordered according to
142
* increasing distance.
143
*
144
* This method is provided in case the values of m_distanceFromRoot change
145
* during the routing calculations.
146
*
147
* @see SPFVertex
148
*/
149
void
Reorder
();
150
151
private
:
152
/**
153
* \brief return true if v1 < v2
154
*
155
* SPFVertex items are added into the queue according to the ordering
156
* defined by this method. If v1 should be popped before v2, this
157
* method return true; false otherwise
158
*
159
* \param v1 first operand
160
* \param v2 second operand
161
* \return True if v1 should be popped before v2; false otherwise
162
*/
163
static
bool
CompareSPFVertex
(
const
SPFVertex
* v1,
const
SPFVertex
* v2);
164
165
typedef
std::list<SPFVertex*>
CandidateList_t
;
//!< container of SPFVertex pointers
166
CandidateList_t
m_candidates
;
//!< SPFVertex candidates
167
168
/**
169
* \brief Stream insertion operator.
170
*
171
* \param os the reference to the output stream
172
* \param q the CandidateQueue
173
* \returns the reference to the output stream
174
*/
175
friend
std::ostream&
operator<<
(std::ostream& os,
const
CandidateQueue
& q);
176
};
177
178
}
// namespace ns3
179
180
#endif
/* CANDIDATE_QUEUE_H */
ns3::CandidateQueue
A Candidate Queue used in routing calculations.
Definition
candidate-queue.h:42
ns3::CandidateQueue::CompareSPFVertex
static bool CompareSPFVertex(const SPFVertex *v1, const SPFVertex *v2)
return true if v1 < v2
Definition
candidate-queue.cc:174
ns3::CandidateQueue::operator<<
friend std::ostream & operator<<(std::ostream &os, const CandidateQueue &q)
Stream insertion operator.
Definition
candidate-queue.cc:48
ns3::CandidateQueue::Pop
SPFVertex * Pop()
Pop the Shortest Path First Vertex pointer at the top of the queue.
Definition
candidate-queue.cc:99
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:113
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:132
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:87
ns3::CandidateQueue::Reorder
void Reorder()
Reorders the Candidate Queue according to the priority scheme.
Definition
candidate-queue.cc:157
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:165
ns3::CandidateQueue::~CandidateQueue
virtual ~CandidateQueue()
Destroy an SPF Candidate Queue and release any resources held by the contents.
Definition
candidate-queue.cc:68
ns3::CandidateQueue::m_candidates
CandidateList_t m_candidates
SPFVertex candidates.
Definition
candidate-queue.h:166
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:75
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:139
ns3::CandidateQueue::CandidateQueue
CandidateQueue()
Create an empty SPF Candidate Queue.
Definition
candidate-queue.cc:62
ns3::CandidateQueue::Empty
bool Empty() const
Test the Candidate Queue to determine if it is empty.
Definition
candidate-queue.cc:125
ns3::Ipv4Address
Ipv4 addresses are stored in host order in this class.
Definition
ipv4-address.h:31
ns3::SPFVertex
Vertex used in shortest path first (SPF) computations.
Definition
global-route-manager-impl.h:60
uint32_t
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
src
internet
model
candidate-queue.h
Generated on Fri Nov 8 2024 13:59:00 for ns-3 by
1.11.0