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: