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     ll_node *cur_node = NULL;
 105
 106     if (list->nelements == 0)
 107         return LL_FAILURE;
 108
 109     for (cur_node = list->first; cur_node != NULL; cur_node = cur_node->next) {
 110         if (cur_node == node) {
 111
 112             if (cur_node->prev)
 113                 cur_node->prev->next = cur_node->next;
 114             else
 115                 list->first = cur_node->next;
 116
 117             if (cur_node->next)
 118                 cur_node->next->prev = cur_node->prev;
 119             else
 120                 list->last = cur_node->prev;
 121
 122             free(cur_node);
 123             list->nelements--;
 124             return LL_SUCCESS;
 125         }
 126     }
 127
 128     return LL_FAILURE;
 129 }
 130
 131
 132 /* ll_add_data is a macro defined in linked_list.h */
 133
 134 /* This routine maintains a list of strings preventing duplication. */
 135 int ll_string(linked_list *list, ll_s_action action, char *string)
 136 {
 137     int status = LL_SUCCESS;
 138     ll_node *cur_node;
 139
 140     switch(action) {
 141       case ll_s_check:
 142         /* Scan the list until we find the string in question */
 143         for (cur_node = list->first; cur_node && (status == FALSE);
 144              cur_node = cur_node->next)
 145             status = (strcmp(string, cur_node->data) == 0);
 146         break;
 147       case ll_s_add:
 148         /* Add a string to the list. */
 149         if (!ll_string(list, ll_s_check, string)) {
 150             if ((cur_node = ll_add_node(list, ll_tail))) {
 151                 char *new_string;
 152                 if ((new_string = calloc(strlen(string) + 1, sizeof(char)))) {
 153                     strcpy(new_string, string);
 154                     ll_add_data(cur_node, new_string);
 155                 }
 156                 else
 157                     status = LL_FAILURE;
 158             }
 159             else
 160                 status = LL_FAILURE;
 161         }
 162         break;
 163       default:
 164         /* This should never happen */
 165         status = LL_FAILURE;
 166         break;
 167     }
 168
 169     return(status);
 170 }