A Discrete-Event Network Simulator
API
nix-vector.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2009 The Georgia Institute of Technology
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Authors: Josh Pelkey <jpelkey@gatech.edu>
19  */
20 
21 #include "ns3/log.h"
22 #include "ns3/fatal-error.h"
23 
24 #include "nix-vector.h"
25 
26 namespace ns3 {
27 
29 
30 typedef std::vector<uint32_t> NixBits_t;
31 
33  : m_nixVector (0),
34  m_used (0),
35  m_currentVectorBitSize (0),
36  m_totalBitSize (0)
37 {
38  NS_LOG_FUNCTION (this);
39 
40  m_nixVector.push_back (0);
41 }
42 
44 {
45  NS_LOG_FUNCTION (this);
46 }
47 
49  : m_nixVector (o.m_nixVector),
50  m_used (o.m_used),
51  m_currentVectorBitSize (o.m_currentVectorBitSize),
52  m_totalBitSize (o.m_totalBitSize)
53 {
54 }
55 
56 NixVector &
58 {
59  if (this == &o)
60  {
61  return *this;
62  }
64  m_used = o.m_used;
67  return *this;
68 }
69 
71 NixVector::Copy (void) const
72 {
73  NS_LOG_FUNCTION (this);
74  // we need to invoke the copy constructor directly
75  // rather than calling Create because the copy constructor
76  // is private.
77  return Ptr<NixVector> (new NixVector (*this), false);
78 }
79 
80 /* For printing the nix vector */
81 std::ostream & operator << (std::ostream &os, const NixVector &nix)
82 {
83  nix.DumpNixVector (os);
84  return os;
85 }
86 
87 void
88 NixVector::AddNeighborIndex (uint32_t newBits, uint32_t numberOfBits)
89 {
90  NS_LOG_FUNCTION (this << newBits << numberOfBits);
91 
92  if (numberOfBits > 32)
93  {
94  NS_FATAL_ERROR ("Can't add more than 32 bits to a nix-vector at one time");
95  }
96 
97  // Check to see if the number
98  // of new bits forces the creation of
99  // a new entry into the NixVector vector
100  // i.e., we will overflow int o.w.
101  if (m_currentVectorBitSize + numberOfBits > 32)
102  {
103  if (m_currentVectorBitSize == 32)
104  {
105  // can't add any more to this vector, so
106  // start a new one
107  m_nixVector.push_back (newBits);
108 
109  // also reset number of bits in
110  // m_currentVectorBitSize
111  // because we are working with a new
112  // entry in the vector
113  m_currentVectorBitSize = numberOfBits;
114  m_totalBitSize += numberOfBits;
115  }
116  else
117  {
118  // Put what we can in the remaining portion of the
119  // vector entry
120  uint32_t tempBits = newBits;
121  tempBits = newBits << m_currentVectorBitSize;
122  tempBits |= m_nixVector.back ();
123  m_nixVector.back () = tempBits;
124 
125  // Now start a new vector entry
126  // and push the remaining bits
127  // there
128  newBits = newBits >> (32 - m_currentVectorBitSize);
129  m_nixVector.push_back (newBits);
130 
131  // also reset number of bits in
132  // m_currentVectorBitSize
133  // because we are working with a new
134  // entry in the vector
135  m_currentVectorBitSize = (numberOfBits - (32 - m_currentVectorBitSize));
136  m_totalBitSize += numberOfBits;
137  }
138  }
139  else
140  {
141  // Shift over the newbits by the
142  // number of current bits. This allows
143  // us to logically OR with the present
144  // NixVector, resulting in the new
145  // NixVector
146  newBits = newBits << m_currentVectorBitSize;
147  newBits |= m_nixVector.back ();
148 
149  // Now insert the new NixVector and
150  // increment number of bits for
151  // m_currentVectorBitSize and m_totalBitSize
152  // accordingly
153  m_nixVector.back () = newBits;
154  m_currentVectorBitSize += numberOfBits;
155  m_totalBitSize += numberOfBits;
156  }
157 }
158 
159 uint32_t
160 NixVector::ExtractNeighborIndex (uint32_t numberOfBits)
161 {
162  NS_LOG_FUNCTION (this << numberOfBits);
163 
164  if (numberOfBits > 32)
165  {
166  NS_FATAL_ERROR ("Can't extract more than 32 bits to a nix-vector at one time");
167  }
168 
169  uint32_t vectorIndex = 0;
170  uint32_t extractedBits = 0;
171  uint32_t totalRemainingBits = GetRemainingBits ();
172 
173  if (numberOfBits > totalRemainingBits)
174  {
175  NS_FATAL_ERROR ("You've tried to extract too many bits of the Nix-vector, " << this << ". NumberBits: "
176  << numberOfBits << " Remaining: " << totalRemainingBits);
177  }
178 
179  if (numberOfBits <= 0)
180  {
181  NS_FATAL_ERROR ("You've specified a number of bits for Nix-vector <= 0!");
182  }
183 
184  // First determine where in the NixVector
185  // vector we need to extract which depends
186  // on the number of used bits and the total
187  // number of bits
188  vectorIndex = ((totalRemainingBits-1) / 32);
189 
190  // Next, determine if this extraction will
191  // span multiple vector entries
192  if (vectorIndex > 0) // we could span more than one
193  {
194  if ((numberOfBits-1) > ((totalRemainingBits-1) % 32)) // we do span more than one
195  {
196  extractedBits = m_nixVector.at (vectorIndex) << (32 - (totalRemainingBits % 32));
197  extractedBits = extractedBits >> ((32 - (totalRemainingBits % 32))
198  - (numberOfBits - (totalRemainingBits % 32)));
199  extractedBits |= (m_nixVector.at (vectorIndex-1)
200  >> (32 - (numberOfBits - (totalRemainingBits % 32))));
201  m_used += numberOfBits;
202  return extractedBits;
203  }
204  }
205 
206  // we don't span more than one
207  extractedBits = m_nixVector.at (vectorIndex) << (32 - (totalRemainingBits % 32));
208  extractedBits = extractedBits >> (32 - (numberOfBits));
209  m_used += numberOfBits;
210  return extractedBits;
211 }
212 
213 uint32_t
215 {
216  NS_LOG_FUNCTION (this);
217  uint32_t totalSizeInBytes = 0;
218  totalSizeInBytes = sizeof (m_used) + sizeof (m_currentVectorBitSize) +
219  sizeof (m_totalBitSize) + (4 * m_nixVector.size ());
220 
221  return totalSizeInBytes;
222 }
223 
224 uint32_t
225 NixVector::Serialize (uint32_t* buffer, uint32_t maxSize) const
226 {
227  NS_LOG_FUNCTION (this << buffer << maxSize);
228  uint32_t* p = buffer;
229  uint32_t size = 0;
230 
231  if (size + 4 <= maxSize)
232  {
233  size += 4;
234  // grab number of used bits
235  *p++ = m_used;
236  }
237  else
238  {
239  return 0;
240  }
241 
242  if (size + 4 <= maxSize)
243  {
244  size += 4;
245  // grab number of current used bits
246  // for the front vector
247  *p++ = m_currentVectorBitSize;
248  }
249  else
250  {
251  return 0;
252  }
253 
254  if (size + 4 <= maxSize)
255  {
256  size += 4;
257  // grab total bit size
258  *p++ = m_totalBitSize;
259  }
260  else
261  {
262  return 0;
263  }
264  for (uint32_t j = 0; j < m_nixVector.size (); j++)
265  {
266  if (size + 4 <= maxSize)
267  {
268  size += 4;
269  *p++ = m_nixVector.at (j);
270  }
271  else
272  {
273  return 0;
274  }
275  }
276 
277  // Serialized successfully
278  return 1;
279 }
280 
281 uint32_t
282 NixVector::Deserialize (const uint32_t* buffer, uint32_t size)
283 {
284  NS_LOG_FUNCTION (this << buffer << size);
285  const uint32_t* p = buffer;
286  uint32_t sizeCheck = size - 4;
287 
288  NS_ASSERT (sizeCheck >= 4);
289  m_used = *p++;
290  sizeCheck -= 4;
291 
292  NS_ASSERT (sizeCheck >= 4);
293  m_currentVectorBitSize = *p++;
294  sizeCheck -= 4;
295 
296  NS_ASSERT (sizeCheck >= 4);
297  m_totalBitSize = *p++;
298  sizeCheck -= 4;
299 
300  // make sure the nix-vector
301  // is empty
302  m_nixVector.clear ();
303  while (sizeCheck > 0)
304  {
305  NS_ASSERT (sizeCheck >= 4);
306  uint32_t nix = *p++;
307  m_nixVector.push_back (nix);
308  sizeCheck -= 4;
309  }
310 
311  NS_ASSERT (sizeCheck == 0);
312 
313  // return zero if an entire nix-vector was
314  // not deserialized
315  return (sizeCheck != 0) ? 0 : 1;
316 }
317 
318 void
319 NixVector::DumpNixVector (std::ostream &os) const
320 {
321  NS_LOG_FUNCTION (this << &os);
322  uint32_t i = m_nixVector.size ();
323  std::vector<uint32_t>::const_reverse_iterator rIter;
324  for (rIter = m_nixVector.rbegin (); rIter != m_nixVector.rend (); rIter++)
325  {
326  uint32_t numBits = BitCount (*rIter);
327 
328  // all this work just to get the nix
329  // vector to print out neat
330 
331  // if it's not the first entry in the vector,
332  // we may have to add some zeros and fill
333  // out the vector
334  if (m_totalBitSize > ((sizeof (uint32_t)*8) * i))
335  {
336  PrintDec2BinNixFill (*rIter,numBits,os);
337  }
338  else if (m_totalBitSize%32 == 0)
339  {
340  PrintDec2BinNix (*rIter,32,os);
341  }
342  else
343  {
344  PrintDec2BinNix (*rIter,m_totalBitSize%32,os);
345  }
346 
347  i--;
348 
349  if (i > 0)
350  {
351  os << "--";
352  }
353  }
354 }
355 
356 uint32_t
358 {
359  NS_LOG_FUNCTION (this);
360 
361  return (m_totalBitSize - m_used);
362 }
363 
364 uint32_t
365 NixVector::BitCount (uint32_t numberOfNeighbors) const
366 {
367  NS_LOG_FUNCTION (this << numberOfNeighbors);
368 
369  // Given the numberOfNeighbors, return the number
370  // of bits needed (essentially, log2(numberOfNeighbors-1)
371  uint32_t bitCount = 0;
372 
373  if (numberOfNeighbors < 2)
374  {
375  return 1;
376  }
377  else
378  {
379  for (numberOfNeighbors -= 1; numberOfNeighbors != 0; numberOfNeighbors >>= 1)
380  {
381  bitCount++;
382  }
383  return bitCount;
384  }
385 }
386 
387 void
388 NixVector::PrintDec2BinNix (uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
389 {
390  NS_LOG_FUNCTION (this << decimalNum << bitCount << &os);
391  if(decimalNum == 0)
392  {
393  for (; bitCount > 0; bitCount--)
394  {
395  os << 0;
396  }
397  return;
398  }
399  if(decimalNum == 1)
400  {
401  for (; bitCount > 1; bitCount--)
402  {
403  os << 0;
404  }
405  os << 1;
406  }
407  else
408  {
409  PrintDec2BinNix (decimalNum / 2,bitCount-1, os);
410  os << decimalNum % 2;
411  }
412 }
413 
414 void
415 NixVector::PrintDec2BinNixFill (uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
416 {
417  NS_LOG_FUNCTION (this << decimalNum << bitCount << &os);
418  if(decimalNum == 0)
419  {
420  os << 0;
421  return;
422  }
423  if(decimalNum == 1)
424  {
425  // check to see if we need to
426  // print out some zeros at the
427  // beginning of the nix vector
428  if ((uint32_t)(sizeof (uint32_t)*8) > bitCount)
429  {
430  for (uint32_t i = ((sizeof (uint32_t)*8)-bitCount); i > 0; i--)
431  {
432  os << 0;
433  }
434  }
435  os << 1;
436  }
437  else
438  {
439  PrintDec2BinNixFill (decimalNum / 2, bitCount, os);
440  os << decimalNum % 2;
441  }
442 }
443 
444 } // namespace ns3
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
Neighbor-index data structure for nix-vector routing.
Definition: nix-vector.h:63
NixVector & operator=(const NixVector &o)
Definition: nix-vector.cc:57
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file...
Definition: assert.h:67
void PrintDec2BinNix(uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
Internal for pretty printing of nix-vector (no fill)
Definition: nix-vector.cc:388
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
#define NS_FATAL_ERROR(msg)
Report a fatal error with a message and terminate.
Definition: fatal-error.h:162
uint32_t m_totalBitSize
A counter of how total bits are in the nix-vector.
Definition: nix-vector.h:190
uint32_t GetRemainingBits(void)
Definition: nix-vector.cc:357
uint32_t ExtractNeighborIndex(uint32_t numberOfBits)
Definition: nix-vector.cc:160
uint32_t Serialize(uint32_t *buffer, uint32_t maxSize) const
Definition: nix-vector.cc:225
NixBits_t m_nixVector
the actual nix-vector
Definition: nix-vector.h:175
uint32_t GetSerializedSize(void) const
Definition: nix-vector.cc:214
std::ostream & operator<<(std::ostream &os, const Angles &a)
print a struct Angles to output
Definition: angles.cc:42
void DumpNixVector(std::ostream &os) const
Print the NixVector.
Definition: nix-vector.cc:319
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::vector< uint32_t > NixBits_t
typedef for the nixVector
Definition: nix-vector.cc:28
Ptr< NixVector > Copy(void) const
Definition: nix-vector.cc:71
uint32_t BitCount(uint32_t numberOfNeighbors) const
Definition: nix-vector.cc:365
void PrintDec2BinNixFill(uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
Internal for pretty printing of nix-vector (fill)
Definition: nix-vector.cc:415
uint32_t Deserialize(const uint32_t *buffer, uint32_t size)
Definition: nix-vector.cc:282
uint32_t m_used
For tracking where we are in the nix-vector.
Definition: nix-vector.h:176
void AddNeighborIndex(uint32_t newBits, uint32_t numberOfBits)
Definition: nix-vector.cc:88
uint32_t m_currentVectorBitSize
For tracking how many bits we have used in the current vector entry.
Definition: nix-vector.h:184