1 /************************************************************
2 **
3 ** COPYRIGHT (C) 1993 UNIVERSITY OF PITTSBURGH
4 ** COPYRIGHT (C) 1996 GANNON UNIVERSITY
5 ** ALL RIGHTS RESERVED
6 **
7 ** This software is distributed on an as-is basis
8 ** with no warranty implied or intended. No author
9 ** or distributor takes responsibility to anyone
10 ** regarding its use of or suitability.
11 **
12 ** The software may be distributed and modified
13 ** freely for academic and other non-commercial
14 ** use but may NOT be utilized or included in whole
15 ** or part within any commercial product.
16 **
17 ** This copyright notice must remain on all copies
18 ** and modified versions of this software.
19 **
20 ************************************************************/
21
22 /* file list.c */
23 /* ------------------------------------------------------------------------
24 * Helper / Utility routines for place and route spl 7/89, stf 2/90
25 * ------------------------------------------------------------------------
26 */
27 #include "list.h"
28
29 /*------------------------------------------------------------------------
30 * The following list processing functions are based on the following two
31 * data structures:
32 typedef struct list_struct list;
33 typedef struct indexed_list ilist;
34
35 struct list_struct
36 {
37 int *this;
38 list *next;
39 }
40
41 struct indexed_list
42 {
43 int index;
44 int *this;
45 int ilist *next;
46 }
47
48 *------------------------------------------------------------------------ */
49
50 /* ------------------------------------------------------------------------
51 * concat_list: append a generic thing to the head of a list.
52 * works for null lists.
53 * ------------------------------------------------------------------------
54 */
55
concat_list(e,l)56 list *concat_list(e,l)
57 int *e;
58 list *l;
59 {
60 list *p;
61
62 p = (list *) calloc(1, sizeof(list));
63 p->this = e;
64 p->next = l;
65
66 return(p);
67 }
68
69 /* ------------------------------------------------------------------------
70 * append_list: append two generic lists together.
71 * Works for either list null.
72 * If both lists are null, it returns null.
73 * ------------------------------------------------------------------------
74 */
75
append_list(l1,l2)76 list *append_list(l1,l2)
77 list *l1, *l2;
78 {
79 list *p;
80 if (l1 == NULL)
81 {
82 return (l2);
83 }
84
85 for(p = l1; p->next != NULL; p = p->next)
86 {
87 ;
88 }
89 p->next = l2;
90
91 return(l1);
92 }
93
94 /*---------------------------------------------------------------
95 * remove_list_element
96 * cut out a generic list element from the middle of a list
97 * note the parameter must be the address of the real thing, not
98 * a copy. so this should be called with the address of a
99 * subfield ie remove_list_element(&(thing->next))
100 * both remove_list_element(thing->next)
101 * and remove_list_element(&thing) (unless thing is global) will not work.
102 *---------------------------------------------------------------
103 */
remove_list_element(lptr)104 void remove_list_element(lptr)
105 list **lptr;
106 {
107 list *trash;
108
109 trash = *lptr;
110 *lptr = trash->next;
111
112 my_free(trash); /* Trash freed, contents not touched. */
113
114 }
115 /*--------------------------------------------------------------------------
116 * delete_if
117 * Clip all of the elements of the given list who's ->this field return TRUE
118 * to the given <testFn>. (Recursive implementation).
119 *--------------------------------------------------------------------------
120 */
delete_if(lptr,testFn)121 list *delete_if(lptr, testFn)
122 list **lptr;
123 int (*testFn)(); /* Should take a single *int as its arg, return TRUE/FALSE */
124 {
125 /* Remove all list elements that return TRUE to the <testFn> call. */
126 list *ll = *lptr;
127 if (*lptr == NULL) return(NULL);
128 else if ((*testFn)(ll->this) == TRUE) /* The first list item should go */
129 {
130 remove_list_element(lptr);
131 return(delete_if(lptr, testFn));
132 }
133
134 else /* Later list items should get nuked */
135 {
136 ll = *lptr;
137 ll->next = delete_if(&ll->next, testFn);
138 return(ll);
139 }
140 }
141 /* ------------------------------------------------------------------------
142 * pushnew - add a unique element to the front of a linked list
143 * ------------------------------------------------------------------------
144 */
pushnew(what,l)145 void pushnew(what, l)
146 int *what;
147 list **l;
148 {
149 list *ll;
150 int flag = TRUE;
151
152 for (ll = *l; ll != NULL; ll = ll->next)
153 {
154 if ((int)what == (int)ll->this) flag = FALSE;
155 }
156 if (flag == TRUE) push(what, l);
157 }
158
159 /* ------------------------------------------------------------------------
160 * push - add to the front of a linked list
161 * ------------------------------------------------------------------------
162 */
push(what,l)163 void push(what, l)
164 int *what;
165 list **l;
166 {
167 list *ll;
168 if ((ll = (list *)calloc(1, sizeof(list))) == NULL)
169 {
170 fprintf(stderr,"\nNo more room (push)"); exit(0);
171 }
172 else
173 {
174 ll->this = what;
175 ll->next = *l;
176 *l = ll;
177 }
178 }
179
180 /* ------------------------------------------------------------------------
181 * pop - (FILO) pop from the front of a linked list
182 * ------------------------------------------------------------------------
183 */
pop(l)184 int *pop(l)
185 list **l;
186 {
187 list *ll = *l;
188 int * item = ll->this;
189 *l = ll->next;
190 my_free(ll);
191 return(item);
192 }
193 /* ------------------------------------------------------------------------
194 * queue - add to the back of a linked list
195 * ------------------------------------------------------------------------
196 */
queue(what,l)197 void queue(what, l)
198 int *what;
199 list **l;
200 {
201 list *q = *l;
202
203 if (q == NULL) /* create the list */
204 {
205 q = (list *)calloc(1, sizeof(list));
206 q->this = what;
207 q->next = NULL;
208 *l = q;
209 }
210 else
211 { /* find the end of <l>: */
212 for(q = *l; q->next != NULL; q = q->next);
213 queue (what, &q->next);
214 }
215 }
216 /* ------------------------------------------------------------------------
217 * trans_item - pull from an unknown position within the first list, push
218 * onto second list
219 * ------------------------------------------------------------------------
220 */
221 extern int *trans_item(what, sList, dList)
222 int *what;
223 list **sList, **dList;
224 {
225 list *r = *dList, *q = *sList;
226
227 if (q == NULL) return (NULL);
228 else if (q->this == what) /* Front of <sList> */
229 { /* Make the transfer */
230 *sList = q->next; /* Pull from <sList> */
231 q->next = *dList; /* Push onto <dList> */
232 *dList = q;
233 return(what);
234 }
235 else
236 { /* find the end of <sList>: */
237 for(q = *sList; ((q->next != NULL) && (q->next->this != what)); q = q->next);
238 return (trans_item(what, &q->next, dList));
239 }
240 }
241
242 /* ------------------------------------------------------------------------
243 * rem_item - pull from an unknown position within the list
244 * ------------------------------------------------------------------------
245 */
rem_item(what,l)246 int *rem_item(what, l)
247 int *what;
248 list **l;
249 {
250 list *q = *l;
251
252 if (q == NULL) return (NULL);
253 else if (q->this == what)
254 {
255 *l = q->next;
256 my_free(q);
257 return(what);
258 }
259 else
260 { /* find the end of <l>: */
261 for(q = *l; ((q->next != NULL) && (q->next->this != what)); q = q->next);
262 return (rem_item(what, &q->next));
263 }
264 }
265 /* ------------------------------------------------------------------------
266 * repl_item - pull from an unknown position within the list, replace with
267 * given element.
268 * ------------------------------------------------------------------------
269 */
repl_item(what,new,l)270 int *repl_item(what, new, l)
271 int *what, *new;
272 list *l;
273 {
274 list *q = l;
275
276 if (q == NULL) return (NULL);
277 else if (q->this == what)
278 {
279 q->this = new;
280 return(what);
281 }
282 else
283 { /* find the end of <l>: */
284 for(q = l; ((q->next != NULL) && (q->next->this != what)); q = q->next);
285 return (repl_item(what, new, q->next));
286 }
287 }
288 /* ------------------------------------------------------------------------
289 * find_item - see if the item is in the list
290 * ------------------------------------------------------------------------
291 */
find_item(what,l)292 list *find_item(what, l)
293 int *what;
294 list *l;
295 {
296 list *q;
297
298 for (q = l; q != NULL; q = q->next)
299 {
300 if (q->this == what) return(q);
301 }
302 return(NULL);
303 }
304
305 /* ------------------------------------------------------------------------
306 * nth - Note: Numbering starts at one.
307 * ------------------------------------------------------------------------
308 */
nth(l,n)309 int *nth(l, n)
310 list *l;
311 int n;
312 {
313 /* This returns the Nth element of the list <l> given that there are at
314 least <n> elements on <l>. */
315 int i = 1;
316 for (; l != NULL; l = l->next)
317 {
318 if (i == n) return(l->this);
319 i++;
320 }
321 return(NULL);
322 }
323 /* ------------------------------------------------------------------------
324 * nth_cdr - Note: Numbering starts at one.
325 * ------------------------------------------------------------------------
326 */
nth_cdr(l,n)327 list *nth_cdr(l, n)
328 list *l;
329 int n;
330 {
331 /* This returns the Nth element of the list <l> given that there are at
332 least <n> elements on <l>. */
333 int i = 1;
334 if (n == 0) return(l); /* simple case... */
335
336 for (; l != NULL; l = l->next)
337 {
338 if (i == n) return(l);
339 i++;
340 }
341 return(NULL);
342 }
343
344 /* ------------------------------------------------------------------------
345 * list_length
346 *
347 * ------------------------------------------------------------------------
348 */
list_length(l)349 int list_length(l)
350 list *l;
351 {
352 int i;
353
354 for(i= 0; l != NULL; l = l->next)
355 {
356 i++;
357 }
358 return(i);
359 }
360
361 /* ------------------------------------------------------------------------
362 * member_p - returns TRUE iff the given pointer returns TRUE when compared
363 * with the ->this slot of some list element.
364 * ------------------------------------------------------------------------
365 */
member_p(e,l,testFn)366 int member_p(e, l, testFn)
367 int *e;
368 list *l;
369 int (*testFn)(); /* Should take two *int's as args, return TRUE/FALSE */
370 {
371 list *ll;
372
373 for(ll = l; ll != NULL; ll = ll->next)
374 {
375 if ((*testFn)(e, ll->this) == TRUE) return(TRUE);
376 }
377 return(FALSE);
378 }
379
380 /* ------------------------------------------------------------------------
381 * member - returns list pointer to the first item that returns TRUE to
382 * the testFn(e, ll->this) query. Returns NULL otherwise.
383 * ------------------------------------------------------------------------
384 */
member(e,l,testFn)385 list *member(e, l, testFn)
386 int *e;
387 list *l;
388 int (*testFn)(); /* Should take two *int's as args, return TRUE/FALSE */
389 {
390 list *ll;
391
392 for(ll = l; ll != NULL; ll = ll->next)
393 {
394 if ((*testFn)(e, ll->this) == TRUE) return(ll);
395 }
396 return(NULL);
397 }
398
399 /* ------------------------------------------------------------------------
400 * rcopy_list: make a copy of a list, reversing it for speed/convience
401 * ------------------------------------------------------------------------
402 */
403
rcopy_list(l)404 list *rcopy_list(l)
405 list *l;
406 {
407 list *ll, *p = NULL;
408
409 for(ll = l; ll != NULL; ll = ll->next)
410 {
411 push(ll->this, &p);
412 }
413 return(p);
414 }
415
416 /* ------------------------------------------------------------------------
417 * copy_list: make a copy of a list, preserving order
418 * ------------------------------------------------------------------------
419 */
copy_list(l)420 list *copy_list(l)
421 list *l;
422 {
423 list *p, *pp;
424
425 if(l == NULL)
426 {
427 /* error: "copy_list passed null list" */
428 return(NULL);
429 }
430 pp = p = (list *) calloc(1, sizeof(list));
431 p->this = l->this;
432 while(l = l->next)
433 {
434 p->next = (list *) calloc(1, sizeof(list));
435 p = p->next;
436 p->this = l->this;
437 }
438 p->next = NULL;
439 return(pp);
440 }
441 /* ------------------------------------------------------------------------
442 * delete_duplicates Modify the given list by deleting duplicate elements:
443 * ------------------------------------------------------------------------
444 */
delete_duplicates(l,testFn)445 list *delete_duplicates(l, testFn)
446 list **l;
447 int (*testFn)(); /* Should take two *int's as args, return TRUE/FALSE */
448 {
449 int *targ;
450 list *p, *pp, *trash, *last;
451
452 if (*l == NULL)
453 {
454 /* error: "delete_duplicates passed null list" */
455 return(NULL);
456 }
457
458 for (p = *l; ((p != NULL) && (p->next != NULL)); p = p->next)
459 {
460 targ = p->this;
461 last = p;
462 for (pp = p->next; pp != NULL;)
463 {
464 if (testFn(targ, pp->this) == TRUE)
465 {
466 last->next = pp->next;
467 trash = pp;
468 pp = pp->next;
469 my_free(trash);
470 }
471 else
472 {
473 last = pp;
474 pp = pp->next;
475 }
476 }
477 }
478 return(*l);
479 }
480 /* ------------------------------------------------------------------------
481 * my_free wipe this pointer from memory.
482 * ------------------------------------------------------------------------
483 */
484 extern int *my_free(p)
485 int *p;
486 {
487 int q = 1; /* NOP */
488 free(p);
489 return(NULL);
490 }
491 /* ------------------------------------------------------------------------
492 * free_list wipe this list from memory. Do not disturb any list elements.
493 * ------------------------------------------------------------------------
494 */
free_list(l)495 list *free_list(l)
496 list *l;
497 {
498 list *ll, *trash;
499 int i;
500 char *cptr;
501
502 for(ll = l; ll != NULL;)
503 {
504 trash = ll;
505 ll = ll->next;
506
507 /* Explicitly wipe memory */ /* ??? */
508 cptr = (char *)trash;
509 for (i = 0; i < sizeof(list); i++)
510 {
511 *(cptr + i) = 0;
512 }
513
514 my_free(trash);
515 }
516 return(NULL);
517 }
518 /* ------------------------------------------------------------------------
519 * sort_list (destructive) sort the given list via orderFn:
520 * ------------------------------------------------------------------------
521 */
sort_list(l,orderFn)522 list *sort_list(l, orderFn)
523 list *l;
524 int (*orderFn)(); /* Should take two *int's as args, return TRUE/FALSE */
525 /* TRUE implies the first element belongs in front of the second */
526 {
527 /* Bubble sort of */
528 list *lp;
529 int i, j , *temp, stop;
530 int exchange, len = list_length(l);
531 stop = len - 1;
532
533 for (i = len; i > 1; i -= 1)
534 {
535 lp = l;
536 exchange = FALSE;
537
538 for (j = 0; ((lp != NULL) && (lp->next != NULL) && (j < stop)); j += 1)
539 {
540 /* One bubbling pass - Compare lp->this with lp->next->this */
541 if (orderFn(lp->this, lp->next->this) == FALSE)
542 {
543 /* Swap lp->this with lp->next->this */
544 temp = lp->this;
545 lp->this = lp->next->this;
546 lp->next->this = temp;
547 exchange = TRUE;
548 }
549 lp = lp->next;
550 }
551 if (exchange == FALSE) break;
552 stop -= 1;
553 }
554 return(l);
555 }
556 /* ------------------------------------------------------------------------
557 * merge_sort (destructive) sort the given list via orderFn:
558 * ------------------------------------------------------------------------
559 */
merge_sort(l1,l2,n,m,orderFn)560 list *merge_sort(l1, l2, n, m, orderFn)
561 list *l1, *l2; /* Two lists to be merge-sorted. */
562 int n, m; /* number of elements from <l1>, <l2> to sort... */
563 int (*orderFn)(); /* Ordering function. Works on list elements */
564 {
565 /* The merge sorter... */
566 list *mid1, *mid2, *t1, *t2, *r, *result;
567 int i, *temp;
568
569 mid1 = mid2 = t1 = t2 = r = result = NULL;
570
571 if (l1 == l2) result = l1; /* Handle the n = 0 case... */
572
573 else if ((n == 1) && (m == 0)) result = l1;
574 else if ((m == 1) && (n == 0)) result = l2;
575
576 else if ((n == 1) && (m == 1)) /* Handle the n = 1 case... */
577 {
578 if (orderFn(l1->this, l2->this) == FALSE)
579 {
580 /* Swap l1->this with l2->this */
581 temp = l1->this;
582 l1->this = l2->this;
583 l2->this = temp;
584 }
585 result = l1;
586 result->next = l2;
587 }
588
589 else /* if (l1 != l2) Handle the general case: */
590 {
591 t1 = nth_cdr(l1, n/2);
592 if (t1 != NULL)
593 {
594 mid1 = t1->next; /* Split <l1> */
595 t1->next = NULL; /* Terminate the temp list */
596 }
597
598 t2 = nth_cdr(l2, m/2);
599 if (t2 != NULL)
600 {
601 mid2 = t2->next; /* Split <l2> */
602 t2->next = NULL; /* Terminate the temp list */
603 }
604
605 /* Recursive calls... */
606 /* Sort the left sublist */
607 if ((n == 0) || (n == 1)) t1 = l1;
608 else t1 = merge_sort(l1, mid1, n/2, n - n/2, orderFn);
609
610 /* Sort the right sublist */
611 if ((m == 0) || (m == 1)) t2 = l2;
612 else t2 = merge_sort(l2, mid2, m/2, m - m/2, orderFn);
613
614 /* Check for errors: */
615 if ((t1 == NULL) && (t2 == NULL)) return(NULL); /* Big Problem!! */
616
617 /* Merge the two sorted sublists, <t1> & <t2>... */
618 for(i = n+m; i != 0; i--) /* Merge all of the elements given... */
619 {
620 if ((t2 != NULL) &&
621 ((t1 == NULL) || (orderFn(t1->this, t2->this) == FALSE)))
622 {
623 /* The first element of <t2> gets added to the <result> list. */
624 if (result != NULL)
625 {
626 r->next = t2;
627 t2 = t2->next;
628 r->next->next = NULL;
629 r = r->next;
630 }
631 else
632 {
633 result = t2;
634 t2 = t2->next;
635 result->next = NULL;
636 r = result;
637 }
638 }
639 else /* ((t2 == NULL) || (orderFn(t1->this, t2->this) != FALSE)) */
640 {
641 /* The first element of <t1> gets added to the <result> list */
642 if (result != NULL)
643 {
644 r->next = t1;
645 t1 = t1->next;
646 r->next->next = NULL;
647 r = r->next;
648 }
649 else
650 {
651 result = t1;
652 t1 = t1->next;
653 result->next = NULL;
654 r = result;
655 }
656 }
657 }
658 }
659 return(result);
660 }
661 /* ------------------------------------------------------------------------
662 * merge_sort_list (destructive) sort the given list via orderFn:
663 * ------------------------------------------------------------------------
664 */
merge_sort_list(l,orderFn)665 list *merge_sort_list(l, orderFn)
666 list **l;
667 int (*orderFn)(); /* Should take two *int's as args, return TRUE/FALSE */
668 /* TRUE implies the first element belongs in front of the second */
669 {
670 return(*l = merge_sort(*l, NULL, list_length(*l), 0, orderFn));
671 }
672
673
674 /* ------------------------------------------------------------------------
675 * slow_sort_list (destructive) sort the given list via orderFn:
676 * ------------------------------------------------------------------------
677 */
slow_sort_list(l,orderFn)678 list *slow_sort_list(l, orderFn)
679 list *l;
680 int (*orderFn)(); /* Should take two *int's as args, return TRUE/FALSE */
681 /* TRUE implies the first element belongs in front of the second */
682 {
683 /* The slow sorter... */
684 list *lp, *lpp;
685 int *temp;
686
687 for (lp = l; ((lp != NULL) && (lp->next != NULL)); lp = lp->next)
688 {
689 for (lpp = lp; lpp != NULL; lpp = lpp->next)
690 {
691 if (orderFn(lp->this, lpp->this) == FALSE)
692 {
693 /* Swap lp->this with lpp->this */
694 temp = lp->this;
695 lp->this = lpp->this;
696 lpp->this = temp;
697 }
698 }
699 }
700 return(l);
701 }
702 /* ------------------------------------------------------------------------
703 * reverse_ilist: make a copy of an indexed list, inverting order while
704 * maintaining the original indexing
705 * ------------------------------------------------------------------------
706 */
reverse_copy_ilist(l)707 ilist *reverse_copy_ilist(l)
708 ilist *l;
709 {
710 ilist *p, *pp = NULL;
711
712 if(l == NULL)
713 {
714 /* error: "reverse_copy_ilist passed null list" */
715 return(NULL);
716 }
717
718 pp = p = (ilist *) calloc(1, sizeof(ilist));
719 pp->this = l->this;
720 pp->index = l->index;
721 pp->next = NULL;
722
723 while(l = l->next)
724 {
725 p = (ilist *) calloc(1, sizeof(ilist));
726 p->next = pp;
727 p->this = l->this;
728 p->index = l->index;
729 pp = p;
730 }
731 return(p);
732 }
733 /* ------------------------------------------------------------------------
734 * rcopy_ilist: make a copy of an indexed list, inverting order
735 * ------------------------------------------------------------------------
736 */
rcopy_ilist(l)737 ilist *rcopy_ilist(l)
738 ilist *l;
739 {
740 ilist *p, *pp = NULL;
741
742 if(l == NULL)
743 {
744 /* error: "rcopy_ilist passed null list" */
745 return(NULL);
746 }
747
748 for (p = l; p != NULL; p = p->next)
749 {
750 ipush(p->this, &pp);
751 }
752 return(pp);
753 }
754 /* ------------------------------------------------------------------------
755 * copy_ilist: make a copy of an indexed list, preserving order
756 * ------------------------------------------------------------------------
757 */
copy_ilist(l)758 ilist *copy_ilist(l)
759 ilist *l;
760 {
761 ilist *p, *pp;
762
763 if(l == NULL)
764 {
765 /* error: "copy_ilist passed null list" */
766 return(NULL);
767 }
768 pp = p = (ilist *) calloc(1, sizeof(ilist));
769 p->this = l->this;
770 p->index = l->index;
771 while(l = l->next)
772 {
773 p->next = (ilist *) calloc(1, sizeof(ilist));
774 p = p->next;
775 p->this = l->this;
776 p->index = l->index;
777 }
778 p->next = NULL;
779 return(pp);
780 }
781
782 /* ------------------------------------------------------------------------
783 * remove_indexed_element remove (by index) an element from a list structure
784 * NOTE: This renumbers the elements following the discovery.
785
786 <<<<HAS PROBLEMS>>>>
787 * ------------------------------------------------------------------------
788 */
remove_indexed_element(indx,lptr)789 int *remove_indexed_element(indx, lptr)
790 int indx;
791 ilist **lptr;
792 {
793 ilist *l, *lst;
794 int *temp = NULL;
795
796 lst = *lptr;
797
798 if((lst == NULL)||(lst->index > indx)||((lst->index != indx) && (lst->next == NULL)))
799 return (NULL);
800 else
801 {
802 for(l = lst; ; l = l->next)
803 {
804 if(l->index == indx)
805 {
806 /* we already have a list at this index */
807 if (l!=lst) lst->next = l -> next; /* free trash? */
808 else *lptr = l->next; /* pop off top of list */
809 temp = l->this;
810 }
811
812 /* renumber & assume it's there */
813 else if (l->index > indx) --l->index;
814
815 /* quit once the list is exausted */
816 if ((l->next == NULL) && (temp)) return(temp);
817 else if (l->next == NULL)
818 { /* renumber the list and return null */
819 for (l = *lptr; ; l = l->next)
820 {
821 if (l->next == NULL) return(temp);
822 else if (l->index > indx) ++l->index;
823 }
824 }
825 lst = l;
826 }
827 }
828 }
829 /* ------------------------------------------------------------------------
830 * irem_item - pull from an unknown position within an indexed list
831 * (no renumbering)
832 * ------------------------------------------------------------------------
833 */
irem_item(what,l,howFar)834 int *irem_item(what, l, howFar)
835 int *what;
836 ilist **l;
837 int howFar; /* If != NULL, places a limit on the search */
838 {
839 ilist *q = *l;
840
841 if ((q == NULL) || ((howFar != NULL) && (q->index > howFar))) return (NULL);
842 else if (what == q->this) /* Found the little Commie! */
843 {
844 *l = q->next; /* Note: No renumbering occurs */
845 my_free(q); /* Nuke it! */
846 return(what);
847 }
848 else
849 { /* find the end of <l>: */
850 for(q = *l; ((q->next != NULL) && (q->next->this != what)); q = q->next);
851 return (irem_item(what, &q->next, howFar));
852 }
853 }
854 /* ------------------------------------------------------------------------
855 * find_indexed_element finds (by index) an element from a list structure
856 * note: this returns the list pointer to the requested element.
857 * ------------------------------------------------------------------------
858 */
find_indexed_element(indx,lst)859 ilist *find_indexed_element(indx, lst)
860 int indx;
861 ilist *lst;
862 {
863 ilist *l;
864
865 if((lst == NULL)||(lst->index > indx)) return (NULL);
866
867 else
868 {
869 for(l = lst; ; l = l->next)
870 {
871 if(l->index == indx) return(l);
872
873 /* quit once the list is exausted */
874 if (l->next == NULL) return(NULL);
875
876 }
877 }
878 }
879 /* ------------------------------------------------------------------------
880 * indexed_list_insert an element to an indexed list structure.
881 * ------------------------------------------------------------------------
882 */
indexed_list_insert(element,indx,lptr)883 int indexed_list_insert(element, indx, lptr)
884 int *element;
885 int indx;
886 ilist **lptr;
887 {
888 ilist *lst = *lptr;
889 ilist *tl, *l;
890
891 if((lst == NULL)||(lst->index > indx))
892 {
893 tl = (ilist *)calloc(1, sizeof(ilist));
894 tl->next = lst;
895 tl->index = indx;
896 tl->this = element;
897 *lptr = tl;
898 return (TRUE);
899 }
900 else
901 {
902 for(l = lst; ; l = l->next)
903 {
904 if(l->index == indx)
905 {
906 /* we already have a list at this index */
907 l->this = element; /* replace the contents with the new stuff */
908 return(TRUE);
909 }
910 if ( (l->next == NULL) || (l->next->index > indx))
911 {/* note we are counting on order of above exp */
912
913 /* we hit the end or fall between two existing lists */
914 tl = (ilist *)calloc(1, sizeof(ilist));
915 tl->index = indx;
916 tl->this = element;
917 tl->next = l->next;
918 l->next = tl;
919 return(TRUE);
920 }
921 }
922 }
923 }
924 /* ------------------------------------------------------------------------
925 * ordered_ilist_insert an element to an indexed list structure.
926 * quite similar to "indexed_list_insert, saving that whenever an element having
927 * the same index value is encountered, rather than replacing the entry (as in
928 * the aforementioned function) a new list element is created, and placed in front
929 * of the first such entry encountered.
930 * ------------------------------------------------------------------------
931 */
ordered_ilist_insert(element,indx,lptr)932 int ordered_ilist_insert(element, indx, lptr)
933 int *element;
934 int indx;
935 ilist **lptr;
936 {
937 ilist *lst = *lptr;
938 ilist *tl, *l;
939
940 if((lst == NULL)||(lst->index > indx))
941 {
942 tl = (ilist *)calloc(1, sizeof(ilist));
943 tl->next = lst;
944 tl->index = indx;
945 tl->this = element;
946 *lptr = tl;
947 return (TRUE);
948 }
949 else
950 {
951 for(l = lst; ; l = l->next)
952 {
953 if ( (l->next == NULL) || (l->next->index >= indx))
954 {/* note we are counting on order of above exp */
955
956 /* we hit the end or fall between two existing lists */
957 tl = (ilist *)calloc(1, sizeof(ilist));
958 tl->index = indx;
959 tl->this = element;
960 tl->next = l->next;
961 l->next = tl;
962 return(TRUE);
963 }
964 }
965 }
966 }
967 /* ------------------------------------------------------------------------
968 * ilist_length
969 *
970 * ------------------------------------------------------------------------
971 */
ilist_length(l)972 int ilist_length(l)
973 ilist *l;
974 {
975 int i;
976
977 for(i= 0; l != NULL; l = l->next)
978 {
979 i++;
980 }
981 return(i);
982 }
983 /* ------------------------------------------------------------------------
984 * ipop - (FILO) pop from the front of a indexed linked list (No renumbering)
985 * ------------------------------------------------------------------------
986 */
ipop(l)987 int *ipop(l)
988 ilist **l;
989 {
990 ilist *ll = *l;
991 int *item = ll->this;
992 *l = ll->next;
993 my_free(ll);
994 return(item);
995 }
996 /* ------------------------------------------------------------------------
997 * ipush - (FILO) push to the front of a indexed linked list (renumbering)
998 * ------------------------------------------------------------------------
999 */
ipush(what,l)1000 void ipush(what, l)
1001 int *what;
1002 ilist **l;
1003 {
1004 ilist *ll;
1005 if ((ll = (ilist *)calloc(1, sizeof(ilist))) == NULL)
1006 {
1007 fprintf(stderr,"\nNo more room (ipush)"); exit(0);
1008 }
1009 else
1010 {
1011 ll->this = what;
1012 ll->next = *l;
1013 ll->index = 0;
1014 *l = ll;
1015 }
1016 for (ll = ll->next; ll != NULL; ll = ll->next)
1017 {
1018 /* Walk down the rest of the list and renumber */
1019 ll->index += 1;
1020 }
1021
1022 }
1023 /* ------------------------------------------------------------------------
1024 * append_ilist: append two generic indexed lists together.
1025 * Works for either list null.
1026 * If both lists are null, it returns null.
1027 * ------------------------------------------------------------------------
1028 */
1029
append_ilist(l1,l2)1030 ilist *append_ilist(l1,l2)
1031 ilist *l1, *l2;
1032 {
1033 ilist *p;
1034 int i;
1035 if (l1 == NULL)
1036 {
1037 return (l2);
1038 }
1039
1040 for(p = l1; p->next != NULL; p = p->next)
1041 {
1042 i = p->index;
1043 }
1044 p->next = l2;
1045 i++;
1046 for (p = l2; p->next != NULL; p = p->next)
1047 {
1048 p->index = ++i;
1049 }
1050
1051 return(l1);
1052 }
1053 /* ------------------------------------------------------------------------
1054 * free_ilist wipe this list from memory. Do not disturb any list elements.
1055 * ------------------------------------------------------------------------
1056 */
free_ilist(l)1057 ilist *free_ilist(l)
1058 ilist *l;
1059 {
1060 ilist *ll, *trash;
1061
1062 for(ll = l; ll != NULL;)
1063 {
1064 trash = ll;
1065 ll = ll->next;
1066 my_free(trash);
1067 }
1068 return(NULL);
1069 }
1070 /* ------------------------------------------------------------------------
1071 * END OF FILE
1072 * ------------------------------------------------------------------------
1073 */
1074
1075