stk_linked_list.h

Go to the documentation of this file.

/*
 * SuperTinyKernel(TM) RTOS: Lightweight High-Performance Deterministic C++ RTOS for Embedded Systems.
 *
 * Source: https://github.com/SuperTinyKernel-RTOS
 *
 * Copyright (c) 2022-2026 Neutron Code Limited <stk@neutroncode.com>. All Rights Reserved.
 * License: MIT License, see LICENSE for a full text.
 */
 
#ifndef STK_LINKED_LIST_H_
#define STK_LINKED_LIST_H_

 
namespace stk {
namespace util {
 
// Forward declaration required so DListEntry can reference DListHead as a friend
// and store a back-pointer to the owning list head.
template <class T, bool _ClosedLoop> class DListHead;

template <class T, bool _ClosedLoop> class DListEntry
{
    friend class DListHead<T, _ClosedLoop>;
 
public:
    explicit DListEntry() : m_head(nullptr), m_next(nullptr), m_prev(nullptr)
    {}

    typedef DListEntry<T, _ClosedLoop> DLEntryType;

    typedef DListHead<T, _ClosedLoop>  DLHeadType;

    DLHeadType *GetHead() const { return m_head; }

    DLEntryType *GetNext() const { return m_next; }

    DLEntryType *GetPrev() const { return m_prev; }

    bool IsLinked() const { return (GetHead() != nullptr); }

    operator T *() { return static_cast<T *>(this); }

    operator const T *() const { return static_cast<const T *>(this); }
 
protected:
    ~DListEntry()
    {}
 
private:
    void Link(DLHeadType *head, DLEntryType *next, DLEntryType *prev)
    {
        m_head = head;
        m_next = next;
        m_prev = prev;
 
        if (m_prev != nullptr)
            m_prev->m_next = this;
 
        if (m_next != nullptr)
            m_next->m_prev = this;
    }

    void Unlink()
    {
        if (m_prev != nullptr)
            m_prev->m_next = m_next;
 
        if (m_next != nullptr)
            m_next->m_prev = m_prev;
 
        m_head = nullptr;
        m_next = nullptr;
        m_prev = nullptr;
    }
 
    DLHeadType  *m_head; 
    DLEntryType *m_next; 
    DLEntryType *m_prev; 
};

template <class T, bool _ClosedLoop> class DListHead
{
    friend class DListEntry<T, _ClosedLoop>;
 
public:
    typedef DListEntry<T, _ClosedLoop> DLEntryType;

    explicit DListHead(): m_count(0), m_first(nullptr), m_last(nullptr)
    {}

    size_t GetSize() const { return m_count; }

    bool IsEmpty() const { return (m_count == 0); }

    DLEntryType *GetFirst() const { return m_first; }

    DLEntryType *GetLast() const { return m_last; }

    void Clear() { while (!IsEmpty()) Unlink(m_first); }

    void LinkBack(DLEntryType *entry) { Link(entry, nullptr, m_last); }

    void LinkBack(DLEntryType &entry) { Link(&entry, nullptr, m_last); }

    void LinkFront(DLEntryType *entry) { Link(entry, m_last, nullptr); }

    void LinkFront(DLEntryType &entry) { Link(&entry, m_last, nullptr); }

    DLEntryType *PopBack()
    {
        DLEntryType *ret = m_last;
        Unlink(ret);
        return ret;
    }

    DLEntryType *PopFront()
    {
        DLEntryType *ret = m_first;
        Unlink(ret);
        return ret;
    }

    void Unlink(DLEntryType *entry)
    {
        STK_ASSERT(entry != nullptr);
        STK_ASSERT(entry->IsLinked());
        STK_ASSERT(entry->GetHead() == this);
 
        if (m_first == entry)
            m_first = entry->GetNext();
 
        if (m_last == entry)
            m_last = entry->GetPrev();
 
        entry->Unlink();
        --m_count;
 
        UpdateEnds();
    }

    void RelinkTo(DListHead &to)
    {
        STK_ASSERT(&to != this);
 
        while (!this->IsEmpty())
        {
            to.LinkBack(this->PopFront());
        }
    }

    void Link(DLEntryType *entry, DLEntryType *next = nullptr, DLEntryType *prev = nullptr)
    {
        STK_ASSERT(entry != nullptr);
        STK_ASSERT(!entry->IsLinked());
 
        if (prev == nullptr)
            next = m_first;
 
        ++m_count;
        entry->Link(this, next, prev);
 
        if ((m_first == nullptr) || (m_first == entry->GetNext()))
            m_first = entry;
 
        if ((m_last == nullptr) || (m_last == entry->GetPrev()))
            m_last = entry;
 
        if (_ClosedLoop)
            UpdateEnds();
    }
 
private:
    void UpdateEnds()
    {
        if (IsEmpty())
        {
            m_first = nullptr;
            m_last  = nullptr;
        }
        else
        if (_ClosedLoop)
        {
            m_first->m_prev = m_last;
            m_last->m_next = m_first;
        }
    }
 
    size_t       m_count; 
    DLEntryType *m_first; 
    DLEntryType *m_last;  
};
 
} // namespace util
} // namespace stk
 
 
#endif /* STK_LINKED_LIST_H_ */