A Discrete-Event Network Simulator
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
17namespace ns3
18{
19
20class 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 */
42{
43 public:
44 /**
45 * @brief Create an empty SPF Candidate Queue.
46 *
47 * @see SPFVertex
48 */
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
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 */
A Candidate Queue used in routing calculations.
static bool CompareSPFVertex(const SPFVertex *v1, const SPFVertex *v2)
return true if v1 < v2
friend std::ostream & operator<<(std::ostream &os, const CandidateQueue &q)
Stream insertion operator.
SPFVertex * Pop()
Pop the Shortest Path First Vertex pointer at the top of the queue.
CandidateQueue(const CandidateQueue &)=delete
SPFVertex * Top() const
Return the Shortest Path First Vertex pointer at the top of the queue.
uint32_t Size() const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.
void Push(SPFVertex *vNew)
Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme.
void Reorder()
Reorders the Candidate Queue according to the priority scheme.
CandidateQueue & operator=(const CandidateQueue &)=delete
std::list< SPFVertex * > CandidateList_t
container of SPFVertex pointers
virtual ~CandidateQueue()
Destroy an SPF Candidate Queue and release any resources held by the contents.
CandidateList_t m_candidates
SPFVertex candidates.
void Clear()
Empty the Candidate Queue and release all of the resources associated with the Shortest Path First Ve...
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
CandidateQueue()
Create an empty SPF Candidate Queue.
bool Empty() const
Test the Candidate Queue to determine if it is empty.
Ipv4 addresses are stored in host order in this class.
Vertex used in shortest path first (SPF) computations.
Every class exported by the ns3 library is enclosed in the ns3 namespace.