asg/list.c

   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
  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
  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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
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
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  */
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