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 TClosedLoop> class DListHead;

template <class T, bool TClosedLoop> class DListEntry
{
    friend class DListHead<T, TClosedLoop>;
 
public:
    explicit DListEntry() : m_head(nullptr), m_next(nullptr), m_prev(nullptr)
    {}
    
    enum { DLEntryTag = 1 };

    typedef DListEntry<T, TClosedLoop> DLEntryType;

    typedef DListHead<T, TClosedLoop>  DLHeadType;

    DLHeadType *GetHead() { return m_head; }
    
    const DLHeadType *GetHead() const { return m_head; }

    DLEntryType *GetNext() { return m_next; }
    
    const DLEntryType *GetNext() const { return m_next; }

    DLEntryType *GetPrev() { return m_prev; }
    
    const 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() = default;
 
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 TClosedLoop> class DListHead
{
    friend class DListEntry<T, TClosedLoop>;
 
public:
    typedef DListEntry<T, TClosedLoop> DLEntryType;

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

    size_t GetSize() const { return m_count; }

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

    DLEntryType *GetFirst() { return m_first; }

    const DLEntryType *GetFirst() const { return m_first; }
    
    DLEntryType *GetLast() { return m_last; }
    
    const 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;
        }
        else if (m_first == entry->GetNext())
        {
            m_first = entry;
        }        
        else
        {
            // noop
        }
 
        if (m_last == nullptr)
        {
            m_last = entry;
        }
        else if (m_last == entry->GetPrev())
        {
            m_last = entry;
        }
        else
        {
            // noop
        }
 
        if __stk_constexpr_cpp17 (TClosedLoop)
        {
            UpdateEnds();
        }
    }
 
private:
    void UpdateEnds()
    {
        if (IsEmpty())
        {
            m_first = nullptr;
            m_last  = nullptr;
        }
        else 
        {
            if __stk_constexpr_cpp17 (TClosedLoop)
            {
                m_first->m_prev = m_last;
                m_last->m_next  = m_first;
            }
        }
    }
 
    size_t       m_count; 
    DLEntryType *m_first; 
    DLEntryType *m_last;  
};

struct DListCast
{
    template <typename TTargetType, typename TSourceType>
    static __stk_forceinline TTargetType *ListEntryToParent(TSourceType *const lentry)
    {
        STK_STATIC_ASSERT_N(TT, TTargetType::DLEntryTag == 1); // TTargetType must inherit DLEntryType
        STK_STATIC_ASSERT_N(ST, TSourceType::DLEntryTag == 1); // TSourceType must inherit DLEntryType
      
        return static_cast<TTargetType *>(lentry);
    }
};
 
} // namespace util
} // namespace stk
 
 
#endif /* STK_LINKED_LIST_H_ */