/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2008 INRIA
 *
 * 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 "tag-list.h"
#include "ns3/log.h"
#include <vector>
#include <string.h>

NS_LOG_COMPONENT_DEFINE ("TagList");

#define USE_FREE_LIST 1
#define FREE_LIST_SIZE 1000
#define OFFSET_MAX (2147483647)

namespace ns3 {

struct TagListData {
  uint32_t size;
  uint32_t count;
  uint32_t dirty;
  uint8_t data[4];
};

#ifdef USE_FREE_LIST
static class TagListDataFreeList : public std::vector<struct TagListData *>
{
public:
  ~TagListDataFreeList ();
} g_freeList;
static uint32_t g_maxSize = 0;

TagListDataFreeList::~TagListDataFreeList ()
{
  for (TagListDataFreeList::iterator i = begin ();
       i != end (); i++)
    {
      uint8_t *buffer = (uint8_t *)(*i);
      delete [] buffer;
    }
}
#endif /* USE_FREE_LIST */

TagList::Iterator::Item::Item (TagBuffer buf_)
    : buf (buf_)
{}

bool 
TagList::Iterator::HasNext (void) const
{
  return m_current < m_end;
}
struct TagList::Iterator::Item 
TagList::Iterator::Next (void)
{
  NS_ASSERT (HasNext ());
  struct Item item = Item (TagBuffer (m_current+16, m_end));
  item.tid.SetUid (m_nextTid);
  item.size = m_nextSize;
  item.start = m_nextStart;
  item.end = m_nextEnd;
  item.start = std::max (item.start, m_offsetStart);
  item.end = std::min (item.end, m_offsetEnd);
  m_current += 4 + 4 + 4 + 4 + item.size;
  item.buf.TrimAtEnd (m_end - m_current);
  PrepareForNext ();
  return item;
}
void
TagList::Iterator::PrepareForNext (void)
{
  while (m_current < m_end)
    {
      TagBuffer buf = TagBuffer (m_current, m_end);
      m_nextTid = buf.ReadU32 ();
      m_nextSize = buf.ReadU32 ();
      m_nextStart = buf.ReadU32 ();
      m_nextEnd = buf.ReadU32 ();
      if (m_nextStart >= m_offsetEnd || m_nextEnd <= m_offsetStart)
	{
	  m_current += 4 + 4 + 4 + 4 + m_nextSize;
	}
      else
	{
	  break;
	}
    }
}
TagList::Iterator::Iterator (uint8_t *start, uint8_t *end, int32_t offsetStart, int32_t offsetEnd)
  : m_current (start),
    m_end (end),
    m_offsetStart (offsetStart),
    m_offsetEnd (offsetEnd)
{
  PrepareForNext ();
}

uint32_t 
TagList::Iterator::GetOffsetStart (void) const
{
  return m_offsetStart;
}


TagList::TagList ()
  : m_used (0),
    m_data (0)
{
  NS_LOG_FUNCTION (this);
}
TagList::TagList (const TagList &o)
  : m_used (o.m_used),
    m_data (o.m_data)
{
  NS_LOG_FUNCTION (this << &o);
  if (m_data != 0)
    {
      m_data->count++;
    }
}
TagList &
TagList::operator = (const TagList &o)
{
  NS_LOG_FUNCTION (this << &o);
  if (this == &o)
    {
      return *this;
    }

  Deallocate (m_data);
  m_data = o.m_data;
  m_used = o.m_used;
  if (m_data != 0)
    {
      m_data->count++;
    }
  return *this;
}
TagList::~TagList ()
{
  NS_LOG_FUNCTION (this);
  Deallocate (m_data);
  m_data = 0;
  m_used = 0;
}

TagBuffer
TagList::Add (TypeId tid, uint32_t bufferSize, int32_t start, int32_t end)
{
  NS_LOG_FUNCTION (this << tid << bufferSize << start << end);
  uint32_t spaceNeeded = m_used + bufferSize + 4 + 4 + 4 + 4;
  NS_ASSERT (m_used <= spaceNeeded);
  if (m_data == 0)
    {
      m_data = Allocate (spaceNeeded);
      m_used = 0;
    } 
  else if (m_data->size < spaceNeeded ||
	   (m_data->count != 1 && m_data->dirty != m_used))
    {
      struct TagListData *newData = Allocate (spaceNeeded);
      memcpy (&newData->data, &m_data->data, m_used);
      Deallocate (m_data);
      m_data = newData;
    }
  TagBuffer tag = TagBuffer (&m_data->data[m_used], 
			     &m_data->data[spaceNeeded]);
  tag.WriteU32 (tid.GetUid ());
  tag.WriteU32 (bufferSize);
  tag.WriteU32 (start);
  tag.WriteU32 (end);
  m_used = spaceNeeded;
  m_data->dirty = m_used;
  return tag;
}

void 
TagList::Add (const TagList &o)
{
  NS_LOG_FUNCTION (this << &o);
  TagList::Iterator i = o.BeginAll ();
  while (i.HasNext ())
    {
      TagList::Iterator::Item item = i.Next ();
      TagBuffer buf = Add (item.tid, item.size, item.start, item.end);
      buf.CopyFrom (item.buf);
    }
}

void 
TagList::RemoveAll (void)
{
  NS_LOG_FUNCTION (this);
  Deallocate (m_data);
  m_data = 0;
  m_used = 0;
}

TagList::Iterator 
TagList::BeginAll (void) const
{
  NS_LOG_FUNCTION (this);
  // I am not totally sure but I might need to use 
  // INT32_MIN instead of zero below.
  return Begin (0, OFFSET_MAX);
}

TagList::Iterator 
TagList::Begin (int32_t offsetStart, int32_t offsetEnd) const
{
  NS_LOG_FUNCTION (this << offsetStart << offsetEnd);
  if (m_data == 0)
    {
      return Iterator (0, 0, offsetStart, offsetEnd);
    }
  else
    {
      return Iterator (m_data->data, &m_data->data[m_used], offsetStart, offsetEnd);
    }
}

bool 
TagList::IsDirtyAtEnd (int32_t appendOffset)
{
  NS_LOG_FUNCTION (this << appendOffset);
  TagList::Iterator i = BeginAll ();
  while (i.HasNext ())
    {
      TagList::Iterator::Item item = i.Next ();
      if (item.end > appendOffset)
	{
	  return true;
	}
    }
  return false;
}

bool 
TagList::IsDirtyAtStart (int32_t prependOffset)
{
  NS_LOG_FUNCTION (this << prependOffset);
  TagList::Iterator i = BeginAll ();
  while (i.HasNext ())
    {
      TagList::Iterator::Item item = i.Next ();
      if (item.start < prependOffset)
	{
	  return true;
	}
    }
  return false;
}

void 
TagList::AddAtEnd (int32_t adjustment, int32_t appendOffset)
{
  NS_LOG_FUNCTION (this << adjustment << appendOffset);
  if (adjustment == 0 && !IsDirtyAtEnd (appendOffset))
    {
      return;
    }
  TagList list;
  TagList::Iterator i = BeginAll ();
  while (i.HasNext ())
    {
      TagList::Iterator::Item item = i.Next ();
      item.start += adjustment;
      item.end += adjustment;

      if (item.start >= appendOffset)
	{
	  continue;
	}
      else if (item.start < appendOffset && item.end > appendOffset)
	{
	  item.end = appendOffset;
	}
      else
	{
	  // nothing to do.
	}
      TagBuffer buf = list.Add (item.tid, item.size, item.start, item.end);
      buf.CopyFrom (item.buf);
    }
  *this = list;  
}

void 
TagList::AddAtStart (int32_t adjustment, int32_t prependOffset)
{
  NS_LOG_FUNCTION (this << adjustment << prependOffset);
  if (adjustment == 0 && !IsDirtyAtStart (prependOffset))
    {
      return;
    }
  TagList list;
  TagList::Iterator i = BeginAll ();
  while (i.HasNext ())
    {
      TagList::Iterator::Item item = i.Next ();
      item.start += adjustment;
      item.end += adjustment;

      if (item.end <= prependOffset)
	{
	  continue;
	}
      else if (item.end > prependOffset && item.start < prependOffset)
	{
	  item.start = prependOffset;
	}
      else
	{
	  // nothing to do.
	}
      TagBuffer buf = list.Add (item.tid, item.size, item.start, item.end);
      buf.CopyFrom (item.buf);
    }
  *this = list;
}

#ifdef USE_FREE_LIST

struct TagListData *
TagList::Allocate (uint32_t size)
{
  NS_LOG_FUNCTION (this << size);
  while (!g_freeList.empty ())
    {
      struct TagListData *data = g_freeList.back ();
      g_freeList.pop_back ();
      NS_ASSERT (data != 0);
      if (data->size >= size)
	{
	  data->count = 1;
	  data->dirty = 0;
	  return data;
	}
      uint8_t *buffer = (uint8_t *)data;
      delete [] buffer;
    }
  uint8_t *buffer = new uint8_t [std::max (size, g_maxSize) + sizeof (struct TagListData) - 4];
  struct TagListData *data = (struct TagListData *)buffer;
  data->count = 1;
  data->size = size;
  data->dirty = 0;
  return data;
}

void 
TagList::Deallocate (struct TagListData *data)
{
  NS_LOG_FUNCTION (this << data);
  if (data == 0)
    {
      return;
    }
  g_maxSize = std::max (g_maxSize, data->size);
  data->count--;
  if (data->count == 0)
    {
      if (g_freeList.size () > FREE_LIST_SIZE ||
	  data->size < g_maxSize)
	{
	  uint8_t *buffer = (uint8_t *)data;
	  delete [] buffer;
	}
      else
	{
	  g_freeList.push_back (data);
	}
    }
}

#else /* USE_FREE_LIST */

struct TagListData *
TagList::Allocate (uint32_t size)
{
  NS_LOG_FUNCTION (this << size);
  uint8_t *buffer = new uint8_t [size + sizeof (struct TagListData) - 4];
  struct TagListData *data = (struct TagListData *)buffer;
  data->count = 1;
  data->size = size;
  data->dirty = 0;
  return data;
}

void 
TagList::Deallocate (struct TagListData *data)
{
  NS_LOG_FUNCTION (this << data);
  if (data == 0)
    {
      return;
    }
  data->count--;
  if (data->count == 0)
    {
      uint8_t *buffer = (uint8_t *)data;
      delete [] buffer;
    }
}

#endif /* USE_FREE_LIST */


} // namespace ns3