1: /*_ list.c Mon Oct 31 1994 */
2: /* Copyright (C) 1986-1994 by Symantec */
3: /* All Rights Reserved */
4: /* Written by Walter Bright */
5:
6: #ifndef __STDIO_H
7: #include <stdio.h>
8: #endif
9: #ifndef __STRING_H
10: #include <string.h>
11: #endif
12: #ifndef __STDARG_H
13: #include <stdarg.h>
14: #endif
15: #ifndef assert
16: #include <assert.h>
17: #endif
18: #ifndef LIST_H
19: #include "list.h"
20: #endif
21: #ifndef MEM_H
22: #include "mem.h"
23: #endif
24:
25: #if MEM_DEBUG
26: #define fileline __FILE__,__LINE__
27: #else
28: #define fileline
29: #endif
30:
31: #ifndef list_freelist
32: list_t list_freelist = NULL; /* list of free list entries */
33: #endif
34: static int nlist; /* number of list items created */
35: int list_inited = 0; /* 1 if initialized */
36:
37: /* Free storage allocation */
38: #ifndef list_new
39:
40: #if (__ZTC__ || __SC__) && !MEM_DEBUG
41: #define list_new() ((list_t) mem_fmalloc(sizeof(struct LIST)))
42: #define list_delete(list) mem_ffree(list)
43: #else
44: #if MEM_DEBUG
45: #define list_new() ((list_t) mem_calloc_debug(sizeof(struct LIST),file,line))
46: #else
47: #define list_new() ((list_t) mem_malloc(sizeof(struct LIST)))
48: #endif
49: #define list_delete(list) mem_free(list)
50: #endif
51:
52: #endif
53:
54: /**********************/
55:
56: void list_init()
57: {
58: #ifdef DEBUG
59: assert(mem_inited);
60: #endif
61: if (list_inited == 0)
62: { nlist = 0;
63: list_inited++;
64: }
65: }
66:
67: /*******************/
68:
69: void list_term()
70: {
71: if (list_inited)
72: {
73: #ifdef DEBUG
74: printf("Max # of lists = %d\n",nlist);
75: #endif
76: while (list_freelist)
77: { list_t list;
78:
79: list = list_next(list_freelist);
80: list_delete(list_freelist);
81: list_freelist = list;
82: nlist--;
83: }
84: #ifdef DEBUG
85: if (nlist)
86: printf("nlist = %d\n",nlist);
87: #endif
88: #if !MEM_DEBUG
89: assert(nlist == 0);
90: #endif
91: list_inited = 0;
92: }
93: }
94:
95: /****************************
96: * Allocate list item.
97: */
98:
99: static list_t list_alloc
100: #if MEM_DEBUG
101: (char *file,int line)
102: #else
103: ()
104: #endif
105: { list_t list;
106:
107: if (list_freelist)
108: { list = list_freelist;
109: list_freelist = list_next(list);
110: #if MEM_DEBUG
111: mem_setnewfileline(list,file,line);
112: #endif
113: }
114: else
115: { nlist++;
116: list = list_new();
117: }
118: return list;
119: }
120:
121: /******************************/
122:
123: void list_free(list_t *plist,list_free_fp freeptr)
124: { list_t list,listnext;
125:
126: list = *plist;
127: *plist = 0; /* block any circular reference bugs */
128: while (list && --list->count == 0)
129: { listnext = list_next(list);
130: if (freeptr)
131: (*freeptr)(list_ptr(list));
132: #if DEBUG
133: memset(list,0,sizeof(*list));
134: #endif
135: #if 1
136: list->next = list_freelist;
137: list_freelist = list;
138: #else
139: list_delete(list);
140: nlist--;
141: #endif
142: list = listnext;
143: }
144: }
145:
146: /***************************/
147:
148: void *list_subtract(list_t *plist,void *ptr)
149: { list_t list;
150:
151: while ((list = *plist) != 0)
152: {
153: if (list_ptr(list) == ptr)
154: {
155: if (--list->count == 0)
156: { *plist = list_next(list);
157: list->next = list_freelist;
158: list_freelist = list;
159: }
160: return ptr;
161: }
162: else
163: plist = &(list_next(list));
164: }
165: return NULL; /* it wasn't in the list */
166: }
167:
168: /*************************/
169:
170: #if MEM_DEBUG
171: #undef list_append
172:
173: list_t list_append(list_t *plist,void *ptr)
174: {
175: return list_append_debug(plist,ptr,__FILE__,__LINE__);
176: }
177:
178: list_t list_append_debug(list_t *plist,void *ptr,char *file,int line)
179: #else
180: list_t list_append(list_t *plist,void *ptr)
181: #endif
182: { register list_t list;
183:
184: while (*plist)
185: plist = &(list_next(*plist)); /* find end of list */
186:
187: #if MEM_DEBUG
188: list = list_alloc(file,line);
189: #else
190: list = list_alloc();
191: #endif
192: if (list)
193: { *plist = list;
194: list_next(list) = 0;
195: list_ptr(list) = ptr;
196: list->count = 1;
197: }
198: return list;
199: }
200:
201: /*************************/
202:
203: list_t list_prepend(list_t *plist,void *ptr)
204: { register list_t list;
205:
206: list = list_alloc(fileline);
207: if (list)
208: { list_next(list) = *plist;
209: list_ptr(list) = ptr;
210: list->count = 1;
211: *plist = list;
212: }
213: return list;
214: }
215:
216: /*************************/
217:
218: #if __SC__ && __INTSIZE == 4 && _M_I86 && !_DEBUG_TRACE
219:
220: __declspec(naked) int __pascal list_nitems(list_t list)
221: {
222: _asm
223: {
224: mov ECX,list-4[ESP]
225: xor EAX,EAX
226: test ECX,ECX
227: jz L1
228: L2:
229: mov ECX,[ECX]LIST.next
230: inc EAX
231: test ECX,ECX
232: jnz L2
233: L1:
234: ret 4
235: }
236: }
237:
238: #else
239:
240: #if __DMC__
241: int __pascal list_nitems(list_t list)
242: #else
243: int list_nitems(list_t list)
244: #endif
245: { register int n;
246:
247: n = 0;
248: while (list)
249: { n++;
250: list = list_next(list);
251: }
252: return n;
253: }
254:
255: #endif
256:
257: /*************************/
258:
259: list_t list_nth(list_t list,int n)
260: { register int i;
261:
262: for (i = 0; i < n; i++)
263: { assert(list);
264: list = list_next(list);
265: }
266: return list;
267: }
268:
269: /*************************/
270:
271: list_t list_last(list_t list)
272: {
273: if (list)
274: while (list_next(list))
275: list = list_next(list);
276: return list;
277: }
278:
279: /**************************/
280:
281: list_t list_prev(list_t start,list_t list)
282: {
283: if (start)
284: { if (start == list)
285: start = NULL;
286: else
287: while (list_next(start) != list)
288: { start = list_next(start);
289: assert(start);
290: }
291: }
292: return start;
293: }
294:
295: /****************************/
296:
297: list_t list_copy(list_t list)
298: { list_t c;
299:
300: c = NULL;
301: for (; list; list = list_next(list))
302: list_append(&c,list_ptr(list));
303: return c;
304: }
305:
306: /****************************/
307:
308: int list_equal(list_t list1,list_t list2)
309: {
310: while (list1 && list2)
311: {
312: if (list_ptr(list1) != list_ptr(list2))
313: break;
314: list1 = list_next(list1);
315: list2 = list_next(list2);
316: }
317: return list1 == list2;
318: }
319:
320: /****************************/
321:
322: int list_cmp(list_t list1,list_t list2,int (*func)(void *,void *))
323: { int result = 0;
324:
325: while (1)
326: {
327: if (!list1)
328: { if (list2)
329: result = -1; /* list1 < list2 */
330: break;
331: }
332: if (!list2)
333: { result = 1; /* list1 > list2 */
334: break;
335: }
336: result = (*func)(list_ptr(list1),list_ptr(list2));
337: if (result)
338: break;
339: list1 = list_next(list1);
340: list2 = list_next(list2);
341: }
342: return result;
343: }
344:
345: /*****************************/
346:
347: list_t list_inlist(list_t list,void *ptr)
348: {
349: for (; list; list = list_next(list))
350: if (list_ptr(list) == ptr)
351: break;
352: return list;
353: }
354:
355: /******************************/
356:
357: list_t list_cat(list_t *pl1,list_t l2)
358: { list_t *pl;
359:
360: for (pl = pl1; *pl; pl = &list_next(*pl))
361: ;
362: *pl = l2;
363: return *pl1;
364: }
365:
366: /******************************/
367:
368: list_t list_build(void *p,...)
369: { list_t alist;
370: list_t *pe;
371: va_list ap;
372:
373: alist = NULL;
374: pe = &alist;
375: for (va_start(ap,p); p; p = va_arg(ap,void *))
376: { list_t list;
377:
378: list = list_alloc(fileline);
379: if (list)
380: { list_next(list) = NULL;
381: list_ptr(list) = p;
382: list->count = 1;
383: *pe = list;
384: pe = &list_next(list);
385: }
386: }
387: va_end(ap);
388: return alist;
389: }
390:
391: /***************************************
392: * Apply a function to each member of a list.
393: */
394:
395: void list_apply(list_t *plist,void (*fp)(void *))
warning C6244: Local declaration of 'fp' hides previous declaration at line '61' of 'c:\projects\extern\d\dmd\src\tk\mem.c'
396: {
397: list_t l;
398:
399: if (fp)
400: for (l = *plist; l; l = list_next(l))
401: {
402: (*fp)(list_ptr(l));
403: }
404: }
405:
406: /*********************************************
407: * Reverse a list.
408: */
409:
410: list_t list_reverse(list_t l)
411: { list_t r;
412: list_t ln;
413:
414: r = NULL;
415: while (l)
416: { ln = list_next(l);
417: list_next(l) = r;
418: r = l;
419: l = ln;
420: }
421: return r;
422: }
423:
424: /**********************************************
425: * Copy list of pointers into an array of pointers.
426: */
427:
428: void list_copyinto(list_t l, void *pa)
429: {
430: void **ppa = (void **)pa;
431: for (; l; l = list_next(l))
432: *(ppa)++ = list_ptr(l);
433: }
434:
435: /**********************************************
436: * Insert item into list at nth position.
437: */
438:
439: list_t list_insert(list_t *pl,void *ptr,int n)
440: {
441: list_t list;
442:
443: while (n)
444: {
445: pl = &list_next(*pl);
446: n--;
447: }
448: list = list_alloc(fileline);
449: if (list)
450: {
451: list_next(list) = *pl;
452: *pl = list;
453: list_ptr(list) = ptr;
454: list->count = 1;
455: }
456: return list;
457: }
458:
459: #ifdef __cplusplus
460: void list_free(list_t *l) { list_free(l,FPNULL); }
461: #endif
462:
463: