xref: /netbsd/usr.bin/make/lst.c (revision f8c804d0)
1 /* $NetBSD: lst.c,v 1.106 2022/02/26 11:57:21 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.106 2022/02/26 11:57:21 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 	free(ln);
168 }
169 
170 /* Replace the datum in the given node with the new datum. */
171 void
LstNode_Set(ListNode * ln,void * datum)172 LstNode_Set(ListNode *ln, void *datum)
173 {
174 	assert(datum != NULL);
175 
176 	ln->datum = datum;
177 }
178 
179 /*
180  * Replace the datum in the given node with NULL.
181  * Having NULL values in a list is unusual though.
182  */
183 void
LstNode_SetNull(ListNode * ln)184 LstNode_SetNull(ListNode *ln)
185 {
186 	ln->datum = NULL;
187 }
188 
189 /*
190  * Return the first node that contains the given datum, or NULL.
191  *
192  * Time complexity: O(length(list))
193  */
194 ListNode *
Lst_FindDatum(List * list,const void * datum)195 Lst_FindDatum(List *list, const void *datum)
196 {
197 	ListNode *ln;
198 
199 	assert(datum != NULL);
200 
201 	for (ln = list->first; ln != NULL; ln = ln->next)
202 		if (ln->datum == datum)
203 			return ln;
204 
205 	return NULL;
206 }
207 
208 /*
209  * Move all nodes from src to the end of dst.
210  * The source list becomes indeterminate.
211  */
212 void
Lst_MoveAll(List * dst,List * src)213 Lst_MoveAll(List *dst, List *src)
214 {
215 	if (src->first != NULL) {
216 		src->first->prev = dst->last;
217 		if (dst->last != NULL)
218 			dst->last->next = src->first;
219 		else
220 			dst->first = src->first;
221 
222 		dst->last = src->last;
223 	}
224 #ifdef CLEANUP
225 	src->first = NULL;
226 	src->last = NULL;
227 #endif
228 }
229 
230 /* Copy the element data from src to the start of dst. */
231 void
Lst_PrependAll(List * dst,List * src)232 Lst_PrependAll(List *dst, List *src)
233 {
234 	ListNode *ln;
235 
236 	for (ln = src->last; ln != NULL; ln = ln->prev)
237 		Lst_Prepend(dst, ln->datum);
238 }
239 
240 /* Copy the element data from src to the end of dst. */
241 void
Lst_AppendAll(List * dst,List * src)242 Lst_AppendAll(List *dst, List *src)
243 {
244 	ListNode *ln;
245 
246 	for (ln = src->first; ln != NULL; ln = ln->next)
247 		Lst_Append(dst, ln->datum);
248 }
249 
250 /* Remove and return the datum at the head of the given list. */
251 void *
Lst_Dequeue(List * list)252 Lst_Dequeue(List *list)
253 {
254 	void *datum = list->first->datum;
255 	Lst_Remove(list, list->first);
256 	assert(datum != NULL);	/* since NULL would mean end of the list */
257 	return datum;
258 }
259 
260 void
Vector_Init(Vector * v,size_t itemSize)261 Vector_Init(Vector *v, size_t itemSize)
262 {
263 	v->len = 0;
264 	v->cap = 10;
265 	v->itemSize = itemSize;
266 	v->items = bmake_malloc(v->cap * v->itemSize);
267 }
268 
269 /*
270  * Add space for a new item to the vector and return a pointer to that space.
271  * The returned data is valid until the next modifying operation.
272  */
273 void *
Vector_Push(Vector * v)274 Vector_Push(Vector *v)
275 {
276 	if (v->len >= v->cap) {
277 		v->cap *= 2;
278 		v->items = bmake_realloc(v->items, v->cap * v->itemSize);
279 	}
280 	v->len++;
281 	return Vector_Get(v, v->len - 1);
282 }
283 
284 /*
285  * Remove the last item from the vector, return the pointer to it.
286  * The returned data is valid until the next modifying operation.
287  */
288 void *
Vector_Pop(Vector * v)289 Vector_Pop(Vector *v)
290 {
291 	assert(v->len > 0);
292 	v->len--;
293 	return Vector_Get(v, v->len);
294 }
295