1 /* $NetBSD: lst.c,v 1.105 2021/03/15 16:45:30 rillig Exp $ */
2
3 /*
4 * Copyright (c) 1988, 1989, 1990, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Adam de Boor.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #include "make.h"
36
37 MAKE_RCSID("$NetBSD: lst.c,v 1.105 2021/03/15 16:45:30 rillig Exp $");
38
39 static ListNode *
LstNodeNew(ListNode * prev,ListNode * next,void * datum)40 LstNodeNew(ListNode *prev, ListNode *next, void *datum)
41 {
42 ListNode *ln = bmake_malloc(sizeof *ln);
43
44 ln->prev = prev;
45 ln->next = next;
46 ln->datum = datum;
47
48 return ln;
49 }
50
51 /* Create and initialize a new, empty list. */
52 List *
Lst_New(void)53 Lst_New(void)
54 {
55 List *list = bmake_malloc(sizeof *list);
56 Lst_Init(list);
57 return list;
58 }
59
60 void
Lst_Done(List * list)61 Lst_Done(List *list)
62 {
63 ListNode *ln, *next;
64
65 for (ln = list->first; ln != NULL; ln = next) {
66 next = ln->next;
67 free(ln);
68 }
69 }
70
71 void
Lst_DoneCall(List * list,LstFreeProc freeProc)72 Lst_DoneCall(List *list, LstFreeProc freeProc)
73 {
74 ListNode *ln, *next;
75
76 for (ln = list->first; ln != NULL; ln = next) {
77 next = ln->next;
78 freeProc(ln->datum);
79 free(ln);
80 }
81 }
82
83 /* Free a list and all its nodes. The node data are not freed though. */
84 void
Lst_Free(List * list)85 Lst_Free(List *list)
86 {
87
88 Lst_Done(list);
89 free(list);
90 }
91
92 /* Insert a new node with the datum before the given node. */
93 void
Lst_InsertBefore(List * list,ListNode * ln,void * datum)94 Lst_InsertBefore(List *list, ListNode *ln, void *datum)
95 {
96 ListNode *newNode;
97
98 assert(datum != NULL);
99
100 newNode = LstNodeNew(ln->prev, ln, datum);
101
102 if (ln->prev != NULL)
103 ln->prev->next = newNode;
104 ln->prev = newNode;
105
106 if (ln == list->first)
107 list->first = newNode;
108 }
109
110 /* Add a piece of data at the start of the given list. */
111 void
Lst_Prepend(List * list,void * datum)112 Lst_Prepend(List *list, void *datum)
113 {
114 ListNode *ln;
115
116 assert(datum != NULL);
117
118 ln = LstNodeNew(NULL, list->first, datum);
119
120 if (list->first == NULL) {
121 list->first = ln;
122 list->last = ln;
123 } else {
124 list->first->prev = ln;
125 list->first = ln;
126 }
127 }
128
129 /* Add a piece of data at the end of the given list. */
130 void
Lst_Append(List * list,void * datum)131 Lst_Append(List *list, void *datum)
132 {
133 ListNode *ln;
134
135 assert(datum != NULL);
136
137 ln = LstNodeNew(list->last, NULL, datum);
138
139 if (list->last == NULL) {
140 list->first = ln;
141 list->last = ln;
142 } else {
143 list->last->next = ln;
144 list->last = ln;
145 }
146 }
147
148 /*
149 * Remove the given node from the given list.
150 * The datum stored in the node must be freed by the caller, if necessary.
151 */
152 void
Lst_Remove(List * list,ListNode * ln)153 Lst_Remove(List *list, ListNode *ln)
154 {
155 /* unlink it from its neighbors */
156 if (ln->next != NULL)
157 ln->next->prev = ln->prev;
158 if (ln->prev != NULL)
159 ln->prev->next = ln->next;
160
161 /* unlink it from the list */
162 if (list->first == ln)
163 list->first = ln->next;
164 if (list->last == ln)
165 list->last = ln->prev;
166 }
167
168 /* Replace the datum in the given node with the new datum. */
169 void
LstNode_Set(ListNode * ln,void * datum)170 LstNode_Set(ListNode *ln, void *datum)
171 {
172 assert(datum != NULL);
173
174 ln->datum = datum;
175 }
176
177 /*
178 * Replace the datum in the given node with NULL.
179 * Having NULL values in a list is unusual though.
180 */
181 void
LstNode_SetNull(ListNode * ln)182 LstNode_SetNull(ListNode *ln)
183 {
184 ln->datum = NULL;
185 }
186
187 /*
188 * Return the first node that contains the given datum, or NULL.
189 *
190 * Time complexity: O(length(list))
191 */
192 ListNode *
Lst_FindDatum(List * list,const void * datum)193 Lst_FindDatum(List *list, const void *datum)
194 {
195 ListNode *ln;
196
197 assert(datum != NULL);
198
199 for (ln = list->first; ln != NULL; ln = ln->next)
200 if (ln->datum == datum)
201 return ln;
202
203 return NULL;
204 }
205
206 /*
207 * Move all nodes from src to the end of dst.
208 * The source list becomes indeterminate.
209 */
210 void
Lst_MoveAll(List * dst,List * src)211 Lst_MoveAll(List *dst, List *src)
212 {
213 if (src->first != NULL) {
214 src->first->prev = dst->last;
215 if (dst->last != NULL)
216 dst->last->next = src->first;
217 else
218 dst->first = src->first;
219
220 dst->last = src->last;
221 }
222 #ifdef CLEANUP
223 src->first = NULL;
224 src->last = NULL;
225 #endif
226 }
227
228 /* Copy the element data from src to the start of dst. */
229 void
Lst_PrependAll(List * dst,List * src)230 Lst_PrependAll(List *dst, List *src)
231 {
232 ListNode *ln;
233
234 for (ln = src->last; ln != NULL; ln = ln->prev)
235 Lst_Prepend(dst, ln->datum);
236 }
237
238 /* Copy the element data from src to the end of dst. */
239 void
Lst_AppendAll(List * dst,List * src)240 Lst_AppendAll(List *dst, List *src)
241 {
242 ListNode *ln;
243
244 for (ln = src->first; ln != NULL; ln = ln->next)
245 Lst_Append(dst, ln->datum);
246 }
247
248 /* Remove and return the datum at the head of the given list. */
249 void *
Lst_Dequeue(List * list)250 Lst_Dequeue(List *list)
251 {
252 void *datum = list->first->datum;
253 Lst_Remove(list, list->first);
254 assert(datum != NULL); /* since NULL would mean end of the list */
255 return datum;
256 }
257
258 void
Vector_Init(Vector * v,size_t itemSize)259 Vector_Init(Vector *v, size_t itemSize)
260 {
261 v->len = 0;
262 v->cap = 10;
263 v->itemSize = itemSize;
264 v->items = bmake_malloc(v->cap * v->itemSize);
265 }
266
267 /*
268 * Add space for a new item to the vector and return a pointer to that space.
269 * The returned data is valid until the next modifying operation.
270 */
271 void *
Vector_Push(Vector * v)272 Vector_Push(Vector *v)
273 {
274 if (v->len >= v->cap) {
275 v->cap *= 2;
276 v->items = bmake_realloc(v->items, v->cap * v->itemSize);
277 }
278 v->len++;
279 return Vector_Get(v, v->len - 1);
280 }
281
282 /*
283 * Remove the last item from the vector, return the pointer to it.
284 * The returned data is valid until the next modifying operation.
285 */
286 void *
Vector_Pop(Vector * v)287 Vector_Pop(Vector *v)
288 {
289 assert(v->len > 0);
290 v->len--;
291 return Vector_Get(v, v->len);
292 }
293