/*---------------------- | List | ----------------------*/ /* Laurie Griffiths, C version 5/12/91 */ /* worth also looking at nt\public\sdk\inc\ntrtl.h which also has some | low level list pointer chaining stuff in it */ /* Note here that Modula-2 style comments (*like this*) are used within examples which are already within C comments to indicate where comments should go in the examples */ /*------------------------------------------------------------------------ | 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 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. Don't ask, just do it */ void APIENTRY List_Term(void); /* Call at end of application (does some checking and resource freeing) */ 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. | The storage is zeroed BEFORE chaining it in. */ 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 | The storage is zeroed BEFORE chaining it in. */ 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. | The storage is zeroed BEFORE chaining it in. ---------------------------------------------------------------------*/ 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. | The storage is zeroed BEFORE chaining it in. ---------------------------------------------------------------------*/ #if 0 // these functions are not actually defined... void APIENTRY List_DeleteAndNext(LPVOID * pCurs); /* Delete the item that *pCurs identifies and move *pCurs to the Next item */ void APIENTRY List_DeleteAndPrev(LPVOID * pCurs); /* Delete the item that *pCurs identifies and move *pCurs to the Prev item */ #endif void APIENTRY List_Delete(LPVOID Curs); /*------------------------------------------------------------------ | Delete the item that Curs identifies. | I'm not too sure about this: | 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)); | I am not sure which is more damaging, a dangling pointer which points | at garbage or one that points at something that is real live data. -------------------------------------------------------------------*/ int APIENTRY List_ItemLength(LPVOID Curs); /* Return the length of the object identified by the cursor Curs */ /*------------------------------------------------------------------ | TRAVERSING THE ULIST | | LIST lst; | object * Curs; | . . . | Curs = List_First(lst); | while (Curs!=NULL) | { DoSomething(*Curs); (* Curs points to YOUR data not to chain ptrs *) | Curs = List_Next(Curs); | } | | This is identically equal to | List_TRAVERSE(lst, Curs) // note NO SEMI COLON! | { DoSomething(*Curs); } -------------------------------------------------------------------*/ #define List_TRAVERSE(lst, curs) for( curs=List_First(lst) \ ; curs!=NULL \ ; curs = List_Next((LPVOID)curs) \ ) #define List_REVERSETRAVERSE(lst, curs) for( curs=List_Last(lst) \ ; curs!=NULL \ ; curs = List_Prev((LPVOID)curs) \ ) LPVOID APIENTRY List_First(LIST lst); /*------------------------------------------------------------------ | Return the address of the first object in lst | If lst is empty then Return NULL. --------------------------------------------------------------------*/ LPVOID APIENTRY List_Last(LIST lst); /*------------------------------------------------------------------ | Return the address of the last object in lst | If lst is empty then return NULL. --------------------------------------------------------------------*/ LPVOID APIENTRY List_Next(LPVOID Curs); /*------------------------------------------------------------------ | Return the address of the object after Curs^. | List_Next(List_Last(lst)) == NULL; List_Next(NULL) is an error. | List_Next(List_Prev(curs)) is illegal if curs identifies first el --------------------------------------------------------------------*/ LPVOID APIENTRY List_Prev(LPVOID Curs); /*------------------------------------------------------------------ | Return the address of the object after Curs^. | List_Prev(List_First(L)) == NULL; List_Prev(NULL) is an error. | List_Prev(List_Next(curs)) is illegal if curs identifies last el --------------------------------------------------------------------*/ /*------------------------------------------------------------------ | Whole list operations -----------------------------------------------------------------*/ void APIENTRY List_Clear(LIST lst); /* arrange that lst is empty after this */ BOOL APIENTRY List_IsEmpty(LIST lst); /* Return TRUE if and only if lst is empty */ void APIENTRY List_Join(LIST l1, LIST l2); /*----------------------------------------------------------------------- | l1 := l1||l2; l2 := empty | The elements themselves are not moved, so pointers to them remain valid. | | l1 gets all the elements of l1 in their original order followed by | all the elements of l2 in the order they were in in l2. | l2 becomes empty. ------------------------------------------------------------------------*/ void APIENTRY List_InsertListAfter(LIST l1, LIST l2, LPVOID Curs); /*----------------------------------------------------------------------- | l1 := l1[...Curs] || l2 || l1[Curs+1...]; l2 := empty | Curs=NULL means insert l2 at the start of l1 | The elements themselves are not moved, so pointers to them remain valid. | | l1 gets the elements of l1 from the start up to and including the element | that Curs points at, in their original order, | followed by all the elements that were in l2, in their original order, | followed by the rest of l1 ------------------------------------------------------------------------*/ void APIENTRY List_InsertListBefore(LIST l1, LIST l2, LPVOID Curs); /*----------------------------------------------------------------------- | l1 := l1[...Curs-1] || l2 || l1[Curs...]; l2 := empty | Curs=NULL means insert l2 at the end of l1 | The elements themselves are not moved, so pointers to them remain valid. | | l1 gets the elements of l1 from the start up to but not including the | element that Curs points at, in their original order, | followed by all the elements that were in l2, in their original order, | followed by the rest of l1. ------------------------------------------------------------------------*/ void APIENTRY List_SplitAfter(LIST l1, LIST l2, LPVOID Curs); /*----------------------------------------------------------------------- | Let l1 be l1 and l2 be l2 | Split l2 off from the front of l1: final l2,l1 = original l1 | | Split l1 into l2: objects of l1 up to and including Curs object | l1: objects of l1 after Curs | Any original contents of l2 are freed. | List_Spilt(l1, l2, NULL) splits l1 before the first object so l1 gets all. | The elements themselves are not moved. ------------------------------------------------------------------------*/ void APIENTRY List_SplitBefore(LIST l1, LIST l2, LPVOID Curs); /*---------------------------------------------------------------------- | Split l2 off from the back of l1: final l1,l2 = original l1 | | Split l1 into l1: objects of l1 up to but not including Curs object | l2: objects of l1 from Curs onwards | Any original contants of l2 are freed. | List_Spilt(l1, l2, NULL) splits l1 after the last object so l1 gets all. | The elements themselves are not moved. -----------------------------------------------------------------------*/ int APIENTRY List_Card(LIST lst); /* Return the number of items in L */ /*------------------------------------------------------------------ | Error handling. | | Each list has within it a flag which indicates whether any illegal | operation has been detected (e.g. DeleteFirst when empty). | Rather than have a flag on every operation, there is a flag held | within the list that can be queried when convenient. Many operations | do not have enough redundancy to allow any meaningful check. This | is a design compromise (for instance to allow P = List_Next(P); | rather than P = List_Next(L, P); which is more awkward, especially | if L is actually a lengthy phrase). | | List_IsOK tests this flag (so is a very simple, quick operation). | MakeOK sets the flag to TRUE, in other words to accept the current | state of the list. | | It is possible for a list to be damaged (whether or not the flag | says OK) for instance by the storage being overwritten. | | List_Check attempts to verify that the list is sound (for instance where | there are both forward and backward pointers they should agree). | | List_Recover attempts to make a sound list out of whatever debris is left. | If the list is damaged, Recover may trap (e.g. address error) but | if the list was damaged then ANY operation on it may trap. | If Check succeeds without trapping then so will Recover. -----------------------------------------------------------------*/ BOOL APIENTRY List_IsOK(LIST lst); /* Check return code */ void APIENTRY List_MakeOK(LIST lst); /* Set return code to good */ BOOL APIENTRY List_Check(LIST lst); /* Attempt to validate the chains */ void APIENTRY List_Recover(PLIST plst); /* Desperate stuff. Attempt to reconstruct something */ /*------------------------------------------------------------------ | It is designed to be as easy to USE as possible, consistent | only with being an opaque type. | | In particular, the decision to use the address of an object a list cursor | means that there is a small amount of extra arithmetic (in the | IMPLEMENTATION) in cursor operations (e.g. Next and Prev). | and spurious arguments are avoided whenever possible, even though | it would allow greater error checking. | | Of the "whole list" operations, Clear is given because it seems to be | a common operation, even though the caller can implement it with almost | the same efficiency as the List implementation module. | Join, Split and InsertListXxx cannot be implemented efficiently without | knowing the representation. --------------------------------------------------------------------*/