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, _ClosedLoop >:

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

Public Types
typedef DListEntry< T, _ClosedLoop >	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 () const
	Get the first (front) entry without removing it.
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, _ClosedLoop >

Detailed Description

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

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, _ClosedLoop>.
_ClosedLoop	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 195 of file stk_linked_list.h.

Member Typedef Documentation

◆ DLEntryType

template<class T, bool _ClosedLoop>

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

Convenience alias for the node type stored in this list.

Definition at line 203 of file stk_linked_list.h.

Constructor & Destructor Documentation

◆ DListHead()

template<class T, bool _ClosedLoop>

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

inlineexplicit

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

Definition at line 207 of file stk_linked_list.h.

207 : m_count(0), m_first(nullptr), m_last(nullptr)

208 {}

stk::util::DListHead::m_first

DLEntryType * m_first

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

Definition stk_linked_list.h:378

stk::util::DListHead::m_count

size_t m_count

Number of entries currently in the list.

Definition stk_linked_list.h:377

stk::util::DListHead::m_last

DLEntryType * m_last

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

Definition stk_linked_list.h:379

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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 234 of file stk_linked_list.h.

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

stk::util::DListHead::IsEmpty

bool IsEmpty() const

Check whether the list contains no entries.

Definition stk_linked_list.h:218

stk::util::DListHead::Unlink

void Unlink(DLEntryType *entry)

Remove entry from this list.

Definition stk_linked_list.h:287

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

Here is the call graph for this function:

◆ GetFirst()

template<class T, bool _ClosedLoop>

DLEntryType * stk::util::DListHead< T, _ClosedLoop >::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 223 of file stk_linked_list.h.

223{ return m_first; }

References m_first.

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

Here is the caller graph for this function:

◆ GetLast()

template<class T, bool _ClosedLoop>

DLEntryType * stk::util::DListHead< T, _ClosedLoop >::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 228 of file stk_linked_list.h.

228{ return m_last; }

References m_last.

◆ GetSize()

template<class T, bool _ClosedLoop>

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

inline

Get the number of entries currently in the list.

Returns: Element count.

Definition at line 213 of file stk_linked_list.h.

213{ return m_count; }

References m_count.

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

Here is the caller graph for this function:

◆ IsEmpty()

template<class T, bool _ClosedLoop>

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

inline

Check whether the list contains no entries.

Returns: true if empty; false otherwise.

Definition at line 218 of file stk_linked_list.h.

218{ return (m_count == 0); }

References m_count.

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

Here is the caller graph for this function:

◆ Link()

template<class T, bool _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 330 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->GetNext()))
            m_first = entry;
 
        if ((m_last == nullptr) || (m_last == entry->GetPrev()))
            m_last = entry;
 
        if (_ClosedLoop)
            UpdateEnds();
    }

References stk::util::DListEntry< T, _ClosedLoop >::GetNext(), stk::util::DListEntry< T, _ClosedLoop >::GetPrev(), stk::util::DListEntry< T, _ClosedLoop >::IsLinked(), stk::util::DListEntry< T, _ClosedLoop >::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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 244 of file stk_linked_list.h.

244{ 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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 239 of file stk_linked_list.h.

239{ 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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 256 of file stk_linked_list.h.

256{ 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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 251 of file stk_linked_list.h.

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

References Link(), and m_last.

Here is the call graph for this function:

◆ PopBack()

template<class T, bool _ClosedLoop>

DLEntryType * stk::util::DListHead< T, _ClosedLoop >::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 263 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 _ClosedLoop>

DLEntryType * stk::util::DListHead< T, _ClosedLoop >::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 275 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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::RelinkTo ( DListHead< T, _ClosedLoop > & 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 311 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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 287 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, _ClosedLoop >::GetHead(), stk::util::DListEntry< T, _ClosedLoop >::GetNext(), stk::util::DListEntry< T, _ClosedLoop >::GetPrev(), stk::util::DListEntry< T, _ClosedLoop >::IsLinked(), m_count, m_first, m_last, STK_ASSERT, stk::util::DListEntry< T, _ClosedLoop >::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 _ClosedLoop>

void stk::util::DListHead< T, _ClosedLoop >::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 _ClosedLoop 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 (_ClosedLoop == false) only the empty-list reset runs; the branch is eliminated at compile time by the constant template parameter.

Definition at line 362 of file stk_linked_list.h.

    {
        if (IsEmpty())
        {
            m_first = nullptr;
            m_last  = nullptr;
        }
        else
        if (_ClosedLoop)
        {
            m_first->m_prev = m_last;
            m_last->m_next = m_first;
        }
    }

References 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, _ClosedLoop >

template<class T, bool _ClosedLoop>

friend class DListEntry< T, _ClosedLoop >

friend

Definition at line 172 of file stk_linked_list.h.

Member Data Documentation

◆ m_count

template<class T, bool _ClosedLoop>

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

private

Number of entries currently in the list.

Definition at line 377 of file stk_linked_list.h.

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

◆ m_first

template<class T, bool _ClosedLoop>

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

private

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

Definition at line 378 of file stk_linked_list.h.

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

◆ m_last

template<class T, bool _ClosedLoop>

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

private

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

Definition at line 379 of file stk_linked_list.h.

Referenced by DListHead(), 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()

◆ GetLast()

◆ 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, _ClosedLoop >

Member Data Documentation

◆ m_count

◆ m_first

◆ m_last