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