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