1 /**********
2 *
3 * Copyright (c) 2003, Division of Imaging Science and Biomedical Engineering,
4 * University of Manchester, UK. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without modification,
7 * are permitted provided that the following conditions are met:
8 *
9 * . Redistributions of source code must retain the above copyright notice,
10 * this list of conditions and the following disclaimer.
11 *
12 * . Redistributions in binary form must reproduce the above copyright notice,
13 * this list of conditions and the following disclaimer in the documentation
14 * and/or other materials provided with the distribution.
15 *
16 * . Neither the name of the University of Manchester nor the names of its
17 * contributors may be used to endorse or promote products derived from this
18 * software without specific prior written permission.
19 *
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
25 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
32 *
33 **********
34 *
35 * Program : TINA
36 * File : $Source: /home/tina/cvs/tina-libs/tina/sys/sysLst_dd.c,v $
37 * Date : $Date: 2008/10/02 11:53:05 $
38 * Version : $Revision: 1.8 $
39 * CVS Id : $Id: sysLst_dd.c,v 1.8 2008/10/02 11:53:05 neil Exp $
40 *
41 * Notes :
42 *
43 * List (doubly directed lists) handling.
44 * List is { int type; List *next; List *last; void *to; }
45 *
46 *********
47 */
48
49 #include "sysLst_dd.h"
50
51 #if HAVE_CONFIG_H
52 #include <config.h>
53 #endif
54
55 #include <stdio.h>
56
57 #if HAVE_STDARG_H
58 # include <stdarg.h>
59 # define VA_START(a, f) va_start(a, f)
60 #else
61 # if HAVE_VARARGS_H
62 # include <varargs.h>
63 # define VA_START(a, f) va_start(a)
64 # endif
65 #endif /* HAVE_STDARG_H */
66 #ifndef VA_START
67 error no variadic api available
68 #endif
69
70 #include <tina/sys/sys_GenDef.h>
71 #include <tina/sys/sys_LstDef.h>
72 #include <tina/sys/sys_MemDef.h>
73 #include <tina/sys/sysMem_ralloc.h>
74 #include <tina/sys/sysGen_error.h>
75
76
77 /* Allocate space and set a single list element */
78 List *dd_link_alloc(void *ptr, int type)
79 {
80 List *list;
81
82 list = ts_ralloc(List);
83 list->next = NULL;
84 list->type = type;
85 list->last = NULL;
86 list->to = ptr;
87 return (list);
88 }
89
90 void dd_ref_set(List * el, void *ptr, int type)
91 {
92 el->to = ptr;
93 el->type = type;
94 }
95
96 List *dd_list_make(int n, int type) /* make and initialize a list
97 * * of length n */
98 {
99 int i;
100 List *list = NULL;
101 List *dd_ref_addtostart(List * list, void *ptr, int type);
102
103 for (i = 0; i < n; i++)
104 list = dd_ref_addtostart(list, NULL, type);
105
106 return (list);
107 }
108
109 List *dd_get_end(List * list)
110 {
111 if (list == NULL)
112 return (NULL);
113
114 while (list->next != NULL)
115 list = list->next;
116
117 return (list);
118 }
119
120 List *dd_get_start(List * list)
121 {
122 if (list == NULL)
123 return (NULL);
124
125 while (list->last != NULL)
126 list = list->last;
127
128 return (list);
129 }
130
131 List *dd_append(List * l1, List * l2) /* append l2 to l1 */
132 {
133 List *lptr;
134
135 if (l1 == NULL)
136 return (l2);
137
138 if (l2 == NULL)
139 return (l1);
140
141 for (lptr = l1; lptr->next != NULL; lptr = lptr->next);
142
143 lptr->next = l2;
144 l2->last = lptr;
145
146 return (l1);
147 }
148
149 /* Add new element to front of list returning front of list */
150 List *dd_link_addtostart(List * list, List * el)
151 {
152 if (el == NULL)
153 return (list);
154
155 el->next = list;
156 el->last = NULL;
157 if (list != NULL)
158 list->last = el;
159 return (el);
160 }
161
162 List *dd_ref_addtostart(List * list, void *ptr, int type)
163 {
164 return (dd_link_addtostart(list, dd_link_alloc(ptr, type)));
165 }
166
167 List *dd_link_addtoend(List * end, List * el)
168 /* add new element to
169 * * back of list
170 * * returning back of
171 * * list */
172 {
173 if (el == NULL)
174 return (end);
175
176 el->next = NULL;
177 el->last = end;
178 if (end != NULL)
179 end->next = el;
180 return (el);
181 }
182
183 List *dd_ref_addtoend(List * end, void *ptr, int type)
184 {
185 return (dd_link_addtoend(end, dd_link_alloc(ptr, type)));
186 }
187
188 List *dd_list_addtoend(List * list, List * el)
189 /* add new element to
190 * * back of list
191 * * returning front of
192 * * list */
193 {
194 List *end;
195
196 if (el == NULL)
197 return (list);
198
199 end = dd_get_end(list);
200 el->next = NULL;
201 el->last = end;
202 if (list == NULL)
203 return (el);
204
205 end->next = el;
206 return (list);
207 }
208
209 void dd_link_addafter(List * at, List * el)
210 /* add new element after
211 * * at */
212 {
213 if (at == NULL || el == NULL)
214 return;
215
216 el->next = at->next;
217 at->next = el;
218 el->last = at;
219 if (el->next != NULL)
220 el->next->last = el;
221 }
222
223 void dd_link_rm_next_el(List * at) /* rm next element from list */
224 {
225 List *temp;
226
227 if (at == NULL || at->next == NULL)
228 return;
229
230 temp = at->next;
231 at->next = at->next->next;
232 if (at->next != NULL)
233 at->next->last = at;
234 rfree((void *) temp);
235 }
236
237 List *dd_link_rm_el(List * at) /* rm element returning next */
238 {
239 List *next;
240
241 if (at == NULL)
242 return (NULL);
243
244 next = at->next;
245
246 if (at->next != NULL)
247 at->next->last = at->last;
248
249 if (at->last != NULL)
250 at->last->next = at->next;
251
252 rfree((void *) at);
253 return (next);
254 }
255
256 void dd_ref_free(List * at, void (*freefunc) ( /* ??? */ )) /* free element at */
257 {
258 if (at == NULL || freefunc == NULL)
259 return;
260
261 freefunc(at->to, at->type);
262 at->to = NULL;
263 }
264
265 void dd_link_rm_next(List * at, void (*freefunc) ( /* ??? */ )) /* free and rm next
266 * * element */
267 {
268 if (at == NULL)
269 return;
270
271 dd_ref_free(at->next, freefunc);
272 (void) dd_link_rm_next_el(at);
273 }
274
275 /* Free and rm this element returning next */
276 List *dd_link_rm(List * at, void (*freefunc) ( /* ??? */ ))
277 {
278 if (at == NULL)
279 return (NULL);
280
281 dd_ref_free(at, freefunc);
282 return (dd_link_rm_el(at));
283 }
284
285 List *dd_list_rm_el(List * list, List * el, void (*freefunc) ( /* ??? */ ))
286 {
287 List *previous=NULL;
288 List *next=NULL;
289 List *ptr;
290
291 /* check sanity of list structure before freeing NAT 21/2/2007 */
292 /* assume that at least ->next data is correct and attempt fix */
293 /* too slow for general use NAT 2/7/11
294 for (ptr = list; ptr !=NULL; ptr= ptr->next)
295 {
296 next = ptr->next;
297 if (ptr == el) break;
298 previous = ptr;
299 }
300 if (el &&(el->last != previous))
301 {
302 error("dd_list_rm_el: fixing inconsistent list, DEBUG HERE (1)", non_fatal);
303 el->last = previous;
304 }
305 if (next && (next->last != el))
306 {
307 error("dd_list_rm_el: fixing inconsistent list, DEBUG HERE (2)", non_fatal);
308 next->last = el;
309 }
310 if (previous && (previous->next != el))
311 {
312 error("dd_list_rm_el: fixing inconsistent list, DEBUG HERE (3)", non_fatal);
313 previous->next = el;
314 }
315 */
316
317 if (list == NULL)
318 return (NULL);
319
320 if (el == list)
321 return (dd_link_rm(el, freefunc)); /* was memory leak NAT 7/2/2002 */
322
323 (void) dd_link_rm(el, freefunc); /* actually removes element * * from list */
324 return (list);
325 }
326
327 List *dd_link_get_by_ref(List * list, void *ptr) /* get list element by
328 * * reference */
329 {
330 List *lptr;
331
332 for (lptr = list; lptr != NULL; lptr = lptr->next)
333 if (lptr->to == ptr)
334 return (lptr);
335
336 return (NULL);
337 }
338
339 List *dd_link_get_by_type(List * list, int type) /* get next list
340 * * element of type */
341 {
342 List *lptr;
343
344 for (lptr = list; lptr != NULL; lptr = lptr->next)
345 if (lptr->type == type)
346 return (lptr);
347
348 return (NULL);
349 }
350
351 List *dd_list_rm_ref(List * list, void *ptr, void (*freefunc) ( /* ??? */ ))
352 {
353 List *el;
354
355 if (list == NULL)
356 return (NULL);
357
358 el = dd_link_get_by_ref(list, ptr);
359 if (el == NULL)
360 {
361 error("dd_list_rm_ref: structure not on list, DEBUG HERE ", non_fatal);
362
363 /* memory leak and bug... original list not returned to call function NAT 2/7/11
364 return (NULL);
365 */
366 return(list);
367 }
368 return (dd_list_rm_el(list, el, freefunc));
369 }
370
371 void dd_list_rm_links(List * list) /* remove a list */
372 {
373 while (list != NULL)
374 list = dd_link_rm_el(list);
375 }
376
377 List *dd_list_rm_links_on_type(List * list, int type)
378 {
379
380 /*mjs modified 24/7/03 - logical fault in while loop, as it could remove all elements
381 giving a null list, which is then passed into the for loop */
382 List *lptr;
383
384 while (list != NULL && list->type == type)
385 list = dd_link_rm_el(list);
386
387 if (list == NULL)
388 return(list);
389
390 if (list == NULL)
391 return NULL;
392
393 for (lptr = list->next; lptr != NULL;)
394 if (lptr->type == type)
395 lptr = dd_link_rm_el(lptr); /* bug found NAT 7/02/2002 */
396 else
397 lptr = lptr->next;
398
399 /*list = dd_get_start(lptr);*/
400
401 return (list);
402 }
403
404 List *dd_list_rm_links_on_func(List * list, Bool(*func) ( /* ??? */ ),
405 void *data)
406 {
407 List *lptr;
408
409 while (list != NULL && func(list->to, list->type, data) == true)
410 list = dd_link_rm_el(list);
411
412 if (list == NULL) return(NULL);
413
414 for (lptr = list->next; lptr != NULL;)
415 if (func(lptr->to, lptr->type, data) == true)
416 lptr = dd_link_rm_el(lptr);
417 else
418 lptr = lptr->next;
419
420 return (list);
421 }
422
423 void dd_list_free_refs(List * list, void (*freefunc) ( /* ??? */ ))
424 /* free the elements of a list */
425 {
426 List *lptr;
427
428 for (lptr = list; lptr != NULL; lptr = lptr->next)
429 dd_ref_free(lptr, freefunc);
430 }
431
432 /* Free and rm the elements of a list */
433 void dd_list_rm(List * list, void (*freefunc) ( /* ??? */ ))
434 {
435 while (list != NULL)
436 list = dd_link_rm(list, freefunc);
437 }
438
439 List *dd_link_copy(List * el, void *(*cpfunc) ( /* ??? */ ), void *data)
440 {
441 void *cpy;
442
443 if (cpfunc == NULL)
444 return (dd_link_alloc(el->to, el->type));
445 cpy = cpfunc(el->to, el->type, data);
446 return ((cpy == NULL) ? NULL : dd_link_alloc(cpy, el->type));
447 }
448
449 List *dd_list_copy(List * list, void *(*cpfunc) ( /* ??? */ ), void *data) /* copy a whole list */
450 {
451 List *copy;
452 List *end;
453 List *lptr;
454
455 copy = NULL;
456
457 if (list == NULL)
458 return (NULL);
459
460 for (end = NULL, lptr = list; end == NULL && lptr != NULL;
461 lptr = lptr->next)
462 end = copy = dd_link_copy((List *) lptr, cpfunc, data); /* bug found NAT 7/02/2002 */
463
464 for (; lptr != NULL; lptr = lptr->next)
465 end = dd_link_addtoend(end, dd_link_copy((List *) lptr, cpfunc, data));
466 return (copy);
467 }
468
469 List *dd_list_reverse(List * list) /* reverse a list without
470 * * copying it */
471 {
472 List *rev = NULL;
473
474 while (list)
475 {
476 List *next;
477
478 next = list->next;
479 rev = dd_link_addtostart(rev, list);
480 list = next;
481 }
482 return (rev);
483 }
484
485 List *dd_list_reversecopy(List * list, void *(*cpfunc) ( /* ??? */ ), void *data)
486 /* bug found in prototype NAT 7/2/2202 */
487 {
488 List *rev = NULL;
489 List *lptr;
490
491 for (lptr = list; lptr != NULL; lptr = lptr->next)
492 rev = dd_link_addtostart(rev, dd_link_copy((List *) lptr->to,
493 (void *(*)()) cpfunc, data));
494
495 return (rev);
496 }
497
498 void dd_apply_func(List * list, void (*func) ( /* ??? */ ), void *data)
499 {
500 List *lptr;
501
502 for (lptr = list; lptr != NULL; lptr = lptr->next)
503 func(lptr->to, lptr->type, data);
504 }
505
506 List *dd_get_min(List * list, Bool(*func) ( /* ??? */ ), void *data)
507 {
508 List *lptr;
509 List *min_ptr = NULL;
510 double min_d = 0.0;
511 double d;
512
513 for (lptr = list; lptr != NULL; lptr = lptr->next)
514 {
515 if (func(lptr->to, lptr->type, data, &d) == true &&
516 (min_ptr == NULL || d < min_d))
517 {
518 min_ptr = lptr;
519 min_d = d;
520 }
521 }
522 return (min_ptr);
523 }
524
525 List *dd_list_add_sorted(List * list, List * el,
526 double (*sortfunc) ( /* ??? */ ))
527 {
528 double val;
529 List *lptr;
530
531 if (el == NULL)
532 return (list);
533 if (list == NULL)
534 {
535 el->next = NULL;
536 return (el);
537 }
538 val = sortfunc(el->to, el->type);
539
540 if (val < sortfunc(list->to, list->type))
541 return (dd_link_addtostart(list, el));
542
543 for (lptr = list; lptr->next != NULL; lptr = lptr->next)
544 if (val < sortfunc(lptr->next->to, lptr->next->type))
545 break;
546
547 dd_link_addafter(lptr, el);
548 return (list);
549 }
550
551 List *dd_nth_el(List * list, int n)
552 {
553 int i;
554
555 for (i = 0; i < n; ++i, list = list->next)
556 if (list == NULL)
557 return (NULL);
558
559 return (list);
560 }
561
562 void *dd_list_query(List * list, void *(*match_func) ( /* ??? */ ),
563 void *key)
564 {
565 void *data;
566
567 for (data = NULL;
568 list && !(data = match_func(key, list->to)); list = list->next);
569
570 return data;
571 }
572
573 List
574 #if HAVE_STDARG_H
575 *dd_list_of(int type, ...)
576 #else
577 *dd_list_of(type, va_alist)
578 int type;
579 va_dcl
580 #endif /* HAVE_STDARG_H */
581 {
582 /* old code NAT 7/2/2002
583 va_list ap;
584 List *list = NULL;
585
586 va_start(ap, ptr);
587
588 while (ptr)
589 {
590 int type = va_arg(ap, int);
591
592 list = dd_ref_addtostart(list, ptr, type);
593 ptr = va_arg(ap, void *);
594
595 }
596 va_end(ap);
597 return (dd_list_reverse(list));
598 */
599 va_list ap;
600 List *list = NULL;
601
602 VA_START(ap, type);
603
604 while (type)
605 {
606 void *ptr = va_arg(ap, void *);
607
608 list = dd_ref_addtostart(list, ptr, type);
609 type = va_arg(ap, int);
610 }
611 va_end(ap);
612 return (dd_list_reverse(list));
613 }
614
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.