1 /*-
2 * Copyright (c) 1988, 1989, 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Adam de Boor.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * $FreeBSD$
33 */
34
35 /*-
36 * lst.c --
37 * Routines to maintain a linked list of objects.
38 */
39
40 #include <stdio.h>
41 #include <stdlib.h>
42
43 #include "lst.h"
44 #include "util.h"
45
46 /**
47 * Lst_Append
48 * Create a new node and add it to the given list after the given node.
49 *
50 * Arguments:
51 * l affected list
52 * ln node after which to append the datum
53 * d said datum
54 *
55 * Side Effects:
56 * A new LstNode is created and linked in to the List. The lastPtr
57 * field of the List will be altered if ln is the last node in the
58 * list. lastPtr and firstPtr will alter if the list was empty and
59 * ln was NULL.
60 */
61 void
Lst_Append(Lst * list,LstNode * ln,void * d)62 Lst_Append(Lst *list, LstNode *ln, void *d)
63 {
64 LstNode *nLNode;
65
66 nLNode = emalloc(sizeof(*nLNode));
67 nLNode->datum = d;
68
69 if (ln == NULL) {
70 nLNode->nextPtr = nLNode->prevPtr = NULL;
71 list->firstPtr = list->lastPtr = nLNode;
72 } else {
73 nLNode->prevPtr = ln;
74 nLNode->nextPtr = ln->nextPtr;
75
76 ln->nextPtr = nLNode;
77 if (nLNode->nextPtr != NULL) {
78 nLNode->nextPtr->prevPtr = nLNode;
79 }
80
81 if (ln == list->lastPtr) {
82 list->lastPtr = nLNode;
83 }
84 }
85 }
86
87 /**
88 * Lst_Concat
89 * Concatenate two lists. New elements are created to hold the data
90 * elements, if specified, but the elements themselves are not copied.
91 * If the elements should be duplicated to avoid confusion with another
92 * list, the Lst_Duplicate function should be called first.
93 *
94 * Arguments:
95 * list1 The list to which list2 is to be appended
96 * list2 The list to append to list1
97 * flags LST_CONCNEW if LstNode's should be duplicated
98 * LST_CONCLINK if should just be relinked
99 *
100 * Side Effects:
101 * New elements are created and appended the first list.
102 */
103 void
Lst_Concat(Lst * list1,Lst * list2,int flags)104 Lst_Concat(Lst *list1, Lst *list2, int flags)
105 {
106 LstNode *ln; /* original LstNode */
107 LstNode *nln; /* new LstNode */
108 LstNode *last; /* the last element in the list. Keeps
109 * bookkeeping until the end */
110
111 if (list2->firstPtr == NULL)
112 return;
113
114 if (flags == LST_CONCLINK) {
115 /*
116 * Link the first element of the second list to the last
117 * element of the first list. If the first list isn't empty,
118 * we then link the last element of the list to the first
119 * element of the second list. The last element of the second
120 * list, if it exists, then becomes the last element of the
121 * first list.
122 */
123 list2->firstPtr->prevPtr = list1->lastPtr;
124 if (list1->lastPtr != NULL)
125 list1->lastPtr->nextPtr = list2->firstPtr;
126 else
127 list1->firstPtr = list2->firstPtr;
128 list1->lastPtr = list2->lastPtr;
129
130 Lst_Init(list2);
131 } else {
132 /*
133 * The loop simply goes through the entire second list creating
134 * new LstNodes and filling in the nextPtr, and prevPtr to fit
135 * into list1 and its datum field from the datum field of the
136 * corresponding element in list2. The 'last' node follows the
137 * last of the new nodes along until the entire list2 has been
138 * appended. Only then does the bookkeeping catch up with the
139 * changes. During the first iteration of the loop, if 'last'
140 * is NULL, the first list must have been empty so the
141 * newly-created node is made the first node of the list.
142 */
143 for (last = list1->lastPtr, ln = list2->firstPtr;
144 ln != NULL;
145 ln = ln->nextPtr) {
146 nln = emalloc(sizeof(*nln));
147 nln->datum = ln->datum;
148 if (last != NULL) {
149 last->nextPtr = nln;
150 } else {
151 list1->firstPtr = nln;
152 }
153 nln->prevPtr = last;
154 last = nln;
155 }
156
157 /*
158 * Finish bookkeeping. The last new element becomes the last
159 * element of list one.
160 */
161 list1->lastPtr = last;
162 last->nextPtr = NULL;
163 }
164 }
165
166 /**
167 * Lst_DeQueue
168 * Remove and return the datum at the head of the given list.
169 *
170 * Results:
171 * The datum in the node at the head or (ick) NULL if the list
172 * is empty.
173 *
174 * Side Effects:
175 * The head node is removed from the list.
176 */
177 void *
Lst_DeQueue(Lst * l)178 Lst_DeQueue(Lst *l)
179 {
180 void *rd;
181 LstNode *tln;
182
183 tln = Lst_First(l);
184 if (tln == NULL) {
185 return (NULL);
186 }
187
188 rd = tln->datum;
189 Lst_Remove(l, tln);
190 return (rd);
191 }
192
193 /**
194 * Lst_Destroy
195 * Destroy a list and free all its resources. If the freeProc is
196 * given, it is called with the datum from each node in turn before
197 * the node is freed.
198 *
199 * Side Effects:
200 * The given list is freed in its entirety.
201 */
202 void
Lst_Destroy(Lst * list,FreeProc * freeProc)203 Lst_Destroy(Lst *list, FreeProc *freeProc)
204 {
205 LstNode *ln;
206
207 if (list->firstPtr == NULL)
208 return;
209
210 if (freeProc != NOFREE) {
211 while ((ln = list->firstPtr) != NULL) {
212 list->firstPtr = ln->nextPtr;
213 (*freeProc)(ln->datum);
214 free(ln);
215 }
216 } else {
217 while ((ln = list->firstPtr) != NULL) {
218 list->firstPtr = ln->nextPtr;
219 free(ln);
220 }
221 }
222 list->lastPtr = NULL;
223 }
224
225 /**
226 * Lst_Duplicate
227 * Duplicate an entire list. If a function to copy a void * is
228 * given, the individual client elements will be duplicated as well.
229 *
230 * Arguments:
231 * dst the destination list (initialized)
232 * src the list to duplicate
233 * copyProc A function to duplicate each void
234 */
235 void
Lst_Duplicate(Lst * dst,Lst * src,DuplicateProc * copyProc)236 Lst_Duplicate(Lst *dst, Lst *src, DuplicateProc *copyProc)
237 {
238 LstNode *ln;
239
240 ln = src->firstPtr;
241 while (ln != NULL) {
242 if (copyProc != NOCOPY)
243 Lst_AtEnd(dst, (*copyProc)(ln->datum));
244 else
245 Lst_AtEnd(dst, ln->datum);
246 ln = ln->nextPtr;
247 }
248 }
249
250 /**
251 * Lst_Insert
252 * Insert a new node with the given piece of data before the given
253 * node in the given list.
254 *
255 * Parameters:
256 * l list to manipulate
257 * ln node before which to insert d
258 * d datum to be inserted
259 *
260 * Side Effects:
261 * the firstPtr field will be changed if ln is the first node in the
262 * list.
263 */
264 void
Lst_Insert(Lst * list,LstNode * ln,void * d)265 Lst_Insert(Lst *list, LstNode *ln, void *d)
266 {
267 LstNode *nLNode; /* new lnode for d */
268
269 nLNode = emalloc(sizeof(*nLNode));
270 nLNode->datum = d;
271
272 if (ln == NULL) {
273 nLNode->prevPtr = nLNode->nextPtr = NULL;
274 list->firstPtr = list->lastPtr = nLNode;
275 } else {
276 nLNode->prevPtr = ln->prevPtr;
277 nLNode->nextPtr = ln;
278
279 if (nLNode->prevPtr != NULL) {
280 nLNode->prevPtr->nextPtr = nLNode;
281 }
282 ln->prevPtr = nLNode;
283
284 if (ln == list->firstPtr) {
285 list->firstPtr = nLNode;
286 }
287 }
288 }
289
290 LstNode *
Lst_Member(Lst * list,void * d)291 Lst_Member(Lst *list, void *d)
292 {
293 LstNode *lNode;
294
295 lNode = list->firstPtr;
296 if (lNode == NULL) {
297 return (NULL);
298 }
299
300 do {
301 if (lNode->datum == d) {
302 return (lNode);
303 }
304 lNode = lNode->nextPtr;
305 } while (lNode != NULL && lNode != list->firstPtr);
306
307 return (NULL);
308 }
309
310 /**
311 * Lst_Remove
312 * Remove the given node from the given list.
313 *
314 * Side Effects:
315 * The list's firstPtr will be set to NULL if ln is the last
316 * node on the list. firsPtr and lastPtr will be altered if ln is
317 * either the first or last node, respectively, on the list.
318 */
319 void
Lst_Remove(Lst * list,LstNode * ln)320 Lst_Remove(Lst *list, LstNode *ln)
321 {
322 /*
323 * unlink it from the list
324 */
325 if (ln->nextPtr != NULL)
326 /* unlink from the backward chain */
327 ln->nextPtr->prevPtr = ln->prevPtr;
328 else
329 /* this was the last element */
330 list->lastPtr = ln->prevPtr;
331
332 if (ln->prevPtr != NULL)
333 /* unlink from the forward chain */
334 ln->prevPtr->nextPtr = ln->nextPtr;
335 else
336 /* this was the first element */
337 list->firstPtr = ln->nextPtr;
338
339 /*
340 * note that the datum is unmolested. The caller must free it as
341 * necessary and as expected.
342 */
343 free(ln);
344 }
345