list.h

<Win2k系统编程>源码.次数为国人自编,内容丰富,还是不错的.

/*
 * LIST.H
 */
/*------------------------------------------------------------------------
| Abstract data type LIST OF (*untyped*) object.
| Different lists can have different types of object in them
| Different items in a list can have different types of object in them.
| The price of this lack of typing is that you have a slightly more
| awkward syntax and you get no help from the compiler if you try to
| put the wrong type of data into the list.
|
| The list is implemented as a collection of items.  Within the item
| somewhere is the object.
|
| Objects are stored UNALIGNED within items.
|
| Use:
|
|   #include <list.h>
|   . . .
|   LIST MyList; (* or LIST liMyList for Hungarians *)
|   . . .
|   MyList = List_Create();
|   List_AddLast(MyList,&MyObject,sizeof(OBJECT));
|
| In the abstract a LIST is a list of objects.  The representation
| is a linked collection of items.  The manner of the linking is
| implementation dependent (as I write this it's linear but when you
| read it it might be a tree (See Knuth for why a tree)).
|
| A LIST is a "handle" for a list which may be thought of as a POINTER
| (whether it is really a pointer or not is implementation dependent)
| so that it can be copied at the risk of creating an alias. e.g.
|
|   L = List_Create();
|   L1 = L;             (* L and L1 are both healthy and empty *)
|   List_AddFirst(L, &elem, sizeof(elem));
|   (* L1 may also appear to have one object, there again it may be sick *)
|   L1 = L;               (* Now they both surely see the one element *)
|   List_Destroy(&L1);    (* L is almost certainly sick now too *)
|   L1 = List_Create();   (* All bets off as to what L is like now
|                            but L1 is empty and healthy
|                         *)
|
| If two handles compare equal then the lists must be equal, but
| unequal handles could address two similar lists i.e. the same list
| of objects held in two different LISTs of items (like pointers).
|
| A LIST can be transferred from one variable to another like this:
|
|   NewList = OldList;           (* copy the handle *)
|   OldList = List_Create();     (* kill the old alias *)
|
| and the Create statement can be omitted if OldList is never touched again.
|
| Items are identified by Cursors.  A cursor is the address of an object
| within an item in the list. i.e. it is the address of the piece of your
| data that you had inserted.  (It is probably NOT the address of the item).
| It is typed as pointer to void here, but you should declare it as a pointer
| to whatever sort of object you are putting in the LIST.
|
| The operations AddFirst, AddLast, AddAfter and AddBefore
| all copy elements by direct assignment.  If an element is itself
| a complex structure (say a tree) then this will only copy a pointer
| or an anchor block or whatever and give all the usual problems of
| aliases.  Clear will make the list empty, but will only free the
| storage that it can "see" directly.  SplitBefore or Split After may
| also perform a Clear operation.  To deal with fancy data structures
| use New rather than Add calls and copy the data yourself
|   e.g.  P = List_NewLast(MyList, sizeof(MyArray[14])*(23-14+1));
|         CopyArraySlice(P, MyArray, 14, 23);
|
| The operations NewFirst, NewLast, NewAfter, NewBefore, First and Last
| all return pointers to elements and thus allow you to do any copying.
| This is how you might copy a whole list of fancy structures:
|
|    void CopyFancyList(LIST * To, LIST From)
|             (* Assumes that To has been Created and is empty *)
|    { PELEMENT Cursor;
|      PELEMENT P;
|
|      List_TRAVERSE(From, Cursor);
|      { P = List_NewLast(To, sizeof(element) );
|        FancyCopy(P, Cursor);    (* Copy so that *Cursor==*P afterwords *)
|      }
|    }
 --------------------------------------------------------------------*/

  typedef struct item_tag FAR * LIST;
  typedef LIST FAR * PLIST;

  void APIENTRY List_Init(void);
  /* MUST BE CALLED BEFORE ANY OF THE OTHER FUNCTIONS. */

  void APIENTRY List_Dump(LPSTR Header, LIST lst);
  /* Dump the internals to current output stream -- debug only */

  void APIENTRY List_Show(LIST lst);
  /* Dump hex representation of handle to current out stream -- debug only */

  LIST APIENTRY List_Create(void);
  /* Create a list.  It will be initially empty */

  void APIENTRY List_Destroy(PLIST plst);
  /* Destroy *plst.  It does not need to be empty first.
  |  All storage directly in the list wil be freed.
  */

  void APIENTRY List_AddFirst(LIST lst, LPVOID pObject, UINT uLen);
  /* Add an item holding Object to the beginning of * plst */

  LPVOID APIENTRY List_NewFirst(LIST lst, UINT uLen);
  /* Return the address of the place for Len bytes of data in a new
  |  item at the start of *plst
  */

  void APIENTRY List_DeleteFirst(LIST lst);
  /* Delete the first item in lst.  Error if lst is empty */

  void APIENTRY List_AddLast(LIST lst, LPVOID pObject, UINT uLen);
  /* Add an item holding Object to the end of lst */

  LPVOID APIENTRY List_NewLast(LIST lst, UINT uLen);
  /* Return the address of the place for uLen bytes of data in a new
  |  item at the end of lst
  */

  void APIENTRY List_DeleteLast(LIST lst);
  /* Delete the last item in lst.  Error if lst is empty */

  void APIENTRY List_AddAfter( LIST lst
                    , LPVOID Curs
                    , LPVOID pObject
                    , UINT uLen
                    );
  /*--------------------------------------------------------------------
  | Add an item holding *pObject to lst immediately after Curs.
  | List_AddAfter(lst, NULL, pObject, Len) adds it to the start of the lst
   ---------------------------------------------------------------------*/

  LPVOID APIENTRY List_NewAfter(LIST lst, LPVOID Curs, UINT uLen);
  /*--------------------------------------------------------------------
  | Return the address of the place for uLen bytes of data in a new
  | item immediately after Curs.
  | List_NewAfter(Lst, NULL, uLen) returns a pointer
  | to space for uLen bytes in a new first element.
   ---------------------------------------------------------------------*/

  void APIENTRY List_AddBefore( LIST lst
                     , LPVOID Curs
                     , LPVOID pObject
                     , UINT uLen
                     );
  /*--------------------------------------------------------------------
  | Add an item holding Object to lst immediately before Curs.
  | List_AddBefore(Lst, NULL, Object, uLen) adds it to the end of the list
   ---------------------------------------------------------------------*/

  LPVOID APIENTRY List_NewBefore(LIST lst, LPVOID Curs, UINT uLen );
  /*--------------------------------------------------------------------
  | Return the address of the place for uLen bytes of data in a new
  | item immediately before Curs.
  | List_NewBefore(Lst, NULL, uLen) returns a pointer
  | to space for uLen bytes in a new last element.
   ---------------------------------------------------------------------*/

  void APIENTRY List_Delete(LPVOID Curs);
  /*------------------------------------------------------------------
  | Delete the item that Curs identifies.
  | This will be only a few (maybe as little as 3) machine instructions
  | quicker than DeleteAndNext or DeleteAndPrev but leaves Curs dangling.
  | It is therefore NOT usually to be preferred.
  | It may be useful when you have a function which returns an LPVOID
  | since the argument does not need to be a variable.
  |     Trivial example: List_Delete(List_First(L));
   -------------------------------------------------------------------*/