candidate-queue.cc

Go to the documentation of this file.

/*
 * Copyright 2007 University of Washington
 *
 * SPDX-License-Identifier: GPL-2.0-only
 */
 
#include "candidate-queue.h"
 
#include "global-route-manager-impl.h"
 
#include "ns3/assert.h"
#include "ns3/log.h"
 
#include <algorithm>
#include <iostream>
 
namespace ns3
{
 
NS_LOG_COMPONENT_DEFINE("CandidateQueue");
 
/**
 * @brief Stream insertion operator.
 *
 * @param os the reference to the output stream
 * @param t the SPFVertex type
 * @returns the reference to the output stream
 */
template <typename T>
std::ostream&
operator<<(std::ostream& os, const typename SPFVertex<T>::VertexType& t)
{
    switch (t)
    {
    case SPFVertex<T>::VertexRouter:
        os << "router";
        break;
    case SPFVertex<T>::VertexNetwork:
        os << "network";
        break;
    default:
        os << "unknown";
        break;
    };
    return os;
}
 
template <typename T>
std::ostream&
operator<<(std::ostream& os, const CandidateQueue<T>& q)
{
    const typename CandidateQueue<T>::CandidateList_t& list = q.m_candidates;
 
    os << "*** CandidateQueue Begin (<id, distance, LSA-type>) ***" << std::endl;
    for (auto iter = list.begin(); iter != list.end(); iter++)
    {
        os << "<" << (*iter)->GetVertexId() << ", " << (*iter)->GetDistanceFromRoot() << ", "
           << (*iter)->GetVertexType() << ">" << std::endl;
    }
    os << "*** CandidateQueue End ***";
    return os;
}
 
template <typename T>
CandidateQueue<T>::CandidateQueue()
    : m_candidates()
{
    NS_LOG_FUNCTION(this);
}
 
template <typename T>
CandidateQueue<T>::~CandidateQueue()
{
    NS_LOG_FUNCTION(this);
    Clear();
}
 
template <typename T>
void
CandidateQueue<T>::Clear()
{
    NS_LOG_FUNCTION(this);
    while (!m_candidates.empty())
    {
        SPFVertex<T>* p = Pop();
        delete p;
        p = nullptr;
    }
}
 
template <typename T>
void
CandidateQueue<T>::Push(SPFVertex<T>* vNew)
{
    NS_LOG_FUNCTION(this << vNew);
 
    auto i = std::upper_bound(m_candidates.begin(),
                              m_candidates.end(),
                              vNew,
                              &CandidateQueue::CompareSPFVertex);
    m_candidates.insert(i, vNew);
}
 
template <typename T>
SPFVertex<T>*
CandidateQueue<T>::Pop()
{
    NS_LOG_FUNCTION(this);
    if (m_candidates.empty())
    {
        return nullptr;
    }
 
    SPFVertex<T>* v = m_candidates.front();
    m_candidates.pop_front();
    return v;
}
 
template <typename T>
SPFVertex<T>*
CandidateQueue<T>::Top() const
{
    NS_LOG_FUNCTION(this);
    if (m_candidates.empty())
    {
        return nullptr;
    }
 
    return m_candidates.front();
}
 
template <typename T>
bool
CandidateQueue<T>::Empty() const
{
    NS_LOG_FUNCTION(this);
    return m_candidates.empty();
}
 
template <typename T>
uint32_t
CandidateQueue<T>::Size() const
{
    NS_LOG_FUNCTION(this);
    return m_candidates.size();
}
 
template <typename T>
SPFVertex<T>*
CandidateQueue<T>::Find(const IpAddress addr) const
{
    NS_LOG_FUNCTION(this);
    auto i = m_candidates.begin();
 
    for (; i != m_candidates.end(); i++)
    {
        SPFVertex<T>* v = *i;
        if (v->GetVertexId() == addr)
        {
            return v;
        }
    }
 
    return nullptr;
}
 
template <typename T>
void
CandidateQueue<T>::Reorder()
{
    NS_LOG_FUNCTION(this);
 
    m_candidates.sort(&CandidateQueue::CompareSPFVertex);
    NS_LOG_LOGIC("After reordering the CandidateQueue");
    NS_LOG_LOGIC(*this);
}
 
/*
 * In this implementation, SPFVertex follows the ordering where
 * a vertex is ranked first if its GetDistanceFromRoot () is smaller;
 * In case of a tie, NetworkLSA is always ranked before RouterLSA.
 *
 * This ordering is necessary for implementing ECMP
 */
template <typename T>
bool
CandidateQueue<T>::CompareSPFVertex(const SPFVertex<T>* v1, const SPFVertex<T>* v2)
{
    NS_LOG_FUNCTION(&v1 << &v2);
 
    bool result = false;
    if (v1->GetDistanceFromRoot() < v2->GetDistanceFromRoot())
    {
        result = true;
    }
    else if (v1->GetDistanceFromRoot() == v2->GetDistanceFromRoot())
    {
        if (v1->GetVertexType() == SPFVertex<T>::VertexNetwork &&
            v2->GetVertexType() == SPFVertex<T>::VertexRouter)
        {
            result = true;
        }
    }
    return result;
}
template class CandidateQueue<Ipv4Manager>;
template class CandidateQueue<Ipv6Manager>;
 
} // namespace ns3