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

/*

 * Copyright (c) 2011 Yufei Cheng

 *

 * 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: Yufei Cheng   <yfcheng@ittc.ku.edu>

 *

 * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director

 * ResiliNets Research Group  http://wiki.ittc.ku.edu/resilinets

 * Information and Telecommunication Technology Center (ITTC)

 * and Department of Electrical Engineering and Computer Science

 * The University of Kansas Lawrence, KS USA.

 *

 * Work supported in part by NSF FIND (Future Internet Design) Program

 * under grant CNS-0626918 (Postmodern Internet Architecture),

 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),

 * US Department of Defense (DoD), and ITTC at The University of Kansas.

 */

#include "dsr-rreq-table.h"

#include "ns3/log.h"

#include <algorithm>

#include <iostream>

NS_LOG_COMPONENT_DEFINE ("RreqTable");

namespace ns3 {

namespace dsr {

NS_OBJECT_ENSURE_REGISTERED (RreqTable);

TypeId RreqTable::GetTypeId ()

{

  static TypeId tid = TypeId ("ns3::dsr::RreqTable")

    .SetParent<Object> ()

    .AddConstructor<RreqTable> ()

  ;

  return tid;

}

RreqTable::RreqTable ()

  : m_linkStates (PROBABLE)

{

}

RreqTable::~RreqTable ()

{

  NS_LOG_FUNCTION_NOARGS ();

}

void

RreqTable::RemoveLeastExpire (std::map<Ipv4Address, RreqTableEntry > & rreqDstMap)

{

  NS_LOG_FUNCTION (this);

  Ipv4Address firstExpire;

  Time max = Seconds (0.0);

  for (std::map<Ipv4Address, RreqTableEntry >::const_iterator i =

         rreqDstMap.begin (); i != rreqDstMap.end (); ++i)

    {

      Ipv4Address dst = i->first;

      RreqTableEntry rreqTableEntry = i->second;

      if (rreqTableEntry.m_expire > max)

        {

          max = rreqTableEntry.m_expire;

          firstExpire = dst;

        }

    }

  rreqDstMap.erase (firstExpire);

}

void

RreqTable::FindAndUpdate (Ipv4Address dst)

{

  NS_LOG_LOGIC ("Find and update the route request entry for " << dst);

  std::map<Ipv4Address, RreqTableEntry >::const_iterator i =

    m_rreqDstMap.find (dst);

  if (i == m_rreqDstMap.end ())

    {

      NS_LOG_DEBUG ("The request table entry not found");

      /*

       * Drop the most aged packet when buffer reaches to max

       */

      if (m_rreqDstMap.size () >= m_requestTableSize)

        {

          RemoveLeastExpire (m_rreqDstMap);

          NS_LOG_DEBUG ("The request table size after erase ");

        }

      RreqTableEntry rreqTableEntry;

      rreqTableEntry.m_reqNo = 0;

      rreqTableEntry.m_expire = Simulator::Now ();

      m_rreqDstMap [dst] = rreqTableEntry;

    }

  else

    {

      NS_LOG_DEBUG ("Find the request table entry, increment the request count");

      Ipv4Address dst = i->first;

      RreqTableEntry rreqTableEntry = i->second;

      NS_LOG_DEBUG ("The request count before incrementing " << rreqTableEntry.m_reqNo);

      rreqTableEntry.m_reqNo = (rreqTableEntry.m_reqNo + 1);

      rreqTableEntry.m_expire = Simulator::Now ();

      m_rreqDstMap [dst] = rreqTableEntry;

    }

}

void

RreqTable::RemoveRreqEntry (Ipv4Address dst)

{

  NS_LOG_DEBUG ("Remove rreq entry with index dst");

  std::map<Ipv4Address, RreqTableEntry >::const_iterator i =

    m_rreqDstMap.find (dst);

  if (i == m_rreqDstMap.end ())

    {

      NS_LOG_DEBUG ("The request table entry not found");

    }

  else

    {

      // erase the request entry

      m_rreqDstMap.erase (dst);

    }

}

uint16_t

RreqTable::GetRreqCnt (Ipv4Address dst)

{

  NS_LOG_DEBUG ("Get the request count for a certain dst");

  std::map<Ipv4Address, RreqTableEntry >::const_iterator i =

    m_rreqDstMap.find (dst);

  if (i == m_rreqDstMap.end ())

    {

      NS_LOG_DEBUG ("The request table entry not found");

      FindAndUpdate (dst);

      return 0;

    }

  else

    {

      RreqTableEntry rreqTableEntry = i->second;

      NS_LOG_DEBUG ("Find the request count for " << dst << " " << rreqTableEntry.m_reqNo);

      return rreqTableEntry.m_reqNo;

    }

}

// ----------------------------------------------------------------------------------------------------------

/**

 * This part takes care of the route request from a specific source

 * need to ignore future route requests from same source for same destination with same identification

 */

bool

RreqTable::FindSrc (Ipv4Address source, Ipv4Address target, uint16_t id)

{

  Purge ();

  std::map<Ipv4Address, std::list<SourceRreqEntry> >::const_iterator i =

    m_rreqMap.find (source);

  if (i == m_rreqMap.end ())

    {

      NS_LOG_LOGIC ("No Request entry for " << source << " found");

      SourceRreqEntry sourceRreqEntry;

      sourceRreqEntry.m_dst = target;

      sourceRreqEntry.m_identification = id;

      sourceRreqEntry.m_expire = m_rreqEntryExpire + Simulator::Now ();

      NS_LOG_DEBUG ("The src rreq expire time " << sourceRreqEntry.m_expire);

      std::list<SourceRreqEntry> rqVector;

      rqVector.push_back (sourceRreqEntry);

      m_rreqMap[source] = rqVector;

      return false;

    }

  else

    {

      NS_LOG_LOGIC ("Request entry for " << source << " found in the cache");

      std::list<SourceRreqEntry> rqVector = i->second;

      for (std::list<SourceRreqEntry>::iterator j = rqVector.begin (); j != rqVector.end (); ++j)

        {

          SourceRreqEntry rreqEntry = *j;

          if ((rreqEntry.m_dst == target) && (rreqEntry.m_identification == id))

            {

              NS_LOG_DEBUG ("Found the request entry for source node with address " << source);

//              j = rqVector.erase (j);

//              rqVector.push_back(*j);

//              m_rreqMap[source] = rqVector;

              return true;

            }

        }

      SourceRreqEntry rreqEntry;

      rreqEntry.m_dst = target;

      rreqEntry.m_identification = id;

      rreqEntry.m_expire = m_rreqEntryExpire + Simulator::Now ();

      if (rqVector.size () >= m_requestIdSize)

        {

          // erase the first element when the size is larger than the request id size (default: 16)

          rqVector.pop_front ();

        }

      // May need to check the size of the entry

      rqVector.push_back (rreqEntry);

      m_rreqMap[source] = rqVector;

      return false;

    }

  return false;

}

void

RreqTable::Purge ()

{

  //Trying to purge the rreq table

  if (m_rreqMap.empty ())

    {

      NS_LOG_DEBUG ("The rreq table is empty");

      return;

    }

  for (std::map<Ipv4Address, std::list<SourceRreqEntry> >::iterator i =

         m_rreqMap.begin (); i != m_rreqMap.end (); )

    {

      // Loop of rreq table entry with the source entries

      std::map<Ipv4Address, std::list<SourceRreqEntry> >::iterator itmp = i;

      /*

       * The rreq table entries

       */

      Ipv4Address dst = i->first;

      std::list<SourceRreqEntry> rqVector = i->second;

      NS_LOG_DEBUG ("The rqVector size for " << dst << " is " << rqVector.size ());

      if (rqVector.size ())

        {

          for (std::list<SourceRreqEntry>::iterator j = rqVector.begin (); j != rqVector.end (); )

            {

              NS_LOG_DEBUG ("The expire time of every entry with expire time " << j->m_expire - Simulator::Now ());

              /*

               * First verify if the rreq table entry has expired or not

               */

              if (j->m_expire - Simulator::Now () <= Seconds (0))

                {

                  /*

                   * When the expire time has passed, erase the certain rreq table entry

                   */

                  NS_LOG_DEBUG ("Erase the expired rreq table entry for " << dst << " with expire time " << j->m_expire - Simulator::Now ());

                  j = rqVector.erase (j);

                }

              else

                {

                  ++j;

                }

            }

          NS_LOG_DEBUG ("The rreq table entry for " << dst << " " << rqVector.size ());

          if (rqVector.size ())

            {

              ++i;

              m_rreqMap.erase (itmp); // erase the entry first

              /*

               * Save the new rreq table entry along with the destination address in map

               */

              std::pair<std::map<Ipv4Address, std::list<SourceRreqEntry> >::iterator, bool> result =

                m_rreqMap.insert (std::make_pair (dst, rqVector));

            }

          else

            {

              ++i;

              m_rreqMap.erase (itmp);

            }

        }

      else

        {

          ++i;

          m_rreqMap.erase (itmp);

        }

    }

  return;

}

// ----------------------------------------------------------------------------------------------------------

/**

 * This part takes care of the route request ID initialized from a specific source to one destination

 * Essentially a counter

 */

uint16_t

RreqTable::CheckUniqueRreqId (Ipv4Address dst)

{

  NS_LOG_DEBUG ("The size of id cache " << m_rreqIdCache.size ());

  std::map<Ipv4Address, uint16_t>::const_iterator i =

    m_rreqIdCache.find (dst);

  if (i == m_rreqIdCache.end ())

    {

      NS_LOG_LOGIC ("No Request id for " << dst << " found");

      m_rreqIdCache[dst] = 0;

      return 0;

    }

  else

    {

      NS_LOG_LOGIC ("Request id for " << dst << " found in the cache");

      uint16_t rreqId = m_rreqIdCache[dst];

      if (rreqId >= m_maxRreqId)

        {

          NS_LOG_DEBUG ("The request id increase past the max value, so reset it to 0");

          rreqId = 0;

          m_rreqIdCache[dst] = rreqId;

        }

      else

        {

          rreqId++;

          m_rreqIdCache[dst] = rreqId;

        }

      NS_LOG_DEBUG ("The Request id for " << dst << " is " << rreqId);

      return rreqId;

    }

}

uint16_t

RreqTable::GetRreqSize ()

{

  return m_rreqIdCache.size ();

}

// ----------------------------------------------------------------------------------------------------------

/**

 * This part takes care of black list which can save unidirectional link information

 */

void

RreqTable::Invalidate ()

{

  if (m_linkStates == QUESTIONABLE)

    {

      return;

    }

  m_linkStates = QUESTIONABLE;

}

BlackList*

RreqTable::FindUnidirectional (Ipv4Address neighbor)

{

  PurgeNeighbor ();  // purge the neighbor cache

  for (std::vector<BlackList>::iterator i = m_blackList.begin ();

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

    {

      if (i->m_neighborAddress == neighbor)

        {

          return &(*i);

        }

    }

  return NULL;

}

bool

RreqTable::MarkLinkAsUnidirectional (Ipv4Address neighbor, Time blacklistTimeout)

{

  NS_LOG_LOGIC ("Add neighbor address in blacklist " << m_blackList.size ());

  for (std::vector<BlackList>::iterator i = m_blackList.begin (); i != m_blackList.end (); ++i)

    {

      if (i->m_neighborAddress == neighbor)

        {

          NS_LOG_DEBUG ("Update the blacklist list timeout if found the blacklist entry");

          i->m_expireTime = std::max (blacklistTimeout + Simulator::Now (), i->m_expireTime);

        }

      BlackList blackList (neighbor, blacklistTimeout + Simulator::Now ());

      m_blackList.push_back (blackList);

      PurgeNeighbor ();

      return true;

    }

  return false;

}

void

RreqTable::PurgeNeighbor ()

{

  /*

   * Purge the expired blacklist entries

   */

  m_blackList.erase (remove_if (m_blackList.begin (), m_blackList.end (),

                                IsExpired ()), m_blackList.end ());

}

} // namespace dsr

} // namespace ns3