![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to list.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff|
Return to list.h CVS log | Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff |
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.