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-2020 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 struct LIST
32 {
33         /* Do not access items in this struct directly, use the         */
34         /* functions designed for that purpose.                         */
35         LIST* next;             /* next element in list                 */
36         int count;              /* when 0, element may be deleted       */
37         union
38         {       void* ptr;      /* data pointer                         */
39                 int data;
40         }
41 }
42 
43 alias list_t = LIST*;             /* pointer to a list entry              */
44 
45 /* FPNULL is a null function pointer designed to be an argument to
46  * list_free().
47  */
48 
49 alias list_free_fp = void function(void*) @nogc nothrow;
50 
51 enum FPNULL = cast(list_free_fp)null;
52 
53 private __gshared list_t list_freelist;
54 
55 /* **************** PUBLIC FUNCTIONS ********************* */
56 
57 /********************************
58  * Returns:
59  *    pointer to next entry in list.
60  */
61 
62 list_t list_next(list_t list) { return list.next; }
63 
64 /********************************
65  * Returns:
66  *    ptr from list entry.
67  */
68 
69 inout(void)* list_ptr(inout list_t list) { return list.ptr; }
70 
71 /********************************
72  * Returns:
73  *    integer item from list entry.
74  */
75 
76 int list_data(list_t list) { return list.data; }
77 
78 /********************************
79  * Prepend integer item to list.
80  */
81 
82 void list_prependdata(list_t *plist,int d)
83 {
84     list_prepend(plist, null).data = d;
85 }
86 
87 list_t list_alloc()
88 {
89     list_t list;
90 
91     if (list_freelist)
92     {
93         list = list_freelist;
94         list_freelist = list_next(list);
95         //mem_setnewfileline(list,file,line);
96     }
97     else
98     {
99         list = list_new();
100     }
101     return list;
102 }
103 
104 list_t list_new() { return cast(list_t)malloc(LIST.sizeof); }
105 void list_delete(list_t list) { free(list); }
106 
107 /********************
108  * Free list.
109  * Params:
110  *      plist =         Pointer to list to free
111  *      freeptr =       Pointer to freeing function for the data pointer
112  *                      (use FPNULL if none)
113  * Output:
114  *      *plist is null
115  */
116 
117 void list_free(list_t* plist, list_free_fp freeptr)
118 {
119     list_t list = *plist;
120     *plist = null;             // block any circular reference bugs
121     while (list && --list.count == 0)
122     {
123         list_t listnext = list_next(list);
124         if (freeptr)
125             (*freeptr)(list_ptr(list));
126         debug memset(list, 0, (*list).sizeof);
127         list.next = list_freelist;
128         list_freelist = list;
129         list = listnext;
130     }
131 }
132 
133 void list_free(list_t *l)
134 {
135      list_free(l, FPNULL);
136 }
137 
138 /***************************
139  * Remove ptr from the list pointed to by *plist.
140  * Output:
141  *      *plist is updated to be the start of the new list
142  * Returns:
143  *      null if *plist is null
144  *      otherwise ptr
145  */
146 
147 void* list_subtract(list_t* plist, void* ptr)
148 {
149     list_t list;
150 
151     while ((list = *plist) != null)
152     {
153         if (list_ptr(list) == ptr)
154         {
155             if (--list.count == 0)
156             {
157                 *plist = list_next(list);
158                 list.next = list_freelist;
159                 list_freelist = list;
160             }
161             return ptr;
162         }
163         else
164             plist = &list.next;
165     }
166     return null;            // it wasn't in the list
167 }
168 
169 /***************************
170  * Remove first element in list pointed to by *plist.
171  * Returns:
172  *      First element, null if *plist is null
173  */
174 
175 void* list_pop(list_t* plist)
176 {
177     return list_subtract(plist, list_ptr(*plist));
178 }
179 
180 /*************************
181  * Append ptr to *plist.
182  * Returns:
183  *      pointer to list item created.
184  *      null if out of memory
185  */
186 
187 list_t list_append(list_t* plist, void* ptr)
188 {
189     while (*plist)
190         plist = &(*plist).next;   // find end of list
191 
192     list_t list = list_alloc();
193     if (list)
194     {
195         *plist = list;
196         list.next = null;
197         list.ptr = ptr;
198         list.count = 1;
199     }
200     return list;
201 }
202 
203 /*************************
204  * Prepend ptr to *plist.
205  * Returns:
206  *      pointer to list item created (which is also the start of the list).
207  *      null if out of memory
208  */
209 
210 list_t list_prepend(list_t *plist, void *ptr)
211 {
212     list_t list = list_alloc();
213     if (list)
214     {
215         list.next = *plist;
216         list.ptr = ptr;
217         list.count = 1;
218         *plist = list;
219     }
220     return list;
221 }
222 
223 /*************************
224  * Count up and return number of items in list.
225  * Returns:
226  *      # of entries in list
227  */
228 
229 int list_nitems(list_t list)
230 {
231     int n = 0;
232     foreach (l; ListRange(list))
233     {
234         ++n;
235     }
236     return n;
237 }
238 
239 /*************************
240  * Returns:
241  *    nth list entry in list.
242  */
243 
244 list_t list_nth(list_t list, int n)
245 {
246     for (int i = 0; i < n; i++)
247     {
248         assert(list);
249         list = list_next(list);
250     }
251     return list;
252 }
253 
254 /************************
255  * Compare two lists.
256  * Returns:
257  *      If they have the same ptrs, return 1 else 0.
258  */
259 
260 int list_equal(list_t list1, list_t list2)
261 {
262     while (list1 && list2)
263     {
264         if (list_ptr(list1) != list_ptr(list2))
265             break;
266         list1 = list_next(list1);
267         list2 = list_next(list2);
268     }
269     return list1 == list2;
270 }
271 
272 /*************************
273  * Search for ptr in list.
274  * Returns:
275  *    If found, return list entry that it is, else null.
276  */
277 
278 list_t list_inlist(list_t list, void* ptr)
279 {
280     foreach (l; ListRange(list))
281         if (l.ptr == ptr)
282             return l;
283     return null;
284 }
285 
286 /***************************************
287  * Apply a function fp to each member of a list.
288  */
289 
290 void list_apply(list_t* plist, void function(void*) @nogc nothrow fp)
291 {
292     if (fp)
293         foreach (l; ListRange(*plist))
294         {
295             (*fp)(list_ptr(l));
296         }
297 }
298 
299 /********************************************
300  * Reverse a list in place.
301  */
302 
303 list_t list_reverse(list_t l)
304 {
305     list_t r = null;
306     while (l)
307     {
308         list_t ln = list_next(l);
309         l.next = r;
310         r = l;
311         l = ln;
312     }
313     return r;
314 }
315 
316 /********************************
317  * Range for Lists.
318  */
319 struct ListRange
320 {
321   pure nothrow @nogc @safe:
322 
323     this(list_t li)
324     {
325         this.li = li;
326     }
327 
328     list_t front() return  { return li; }
329     void popFront() { li = li.next; }
330     bool empty() const { return !li; }
331 
332   private:
333     list_t li;
334 }