author | Craig Dowell <craigdo@ee.washington.edu> |
Wed, 18 Jul 2007 14:35:06 -0700 | |
changeset 1099 | 1e97c5a86b24 |
parent 1085 | c12d61407468 |
child 1101 | 6a34eab865da |
permissions | -rw-r--r-- |
1074 | 1 |
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
2 |
/* |
|
3 |
* This program is free software; you can redistribute it and/or modify |
|
4 |
* it under the terms of the GNU General Public License version 2 as |
|
5 |
* published by the Free Software Foundation; |
|
6 |
* |
|
7 |
* This program is distributed in the hope that it will be useful, |
|
8 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
9 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
|
10 |
* GNU General Public License for more details. |
|
11 |
* |
|
12 |
* You should have received a copy of the GNU General Public License |
|
13 |
* along with this program; if not, write to the Free Software |
|
14 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
|
15 |
*/ |
|
16 |
||
17 |
#ifndef CANDIDATE_QUEUE_H |
|
18 |
#define CANDIDATE_QUEUE_H |
|
19 |
||
20 |
#include <stdint.h> |
|
21 |
#include <list> |
|
22 |
#include "static-route-manager.h" |
|
23 |
||
24 |
namespace ns3 { |
|
25 |
||
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
26 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
27 |
* \brief a Candidate Queue used in static routing. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
28 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
29 |
* The CandidateQueue is used in the OSPF shortest path computations. It |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
30 |
* is a priority queue used to store candidates for the shortest path to a |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
31 |
* given network. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
32 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
33 |
* The queue holds Shortest Path First Vertex pointers and orders them |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
34 |
* according to the lowest value of the field m_distanceFromRoot. Remaining |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
35 |
* vertices are ordered according to increasing distance. This implements a |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
36 |
* priority queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
37 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
38 |
* Although a STL priority_queue almost does what we want, the requirement |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
39 |
* for a Find () operation, the dynamic nature of the data and the derived |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
40 |
* requirement for a Reorder () operation led us to implement this simple |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
41 |
* enhanced priority queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
42 |
*/ |
1074 | 43 |
class CandidateQueue |
44 |
{ |
|
45 |
public: |
|
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
46 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
47 |
* Create an empty SPF Candidate Queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
48 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
49 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
50 |
*/ |
1074 | 51 |
CandidateQueue (); |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
52 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
53 |
* Destroy an SPF Candidate Queue and release any resources held by the |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
54 |
* contents. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
55 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
56 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
57 |
*/ |
1074 | 58 |
virtual ~CandidateQueue (); |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
59 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
60 |
* Empty the Candidate Queue and release all of the resources associated |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
61 |
* with the Shortest Path First Vertex pointers in the queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
62 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
63 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
64 |
*/ |
1074 | 65 |
void Clear (void); |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
66 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
67 |
* Push a Shortest Path First Vertex pointer onto the queue according to the |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
68 |
* priority scheme. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
69 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
70 |
* On completion, the top of the queue will hold the Shortest Path First |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
71 |
* Vertex pointer that points to a vertex having lowest value of the field |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
72 |
* m_distanceFromRoot. Remaining vertices are ordered according to |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
73 |
* increasing distance. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
74 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
75 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
76 |
* @param vNew The Shortest Path First Vertex to add to the queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
77 |
*/ |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
78 |
void Push (SPFVertex *vNew); |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
79 |
/** |
1085
c12d61407468
delete vertices, fix candidate queue pop/top semantics
Craig Dowell <craigdo@ee.washington.edu>
parents:
1081
diff
changeset
|
80 |
* Pop the Shortest Path First Vertex pointer at the top of the queue. |
c12d61407468
delete vertices, fix candidate queue pop/top semantics
Craig Dowell <craigdo@ee.washington.edu>
parents:
1081
diff
changeset
|
81 |
* The caller is given the responsiblity for releasing the resources |
c12d61407468
delete vertices, fix candidate queue pop/top semantics
Craig Dowell <craigdo@ee.washington.edu>
parents:
1081
diff
changeset
|
82 |
* associated with the vertex. |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
83 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
84 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
85 |
* @see Top () |
1085
c12d61407468
delete vertices, fix candidate queue pop/top semantics
Craig Dowell <craigdo@ee.washington.edu>
parents:
1081
diff
changeset
|
86 |
* @returns The Shortest Path First Vertex pointer at the top of the queue. |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
87 |
*/ |
1085
c12d61407468
delete vertices, fix candidate queue pop/top semantics
Craig Dowell <craigdo@ee.washington.edu>
parents:
1081
diff
changeset
|
88 |
SPFVertex* Pop (void); |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
89 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
90 |
* Return the Shortest Path First Vertex pointer at the top of the queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
91 |
* This method does not pop the SPFVertex* off of the queue, it simply |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
92 |
* returns the pointer. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
93 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
94 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
95 |
* @see Pop () |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
96 |
* @returns The Shortest Path First Vertex pointer at the top of the queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
97 |
*/ |
1099
1e97c5a86b24
General cleanup -- const correctness, encapsulation, documentation, etc.
Craig Dowell <craigdo@ee.washington.edu>
parents:
1085
diff
changeset
|
98 |
SPFVertex* Top (void) const; |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
99 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
100 |
* Test the Candidate Queue to determine if it is empty. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
101 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
102 |
* @returns True if the queue is empty, false otherwise. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
103 |
*/ |
1099
1e97c5a86b24
General cleanup -- const correctness, encapsulation, documentation, etc.
Craig Dowell <craigdo@ee.washington.edu>
parents:
1085
diff
changeset
|
104 |
bool Empty (void) const; |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
105 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
106 |
* Return the number of Shortest Path First Vertex pointers presently |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
107 |
* stored in the Candidate Queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
108 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
109 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
110 |
* @returns The number of SPFVertex* pointers in the Candidate Queue. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
111 |
*/ |
1099
1e97c5a86b24
General cleanup -- const correctness, encapsulation, documentation, etc.
Craig Dowell <craigdo@ee.washington.edu>
parents:
1085
diff
changeset
|
112 |
uint32_t Size (void) const; |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
113 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
114 |
* Searches the Candidate Queue for a Shortest Path First Vertex pointer |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
115 |
* that points to a vertex having the given IP address. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
116 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
117 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
118 |
* @param addr The IP address to search for. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
119 |
* @returns The SPFVertex* pointer corresponding to the given IP address. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
120 |
*/ |
1099
1e97c5a86b24
General cleanup -- const correctness, encapsulation, documentation, etc.
Craig Dowell <craigdo@ee.washington.edu>
parents:
1085
diff
changeset
|
121 |
SPFVertex* Find (const Ipv4Address addr) const; |
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
122 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
123 |
* Reorders the Candidate Queue according to the priority scheme. On |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
124 |
* completion, the top of the queue will hold the Shortest Path First |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
125 |
* Vertex pointer that points to a vertex having lowest value of the field |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
126 |
* m_distanceFromRoot. Remaining vertices are ordered according to |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
127 |
* increasing distance. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
128 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
129 |
* This method is provided in case the values of m_distanceFromRoot change |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
130 |
* during the routing calculations. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
131 |
* |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
132 |
* @see SPFVertex |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
133 |
*/ |
1074 | 134 |
void Reorder (void); |
135 |
||
136 |
protected: |
|
137 |
typedef std::list<SPFVertex*> CandidateList_t; |
|
138 |
CandidateList_t m_candidates; |
|
139 |
||
140 |
private: |
|
1081
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
141 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
142 |
* Candidate Queue copy construction is disallowed (not implemented) to |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
143 |
* prevent the compiler from slipping in incorrect versions that don't |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
144 |
* properly deal with deep copies. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
145 |
*/ |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
146 |
CandidateQueue (CandidateQueue& sr); |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
147 |
/** |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
148 |
* Candidate Queue assignment operator is disallowed (not implemented) to |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
149 |
* prevent the compiler from slipping in incorrect versions that don't |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
150 |
* properly deal with deep copies. |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
151 |
*/ |
5a7c0124cb78
dox for candidate queue
Craig Dowell <craigdo@ee.washington.edu>
parents:
1075
diff
changeset
|
152 |
CandidateQueue& operator= (CandidateQueue& sr); |
1074 | 153 |
}; |
154 |
||
155 |
} // namespace ns3 |
|
156 |
||
157 |
#endif /* CANDIDATE_QUEUE_H */ |