linked_list.hpp

Go to the documentation of this file.

/*
 * Singly-linked list.
 * Copyright (C) 2014 Pavel Kirienko <pavel.kirienko@gmail.com>
 */

#ifndef UAVCAN_UTIL_LINKED_LIST_HPP_INCLUDED
#define UAVCAN_UTIL_LINKED_LIST_HPP_INCLUDED

#include <cstdlib>
#include <cassert>
#include <uavcan/build_config.hpp>
#include <uavcan/util/templates.hpp>

namespace uavcan
{
template <typename T>
class UAVCAN_EXPORT LinkedListNode : Noncopyable
{
    T* next_;

protected:
    LinkedListNode()
        : next_(UAVCAN_NULLPTR)
    { }

    ~LinkedListNode() { }

public:
    T* getNextListNode() const { return next_; }

    void setNextListNode(T* node)
    {
        next_ = node;
    }
};

template <typename T>
class UAVCAN_EXPORT LinkedListRoot : Noncopyable
{
    T* root_;

public:
    LinkedListRoot()
        : root_(UAVCAN_NULLPTR)
    { }

    T* get() const { return root_; }
    bool isEmpty() const { return get() == UAVCAN_NULLPTR; }

    unsigned getLength() const;

    void insert(T* node);

    template <typename Predicate>
    void insertBefore(T* node, Predicate predicate);

    void remove(const T* node);
};

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

/*
 * LinkedListRoot<>
 */
template <typename T>
unsigned LinkedListRoot<T>::getLength() const
{
    T* node = root_;
    unsigned cnt = 0;
    while (node)
    {
        cnt++;
        node = node->getNextListNode();
    }
    return cnt;
}

template <typename T>
void LinkedListRoot<T>::insert(T* node)
{
    if (node == UAVCAN_NULLPTR)
    {
        UAVCAN_ASSERT(0);
        return;
    }
    remove(node);  // Making sure there will be no loops
    node->setNextListNode(root_);
    root_ = node;
}

template <typename T>
template <typename Predicate>
void LinkedListRoot<T>::insertBefore(T* node, Predicate predicate)
{
    if (node == UAVCAN_NULLPTR)
    {
        UAVCAN_ASSERT(0);
        return;
    }

    remove(node);

    if (root_ == UAVCAN_NULLPTR || predicate(root_))
    {
        node->setNextListNode(root_);
        root_ = node;
    }
    else
    {
        T* p = root_;
        while (p->getNextListNode())
        {
            if (predicate(p->getNextListNode()))
            {
                break;
            }
            p = p->getNextListNode();
        }
        node->setNextListNode(p->getNextListNode());
        p->setNextListNode(node);
    }
}

template <typename T>
void LinkedListRoot<T>::remove(const T* node)
{
    if (root_ == UAVCAN_NULLPTR || node == UAVCAN_NULLPTR)
    {
        return;
    }

    if (root_ == node)
    {
        root_ = root_->getNextListNode();
    }
    else
    {
        T* p = root_;
        while (p->getNextListNode())
        {
            if (p->getNextListNode() == node)
            {
                p->setNextListNode(p->getNextListNode()->getNextListNode());
                break;
            }
            p = p->getNextListNode();
        }
    }
}

}

#endif // UAVCAN_UTIL_LINKED_LIST_HPP_INCLUDED