Ns-3 Nix-vector Routing

src/common/nix-vector.cc

+/* -*-  Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2009 The Georgia Institute of Technology 
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Authors: Josh Pelkey <jpelkey@gatech.edu>
+ */
+
+#include "ns3/log.h"
+
+#include "nix-vector.h"
+
+NS_LOG_COMPONENT_DEFINE ("NixVector");
+
+namespace ns3 {
+
+NS_OBJECT_ENSURE_REGISTERED (NixVector);
+
+typedef std::vector<uint32_t> NixBits_t;
+
+NixVector::NixVector ()
+  : m_nixVector (0),m_used (0),m_currentVectorBitSize (0),m_totalBitSize (0)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  m_nixVector.push_back (0);
+}
+
+NixVector::~NixVector ()
+{
+  NS_LOG_FUNCTION_NOARGS ();
+}
+
+Ptr<NixVector>
+NixVector::Copy (void) const
+{
+  // we need to invoke the copy constructor directly
+  // rather than calling Create because the copy constructor
+  // is private.
+  return Ptr<NixVector> (new NixVector (*this), false);
+}
+
+NixVector::NixVector (const NixVector &o)
+  : m_nixVector (o.m_nixVector),
+    m_used (o.m_used),
+    m_currentVectorBitSize (o.m_currentVectorBitSize),
+    m_totalBitSize (o.m_totalBitSize)
+{}
+
+NixVector &
+NixVector::operator = (const NixVector &o)
+{
+  if (this == &o)
+  {
+    return *this;
+  }
+  m_nixVector = o.m_nixVector;
+  m_used = o.m_used;
+  m_currentVectorBitSize = o.m_currentVectorBitSize;
+  m_totalBitSize = o.m_totalBitSize;
+  return *this;
+}
+
+TypeId
+NixVector::GetTypeId(void)
+{
+  static TypeId tid = TypeId ("ns3::NixVector")
+   .SetParent<Object> ()
+   .AddConstructor<NixVector> ()
+    ;
+
+  return tid;
+}
+
+std::ostream & operator << (std::ostream &os, const NixVector &nix)
+{
+  nix.DumpNixVector (os); 
+  return os;
+}
+
+void
+NixVector::AddNeighborIndex (uint32_t newBits, uint32_t numberOfBits)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  if (numberOfBits > 32)
+    NS_FATAL_ERROR ("Can't add more than 32 bits to a nix-vector at one time");
+
+  // Check to see if the number
+  // of new bits forces the creation of 
+  // a new entry into the NixVector vector
+  // i.e., we will overflow int o.w.
+  if (m_currentVectorBitSize + numberOfBits > 32) 
+  {
+    if (m_currentVectorBitSize == 32)
+    {
+      // can't add any more to this vector, so 
+      // start a new one
+      m_nixVector.push_back(newBits);
+
+      // also reset number of bits in
+      // m_currentVectorBitSize
+      // because we are working with a new 
+      // entry in the vector
+      m_currentVectorBitSize = numberOfBits;
+      m_totalBitSize += numberOfBits;
+    }
+    else
+    {
+      // Put what we can in the remaining portion of the 
+      // vector entry
+      uint32_t tempBits = newBits;
+      tempBits = newBits << m_currentVectorBitSize;
+      tempBits |= m_nixVector.back ();
+      m_nixVector.back () = tempBits;
+
+      // Now start a new vector entry
+      // and push the remaining bits 
+      // there
+      newBits = newBits >> (32 - m_currentVectorBitSize);
+      m_nixVector.push_back (newBits);
+    
+      // also reset number of bits in
+      // m_currentVectorBitSize
+      // because we are working with a new 
+      // entry in the vector
+      m_currentVectorBitSize = (numberOfBits - (32 - m_currentVectorBitSize));
+      m_totalBitSize += numberOfBits;
+    }
+  }
+  else
+  {
+    // Shift over the newbits by the
+    // number of current bits.  This allows 
+    // us to logically OR with the present 
+    // NixVector, resulting in the new 
+    // NixVector
+    newBits = newBits << m_currentVectorBitSize;
+    newBits |= m_nixVector.back ();
+  
+    // Now insert the new NixVector and 
+    // increment number of bits for
+    // m_currentVectorBitSize and m_totalBitSize
+    // accordingly 
+    m_nixVector.back () = newBits;
+    m_currentVectorBitSize += numberOfBits;
+    m_totalBitSize += numberOfBits;
+  }
+}
+
+uint32_t
+NixVector::ExtractNeighborIndex (uint32_t numberOfBits)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  if (numberOfBits > 32)

[craigdo, 2009/09/11 22:38:17]

Coding standard says to add braces even if single statement

[jpelkey, 2009/09/12 18:34:14]

On 2009/09/11 22:38:17, craigdo wrote:
> Coding standard says to add braces even if single statement

Done.

+    NS_FATAL_ERROR ("Can't extract more than 32 bits to a nix-vector at one time");
+
+  uint32_t vectorIndex = 0;
+  uint32_t extractedBits = 0;
+  uint32_t totalRemainingBits = GetRemainingBits ();
+
+  if (numberOfBits > totalRemainingBits)
+  {
+    NS_FATAL_ERROR ("You've tried to extract too many bits of the Nix-vector, " << this << ". NumberBits: " 
+                     << numberOfBits << " Remaining: " << totalRemainingBits);
+  }
+
+  if (numberOfBits <= 0)
+  {
+    NS_FATAL_ERROR ("You've specified a number of bits for Nix-vector <= 0!");
+  }
+
+  // First determine where in the NixVector 
+  // vector we need to extract which depends
+  // on the number of used bits and the total
+  // number of bits
+  vectorIndex = ((totalRemainingBits-1) / 32);
+
+  // Next, determine if this extraction will
+  // span multiple vector entries
+  if (vectorIndex > 0) // we could span more than one
+  {
+    if ((numberOfBits-1) > ((totalRemainingBits-1) % 32)) // we do span more than one
+    {
+
+      extractedBits = m_nixVector.at (vectorIndex) << (32 - (totalRemainingBits % 32));
+      extractedBits = extractedBits >> ((32 - (totalRemainingBits % 32)) - (numberOfBits - (totalRemainingBits % 32)));
+
+      extractedBits |= (m_nixVector.at (vectorIndex-1) >> (32 - (numberOfBits - (totalRemainingBits % 32))));
+      m_used += numberOfBits;
+
+      return extractedBits;
+    }
+  }
+
+  // we don't span more than one
+  extractedBits = m_nixVector.at (vectorIndex) << (32 - (totalRemainingBits % 32));
+  extractedBits = extractedBits >> (32 - (numberOfBits));
+
+  m_used += numberOfBits;
+
+  return extractedBits;
+
+}
+
+NixBits_t
+NixVector::GetNixVector (void)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+  
+  return m_nixVector;
+}
+
+uint32_t
+NixVector::GetSerializedSize (void) const
+{
+  uint32_t totalSizeInBytes;
+  totalSizeInBytes = sizeof (m_used) + sizeof (m_currentVectorBitSize) + 
+                     sizeof (m_totalBitSize) + (4 * m_nixVector.size ());
+
+  // add four to this to account 
+  // for the nix-vector length 
+  // entry
+  return totalSizeInBytes+4;
+}
+
+void
+NixVector::Serialize (Buffer::Iterator i, uint32_t size) const
+{
+  uint32_t bytesWritten = 0;
+
+  i.WriteU32 (size);
+  bytesWritten += 4;
+
+  i.WriteU32 (m_used);
+  bytesWritten += 4;
+
+  i.WriteU32 (m_currentVectorBitSize);
+  bytesWritten += 4;
+
+  i.WriteU32 (m_totalBitSize);
+  bytesWritten += 4;
+
+  for (uint32_t j = 0; j < m_nixVector.size (); j++)
+  {
+    i.WriteU32 (m_nixVector.at(j));
+    bytesWritten += 4;
+  }
+
+  NS_ASSERT (bytesWritten == size);
+}
+
+uint32_t
+NixVector::Deserialize (Buffer::Iterator i)
+{
+  NS_LOG_FUNCTION (this);
+  uint32_t totalSize = i.ReadU32 ();
+  uint32_t size = totalSize;
+  size -= 4;
+
+  NS_ASSERT (size >= 4);
+  m_used = i.ReadU32 ();
+  size -=4;
+
+  NS_ASSERT (size >= 4);
+  m_currentVectorBitSize = i.ReadU32 ();
+  size -=4;
+
+  NS_ASSERT (size >= 4);
+  m_totalBitSize = i.ReadU32 ();
+  size -=4;
+
+  // make sure the nix-vector
+  // is empty
+  m_nixVector.clear ();
+  while (size > 0)
+  {
+    NS_ASSERT (size >= 4);
+    m_nixVector.push_back (i.ReadU32 ());
+    size -=4;
+  }
+
+  NS_ASSERT (size == 0);
+  return totalSize;
+}
+
+void
+NixVector::DumpNixVector (std::ostream &os) const
+{
+  NS_LOG_FUNCTION_NOARGS ();
+  uint32_t i = m_nixVector.size ();
+  std::vector<uint32_t>::const_iterator iter = m_nixVector.end ();
+  do

[craigdo, 2009/09/11 22:38:17]

I'm curious why this isn't a for loop.  That would seem more natural.  What
happens if this list is empty?  Can it ever be?

[jpelkey, 2009/09/12 18:34:14]

On 2009/09/11 22:38:17, craigdo wrote:
> I'm curious why this isn't a for loop.  That would seem more natural.  What
> happens if this list is empty?  Can it ever be?

I was iterating in reverse and "do, while" was just the first thing that came to
my mind.  I changed this to a for loop with a reverse iterator.  Not an issue
now, but to answer your question, the list can't be empty, NixVector constructor
pushes back an entry.

+  {
+    iter--;
+    
+    // all this work just to get the nix 
+    // vector to print out neat
+    if (m_totalBitSize == 32)

[craigdo, 2009/09/11 22:38:17]

Coding standard says use {}.  Many more instances follow this one.

[jpelkey, 2009/09/12 18:34:14]

On 2009/09/11 22:38:17, craigdo wrote:
> Coding standard says use {}.  Many more instances follow this one.

Done.

+      PrintDec2BinNixFill (*iter,32,os);
+    else if (m_totalBitSize > ((sizeof (uint32_t)*8) * i))
+      PrintDec2BinNix (*iter,BitCount (*iter),os);
+    else
+      PrintDec2BinNixFill (*iter,m_totalBitSize%32,os);
+
+    i--;
+
+    if (iter != m_nixVector.begin ())
+      os << "--";
+
+  } while (iter != m_nixVector.begin ());
+
+}
+
+uint32_t 
+NixVector::GetRemainingBits (void)
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  return (m_totalBitSize - m_used);
+}
+
+uint32_t
+NixVector::BitCount (uint32_t numberOfNeighbors) const
+{
+  NS_LOG_FUNCTION_NOARGS ();
+
+  // Given the numberOfNeighbors, return the number 
+  // of bits needed (essentailly, log2(numberOfNeighbors-1)

[craigdo, 2009/09/11 22:38:17]

essentially

[jpelkey, 2009/09/12 18:34:14]

On 2009/09/11 22:38:17, craigdo wrote:
> essentially

Done.

+  uint32_t bitCount = 0;
+  
+  if (numberOfNeighbors < 2) 
+    return 1;
+  else
+  {
+    for (numberOfNeighbors -= 1; numberOfNeighbors != 0; numberOfNeighbors >>= 1)
+      bitCount++;
+
+    return bitCount;
+  }
+}
+
+void
+NixVector::PrintDec2BinNixFill (uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
+{
+  if(decimalNum == 0)
+  {
+    os << 0;
+    return;
+  }
+  if(decimalNum == 1)
+  {
+    for (; bitCount > 1; bitCount--)
+      os << 0;
+
+    os << 1;
+  }
+  else
+  {
+    PrintDec2BinNixFill (decimalNum / 2,bitCount-1, os);
+    os << decimalNum % 2;
+  }
+}
+
+void
+NixVector::PrintDec2BinNix (uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
+{
+  if(decimalNum == 0)
+  {
+    os << 0;
+    return;
+  }
+  if(decimalNum == 1)
+  {
+    // check to see if we need to 
+    // print out some zeros at the 
+    // beginning of the nix vector
+    if ((uint32_t)(sizeof (uint32_t)*8) > bitCount)
+    {
+      for (uint32_t i = ((sizeof (uint32_t)*8)-bitCount); i > 0; i--)
+        os << 0;
+    }
+
+    os << 1;
+  }
+  else
+  {
+    PrintDec2BinNix (decimalNum / 2, bitCount, os);
+    os << decimalNum % 2;
+  }
+}

[craigdo, 2009/09/11 22:38:17]

It would be nice to see some unit tests for this.

[jpelkey, 2009/09/12 18:34:14]

On 2009/09/11 22:38:17, craigdo wrote:
> It would be nice to see some unit tests for this.

I will start putting some together.

+} // namespace ns3