LLIST.H

/*++ 
 
Module Name: 
 
    llist.h 
 
Abstract: 
 
    This  module  is  a  standalone  collection  of  linked-list definition and 
    manipulation  macros  originally  defined  within  the  Windows NT 
    development. 
 
--*/ 
 
#ifndef _LLIST_ 
#define _LLIST_ 
#include <winsock2.h> 
 
 
 
#if !defined( _WINNT_ ) 
// 
//  From NTDEF.H. 
// 
 
//  Doubly  linked  list  structure.   Can be used as either a list head, or as 
//  link storage within a linked-list item. 
 
typedef struct _LIST_ENTRY { 
   struct _LIST_ENTRY *Flink; 
   struct _LIST_ENTRY *Blink; 
} LIST_ENTRY, *PLIST_ENTRY, *RESTRICTED_POINTER PRLIST_ENTRY; 
 
 
 
  
// LONG 
// FIELD_OFFSET( 
//     IN <typename>   type, 
//     IN <fieldname>  field 
//     ); 
#define FIELD_OFFSET(type, field)    ((LONG)&(((type *)0)->field)) 
/*++ 
 
Routine Description: 
 
    Calculates  the  byte offset of a field in a structure of type "type".  The 
    offset is from the beginning of the containing structure. 
 
    Note  that  since  this macro uses compile-time type knowledge, there is no 
    equivalent C procedure for this macro. 
 
Arguments: 
 
    type  - Supplies the type name of the containing structure. 
 
    field - Supplies  the  field  name  of  the  field  whose  offset  is to be 
            computed. 
 
Return Value: 
 
    Returns  the byte offset of the named field within a structure of the named 
    type. 
--*/ 
 
 
 
  
// <typename> FAR * 
// CONTAINING_RECORD( 
//     IN PVOID       address, 
//     IN <typename>  type, 
//     IN <fieldname> field 
//     ); 
#define CONTAINING_RECORD(address, type, field) ((type FAR *)( \ 
                                          (PCHAR)(address) - \ 
                                          (PCHAR)(&((type *)0)->field))) 
/*++ 
 
Routine Description: 
 
    Retrieves  a  typed  pointer to a linked list item given the address of the 
    link  storage  structure  embedded in the linked list item, the type of the 
    linked  list  item,  and  the  field  name  of  the  embedded  link storage 
    structure. 
 
    Note  that  since  this macro uses compile-time type knowledge, there is no 
    equivalent C procedure for this macro. 
 
Arguments: 
 
    address - Supplies  the  address of a LIST_ENTRY structure embedded in an a 
              linked list item. 
 
    type    - Supplies  the  type  name  of  the  containing  linked  list item 
              structure. 
 
    field   - Supplies  the  field  name  if  the LIST_ENTRY structure embedded 
              within the linked list item structure. 
 
Return Value: 
 
    Returns a pointer to the linked list item. 
--*/ 
 
 
#endif  // !defined( _WINNT_ ) 
 
 
// 
//  From NTRTL.H. 
// 
 
//  Doubly-linked list manipulation routines.  Implemented as macros 
//  but logically these are procedures. 
 
 
 
  
// VOID 
// InitializeListHead( 
//     IN PLIST_ENTRY ListHead 
//     ); 
#define InitializeListHead(ListHead) (\ 
    (ListHead)->Flink = (ListHead)->Blink = (ListHead)) 
/*++ 
 
Routine Description: 
 
    Initializes  a  PLIST_ENTRY  structure to be the head of an initially empty 
    linked list. 
 
Arguments: 
 
    ListHead - Supplies a reference to the structure to be initialized. 
 
Return Value: 
 
    None 
--*/ 
 
 
 
  
// BOOLEAN 
// IsListEmpty( 
//     IN PLIST_ENTRY ListHead 
//     ); 
#define IsListEmpty(ListHead) \ 
    ((ListHead)->Flink == (ListHead)) 
/*++ 
 
Routine Description: 
 
    Determines whether or not a list is empty. 
 
Arguments: 
 
    ListHead - Supplies  a  reference  to  the  head  of  the linked list to be 
               examined. 
 
Return Value: 
 
    TRUE  - The linked list is empty. 
 
    FALSE - The linked list contains at least one item. 
--*/ 
 
 
 
  
// PLIST_ENTRY 
// RemoveHeadList( 
//     IN PLIST_ENTRY ListHead 
//     ); 
#define RemoveHeadList(ListHead) \ 
    (ListHead)->Flink;\ 
    {RemoveEntryList((ListHead)->Flink)} 
/*++ 
 
Routine Description: 
 
    Removes  the  "head" (first) item from a linked list, returning the pointer 
    to  the  removed  entry's embedded linkage structure.  Attempting to remove 
    the  head  item  from  a  (properly  initialized)  linked  list is a no-op, 
    returning the pointer to the head of the linked list. 
 
    The  caller  may  use  the  CONTAINING_RECORD macro to amplify the returned 
    linkage structure pointer to the containing linked list item structure. 
 
Arguments: 
 
    ListHead - Supplies  a  reference  to  the  head  of  the linked list to be 
               operated upon. 
 
Return Value: 
 
    Returns  a pointer to the newly removed linked list item's embedded linkage 
    structure, or the linked list head in the case of an empty list. 
--*/ 
 
 
 
  
// PLIST_ENTRY 
// RemoveTailList( 
//     IN PLIST_ENTRY ListHead 
//     ); 
#define RemoveTailList(ListHead) \ 
    (ListHead)->Blink;\ 
    {RemoveEntryList((ListHead)->Blink)} 
/*++ 
 
Routine Description: 
 
    Removes the "tail" (last) item from a linked list, returning the pointer to 
    the  removed  entry's embedded linkage structure.  Attempting to remove the 
    tail  item  from a (properly initialized) linked list is a no-op, returning 
    the pointer to the head of the linked list. 
 
    The  caller  may  use  the  CONTAINING_RECORD macro to amplify the returned 
    linkage structure pointer to the containing linked list item structure. 
 
Arguments: 
 
    ListHead - Supplies  a  reference  to  the  head  of  the linked list to be 
               operated upon. 
 
Return Value: 
 
    Returns  a pointer to the newly removed linked list item's embedded linkage 
    structure, or the linked list head in the case of an empty list. 
--*/ 
 
 
 
  
// VOID 
// RemoveEntryList( 
//     IN PLIST_ENTRY Entry 
//     ); 
#define RemoveEntryList(Entry) {\ 
    PLIST_ENTRY _EX_Blink;\ 
    PLIST_ENTRY _EX_Flink;\ 
    _EX_Flink = (Entry)->Flink;\ 
    _EX_Blink = (Entry)->Blink;\ 
    _EX_Blink->Flink = _EX_Flink;\ 
    _EX_Flink->Blink = _EX_Blink;\ 
    } 
/*++ 
 
Routine Description: 
 
    Removes  an  item  from a linked list.  Attempting to remove the head of an 
    empty list is a no-op. 
 
Arguments: 
 
    Entry - Supplies  a reference to the linkage structure embedded in a linked 
            list item structure. 
 
Return Value: 
 
    None 
--*/ 
 
 
 
  
// VOID 
// InsertTailList( 
//     IN PLIST_ENTRY ListHead, 
//     IN PLIST_ENTRY Entry 
//     ); 
#define InsertTailList(ListHead,Entry) {\ 
    PLIST_ENTRY _EX_Blink;\ 
    PLIST_ENTRY _EX_ListHead;\ 
    _EX_ListHead = (ListHead);\ 
    _EX_Blink = _EX_ListHead->Blink;\ 
    (Entry)->Flink = _EX_ListHead;\ 
    (Entry)->Blink = _EX_Blink;\ 
    _EX_Blink->Flink = (Entry);\ 
    _EX_ListHead->Blink = (Entry);\ 
    } 
/*++ 
 
Routine Description: 
 
    Inserts a new item as the "tail" (last) item of a linked list. 
 
Arguments: 
 
    ListHead - Supplies  a  reference  to  the  head  of  the linked list to be 
               operated upon. 
 
    Entry    - Supplies  a  reference  to the linkage structure embedded in the 
               linked list item to be added to the linked list. 
 
Return Value: 
 
    None 
--*/ 
 
 
 
  
// VOID 
// InsertHeadList( 
//     IN PLIST_ENTRY ListHead, 
//     IN PLIST_ENTRY Entry 
//     ); 
#define InsertHeadList(ListHead,Entry) {\ 
    PLIST_ENTRY _EX_Flink;\ 
    PLIST_ENTRY _EX_ListHead;\ 
    _EX_ListHead = (ListHead);\ 
    _EX_Flink = _EX_ListHead->Flink;\ 
    (Entry)->Flink = _EX_Flink;\ 
    (Entry)->Blink = _EX_ListHead;\ 
    _EX_Flink->Blink = (Entry);\ 
    _EX_ListHead->Flink = (Entry);\ 
    } 
/*++ 
 
Routine Description: 
 
    Inserts a new item as the "head" (first) item of a linked list. 
 
Arguments: 
 
    ListHead - Supplies  a  reference  to  the  head  of  the linked list to be 
               operated upon. 
 
    Entry    - Supplies  a  reference  to the linkage structure embedded in the 
               linked list item to be added to the linked list. 
 
Return Value: 
 
    None 
--*/ 
 
 
 
// 
// 
//  PSINGLE_LIST_ENTRY 
//  PopEntryList( 
//      PSINGLE_LIST_ENTRY ListHead 
//      ); 
// 
 
#define PopEntryList(ListHead) \ 
    (ListHead)->Next;\ 
    {\ 
        PSINGLE_LIST_ENTRY FirstEntry;\ 
        FirstEntry = (ListHead)->Next;\ 
        if (FirstEntry != NULL) {     \ 
            (ListHead)->Next = FirstEntry->Next;\ 
        }                             \ 
    } 
 
 
// 
//  VOID 
//  PushEntryList( 
//      PSINGLE_LIST_ENTRY ListHead, 
//      PSINGLE_LIST_ENTRY Entry 
//      ); 
// 
 
#define PushEntryList(ListHead,Entry) \ 
    (Entry)->Next = (ListHead)->Next; \ 
    (ListHead)->Next = (Entry) 
 
 
// Samples: 
// 
// // 
// //  Define a list head. 
// // 
// 
// LIST_ENTRY FooList; 
// 
// // 
// //  Define a structure that will be on the list. 
// // 
// //  NOTE:  For debugging purposes, it usually makes life simpler to make the 
// //  LIST_ENTRY  the  first  field  of  the  structure,  but  this  is  not a 
// //  requirement. 
// // 
// 
// typedef struct _FOO 
// { 
//     LIST_ENTRY FooListEntry; 
//     . 
//     . 
//     . 
// 
// } FOO, * PFOO; 
// 
// // 
// //  Initialize an empty list. 
// // 
// 
// InitializeListHead( &FooList ); 
// 
// // 
// //  Create an object, append it to the end of the list. 
// // 
// 
// PFOO foo; 
// 
// foo = ALLOC( sizeof(FOO) ); 
// {check for errors, initialize FOO structure} 
// 
// InsertTailList( &FooList, &foo->FooListEntry ); 
// 
// // 
// //  Scan list and delete selected items. 
// // 
// 
// PFOO foo; 
// PLIST_ENTRY listEntry; 
// 
// listEntry = FooList.Flink; 
// 
// while( listEntry != &FooList ) 
// { 
//     foo = CONTAINING_RECORD( listEntry, 
//                              FOO, 
//                              FooListEntry ); 
//     listEntry = listEntry->Flink; 
// 
//     if( SomeFunction( foo ) ) 
//     { 
//         RemoveEntryList( &foo->FooListEntry ); 
//      FREE( foo ); 
//     } 
// } 
// 
// // 
// //  Purge all items from a list. 
// // 
// 
// PFOO foo; 
// PLIST_ENTRY listEntry; 
// 
// while( !IsListEmpty( &FooList ) ) 
// { 
//     listEntry = RemoveHeadList( &FooList ); 
//     foo = CONTAINING_RECORD( listEntry, 
//                              FOO, 
//                              FooListEntry ); 
// 
//     FREE( foo ); 
// } 
 
 
#endif  // _LLIST_