~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina4/src/sys/lists/ddlists.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**@(#)List (doubly directed lists) handling.
  2  * @(#)List is { int type; List *next; List *last; void *to; }
  3  */
  4 #include <tina/sys.h>
  5 #include <tina/sysfuncs.h>
  6 
  7 /* Allocate space and set a single list element */
  8 List *dd_link_alloc(void *ptr, int type)
  9 {
 10     List *list;
 11 
 12     list = ts_ralloc(List);
 13     list->next = NULL;
 14     list->type = type;
 15     list->last = NULL;
 16     list->to = ptr;
 17     return (list);
 18 }
 19 
 20 void    dd_ref_set(List * el, void *ptr, int type)
 21 {
 22     el->to = ptr;
 23     el->type = type;
 24 }
 25 
 26 List *dd_list_make(int n, int type)     /* make and initialize a list
 27                                          * of length n */
 28 
 29 
 30 {
 31     int     i;
 32     List *list = NULL;
 33     List *dd_ref_addtostart(List * list, void *ptr, int type);
 34 
 35     for (i = 0; i < n; i++)
 36         list = dd_ref_addtostart(list, NULL, type);
 37 
 38     return (list);
 39 }
 40 
 41 List *dd_get_end(List * list)
 42 {
 43     if (list == NULL)
 44         return (NULL);
 45 
 46     while (list->next != NULL)
 47         list = list->next;
 48 
 49     return (list);
 50 }
 51 
 52 List *dd_get_start(List * list)
 53 {
 54     if (list == NULL)
 55         return (NULL);
 56 
 57     while (list->last != NULL)
 58         list = list->last;
 59 
 60     return (list);
 61 }
 62 
 63 List *dd_append(List * l1, List * l2)   /* append l2 to l1 */
 64 
 65 {
 66     List *lptr;
 67 
 68     if (l1 == NULL)
 69         return (l2);
 70 
 71     if (l2 == NULL)
 72         return (l1);
 73 
 74     for (lptr = l1; lptr->next != NULL; lptr = lptr->next);
 75 
 76     lptr->next = l2;
 77     l2->last = lptr;
 78 
 79     return (l1);
 80 }
 81 
 82 /* Add new element to front of list returning front of list */
 83 List *dd_link_addtostart(List * list, List * el)
 84 {
 85     if (el == NULL)
 86         return (list);
 87 
 88     el->next = list;
 89     el->last = NULL;
 90     if (list != NULL)
 91         list->last = el;
 92     return (el);
 93 }
 94 
 95 List *dd_ref_addtostart(List * list, void *ptr, int type)
 96 {
 97     return (dd_link_addtostart(list, dd_link_alloc(ptr, type)));
 98 }
 99 
100 List *dd_link_addtoend(List * end, List * el)   /* add new element to
101                                                          * back of list
102                                                          * returning back of
103                                                          * list */
104 
105 
106 {
107     if (el == NULL)
108         return (end);
109 
110     el->next = NULL;
111     el->last = end;
112     if (end != NULL)
113         end->next = el;
114     return (el);
115 }
116 
117 List *dd_ref_addtoend(List * end, void *ptr, int type)
118 {
119     return (dd_link_addtoend(end, dd_link_alloc(ptr, type)));
120 }
121 
122 List *dd_list_addtoend(List * list, List * el)  /* add new element to
123                                          * back of list
124                                          * returning front of
125                                          * list */
126 {
127     List *end;
128 
129     if (el == NULL)
130         return (list);
131 
132     end = dd_get_end(list);
133     el->next = NULL;
134     el->last = end;
135     if (list == NULL)
136         return (el);
137 
138     end->next = el;
139     return (list);
140 }
141 
142 void    dd_link_addafter(List * at, List * el)  /* add new element after
143                                                          * at */
144 
145 
146 {
147     if (at == NULL || el == NULL)
148         return;
149 
150     el->next = at->next;
151     at->next = el;
152     el->last = at;
153     if (el->next != NULL)
154         el->next->last = el;
155 }
156 
157 void    dd_link_rm_next_el(List * at)   /* rm next element from list */
158 
159 {
160     List *temp;
161 
162     if (at == NULL || at->next == NULL)
163         return;
164 
165     temp = at->next;
166     at->next = at->next->next;
167     if (at->next != NULL)
168         at->next->last = at;
169     rfree((void *) temp);
170 }
171 
172 List *dd_link_rm_el(List * at)  /* rm element returning next */
173 
174 {
175     List *next;
176 
177     if (at == NULL)
178         return (NULL);
179 
180     next = at->next;
181 
182     if (at->next != NULL)
183         at->next->last = at->last;
184 
185     if (at->last != NULL)
186         at->last->next = at->next;
187 
188     rfree((void *) at);
189     return (next);
190 }
191 
192 void    dd_ref_free(List * at, void (*freefunc) ( /* ??? */ ))  /* free element at */
193 
194 
195 {
196     if (at == NULL || freefunc == NULL)
197         return;
198 
199     freefunc(at->to, at->type);
200     at->to = NULL;
201 }
202 
203 void    dd_link_rm_next(List * at, void (*freefunc) ( /* ??? */ ))      /* free and rm next
204                                                                          * element */
205 
206 
207 {
208     if (at == NULL)
209         return;
210 
211     dd_ref_free(at->next, freefunc);
212     (void) dd_link_rm_next_el(at);
213 }
214 
215 /* Free and rm this element returning next */
216 List *dd_link_rm(List * at, void (*freefunc) ( /* ??? */ ))
217 {
218     if (at == NULL)
219         return (NULL);
220 
221     dd_ref_free(at, freefunc);
222     return (dd_link_rm_el(at));
223 }
224 
225 List *dd_list_rm_el(List * list, List * el, void (*freefunc) ( /* ??? */ ))
226 {
227     if (list == NULL)
228         return (NULL);
229 
230     if (el == list)
231         return (dd_link_rm(el,freefunc)); /* was memory leak NAT 7/2/2002 */
232 
233     (void) dd_link_rm(el, freefunc);    /* actually removes element
234                                          * from list */
235     return (list);
236 }
237 
238 List *dd_link_get_by_ref(List * list, void *ptr)        /* get list element by
239                                                          * reference */
240 {
241     List *lptr;
242 
243     for (lptr = list; lptr != NULL; lptr = lptr->next)
244         if (lptr->to == ptr)
245             return (lptr);
246 
247     return (NULL);
248 }
249 
250 List *dd_link_get_by_type(List * list, int type)        /* get next list
251                                                          * element of type */
252 
253 
254 {
255     List *lptr;
256 
257     for (lptr = list; lptr != NULL; lptr = lptr->next)
258         if (lptr->type == type)
259             return (lptr);
260 
261     return (NULL);
262 }
263 
264 List *dd_list_rm_ref(List * list, void *ptr, void (*freefunc) ( /* ??? */ ))
265 {
266     List *el;
267 
268     if (list == NULL)
269         return (NULL);
270 
271     el = dd_link_get_by_ref(list, ptr);
272     if (el == NULL)
273         return (NULL);
274     return (dd_list_rm_el(list, el, freefunc));
275 }
276 
277 void    dd_list_rm_links(List * list)   /* remove a list */
278 
279 {
280     while (list != NULL)
281         list = dd_link_rm_el(list);
282 }
283 
284 List *dd_list_rm_links_on_type(List * list, int type)
285 {
286     List *lptr;
287 
288     while (list != NULL && list->type == type)
289         list = dd_link_rm_el(list);
290 
291     for (lptr = list->next; lptr != NULL;)
292         if (lptr->type == type)
293             lptr = dd_link_rm_el(lptr); /* bug found NAT 7/02/2002 */
294         else
295             lptr = lptr->next;
296 
297     return (list);
298 }
299 
300 List *dd_list_rm_links_on_func(List * list, Bool(*func) ( /* ??? */ ), 
301                                void *data)
302 {
303     List *lptr;
304 
305     while (list != NULL && func(list->to, list->type, data) == true)
306         list = dd_link_rm_el(list);
307 
308     for (lptr = list->next; lptr != NULL;)
309         if (func(lptr->to, lptr->type, data) == true)
310             lptr = dd_link_rm_el(lptr);
311         else
312             lptr = lptr->next;
313 
314     return (list);
315 }
316 
317 void    dd_list_free_refs(List * list, void (*freefunc) ( /* ??? */ ))
318 /* free the elements of  a list */
319 {
320     List *lptr;
321 
322     for (lptr = list; lptr != NULL; lptr = lptr->next)
323         dd_ref_free(lptr, freefunc);
324 }
325 
326 /* Free and rm the elements of a list */
327 void    dd_list_rm(List * list, void (*freefunc) ( /* ??? */ ))
328 {
329     while (list != NULL)
330         list = dd_link_rm(list, freefunc);
331 }
332 
333 List *dd_link_copy(List * el, void *(*cpfunc) ( /* ??? */ ), void *data)
334 {
335     void   *cpy;
336 
337     if (cpfunc == NULL)
338         return (dd_link_alloc(el->to, el->type));
339     cpy = cpfunc(el->to, el->type, data);
340     return ((cpy == NULL) ? NULL : dd_link_alloc(cpy, el->type));
341 }
342 
343 List *dd_list_copy(List * list, void *(*cpfunc) ( /* ??? */ ), void *data)      /* copy a whole list */
344 {
345     List *copy;
346     List *end;
347     List *lptr;
348 
349     if (list == NULL)
350         return (NULL);
351 
352     for (end = NULL, lptr = list; end == NULL && lptr != NULL; lptr = lptr->next)
353         end = copy = dd_link_copy((List *) lptr, cpfunc, data); /* bug found NAT 7/02/2002 */
354 
355     for (; lptr != NULL; lptr = lptr->next)
356         end = dd_link_addtoend(end, dd_link_copy((List *) lptr, cpfunc, data));
357     return (copy);
358 }
359 
360 List *dd_list_reverse(List * list)      /* reverse a list without
361                                          * copying it */
362 
363 {
364     List *rev = NULL;
365 
366     while (list)
367     {
368         List *next;
369 
370         next = list->next;
371         rev = dd_link_addtostart(rev, list);
372         list = next;
373     }
374     return (rev);
375 }
376 
377 List *dd_list_reversecopy(List * list, void *(*cpfunc) ( /* ??? */ ), void *data)
378 /* bug found in prototype NAT 7/2/2202 */
379 {
380     List *rev = NULL;
381     List *lptr;
382 
383     for (lptr = list; lptr != NULL; lptr = lptr->next)
384         rev = dd_link_addtostart(rev, dd_link_copy((List *) lptr->to,
385                                         (void *(*) ()) cpfunc, data));
386 
387     return (rev);
388 }
389 
390 void    dd_apply_func(List * list, void (*func) ( /* ??? */ ), void *data)
391 {
392     List *lptr;
393 
394     for (lptr = list; lptr != NULL; lptr = lptr->next)
395         func(lptr->to, lptr->type, data);
396 }
397 
398 List *dd_get_min(List * list, Bool(*func) ( /* ??? */ ), void *data)
399 {
400     List *lptr;
401     List *min_ptr = NULL;
402     double  min_d = 0.0;
403     double  d;
404 
405     for (lptr = list; lptr != NULL; lptr = lptr->next)
406     {
407         if (func(lptr->to, lptr->type, data, &d) == true &&
408             (min_ptr == NULL || d < min_d))
409         {
410             min_ptr = lptr;
411             min_d = d;
412         }
413     }
414     return (min_ptr);
415 }
416 
417 List   *dd_list_add_sorted(List * list, List * el, double (*sortfunc) ( /* ??? */ ))
418 {
419     double   val;
420     List   *lptr;
421 
422     if (el == NULL)
423         return (list);
424     if (list == NULL)
425     {
426         el->next = NULL;
427         return (el);
428     }
429     val = sortfunc(el->to, el->type);
430 
431     if (val < sortfunc(list->to, list->type))
432         return (dd_link_addtostart(list, el));
433 
434     for (lptr = list; lptr->next != NULL; lptr = lptr->next)
435         if (val < sortfunc(lptr->next->to, lptr->next->type))
436             break;
437 
438     dd_link_addafter(lptr, el);
439     return (list);
440 }
441 
442 List *dd_nth_el(List * list, int n)
443 {
444     int     i;
445 
446     for (i = 0; i < n; ++i, list = list->next)
447         if (list == NULL)
448             return (NULL);
449 
450     return (list);
451 }
452 
453 void *dd_list_query(List * list, void *(*match_func) ( /* ??? */ ), void *key)
454 {
455     void   *data;
456 
457     for (data = NULL;
458          list && !(data = match_func(key, list->to));
459          list = list->next);
460 
461     return data;
462 }
463 
464 #ifndef ANSIFYING
465 #ifdef __STRICT_ANSI__
466 
467 
468 List *dd_list_of(int type,...)
469 {
470 /* old code NAT 7/2/2002
471     va_list ap;
472     List *list = NULL;
473 
474     va_start(ap, ptr);
475 
476     while (ptr)
477     {
478         int     type = va_arg(ap, int);
479 
480         list = dd_ref_addtostart(list, ptr, type);
481         ptr = va_arg(ap, void *);
482 
483     }
484     va_end(ap);
485     return (dd_list_reverse(list));
486 */
487     va_list ap;
488     List   *list = NULL;
489 
490     va_start(ap, type);
491 
492     while (type)
493     {
494         void   *ptr = va_arg(ap, void *);
495 
496         list = dd_ref_addtostart(list, ptr, type);
497         type = va_arg(ap, int);
498     }
499     va_end(ap);
500     return (dd_list_reverse(list));
501 }
502 
503 #else
504 
505 List *dd_list_of(va_alist) va_dcl
506 {
507 /*   old code NAT 7/2/2002
508     va_list ap;
509     List *list = NULL;
510     void   *ptr;
511 
512     va_start(ap);
513     while ((ptr = va_arg(ap, void *)) != NULL)
514     {
515         int     type = va_arg(ap, int);
516 
517         list = dd_ref_addtostart(list, ptr, type);
518     }
519     va_end(ap);
520 
521     return (dd_list_reverse(list));
522 */
523     va_list ap;
524     List   *list = NULL;
525     int     type;
526 
527     va_start(ap);
528     while ((type = va_arg(ap, int)) != 0)
529     {
530         void   *ptr = va_arg(ap, void *);
531 
532         list = dd_ref_addtostart(list, ptr, type);
533     }
534     va_end(ap);
535     return (dd_list_reverse(list));
536 }
537 
538 #endif                          /* __STRICT_ANSI__ */
539 #endif                          /* ANSIFYING */
540 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.