src/WINNT/aklog/linked_list.c

   1 /* Copyright 1999, 1991, 1999 by the Massachusetts Institute of Technology.
   2  *
   3  * Permission to use, copy, modify, and distribute this
   4  * software and its documentation for any purpose and without
   5  * fee is hereby granted, provided that the above copyright
   6  * notice appear in all copies and that both that copyright
   7  * notice and this permission notice appear in supporting
   8  * documentation, and that the name of M.I.T. not be used in
   9  * advertising or publicity pertaining to distribution of the
  10  * software without specific, written prior permission.
  11  * M.I.T. makes no representations about the suitability of
  12  * this software for any purpose.  It is provided "as is"
  13  * without express or implied warranty.
  14  */
  15
  16 /* This file contains general linked list routines. */
  17
  18 static const char rcsid[] = "$Id$";
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #include "linked_list.h"
  25
  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 void ll_init(linked_list *list)
  37 {
  38   if (list == NULL)
  39     {
  40       fprintf(stderr, "Error: calling ll_init with null pointer.\n");
  41       abort();
  42     }
  43
  44   list->first = list->last = NULL;
  45   list->nelements = 0;
  46 }
  47
  48 /*
  49  * Modifies:
  50  *   list
  51  * Effects:
  52  *   Adds a node to one end of the list (as specified by which_end)
  53  *   and returns a pointer to the node added.  which_end is of type
  54  *   ll_end and should be either ll_head or ll_tail as specified in
  55  *   list.h.  If there is not enough memory to allocate a node,
  56  *   the program returns NULL.
  57  */
  58 ll_node *ll_add_node(linked_list *list, ll_end which_end)
  59 {
  60   ll_node *node = NULL;
  61
  62   node = malloc(sizeof(ll_node));
  63   if (node)
  64     {
  65       node->data = NULL;
  66       if (list->nelements == 0)
  67         {
  68           list->first = node;
  69           list->last = node;
  70           list->nelements = 1;
  71           node->prev = node->next = NULL;
  72         }
  73       else
  74         {
  75           switch (which_end)
  76             {
  77             case ll_head:
  78               list->first->prev = node;
  79               node->next = list->first;
  80               list->first = node;
  81               node->prev = NULL;
  82               break;
  83             case ll_tail:
  84               list->last->next = node;
  85               node->prev = list->last;
  86               list->last = node;
  87               node->next = NULL;
  88               break;
  89             default:
  90               fprintf(stderr, "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 /*
 103  * Modifies:
 104  *   list
 105  * Effects:
 106  *   If node is in list, deletes node and returns LL_SUCCESS.
 107  *   Otherwise, returns LL_FAILURE.  If node contains other data,
 108  *   it is the responsibility of the caller to free it.  Also, since
 109  *   this routine frees node, after the routine is called, "node"
 110  *   won't point to valid data.
 111  */
 112 int ll_delete_node(linked_list *list, ll_node *node)
 113 {
 114   ll_node *cur_node;
 115
 116   for (cur_node = list->first; cur_node; cur_node = cur_node->next)
 117     {
 118       if (cur_node == node)
 119         {
 120           if (cur_node->prev)
 121             cur_node->prev->next = cur_node->next;
 122           else
 123             list->first = cur_node->next;
 124
 125           if (cur_node->next)
 126             cur_node->next->prev = cur_node->prev;
 127           else
 128             list->last = cur_node->prev;
 129
 130           free(cur_node);
 131           list->nelements--;
 132           return LL_SUCCESS;
 133         }
 134     }
 135
 136   return LL_FAILURE;
 137 }
 138
 139 int ll_string_check(linked_list *list, char *string)
 140 {
 141   ll_node *cur_node;
 142
 143   /* Scan the list until we find the string in question */
 144   for (cur_node = list->first; cur_node; cur_node = cur_node->next)
 145     {
 146       if (strcmp(string, cur_node->data) == 0)
 147         return 1;
 148     }
 149   return 0;
 150 }
 151
 152 /* This routine maintains a list of strings preventing duplication. */
 153 int ll_add_string(linked_list *list, char *string)
 154 {
 155   ll_node *node;
 156   char *new_string;
 157
 158   if (!ll_string_check(list, string))
 159     {
 160       node = ll_add_node(list, ll_tail);
 161       if (node)
 162         {
 163           new_string = strdup(string);
 164           if (new_string)
 165             ll_add_data(node, new_string);
 166           else
 167             return LL_FAILURE;
 168         }
 169       else
 170         return LL_FAILURE;
 171     }
 172   return LL_SUCCESS;
 173 }