Intrusive doubly-linked list container. Manages a collection of DListEntry nodes embedded in host objects of type T. More...

#include <stk_linked_list.h>

Inheritance diagram for stk::util::DListHead< T, TClosedLoop >:

Collaboration diagram for stk::util::DListHead< T, TClosedLoop >:

Public Types
typedef DListEntry< T, TClosedLoop >	DLEntryType
	Convenience alias for the node type stored in this list.

Public Member Functions
	DListHead ()
	Construct an empty list head (count = 0, first = last = NULL).
size_t	GetSize () const
	Get the number of entries currently in the list.
bool	IsEmpty () const
	Check whether the list contains no entries.
DLEntryType *	GetFirst ()
	Get the first (front) entry without removing it.
const DLEntryType *	GetFirst () const
	Get the first (front) entry without removing it.
DLEntryType *	GetLast ()
	Get the last (back) entry without removing it.
const DLEntryType *	GetLast () const
	Get the last (back) entry without removing it.
void	Clear ()
	Remove and unlink all entries. After this call the list is empty.
void	LinkBack (DLEntryType *entry)
	Append entry to the back of the list (pointer overload).
void	LinkBack (DLEntryType &entry)
	Append entry to the back of the list (reference overload).
void	LinkFront (DLEntryType *entry)
	Prepend entry to the front of the list (pointer overload).
void	LinkFront (DLEntryType &entry)
	Prepend entry to the front of the list (reference overload).
DLEntryType *	PopBack ()
	Remove and return the last entry.
DLEntryType *	PopFront ()
	Remove and return the first entry.
void	Unlink (DLEntryType *entry)
	Remove entry from this list.
void	RelinkTo (DListHead &to)
	Move all entries from this list to the back of to, preserving order.
void	Link (DLEntryType entry, DLEntryType next=nullptr, DLEntryType *prev=nullptr)
	Insert entry into the list between prev and next.

Private Member Functions
void	UpdateEnds ()
	Repair the boundary and circular pointers after every structural change.

Private Attributes
size_t	m_count
	Number of entries currently in the list.
DLEntryType *	m_first
	Pointer to the first (front) entry, or `NULL` when empty.
DLEntryType *	m_last
	Pointer to the last (back) entry, or `NULL` when empty.

Friends
class	DListEntry< T, TClosedLoop >

Detailed Description

template<class T, bool TClosedLoop>
class stk::util::DListHead< T, TClosedLoop >

Intrusive doubly-linked list container. Manages a collection of DListEntry nodes embedded in host objects of type T.

Template Parameters

T	The host class whose instances are stored in this list. Each T must derive from DListEntry<T, TClosedLoop>.
TClosedLoop	When `true` the list is maintained as a circular ring: after every insertion or removal, last->next is set to first and first->prev is set to last. This allows scheduler algorithms to wrap around the end of the list in O(1) without a branch. When `false` the boundary pointers remain `NULL` (standard open list).

Note: Complexity: all operations are O(1) except Clear() and RelinkTo() which are O(n).; An entry may only be in one list at a time. Attempting to insert an already-linked entry will trigger an assertion.; PopBack() and PopFront() call Unlink() internally. Calling them on an empty list will pass NULL to Unlink() and trigger an assertion. Guard with IsEmpty().; Not thread-safe. The caller is responsible for protecting concurrent access with a hw::CriticalSection or equivalent.

Definition at line 223 of file stk_linked_list.h.

Member Typedef Documentation

◆ DLEntryType

template<class T, bool TClosedLoop>

typedef DListEntry<T, TClosedLoop> stk::util::DListHead< T, TClosedLoop >::DLEntryType

Convenience alias for the node type stored in this list.

Definition at line 231 of file stk_linked_list.h.

Constructor & Destructor Documentation

◆ DListHead()

template<class T, bool TClosedLoop>

stk::util::DListHead< T, TClosedLoop >::DListHead ( )

inlineexplicit

Construct an empty list head (count = 0, first = last = NULL).

Definition at line 235 of file stk_linked_list.h.

235 : m_count(0U), m_first(nullptr), m_last(nullptr)

236 {}

stk::util::DListHead

Intrusive doubly-linked list container. Manages a collection of DListEntry nodes embedded in host obj...

Definition stk_linked_list.h:224

stk::util::DListHead::m_first

DLEntryType * m_first

Pointer to the first (front) entry, or NULL when empty.

Definition stk_linked_list.h:446

stk::util::DListHead::m_last

DLEntryType * m_last

Pointer to the last (back) entry, or NULL when empty.

Definition stk_linked_list.h:447

stk::util::DListHead::m_count

size_t m_count

Number of entries currently in the list.

Definition stk_linked_list.h:445

References m_count, m_first, and m_last.

Referenced by RelinkTo().

Here is the caller graph for this function:

Member Function Documentation

◆ Clear()

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::Clear ( )

inline

Remove and unlink all entries. After this call the list is empty.

Note: Runs in O(n). Each entry is individually unlinked so its pointers are reset to NULL and it is left in a clean state suitable for re-insertion.

Definition at line 272 of file stk_linked_list.h.

272{ while (!IsEmpty()) Unlink(m_first); }

stk::util::DListHead::Unlink

void Unlink(DLEntryType *entry)

Remove entry from this list.

Definition stk_linked_list.h:325

stk::util::DListHead::IsEmpty

bool IsEmpty() const

Check whether the list contains no entries.

Definition stk_linked_list.h:246

References IsEmpty(), m_first, and Unlink().

Here is the call graph for this function:

◆ GetFirst() [1/2]

template<class T, bool TClosedLoop>

DLEntryType * stk::util::DListHead< T, TClosedLoop >::GetFirst ( )

inline

Get the first (front) entry without removing it.

Returns: Pointer to the first DListEntry, or NULL if the list is empty.

Definition at line 251 of file stk_linked_list.h.

251{ return m_first; }

References m_first.

Referenced by stk::SchedulabilityCheck::IsSchedulableWCRT().

Here is the caller graph for this function:

◆ GetFirst() [2/2]

template<class T, bool TClosedLoop>

const DLEntryType * stk::util::DListHead< T, TClosedLoop >::GetFirst ( ) const

inline

Get the first (front) entry without removing it.

Returns: Pointer to the first DListEntry, or NULL if the list is empty.

Definition at line 256 of file stk_linked_list.h.

256{ return m_first; }

References m_first.

◆ GetLast() [1/2]

template<class T, bool TClosedLoop>

DLEntryType * stk::util::DListHead< T, TClosedLoop >::GetLast ( )

inline

Get the last (back) entry without removing it.

Returns: Pointer to the last DListEntry, or NULL if the list is empty.

Definition at line 261 of file stk_linked_list.h.

261{ return m_last; }

References m_last.

◆ GetLast() [2/2]

template<class T, bool TClosedLoop>

const DLEntryType * stk::util::DListHead< T, TClosedLoop >::GetLast ( ) const

inline

Get the last (back) entry without removing it.

Returns: Pointer to the last DListEntry, or NULL if the list is empty.

Definition at line 266 of file stk_linked_list.h.

266{ return m_last; }

References m_last.

◆ GetSize()

template<class T, bool TClosedLoop>

size_t stk::util::DListHead< T, TClosedLoop >::GetSize ( ) const

inline

Get the number of entries currently in the list.

Returns: Element count.

Definition at line 241 of file stk_linked_list.h.

241{ return m_count; }

References m_count.

Referenced by stk::SchedulabilityCheck::IsSchedulableWCRT().

Here is the caller graph for this function:

◆ IsEmpty()

template<class T, bool TClosedLoop>

bool stk::util::DListHead< T, TClosedLoop >::IsEmpty ( ) const

inline

Check whether the list contains no entries.

Returns: true if empty; false otherwise.

Definition at line 246 of file stk_linked_list.h.

246{ return (m_count == 0U); }

References m_count.

Referenced by Clear(), RelinkTo(), and UpdateEnds().

Here is the caller graph for this function:

◆ Link()

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::Link	(	DLEntryType *	entry,
		DLEntryType *	next = nullptr,
		DLEntryType *	prev = nullptr )

inline

Insert entry into the list between prev and next.

Parameters

[in]	entry	Entry to insert. Must be non-NULL and not currently linked.
[in]	next	Entry that will follow entry after insertion, or `NULL` to append.
[in]	prev	Entry that will precede entry after insertion, or `NULL` to prepend.

Note: When prev is NULL the method treats this as a front-insertion: next is overridden to m_first so entry becomes the new first element.; Updates m_first and m_last as needed. For closed-loop lists, calls UpdateEnds() to maintain the circular back-link from last to first.

Definition at line 372 of file stk_linked_list.h.

    {
        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();
        }
    }

References __stk_constexpr_cpp17, stk::util::DListEntry< T, TClosedLoop >::GetNext(), stk::util::DListEntry< T, TClosedLoop >::GetPrev(), stk::util::DListEntry< T, TClosedLoop >::IsLinked(), stk::util::DListEntry< T, TClosedLoop >::Link(), m_count, m_first, m_last, STK_ASSERT, and UpdateEnds().

Referenced by LinkBack(), LinkBack(), LinkFront(), and LinkFront().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LinkBack() [1/2]

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::LinkBack ( DLEntryType & entry )

inline

Append entry to the back of the list (reference overload).

Parameters

[in] entry Entry to insert. Must not already be linked to any list.

Definition at line 282 of file stk_linked_list.h.

282{ Link(&entry, nullptr, m_last); }

References Link(), and m_last.

Here is the call graph for this function:

◆ LinkBack() [2/2]

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::LinkBack ( DLEntryType * entry )

inline

Append entry to the back of the list (pointer overload).

Parameters

[in] entry Entry to insert. Must not already be linked to any list.

Definition at line 277 of file stk_linked_list.h.

277{ Link(entry, nullptr, m_last); }

References Link(), and m_last.

Referenced by RelinkTo().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LinkFront() [1/2]

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::LinkFront ( DLEntryType & entry )

inline

Prepend entry to the front of the list (reference overload).

Parameters

[in] entry Entry to insert. Must not already be linked to any list.

Definition at line 294 of file stk_linked_list.h.

294{ Link(&entry, m_last, nullptr); }

References Link(), and m_last.

Here is the call graph for this function:

◆ LinkFront() [2/2]

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::LinkFront ( DLEntryType * entry )

inline

Prepend entry to the front of the list (pointer overload).

Parameters

[in] entry Entry to insert. Must not already be linked to any list.

Note: In an open list, entry becomes the new first element. In a closed loop, the circular pointers are updated by UpdateEnds().

Definition at line 289 of file stk_linked_list.h.

289{ Link(entry, m_last, nullptr); }

References Link(), and m_last.

Here is the call graph for this function:

◆ PopBack()

template<class T, bool TClosedLoop>

DLEntryType * stk::util::DListHead< T, TClosedLoop >::PopBack ( )

inline

Remove and return the last entry.

Returns: Pointer to the removed entry.

Warning: Triggers an assertion if the list is empty (Unlink receives NULL). Always check IsEmpty() before calling.

Definition at line 301 of file stk_linked_list.h.

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

References m_last, and Unlink().

Here is the call graph for this function:

◆ PopFront()

template<class T, bool TClosedLoop>

DLEntryType * stk::util::DListHead< T, TClosedLoop >::PopFront ( )

inline

Remove and return the first entry.

Returns: Pointer to the removed entry.

Warning: Triggers an assertion if the list is empty (Unlink receives NULL). Always check IsEmpty() before calling.

Definition at line 313 of file stk_linked_list.h.

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

References m_first, and Unlink().

Referenced by RelinkTo().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ RelinkTo()

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::RelinkTo ( DListHead< T, TClosedLoop > & to )

inline

Move all entries from this list to the back of to, preserving order.

Parameters

[in] to Destination list. Must not be the same object as *this.

Note: After this call *this is empty and every entry that was here is now at the back of to, in the same relative order.; Asserts that to is not the same list as *this.

Definition at line 353 of file stk_linked_list.h.

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

References DListHead(), IsEmpty(), LinkBack(), PopFront(), and STK_ASSERT.

Here is the call graph for this function:

◆ Unlink()

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::Unlink ( DLEntryType * entry )

inline

Remove entry from this list.

Parameters

[in] entry Entry to remove. Must be non-NULL, currently linked, and owned by this list.

Note: Asserts that entry is non-NULL, is linked, and belongs to this head. Decrements m_count and calls UpdateEnds() to repair boundary and closed-loop pointers.

Definition at line 325 of file stk_linked_list.h.

    {
        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();
    }

References stk::util::DListEntry< T, TClosedLoop >::GetHead(), stk::util::DListEntry< T, TClosedLoop >::GetNext(), stk::util::DListEntry< T, TClosedLoop >::GetPrev(), stk::util::DListEntry< T, TClosedLoop >::IsLinked(), m_count, m_first, m_last, STK_ASSERT, stk::util::DListEntry< T, TClosedLoop >::Unlink(), and UpdateEnds().

Referenced by Clear(), PopBack(), and PopFront().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ UpdateEnds()

template<class T, bool TClosedLoop>

void stk::util::DListHead< T, TClosedLoop >::UpdateEnds ( )

inlineprivate

Repair the boundary and circular pointers after every structural change.

Note

Called after every insertion and removal. Two responsibilities:

If the list is now empty, resets m_first and m_last to NULL so the head is in a canonical empty state.
If TClosedLoop is true and the list is non-empty, sets m_last->m_next = m_first and m_first->m_prev = m_last to maintain the circular invariant.

For open lists (TClosedLoop == false) only the empty-list reset runs; the branch is eliminated at compile time by the constant template parameter.

Definition at line 428 of file stk_linked_list.h.

    {
        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;
            }
        }
    }

References __stk_constexpr_cpp17, IsEmpty(), m_first, and m_last.

Referenced by Link(), and Unlink().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DListEntry< T, TClosedLoop >

template<class T, bool TClosedLoop>

friend class DListEntry< T, TClosedLoop >

friend

Definition at line 200 of file stk_linked_list.h.

Member Data Documentation

◆ m_count

template<class T, bool TClosedLoop>

size_t stk::util::DListHead< T, TClosedLoop >::m_count

private

Number of entries currently in the list.

Definition at line 445 of file stk_linked_list.h.

Referenced by DListHead(), GetSize(), IsEmpty(), Link(), and Unlink().

◆ m_first

template<class T, bool TClosedLoop>

DLEntryType* stk::util::DListHead< T, TClosedLoop >::m_first

private

Pointer to the first (front) entry, or NULL when empty.

Definition at line 446 of file stk_linked_list.h.

Referenced by Clear(), DListHead(), GetFirst(), GetFirst(), Link(), PopFront(), Unlink(), and UpdateEnds().

◆ m_last

template<class T, bool TClosedLoop>

DLEntryType* stk::util::DListHead< T, TClosedLoop >::m_last

private

Pointer to the last (back) entry, or NULL when empty.

Definition at line 447 of file stk_linked_list.h.

Referenced by DListHead(), GetLast(), GetLast(), Link(), LinkBack(), LinkBack(), LinkFront(), LinkFront(), PopBack(), Unlink(), and UpdateEnds().

The documentation for this class was generated from the following file:

stk_linked_list.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ DLEntryType

Constructor & Destructor Documentation

◆ DListHead()

Member Function Documentation

◆ Clear()

◆ GetFirst() [1/2]

◆ GetFirst() [2/2]

◆ GetLast() [1/2]

◆ GetLast() [2/2]

◆ GetSize()

◆ IsEmpty()

◆ Link()

◆ LinkBack() [1/2]

◆ LinkBack() [2/2]

◆ LinkFront() [1/2]

◆ LinkFront() [2/2]

◆ PopBack()

◆ PopFront()

◆ RelinkTo()

◆ Unlink()

◆ UpdateEnds()

Friends And Related Symbol Documentation

◆ DListEntry< T, TClosedLoop >

Member Data Documentation

◆ m_count

◆ m_first

◆ m_last