src/aklog/linked_list.c

   1 /*
   2  * $Id$
   3  *
   4  * This file contains general linked list routines.
   5  *
   6  * Copyright 1990,1991 by the Massachusetts Institute of Technology
   7  * For distribution and copying rights, see the file "mit-copyright.h"
   8  */
   9
  10 #if !defined(lint) && !defined(SABER)
  11 static char *rcsid_list_c = "$Id$";
  12 #endif /* lint || SABER */
  13
  14 #include <stdio.h>
  15 #include "linked_list.h"
  16
  17 #ifndef NULL
  18 #define NULL 0
  19 #endif
  20
  21 #ifndef TRUE
  22 #define TRUE 1
  23 #endif
  24
  25 #ifndef FALSE
  26 #define FALSE 0
  27 #endif
  28
  29 char *calloc();
  30
  31 #ifdef __STDC__
  32 void ll_init(linked_list *list)
  33   /*
  34    * Requires:
  35    *   List must point to a linked list structure.  It is not acceptable
  36    *   to pass a null pointer to this routine.
  37    * Modifies:
  38    *   list
  39    * Effects:
  40    *   Initializes the list to be one with no elements.  If list is
  41    *   NULL, prints an error message and causes the program to crash.
  42    */
  43 #else
  44 void ll_init(list)
  45   linked_list *list;
  46 #endif /* __STDC__ */
  47 {
  48     if (list == NULL) {
  49         fprintf(stderr, "Error: calling ll_init with null pointer.\n");
  50         abort();
  51     }
  52
  53     /* This sets everything to zero, which is what we want. */
  54 #ifdef WINDOWS
  55         memset(list, 0, sizeof(linked_list));
  56 #else
  57     bzero((char *)list, sizeof(linked_list));
  58 #endif /* WINDOWS */
  59 }
  60
  61 #ifdef __STDC__
  62 ll_node *ll_add_node(linked_list *list, ll_end which_end)
  63   /*
  64    * Modifies:
  65    *   list
  66    * Effects:
  67    *   Adds a node to one end of the list (as specified by which_end)
  68    *   and returns a pointer to the node added.  which_end is of type
  69    *   ll_end and should be either ll_head or ll_tail as specified in
  70    *   list.h.  If there is not enough memory to allocate a node,
  71    *   the program returns NULL.
  72    */
  73 #else
  74 ll_node *ll_add_node(list, which_end)
  75   linked_list *list;
  76   ll_end which_end;
  77 #endif /* __STDC__ */
  78 {
  79     ll_node *node = NULL;
  80
  81     if ((node = (ll_node *)calloc(1, sizeof(ll_node))) != NULL) {
  82         if (list->nelements == 0) {
  83             list->first = node;
  84             list->last = node;
  85             list->nelements = 1;
  86         }
  87         else {
  88             switch (which_end) {
  89               case ll_head:
  90                 list->first->prev = node;
  91                 node->next = list->first;
  92                 list->first = node;
  93                 break;
  94               case ll_tail:
  95                 list->last->next = node;
  96                 node->prev = list->last;
  97                 list->last = node;
  98                 break;
  99               default:
 100                 fprintf(stderr, "%s%s",
 101                         "ll_add_node got a which_end parameter that ",
 102                         "it can't handle.\n");
 103                 abort();
 104             }
 105             list->nelements++;
 106         }
 107     }
 108
 109     return(node);
 110 }
 111
 112
 113 #ifdef __STDC__
 114 int ll_delete_node(linked_list *list, ll_node *node)
 115   /*
 116    * Modifies:
 117    *   list
 118    * Effects:
 119    *   If node is in list, deletes node and returns LL_SUCCESS.
 120    *   Otherwise, returns LL_FAILURE.  If node contains other data,
 121    *   it is the responsibility of the caller to free it.  Also, since
 122    *   this routine frees node, after the routine is called, "node"
 123    *   won't point to valid data.
 124    */
 125 #else
 126 int ll_delete_node(list, node)
 127   linked_list *list;
 128   ll_node *node;
 129 #endif /* __STDC__ */
 130 {
 131     int status = LL_SUCCESS;
 132     ll_node *cur_node = NULL;
 133     int found = FALSE;
 134
 135     if (list->nelements == 0)
 136         status = LL_FAILURE;
 137     else {
 138         for (cur_node = list->first; (cur_node != NULL) && !found;
 139              cur_node = cur_node->next) {
 140             if (cur_node == node) {
 141
 142                 if (cur_node->prev)
 143                     cur_node->prev->next = cur_node->next;
 144                 else
 145                     list->first = cur_node->next;
 146
 147                 if (cur_node->next)
 148                     cur_node->next->prev = cur_node->prev;
 149                 else
 150                     list->last = cur_node->prev;
 151
 152                 free(cur_node);
 153                 list->nelements--;
 154                 found = TRUE;
 155             }
 156         }
 157     }
 158
 159     if (!found)
 160         status = LL_FAILURE;
 161
 162     return(status);
 163 }
 164
 165
 166 /* ll_add_data is a macro defined in linked_list.h */
 167
 168 /* This routine maintains a list of strings preventing duplication. */
 169 #ifdef __STDC__
 170 int ll_string(linked_list *list, ll_s_action action, char *string)
 171 #else
 172 int ll_string(list, action, string)
 173   linked_list *list;
 174   ll_s_action action;
 175   char *string;
 176 #endif /* __STDC__ */
 177 {
 178     int status = LL_SUCCESS;
 179     ll_node *cur_node;
 180
 181     switch(action) {
 182       case ll_s_check:
 183         /* Scan the list until we find the string in question */
 184         for (cur_node = list->first; cur_node && (status == FALSE);
 185              cur_node = cur_node->next)
 186             status = (strcmp(string, cur_node->data) == 0);
 187         break;
 188       case ll_s_add:
 189         /* Add a string to the list. */
 190         if (!ll_string(list, ll_s_check, string)) {
 191             if (cur_node = ll_add_node(list, ll_tail)) {
 192                 char *new_string;
 193                 if (new_string = (char *)calloc(strlen(string) + 1,
 194                                                 sizeof(char))) {
 195                     strcpy(new_string, string);
 196                     ll_add_data(cur_node, new_string);
 197                 }
 198                 else
 199                     status = LL_FAILURE;
 200             }
 201             else
 202                 status = LL_FAILURE;
 203         }
 204         break;
 205       default:
 206         /* This should never happen */
 207         status = LL_FAILURE;
 208         break;
 209     }
 210
 211     return(status);
 212 }