1/* $NetBSD: lst.c,v 1.104 2021/02/01 19:39:31 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
37MAKE_RCSID("$NetBSD: lst.c,v 1.104 2021/02/01 19:39:31 rillig Exp $");
38
39static ListNode *
40LstNodeNew(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. */
52List *
53Lst_New(void)
54{
55	List *list = bmake_malloc(sizeof *list);
56	Lst_Init(list);
57	return list;
58}
59
60void
61Lst_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
71void
72Lst_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. */
84void
85Lst_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. */
93void
94Lst_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. */
111void
112Lst_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. */
130void
131Lst_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 */
152void
153Lst_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. */
169void
170LstNode_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 */
181void
182LstNode_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 */
192ListNode *
193Lst_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 empty but is not freed.
209 */
210void
211Lst_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}
223
224/* Copy the element data from src to the start of dst. */
225void
226Lst_PrependAll(List *dst, List *src)
227{
228	ListNode *ln;
229
230	for (ln = src->last; ln != NULL; ln = ln->prev)
231		Lst_Prepend(dst, ln->datum);
232}
233
234/* Copy the element data from src to the end of dst. */
235void
236Lst_AppendAll(List *dst, List *src)
237{
238	ListNode *ln;
239
240	for (ln = src->first; ln != NULL; ln = ln->next)
241		Lst_Append(dst, ln->datum);
242}
243
244/* Remove and return the datum at the head of the given list. */
245void *
246Lst_Dequeue(List *list)
247{
248	void *datum = list->first->datum;
249	Lst_Remove(list, list->first);
250	assert(datum != NULL);	/* since NULL would mean end of the list */
251	return datum;
252}
253
254void
255Vector_Init(Vector *v, size_t itemSize)
256{
257	v->len = 0;
258	v->cap = 10;
259	v->itemSize = itemSize;
260	v->items = bmake_malloc(v->cap * v->itemSize);
261}
262
263/*
264 * Add space for a new item to the vector and return a pointer to that space.
265 * The returned data is valid until the next modifying operation.
266 */
267void *
268Vector_Push(Vector *v)
269{
270	if (v->len >= v->cap) {
271		v->cap *= 2;
272		v->items = bmake_realloc(v->items, v->cap * v->itemSize);
273	}
274	v->len++;
275	return Vector_Get(v, v->len - 1);
276}
277
278/*
279 * Remove the last item from the vector, return the pointer to it.
280 * The returned data is valid until the next modifying operation.
281 */
282void *
283Vector_Pop(Vector *v)
284{
285	assert(v->len > 0);
286	v->len--;
287	return Vector_Get(v, v->len);
288}
289