Commit | Line | Data |
---|---|---|
805e021f CE |
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 | } |