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