text: /*++ BUILD Version: 0005    // Increment this if a change has global effects
  
  Copyright (c) 1989-1999  Microsoft Corporation
  
  Module Name:
  
      llsrtl.h
  
  Abstract:
  
      Include file for NT runtime routines that are callable by both
      kernel mode code in the executive and user mode code in various
      NT subsystems.
  
  Author:
  
      Steve Wood (stevewo) 31-Mar-1989
  
  Environment:
  
      These routines are statically linked in the caller's executable and
      are callable in either kernel mode or user mode.
  
  Revision History:
  
  --*/
  
  #ifndef _LLSRTL_
  #define _LLSRTL_
  
  #if defined (_MSC_VER)
  #if ( _MSC_VER >= 800 )
  #pragma warning(disable:4514)
  #if _MSC_VER >= 1200
  #pragma warning(push)
  #endif
  #pragma warning(disable:4001)
  #pragma warning(disable:4201)
  #pragma warning(disable:4214)
  #endif
  #if (_MSC_VER > 1020)
  #pragma once
  #endif
  #endif
  
  // begin_ntddk begin_wdm begin_winnt begin_ntifs begin_nthal
  //
  // for move macros
  //
  #ifdef _MAC
  #ifndef _INC_STRING
  #include <string.h>
  #endif /* _INC_STRING */
  #else
  #include <string.h>
  #endif // _MAC
  
  // end_ntddk end_wdm end_winnt end_ntifs end_nthal
  
  #ifdef __cplusplus
  extern "C" {
  #endif
  
  // begin_ntddk begin_wdm begin_nthal begin_ntifs begin_ntndis
  //
  // If debugging support enabled, define an ASSERT macro that works.  Otherwise
  // define the ASSERT macro to expand to an empty expression.
  //
  
  #if DBG
  
  NTSYSAPI
  VOID
  NTAPI
  RtlAssert(
      PVOID FailedAssertion,
      PVOID FileName,
      ULONG LineNumber,
      PCHAR Message
      );
  
  #ifndef ASSERT
  #define ASSERT( exp ) \
      ((!(exp)) ? \
          RtlAssert( #exp, __FILE__, __LINE__, NULL ) : \
          ((void)0))
  #endif
  
  #ifndef ASSERTMSG
  #define ASSERTMSG( msg, exp ) \
      ((!(exp)) ? \
          RtlAssert( #exp, __FILE__, __LINE__, msg ) : \
          ((void)0))
  #endif
  
  #else
  #ifndef ASSERT
  #define ASSERT( exp ) ((void)0)
  #endif
  
  #ifndef ASSERTMSG
  #define ASSERTMSG( msg, exp ) ((void)0)
  #endif
  #endif // DBG
  
  // end_ntddk end_wdm end_nthal end_ntifs end_ntndis
  
  // begin_ntddk begin_wdm begin_nthal begin_ntifs begin_ntndis
  //
  //  Doubly-linked list manipulation routines.  Implemented as macros
  //  but logically these are procedures.
  //
  
  //
  //  VOID
  //  InitializeListHead(
  //      PLIST_ENTRY ListHead
  //      );
  //
  
  #define InitializeListHead(ListHead) (\
      (ListHead)->Flink = (ListHead)->Blink = (ListHead))
  
  //
  //  BOOLEAN
  //  IsListEmpty(
  //      PLIST_ENTRY ListHead
  //      );
  //
  
  #define IsListEmpty(ListHead) \
      ((ListHead)->Flink == (ListHead))
  
  //
  //  PLIST_ENTRY
  //  RemoveHeadList(
  //      PLIST_ENTRY ListHead
  //      );
  //
  
  #define RemoveHeadList(ListHead) \
      (ListHead)->Flink;\
      {RemoveEntryList((ListHead)->Flink)}
  
  //
  //  PLIST_ENTRY
  //  RemoveTailList(
  //      PLIST_ENTRY ListHead
  //      );
  //
  
  #define RemoveTailList(ListHead) \
      (ListHead)->Blink;\
      {RemoveEntryList((ListHead)->Blink)}
  
  //
  //  VOID
  //  RemoveEntryList(
  //      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;\
      }
  
  //
  //  VOID
  //  InsertTailList(
  //      PLIST_ENTRY ListHead,
  //      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);\
      }
  
  //
  //  VOID
  //  InsertHeadList(
  //      PLIST_ENTRY ListHead,
  //      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);\
      }
  
  //
  //
  //  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)
  
  // end_wdm end_nthal end_ntifs end_ntndis
  
  
  // end_ntddk
  
  
  //
  //  Define the generic table package.  Note a generic table should really
  //  be an opaque type.  We provide routines to manipulate the structure.
  //
  //  A generic table is package for inserting, deleting, and looking up elements
  //  in a table (e.g., in a symbol table).  To use this package the user
  //  defines the structure of the elements stored in the table, provides a
  //  comparison function, a memory allocation function, and a memory
  //  deallocation function.
  //
  //  Note: the user compare function must impose a complete ordering among
  //  all of the elements, and the table does not allow for duplicate entries.
  //
  
  //
  // Add an empty typedef so that functions can reference the
  // a pointer to the generic table struct before it is declared.
  //
  
  struct _LLS_GENERIC_TABLE;
  
  //
  //  The results of a compare can be less than, equal, or greater than.
  //
  
  typedef enum _LLS_GENERIC_COMPARE_RESULTS {
      LLSGenericLessThan,
      LLSGenericGreaterThan,
      LLSGenericEqual
  } LLS_GENERIC_COMPARE_RESULTS;
  
  //
  //  The comparison function takes as input pointers to elements containing
  //  user defined structures and returns the results of comparing the two
  //  elements.
  //
  
  typedef
  LLS_GENERIC_COMPARE_RESULTS
  (NTAPI *PLLS_GENERIC_COMPARE_ROUTINE) (
      struct _LLS_GENERIC_TABLE *Table,
      PVOID FirstStruct,
      PVOID SecondStruct
      );
  
  //
  //  The allocation function is called by the generic table package whenever
  //  it needs to allocate memory for the table.
  //
  
  typedef
  PVOID
  (NTAPI *PLLS_GENERIC_ALLOCATE_ROUTINE) (
      struct _LLS_GENERIC_TABLE *Table,
      CLONG ByteSize
      );
  
  //
  //  The deallocation function is called by the generic table package whenever
  //  it needs to deallocate memory from the table that was allocated by calling
  //  the user supplied allocation function.
  //
  
  typedef
  VOID
  (NTAPI *PLLS_GENERIC_FREE_ROUTINE) (
      struct _LLS_GENERIC_TABLE *Table,
      PVOID Buffer
      );
  
  //
  //  To use the generic table package the user declares a variable of type
  //  GENERIC_TABLE and then uses the routines described below to initialize
  //  the table and to manipulate the table.  Note that the generic table
  //  should really be an opaque type.
  //
  
  typedef struct _LLS_GENERIC_TABLE {
      PRTL_SPLAY_LINKS TableRoot;
      LIST_ENTRY InsertOrderList;
      PLIST_ENTRY OrderedPointer;
      ULONG WhichOrderedElement;
      ULONG NumberGenericTableElements;
      PLLS_GENERIC_COMPARE_ROUTINE CompareRoutine;
      PLLS_GENERIC_ALLOCATE_ROUTINE AllocateRoutine;
      PLLS_GENERIC_FREE_ROUTINE FreeRoutine;
      PVOID TableContext;
  } LLS_GENERIC_TABLE;
  typedef LLS_GENERIC_TABLE *PLLS_GENERIC_TABLE;
  
  //
  // This enumerated type is used as the function return value of the function
  // that is used to search the tree for a key. FoundNode indicates that the
  // function found the key. Insert as left indicates that the key was not found
  // and the node should be inserted as the left child of the parent. Insert as
  // right indicates that the key was not found and the node should be inserted
  //  as the right child of the parent.
  //
  typedef enum _LLS_TABLE_SEARCH_RESULT{
      LLSTableEmptyTree,
      LLSTableFoundNode,
      LLSTableInsertAsLeft,
      LLSTableInsertAsRight
  } LLS_TABLE_SEARCH_RESULT;
  
  //
  //  The procedure InitializeGenericTable takes as input an uninitialized
  //  generic table variable and pointers to the three user supplied routines.
  //  This must be called for every individual generic table variable before
  //  it can be used.
  //
  
  
  VOID
  NTAPI
  LLSInitializeGenericTable (
      PLLS_GENERIC_TABLE Table,
      PLLS_GENERIC_COMPARE_ROUTINE CompareRoutine,
      PLLS_GENERIC_ALLOCATE_ROUTINE AllocateRoutine,
      PLLS_GENERIC_FREE_ROUTINE FreeRoutine,
      PVOID TableContext
      );
  
  //
  //  The function InsertElementGenericTable will insert a new element
  //  in a table.  It does this by allocating space for the new element
  //  (this includes splay links), inserting the element in the table, and
  //  then returning to the user a pointer to the new element.  If an element
  //  with the same key already exists in the table the return value is a pointer
  //  to the old element.  The optional output parameter NewElement is used
  //  to indicate if the element previously existed in the table.  Note: the user
  //  supplied Buffer is only used for searching the table, upon insertion its
  //  contents are copied to the newly created element.  This means that
  //  pointer to the input buffer will not point to the new element.
  //
  
  
  PVOID
  NTAPI
  LLSInsertElementGenericTable (
      PLLS_GENERIC_TABLE Table,
      PVOID Buffer,
      CLONG BufferSize,
      PBOOLEAN NewElement OPTIONAL
      );
  
  //
  //  The function InsertElementGenericTableFull will insert a new element
  //  in a table.  It does this by allocating space for the new element
  //  (this includes splay links), inserting the element in the table, and
  //  then returning to the user a pointer to the new element.  If an element
  //  with the same key already exists in the table the return value is a pointer
  //  to the old element.  The optional output parameter NewElement is used
  //  to indicate if the element previously existed in the table.  Note: the user
  //  supplied Buffer is only used for searching the table, upon insertion its
  //  contents are copied to the newly created element.  This means that
  //  pointer to the input buffer will not point to the new element.
  //  This routine is passed the NodeOrParent and SearchResult from a
  //  previous RtlLookupElementGenericTableFull.
  //
  
  
  PVOID
  NTAPI
  LLSInsertElementGenericTableFull (
      PLLS_GENERIC_TABLE Table,
      PVOID Buffer,
      CLONG BufferSize,
      PBOOLEAN NewElement OPTIONAL,
      PVOID NodeOrParent,
      LLS_TABLE_SEARCH_RESULT SearchResult
      );
  
  //
  //  The function DeleteElementGenericTable will find and delete an element
  //  from a generic table.  If the element is located and deleted the return
  //  value is TRUE, otherwise if the element is not located the return value
  //  is FALSE.  The user supplied input buffer is only used as a key in
  //  locating the element in the table.
  //
  
  
  BOOLEAN
  NTAPI
  LLSDeleteElementGenericTable (
      PLLS_GENERIC_TABLE Table,
      PVOID Buffer
      );
  
  //
  //  The function LookupElementGenericTable will find an element in a generic
  //  table.  If the element is located the return value is a pointer to
  //  the user defined structure associated with the element, otherwise if
  //  the element is not located the return value is NULL.  The user supplied
  //  input buffer is only used as a key in locating the element in the table.
  //
  
  
  PVOID
  NTAPI
  LLSLookupElementGenericTable (
      PLLS_GENERIC_TABLE Table,
      PVOID Buffer
      );
  
  //
  //  The function LookupElementGenericTableFull will find an element in a generic
  //  table.  If the element is located the return value is a pointer to
  //  the user defined structure associated with the element.  If the element is not
  //  located then a pointer to the parent for the insert location is returned.  The
  //  user must look at the SearchResult value to determine which is being returned.
  //  The user can use the SearchResult and parent for a subsequent FullInsertElement
  //  call to optimize the insert.
  //
  
  
  PVOID
  NTAPI
  LLSLookupElementGenericTableFull (
      PLLS_GENERIC_TABLE Table,
      PVOID Buffer,
      OUT PVOID *NodeOrParent,
      OUT LLS_TABLE_SEARCH_RESULT *SearchResult
      );
  
  //
  //  The function EnumerateGenericTable will return to the caller one-by-one
  //  the elements of of a table.  The return value is a pointer to the user
  //  defined structure associated with the element.  The input parameter
  //  Restart indicates if the enumeration should start from the beginning
  //  or should return the next element.  If the are no more new elements to
  //  return the return value is NULL.  As an example of its use, to enumerate
  //  all of the elements in a table the user would write:
  //
  //      for (ptr = EnumerateGenericTable(Table, TRUE);
  //           ptr != NULL;
  //           ptr = EnumerateGenericTable(Table, FALSE)) {
  //              :
  //      }
  //
  //
  //  PLEASE NOTE:
  //
  //      If you enumerate a GenericTable using RtlEnumerateGenericTable, you
  //      will flatten the table, turning it into a sorted linked list.
  //      To enumerate the table without perturbing the splay links, use
  //      RtlEnumerateGenericTableWithoutSplaying
  
  
  PVOID
  NTAPI
  LLSEnumerateGenericTable (
      PLLS_GENERIC_TABLE Table,
      BOOLEAN Restart
      );
  
  //
  //  The function EnumerateGenericTableWithoutSplaying will return to the
  //  caller one-by-one the elements of of a table.  The return value is a
  //  pointer to the user defined structure associated with the element.
  //  The input parameter RestartKey indicates if the enumeration should
  //  start from the beginning or should return the next element.  If the
  //  are no more new elements to return the return value is NULL.  As an
  //  example of its use, to enumerate all of the elements in a table the
  //  user would write:
  //
  //      RestartKey = NULL;
  //      for (ptr = EnumerateGenericTableWithoutSplaying(Table, &RestartKey);
  //           ptr != NULL;
  //           ptr = EnumerateGenericTableWithoutSplaying(Table, &RestartKey)) {
  //              :
  //      }
  //
  //  If RestartKey is NULL, the package will start from the least entry in the
  //  table, otherwise it will start from the last entry returned.
  //
  //
  //  Note that unlike RtlEnumerateGenericTable, this routine will NOT perturb
  //  the splay order of the tree.
  //
  
  
  PVOID
  NTAPI
  LLSEnumerateGenericTableWithoutSplaying (
      PLLS_GENERIC_TABLE Table,
      PVOID *RestartKey
      );
  
  //
  // The function GetElementGenericTable will return the i'th element
  // inserted in the generic table.  I = 0 implies the first element,
  // I = (RtlNumberGenericTableElements(Table)-1) will return the last element
  // inserted into the generic table.  The type of I is ULONG.  Values
  // of I > than (NumberGenericTableElements(Table)-1) will return NULL.  If
  // an arbitrary element is deleted from the generic table it will cause
  // all elements inserted after the deleted element to "move up".
  
  
  PVOID
  NTAPI
  LLSGetElementGenericTable(
      PLLS_GENERIC_TABLE Table,
      ULONG I
      );
  
  //
  // The function NumberGenericTableElements returns a ULONG value
  // which is the number of generic table elements currently inserted
  // in the generic table.
  
  
  ULONG
  NTAPI
  LLSNumberGenericTableElements(
      PLLS_GENERIC_TABLE Table
      );
  
  //
  //  The function IsGenericTableEmpty will return to the caller TRUE if
  //  the input table is empty (i.e., does not contain any elements) and
  //  FALSE otherwise.
  //
  
  
  BOOLEAN
  NTAPI
  LLSIsGenericTableEmpty (
      PLLS_GENERIC_TABLE Table
      );
  
  // end_ntifs
  
  #endif // _LLSRTL_
  