4 * This file contains general linked list routines.
6 * Copyright 1990,1991 by the Massachusetts Institute of Technology
7 * For distribution and copying rights, see the file "mit-copyright.h"
10 #if !defined(lint) && !defined(SABER)
11 static char *rcsid_list_c = "$Id$";
12 #endif /* lint || SABER */
15 #include "linked_list.h"
32 void ll_init(linked_list *list)
35 * List must point to a linked list structure. It is not acceptable
36 * to pass a null pointer to this routine.
40 * Initializes the list to be one with no elements. If list is
41 * NULL, prints an error message and causes the program to crash.
49 fprintf(stderr, "Error: calling ll_init with null pointer.\n");
53 /* This sets everything to zero, which is what we want. */
55 memset(list, 0, sizeof(linked_list));
57 bzero((char *)list, sizeof(linked_list));
62 ll_node *ll_add_node(linked_list *list, ll_end which_end)
67 * Adds a node to one end of the list (as specified by which_end)
68 * and returns a pointer to the node added. which_end is of type
69 * ll_end and should be either ll_head or ll_tail as specified in
70 * list.h. If there is not enough memory to allocate a node,
71 * the program returns NULL.
74 ll_node *ll_add_node(list, which_end)
81 if ((node = (ll_node *)calloc(1, sizeof(ll_node))) != NULL) {
82 if (list->nelements == 0) {
90 list->first->prev = node;
91 node->next = list->first;
95 list->last->next = node;
96 node->prev = list->last;
100 fprintf(stderr, "%s%s",
101 "ll_add_node got a which_end parameter that ",
102 "it can't handle.\n");
114 int ll_delete_node(linked_list *list, ll_node *node)
119 * If node is in list, deletes node and returns LL_SUCCESS.
120 * Otherwise, returns LL_FAILURE. If node contains other data,
121 * it is the responsibility of the caller to free it. Also, since
122 * this routine frees node, after the routine is called, "node"
123 * won't point to valid data.
126 int ll_delete_node(list, node)
129 #endif /* __STDC__ */
131 int status = LL_SUCCESS;
132 ll_node *cur_node = NULL;
135 if (list->nelements == 0)
138 for (cur_node = list->first; (cur_node != NULL) && !found;
139 cur_node = cur_node->next) {
140 if (cur_node == node) {
143 cur_node->prev->next = cur_node->next;
145 list->first = cur_node->next;
148 cur_node->next->prev = cur_node->prev;
150 list->last = cur_node->prev;
166 /* ll_add_data is a macro defined in linked_list.h */
168 /* This routine maintains a list of strings preventing duplication. */
170 int ll_string(linked_list *list, ll_s_action action, char *string)
172 int ll_string(list, action, string)
176 #endif /* __STDC__ */
178 int status = LL_SUCCESS;
183 /* Scan the list until we find the string in question */
184 for (cur_node = list->first; cur_node && (status == FALSE);
185 cur_node = cur_node->next)
186 status = (strcmp(string, cur_node->data) == 0);
189 /* Add a string to the list. */
190 if (!ll_string(list, ll_s_check, string)) {
191 if (cur_node = ll_add_node(list, ll_tail)) {
193 if (new_string = (char *)calloc(strlen(string) + 1,
195 strcpy(new_string, string);
196 ll_add_data(cur_node, new_string);
206 /* This should never happen */