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