linklist.c

   1 /*
   2 **  FACILITY:  linklist.c
   3 **
   4 **  MODULE DESCRIPTION:
   5 **
   6 **      general routines for linked lists
   7 **          + newlist: initialize new list
   8 **          + insertll: insert item in list
   9 **          + searchll: search for item in list
  10 **          + emptyll: delete all items from a linked list
  11 **          + doll: run a function for every item from the linked list
  12 **          + getnextll: get the next item from the list
  13 **          + copyll: copy a complete linked list
  14 **          + llitembynr: return pointer to the data of item nr of the list
  15 **          + llrembynr: remove item nr from the list and return pointer
  16 **                       to the data
  17 **          + pushll: add item to the end of a linked list
  18 **          + findlastll: find last item in the last that
  19 **                        corresponds with what we want
  20 **          (+ delll: delete an item from the list)
  21 **
  22 **  AUTHORS:
  23 **
  24 **      Kurt Van den Branden
  25 **
  26 **  CREATION DATE:  22/01/97
  27 **
  28 **  DESIGN ISSUES:
  29 **
  30 **      these functions should be as general as possible
  31 **      you can put any data at the nodes from the list
  32 **      you have to provide your own compare-routine
  33 **
  34 */
  35 /*
  36 **    Copyright (C) 1998 Kurt Van den Branden
  37 **
  38 ** This program is free software; you can redistribute it and/or modify
  39 ** it under the terms of the GNU General Public License as published by
  40 ** the Free Software Foundation; either version 2 of the License, or
  41 ** (at your option) any later version.
  42 **
  43 ** This program is distributed in the hope that it will be useful,
  44 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
  45 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  46 ** GNU General Public License for more details.
  47 **
  48 ** You should have received a copy of the GNU General Public License
  49 ** along with this program; if not, write to the Free Software
  50 ** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  51 */
  52
  53
  54 /*
  55 **
  56 **  INCLUDE FILES
  57 **
  58 */
  59
  60 #include <stdio.h>
  61 #include <malloc.h>
  62 #include "linklist.h"
  63
  64 #ifdef FASTLLIST
  65 /*
  66 **++
  67 **  FUNCTIONAL DESCRIPTION:
  68 **
  69 **      newlist: initialize a new linked list
  70 **
  71 **  FORMAL PARAMETERS:
  72 **
  73 **      head: pointer to header of new list
  74 **
  75 **  RETURN VALUE:
  76 **
  77 **      0: OK
  78 **      -1: error
  79 **
  80 **--
  81 */
  82 int newlist (listheader * head)
  83 {
  84     head->firstitem = NULL;
  85     head->curnr = -1;
  86     head->curptr = NULL;
  87     head->lastptr = NULL;
  88     return (0);
  89 }
  90 #endif
  91
  92 /*
  93 **++
  94 **  FUNCTIONAL DESCRIPTION:
  95 **
  96 **      insertll: insert item in a linked list
  97 **
  98 **  FORMAL PARAMETERS:
  99 **
 100 **      head: pointer to head of linked list
 101 **      newitem: void-pointer to item that has to be inserted in the list
 102 **      compfunction: pointer to a function that can compare to items
 103 **                    it should return -1, 0, 1. to indicate that the
 104 **                    first item is smaller, equal, larger than the second
 105 **
 106 **  RETURN VALUE:
 107 **
 108 **      0 : OK
 109 **      -1: error
 110 **      1 : item already in the list (0 was returned by compfunction)
 111 **
 112 **--
 113 */
 114 int insertll (listheader * head, void * newitem, int (* compfunction)())
 115 {
 116     listitem *curitem,
 117              *previtem,
 118              *dumitem;
 119     int compresult;
 120
 121 #ifdef FASTLLIST
 122     head->curnr = -1;
 123     head->curptr = NULL;
 124 #endif
 125
 126     if (head->firstitem == NULL)
 127     {
 128         dumitem = (listitem *) malloc (sizeof (listitem));
 129         dumitem->itemptr = newitem;
 130         dumitem->next = NULL;
 131         head->firstitem = dumitem;
 132 #ifdef FASTLLIST
 133         head->lastptr = dumitem;
 134 #endif
 135         return (0);
 136     }
 137
 138     previtem = NULL;
 139     curitem = head->firstitem;
 140     while (curitem != NULL)
 141     {
 142         compresult = (* compfunction)(curitem->itemptr, newitem);
 143         if (compresult == 0)
 144         {
 145             return (1);
 146         }
 147         else if (compresult > 0)
 148         {
 149             dumitem = (listitem *) malloc (sizeof (listitem));
 150             dumitem->itemptr = newitem;
 151             dumitem->next = NULL;
 152             if (previtem == NULL)
 153             {
 154                 head->firstitem = dumitem;
 155             }
 156             else
 157             {
 158                 previtem->next = dumitem;
 159             }
 160             dumitem->next = curitem;
 161             return (0);
 162         }
 163         else
 164         {
 165             previtem = curitem;
 166             curitem = curitem->next;
 167         }
 168     }
 169     dumitem = (listitem *) malloc (sizeof (listitem));
 170     dumitem->itemptr = newitem;
 171     dumitem->next = NULL;
 172     previtem->next = dumitem;
 173
 174 #ifdef FASTLLIST
 175     head->lastptr = dumitem;
 176 #endif
 177
 178     return (0);
 179 }
 180
 181
 182 /*
 183 **++
 184 **  FUNCTIONAL DESCRIPTION:
 185 **
 186 **      llremitem: delete item from a linked list
 187 **
 188 **  FORMAL PARAMETERS:
 189 **
 190 **      head: pointer to head of linked list
 191 **      newitem: void-pointer to an item that has to be compared with
 192 **               what has to be deleted
 193 **      compfunction: pointer to a function that can compare to items
 194 **                    it should return -1, 0, 1. to indicate that the
 195 **                    first item is smaller, equal, larger than the second
 196 **
 197 **  RETURN VALUE:
 198 **
 199 **      pointer to data (has to be deleted by calling procedure)
 200 **      NULL
 201 **
 202 **--
 203 */
 204 void * llremitem (listheader * head, void * newitem, int (* compfunction)())
 205 {
 206     listitem *curitem,
 207              *previtem;
 208     int compresult;
 209     void * data;
 210
 211     if ((head == NULL) || (head->firstitem == NULL))
 212     {
 213         return (NULL);
 214     }
 215
 216     previtem = NULL;
 217     curitem = head->firstitem;
 218     while (curitem != NULL)
 219     {
 220         compresult = (* compfunction)(curitem->itemptr, newitem);
 221         if (compresult == 0)
 222         {
 223             if (previtem == NULL)
 224             {
 225                 head->firstitem = curitem->next;
 226             }
 227             else
 228             {
 229                 previtem->next = curitem->next;
 230             }
 231 #ifdef FASTLLIST
 232             if (head->lastptr == curitem)
 233                 head->lastptr = previtem;
 234             head->curptr = NULL;
 235             head->curnr = -1;
 236 #endif
 237             data = curitem->itemptr;
 238             free (curitem);
 239             return (data);
 240         }
 241         else if (compresult > 0)
 242         {
 243             return (NULL);
 244         }
 245         else
 246         {
 247             previtem = curitem;
 248             curitem = curitem->next;
 249         }
 250     }
 251
 252     return (NULL);
 253 }
 254
 255
 256 /*
 257 **++
 258 **  FUNCTIONAL DESCRIPTION:
 259 **
 260 **      pushll: add item to the end of a linked list
 261 **
 262 **  FORMAL PARAMETERS:
 263 **
 264 **      head: pointer to head of linked list
 265 **      newitem: void-pointer to item that has to be inserted in the list
 266 **
 267 **  RETURN VALUE:
 268 **
 269 **      0 : OK
 270 **      -1: error
 271 **
 272 **--
 273 */
 274 int pushll (listheader * head, void * newitem)
 275 {
 276     listitem *curitem,
 277              *previtem,
 278              *dumitem;
 279
 280     dumitem = (listitem *) malloc (sizeof (listitem));
 281     dumitem->itemptr = newitem;
 282     dumitem->next = NULL;
 283
 284 #ifdef FASTLLIST
 285     if (head->lastptr == NULL)
 286         head->firstitem = dumitem;
 287     else
 288         head->lastptr->next = dumitem;
 289     head->lastptr = dumitem;
 290 #else
 291     if (head->firstitem == NULL)
 292     {
 293         head->firstitem = dumitem;
 294         return (0);
 295     }
 296
 297     previtem = NULL;
 298     curitem = head->firstitem;
 299     while (curitem != NULL)
 300     {
 301         previtem = curitem;
 302         curitem = curitem->next;
 303     }
 304     previtem->next = dumitem;
 305 #endif
 306
 307     return (0);
 308 }
 309
 310
 311 /*
 312 **++
 313 **  FUNCTIONAL DESCRIPTION:
 314 **
 315 **      unshiftll: add item to the beginning of a linked list
 316 **
 317 **  FORMAL PARAMETERS:
 318 **
 319 **      head: pointer to head of linked list
 320 **      newitem: void-pointer to item that has to be inserted in the list
 321 **
 322 **  RETURN VALUE:
 323 **
 324 **      0 : OK
 325 **      -1: error
 326 **
 327 **--
 328 */
 329 int unshiftll (listheader * head, void * newitem)
 330 {
 331     listitem *dumitem;
 332
 333     dumitem = (listitem *) malloc (sizeof (listitem));
 334     dumitem->itemptr = newitem;
 335     dumitem->next = head->firstitem;
 336     head->firstitem = dumitem;
 337
 338 #ifdef FASTLLIST
 339     if (head->lastptr == NULL)
 340         head->lastptr = dumitem;
 341     head->curptr = NULL;
 342     head->curnr = -1;
 343 #endif
 344
 345     return (0);
 346 }
 347
 348
 349 /*
 350 **++
 351 **  FUNCTIONAL DESCRIPTION:
 352 **
 353 **      searchll : find an item in a linked list
 354 **
 355 **  FORMAL PARAMETERS:
 356 **
 357 **      head: pointer to listhead
 358 **      item: pointer to item to search for
 359 **      compfunction: pointer to a function that can compare to items
 360 **                    it should return -1, 0, 1. to indicate that the
 361 **                    first item is smaller, equal, larger than the second
 362 **
 363 **  RETURN VALUE:
 364 **
 365 **      pointer to the found item, or NULL if not found
 366 **
 367 **--
 368 */
 369 void * searchll (listheader * head, void * item, int (* compfunction)())
 370 {
 371     listitem * curitem;
 372     int compresult;
 373
 374     curitem = head->firstitem;
 375     while (curitem != NULL)
 376     {
 377         compresult = (* compfunction)(curitem->itemptr, item);
 378         if (compresult == 0)
 379         {
 380             return (curitem->itemptr);
 381         }
 382         else if (compresult > 0)
 383         {
 384             return (NULL);
 385         }
 386         curitem = curitem->next;
 387     }
 388     return (NULL);
 389 }
 390
 391
 392 /*
 393 **++
 394 **  FUNCTIONAL DESCRIPTION:
 395 **
 396 **      emptyll: remove all items from a linked list
 397 **
 398 **  FORMAL PARAMETERS:
 399 **
 400 **      head: pointer to the listheader
 401 **      delfunction: pointer to a function that is called to delete each
 402 **                   item from the list, it is called with 1 parameter,
 403 **                   a void-pointer to the item, no return-value is expected
 404 **
 405 **  RETURN VALUE:
 406 **
 407 **      0: OK
 408 **      -1: error
 409 **
 410 **--
 411 */
 412 int emptyll (listheader * head, void (* delfunction)(void *))
 413 {
 414     listitem * curitem,
 415              * dumitem;
 416
 417     if (head == NULL)
 418     {
 419         return (0);
 420     }
 421
 422     curitem = head->firstitem;
 423     while (curitem != NULL)
 424     {
 425         (* delfunction)(curitem->itemptr);
 426         dumitem = curitem->next;
 427         free (curitem);
 428         curitem = dumitem;
 429     }
 430     head->firstitem = NULL;
 431
 432 #ifdef FASTLLIST
 433     head->lastptr = NULL;
 434     head->curptr = NULL;
 435     head->curnr = -1;
 436 #endif
 437
 438     return (0);
 439 }
 440
 441
 442 /*
 443 **++
 444 **  FUNCTIONAL DESCRIPTION:
 445 **
 446 **      doll: execute a function for all the items from a linked list
 447 **
 448 **  FORMAL PARAMETERS:
 449 **
 450 **      head: pointer to the listheader
 451 **      dofunction: pointer to a function that is called for each
 452 **                   item from the list, it is called with 1 parameter,
 453 **                   a void-pointer to the item, no return-value is expected
 454 **
 455 **  RETURN VALUE:
 456 **
 457 **      0: OK
 458 **      -1: error
 459 **
 460 **--
 461 */
 462 int doll (listheader * head, void (* dofunction)())
 463 {
 464     listitem * curitem;
 465
 466     curitem = head->firstitem;
 467     while (curitem != NULL)
 468     {
 469         (* dofunction)(curitem->itemptr);
 470         curitem = curitem->next;
 471     }
 472     return (0);
 473 }
 474
 475
 476 /*
 477 **++
 478 **  FUNCTIONAL DESCRIPTION:
 479 **
 480 **      llitembynr: return the data for item nr from the list
 481 **
 482 **  FORMAL PARAMETERS:
 483 **
 484 **      head: pointer to the listheader
 485 **      nr : item to return, the first item of the list = 1
 486 **
 487 **  RETURN VALUE:
 488 **
 489 **      pointer to data
 490 **      NULL on error
 491 **
 492 **--
 493 */
 494 void * llitembynr (listheader * head, int nr)
 495 {
 496     listitem * curitem;
 497     int counter;
 498
 499     if (head == NULL)
 500     {
 501         return (NULL);
 502     }
 503
 504 #ifdef FASTLLIST
 505     if (head->curnr == (nr - 1))
 506         curitem = head->curptr->next;
 507     else if (head->curnr == nr)
 508         curitem = head->curptr;
 509     else
 510     {
 511 #endif
 512         curitem = head->firstitem;
 513         counter = 1;
 514         while ((curitem != NULL) && (counter != nr))
 515         {
 516             counter++;
 517             curitem = curitem->next;
 518         }
 519 #ifdef FASTLLIST
 520     }
 521 #endif
 522
 523     if (curitem != NULL)
 524     {
 525 #ifdef FASTLLIST
 526         head->curnr = nr;
 527         head->curptr = curitem;
 528 #endif
 529         return (curitem->itemptr);
 530     }
 531     return (NULL);
 532 }
 533
 534
 535 /*
 536 **++
 537 **  FUNCTIONAL DESCRIPTION:
 538 **
 539 **      llrembynr: remove item nr from the list and return pointer to
 540 **                 the data from this item
 541 **
 542 **  FORMAL PARAMETERS:
 543 **
 544 **      head: pointer to the listheader
 545 **      nr : item to remove, the first item of the list = 1
 546 **
 547 **  RETURN VALUE:
 548 **
 549 **      pointer to data
 550 **      NULL on error
 551 **
 552 **--
 553 */
 554 void * llrembynr (listheader * head, int nr)
 555 {
 556     listitem * previtem = NULL,
 557         * curitem;
 558     int counter;
 559     void * data;
 560
 561     if (head == NULL)
 562     {
 563         return (NULL);
 564     }
 565
 566 #ifdef FASTLLIST
 567     // use information from the last llitembynr
 568     if (head->curnr == (nr - 1))
 569     {
 570         previtem = head->curptr;
 571         curitem = head->curptr->next;
 572     }
 573     else
 574     {
 575 #endif
 576         curitem = head->firstitem;
 577         counter = 1;
 578         while ((curitem != NULL) && (counter != nr))
 579         {
 580             counter++;
 581             previtem = curitem;
 582             curitem = curitem->next;
 583         }
 584 #ifdef FASTLLIST
 585     }
 586 #endif
 587
 588     if (curitem != NULL)
 589     {
 590         if (previtem == NULL)
 591         {
 592             head->firstitem = curitem->next;
 593         }
 594         else
 595         {
 596             previtem->next = curitem->next;
 597         }
 598 #ifdef FASTLLIST
 599         if (curitem == head->lastptr)
 600             head->lastptr = previtem;
 601         head->curptr = NULL;
 602         head->curnr = -1;
 603 #endif
 604
 605         data = curitem->itemptr;
 606         free (curitem);
 607         return (data);
 608     }
 609
 610     return (NULL);
 611 }
 612
 613
 614 /*
 615 **++
 616 **  FUNCTIONAL DESCRIPTION:
 617 **
 618 **      copyll: copy a complete linked list and all the data in it
 619 **
 620 **  FORMAL PARAMETERS:
 621 **
 622 **      head: pointer to the listheader
 623 **      copyfunction: pointer to a function that is called for each
 624 **                    item from the list, it is called with 1 parameter,
 625 **                    a void-pointer to the item.
 626 **                    as return-value, a void pointer to a copy of the input
 627 **                    item is expected
 628 **
 629 **  RETURN VALUE:
 630 **
 631 **      pointer to the head of the copied list
 632 **
 633 **--
 634 */
 635 listheader * copyll (listheader * head, void * (* copyfunction)())
 636 {
 637     listitem * curitem,
 638         * newitem = NULL,
 639         * dumitem;
 640     listheader * newheader;
 641
 642     if (head == NULL)
 643     {
 644         return (NULL);
 645     }
 646
 647     curitem = head->firstitem;
 648     newheader = (listheader *) malloc (sizeof (listheader));
 649     newheader->firstitem = NULL;
 650     while (curitem != NULL)
 651     {
 652         dumitem = (listitem *) malloc (sizeof (listitem));
 653
 654         dumitem->next = NULL;
 655         dumitem->itemptr = (* copyfunction)(curitem->itemptr);
 656         if (newitem == NULL)
 657         {
 658             newheader->firstitem = dumitem;
 659         }
 660         else
 661         {
 662             newitem->next = dumitem;
 663         }
 664         newitem = dumitem;
 665
 666         curitem = curitem->next;
 667     }
 668
 669 #ifdef FASTLLIST
 670     newheader->lastptr = newitem;
 671     newheader->curptr = NULL;
 672     newheader->curnr = -1;
 673 #endif
 674
 675     return (newheader);
 676 }
 677
 678
 679 /*
 680 **++
 681 **  FUNCTIONAL DESCRIPTION:
 682 **
 683 **      getnextll
 684 **
 685 **  FORMAL PARAMETERS:
 686 **
 687 **      head: header of the linked list
 688 **      curptr: pointer to the current item in the list
 689 **
 690 **  RETURN VALUE:
 691 **
 692 **      pointer to the next item in the linked list (the item after curptr)
 693 **      the order of the list is the same order then during inclusion
 694 **      if curptr is not found in the list, or there is no next item, the
 695 **      NULL is returned.
 696 **
 697 **--
 698 */
 699 void * getnextll (listheader * head, void * curptr)
 700 {
 701     listitem * curitem;
 702
 703     curitem = head->firstitem;
 704     while ((curitem != NULL) && (curitem->itemptr != curptr))
 705     {
 706         curitem = curitem->next;
 707     }
 708     if ((curitem == NULL) || (curitem->next == NULL))
 709     {
 710         return (NULL);
 711     }
 712
 713     curitem = curitem->next;
 714     return (curitem->itemptr);
 715 }
 716
 717
 718 /*
 719 **++
 720 **  FUNCTIONAL DESCRIPTION:
 721 **
 722 **      findlastll
 723 **
 724 **  FORMAL PARAMETERS:
 725 **
 726 **      head: header of the linked list
 727 **      checkfunction: function to be called with each item from the list
 728 **            and returning 1 or 0 (1: item we are looking for, 0: not)
 729 **
 730 **  RETURN VALUE:
 731 **
 732 **      number of the last item in the list that makes the checkfunction
 733 **      return 1
 734 **
 735 **--
 736 */
 737 int findlastll (listheader * head, int (* checkfunction)(void*))
 738 {
 739     listitem * curitem;
 740     int theitem = 0,
 741         nr = 1;
 742
 743     curitem = head->firstitem;
 744     while (curitem != NULL)
 745     {
 746         if ((* checkfunction) (curitem->itemptr) == 1)
 747             theitem = nr;
 748
 749         nr++;
 750         curitem = curitem->next;
 751     }
 752
 753     return (theitem);
 754 }
 755
 756
 757 /*
 758 ** returns the number of items in the linked list
 759 */
 760 int lllength (listheader * head)
 761 {
 762     listitem * curitem;
 763     int counter = 0;
 764
 765     curitem = head->firstitem;
 766     while (curitem != NULL)
 767     {
 768         counter++;
 769         curitem = curitem->next;
 770     }
 771
 772     return (counter);
 773 }