1 /**
2  * Interface to the C linked list type.
3  *
4  * List is a complete package of functions to deal with singly linked
5  * lists of pointers or integers.
6  * Features:
7  *      1. Uses mem package.
8  *      2. Has loop-back tests.
9  *      3. Each item in the list can have multiple predecessors, enabling
10  *         different lists to 'share' a common tail.
11  *
12  * Copyright:   Copyright (C) 1986-1990 by Northwest Software
13  *              Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved
14  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
15  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
16  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/dlist.d, backend/dlist.d)
17  */
18 
19 module dmd.backend.dlist;
20 
21 import core.stdc.stdarg;
22 import core.stdc.stdio;
23 import core.stdc.stdlib;
24 import core.stdc.string;
25 
26 extern (C++):
27 
28 nothrow:
29 @nogc
30 {
31 
32 /* **************** TYPEDEFS AND DEFINES ****************** */
33 
34 struct LIST
35 {
36         /* Do not access items in this struct directly, use the         */
37         /* functions designed for that purpose.                         */
38         LIST* next;             /* next element in list                 */
39         int count;              /* when 0, element may be deleted       */
40         union
41         {       void* ptr;      /* data pointer                         */
42                 int data;
43         }
44 }
45 
46 alias list_t = LIST*;             /* pointer to a list entry              */
47 
48 /* FPNULL is a null function pointer designed to be an argument to
49  * list_free().
50  */
51 
52 alias list_free_fp = void function(void*) @nogc nothrow;
53 
54 enum FPNULL = cast(list_free_fp)null;
55 
56 /* **************** PUBLIC VARIABLES ********************* */
57 
58 __gshared
59 {
60     int list_inited;         // != 0 if list package is initialized
61     list_t list_freelist;
62     int nlist;
63 }
64 
65 /* **************** PUBLIC FUNCTIONS ********************* */
66 
67 /********************************
68  * Create link to existing list, that is, share the list with
69  * somebody else.
70  *
71  * Returns:
72  *    pointer to that list entry.
73  */
74 
75 list_t list_link(list_t list)
76 {
77     if (list)
78         ++list.count;
79     return list;
80 }
81 
82 /********************************
83  * Returns:
84  *    pointer to next entry in list.
85  */
86 
87 list_t list_next(list_t list) { return list.next; }
88 
89 /********************************
90  * Returns:
91  *    ptr from list entry.
92  */
93 
94 inout(void)* list_ptr(inout list_t list) { return list.ptr; }
95 
96 /********************************
97  * Returns:
98  *    integer item from list entry.
99  */
100 
101 int list_data(list_t list) { return list.data; }
102 
103 /********************************
104  * Append integer item to list.
105  */
106 
107 void list_appenddata(list_t* plist, int d)
108 {
109     list_append(plist, null).data = d;
110 }
111 
112 /********************************
113  * Prepend integer item to list.
114  */
115 
116 void list_prependdata(list_t *plist,int d)
117 {
118     list_prepend(plist, null).data = d;
119 }
120 
121 /**********************
122  * Initialize list package.
123  * Output:
124  *      list_inited = 1
125  */
126 
127 void list_init()
128 {
129     if (list_inited == 0)
130     {
131         nlist = 0;
132         list_inited++;
133     }
134 }
135 
136 /*******************
137  * Terminate list package.
138  * Output:
139  *      list_inited = 0
140  */
141 
142 void list_term()
143 {
144     if (list_inited)
145     {
146         debug printf("Max # of lists = %d\n",nlist);
147         while (list_freelist)
148         {
149             list_t list = list_next(list_freelist);
150             list_delete(list_freelist);
151             list_freelist = list;
152             nlist--;
153         }
154         debug if (nlist)
155             printf("nlist = %d\n",nlist);
156         assert(nlist == 0);
157         list_inited = 0;
158     }
159 }
160 
161 
162 list_t list_alloc()
163 {
164     list_t list;
165 
166     if (list_freelist)
167     {
168         list = list_freelist;
169         list_freelist = list_next(list);
170         //mem_setnewfileline(list,file,line);
171     }
172     else
173     {
174         nlist++;
175         list = list_new();
176     }
177     return list;
178 }
179 
180 list_t list_alloc(const(char)* file, int line)
181 {
182     return list_alloc();
183 }
184 
185 
186 list_t list_new() { return cast(list_t)malloc(LIST.sizeof); }
187 void list_delete(list_t list) { free(list); }
188 
189 /********************
190  * Free list.
191  * Params:
192  *      plist =         Pointer to list to free
193  *      freeptr =       Pointer to freeing function for the data pointer
194  *                      (use FPNULL if none)
195  * Output:
196  *      *plist is null
197  */
198 
199 void list_free(list_t* plist, list_free_fp freeptr)
200 {
201     list_t list = *plist;
202     *plist = null;             // block any circular reference bugs
203     while (list && --list.count == 0)
204     {
205         list_t listnext = list_next(list);
206         if (freeptr)
207             (*freeptr)(list_ptr(list));
208         debug memset(list, 0, (*list).sizeof);
209         list.next = list_freelist;
210         list_freelist = list;
211         list = listnext;
212     }
213 }
214 
215 void list_free(list_t *l)
216 {
217      list_free(l, FPNULL);
218 }
219 
220 /***************************
221  * Remove ptr from the list pointed to by *plist.
222  * Output:
223  *      *plist is updated to be the start of the new list
224  * Returns:
225  *      null if *plist is null
226  *      otherwise ptr
227  */
228 
229 void* list_subtract(list_t* plist, void* ptr)
230 {
231     list_t list;
232 
233     while ((list = *plist) != null)
234     {
235         if (list_ptr(list) == ptr)
236         {
237             if (--list.count == 0)
238             {
239                 *plist = list_next(list);
240                 list.next = list_freelist;
241                 list_freelist = list;
242             }
243             return ptr;
244         }
245         else
246             plist = &list.next;
247     }
248     return null;            // it wasn't in the list
249 }
250 
251 /***************************
252  * Remove first element in list pointed to by *plist.
253  * Returns:
254  *      First element, null if *plist is null
255  */
256 
257 void* list_pop(list_t* plist)
258 {
259     return list_subtract(plist, list_ptr(*plist));
260 }
261 
262 /*************************
263  * Append ptr to *plist.
264  * Returns:
265  *      pointer to list item created.
266  *      null if out of memory
267  */
268 
269 list_t list_append(list_t* plist, void* ptr)
270 {
271     while (*plist)
272         plist = &(*plist).next;   // find end of list
273 
274     list_t list = list_alloc();
275     if (list)
276     {
277         *plist = list;
278         list.next = null;
279         list.ptr = ptr;
280         list.count = 1;
281     }
282     return list;
283 }
284 
285 list_t list_append_debug(list_t* plist, void* ptr, const(char)* file, int line)
286 {
287     return list_append(plist, ptr);
288 }
289 
290 /*************************
291  * Prepend ptr to *plist.
292  * Returns:
293  *      pointer to list item created (which is also the start of the list).
294  *      null if out of memory
295  */
296 
297 list_t list_prepend(list_t *plist, void *ptr)
298 {
299     list_t list = list_alloc();
300     if (list)
301     {
302         list.next = *plist;
303         list.ptr = ptr;
304         list.count = 1;
305         *plist = list;
306     }
307     return list;
308 }
309 
310 /*************************
311  * Count up and return number of items in list.
312  * Returns:
313  *      # of entries in list
314  */
315 
316 int list_nitems(list_t list)
317 {
318     int n = 0;
319     foreach (l; ListRange(list))
320     {
321         ++n;
322     }
323     return n;
324 }
325 
326 /*************************
327  * Returns:
328  *    nth list entry in list.
329  */
330 
331 list_t list_nth(list_t list, int n)
332 {
333     for (int i = 0; i < n; i++)
334     {
335         assert(list);
336         list = list_next(list);
337     }
338     return list;
339 }
340 
341 /***********************
342  * Returns:
343  *    last list entry in list.
344  */
345 
346 list_t list_last(list_t list)
347 {
348     if (list)
349         while (list_next(list))
350             list = list_next(list);
351     return list;
352 }
353 
354 /********************************
355  * Returns:
356  *    pointer to previous item in list.
357  */
358 
359 list_t list_prev(list_t start, list_t list)
360 {
361     if (start)
362     {
363         if (start == list)
364             start = null;
365         else
366             while (list_next(start) != list)
367             {
368                 start = list_next(start);
369                 assert(start);
370             }
371     }
372     return start;
373 }
374 
375 /***********************
376  * Copy a list and return it.
377  */
378 
379 list_t list_copy(list_t list)
380 {
381     list_t c = null;
382     for (; list; list = list_next(list))
383         list_append(&c,list_ptr(list));
384     return c;
385 }
386 
387 /************************
388  * Compare two lists.
389  * Returns:
390  *      If they have the same ptrs, return 1 else 0.
391  */
392 
393 int list_equal(list_t list1, list_t list2)
394 {
395     while (list1 && list2)
396     {
397         if (list_ptr(list1) != list_ptr(list2))
398             break;
399         list1 = list_next(list1);
400         list2 = list_next(list2);
401     }
402     return list1 == list2;
403 }
404 
405 /************************
406  * Compare two lists using the comparison function fp.
407  * The comparison function is the same as used for qsort().
408  * Returns:
409  *    If they compare equal, return 0 else value returned by fp.
410  */
411 
412 int list_cmp(list_t list1, list_t list2, int function(void*, void*) @nogc nothrow fp)
413 {
414     int result = 0;
415 
416     while (1)
417     {
418         if (!list1)
419         {   if (list2)
420                 result = -1;    /* list1 < list2        */
421             break;
422         }
423         if (!list2)
424         {   result = 1;         /* list1 > list2        */
425             break;
426         }
427         result = (*fp)(list_ptr(list1),list_ptr(list2));
428         if (result)
429             break;
430         list1 = list_next(list1);
431         list2 = list_next(list2);
432     }
433     return result;
434 }
435 
436 /*************************
437  * Search for ptr in list.
438  * Returns:
439  *    If found, return list entry that it is, else null.
440  */
441 
442 list_t list_inlist(list_t list, void* ptr)
443 {
444     foreach (l; ListRange(list))
445         if (l.ptr == ptr)
446             return l;
447     return null;
448 }
449 
450 /*************************
451  * Concatenate two lists (l2 appended to l1).
452  * Output:
453  *      *pl1 updated to be start of concatenated list.
454  * Returns:
455  *      *pl1
456  */
457 
458 list_t list_cat(list_t *pl1, list_t l2)
459 {
460     list_t *pl;
461     for (pl = pl1; *pl; pl = &(*pl).next)
462     { }
463     *pl = l2;
464     return *pl1;
465 }
466 
467 /***************************************
468  * Apply a function fp to each member of a list.
469  */
470 
471 void list_apply(list_t* plist, void function(void*) @nogc nothrow fp)
472 {
473     if (fp)
474         foreach (l; ListRange(*plist))
475         {
476             (*fp)(list_ptr(l));
477         }
478 }
479 
480 /********************************************
481  * Reverse a list in place.
482  */
483 
484 list_t list_reverse(list_t l)
485 {
486     list_t r = null;
487     while (l)
488     {
489         list_t ln = list_next(l);
490         l.next = r;
491         r = l;
492         l = ln;
493     }
494     return r;
495 }
496 
497 
498 /**********************************************
499  * Copy list of pointers into an array of pointers.
500  */
501 
502 void list_copyinto(list_t l, void *pa)
503 {
504     void **ppa = cast(void **)pa;
505     for (; l; l = l.next)
506     {
507         *ppa = l.ptr;
508         ++ppa;
509     }
510 }
511 
512 /**********************************************
513  * Insert item into list at nth position.
514  */
515 
516 list_t list_insert(list_t *pl,void *ptr,int n)
517 {
518     list_t list;
519 
520     while (n)
521     {
522         pl = &(*pl).next;
523         n--;
524     }
525     list = list_alloc();
526     if (list)
527     {
528         list.next = *pl;
529         *pl = list;
530         list.ptr = ptr;
531         list.count = 1;
532     }
533     return list;
534 }
535 
536 /********************************
537  * Range for Lists.
538  */
539 struct ListRange
540 {
541   pure nothrow @nogc @safe:
542 
543     this(list_t li)
544     {
545         this.li = li;
546     }
547 
548     list_t front() return  { return li; }
549     void popFront() { li = li.next; }
550     bool empty() const { return !li; }
551 
552   private:
553     list_t li;
554 }
555 
556 }
557 
558 /* The following function should be nothrow @nogc, too, but on
559  * some platforms core.stdc.stdarg is not fully nothrow @nogc.
560  */
561 
562 /*************************
563  * Build a list out of the null-terminated argument list.
564  * Returns:
565  *      generated list
566  */
567 
568 list_t list_build(void *p,...)
569 {
570     va_list ap;
571 
572     list_t alist = null;
573     list_t *pe = &alist;
574     for (va_start(ap,p); p; p = va_arg!(void*)(ap))
575     {
576         list_t list = list_alloc();
577         if (list)
578         {
579             list.next = null;
580             list.ptr = p;
581             list.count = 1;
582             *pe = list;
583             pe = &list.next;
584         }
585     }
586     va_end(ap);
587     return alist;
588 }
589 
590