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 *dumitem;
 277
 278     dumitem = (listitem *) malloc (sizeof (listitem));
 279     dumitem->itemptr = newitem;
 280     dumitem->next = NULL;
 281
 282 #ifdef FASTLLIST
 283     if (head->lastptr == NULL)
 284         head->firstitem = dumitem;
 285     else
 286         head->lastptr->next = dumitem;
 287     head->lastptr = dumitem;
 288 #else
 289     listitem *curitem,
 290       *previtem;
 291
 292     if (head->firstitem == NULL)
 293     {
 294         head->firstitem = dumitem;
 295         return (0);
 296     }
 297
 298     previtem = NULL;
 299     curitem = head->firstitem;
 300     while (curitem != NULL)
 301     {
 302         previtem = curitem;
 303         curitem = curitem->next;
 304     }
 305     previtem->next = dumitem;
 306 #endif
 307
 308     return (0);
 309 }
 310
 311
 312 /*
 313 **++
 314 **  FUNCTIONAL DESCRIPTION:
 315 **
 316 **      unshiftll: add item to the beginning of a linked list
 317 **
 318 **  FORMAL PARAMETERS:
 319 **
 320 **      head: pointer to head of linked list
 321 **      newitem: void-pointer to item that has to be inserted in the list
 322 **
 323 **  RETURN VALUE:
 324 **
 325 **      0 : OK
 326 **      -1: error
 327 **
 328 **--
 329 */
 330 int unshiftll (listheader * head, void * newitem)
 331 {
 332     listitem *dumitem;
 333
 334     dumitem = (listitem *) malloc (sizeof (listitem));
 335     dumitem->itemptr = newitem;
 336     dumitem->next = head->firstitem;
 337     head->firstitem = dumitem;
 338
 339 #ifdef FASTLLIST
 340     if (head->lastptr == NULL)
 341         head->lastptr = dumitem;
 342     head->curptr = NULL;
 343     head->curnr = -1;
 344 #endif
 345
 346     return (0);
 347 }
 348
 349
 350 /*
 351 **++
 352 **  FUNCTIONAL DESCRIPTION:
 353 **
 354 **      searchll : find an item in a linked list
 355 **
 356 **  FORMAL PARAMETERS:
 357 **
 358 **      head: pointer to listhead
 359 **      item: pointer to item to search for
 360 **      compfunction: pointer to a function that can compare to items
 361 **                    it should return -1, 0, 1. to indicate that the
 362 **                    first item is smaller, equal, larger than the second
 363 **
 364 **  RETURN VALUE:
 365 **
 366 **      pointer to the found item, or NULL if not found
 367 **
 368 **--
 369 */
 370 void * searchll (listheader * head, void * item, int (* compfunction)())
 371 {
 372     listitem * curitem;
 373     int compresult;
 374
 375     curitem = head->firstitem;
 376     while (curitem != NULL)
 377     {
 378         compresult = (* compfunction)(curitem->itemptr, item);
 379         if (compresult == 0)
 380         {
 381             return (curitem->itemptr);
 382         }
 383         else if (compresult > 0)
 384         {
 385             return (NULL);
 386         }
 387         curitem = curitem->next;
 388     }
 389     return (NULL);
 390 }
 391
 392
 393 /*
 394 **++
 395 **  FUNCTIONAL DESCRIPTION:
 396 **
 397 **      emptyll: remove all items from a linked list
 398 **
 399 **  FORMAL PARAMETERS:
 400 **
 401 **      head: pointer to the listheader
 402 **      delfunction: pointer to a function that is called to delete each
 403 **                   item from the list, it is called with 1 parameter,
 404 **                   a void-pointer to the item, no return-value is expected
 405 **
 406 **  RETURN VALUE:
 407 **
 408 **      0: OK
 409 **      -1: error
 410 **
 411 **--
 412 */
 413 int emptyll (listheader * head, void (* delfunction)(void *))
 414 {
 415     listitem * curitem,
 416              * dumitem;
 417
 418     if (head == NULL)
 419     {
 420         return (0);
 421     }
 422
 423     curitem = head->firstitem;
 424     while (curitem != NULL)
 425     {
 426         (* delfunction)(curitem->itemptr);
 427         dumitem = curitem->next;
 428         free (curitem);
 429         curitem = dumitem;
 430     }
 431     head->firstitem = NULL;
 432
 433 #ifdef FASTLLIST
 434     head->lastptr = NULL;
 435     head->curptr = NULL;
 436     head->curnr = -1;
 437 #endif
 438
 439     return (0);
 440 }
 441
 442
 443 /*
 444 **++
 445 **  FUNCTIONAL DESCRIPTION:
 446 **
 447 **      doll: execute a function for all the items from a linked list
 448 **
 449 **  FORMAL PARAMETERS:
 450 **
 451 **      head: pointer to the listheader
 452 **      dofunction: pointer to a function that is called for each
 453 **                   item from the list, it is called with 1 parameter,
 454 **                   a void-pointer to the item, no return-value is expected
 455 **
 456 **  RETURN VALUE:
 457 **
 458 **      0: OK
 459 **      -1: error
 460 **
 461 **--
 462 */
 463 int doll (listheader * head, void (* dofunction)())
 464 {
 465     listitem * curitem;
 466
 467     curitem = head->firstitem;
 468     while (curitem != NULL)
 469     {
 470         (* dofunction)(curitem->itemptr);
 471         curitem = curitem->next;
 472     }
 473     return (0);
 474 }
 475
 476
 477 /*
 478 **++
 479 **  FUNCTIONAL DESCRIPTION:
 480 **
 481 **      llitembynr: return the data for item nr from the list
 482 **
 483 **  FORMAL PARAMETERS:
 484 **
 485 **      head: pointer to the listheader
 486 **      nr : item to return, the first item of the list = 1
 487 **
 488 **  RETURN VALUE:
 489 **
 490 **      pointer to data
 491 **      NULL on error
 492 **
 493 **--
 494 */
 495 void * llitembynr (listheader * head, int nr)
 496 {
 497     listitem * curitem;
 498     int counter;
 499
 500     if (head == NULL)
 501     {
 502         return (NULL);
 503     }
 504
 505 #ifdef FASTLLIST
 506     if (head->curnr == (nr - 1))
 507         curitem = head->curptr->next;
 508     else if (head->curnr == nr)
 509         curitem = head->curptr;
 510     else
 511     {
 512 #endif
 513         curitem = head->firstitem;
 514         counter = 1;
 515         while ((curitem != NULL) && (counter != nr))
 516         {
 517             counter++;
 518             curitem = curitem->next;
 519         }
 520 #ifdef FASTLLIST
 521     }
 522 #endif
 523
 524     if (curitem != NULL)
 525     {
 526 #ifdef FASTLLIST
 527         head->curnr = nr;
 528         head->curptr = curitem;
 529 #endif
 530         return (curitem->itemptr);
 531     }
 532     return (NULL);
 533 }
 534
 535
 536 /*
 537 **++
 538 **  FUNCTIONAL DESCRIPTION:
 539 **
 540 **      llrembynr: remove item nr from the list and return pointer to
 541 **                 the data from this item
 542 **
 543 **  FORMAL PARAMETERS:
 544 **
 545 **      head: pointer to the listheader
 546 **      nr : item to remove, the first item of the list = 1
 547 **
 548 **  RETURN VALUE:
 549 **
 550 **      pointer to data
 551 **      NULL on error
 552 **
 553 **--
 554 */
 555 void * llrembynr (listheader * head, int nr)
 556 {
 557     listitem * previtem = NULL,
 558         * curitem;
 559     int counter;
 560     void * data;
 561
 562     if (head == NULL)
 563     {
 564         return (NULL);
 565     }
 566
 567 #ifdef FASTLLIST
 568     // use information from the last llitembynr
 569     if (head->curnr == (nr - 1))
 570     {
 571         previtem = head->curptr;
 572         curitem = head->curptr->next;
 573     }
 574     else
 575     {
 576 #endif
 577         curitem = head->firstitem;
 578         counter = 1;
 579         while ((curitem != NULL) && (counter != nr))
 580         {
 581             counter++;
 582             previtem = curitem;
 583             curitem = curitem->next;
 584         }
 585 #ifdef FASTLLIST
 586     }
 587 #endif
 588
 589     if (curitem != NULL)
 590     {
 591         if (previtem == NULL)
 592         {
 593             head->firstitem = curitem->next;
 594         }
 595         else
 596         {
 597             previtem->next = curitem->next;
 598         }
 599 #ifdef FASTLLIST
 600         if (curitem == head->lastptr)
 601             head->lastptr = previtem;
 602         head->curptr = NULL;
 603         head->curnr = -1;
 604 #endif
 605
 606         data = curitem->itemptr;
 607         free (curitem);
 608         return (data);
 609     }
 610
 611     return (NULL);
 612 }
 613
 614
 615 /*
 616 **++
 617 **  FUNCTIONAL DESCRIPTION:
 618 **
 619 **      copyll: copy a complete linked list and all the data in it
 620 **
 621 **  FORMAL PARAMETERS:
 622 **
 623 **      head: pointer to the listheader
 624 **      copyfunction: pointer to a function that is called for each
 625 **                    item from the list, it is called with 1 parameter,
 626 **                    a void-pointer to the item.
 627 **                    as return-value, a void pointer to a copy of the input
 628 **                    item is expected
 629 **
 630 **  RETURN VALUE:
 631 **
 632 **      pointer to the head of the copied list
 633 **
 634 **--
 635 */
 636 listheader * copyll (listheader * head, void * (* copyfunction)())
 637 {
 638     listitem * curitem,
 639         * newitem = NULL,
 640         * dumitem;
 641     listheader * newheader;
 642
 643     if (head == NULL)
 644     {
 645         return (NULL);
 646     }
 647
 648     curitem = head->firstitem;
 649     newheader = (listheader *) malloc (sizeof (listheader));
 650     newheader->firstitem = NULL;
 651     while (curitem != NULL)
 652     {
 653         dumitem = (listitem *) malloc (sizeof (listitem));
 654
 655         dumitem->next = NULL;
 656         dumitem->itemptr = (* copyfunction)(curitem->itemptr);
 657         if (newitem == NULL)
 658         {
 659             newheader->firstitem = dumitem;
 660         }
 661         else
 662         {
 663             newitem->next = dumitem;
 664         }
 665         newitem = dumitem;
 666
 667         curitem = curitem->next;
 668     }
 669
 670 #ifdef FASTLLIST
 671     newheader->lastptr = newitem;
 672     newheader->curptr = NULL;
 673     newheader->curnr = -1;
 674 #endif
 675
 676     return (newheader);
 677 }
 678
 679
 680 /*
 681 **++
 682 **  FUNCTIONAL DESCRIPTION:
 683 **
 684 **      getnextll
 685 **
 686 **  FORMAL PARAMETERS:
 687 **
 688 **      head: header of the linked list
 689 **      curptr: pointer to the current item in the list
 690 **
 691 **  RETURN VALUE:
 692 **
 693 **      pointer to the next item in the linked list (the item after curptr)
 694 **      the order of the list is the same order then during inclusion
 695 **      if curptr is not found in the list, or there is no next item, the
 696 **      NULL is returned.
 697 **
 698 **--
 699 */
 700 void * getnextll (listheader * head, void * curptr)
 701 {
 702     listitem * curitem;
 703
 704     curitem = head->firstitem;
 705     while ((curitem != NULL) && (curitem->itemptr != curptr))
 706     {
 707         curitem = curitem->next;
 708     }
 709     if ((curitem == NULL) || (curitem->next == NULL))
 710     {
 711         return (NULL);
 712     }
 713
 714     curitem = curitem->next;
 715     return (curitem->itemptr);
 716 }
 717
 718
 719 /*
 720 **++
 721 **  FUNCTIONAL DESCRIPTION:
 722 **
 723 **      findlastll
 724 **
 725 **  FORMAL PARAMETERS:
 726 **
 727 **      head: header of the linked list
 728 **      checkfunction: function to be called with each item from the list
 729 **            and returning 1 or 0 (1: item we are looking for, 0: not)
 730 **
 731 **  RETURN VALUE:
 732 **
 733 **      number of the last item in the list that makes the checkfunction
 734 **      return 1
 735 **
 736 **--
 737 */
 738 int findlastll (listheader * head, int (* checkfunction)(void*))
 739 {
 740     listitem * curitem;
 741     int theitem = 0,
 742         nr = 1;
 743
 744     curitem = head->firstitem;
 745     while (curitem != NULL)
 746     {
 747         if ((* checkfunction) (curitem->itemptr) == 1)
 748             theitem = nr;
 749
 750         nr++;
 751         curitem = curitem->next;
 752     }
 753
 754     return (theitem);
 755 }
 756
 757
 758 /*
 759 ** returns the number of items in the linked list
 760 */
 761 int lllength (listheader * head)
 762 {
 763     listitem * curitem;
 764     int counter = 0;
 765
 766     curitem = head->firstitem;
 767     while (curitem != NULL)
 768     {
 769         counter++;
 770         curitem = curitem->next;
 771     }
 772
 773     return (counter);
 774 }