home *** CD-ROM | disk | FTP | other *** search
/ Magazyn Amiga 5 / MA_Cover_5.iso / ppc / atari / atari800-0.8.6 / list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-05-10  |  9.9 KB  |  506 lines
  1. /*
  2.  * Module:       Linked List
  3.  * Author:       David J. Firth
  4.  * Date Written: A long time ago!
  5.  * Version:      1.0
  6.  *
  7.  * Description
  8.  * -----------
  9.  *
  10.  * This module contains a series of general purpose routines for the
  11.  * manipulation of Linked Lists.
  12.  */
  13.  
  14. /**
  15.   The "List" library contains a set of routines that create and
  16.   manipulate Linked Lists.
  17.   **/
  18.  
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21.  
  22. static char *rcsid = "$Id: list.c,v 1.3 1998/02/21 14:56:45 david Exp $";
  23.  
  24. #include "list.h"
  25.  
  26. #define    FALSE 0
  27. #define    TRUE 1
  28.  
  29. /*+
  30.    Creates an empty List
  31.  
  32.    List *ListCreate Returns an empty list.
  33.    + */
  34.  
  35. List *ListCreate(void)
  36. {
  37.     List *list;
  38.  
  39.     list = (List *) malloc(sizeof(List));
  40.     if (list) {
  41.         list->head = NULL;
  42.         list->tail = NULL;
  43.         list->current = NULL;
  44.         list->next = NULL;
  45.     }
  46.     return list;
  47. }
  48.  
  49. /*+
  50.    Releases all storages allocated by the supplied List. The data contained
  51.    in each node should be released by the function specified in the
  52.    argument list.
  53.  
  54.    int ListFree returns TRUE on success and FALSE on failure.
  55.  
  56.    List *list The List to deallocate.
  57.  
  58.    void (*func)() The function that deallocates the data. The deallocation
  59.    function is called with a single argument (the data). The free() function
  60.    can be specified if the data is a pointer to an array of characters. A
  61.    NULL value can be supplied if a deallocation function is not necessary.
  62.    + */
  63.  
  64. int ListFree(List * list, void (*func) ())
  65. {
  66.     struct list_entry *temp;
  67.     struct list_entry *next;
  68.  
  69.     int ok = FALSE;
  70.  
  71.     if (list) {
  72.         for (temp = list->head; temp; temp = next) {
  73.             next = temp->next;
  74.             if (func)
  75.                 (*func) (temp->data);
  76.             free(temp);
  77.         }
  78.  
  79.         free(list);
  80.  
  81.         ok = TRUE;
  82.     }
  83.     return ok;
  84. }
  85.  
  86. /*+
  87.    Adds the supplied data item to Head of List.
  88.  
  89.    int ListAddHead Returns TRUE on success and FALSE on failure.
  90.  
  91.    List *list The list that the data item is to be added to.
  92.  
  93.    void *data Data item that is added to the list. This can be a pointer to
  94.    anything, and with care a simple integer value.
  95.    + */
  96.  
  97. int ListAddHead(List * list, void *data)
  98. {
  99.     struct list_entry *temp;
  100.  
  101.     int ok = FALSE;
  102.  
  103.     if (list) {
  104.         temp = (struct list_entry *) malloc(sizeof(struct list_entry));
  105.         if (temp) {
  106.             temp->prev = NULL;
  107.             temp->next = list->head;
  108.             temp->data = data;
  109.  
  110.             if (list->head) {
  111.                 list->head->prev = temp;
  112.                 list->head = temp;
  113.             }
  114.             else {
  115.                 list->head = list->tail = temp;
  116.             }
  117.  
  118.             ok = TRUE;
  119.         }
  120.     }
  121.     return ok;
  122. }
  123.  
  124. /*+
  125.    Adds the supplied data item to Tail of List.
  126.  
  127.    int ListAddTail Returns TRUE on success and FALSE on failure.
  128.  
  129.    List *list The list that the data item is to be added to.
  130.  
  131.    void *data Data item that is added to the list. This can be a pointer to
  132.    anything, and with care a simple integer value.
  133.    + */
  134.  
  135. int ListAddTail(List * list, void *data)
  136. {
  137.     struct list_entry *temp;
  138.  
  139.     int ok = FALSE;
  140.  
  141.     if (list) {
  142.         temp = (struct list_entry *) malloc(sizeof(struct list_entry));
  143.         if (temp) {
  144.             temp->prev = list->tail;
  145.             temp->next = NULL;
  146.             temp->data = data;
  147.  
  148.             if (list->tail) {
  149.                 list->tail->next = temp;
  150.                 list->tail = temp;
  151.             }
  152.             else {
  153.                 list->head = list->tail = temp;
  154.             }
  155.  
  156.             ok = TRUE;
  157.         }
  158.     }
  159.     return ok;
  160. }
  161.  
  162. /*+
  163.    Merges list1 and list2. This is performed by appending list2 onto
  164.    list1. On return from this routine, list2 will have been de-allocated
  165.    and the return value will be the same as list1.
  166.  
  167.    List *ListMerge list1 with list2 appended.
  168.  
  169.    List *list1 This is the primary list.
  170.  
  171.    List *list2 This is list that will be appended to the primary list.
  172.    + */
  173.  
  174. List *ListMerge(List * list1, List * list2)
  175. {
  176.     if (!list1->head) {
  177.         list1->head = list2->head;
  178.         list1->tail = list2->tail;
  179.     }
  180.     else if (list2->head) {
  181.         list1->tail->next = list2->head;
  182.         list2->head->prev = list1->tail;
  183.         list1->tail = list2->tail;
  184.     }
  185.     list2->head = NULL;
  186.     list2->tail = NULL;
  187.  
  188.     ListFree(list2, NULL);
  189.  
  190.     return list1;
  191. }
  192.  
  193. /*+
  194.    ListSort() is called to sort a list into order.
  195.  
  196.    List *list List that is to be sorted.
  197.  
  198.    int (*func)() Pointer to a function that compares two entries in the list.
  199.    The function should return -1 if entry1 < entry2, 0 if entry1 = entry2
  200.    and +1 if entry1 > entry2.
  201.    + */
  202.  
  203. void ListSort(List * list, int (*func) ())
  204. {
  205.     struct list_entry *next;
  206.     struct list_entry *temp;
  207.  
  208.     void *data;
  209.     int done;
  210.     int result;
  211.  
  212.     if (list->head) {
  213.         done = FALSE;
  214.  
  215.         while (!done) {
  216.             done = TRUE;
  217.  
  218.             for (temp = list->head, next = temp->next; next; temp = next, next = temp->next) {
  219.                 result = (*func) (temp->data, next->data);
  220.                 if (result == 1) {
  221.                     data = temp->data;
  222.                     temp->data = next->data;
  223.                     next->data = data;
  224.  
  225.                     done = FALSE;
  226.                 }
  227.             }
  228.         }
  229.     }
  230. }
  231.  
  232. /*+
  233.    Resets current node back to head node.
  234.  
  235.    int ListReset returns TRUE on success and FALSE on failure.
  236.  
  237.    List *list The list to be reset.
  238.    + */
  239.  
  240. int ListReset(List * list)
  241. {
  242.     int status = FALSE;
  243.  
  244.     if (list) {
  245.         list->current = NULL;
  246.         list->prev = list->tail;
  247.         list->next = list->head;
  248.         status = TRUE;
  249.     }
  250.     return status;
  251. }
  252.  
  253. /*+
  254.    This routine is used to traverse a list. Each time it is called the
  255.    next item in the list is returned. If ListReset() is called beforehand
  256.    then ListTraverse() returns the head node.
  257.  
  258.    int ListTraverse Returns TRUE indicates that the next entry has been
  259.    returned. FALSE indicates that the end of the list has been
  260.    reached and no entry has been returned.
  261.  
  262.    List *list The list to be traversed.
  263.  
  264.    void **entry This is an output variable and is used to store the address
  265.    of the next data item in the list.
  266.    + */
  267.  
  268. int ListTraverse(List * list, void **entry /*+ Current Entry + */ )
  269. {
  270.     struct list_entry *next;
  271.  
  272.     int status;
  273.  
  274.     next = list->next;
  275.     if (next) {
  276.         *entry = next->data;
  277.         list->current = next;
  278.         list->prev = next->prev;
  279.         list->next = next->next;
  280.         status = TRUE;
  281.     }
  282.     else {
  283.         status = FALSE;
  284.     }
  285.  
  286.     return status;
  287. }
  288.  
  289. /*+
  290.    This routine is used to traverse a list. Each time it is called the
  291.    previous item in the list is returned. If ListReset() is called
  292.    beforehand then ListTraverseBck() returns the tail node.
  293.  
  294.    int ListTraverseBck Returns TRUE indicates that the previous entry has
  295.    been returned. FALSE indicates that the begining of the list has been
  296.    reached and no entry has been returned.
  297.  
  298.    List *list The list to be traversed.
  299.  
  300.    void **entry This is an output variable and is used to store the address
  301.    of the previous data item in the list.
  302.    + */
  303.  
  304. int ListTraverseBck(List * list, void **entry /*+ Current Entry + */ )
  305. {
  306.     struct list_entry *prev;
  307.  
  308.     int status;
  309.  
  310.     prev = list->prev;
  311.     if (prev) {
  312.         *entry = prev->data;
  313.         list->current = prev;
  314.         list->prev = prev->prev;
  315.         list->next = prev->next;
  316.         status = TRUE;
  317.     }
  318.     else {
  319.         status = FALSE;
  320.     }
  321.  
  322.     return status;
  323. }
  324.  
  325. /*
  326.    =====================================================
  327.    Routines to be called from within a ListTraverse Loop
  328.    =====================================================
  329.  */
  330.  
  331. /*+
  332.    Deletes the current entry in the supplied linked list. Used in
  333.    conjunction with ListTraverse().
  334.  
  335.    int ListDeleteEntry Returns TRUE on success and FALSE on failure.
  336.  
  337.    List *list The current entry in this list will be deleted.
  338.    + */
  339.  
  340. int ListDeleteEntry(List * list)
  341. {
  342.     int status = FALSE;
  343.  
  344.     if (list) {
  345.         struct list_entry *current;
  346.  
  347.         current = list->current;
  348.         if (current) {
  349.             struct list_entry *prev;
  350.             struct list_entry *next;
  351.  
  352.             prev = current->prev;
  353.             next = current->next;
  354.  
  355.             free(current);
  356.  
  357.             if (prev)
  358.                 prev->next = next;
  359.             else
  360.                 list->head = next;
  361.  
  362.             if (next)
  363.                 next->prev = prev;
  364.             else
  365.                 list->tail = prev;
  366.  
  367.             status = TRUE;
  368.         }
  369.     }
  370.     return status;
  371. }
  372.  
  373. /*+
  374.    Inserts the supplied data item just before the current entry in the
  375.    supplied list. Used in conjunction with ListTraverse().
  376.  
  377.    int ListInsertBefore Returns TRUE on success and FALSE on failure.
  378.  
  379.    List *list The data item will be inserted before the current entry
  380.    in this list.
  381.  
  382.    void *data This is the data item that will be inserted into the list.
  383.    + */
  384.  
  385. int ListInsertBefore(List * list, void *data)
  386. {
  387.     int status = FALSE;
  388.  
  389.     if (list) {
  390.         if (list->current) {
  391.             struct list_entry *current;
  392.             struct list_entry *prev;
  393.             struct list_entry *temp;
  394.  
  395.             current = list->current;
  396.             prev = current->prev;
  397.  
  398.             temp = (struct list_entry *) malloc(sizeof(struct list_entry));
  399.             if (temp) {
  400.                 temp->prev = prev;
  401.                 temp->next = current;
  402.                 temp->data = data;
  403.  
  404.                 current->prev = temp;
  405.  
  406.                 if (prev) {
  407.                     prev->next = temp;
  408.                 }
  409.                 else {
  410.                     list->head = temp;
  411.                 }
  412.  
  413.                 status = TRUE;
  414.             }
  415.         }
  416.     }
  417.     return status;
  418. }
  419.  
  420. /*+
  421.    Inserts the supplied data item just after the current entry in the
  422.    supplied list. Used in conjunction with ListTraverse().
  423.  
  424.    int ListInsertAfter Returns TRUE on success and FALSE on failure.
  425.  
  426.    List *list The data item will be inserted after the current entry
  427.    in this list.
  428.  
  429.    void *data This is the data item that will be inserted into the list.
  430.    + */
  431.  
  432. int ListInsertAfter(List * list, void *data)
  433. {
  434.     int status = FALSE;
  435.  
  436.     if (list) {
  437.         if (list->current) {
  438.             struct list_entry *current;
  439.             struct list_entry *next;
  440.             struct list_entry *temp;
  441.  
  442.             current = list->current;
  443.             next = current->next;
  444.  
  445.             temp = (struct list_entry *) malloc(sizeof(struct list_entry));
  446.             if (temp) {
  447.                 temp->prev = current;
  448.                 temp->next = next;
  449.                 temp->data = data;
  450.  
  451.                 current->next = temp;
  452.  
  453.                 if (next) {
  454.                     next->prev = temp;
  455.                 }
  456.                 else {
  457.                     list->tail = temp;
  458.                 }
  459.  
  460.                 status = TRUE;
  461.             }
  462.         }
  463.     }
  464.     return status;
  465. }
  466.  
  467. /*+
  468.    Swaps two adjacent items in the list. The two items that are swapped are
  469.    the current entry and the next entry. Used in conjunction with
  470.    ListTraverse().
  471.  
  472.    int ListSwapEntry Returns TRUE on success and FALSE on failure.
  473.  
  474.    List *list List containing the items to be swapped.
  475.    + */
  476.  
  477. int ListSwapEntry(List * list)
  478. {
  479.     int status = FALSE;
  480.  
  481.     if (list) {
  482.         if (list->current) {
  483.             struct list_entry *current;
  484.  
  485.             current = list->current;
  486.  
  487.             if (current) {
  488.                 struct list_entry *prev;
  489.  
  490.                 prev = current->prev;
  491.  
  492.                 if (prev) {
  493.                     void *temp;
  494.  
  495.                     temp = prev->data;
  496.                     prev->data = current->data;
  497.                     current->data = temp;
  498.  
  499.                     status = TRUE;
  500.                 }
  501.             }
  502.         }
  503.     }
  504.     return status;
  505. }
  506.