Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(1650)

Unified Diff: src/common/nix-vector.cc

Issue 117046: Ns-3 Nix-vector Routing (Closed)
Patch Set: Documentation of NixVector in packet Created 14 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Please Sign in to add in-line comments.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/common/nix-vector.h ('k') | src/common/packet.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/common/nix-vector.cc
===================================================================
new file mode 100644
--- /dev/null
+++ b/src/common/nix-vector.cc
@@ -0,0 +1,419 @@
+/* -*- 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)
+ {
+ 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;
+}
+
+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_reverse_iterator rIter;
+ for (rIter = m_nixVector.rbegin (); rIter != m_nixVector.rend (); rIter++)
+ {
+ uint32_t numBits = BitCount (*rIter);
+
+ // all this work just to get the nix
+ // vector to print out neat
+
+ // if it's not the first entry in the vector,
+ // we may have to add some zeros and fill
+ // out the vector
+ if (m_totalBitSize > ((sizeof (uint32_t)*8) * i))
+ {
+ PrintDec2BinNixFill (*rIter,numBits,os);
+ }
+ else if (m_totalBitSize%32 == 0)
+ {
+ PrintDec2BinNix (*rIter,32,os);
+ }
+ else
+ {
+ PrintDec2BinNix (*rIter,m_totalBitSize%32,os);
+ }
+
+ i--;
+
+ if (i > 0)
+ {
+ os << "--";
+ }
+ }
+}
+
+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 (essentially, log2(numberOfNeighbors-1)
+ uint32_t bitCount = 0;
+
+ if (numberOfNeighbors < 2)
+ {
+ return 1;
+ }
+ else
+ {
+ for (numberOfNeighbors -= 1; numberOfNeighbors != 0; numberOfNeighbors >>= 1)
+ {
+ bitCount++;
+ }
+ return bitCount;
+ }
+}
+
+void
+NixVector::PrintDec2BinNix (uint32_t decimalNum, uint32_t bitCount, std::ostream &os) const
+{
+ if(decimalNum == 0)
+ {
+ for (; bitCount > 0; bitCount--)
+ {
+ os << 0;
+ }
+ return;
+ }
+ if(decimalNum == 1)
+ {
+ for (; bitCount > 1; bitCount--)
+ {
+ os << 0;
+ }
+ os << 1;
+ }
+ else
+ {
+ PrintDec2BinNix (decimalNum / 2,bitCount-1, os);
+ os << decimalNum % 2;
+ }
+}
+
+void
+NixVector::PrintDec2BinNixFill (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
+ {
+ PrintDec2BinNixFill (decimalNum / 2, bitCount, os);
+ os << decimalNum % 2;
+ }
+}
+
+} // namespace ns3
« no previous file with comments | « src/common/nix-vector.h ('k') | src/common/packet.h » ('j') | no next file with comments »

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b