/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

/*

 * Copyright (c) 2006,2007 INRIA

 * All rights reserved.

 *

 * 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

 *

 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>

 */

#include <utility>

#include <list>

#include "ns3/assert.h"

#include "ns3/fatal-error.h"

#include "packet-history.h"

#include "chunk.h"

#include "buffer.h"

namespace {

class ItemList

{

public:

  void InitPayload (uint32_t packetUid, uint32_t size);

  void AddHeader (uint32_t type, uint32_t size);

  void AddTrailer (uint32_t type, uint32_t size);

  void RemHeader (uint32_t type, uint32_t size);

  void RemTrailer (uint32_t type, uint32_t size);

  void RemAtStart (uint32_t toRemove);

  void RemAtEnd (uint32_t toRemove);

  void AddAtEnd (ItemList const *other);

  void Print (std::ostream &os, ns3::Buffer buffer, const ns3::PacketPrinter &printer) const;

private:

  enum Type {

    PAYLOAD,

    HEADER,

    TRAILER,

  };

  struct Item

  {

    enum ItemList::Type m_type;

    uint32_t m_size;

    uint32_t m_chunkType;

    uint32_t m_fragmentStart;

    uint32_t m_fragmentEnd;

    uint32_t m_packetUid;

  };

  std::list<Item> m_itemList;

};

void 

ItemList::InitPayload (uint32_t packetUid, uint32_t size)

{

  NS_ASSERT (m_itemList.empty ());

  struct Item item;

  item.m_type = ItemList::PAYLOAD;

  item.m_chunkType = 0;

  item.m_size = size;

  item.m_fragmentStart = 0;

  item.m_fragmentEnd = item.m_size;

  item.m_packetUid = packetUid;

  m_itemList.push_back (item);

}

void 

ItemList::AddHeader (uint32_t type, uint32_t size)

{

  struct Item item;

  item.m_type = ItemList::HEADER;

  item.m_chunkType = type;

  item.m_size = size;

  item.m_fragmentStart = 0;

  item.m_fragmentEnd = size;

  item.m_packetUid = m_itemList.front ().m_packetUid;

  m_itemList.push_front (item);

}

void 

ItemList::AddTrailer (uint32_t type, uint32_t size)

{

  struct Item item;

  item.m_type = ItemList::TRAILER;

  item.m_chunkType = type;

  item.m_size = size;

  item.m_fragmentStart = 0;

  item.m_fragmentEnd = size;

  item.m_packetUid = m_itemList.back ().m_packetUid;

  m_itemList.push_back (item);

}

void 

ItemList::RemHeader (uint32_t type, uint32_t size)

{

  struct Item item = m_itemList.front ();

  if (item.m_type != ItemList::HEADER ||

      item.m_size != size ||

      item.m_chunkType != type)

    {

      NS_FATAL_ERROR ("Removing Unexpected header");

    }

  else if (item.m_fragmentStart != 0 ||

           item.m_fragmentEnd != item.m_size)

    {

      NS_FATAL_ERROR ("Removing non-complete header");

    }

  m_itemList.pop_front ();

}

void 

ItemList::RemTrailer (uint32_t type, uint32_t size)

{

  struct Item item = m_itemList.back ();

  if (item.m_type != ItemList::TRAILER ||

      item.m_size != size ||

      item.m_chunkType != type)

    {

      NS_FATAL_ERROR ("Removing Unexpected trailer");

    }

  else if (item.m_fragmentStart != 0 ||

           item.m_fragmentEnd != item.m_size)

    {

      NS_FATAL_ERROR ("Removing non-complete trailer");

    }

  m_itemList.pop_back ();

}

void 

ItemList::RemAtStart (uint32_t toRemove)

{

  uint32_t leftToRemove = toRemove;

  while (!m_itemList.empty () && leftToRemove > 0)

    {

      struct Item &item = m_itemList.front ();

      if (item.m_fragmentEnd - item.m_fragmentStart <= leftToRemove)

        {

          m_itemList.pop_front ();

          leftToRemove -= item.m_size;

        }

      else

        {

          item.m_fragmentStart += leftToRemove;

          leftToRemove = 0;

          NS_ASSERT (item.m_size >= item.m_fragmentEnd - item.m_fragmentStart &&

                     item.m_fragmentStart <= item.m_fragmentEnd);

        }

    }

  NS_ASSERT (leftToRemove == 0);

}

void 

ItemList::RemAtEnd (uint32_t toRemove)

{

  uint32_t leftToRemove = toRemove;

  while (!m_itemList.empty () && leftToRemove > 0)

    {

      struct Item &item = m_itemList.back ();

      if (item.m_fragmentEnd - item.m_fragmentStart <= leftToRemove)

        {

          m_itemList.pop_back ();

          leftToRemove -= item.m_size;

        }

      else

        {

          item.m_fragmentEnd -= leftToRemove;

          leftToRemove = 0;

        }

      NS_ASSERT (item.m_size >= item.m_fragmentEnd - item.m_fragmentStart &&

                 item.m_fragmentStart <= item.m_fragmentEnd &&

                 item.m_fragmentEnd <= item.m_size);

    }

  NS_ASSERT (leftToRemove == 0);

}

void 

ItemList::AddAtEnd (ItemList const *other)

{

  for (std::list<ItemList::Item>::const_iterator i = other->m_itemList.begin (); 

       i != other->m_itemList.end (); i++)

    {

      const ItemList::Item &item = *i;

      ItemList::Item &last = m_itemList.back ();

      if (item.m_packetUid == last.m_packetUid &&

          item.m_type == last.m_type &&

          item.m_chunkType == last.m_chunkType &&

          item.m_size == last.m_size &&

          last.m_fragmentEnd != last.m_size && 

          item.m_fragmentStart == last.m_fragmentEnd)

        {

          last.m_fragmentEnd = item.m_fragmentEnd;

        }

      else

        {

          m_itemList.push_back (item);

        }

    }

}

void 

ItemList::Print (std::ostream &os, ns3::Buffer buffer, const ns3::PacketPrinter &printer) const

{

  NS_ASSERT (!m_itemList.empty ());

  uint32_t totalSize = 0;

  for (std::list<ItemList::Item>::const_iterator i = m_itemList.begin (); 

       i != m_itemList.end (); i++)

    {

      ItemList::Item item = *i;

      totalSize += item.m_fragmentEnd - item.m_fragmentStart;

    }

  NS_ASSERT (totalSize == buffer.GetSize ());

  uint32_t offset = 0;

  for (std::list<ItemList::Item>::const_iterator i = m_itemList.begin (); 

       i != m_itemList.end (); i++)

    {

      ItemList::Item item = *i;

      if (item.m_type == ItemList::PAYLOAD)

        {

          printer.PrintPayload (os, item.m_packetUid, item.m_size, item.m_fragmentStart, item.m_fragmentEnd);

        }

      else if (item.m_fragmentStart != 0 || 

               item.m_fragmentEnd != item.m_size)

        {

          printer.PrintChunkFragment (item.m_chunkType, os, item.m_packetUid, item.m_size, 

                                      item.m_fragmentStart, item.m_fragmentEnd);

        }

      else if (item.m_type == ItemList::HEADER)

        {

          ns3::Buffer::Iterator j = buffer.Begin ();

          j.Next (offset);

          printer.PrintChunk (item.m_chunkType, j, os, item.m_packetUid, item.m_size);

        }

      else if (item.m_type == ItemList::TRAILER)

        {

          ns3::Buffer::Iterator j = buffer.End ();

          j.Prev (totalSize - (offset + item.m_size));

          printer.PrintChunk (item.m_chunkType, j, os, item.m_packetUid, item.m_size);

        }

      else 

        {

          NS_ASSERT (false);

        }

      offset += item.m_fragmentEnd - item.m_fragmentStart;

    }

}

} // anonymous namespace

namespace ns3 {

bool PacketHistory::m_enable = false;

uint32_t PacketHistory::m_maxSize = 0;

PacketHistory::DataFreeList PacketHistory::m_freeList;

void 

PacketHistory::Enable (void)

{

  m_enable = true;

}

PacketHistory::PacketHistory ()

  : m_data (0),

    m_end (0),

    m_n (0),

    m_aggregated (false)

{

  Construct (0, 0);

}

PacketHistory::PacketHistory (uint32_t uid, uint32_t size)

  : m_data (0),

    m_end (0),

    m_n (0),

    m_aggregated (false)

{

  Construct (uid, size);

}

void

PacketHistory::Construct (uint32_t uid, uint32_t size)

{

  if (m_enable) 

    {

      m_data = PacketHistory::Create (size);

      AppendOneCommand (PacketHistory::INIT,

                        size, uid);

    }

}

PacketHistory::PacketHistory (PacketHistory const &o)

  : m_data (o.m_data),

    m_end (o.m_end),

    m_n (o.m_n),

    m_aggregated (o.m_aggregated)

{

  if (m_data != 0) 

    {

      m_data->m_count++;

    }

}

PacketHistory &

PacketHistory::operator = (PacketHistory const& o)

{

  if (m_data == o.m_data) 

    {

      // self assignment

      return *this;

    }

  if (m_data != 0) 

    {

      m_data->m_count--;

      if (m_data->m_count == 0) 

        {

          PacketHistory::Recycle (m_data);

        }

    }

  m_data = o.m_data;

  m_end = o.m_end;

  m_n = o.m_n;

  m_aggregated = o.m_aggregated;

  if (m_data != 0) 

    {

      m_data->m_count++;

    }

  return *this;

}

PacketHistory::~PacketHistory ()

{

  if (m_data != 0) 

    {

      m_data->m_count--;

      if (m_data->m_count == 0) 

        {

          PacketHistory::Recycle (m_data);

        }

    }

}

struct PacketHistory::CommandData *

PacketHistory::Create (uint32_t size)

{

  if (size > m_maxSize)

    {

      m_maxSize = size;

    }

  while (!m_freeList.empty ()) 

    {

      struct PacketHistory::CommandData *data = m_freeList.back ();

      m_freeList.pop_back ();

      if (data->m_size >= size) 

        {

          data->m_count = 1;

          return data;

        }

      PacketHistory::Deallocate (data);

    }

  return PacketHistory::Allocate (size);

}

void

PacketHistory::Recycle (struct CommandData *data)

{

  NS_ASSERT (data->m_count == 0);

  if (m_freeList.size () > 1000 ||

      data->m_size < m_maxSize) 

    {

      PacketHistory::Deallocate (data);

    } 

  else 

    {

      m_freeList.push_back (data);

    }

}

struct PacketHistory::CommandData *

PacketHistory::Allocate (uint32_t n)

{

  uint32_t size = sizeof (struct CommandData);

  if (n <= 4)

    {

      n = 4;

    }

  size += (n-4) * (4 + 1);

  uint8_t *buf = new uint8_t [size];

  struct CommandData *data = (struct CommandData *)buf;

  data->m_size = n;

  data->m_count = 1;

  return data;

}

void 

PacketHistory::Deallocate (struct CommandData *data)

{

  uint8_t *buf = (uint8_t *)data;

  delete [] buf;

}

void

PacketHistory::AppendOneCommand (uint32_t type, uint32_t data0, uint32_t data1)

{

  NS_ASSERT (m_data != 0);

  uint32_t n = GetUleb128Size (type);

  n += GetUleb128Size (data0);

  n += GetUleb128Size (data1);

  if (m_data->m_size > m_end + n)

    {

      if (m_data->m_count == 1 ||

          m_data->m_dirtyEnd == m_end)

        {

          AppendValue (type);

          AppendValue (data0);

          AppendValue (data1);

          m_n++;

          return;

        }

      else

        {

          uint8_t *buffer = &(m_data->m_data[m_end]);

          uint32_t lastType = ReadForwardValue (&buffer);

          if (lastType == type)

            {

              uint32_t lastData = ReadForwardValue (&buffer);

              if (lastData == data0)

                {

                  lastData = ReadForwardValue (&buffer);

                  if (lastData == data1)

                    {

                      return;

                    }

                }

            }

        }

    }

  Reserve (n);

  AppendValue (type);

  AppendValue (data0);

  AppendValue (data1);

  m_n++;

}

void

PacketHistory::AppendOneCommand (uint32_t type, uint32_t data)

{

  NS_ASSERT (m_data != 0);

  uint32_t n = GetUleb128Size (data);

  n += GetUleb128Size (type);

  if (m_data->m_size > m_end + n)

    {

      if (m_data->m_count == 1 ||

          m_data->m_dirtyEnd == m_end)

        {

          AppendValue (type);

          AppendValue (data);

          m_n++;

          return;

        }

      else

        {

          uint8_t *buffer = &(m_data->m_data[m_end]);

          uint32_t lastType = ReadForwardValue (&buffer);

          if (lastType == type)

            {

              uint32_t lastData = ReadForwardValue (&buffer);

              if (lastData == data)

                {

                  return;

                }

            }

        }

    }

  Reserve (n);

  AppendValue (type);

  AppendValue (data);

  m_n++;

}

void

PacketHistory::ReserveCopy (uint32_t size)

{

  struct CommandData *newData = PacketHistory::Create (m_end + size);

  memcpy (newData->m_data, m_data->m_data, m_end);

  newData->m_dirtyEnd = m_end;

  m_data->m_count--;

  if (m_data->m_count == 0) 

    {

      PacketHistory::Recycle (m_data);

    }

  m_data = newData;

}

void

PacketHistory::Reserve (uint32_t size)

{

  NS_ASSERT (m_data != 0);

  if (m_data->m_size > m_end + size &&

      (m_data->m_count == 1 ||

       m_data->m_dirtyEnd == m_end))