A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
nix-vector.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2009 The Georgia Institute of Technology
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Authors: Josh Pelkey <jpelkey@gatech.edu>
7 */
8
9#include "nix-vector.h"
10
11#include "ns3/fatal-error.h"
12#include "ns3/log.h"
13
14namespace ns3
15{
16
17NS_LOG_COMPONENT_DEFINE("NixVector");
18
19typedef std::vector<uint32_t> NixBits_t; //!< typedef for the nixVector
20
22 : m_nixVector(0),
23 m_used(0),
24 m_totalBitSize(0),
25 m_epoch(0)
26{
27 NS_LOG_FUNCTION(this);
28}
29
34
36 : m_nixVector(o.m_nixVector),
37 m_used(o.m_used),
38 m_totalBitSize(o.m_totalBitSize),
39 m_epoch(o.m_epoch)
40{
41}
42
45{
46 if (this == &o)
47 {
48 return *this;
49 }
51 m_used = o.m_used;
53 m_epoch = o.m_epoch;
54 return *this;
55}
56
59{
60 NS_LOG_FUNCTION(this);
61 // we need to invoke the copy constructor directly
62 // rather than calling Create because the copy constructor
63 // is private.
64 return Ptr<NixVector>(new NixVector(*this), false);
65}
66
67/* For printing the nix vector */
68std::ostream&
69operator<<(std::ostream& os, const NixVector& nix)
70{
71 nix.DumpNixVector(os);
72 os << " (" << nix.GetRemainingBits() << " bits left)";
73 return os;
74}
75
76void
78{
79 NS_LOG_FUNCTION(this << newBits << numberOfBits);
80
81 if (numberOfBits > 32)
82 {
83 NS_FATAL_ERROR("Can't add more than 32 bits to a nix-vector at one time");
84 }
85
86 // This can be in the range [0,31]
87 uint32_t currentVectorBitSize = m_totalBitSize % 32;
88
89 if (currentVectorBitSize == 0)
90 {
91 m_nixVector.push_back(0);
92 }
93
94 // Check to see if the number
95 // of new bits forces the creation of
96 // a new entry into the NixVector vector
97 // i.e., we will overflow int o.w.
98 if (currentVectorBitSize + numberOfBits > 32)
99 {
100 // Put what we can in the remaining portion of the
101 // vector entry
102 uint32_t tempBits = newBits;
103 tempBits = newBits << currentVectorBitSize;
104 tempBits |= m_nixVector.back();
105 m_nixVector.back() = tempBits;
106
107 // Now start a new vector entry
108 // and push the remaining bits
109 // there
110 newBits = newBits >> (32 - currentVectorBitSize);
111 m_nixVector.push_back(newBits);
112 }
113 else
114 {
115 // Shift over the newbits by the
116 // number of current bits. This allows
117 // us to logically OR with the present
118 // NixVector, resulting in the new
119 // NixVector
120 newBits = newBits << currentVectorBitSize;
121 newBits |= m_nixVector.back();
122
123 // Now insert the new NixVector and
124 // increment number of bits for
125 // currentVectorBitSize and m_totalBitSize
126 // accordingly
127 m_nixVector.back() = newBits;
128 }
129 m_totalBitSize += numberOfBits;
130}
131
134{
135 NS_LOG_FUNCTION(this << numberOfBits);
136
137 if (numberOfBits > 32)
138 {
139 NS_FATAL_ERROR("Can't extract more than 32 bits to a nix-vector at one time");
140 }
141
142 uint32_t vectorIndex = 0;
143 uint32_t extractedBits = 0;
144 uint32_t totalRemainingBits = GetRemainingBits();
145
146 if (numberOfBits > totalRemainingBits)
147 {
148 NS_FATAL_ERROR("You've tried to extract too many bits of the Nix-vector, "
149 << this << ". NumberBits: " << numberOfBits
150 << " Remaining: " << totalRemainingBits);
151 }
152
153 if (numberOfBits <= 0)
154 {
155 NS_FATAL_ERROR("You've specified a number of bits for Nix-vector <= 0!");
156 }
157
158 // First determine where in the NixVector
159 // vector we need to extract which depends
160 // on the number of used bits and the total
161 // number of bits
162 vectorIndex = ((totalRemainingBits - 1) / 32);
163
164 // Next, determine if this extraction will
165 // span multiple vector entries
166 if (vectorIndex > 0) // we could span more than one
167 {
168 if ((numberOfBits - 1) > ((totalRemainingBits - 1) % 32)) // we do span more than one
169 {
170 extractedBits = m_nixVector.at(vectorIndex) << (32 - (totalRemainingBits % 32));
171 extractedBits = extractedBits >> ((32 - (totalRemainingBits % 32)) -
172 (numberOfBits - (totalRemainingBits % 32)));
173 extractedBits |= (m_nixVector.at(vectorIndex - 1) >>
174 (32 - (numberOfBits - (totalRemainingBits % 32))));
175 m_used += numberOfBits;
176 return extractedBits;
177 }
178 }
179
180 // we don't span more than one
181 extractedBits = m_nixVector.at(vectorIndex) << (32 - (totalRemainingBits % 32));
182 extractedBits = extractedBits >> (32 - (numberOfBits));
183 m_used += numberOfBits;
184 return extractedBits;
185}
186
189{
190 NS_LOG_FUNCTION(this);
191
192 if (m_totalBitSize == 0)
193 {
194 return sizeof(m_totalBitSize);
195 }
196
197 return sizeof(m_used) + sizeof(m_totalBitSize) + (sizeof(uint32_t) * m_nixVector.size()) +
198 sizeof(m_epoch);
199}
200
203{
204 NS_LOG_FUNCTION(this << buffer << maxSize);
205 uint32_t* p = buffer;
206
207 if (maxSize < GetSerializedSize())
208 {
209 return 0;
210 }
211
212 *p++ = m_totalBitSize;
213
214 if (m_totalBitSize)
215 {
216 *p++ = m_used;
217 for (uint32_t j = 0; j < m_nixVector.size(); j++)
218 {
219 *p++ = m_nixVector.at(j);
220 }
221 *p++ = m_epoch;
222 }
223
224 return 1;
225}
226
229{
230 NS_LOG_FUNCTION(this << buffer << size);
231 const uint32_t* p = buffer;
232
233 NS_ASSERT_MSG(size >= sizeof(m_totalBitSize),
234 "NixVector minimum serialized length is " << sizeof(m_totalBitSize) << " bytes");
235 if (size < sizeof(m_totalBitSize))
236 {
237 // return zero if an entire nix-vector was
238 // not deserialized
239 return 0;
240 }
241
242 m_totalBitSize = *p++;
243
244 if (m_totalBitSize)
245 {
246 m_used = *p++;
247
248 // NixVector is packed in 32-bit unsigned ints.
249 uint32_t nixVectorLength = m_totalBitSize / 32;
250 nixVectorLength += (m_totalBitSize % 32) ? 1 : 0;
251
252 NS_ASSERT_MSG(size >= 16 + nixVectorLength,
253 "NixVector serialized length should have been " << 16 + nixVectorLength
254 << " but buffer is shorter");
255 if (size < 16 + nixVectorLength * 4)
256 {
257 // return zero if an entire nix-vector was
258 // not deserialized
259 return 0;
260 }
261
262 // make sure the nix-vector
263 // is empty
264 m_nixVector.clear();
265 for (uint32_t j = 0; j < nixVectorLength; j++)
266 {
267 uint32_t nix = *p++;
268 m_nixVector.push_back(nix);
269 }
270
271 m_epoch = *p++;
272 }
273
274 return GetSerializedSize();
275}
276
277void
278NixVector::DumpNixVector(std::ostream& os) const
279{
280 NS_LOG_FUNCTION(this << &os);
281
282 if (m_nixVector.empty())
283 {
284 os << "0";
285 return;
286 }
287
288 std::vector<uint32_t>::const_reverse_iterator rIter;
289 bool first = true;
290
291 for (rIter = m_nixVector.rbegin(); rIter != m_nixVector.rend();)
292 {
293 if (m_totalBitSize % 32 != 0 && first)
294 {
295 PrintDec2BinNix(*rIter, m_totalBitSize % 32, os);
296 }
297 else
298 {
299 PrintDec2BinNix(*rIter, 32, os);
300 }
301 first = false;
302
303 rIter++;
304 if (rIter != m_nixVector.rend())
305 {
306 os << "--";
307 }
308 }
309}
310
313{
314 NS_LOG_FUNCTION(this);
315
316 return (m_totalBitSize - m_used);
317}
318
320NixVector::BitCount(uint32_t numberOfNeighbors) const
321{
322 NS_LOG_FUNCTION(this << numberOfNeighbors);
323
324 // Given the numberOfNeighbors, return the number
325 // of bits needed (essentially, log2(numberOfNeighbors-1)
326 uint32_t bitCount = 0;
327
328 if (numberOfNeighbors < 2)
329 {
330 return 1;
331 }
332 else
333 {
334 for (numberOfNeighbors -= 1; numberOfNeighbors != 0; numberOfNeighbors >>= 1)
335 {
336 bitCount++;
337 }
338 return bitCount;
339 }
340}
341
342void
343NixVector::PrintDec2BinNix(uint32_t decimalNum, uint32_t bitCount, std::ostream& os) const
344{
345 NS_LOG_FUNCTION(this << decimalNum << bitCount << &os);
346 if (decimalNum == 0)
347 {
348 for (; bitCount > 0; bitCount--)
349 {
350 os << 0;
351 }
352 return;
353 }
354 if (decimalNum == 1)
355 {
356 for (; bitCount > 1; bitCount--)
357 {
358 os << 0;
359 }
360 os << 1;
361 }
362 else
363 {
364 PrintDec2BinNix(decimalNum / 2, bitCount - 1, os);
365 os << decimalNum % 2;
366 }
367}
368
369void
371{
372 m_epoch = epoch;
373}
374
377{
378 return m_epoch;
379}
380
381} // namespace ns3
Neighbor-index data structure for nix-vector routing.
Definition nix-vector.h:54
void AddNeighborIndex(uint32_t newBits, uint32_t numberOfBits)
Definition nix-vector.cc:77
uint32_t m_used
For tracking where we are in the nix-vector.
Definition nix-vector.h:178
uint32_t GetSerializedSize() const
uint32_t m_epoch
Epoch of the Nix-vector creation.
Definition nix-vector.h:186
uint32_t GetRemainingBits() const
NixVector & operator=(const NixVector &o)
Definition nix-vector.cc:44
uint32_t m_totalBitSize
A counter of how total bits are in the nix-vector.
Definition nix-vector.h:184
uint32_t Serialize(uint32_t *buffer, uint32_t maxSize) const
uint32_t ExtractNeighborIndex(uint32_t numberOfBits)
NixBits_t m_nixVector
the actual nix-vector
Definition nix-vector.h:177
void SetEpoch(uint32_t epoch)
Set the NixVector Epoch.
void DumpNixVector(std::ostream &os) const
Print the NixVector.
uint32_t Deserialize(const uint32_t *buffer, uint32_t size)
Ptr< NixVector > Copy() const
Definition nix-vector.cc:58
uint32_t BitCount(uint32_t numberOfNeighbors) const
void PrintDec2BinNix(uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
Internal for pretty printing of nix-vector (no fill)
uint32_t GetEpoch() const
Get the NixVector Epoch.
Smart pointer class similar to boost::intrusive_ptr.
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
Definition assert.h:75
#define NS_FATAL_ERROR(msg)
Report a fatal error with a message and terminate.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
Definition first.py:1
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::ostream & operator<<(std::ostream &os, const Angles &a)
Definition angles.cc:148
std::vector< uint32_t > NixBits_t
typedef for the nixVector
Definition nix-vector.cc:19