Return to list.h CVS log

Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff

Annotation of mstools/samples/sdktools/windiff/list.h, revision 1.1

1.1     ! root        1: 
        !             2: /******************************************************************************\
        !             3: *       This is a part of the Microsoft Source Code Samples. 
        !             4: *       Copyright (C) 1993 Microsoft Corporation.
        !             5: *       All rights reserved. 
        !             6: *       This source code is only intended as a supplement to 
        !             7: *       Microsoft Development Tools and/or WinHelp documentation.
        !             8: *       See these sources for detailed information regarding the 
        !             9: *       Microsoft samples programs.
        !            10: \******************************************************************************/
        !            11: 
        !            12: /*
        !            13:  * LIST.H
        !            14:  */
        !            15: /*------------------------------------------------------------------------
        !            16: | Abstract data type LIST OF (*untyped*) object.
        !            17: | Different lists can have different types of object in them
        !            18: | Different items in a list can have different types of object in them.
        !            19: | The price of this lack of typing is that you have a slightly more
        !            20: | awkward syntax and you get no help from the compiler if you try to
        !            21: | put the wrong type of data into the list.
        !            22: |
        !            23: | The list is implemented as a collection of items.  Within the item
        !            24: | somewhere is the object.
        !            25: |
        !            26: | Objects are stored UNALIGNED within items.
        !            27: |
        !            28: | Use:
        !            29: |
        !            30: |   #include <list.h>
        !            31: |   . . .
        !            32: |   LIST MyList; (* or LIST liMyList for Hungarians *)
        !            33: |   . . .
        !            34: |   MyList = List_Create();
        !            35: |   List_AddLast(MyList,&MyObject,sizeof(OBJECT));
        !            36: |
        !            37: | In the abstract a LIST is a list of objects.  The representation
        !            38: | is a linked collection of items.  The manner of the linking is
        !            39: | implementation dependent (as I write this it's linear but when you
        !            40: | read it it might be a tree (See Knuth for why a tree)).
        !            41: |
        !            42: | A LIST is a "handle" for a list which may be thought of as a POINTER
        !            43: | (whether it is really a pointer or not is implementation dependent)
        !            44: | so that it can be copied at the risk of creating an alias. e.g.
        !            45: |
        !            46: |   L = List_Create();
        !            47: |   L1 = L;             (* L and L1 are both healthy and empty *)
        !            48: |   List_AddFirst(L, &elem, sizeof(elem));
        !            49: |   (* L1 may also appear to have one object, there again it may be sick *)
        !            50: |   L1 = L;               (* Now they both surely see the one element *)
        !            51: |   List_Destroy(&L1);    (* L is almost certainly sick now too *)
        !            52: |   L1 = List_Create();   (* All bets off as to what L is like now
        !            53: |                            but L1 is empty and healthy
        !            54: |                         *)
        !            55: |
        !            56: | If two handles compare equal then the lists must be equal, but
        !            57: | unequal handles could address two similar lists i.e. the same list
        !            58: | of objects held in two different LISTs of items (like pointers).
        !            59: |
        !            60: | A LIST can be transferred from one variable to another like this:
        !            61: |
        !            62: |   NewList = OldList;           (* copy the handle *)
        !            63: |   OldList = List_Create();     (* kill the old alias *)
        !            64: |
        !            65: | and the Create statement can be omitted if OldList is never touched again.
        !            66: |
        !            67: | Items are identified by Cursors.  A cursor is the address of an object
        !            68: | within an item in the list. i.e. it is the address of the piece of your
        !            69: | data that you had inserted.  (It is probably NOT the address of the item).
        !            70: | It is typed as pointer to void here, but you should declare it as a pointer
        !            71: | to whatever sort of object you are putting in the LIST.
        !            72: |
        !            73: | The operations AddFirst, AddLast, AddAfter and AddBefore
        !            74: | all copy elements by direct assignment.  If an element is itself
        !            75: | a complex structure (say a tree) then this will only copy a pointer
        !            76: | or an anchor block or whatever and give all the usual problems of
        !            77: | aliases.  Clear will make the list empty, but will only free the
        !            78: | storage that it can "see" directly.  SplitBefore or Split After may
        !            79: | also perform a Clear operation.  To deal with fancy data structures
        !            80: | use New rather than Add calls and copy the data yourself
        !            81: |   e.g.  P = List_NewLast(MyList, sizeof(MyArray[14])*(23-14+1));
        !            82: |         CopyArraySlice(P, MyArray, 14, 23);
        !            83: |
        !            84: | The operations NewFirst, NewLast, NewAfter, NewBefore, First and Last
        !            85: | all return pointers to elements and thus allow you to do any copying.
        !            86: | This is how you might copy a whole list of fancy structures:
        !            87: |
        !            88: |    void CopyFancyList(LIST * To, LIST From)
        !            89: |             (* Assumes that To has been Created and is empty *)
        !            90: |    { PELEMENT Cursor;
        !            91: |      PELEMENT P;
        !            92: |
        !            93: |      List_TRAVERSE(From, Cursor);
        !            94: |      { P = List_NewLast(To, sizeof(element) );
        !            95: |        FancyCopy(P, Cursor);    (* Copy so that *Cursor==*P afterwords *)
        !            96: |      }
        !            97: |    }
        !            98:  --------------------------------------------------------------------*/
        !            99: 
        !           100:   typedef struct item_tag FAR * LIST;
        !           101:   typedef LIST FAR * PLIST;
        !           102: 
        !           103:   void APIENTRY List_Init(void);
        !           104:   /* MUST BE CALLED BEFORE ANY OF THE OTHER FUNCTIONS. */
        !           105: 
        !           106:   void APIENTRY List_Dump(LPSTR Header, LIST lst);
        !           107:   /* Dump the internals to current output stream -- debug only */
        !           108: 
        !           109:   void APIENTRY List_Show(LIST lst);
        !           110:   /* Dump hex representation of handle to current out stream -- debug only */
        !           111: 
        !           112:   LIST APIENTRY List_Create(void);
        !           113:   /* Create a list.  It will be initially empty */
        !           114: 
        !           115:   void APIENTRY List_Destroy(PLIST plst);
        !           116:   /* Destroy *plst.  It does not need to be empty first.
        !           117:   |  All storage directly in the list wil be freed.
        !           118:   */
        !           119: 
        !           120:   void APIENTRY List_AddFirst(LIST lst, LPVOID pObject, UINT uLen);
        !           121:   /* Add an item holding Object to the beginning of * plst */
        !           122: 
        !           123:   LPVOID APIENTRY List_NewFirst(LIST lst, UINT uLen);
        !           124:   /* Return the address of the place for Len bytes of data in a new
        !           125:   |  item at the start of *plst
        !           126:   */
        !           127: 
        !           128:   void APIENTRY List_DeleteFirst(LIST lst);
        !           129:   /* Delete the first item in lst.  Error if lst is empty */
        !           130: 
        !           131:   void APIENTRY List_AddLast(LIST lst, LPVOID pObject, UINT uLen);
        !           132:   /* Add an item holding Object to the end of lst */
        !           133: 
        !           134:   LPVOID APIENTRY List_NewLast(LIST lst, UINT uLen);
        !           135:   /* Return the address of the place for uLen bytes of data in a new
        !           136:   |  item at the end of lst
        !           137:   */
        !           138: 
        !           139:   void APIENTRY List_DeleteLast(LIST lst);
        !           140:   /* Delete the last item in lst.  Error if lst is empty */
        !           141: 
        !           142:   void APIENTRY List_AddAfter( LIST lst
        !           143:                     , LPVOID Curs
        !           144:                     , LPVOID pObject
        !           145:                     , UINT uLen
        !           146:                     );
        !           147:   /*--------------------------------------------------------------------
        !           148:   | Add an item holding *pObject to lst immediately after Curs.
        !           149:   | List_AddAfter(lst, NULL, pObject, Len) adds it to the start of the lst
        !           150:    ---------------------------------------------------------------------*/
        !           151: 
        !           152:   LPVOID APIENTRY List_NewAfter(LIST lst, LPVOID Curs, UINT uLen);
        !           153:   /*--------------------------------------------------------------------
        !           154:   | Return the address of the place for uLen bytes of data in a new
        !           155:   | item immediately after Curs.
        !           156:   | List_NewAfter(Lst, NULL, uLen) returns a pointer
        !           157:   | to space for uLen bytes in a new first element.
        !           158:    ---------------------------------------------------------------------*/
        !           159: 
        !           160:   void APIENTRY List_AddBefore( LIST lst
        !           161:                      , LPVOID Curs
        !           162:                      , LPVOID pObject
        !           163:                      , UINT uLen
        !           164:                      );
        !           165:   /*--------------------------------------------------------------------
        !           166:   | Add an item holding Object to lst immediately before Curs.
        !           167:   | List_AddBefore(Lst, NULL, Object, uLen) adds it to the end of the list
        !           168:    ---------------------------------------------------------------------*/
        !           169: 
        !           170:   LPVOID APIENTRY List_NewBefore(LIST lst, LPVOID Curs, UINT uLen );
        !           171:   /*--------------------------------------------------------------------
        !           172:   | Return the address of the place for uLen bytes of data in a new
        !           173:   | item immediately before Curs.
        !           174:   | List_NewBefore(Lst, NULL, uLen) returns a pointer
        !           175:   | to space for uLen bytes in a new last element.
        !           176:    ---------------------------------------------------------------------*/
        !           177: 
        !           178:   void APIENTRY List_Delete(LPVOID Curs);
        !           179:   /*------------------------------------------------------------------
        !           180:   | Delete the item that Curs identifies.
        !           181:   | This will be only a few (maybe as little as 3) machine instructions
        !           182:   | quicker than DeleteAndNext or DeleteAndPrev but leaves Curs dangling.
        !           183:   | It is therefore NOT usually to be preferred.
        !           184:   | It may be useful when you have a function which returns an LPVOID
        !           185:   | since the argument does not need to be a variable.
        !           186:   |     Trivial example: List_Delete(List_First(L));
        !           187:    -------------------------------------------------------------------*/
        !           188: 
        !           189:   int APIENTRY List_ItemLength(LPVOID Curs);
        !           190:   /* Return the length of the object identified by the cursor Curs */
        !           191: 
        !           192:   /*------------------------------------------------------------------
        !           193:   | TRAVERSING THE ULIST
        !           194:   |
        !           195:   | LIST lst;
        !           196:   | object * Curs;
        !           197:   | . . .
        !           198:   | Curs = List_First(lst);
        !           199:   | while (Curs!=NULL)
        !           200:   | {  DoSomething(*Curs);   (* Curs points to YOUR data not to chain ptrs *)
        !           201:   |    Curs = List_Next(Curs);
        !           202:   | }
        !           203:   |
        !           204:   | This is identically equal to
        !           205:   | List_TRAVERSE(lst, Curs)  // note NO SEMI COLON!
        !           206:   | {  DoSomething(*Curs); }
        !           207:    -------------------------------------------------------------------*/
        !           208: 
        !           209:   #define List_TRAVERSE(lst, curs)  for(  curs=List_First(lst)            \
        !           210:                                        ;  curs!=NULL                      \
        !           211:                                        ;  curs = List_Next((LPVOID)curs)  \
        !           212:                                        )
        !           213: 
        !           214:   LPVOID APIENTRY List_First(LIST lst);
        !           215:   /*------------------------------------------------------------------
        !           216:   | Return the address of the first object in lst
        !           217:   |  If lst is empty then Return NULL.
        !           218:   --------------------------------------------------------------------*/
        !           219: 
        !           220:   LPVOID APIENTRY List_Last(LIST lst);
        !           221:   /*------------------------------------------------------------------
        !           222:   | Return the address of the last object in lst
        !           223:   | If lst is empty then return NULL.
        !           224:   --------------------------------------------------------------------*/
        !           225: 
        !           226:   LPVOID APIENTRY List_Next(LPVOID Curs);
        !           227:   /*------------------------------------------------------------------
        !           228:   | Return the address of the object after Curs^.
        !           229:   | List_Next(List_Last(lst)) == NULL;  List_Next(NULL) is an error.
        !           230:   | List_Next(List_Prev(curs)) is illegal if curs identifies first el
        !           231:   --------------------------------------------------------------------*/
        !           232: 
        !           233:   LPVOID APIENTRY List_Prev(LPVOID Curs);
        !           234:   /*------------------------------------------------------------------
        !           235:   | Return the address of the object after Curs^.
        !           236:   | List_Prev(List_First(L)) == NULL;  List_Prev(NULL) is an error.
        !           237:   | List_Prev(List_Next(curs)) is illegal if curs identifies last el
        !           238:   --------------------------------------------------------------------*/
        !           239: 
        !           240:   /*------------------------------------------------------------------
        !           241:   |  Whole list operations
        !           242:    -----------------------------------------------------------------*/
        !           243:   void APIENTRY List_Clear(LIST lst);
        !           244:   /* arrange that lst is empty after this */
        !           245: 
        !           246:   BOOL APIENTRY List_IsEmpty(LIST lst);
        !           247:   /* Return TRUE if and only if lst is empty */
        !           248: 
        !           249:   void APIENTRY List_Join(LIST l1, LIST l2);
        !           250:   /*-----------------------------------------------------------------------
        !           251:   | l1 := l1||l2; l2 := empty
        !           252:   | The elements themselves are not moved, so pointers to them remain valid.
        !           253:   |
        !           254:   | l1 gets all the elements of l1 in their original order followed by
        !           255:   | all the elements of l2 in the order they were in in l2.
        !           256:   | l2 becomes empty.
        !           257:    ------------------------------------------------------------------------*/
        !           258: 
        !           259:   void APIENTRY List_InsertListAfter(LIST l1, LIST l2, LPVOID Curs);
        !           260:   /*-----------------------------------------------------------------------
        !           261:   | l1 := l1[...Curs] || l2 || l1[Curs+1...]; l2 := empty
        !           262:   | Curs=NULL means insert l2 at the start of l1
        !           263:   | The elements themselves are not moved, so pointers to them remain valid.
        !           264:   |
        !           265:   | l1 gets the elements of l1 from the start up to and including the element
        !           266:   | that Curs points at, in their original order,
        !           267:   | followed by all the elements that were in l2, in their original order,
        !           268:   | followed by the rest of l1
        !           269:    ------------------------------------------------------------------------*/
        !           270: 
        !           271:   void APIENTRY List_InsertListBefore(LIST l1, LIST l2, LPVOID Curs);
        !           272:   /*-----------------------------------------------------------------------
        !           273:   | l1 := l1[...Curs-1] || l2 || l1[Curs...]; l2 := empty
        !           274:   | Curs=NULL means insert l2 at the end of l1
        !           275:   | The elements themselves are not moved, so pointers to them remain valid.
        !           276:   |
        !           277:   | l1 gets the elements of l1 from the start up to but not including the
        !           278:   | element that Curs points at, in their original order,
        !           279:   | followed by all the elements that were in l2, in their original order,
        !           280:   | followed by the rest of l1.
        !           281:    ------------------------------------------------------------------------*/
        !           282: 
        !           283:   void APIENTRY List_SplitAfter(LIST l1, LIST l2, LPVOID Curs);
        !           284:   /*-----------------------------------------------------------------------
        !           285:   | Let l1 be l1 and l2 be l2
        !           286:   | Split l2 off from the front of l1:    final l2,l1 = original l1
        !           287:   |
        !           288:   | Split l1 into l2: objects of l1 up to and including Curs object
        !           289:   |               l1: objects of l1 after Curs
        !           290:   | Any original contents of l2 are freed.
        !           291:   | List_Spilt(l1, l2, NULL) splits l1 before the first object so l1 gets all.
        !           292:   | The elements themselves are not moved.
        !           293:    ------------------------------------------------------------------------*/
        !           294: 
        !           295:   void APIENTRY List_SplitBefore(LIST l1, LIST l2, LPVOID Curs);
        !           296:   /*----------------------------------------------------------------------
        !           297:   | Split l2 off from the back of l1:  final l1,l2 = original l1
        !           298:   |
        !           299:   | Split l1 into l1: objects of l1 up to but not including Curs object
        !           300:   |               l2: objects of l1 from Curs onwards
        !           301:   | Any original contants of l2 are freed.
        !           302:   | List_Spilt(l1, l2, NULL) splits l1 after the last object so l1 gets all.
        !           303:   | The elements themselves are not moved.
        !           304:    -----------------------------------------------------------------------*/
        !           305: 
        !           306:   int APIENTRY List_Card(LIST lst);
        !           307:   /* Return the number of items in L */
        !           308: 
        !           309:   /*------------------------------------------------------------------
        !           310:   | Error handling.
        !           311:   |
        !           312:   | Each list has within it a flag which indicates whether any illegal
        !           313:   | operation has been detected (e.g. DeleteFirst when empty).
        !           314:   | Rather than have a flag on every operation, there is a flag held
        !           315:   | within the list that can be queried when convenient.  Many operations
        !           316:   | do not have enough redundancy to allow any meaningful check.  This
        !           317:   | is a design compromise (for instance to allow P = List_Next(P);
        !           318:   | rather than P = List_Next(L, P); which is more awkward, especially
        !           319:   | if L is actually a lengthy phrase).
        !           320:   |
        !           321:   | List_IsOK tests this flag (so is a very simple, quick operation).
        !           322:   | MakeOK sets the flag to TRUE, in other words to accept the current
        !           323:   | state of the list.
        !           324:   |
        !           325:   | It is possible for a list to be damaged (whether or not the flag
        !           326:   | says OK) for instance by the storage being overwritten.
        !           327:   |
        !           328:   | List_Check attempts to verify that the list is sound (for instance where
        !           329:   | there are both forward and backward pointers they should agree).
        !           330:   |
        !           331:   | List_Recover attempts to make a sound list out of whatever debris is left.
        !           332:   | If the list is damaged, Recover may trap (e.g. address error) but
        !           333:   | if the list was damaged then ANY operation on it may trap.
        !           334:   | If Check succeeds without trapping then so will Recover.
        !           335:    -----------------------------------------------------------------*/
        !           336: 
        !           337:   BOOL APIENTRY List_IsOK(LIST lst);
        !           338:   /* Check return code */
        !           339: 
        !           340:   void APIENTRY List_MakeOK(LIST lst);
        !           341:   /* Set return code to good */
        !           342: 
        !           343:   BOOL APIENTRY List_Check(LIST lst);
        !           344:   /* Attempt to validate the chains */
        !           345: 
        !           346:   void APIENTRY List_Recover(PLIST plst);
        !           347:   /* Desperate stuff.  Attempt to reconstruct something */
        !           348: 
        !           349: /*------------------------------------------------------------------
        !           350: |  It is designed to be as easy to USE as possible, consistent
        !           351: |  only with being an opaque type.
        !           352: |
        !           353: |  In particular, the decision to use the address of an object a list cursor
        !           354: |  means that there is a small amount of extra arithmetic (in the
        !           355: |  IMPLEMENTATION) in cursor operations (e.g. Next and Prev).
        !           356: |  and spurious arguments are avoided whenever possible, even though
        !           357: |  it would allow greater error checking.
        !           358: |
        !           359: | Of the "whole list" operations, Clear is given because it seems to be
        !           360: | a common operation, even though the caller can implement it with almost
        !           361: | the same efficiency as the List implementation module.
        !           362: | Join, Split and InsertListXxx cannot be implemented efficiently without
        !           363: | knowing the representation.
        !           364:  --------------------------------------------------------------------*/

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.