1 static char rcsid[] = "$Id: list.c 220326 2019-09-12 20:40:15Z twu $";
2 #ifdef HAVE_CONFIG_H
3 #include <config.h>
4 #endif
5
6 #include "list.h"
7 #include <stdio.h>
8 #include <stdlib.h>
9 #include <string.h>
10 #include "mem.h"
11
12 #define T List_T
13
14 #if !defined(HAVE_INLINE)
15 T
List_push(T list,void * x)16 List_push (T list, void *x) {
17 T new = (T) MALLOC(sizeof(*new));
18
19 new->first = x;
20 new->rest = list;
21 return new;
22 }
23
24 T
List_pop(T list,void ** x)25 List_pop (T list, void **x) {
26 T head;
27
28 if (list) {
29 head = list->rest;
30 *x = list->first;
31 FREE(list);
32 return head;
33 } else {
34 return list;
35 }
36 }
37
38 void *
List_head(T list)39 List_head (T list) {
40 return list->first;
41 }
42
43 T
List_next(T list)44 List_next (T list) {
45 if (list) {
46 return list->rest;
47 } else {
48 return NULL;
49 }
50 }
51
52 void
List_free(T * list)53 List_free (T *list) {
54 T prev;
55
56 while ((prev = *list) != NULL) {
57 *list = prev->rest;
58 FREE(prev);
59 }
60
61 return;
62 }
63
64 int
List_length(T list)65 List_length (T list) {
66 int n;
67
68 for (n = 0; list; list = list->rest) {
69 n++;
70 }
71
72 return n;
73 }
74
75 T
List_reverse(T list)76 List_reverse (T list) {
77 T head = NULL, next;
78
79 for ( ; list; list = next) {
80 next = list->rest;
81 list->rest = head;
82 head = list;
83 }
84 return head;
85 }
86
87 T
List_transfer_one(T dest,T * source)88 List_transfer_one (T dest, T *source) {
89 T next;
90
91 next = (*source)->rest;
92 (*source)->rest = dest;
93 dest = *source;
94 *source = next;
95 return dest;
96 }
97 #endif
98
99
100 T
List_push_keep(T list,void * x)101 List_push_keep (T list, void *x) {
102 T new = (T) MALLOC_KEEP(sizeof(*new));
103
104 new->first = x;
105 new->rest = list;
106 return new;
107 }
108
109 T
List_push_out(T list,void * x)110 List_push_out (T list, void *x) {
111 T new = (T) MALLOC_OUT(sizeof(*new));
112
113 new->first = x;
114 new->rest = list;
115 return new;
116 }
117
118 T
List_pop_out(T list,void ** x)119 List_pop_out (T list, void **x) {
120 T head;
121
122 if (list) {
123 head = list->rest;
124 *x = list->first;
125 FREE_OUT(list);
126 return head;
127 } else {
128 return list;
129 }
130 }
131
132 void
List_head_set(T this,void * x)133 List_head_set (T this, void *x) {
134 this->first = x;
135 return;
136 }
137
138 void
List_tail_set(T this,T rest)139 List_tail_set (T this, T rest) {
140 this->rest = rest;
141 return;
142 }
143
144 void
List_free_keep(T * list)145 List_free_keep (T *list) {
146 T prev;
147
148 while ((prev = *list) != NULL) {
149 *list = (*list)->rest;
150 FREE_KEEP(prev);
151 }
152 }
153
154 void
List_free_out(T * list)155 List_free_out (T *list) {
156 T prev;
157
158 while ((prev = *list) != NULL) {
159 *list = (*list)->rest;
160 FREE_OUT(prev);
161 }
162 }
163
164 T
List_truncate(T list,int n)165 List_truncate (T list, int n) {
166 T head = list;
167
168 while (--n > 0) {
169 list = list->rest;
170 }
171 if (list) {
172 list->rest = (T) NULL;
173 }
174 return head;
175 }
176
177 void **
List_to_array(T list,void * end)178 List_to_array (T list, void *end) {
179 void **array;
180 int i, n = List_length(list);
181
182 #if 0
183 if (n == 0) {
184 return (void *) NULL;
185 } else {
186 #endif
187 array = (void **) MALLOC((n+1)*sizeof(*array));
188 for (i = 0; i < n; i++) {
189 array[i] = list->first;
190 list = list->rest;
191 }
192 array[i] = end;
193 return array;
194 #if 0
195 }
196 #endif
197 }
198
199 void
List_fill_array(void ** array,T list)200 List_fill_array (void **array, T list) {
201 int i = 0;
202
203 while (list) {
204 array[i++] = list->first;
205 list = list->rest;
206 }
207 return;
208 }
209
210 void
List_fill_array_and_free(void ** array,T * list)211 List_fill_array_and_free (void **array, T *list) {
212 T prev;
213 int i = 0;
214
215 while ((prev = *list) != NULL) {
216 array[i++] = prev->first;
217 *list = prev->rest;
218 FREE(prev);
219 }
220
221 return;
222 }
223
224 T
List_fill_array_with_handle(struct T * new,void ** array,int nelts)225 List_fill_array_with_handle (struct T *new, void **array, int nelts) {
226 T list = NULL;
227 int i;
228
229 for (i = nelts; i > 0; i--) {
230 new[i].first = array[i-1];
231 new[i].rest = list;
232 list = &(new[i]);
233 }
234
235 /* Add initial list element as a handle */
236 new[0].first = (void *) NULL;
237 new[0].rest = list;
238
239 return &(new[0]);
240 }
241
242
243 void **
List_to_array_out(T list,void * end)244 List_to_array_out (T list, void *end) {
245 void **array;
246 int i, n = List_length(list);
247
248 #if 0
249 if (n == 0) {
250 return (void *) NULL;
251 } else {
252 #endif
253 array = (void **) MALLOC_OUT((n+1)*sizeof(*array));
254 for (i = 0; i < n; i++) {
255 array[i] = list->first;
256 list = list->rest;
257 }
258 array[i] = end;
259 return array;
260 #if 0
261 }
262 #endif
263 }
264
265 void **
List_to_array_n(int * n,T list)266 List_to_array_n (int *n, T list) {
267 void **array;
268 int i;
269
270 *n = List_length(list);
271 if (*n == 0) {
272 return NULL;
273 } else {
274 array = (void **) MALLOC((*n)*sizeof(*array));
275 for (i = 0; i < *n; i++) {
276 array[i] = list->first;
277 list = list->rest;
278 }
279 return array;
280 }
281 }
282
283 void **
List_to_array_out_n(int * n,T list)284 List_to_array_out_n (int *n, T list) {
285 void **array;
286 int i;
287
288 *n = List_length(list);
289 if (*n == 0) {
290 return NULL;
291 } else {
292 array = (void **) MALLOC((*n)*sizeof(*array));
293 for (i = 0; i < *n; i++) {
294 array[i] = list->first;
295 list = list->rest;
296 }
297 return array;
298 }
299 }
300
301 T
List_copy(T list)302 List_copy (T list) {
303 T head, *p = &head;
304
305 for ( ; list; list = list->rest) {
306 *p = (T) MALLOC(sizeof(**p));
307 (*p)->first = list->first;
308 p = &(*p)->rest;
309 }
310 *p = NULL;
311 return head;
312 }
313
314 void
List_dump(T list)315 List_dump (T list) {
316 while (list) {
317 printf("%p\n",list);
318 list = list->rest;
319 }
320 return;
321 }
322
323 T
List_append(T list,T tail)324 List_append (T list, T tail) {
325 T *p = &list;
326
327 while (*p) {
328 p = &(*p)->rest;
329 }
330 *p = tail;
331 return list;
332 }
333
334
335 T
List_drop_last(T list,void ** x)336 List_drop_last (T list, void **x) {
337 T *p = &list;
338
339 while ((*p)->rest) {
340 p = &(*p)->rest;
341 }
342 *x = (*p)->first;
343 /* FREE(*p); */
344 *p = NULL;
345
346 return list;
347 }
348
349 void
List_last_set(T list,void * x)350 List_last_set (T list, void *x) {
351 T *p = &list;
352
353 while ((*p)->rest) {
354 p = &(*p)->rest;
355 }
356 (*p)->first = x;
357
358 return;
359 }
360
361
362 void *
List_last_value(T this)363 List_last_value (T this) {
364 T last = NULL, r;
365
366 for (r = this; r != NULL; r = r->rest) {
367 last = r;
368 }
369 return last->first;
370 }
371
372 T
List_last_item(T this)373 List_last_item (T this) {
374 T last = NULL, r;
375
376 for (r = this; r != NULL; r = r->rest) {
377 last = r;
378 }
379 return last;
380 }
381
382 void *
List_index(T this,int index)383 List_index (T this, int index) {
384 while (index-- > 0) {
385 this = this->rest;
386 }
387 return this->first;
388 }
389
390
391 #if 0
392 /* Old definition, which doesn't make sense */
393 void
394 List_insert (T *listptr, void *x) {
395 T new = (T) MALLOC(sizeof(*new));
396
397 new->first = x;
398 new->rest = *listptr;
399 *listptr = new;
400
401 return;
402 }
403 #else
404 T
List_insert(T p,void * x)405 List_insert (T p, void *x) {
406 T new = (T) MALLOC(sizeof(*new));
407
408 new->first = x;
409 new->rest = p->rest;
410 p->rest = new;
411 return new;
412 }
413 #endif
414
415 void
List_reinsert(T * listptr,T cell)416 List_reinsert (T *listptr, T cell) {
417 cell->rest = *listptr;
418 *listptr = cell;
419
420 return;
421 }
422
423 T
List_push_existing(T dest,T source)424 List_push_existing (T dest, T source) {
425 source->rest = dest;
426 return source;
427 }
428
429 T
List_from_string(char * string)430 List_from_string (char *string) {
431 T this = NULL;
432 char *p = string, *scout = string, *substring;
433 int substringlen;
434
435 while (*++scout != '\0') {
436 if (*scout == ',') {
437 substringlen = (scout-p)/sizeof(char);
438 substring = (char *) MALLOC((substringlen+1)*sizeof(char));
439 strncpy(substring,p,substringlen);
440 substring[substringlen] = '\0';
441 this = List_push(this,substring);
442 scout++;
443 p = scout;
444 }
445 }
446
447 substringlen = (scout-p)/sizeof(char);
448 substring = (char *) MALLOC((substringlen+1)*sizeof(char));
449 strncpy(substring,p,substringlen);
450 substring[substringlen] = '\0';
451 this = List_push(this,substring);
452
453 return List_reverse(this);
454 }
455