// Support for NixVector routing// George F. Riley, Georgia Tech, Winter 2000#include <stdio.h>#include "nixvec.h"#ifndef TEST_NIXVEC// Constructor from existingNixVec::NixVec(NixVec* p) : m_used(0), m_alth(p->m_alth){  if (Lth() > NIX_BPW)    { // Need to allocate storage      m_pNV = new Nix_t[Lth() / NIX_BPW];      memcpy(m_pNV, p->m_pNV, Lth()/8);    }  else    { // Just use the pointer      m_pNV = p->m_pNV;    }}NixVec::~NixVec(){ // Destructor   if(0)printf("Hello from nixvec destructor\n");  if (Lth() > NIX_BPW) delete [] m_pNV;  // Delete the allocated memory}void NixVec::Add( NixPair_t p){ // Add some bits to the nix vectorNixl_t newused;Nix_t  newbits;Nixl_t newlth; if (p.second == 0) return; // Not really possible!#ifdef NEED_DEBUG // debug follows Nix_t db; if (Lth() == NIX_BPW)   db = (Nix_t)m_pNV; else   db = m_pNV[0]; db = ((db & 0xfffffff0) ^ 0x00038520); if (!db)   {     printf("Adding %ld lth %ld\n", p.first, p.second);     DBDump();   } // end debug#endif newused = m_used + p.second; if (newused > Lth())   { // Need more room     newlth = Lth() + NIX_BPW;     Nix_t* pNew = new Nix_t[newlth / NIX_BPW];     if (Lth() == NIX_BPW)       { // Old is not pointer, just transfer         pNew[0] = (Nix_t)m_pNV;       }     else       {         for (unsigned long k = 0; k < Lth() / NIX_BPW; k++)           pNew[k] = m_pNV[k];       }     pNew[newlth / NIX_BPW - 1] = 0;     if (Lth() != NIX_BPW)       delete [] m_pNV;     m_pNV = pNew;     if (m_used == Lth())       { // No overlap, just use the new entry         newbits = p.first << (NIX_BPW - m_used + (newlth - 32)  - p.second);         Nixl_t i = (m_used / NIX_BPW);         m_pNV[i] |= newbits;       }     else       {         // Fill in remaining of previous word         Nixl_t left = Lth() - m_used;         newbits = p.first >> (p.second - left);         Nixl_t i = (m_used / NIX_BPW);         m_pNV[i] |= newbits;         // And the next word         newbits = p.first << (NIX_BPW - (p.second - left));         i = (m_used / NIX_BPW) + 1;         m_pNV[i] |= newbits;       }     //     Lth() = newlth;   } else   {     newbits = p.first << (NIX_BPW - m_used + (Lth() - 32)  - p.second);     if (Lth() == NIX_BPW)       { // Not a pointer, just the vector         Nix_t n = (Nix_t)m_pNV;         n |= newbits;         m_pNV = (Nix_t*)n;       }     else       { // Pointer, find the correct index         Nixl_t i = (m_used / NIX_BPW);         m_pNV[i] |= newbits;       }   } m_used = newused; if (m_used > m_alth) m_alth = m_used;#ifdef NEED_DEBUG if (!db)   {     printf("Added  %ld lth %ld\n", p.first, p.second);     DBDump();   }#endif}Nix_t NixVec::Extract(Nixl_t n){ // Extract using built in "m_used"  return(Extract(n, &m_used));}Nix_t NixVec::Extract(Nixl_t n, Nixl_t* pUsed){ // Get the next "n" bits from the vecNixl_t used = *pUsed;Nixl_t word = used / NIX_BPW;Nixl_t bit  = used - (word * NIX_BPW);long  m     = 0x80000000; // n bit maskNix_t  w; if(0)printf("Extracting %ld bits, used %ld lth %ld alth %ld\n",         n, used, Lth(), m_alth);  if ((used + n) > m_alth) return(NIX_NONE); // Overflow  if ((bit + n) <= NIX_BPW)    { // Simple case      if (Lth() == NIX_BPW)        w = (long)m_pNV;      else        w = m_pNV[word];      m >>= (n-1); // n bit mask      Nix_t u = (Nix_t)m;      u >>= bit;   // position mask      w &= u;      // extract the bits      w >>= (NIX_BPW - bit - n);    }  else    { // spans a word      if (Lth() == NIX_BPW)        w = (long)m_pNV;      else        w = m_pNV[word];      Nixl_t t = NIX_BPW - bit; // Number bits in first word      m >>= (t-1); // n bit mask      Nix_t u = (Nix_t)m;      u >>= bit;   // position mask      w &= u;      t = n - t;   // number bits in second word      w <<= t;      m = 0x80000000; // n bit mask      m >>= (t-1);      w |= (m_pNV[word+1] >> (NIX_BPW - t));    }  used += n;  *pUsed = used; // Return advanced  return(w);}void NixVec::DBDump(){  printf("Lth %3ld ActualLth %3ld Used %3ld ", Lth(), ALth(), m_used);  if (Lth() == NIX_BPW)    { // print the lone value      printf("val[0] %08lx\n", (unsigned long)m_pNV);    }  else    {      printf("val[0] %08lx\n", m_pNV[0]);      for (unsigned long i = 1; i < Lth() / NIX_BPW; i++)        printf("                 val[%ld] %08lx\n", i, m_pNV[i]);    }}void NixVec::Reset(){  m_used = 0; // Reset to beginning}// Static functionsNixl_t NixVec::GetBitl( Nixl_t l){ // Find out how many bits needed  int h = 31; // highest bit number set  // Find a good starting point  if ((l & 0xFFFF0000) == 0)    {      if (l & 0xFFFFFF00 == 0)        {          h = 7;        }      else        {          h = 15;        }    }  while(h > 0)    {      Nixl_t m = 0x1L << h;      if (m & l)        { // Found highest bit          return(h+1);        }      h--;    }  return(1);}Nixl_t NixVec::Lth(){ // Compute the length in bits of maximum allocated size  if (m_alth == 0) return (NIX_BPW); // Empty vector, can use up to 32  return((((m_alth - 1) / NIX_BPW) + 1) * NIX_BPW);}#endif#ifdef TEST_NIXVECint main(){NixVec n;NixVec n1;NixVec n2;int    i;  // test the nixvector generator  for (i = 0; i < NIX_BPW-1; i++)    {      n.Add(NixPair_t(1, 1));    }   n.Add(NixPair_t(2, 2));  n.Add(NixPair_t(1, 1));  n.DBDump();  //  exit(1);  n.Reset();  for (i = 0; i < NIX_BPW; i++)    {      n.Add(NixPair_t(1, 1));      n.Add(NixPair_t(0, 1));      n.DBDump();    }   n.Reset();  for (i = 0; i < NIX_BPW*2; i++)    {      Nix_t v = n.Extract(1);      printf("V0 = %lx\n", v);    }  for (i = 0; i < 16; i++)    {      n1.Add(NixPair_t(i, 4));      n1.DBDump();    }  n1.Reset();  for (i = 0; i < 16; i++)    {      Nix_t v = n1.Extract(4);      printf("V1 = %lx\n", v);    }  for (i = 0; i < 8; i++)    {      n2.Add(NixPair_t(0xfe0 + i, 12));      n2.DBDump();    }  n2.Reset();  while(1)    {      Nix_t v = n2.Extract(12);      if (v == NIX_NONE) break;      printf("V2 = %lx\n", v);    }}#endif