ListCls.cpp

Go to the documentation of this file.

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Project: uLib - Utility library.
// Module: Enhanced double-linked list class.
// 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.
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// NOTA BENE: Contributors - ListCls.cpp and it's siblings can NOT use general
// Win32 stuff from uLib like Debug.h or StrFunc.h, because DLinkList must
// maintain _cross-platform build ability_.

#define ListFunc_Internal // Includes internal defines (currently unused)
#include <uLib/ListFunc.h>
#include <assert.h>

//-----------------------------------------------------------------------------

#if (defined(_DEBUG) && defined(_WIN32) && defined(_MSC_VER))
  #define DBG_LIST 1 /* enable this to add som sanity checking for bug hunts */

  // Caveat Emptor: This ought not even be here, since it's Win32 specific.
  // If you absolutely need to debug DLinkList on another platform,
  // be sure you have facsimile implementations of the used Win32 functions.
  // E.g #define IsBadReadPtr( addr,len ) false, or your real McCoy, et c.
  // You'll need these:
  // BOOL IsBadReadPtr( __in const PVOID lpData, __in UINT_PTR cbData );
  // BOOL IsBadWritePtr( __in PVOID lpData, __in UINT_PTR cbData );
  // void OutputDebugString( __in_opt LPCTSTR lpOutputString );
  // LN

  static bool IsBadRWPtr( PVOID Addr, UINT Len )
  {
    BOOL isBad = IsBadReadPtr( Addr, Len ); // Win32
    if (!isBad) isBad = IsBadWritePtr( Addr, Len ); // Win32
    return !!isBad;
  }
  #include <tchar.h>
  #include <stdio.h>
  #define DP_ERROR   3
  #define DP_WARNING 4
  #define DP_DEBUG   6
  #define _F(s) _T("[%s] ") _T(s), __FUNCTION__
  #ifndef dimof
    #define dimof(x)  (sizeof(x)/sizeof(x[0])) 
  #endif
  static void __cdecl DPrint( UINT Lv, PCTSTR Txt, ... )
  {
    va_list va;
    TCHAR szBuf[256];
    (void)&Lv; // unused
    va_start( va, Txt );
  #pragma warning( disable: 4996 )
    _vsntprintf( szBuf, dimof(szBuf), Txt, va );
  #pragma warning( default: 4996 )
    va_end( va );
    OutputDebugString( szBuf ); // Win32
  }
#else
  #define DBG_LIST 0
#endif

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

DLinkList::DLinkList( bool Safe )
{ 
    _InitializeListHead( this ); // Flink = Blink = this;
    SafeRemove = Safe;
    Count = 0;
}

DLinkList::DLinkList( PLIST_ENTRY ListHead, bool Safe ) // Pick up a plain DDK list.
{
    SafeRemove = Safe;
    _grabList( ListHead );
}

DLinkList::~DLinkList()
{
  #if DBG_LIST
    if (Count) DPrint( DP_WARNING, _F("Deleting list with %lu items remaining!\n"), Count );
  #endif
}

PLIST_ENTRY DLinkList::Append( PLIST_ENTRY Entry ) // InsertTailList
{
    if (Entry)
    {
        Entry->Flink = this;
        Entry->Blink = Blink;
        Blink->Flink = Entry;
        this-> Blink = Entry;
        Count++;
    }
    return Entry;
}

PLIST_ENTRY DLinkList::Prepend( PLIST_ENTRY Entry ) // InsertHeadList
{
    if (Entry)
    {
        Entry->Flink = Flink;
        Entry->Blink = this;
        Flink->Blink = Entry;
        this-> Flink = Entry;
        Count++;
    }
    return Entry;
}

UINT DLinkList::AppendList( IN PLIST_ENTRY ListToAppend, OPTOUT PLIST_ENTRY* ppFirst ) // preliminary
{
    // ListToAppend is the *head* of the list to append.

    if (_IsListEmpty( ListToAppend )) return 0;

    PLIST_ENTRY FirstEntry = ListToAppend->Flink;
    PLIST_ENTRY LastEntry  = ListToAppend->Blink;

    LastEntry->Flink = this;
    FirstEntry->Blink = Blink;
    Blink->Flink = FirstEntry;
    Blink = LastEntry;

    UINT nrAdded = 0; // Count the added list items.
    for( PLIST_ENTRY Entry = FirstEntry; Entry != this; nrAdded++, Entry = Entry->Flink );
    Count += nrAdded;

    _InitializeListHead( ListToAppend ); // The list doesn't belong there anymore.
    if (ppFirst) *ppFirst = FirstEntry;
    return nrAdded;
}

UINT DLinkList::AppendList( IN PDLinkList ListToAppend, OPTOUT PLIST_ENTRY* ppFirst ) // preliminary
{
    ListToAppend->Count = 0; // In this case it's safe to zero the source in advance.
    return AppendList( (PLIST_ENTRY)ListToAppend, ppFirst );
}

bool DLinkList::Exist( PLIST_ENTRY Entry ) // true if Entry found in list
{
    if (Entry)
    {
      #if DBG_LIST // Do some sanity check on behalf of the caller..
        // If these occur in uLib itself, there is a broken implementation.
        // If they occur in the caller's code, it's their own responsibility.
        if (IsBadRWPtr( Entry, sizeof(LIST_ENTRY) ))
        {
            DPrint( DP_ERROR, _F("R/W Error: %p\n"), Entry );
            goto __notFound;
        }
        #ifdef _MSC_VER
          // Detect double deletion, which would demand SEH handling
          // that is NOT available in GCC and other open source compilers.
          #ifdef _WIN64
            static const void* _TAG = (void*) 0xfeeefeeefeeefeee; // vs2oo8
          #else
            static const void* _TAG = (void*) 0xfeeefeee; // vs2oo8
          #endif
          bool deleted = (Entry == _TAG);
          if (!deleted) deleted = (Entry->Flink == _TAG) || (Entry->Blink == _TAG);
          if (deleted)
          {
              DPrint( DP_ERROR, _F("Deleted entry: %p\n"), Entry );
              goto __notFound;
          }
         #endif //_MSC_VER
      #endif //DBG_LIST

        PLIST_ENTRY Item = Flink;
        while( Item != this )
        {
            if (Item == Entry) return true; // Found
            Item = Item->Flink;
        }

      #if DBG_LIST
      __notFound: ((void)0); // MSVC don't accept a label directly before an end brace.
      #endif
    }
    return false; // NULL Entry, empty list, or Not found
}

// GetNext() and GetPrev() provides *fully circular* access to the list.

PLIST_ENTRY DLinkList::GetNext( PLIST_ENTRY Current )
{
    PLIST_ENTRY next = NULL;
    if (!IsEmpty())
    {
        next = Current->Flink;
        if (next == this) next = Flink; // Wrap around to beginning of list.
    }
    return next;
}

PLIST_ENTRY DLinkList::GetPrev( PLIST_ENTRY Current )
{
    PLIST_ENTRY next = NULL;
    if (!IsEmpty())
    {
        next = Current->Blink;
        if (next == this) next = Blink; // Wrap around to end of list.
    }
    return next;
}

PLIST_ENTRY DLinkList::RemoveEntry( PLIST_ENTRY Entry )
{
    if (Entry)
    {
        if (SafeRemove && !Exist( Entry )) Entry = NULL;
        else
        {
            PLIST_ENTRY _Flink = Entry->Flink;
            PLIST_ENTRY _Blink = Entry->Blink;
            _Blink->Flink = _Flink;
            _Flink->Blink = _Blink;
            Count--;
            UnlinkListEntry( Entry );
        }
    }
    return Entry;
}

PLIST_ENTRY DLinkList::RemoveFirst()
{
    return RemoveEntry( Flink );
}

PLIST_ENTRY DLinkList::RemoveLast()
{
    return RemoveEntry( Blink );
}

void DLinkList::RemoveAll( PDListFunc ItemAction, void* UserData )
{
    if (ItemAction) while( Flink != this )
    {
      #if 0
        if (!ItemAction( RemoveFirst(), UserData )) break; // Abort if user rtn false.
      #else // Retain the entry for which the callback returned false.
        PLIST_ENTRY item = RemoveFirst();
        #if 0
        if ( !item )
        {
            // This should not be possible, since RemoveFirst always calls
            // RemoveEntry with an item that *is* in the list, i.e. Exist()==true.
            // If it was NULL for some obscure reason, it would have been
            // rejected already when attempting to add it to the list.
            DPrint( DP_ERROR, _F("NULL Flink found. Check your code!\n"));
            break; 
        }
        #endif
        if ( !ItemAction( item, UserData ))
        {
            Prepend( item ); // Put it back where it came from.
            break; // User returned false, so abort enumeration.
        }
      #endif
    }
    else
    {
        // Caller didn't provide an action callback, so there's nothing to do
        // except clearing the list. Traversing through RemoveEntry is superfluous.

        _InitializeListHead( this ); // i.e. while( Flink != this ) RemoveFirst();
        Count = 0;
    }
}

PLIST_ENTRY DLinkList::operator [] ( size_t Index )
{
    if (IsEmpty()) return NULL;
    for( PLIST_ENTRY Entry = Flink; Entry != this; Entry = Entry->Flink, Index-- )
        if (Index == 0) return Entry;
    return NULL;
}

// The arrangement of the loop makes these iterators tolerant to Entry removal.

PLIST_ENTRY DLinkList::FirstThat( PDListFunc Match, void* UserData )
{
    if (!IsEmpty())
    {
        PLIST_ENTRY Entry = Flink;
        while( Entry != this )
        {
            PLIST_ENTRY Next = Entry->Flink; // Preload, in case Match removes Entry.
            if (Match( Entry, UserData )) return Entry;
            Entry = Next;
        }
    }
    return NULL;
}

PLIST_ENTRY DLinkList::LastThat( PDListFunc Match, void* UserData )
{
    if (!IsEmpty())
    {
        PLIST_ENTRY Entry = Blink;
        while( Entry != this )
        {
            PLIST_ENTRY Next = Entry->Blink;
            if (Match( Entry, UserData )) return Entry;
            Entry = Next;
        }
    }
    return NULL;
}

bool DLinkList::ForEach( PDListFunc Action, void* UserData )
{
    if (IsEmpty()) return false;
    PLIST_ENTRY Entry = Flink;
    while( Entry != this )
    {
        PLIST_ENTRY Next = Entry->Flink;
        if (!Action( Entry, UserData )) return false;
        Entry = Next;
    }
    return true;
}

// Quicksort by swapping links, not swapping node data.
// White magic based on code adapted from:
//   Unknown@GeeksForGeeks.org
//   KeremSahin@ideone.com

void DLinkList::QuickSort( PDListComp Compare, void* Context )
{
    // if ((Flink != this) && (Flink->Flink != this)) // If more than one entry..
    if (Count > 1) _qsortRecursion( &Flink, &Blink, Compare, Context );
}

void DLinkList::_qsortRecursion(
    PLIST_ENTRY *ppHead, PLIST_ENTRY *ppTail, PDListComp Compare, void* Context )
{
    // Quicksort recursion, protected

    PLIST_ENTRY pPivot = *ppTail;

    if ((*ppHead != this) && (*ppTail != this) && (*ppHead != *ppTail))
    {
        _qsortPartition( ppHead, ppTail, Compare, Context ); // Partition
        _qsortRecursion( ppHead, &(pPivot->Blink), Compare, Context ); // Sort left part
        _qsortRecursion( &(pPivot->Flink), ppTail, Compare, Context ); // Sort right part

        // Connect pivot to left & right parts

        if (pPivot->Blink != this)
            pPivot->Blink->Flink = pPivot;

        if (pPivot->Flink != this)
            pPivot->Flink->Blink = pPivot;
    }
}

void DLinkList::_qsortPartition(
    PLIST_ENTRY *ppHead, PLIST_ENTRY *ppTail, PDListComp Compare, void* Context )
{
    // Quicksort partitioning, protected

    PLIST_ENTRY pNewTail = NULL;
    PLIST_ENTRY pCurr = *ppHead;
    PLIST_ENTRY pPivot = *ppTail;

    while( pCurr != pPivot )
    {
        int cmp = Compare( pCurr, pPivot, Context );
        if (cmp > 0) // using normal C tristate comparison value -x/0/+x
        {
            if (pCurr->Blink != this)
                pCurr->Blink->Flink = pCurr->Flink;

            if (pCurr->Flink != this)
                pCurr->Flink->Blink = pCurr->Blink;

            pNewTail = pCurr;
            pCurr = pCurr->Flink;
            if (pCurr->Blink == this)
                *ppHead = pCurr;

            pNewTail->Blink = *ppTail;
            pNewTail->Flink = this;
            (*ppTail)->Flink = pNewTail;
            *ppTail = pNewTail;
        }
        else
            pCurr = pCurr->Flink;
    }

    if (pPivot->Blink != this)
        pPivot->Blink->Flink = this;

    if (pPivot->Flink != this)
        pPivot->Flink->Blink = this;
}

// Specials - Export/Import to/from listheads and headless lists

PDLinkList DLinkList::operator = ( PLIST_ENTRY SrcListHead )
{
    // Fail if this is not empty, or the other list is empty.
    if (!IsEmpty() || _IsListEmpty( SrcListHead )) return NULL;
    _grabList( SrcListHead );
    return this;
}

void DLinkList::_grabList( PLIST_ENTRY ListHead )
{
    if (_IsListEmpty( ListHead ))
        _InitializeListHead( this );
    else
    {
        Flink = ListHead->Flink; // Pick up the list.
        Blink = ListHead->Blink; // -"-
        Blink->Flink = Flink->Blink = this; // Change list head.
        // This side effect is deliberate, to prevent cross-link errors...
        _InitializeListHead( ListHead ); // The list doesn't belong to ListHead anymore.
    }
    PLIST_ENTRY Entry = Flink; // Count the list items.
    for( Count = 0; Entry != this; Count++, Entry = Entry->Flink );
}

UINT DLinkList::ExportToListHead( PLIST_ENTRY ListHead OUT ) // Complement to c'tor 2.
{
    UINT nrEntries = 0;
    if (ListHead)
    {
        ListHead->Flink = Flink;
        ListHead->Blink = Blink;
        ListHead->Blink->Flink = ListHead->Flink->Blink = ListHead;
        _InitializeListHead( this ); // The list doesn't belong to this anymore.
        nrEntries = Count;
        Count = 0;
    }
    return nrEntries;
}

UINT DLinkList::ImportFromListHead( PLIST_ENTRY ListHead, PLIST_ENTRY* ppFirst )
{
    UINT nrEntries = 0;
    if (ListHead)
    {
        if (Count) nrEntries = AppendList( ListHead, ppFirst );
        else
        {
            _grabList( ListHead );
            if (ppFirst) *ppFirst = Flink;
            nrEntries = Count;
        }
    }
    return nrEntries;
}

UINT DLinkList::ExportToHeadlessList( PLIST_ENTRY* Target OUT ) // Special
{
    LIST_ENTRY Head;
    PLIST_ENTRY FirstEntry = Flink;
    UINT nrEntries = ExportToListHead( &Head ); 
    _RemoveEntryList( &Head ); // Thus it becomes headless (aka. circular).
    *Target = FirstEntry;
    return nrEntries;
}

UINT DLinkList::ImportHeadlessList( PLIST_ENTRY Circular, PLIST_ENTRY* ppFirst ) // Special
{
    UINT nrAdded = 0;
    if (Circular)
    {
        PLIST_ENTRY FirstEntry = Circular;
        PLIST_ENTRY LastEntry  = Circular->Blink;
        PLIST_ENTRY Entry;

        if (!Count) // If empty, just usurp the circular list
        {
            Flink = FirstEntry;
            Blink = LastEntry;
            Blink->Flink = Flink->Blink = this;
        }
        else // Append the circular list to this
        {
            LastEntry->Flink = this;
            FirstEntry->Blink = Blink;
            Blink->Flink = FirstEntry;
            Blink = LastEntry;
        }
        // Count the added list items.
        for( Entry = FirstEntry; Entry != this; nrAdded++, Entry = Entry->Flink );
        Count += nrAdded;
        if (ppFirst) *ppFirst = FirstEntry;
    }
    return nrAdded;
}

//-----------------------------------------------------------------------------
// Single link list
//-----------------------------------------------------------------------------

#define SLIST_SPEEDY 0

bool __forceinline SLinkList::IsEmpty()
{
  #if SEMICIRCULAR_SLIST // Work in progress..
    return (Next == this);
  #else
    return (Next == NULL);
  #endif
}

// PONDER: Finish implementing the SEMICIRCULAR_SLIST option..?
// Pro's? Con's? "Just because I can" doesn't feel like an adequate reason.

PSINGLE_LIST_ENTRY SLinkList::PushEntry( PSINGLE_LIST_ENTRY Entry ) 
{
    if (Entry)
    {
      #if SLIST_SPEEDY
        Entry->Next = Next;
        Next = Entry;
      #else // Call "transmutable" C function
        _PushEntryList( this, Entry );
      #endif
        Count++;
    }
    return Entry;
}

PSINGLE_LIST_ENTRY SLinkList::PopEntry() 
{
  #if SLIST_SPEEDY
    PSINGLE_LIST_ENTRY Entry = Next;
    if (Entry != NULL)
    {
        Next = Entry->Next;
        _InitializeEntryList( Entry ); // "Unlink" the entry.
        Count--;
    }
  #else // Call "transmutable" C function
    PSINGLE_LIST_ENTRY Entry = _PopEntryList( this );
    if (Entry)
    {
        _InitializeEntryList( Entry ); // "Unlink" the entry.
        Count--;
    }
  #endif
    return Entry;
}

PSINGLE_LIST_ENTRY SLinkList::Append( PSINGLE_LIST_ENTRY Entry ) // Return Entry
{
    if (Entry)
    {
        if (Next == NULL) // If list is empty
            PushEntry( Entry );
        else
        {
            PSINGLE_LIST_ENTRY item = Next;
            while (item->Next != NULL) // Find the last entry
            {
                item = item->Next;
            }
            Entry->Next = item->Next; //= NULL;
            item->Next = Entry;
            Count++;
        }
    }
    return Entry;
}

PSINGLE_LIST_ENTRY SLinkList::Remove( PSINGLE_LIST_ENTRY Entry )
{
    if (!Entry || IsEmpty()) return NULL;

    PSINGLE_LIST_ENTRY Item = Next;
    PSINGLE_LIST_ENTRY Prev = this;
    while( Item != Entry )
    {
        Prev = Item;
        Item = Item->Next;
        if (!Item) return NULL;
    }
    Count--;
    Prev->Next = Item->Next;
    _InitializeEntryList( Item ); // "Unlink" the entry.
    return Item;
}

PSINGLE_LIST_ENTRY SLinkList::operator [] ( size_t Index ) // Indexed access (can be slow)
{
    if (IsEmpty()) return NULL;
    for( PSINGLE_LIST_ENTRY Entry = Next; Entry != NULL; Entry = Entry->Next, Index-- )
        if (Index == 0) return Entry;
    return NULL;
}

void SLinkList::RemoveAll( PSListFunc ItemAction, void* UserData )
{
    if (!ItemAction) 
        while( Next != NULL ) PopEntry();
    else while( Next != NULL )
        if (!ItemAction( PopEntry(), UserData )) break; // Abort if user rtn false.
}

PSINGLE_LIST_ENTRY SLinkList::FirstThat( PSListFunc Match, void* UserData )
{
    if (!IsEmpty())
    {
        PSINGLE_LIST_ENTRY Entry = Next;
        while( Entry != NULL )
        {
            PSINGLE_LIST_ENTRY NextEntry = Entry->Next;
            if (Match( Entry, UserData )) return Entry;
            Entry = NextEntry;
        }
    }
    return NULL;
}

bool SLinkList::ForEach( PSListFunc Action, void* UserData )
{
    if (IsEmpty()) return false;

    PSINGLE_LIST_ENTRY Entry = Next;
    while( Entry != NULL )
    {
        PSINGLE_LIST_ENTRY NextEntry = Entry->Next;
        if (!Action( Entry, UserData )) return false;
        Entry = NextEntry;
    }
    return true;
}

//-----------------------------------------------------------------------------
// EOF