#include <uLib/ListFunc.h>

Inheritance diagram for DLinkList:

Detailed Description

DLinkList is a semi-circular double linked list manipulation class.
That is, the first and last entries always point to the list head, not to each other.
The protected LIST_ENTRY is the list head.

One of it's more powerful features is DLinkList::QuickSort(),
which performs it's work by swapping links, not node data,
meaning You can sort large nodes without performance penalty.

Working with legacy LIST_ENTRY structs: DLinkList works with pointers to LIST_ENTRY, so it doesn't care if Your struct
is a C++ direct descendant of LIST_ENTRY, or has a LIST_ENTRY as it's first member.
The only important thing is that Flink and Blink are it's first physical entities.

How you allocate and deallocate Your structs is entirely up to Your discretion.
Just make sure to provide the proper callback for DLinkList::RemoveAll(), to match
how You chose to allocate Your structs.

Definition at line 184 of file ListFunc.h.

Public Data
UINT	Count

bool	SafeRemove

Public Functions
	DLinkList (bool Safe=true)

	DLinkList (PLIST_ENTRY ListHead, bool Safe)

	~DLinkList ()

PDLinkList	operator= (PLIST_ENTRY ListHead)

PLIST_ENTRY	operator+= (PLIST_ENTRY Entry)

PLIST_ENTRY	operator -= (PLIST_ENTRY Entry)

bool	IsEmpty ()

bool	Exist (PLIST_ENTRY Entry)

PLIST_ENTRY	GetFirst ()

PLIST_ENTRY	GetLast ()

PLIST_ENTRY	GetNext (PLIST_ENTRY Current)

PLIST_ENTRY	GetPrev (PLIST_ENTRY Current)

PLIST_ENTRY	Append (PLIST_ENTRY Entry)

PLIST_ENTRY	Prepend (PLIST_ENTRY Entry)

PLIST_ENTRY	RemoveEntry (PLIST_ENTRY Entry)

PLIST_ENTRY	RemoveFirst ()

PLIST_ENTRY	RemoveLast ()

void	RemoveAll (PDListFunc ItemAction, void *UserData=NULL)

PLIST_ENTRY	Push (PLIST_ENTRY Entry)

PLIST_ENTRY	Pull ()

PLIST_ENTRY	Pop ()

PLIST_ENTRY	operator [] (size_t Index)

bool	ForEach (PDListFunc Action, void *UserData=NULL)

PLIST_ENTRY	FirstThat (PDListFunc Match, void *UserData=NULL)

PLIST_ENTRY	LastThat (PDListFunc Match, void *UserData=NULL)

void	QuickSort (PDListComp Compare, void *UserData=NULL)

UINT	AppendList (IN PLIST_ENTRY ListToAppend, OPTOUT PLIST_ENTRY *ppFirst)

UINT	AppendList (IN PDLinkList ListToAppend, OPTOUT PLIST_ENTRY *ppFirst)

UINT	operator+= (PDLinkList ListToAppend)

UINT	ExportToListHead (PLIST_ENTRY ListHead)

UINT	ImportFromListHead (IN PLIST_ENTRY ListHead, OPTOUT PLIST_ENTRY *ppFirst)

UINT	ExportToHeadlessList (PLIST_ENTRY *Circular)

UINT	ImportHeadlessList (IN PLIST_ENTRY Circular, OPTOUT PLIST_ENTRY *ppFirst)

Additional Inherited Members
Protected Attributes inherited from LIST_ENTRY
struct _LIST_ENTRY *	Flink

struct _LIST_ENTRY *	Blink

Constructor & Destructor Documentation

◆ DLinkList() [1/2]

DLinkList::DLinkList ( bool Safe = true )

Default constructor.

Definition at line 70 of file ListCls.cpp.

◆ DLinkList() [2/2]

DLinkList::DLinkList	(	PLIST_ENTRY	ListHead,
		bool	Safe
	)

Special constuctor to pick up (re-head) a plain NT list head.

Side Effects: ListHead will be reset to an empty list after the list is re-headed to 'this', to prevent cross-link errors.

Definition at line 77 of file ListCls.cpp.

◆ ~DLinkList()

DLinkList::~DLinkList ( )

DLinkList doesn't need a destructor since it doesn't allocate anything.
However, it is included, to emit a debugger message if the list is not empty.

Definition at line 83 of file ListCls.cpp.

Member Function Documentation

◆ operator=()

PDLinkList DLinkList::operator= ( PLIST_ENTRY ListHead )

operator=( PLIST_ENTRY ListHead ) usurps the ListHead list.
The DLinkList instance must be empty before using this operator.

Returns: Returns this on success, else NULL (ListHead is empty, or this is not).

Side Effects: ListHead is set empty to prevent cross-link errors which might otherwise occur.

Definition at line 407 of file ListCls.cpp.

◆ operator+=() [1/2]

PLIST_ENTRY DLinkList::operator+= ( PLIST_ENTRY Entry )

inline

Append an entry.

Definition at line 222 of file ListFunc.h.

◆ operator -=()

PLIST_ENTRY DLinkList::operator -= ( PLIST_ENTRY Entry )

inline

Remove an entry.

Definition at line 223 of file ListFunc.h.

◆ IsEmpty()

bool DLinkList::IsEmpty ( )

inline

Definition at line 225 of file ListFunc.h.

◆ Exist()

bool DLinkList::Exist ( PLIST_ENTRY Entry )

Returns true if Entry is found.

Definition at line 145 of file ListCls.cpp.

◆ GetFirst()

PLIST_ENTRY DLinkList::GetFirst ( )

inline

Definition at line 228 of file ListFunc.h.

◆ GetLast()

PLIST_ENTRY DLinkList::GetLast ( )

inline

Definition at line 229 of file ListFunc.h.

◆ GetNext()

PLIST_ENTRY DLinkList::GetNext ( PLIST_ENTRY Current )

GetNext() and GetPrev() provides fully circular access to this list.
For performance reasons, these two does not validate Current,
so be sure to use an entry that is in the list, lest Hell break loose.

Returns: Next/Previous entry, or NULL (if the list is empty).

Definition at line 191 of file ListCls.cpp.

◆ GetPrev()

PLIST_ENTRY DLinkList::GetPrev ( PLIST_ENTRY Current )

See GetNext().

Definition at line 202 of file ListCls.cpp.

◆ Append()

PLIST_ENTRY DLinkList::Append ( PLIST_ENTRY Entry )

Insert at tail, i.e InsertTailList

Definition at line 90 of file ListCls.cpp.

◆ Prepend()

PLIST_ENTRY DLinkList::Prepend ( PLIST_ENTRY Entry )

Insert at head, i.e InsertHeadList

Definition at line 103 of file ListCls.cpp.

◆ RemoveEntry()

PLIST_ENTRY DLinkList::RemoveEntry ( PLIST_ENTRY Entry )

Returns Entry if removed, else NULL.

Definition at line 213 of file ListCls.cpp.

◆ RemoveFirst()

PLIST_ENTRY DLinkList::RemoveFirst ( )

Remove at head.

Definition at line 231 of file ListCls.cpp.

◆ RemoveLast()

PLIST_ENTRY DLinkList::RemoveLast ( )

Remove at tail.

Definition at line 236 of file ListCls.cpp.

◆ RemoveAll()

void DLinkList::RemoveAll	(	PDListFunc	ItemAction,
		void *	UserData = `NULL`
	)

RemoveAll removes all entries from the list, calling ItemAction for each.
Use ItemAction to e.g. delete your entries, or any other cleanup you need.
If ItemAction returns false, the remaining operation is aborted.
If ItemAction is NULL, the entries are just removed, which might leak. See also PDListFunc

Definition at line 241 of file ListCls.cpp.

◆ Push()

PLIST_ENTRY DLinkList::Push ( PLIST_ENTRY Entry )

inline

Prepend().

Definition at line 258 of file ListFunc.h.

◆ Pull()

PLIST_ENTRY DLinkList::Pull ( void )

inline

Push() / Pull() = FIFO (Queue)

Definition at line 259 of file ListFunc.h.

◆ Pop()

PLIST_ENTRY DLinkList::Pop ( void )

inline

Push() / Pop() = LIFO (Stack)

Definition at line 260 of file ListFunc.h.

◆ operator []()

PLIST_ENTRY DLinkList::operator [] ( size_t Index )

Indexed access (can be slow).

Definition at line 277 of file ListCls.cpp.

◆ ForEach()

bool DLinkList::ForEach	(	PDListFunc	Action,
		void *	UserData = `NULL`
	)

ForEach invokes the Action callback on each list entry.
Note: ForEach is not intended for clearing a list, use RemoveAll() for that.

Warning: If you should ever need to remove an Entry in the callback for one of the iterative methods,
be sure to use RemoveEntry(), otherwise you will knock the Count member out of sync.
The obvious way to let the callback know it's list is to pass a pointer to it via the UserData param.
In this situation you may also want to temporarily (or permanently)
disable SafeRemove on the list, for performance reasons.

See PDListFunc for callback details.

Definition at line 317 of file ListCls.cpp.

◆ FirstThat()

PLIST_ENTRY DLinkList::FirstThat	(	PDListFunc	Match,
		void *	UserData = `NULL`
	)

Find the first matching entry, as determined by the Match callback.
See also ForEach().

Definition at line 287 of file ListCls.cpp.

◆ LastThat()

PLIST_ENTRY DLinkList::LastThat	(	PDListFunc	Match,
		void *	UserData = `NULL`
	)

Find the last matching entry, as determined by the Match callback.
See also ForEach().

Definition at line 302 of file ListCls.cpp.

◆ QuickSort()

void DLinkList::QuickSort	(	PDListComp	Compare,
		void *	UserData = `NULL`
	)

Quicksort the list by swapping links, not node data (so you can sort large Entries).
The Compare function should return a C tristate comparison value -x/0/+x.
UserData (optional) can be anything your comparator might need, or NULL.

See PDListComp for callback details.

Definition at line 335 of file ListCls.cpp.

◆ AppendList() [1/2]

UINT DLinkList::AppendList	(	IN PLIST_ENTRY	ListToAppend,
		OPTOUT PLIST_ENTRY *	ppFirst
	)

AppendList appends another list to the end of this.

Parameters

ListToAppend	The list head of the list to append. (This differs from the DDK AppendTailList function, which expects a headless list as it's source argument.)
ppFirst	If provided, recieves a pointer to the first added entry.

Returns: Returns the nr of items added.

Side Effects: ListToAppend is reset to empty, to prevent cross-links.

See also: DLinkList( PLIST_ENTRY ListHead, bool Safe ).

Definition at line 116 of file ListCls.cpp.

◆ AppendList() [2/2]

UINT DLinkList::AppendList	(	IN PDLinkList	ListToAppend,
		OPTOUT PLIST_ENTRY *	ppFirst
	)

See AppendList().

Definition at line 139 of file ListCls.cpp.

◆ operator+=() [2/2]

UINT DLinkList::operator+= ( PDLinkList ListToAppend )

inline

Definition at line 309 of file ListFunc.h.

◆ ExportToListHead()

UINT DLinkList::ExportToListHead ( PLIST_ENTRY ListHead OUT )

ExportToListHead transfers this to a plain NT listhead.
After ExportToListHead, the list's head pointers will refer to ListHead,
not this, so you must access the entries through ListHead.

Side Effects: Be aware that 'this' is reset to an empty list after the list is transferred to ListHead, to prevent cross-links.

Returns: Returns the nr of entries in the list.

Definition at line 431 of file ListCls.cpp.

◆ ImportFromListHead()

UINT DLinkList::ImportFromListHead	(	IN PLIST_ENTRY	ListHead,
		OPTOUT PLIST_ENTRY *	ppFirst
	)

ImportFromListHead adds all entries from ListHead to this list.

Side Effects: ListHead is reset to an empty list to prevent cross-links.

Returns: Returns the nr of entries added to this list, possibly 0.

◆ ExportToHeadlessList()

UINT DLinkList::ExportToHeadlessList ( PLIST_ENTRY * Circular )

[SPECIAL] ExportToHeadlessList transfers this to a headless (i.e. circular) list.

Side Effects: 'this' is reset to an empty list to prevent cross-links.

Returns: Returns the nr of entries in the list.

Definition at line 462 of file ListCls.cpp.

◆ ImportHeadlessList()

UINT DLinkList::ImportHeadlessList	(	IN PLIST_ENTRY	Circular,
		OPTOUT PLIST_ENTRY *	ppFirst
	)

[SPECIAL] ImportHeadlessList usurps a circular list into 'this'.
If 'this' is empty, Circular simply becomes this "headed" list,
otherwise Circular is appended at the end of this list.

Returns: Returns nr of items imported, or zero on failure.

Warning: Circular becomes a "headed" list, but because the passed in list has no head it can't be reset to empty,
so be careful to not create cross-links by subsequent use of your passed in list from other heads.

Example: list.ImportHeadlessList( headless, NULL );
list.QuickSort( sort_Alpha );
list.ExportToHeadlessList( &headless );

See also: AttachHeadlessList() (for hybrid head/headless lists); ExportToHeadlessList().

Definition at line 472 of file ListCls.cpp.

Member Data Documentation

◆ Count

UINT DLinkList::Count

Nr of items in the linked list.

Definition at line 186 of file ListFunc.h.

◆ SafeRemove

bool DLinkList::SafeRemove

Set true to check existence before removing an entry.
RemoveEntry is much faster without this, but the programmer must be sure to not try removing an item which isn't in the list.
Doing so is an error and will create a mess (cross-linked list) and cause undefined behavior.

When true, RemoveEntry() calls Exist() before commencing removal.
This protects against cross-link errors, but the list has to be traversed, possibly in it's entirety,
each time an item is removed, which can take a long time, especially when removing many entries from a big list.

RemoveAll() has been implemented to be efficient even with SafeRemove on,
by always removing the first item, which makes Exist as fast as possible.

Definition at line 187 of file ListFunc.h.

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

Detailed Description

Public Data

Public Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ DLinkList() [1/2]

◆ DLinkList() [2/2]

◆ ~DLinkList()

Member Function Documentation

◆ operator=()

◆ operator+=() [1/2]

◆ operator -=()

◆ IsEmpty()

◆ Exist()

◆ GetFirst()

◆ GetLast()

◆ GetNext()

◆ GetPrev()

◆ Append()

◆ Prepend()

◆ RemoveEntry()

◆ RemoveFirst()

◆ RemoveLast()

◆ RemoveAll()

◆ Push()

◆ Pull()

◆ Pop()

◆ operator []()

◆ ForEach()

◆ FirstThat()

◆ LastThat()

◆ QuickSort()

◆ AppendList() [1/2]

◆ AppendList() [2/2]

◆ operator+=() [2/2]

◆ ExportToListHead()

◆ ImportFromListHead()

◆ ExportToHeadlessList()

◆ ImportHeadlessList()

Member Data Documentation

◆ Count

◆ SafeRemove