ListFunc.c

Go to the documentation of this file.

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Project: uLib - User mode library.
// Module: Linked list C function equivalents of DDK macros. 
// Author: Copyright (c) Love Nystrom
// License: NNOSL (BSD descendant, see NNOSL.txt in the base directory).
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// Based on the list macros in ntddk.h; Slightly optimized.
// Id's have a disambiguating leading underscore.

#include <uLib/ListFunc.h>

//-----------------------------------------------------------------------------
// C API's
//-----------------------------------------------------------------------------

void _InitializeListHead( PLIST_ENTRY ListHead )
{
    ListHead->Flink = ListHead->Blink = ListHead;
}

bool _IsListEmpty( PLIST_ENTRY ListHead )
{
    return (!ListHead || (ListHead->Flink == ListHead));
}

PLIST_ENTRY _RemoveTailList( PLIST_ENTRY ListHead )
{
    register PLIST_ENTRY Entry = ListHead->Blink;
    register PLIST_ENTRY Blink = Entry->Blink;
    Blink->Flink = ListHead;
    ListHead->Blink = Blink;
    UnlinkListEntry( Entry );
    return Entry;
}

PLIST_ENTRY _RemoveHeadList( PLIST_ENTRY ListHead )
{
    register PLIST_ENTRY Entry = ListHead->Flink;
    register PLIST_ENTRY Flink = Entry->Flink;
    Flink->Blink = ListHead;
    ListHead->Flink = Flink;
    UnlinkListEntry( Entry );
    return Entry;
}

void _RemoveEntryList( PLIST_ENTRY Entry )
{
  // Overall performance is approximately equal for the two versions
  #if 1 // 6 refs and 2 assigns
    Entry->Blink->Flink = Entry->Flink;
    Entry->Flink->Blink = Entry->Blink;
  #else // 4 refs and 4 assigns
    register PLIST_ENTRY Flink = Entry->Flink;
    register PLIST_ENTRY Blink = Entry->Blink;
    Blink->Flink = Flink;
    Flink->Blink = Blink;
  #endif
    UnlinkListEntry( Entry );
}

void _InsertTailList( PLIST_ENTRY ListHead, PLIST_ENTRY Entry )
{
    register PLIST_ENTRY Blink = ListHead->Blink;
    Entry->Flink = ListHead;
    Entry->Blink = Blink;
    Blink->Flink = Entry;
    ListHead->Blink = Entry;
}

void _InsertHeadList( PLIST_ENTRY ListHead, PLIST_ENTRY Entry )
{
    register PLIST_ENTRY Flink = ListHead->Flink;
    Entry->Flink = Flink;
    Entry->Blink = ListHead;
    Flink->Blink = Entry;
    ListHead->Flink = Entry;
}

// Addendum -------------------------------------------------------------------

UINT GetListEntryCount( PLIST_ENTRY ListHead )
{
    UINT Count = 0; PLIST_ENTRY Entry;
    if (ListHead) for( 
        Entry = ListHead->Flink; Entry != ListHead; 
        Count++, Entry = Entry->Flink
        );
    return Count;
}

bool ListForEach( PLIST_ENTRY ListHead, 
    bool (__stdcall *Action)( PLIST_ENTRY Entry, void* UserData ), 
    void* UserData )
{
    PLIST_ENTRY Entry;
    if (_IsListEmpty( ListHead )) return false;
    Entry = ListHead->Flink;
    while( Entry != ListHead )
    {
        PLIST_ENTRY Next = Entry->Flink;
        if (!Action( Entry, UserData )) return false;
        Entry = Next;
    }
    return true;
}

void AttachHeadlessList( OUT PLIST_ENTRY Head, IN PLIST_ENTRY Circular )
{
    Head->Flink = Circular;
    Head->Blink = Circular->Blink;
}

#if 0 // Pending
void _AppendTailList( PLIST_ENTRY ListHead, PLIST_ENTRY HeadlessListToAppend )
{
    PLIST_ENTRY ListEnd = ListHead->Blink;
 
    ListHead->Blink->Flink = HeadlessListToAppend;
    ListHead->Blink = HeadlessListToAppend->Blink;
    HeadlessListToAppend->Blink->Flink = ListHead;
    HeadlessListToAppend->Blink = ListEnd;
}

PLIST_ENTRY _AppendList( PLIST_ENTRY Head, PLIST_ENTRY HeadedListToAppend )
{
    PLIST_ENTRY FirstEntry;
    if (IsListEmpty( HeadedListToAppend )) return NULL;

    FirstEntry = HeadedListToAppend->Flink;
    _RemoveEntryList( HeadedListToAppend ); // Remove the listhead
    _InitializeListHead( HeadedListToAppend ); // Reset to empty
    _AppendTailList( Head, FirstEntry );
    return FirstEntry;
}
#endif

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

// Hmm.. Where and when did [MSDN] InitializeEntryList disappear ?
// Did I just collect it from a parallell universe ?

void _InitializeEntryList( PSINGLE_LIST_ENTRY EntryOrHead ) {
    #if SEMICIRCULAR_SLIST
      EntryOrHead->Next = EntryOrHead;
    #else
      EntryOrHead->Next = NULL;
    #endif
    }

void _PushEntryList( PSINGLE_LIST_ENTRY ListHead, PSINGLE_LIST_ENTRY Entry ) {
    Entry->Next = ListHead->Next;
    ListHead->Next = Entry;
    }

PSINGLE_LIST_ENTRY _PopEntryList( PSINGLE_LIST_ENTRY ListHead ) {
    PSINGLE_LIST_ENTRY Entry = ListHead->Next;
    #if SEMICIRCULAR_SLIST
      if (Entry == ListHead) Entry = NULL; else ListHead->Next = Entry->Next;
    #else    
      //ListHead->Next = (Entry == NULL) ? ListHead : Entry->Next; // Hybrid
      if (Entry != NULL) ListHead->Next = Entry->Next; // DDK compliant
    #endif
    return Entry;
    }

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