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 }