heap-scheduler.cc

Go to the documentation of this file.

/*
 * Copyright (c) 2006 INRIA
 * Copyright (c) 2005 Mathieu Lacage
 *
 * 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 "heap-scheduler.h"
 
#include "assert.h"
#include "event-impl.h"
#include "log.h"
 
namespace ns3
{
 
NS_LOG_COMPONENT_DEFINE("HeapScheduler");
 
NS_OBJECT_ENSURE_REGISTERED(HeapScheduler);
 
TypeId
HeapScheduler::GetTypeId()
{
    static TypeId tid = TypeId("ns3::HeapScheduler")
                            .SetParent<Scheduler>()
                            .SetGroupName("Core")
                            .AddConstructor<HeapScheduler>();
    return tid;
}
 
HeapScheduler::HeapScheduler()
{
    NS_LOG_FUNCTION(this);
    // we purposely waste an item at the start of
    // the array to make sure the indexes in the
    // array start at one.
    Scheduler::Event empty = {nullptr, {0, 0}};
    m_heap.push_back(empty);
}
 
HeapScheduler::~HeapScheduler()
{
    NS_LOG_FUNCTION(this);
}
 
std::size_t
HeapScheduler::Parent(std::size_t id) const
{
    NS_LOG_FUNCTION(this << id);
    return id / 2;
}
 
std::size_t
HeapScheduler::Sibling(std::size_t id) const
{
    NS_LOG_FUNCTION(this << id);
    return id + 1;
}
 
std::size_t
HeapScheduler::LeftChild(std::size_t id) const
{
    NS_LOG_FUNCTION(this << id);
    return id * 2;
}
 
std::size_t
HeapScheduler::RightChild(std::size_t id) const
{
    NS_LOG_FUNCTION(this << id);
    return id * 2 + 1;
}
 
std::size_t
HeapScheduler::Root() const
{
    NS_LOG_FUNCTION(this);
    return 1;
}
 
bool
HeapScheduler::IsRoot(std::size_t id) const
{
    NS_LOG_FUNCTION(this << id);
    return (id == Root());
}
 
std::size_t
HeapScheduler::Last() const
{
    NS_LOG_FUNCTION(this);
    return m_heap.size() - 1;
}
 
bool
HeapScheduler::IsBottom(std::size_t id) const
{
    NS_LOG_FUNCTION(this << id);
    return (id >= m_heap.size());
}
 
void
HeapScheduler::Exch(std::size_t a, std::size_t b)
{
    NS_LOG_FUNCTION(this << a << b);
    NS_ASSERT(b < m_heap.size() && a < m_heap.size());
    NS_LOG_DEBUG("Exch " << a << ", " << b);
    Event tmp(m_heap[a]);
    m_heap[a] = m_heap[b];
    m_heap[b] = tmp;
}
 
bool
HeapScheduler::IsLessStrictly(std::size_t a, std::size_t b) const
{
    NS_LOG_FUNCTION(this << a << b);
    return m_heap[a] < m_heap[b];
}
 
std::size_t
HeapScheduler::Smallest(std::size_t a, std::size_t b) const
{
    NS_LOG_FUNCTION(this << a << b);
    return IsLessStrictly(a, b) ? a : b;
}
 
bool
HeapScheduler::IsEmpty() const
{
    NS_LOG_FUNCTION(this);
    return (m_heap.size() == 1);
}
 
void
HeapScheduler::BottomUp()
{
    NS_LOG_FUNCTION(this);
    std::size_t index = Last();
    while (!IsRoot(index) && IsLessStrictly(index, Parent(index)))
    {
        Exch(index, Parent(index));
        index = Parent(index);
    }
}
 
void
HeapScheduler::TopDown(std::size_t start)
{
    NS_LOG_FUNCTION(this << start);
    std::size_t index = start;
    std::size_t right = RightChild(index);
    while (!IsBottom(right))
    {
        std::size_t left = LeftChild(index);
        std::size_t tmp = Smallest(left, right);
        if (IsLessStrictly(index, tmp))
        {
            return;
        }
        Exch(index, tmp);
        index = tmp;
        right = RightChild(index);
    }
    if (IsBottom(index))
    {
        return;
    }
    NS_ASSERT(!IsBottom(index));
    std::size_t left = LeftChild(index);
    if (IsBottom(left))
    {
        return;
    }
    if (IsLessStrictly(index, left))
    {
        return;
    }
    Exch(index, left);
}
 
void
HeapScheduler::Insert(const Event& ev)
{
    NS_LOG_FUNCTION(this << &ev);
    m_heap.push_back(ev);
    BottomUp();
}
 
Scheduler::Event
HeapScheduler::PeekNext() const
{
    NS_LOG_FUNCTION(this);
    return m_heap[Root()];
}
 
Scheduler::Event
HeapScheduler::RemoveNext()
{
    NS_LOG_FUNCTION(this);
    Event next = m_heap[Root()];
    Exch(Root(), Last());
    m_heap.pop_back();
    TopDown(Root());
    return next;
}
 
void
HeapScheduler::Remove(const Event& ev)
{
    NS_LOG_FUNCTION(this << &ev);
    std::size_t uid = ev.key.m_uid;
    for (std::size_t i = 1; i < m_heap.size(); i++)
    {
        if (uid == m_heap[i].key.m_uid)
        {
            NS_ASSERT(m_heap[i].impl == ev.impl);
            Exch(i, Last());
            m_heap.pop_back();
            TopDown(i);
            return;
        }
    }
    NS_ASSERT(false);
}
 
} // namespace ns3