home *** CD-ROM | disk | FTP | other *** search
/ Aminet 18 / aminetcdnumber181997.iso / Aminet / text / hyper / hsc_source.lha / hsc / source / ugly / dllist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-21  |  8.9 KB  |  415 lines
  1. /*
  2.  * ugly/dllist.c
  3.  *
  4.  * double linked list processing functions
  5.  *
  6.  * Copyright (C) 1994,95,96  Thomas Aglassinger
  7.  *
  8.  * This program is free software; you can redistribute it and/or modify
  9.  * it under the terms of the GNU General Public License as published by
  10.  * the Free Software Foundation; either version 2 of the License, or
  11.  * (at your option) any later version.
  12.  *
  13.  * This program is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.  * GNU General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU General Public License
  19.  * along with this program; if not, write to the Free Software
  20.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  *
  22.  * updated: 11-Sep-1996
  23.  * created:  1-Mar-1994
  24.  *
  25.  *---------------------------------------------------------
  26.  */
  27.  
  28. #include <stdlib.h>
  29. #include <stdio.h>
  30.  
  31. #include "utypes.h"
  32. #include "umemory.h"
  33.  
  34. /* include header file without external prototypes */
  35. #define NOEXTERN_UGLY_DLLIST_H
  36. #include "dllist.h"
  37.  
  38. /*
  39.  * init_dllist
  40.  *
  41.  * alloc & initialise new double linked list
  42.  *
  43.  * result: ptr to new list
  44.  * errors: return NULL (out of mem)
  45.  *
  46.  */
  47. DLLIST *init_dllist(void (*fn_del_data) (APTR data))
  48. {
  49.     DLLIST *newlist;
  50.  
  51.     newlist =                   /* alloc mem for list */
  52.         umalloc(sizeof(DLLIST));
  53.  
  54.     if (newlist)
  55.     {
  56.         newlist->first = NULL;  /* init new list */
  57.         newlist->last = NULL;
  58.         newlist->entry_num = 0;
  59.         newlist->user_data = NULL;
  60.         newlist->del_data = fn_del_data;
  61.     }
  62.  
  63.     return newlist;             /* return new list */
  64. }
  65.  
  66. /*
  67.  * new_dlnode()
  68.  *
  69.  * alloc & init new double linked list node
  70.  *
  71.  * result: new list node
  72.  * errors: return NULL (out of mem)
  73.  *
  74.  */
  75. DLNODE *new_dlnode(void)
  76. {
  77.     DLNODE *newnode;
  78.  
  79.     newnode =                   /* alloc mem for new node */
  80.         umalloc(sizeof(DLNODE));
  81.  
  82.     if (newnode)
  83.     {                           /* alloc successful? */
  84.         newnode->prev = NULL;   /* Y-> init node */
  85.         newnode->next = NULL;
  86.         newnode->data = NULL;
  87.     }
  88.  
  89.     return newnode;             /* return newnode */
  90. }
  91.  
  92. /* 
  93.  * detach_dlnode()
  94.  *
  95.  * remove entry from double linked list,
  96.  * but do not delete the entries data
  97.  *
  98.  */
  99. APTR detach_dlnode(DLLIST * list, DLNODE * node)
  100. {
  101.     APTR nd_data = NULL;
  102.  
  103.     if (list && node)
  104.     {                           /* list & node node defined? */
  105.         nd_data = node->data;   /*     remeber data */
  106.         if (node->prev)         /*     remove node from list */
  107.             node->prev->next = node->next;
  108.         else
  109.             list->first = node->next;
  110.         list->entry_num--;
  111.  
  112.         if (node->next)
  113.             node->next->prev = node->prev;
  114.         else
  115.             list->last = node->prev;
  116.  
  117.         ufree(node);            /*     free node */
  118.     }
  119.  
  120.     return nd_data;
  121. }
  122.  
  123. /* 
  124.  * del_dlnode()
  125.  *
  126.  * remove entry from double linked list
  127.  *
  128.  */
  129. void del_dlnode(DLLIST * list, DLNODE * node)
  130. {
  131.  
  132.     if (list && node)
  133.     {                           /* list & node node defined? */
  134.         void (*dd) (APTR) = list->del_data;
  135.  
  136.         if (node->data)         /* Y-> call destructor */
  137.             if (dd)
  138.                 (*dd) (node->data);
  139.  
  140.         if (node->prev)         /*     remove node from list */
  141.             node->prev->next = node->next;
  142.         else
  143.             list->first = node->next;
  144.         list->entry_num--;
  145.  
  146.         if (node->next)
  147.             node->next->prev = node->prev;
  148.         else
  149.             list->last = node->prev;
  150.  
  151.         node->prev = NULL;      /*     clear node */
  152.         node->next = NULL;
  153.         node->data = NULL;
  154.  
  155.         ufree(node);            /*     free node */
  156.     }
  157. }
  158.  
  159. /*
  160.  * del_all_dlnodes()
  161.  *
  162.  * remove all nodes from a list
  163.  */
  164. VOID del_all_dlnodes(DLLIST * list)
  165. {
  166.     while (list->first)
  167.         del_dlnode(list, list->first);
  168. }
  169.  
  170. /*
  171.  * ins_dlnode()
  172.  *
  173.  * insert a data entry into double linked list BEFORE node
  174.  *
  175.  */
  176. DLNODE *ins_dlnode(DLLIST * list, DLNODE * node, APTR data)
  177. {
  178.     DLNODE *newnode = NULL;
  179.  
  180.     if (list)
  181.     {
  182.         newnode = new_dlnode();
  183.  
  184.         if (newnode)
  185.         {
  186.             newnode->data = data;
  187.             list->entry_num++;
  188.  
  189.             if (node)
  190.             {
  191.                 if (list->first == node)
  192.                 {
  193.                     /*
  194.                      * insert as first entry
  195.                      */
  196.                     list->first = newnode;
  197.                 }
  198.                 else
  199.                 {
  200.                     /*
  201.                      * insert somewhere in the list
  202.                      */
  203.                     node->prev->next = newnode;
  204.                     newnode->prev = node->prev;
  205.                 }
  206.                 node->prev = newnode;
  207.                 newnode->next = node;
  208.             }
  209.             else
  210.             {                   /* append as last entry */
  211.                 if (list->last)
  212.                     list->last->next = newnode;
  213.                 newnode->prev = list->last;
  214.                 list->last = newnode;
  215.             }
  216.  
  217.             if (list->first == NULL)
  218.                 list->first = newnode;
  219.             if (list->last == NULL)
  220.                 list->last = newnode;
  221.         }
  222.     }
  223.  
  224.     return newnode;
  225. }
  226.  
  227. /*
  228.  * app_dlnode
  229.  *
  230.  * append new node to list (at end)
  231.  *
  232.  * result:
  233.  * errors: return NULL (out of mem)
  234.  *
  235.  */
  236. DLNODE *app_dlnode(DLLIST * list, APTR data)
  237. {
  238.     DLNODE *newnode = NULL;
  239.  
  240.     if (list)
  241.         newnode = ins_dlnode(list, NULL, data);
  242.  
  243.     return newnode;
  244. }
  245.  
  246. /*
  247.  * add_dlnode
  248.  *
  249.  * add new node to list (as first entry)
  250.  *
  251.  * result: new node
  252.  * errors: return NULL (out of mem)
  253.  *
  254.  */
  255. DLNODE *add_dlnode(DLLIST * list, APTR data)
  256. {
  257.     DLNODE *newnode = NULL;
  258.  
  259.     if (list)
  260.         newnode = ins_dlnode(list, list->first, data);
  261.  
  262.     return newnode;
  263. }
  264.  
  265. /*
  266.  * del_dllist
  267.  *
  268.  * free whole list and its nodes and data
  269.  *
  270.  */
  271. void del_dllist(DLLIST * list)
  272. {
  273.     if (list)
  274.     {
  275.         /* remove all nodes */
  276.         while (list->first)
  277.             del_dlnode(list, list->first);
  278.  
  279.         /* remove list structure */
  280.         list->first = NULL;
  281.         list->last = NULL;
  282.         list->entry_num = 0;
  283.         list->user_data = NULL;
  284.         list->del_data = NULL;
  285.         ufree(list);
  286.     }
  287. }
  288.  
  289. /*
  290.  * do_dllist
  291.  *
  292.  * call a function with every node of a list
  293.  */
  294. void do_dllist(DLLIST * list, void (*func) (APTR data))
  295. {
  296.     if (list)
  297.     {
  298.         DLNODE *nd = list->first;
  299.  
  300.         while (nd)
  301.         {
  302.             (*func) (nd->data);
  303.             nd = nd->next;
  304.         }
  305.     }
  306. }
  307.  
  308. /*
  309.  * fprintf_dllist
  310.  *
  311.  * output a whole list to a stream
  312.  * (more or less only a debugging function)
  313.  */
  314. void fprintf_dllist(FILE * stream, DLLIST * list,
  315.                     void (*fprintf_data) (FILE * stream, APTR data))
  316. {
  317.     if (list)
  318.     {
  319.         DLNODE *node;
  320.         ULONG i = 1;
  321.  
  322.         node = list->first;
  323.         if (node)
  324.         {
  325.             while (node)
  326.             {
  327.                 fprintf(stream, "%4lu: ", i++);
  328.                 if (fprintf_data)
  329.                     (*fprintf_data) (stream, node->data);
  330.                 else
  331.                     fprintf(stream, "%s\n", (STRPTR) node->data);
  332.                 node = node->next;
  333.             }
  334.         }
  335.         else
  336.             fprintf(stream, "  [empty list]\n");
  337.     }
  338.     else
  339.         fprintf(stream, "  [no list]\n");
  340. }
  341.  
  342. /*
  343.  * find_dlnode
  344.  *
  345.  * search for specific data in a list, starting at a specific node
  346.  *
  347.  * params: start....startnode to begin search with
  348.  *         data.....data to be found
  349.  *         compare..funtions that compares two data-items;
  350.  *                  returns -1 if items are equal, else 0
  351.  * result: ptr to node that contains requested data
  352.  *         or NULL if not found
  353.  */
  354. DLNODE *find_dlnode(DLNODE * start, APTR data,
  355.                     int (*compare) (APTR cmp_data, APTR list_data))
  356. {
  357.     DLNODE *search = start;
  358.     int found = 0;
  359.  
  360.     while (search && !(found))
  361.     {
  362.         found = (*compare) (data, search->data);
  363.         if (!found)
  364.             search = search->next;
  365.     }
  366.  
  367.     return search;
  368. }
  369.  
  370. /*
  371.  * find_dlnode_bw
  372.  *
  373.  * search for specific data in a list, starting at a specific node,
  374.  * search directions set to backwards
  375.  *
  376.  * params: start....startnode to begin search with
  377.  *         data.....data to be found
  378.  *         compare..funtions that compares two data-items;
  379.  *                  returns -1 if items are equal, else 0
  380.  * result: ptr to node that contains requested data
  381.  *         or NULL if not found
  382.  */
  383. DLNODE *find_dlnode_bw(DLNODE * start, APTR data,
  384.                     int (*compare) (APTR cmp_data, APTR list_data))
  385. {
  386.     DLNODE *search = start;
  387.     int found = 0;
  388.  
  389.     while (search && !(found))
  390.     {
  391.         found = (*compare) (data, search->data);
  392.         if (!found)
  393.             search = search->prev;
  394.     }
  395.  
  396.     return search;
  397. }
  398.  
  399. /*
  400.  * empty_dllist
  401.  *
  402.  * check if a list is empty
  403.  *
  404.  * params: list..list to check for emptyness
  405.  * result: TRUE, if list contains no nodes
  406.  */
  407. BOOL empty_dllist(DLLIST * list)
  408. {
  409.     if (list->first)
  410.         return TRUE;
  411.     else
  412.         return FALSE;
  413. }
  414.  
  415.