ListFunc.h

Go to the documentation of this file.

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Project: uLib - User mode utility library.
// Module: Enhanced double-linked and single-linked list classes.
// Author: Copyright (c) Love Nystrom
// License: NNOSL (BSD descendant, see NNOSL.txt in the base directory).
// Credits:
//   Someone on Microsoft's kernel team for the original ntddk macros.
//   Unknown@GeeksForGeeks.org  Original ideas for QuickSort.
//   KeremSahin@ideone.com      Original ideas for QuickSort.
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// DLinkList -- Double linked list manipulation class.
// Initially based on the list macros in ntddk.h, and thoroughly enhanced.
// 2018: ListForEach and GetListEntryCount APIs have been added, to facilitate
// solid enumeration for standard listhead lists, and easily count their entries.

#ifndef _ListFunc_h_incl_
#define _ListFunc_h_incl_

//==---------------------------------------------------------------------------
//==---------------------------------------------------------------------------

#ifndef _NTDEF_ // NtDef.h declares LIST_ENTRY in kernel mode.
#if defined(WIN32) || defined(_WIN32) || defined(__WIN32__) // 3 id's I've seen
#include <Windows.h>
#else // Non-Windows compilation
// DList
typedef struct _LIST_ENTRY
{
    struct _LIST_ENTRY *Flink;
    struct _LIST_ENTRY *Blink;
}
*PLIST_ENTRY, LIST_ENTRY; // NB: Backward order due to doxygen.
// SList
typedef struct _SINGLE_LIST_ENTRY
{
    struct _SINGLE_LIST_ENTRY *Next;
}
*PSINGLE_LIST_ENTRY, SINGLE_LIST_ENTRY;
#endif
#endif//ndef _NTDEF_

#ifdef __cplusplus
extern "C" {
#elif !defined( __bool_defined )
//typedef enum { false,true } bool; // int-size!
typedef unsigned char bool; // single byte, compliant.
#define true    (1==1)  // note: constant folding applies.
#define false   (1==0)  // -"-
#define __bool_defined
#endif

#ifndef INOUT // Supplements to classic annotations
  #define INOUT
  #define OPTIN
  #define OPTOUT
  #define OPTIO
#endif
#ifdef ListFunc_Internal
// Currently unused.
#endif

//-----------------------------------------------------------------------------
// C API's - Function equivalents of the DDK macros.
// Note: Leading underscore disambiguates from the macro and inline versions.
//-----------------------------------------------------------------------------


#define InitializeListEntry(E)  (E)->Flink = (E)->Blink = (E)
#define _InitializeListEntry(E) _InitializeListHead( (PLIST_ENTRY)(E) )


#define UnlinkListEntry(E)  InitializeListEntry( E )

// Double-linked list

void  _InitializeListHead( PLIST_ENTRY ListHead );   
bool  _IsListEmpty( PLIST_ENTRY ListHead );          
void  _InsertTailList( PLIST_ENTRY ListHead, PLIST_ENTRY Entry ); 
void  _InsertHeadList( PLIST_ENTRY ListHead, PLIST_ENTRY Entry ); 
void  _RemoveEntryList( PLIST_ENTRY Entry );         
PLIST_ENTRY _RemoveHeadList( PLIST_ENTRY ListHead ); 
PLIST_ENTRY _RemoveTailList( PLIST_ENTRY ListHead ); 

// Supplementary APIs for standard lists.

UINT  GetListEntryCount( PLIST_ENTRY ListHead ); 


bool  ListForEach( 
        PLIST_ENTRY ListHead, 
        bool (__stdcall *Action)( PLIST_ENTRY Entry, void* UserData ),
        void* UserData 
        );


void AttachHeadlessList( OUT PLIST_ENTRY Head, IN PLIST_ENTRY Circular );

// Single-linked list

void  _InitializeEntryList( PSINGLE_LIST_ENTRY EntryOrHead ); 
void  _PushEntryList( PSINGLE_LIST_ENTRY ListHead, PSINGLE_LIST_ENTRY Entry ); 
PSINGLE_LIST_ENTRY _PopEntryList( PSINGLE_LIST_ENTRY ListHead ); 

#ifdef __cplusplus
} // end extern "C"

//-----------------------------------------------------------------------------
// C++ double-linked list class
//-----------------------------------------------------------------------------

typedef class DLinkList* PDLinkList; 


typedef bool (__stdcall *PDListFunc)( PLIST_ENTRY Entry, void* UserData );


typedef int  (__stdcall *PDListComp)( PLIST_ENTRY X, PLIST_ENTRY Y, void* UserData );

//+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// NOTA BENE: Contributors, do NOT add virtual members to DLinkList !!
// The introduction of a vtable would offset (&Flink) by sizeof(void*),
// which would break the equality (this) == (&Flink).

class DLinkList : protected LIST_ENTRY {
public:
    UINT Count; 
    bool SafeRemove; 

    DLinkList( bool Safe = true ); 


    DLinkList( PLIST_ENTRY ListHead, bool Safe );


    ~DLinkList(); // N.B: Can't be virtual, since that would make (this) != (&Flink) !


    PDLinkList operator = ( PLIST_ENTRY ListHead );

    PLIST_ENTRY operator += ( PLIST_ENTRY Entry ) { return Append( Entry ); } 
    PLIST_ENTRY operator -= ( PLIST_ENTRY Entry ) { return RemoveEntry( Entry ); } 

    bool IsEmpty() { return Flink == this; }
    bool Exist( PLIST_ENTRY Entry );            

    PLIST_ENTRY GetFirst() { return Flink; }    // At head
    PLIST_ENTRY GetLast()  { return Blink; }    // At tail


    PLIST_ENTRY GetNext( PLIST_ENTRY Current );
    PLIST_ENTRY GetPrev( PLIST_ENTRY Current ); 

    // Add entries

    PLIST_ENTRY Append( PLIST_ENTRY Entry );    
    PLIST_ENTRY Prepend( PLIST_ENTRY Entry );   

    // Remove entries

    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 ) { return Prepend( Entry ); } 
    PLIST_ENTRY Pull() { return RemoveLast(); }  
    PLIST_ENTRY Pop()  { return RemoveFirst(); } 

    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 );

public: // IMPORT / EXPORT


    UINT AppendList( IN PLIST_ENTRY ListToAppend, OPTOUT PLIST_ENTRY* ppFirst );
    UINT AppendList( IN PDLinkList ListToAppend, OPTOUT PLIST_ENTRY* ppFirst ); 
    UINT operator += ( PDLinkList ListToAppend ) { return AppendList( ListToAppend, NULL ); }


    UINT ExportToListHead( PLIST_ENTRY ListHead ); 


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


    UINT ExportToHeadlessList( PLIST_ENTRY* Circular ); // Preliminary


    UINT ImportHeadlessList( IN PLIST_ENTRY Circular, OPTOUT PLIST_ENTRY* ppFirst ); // Preliminary

protected:
    void _grabList( PLIST_ENTRY ListHead );
    void _qsortPartition(
        PLIST_ENTRY *ppHead, PLIST_ENTRY *ppTail, PDListComp Compare, void* UserData
        );
    void _qsortRecursion(
        PLIST_ENTRY *ppHead, PLIST_ENTRY *ppTail, PDListComp Compare, void* UserData
        );
};

//-----------------------------------------------------------------------------
// SLinkList -- Single linked list.
//-----------------------------------------------------------------------------

typedef class SLinkList* PSLinkList; 
typedef bool (__stdcall *PSListFunc)( PSINGLE_LIST_ENTRY Entry, void* UserData );


class SLinkList : protected SINGLE_LIST_ENTRY {
public:
    UINT Count; 

    SLinkList() : Count(0) { _InitializeEntryList( this ); }

    bool __forceinline IsEmpty(); 
    PSINGLE_LIST_ENTRY GetFirst() { return Next; } 


    PSINGLE_LIST_ENTRY  PushEntry( PSINGLE_LIST_ENTRY Entry ); 
    PSINGLE_LIST_ENTRY  PopEntry(); 


    PSINGLE_LIST_ENTRY  Append( PSINGLE_LIST_ENTRY Entry ); // Return Entry


    PSINGLE_LIST_ENTRY  Remove( PSINGLE_LIST_ENTRY Entry );

    // Some nifty operators are nice to have

    PSINGLE_LIST_ENTRY operator += ( PSINGLE_LIST_ENTRY Entry ) { return PushEntry( Entry ); } 
    PSINGLE_LIST_ENTRY operator -= ( PSINGLE_LIST_ENTRY Entry ) { return Remove( Entry ); } 

    PSINGLE_LIST_ENTRY operator [] ( size_t Index ); 


    void    RemoveAll( PSListFunc ItemAction, void* UserData = NULL );

    
    PSINGLE_LIST_ENTRY  FirstThat( PSListFunc Match, void* UserData = NULL );
    bool    ForEach( PSListFunc Action, void* UserData = NULL ); 
};

#endif //__cplusplus
//-----------------------------------------------------------------------------
#endif //ndef _ListFunc_h_incl_
// EOF