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