1/* $NetBSD: lst.c,v 1.108 2024/04/27 17:33:46 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.108 2024/04/27 17:33:46 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
51void
52Lst_Done(List *list)
53{
54	ListNode *ln, *next;
55
56	for (ln = list->first; ln != NULL; ln = next) {
57		next = ln->next;
58		free(ln);
59	}
60}
61
62void
63Lst_DoneFree(List *list)
64{
65	ListNode *ln, *next;
66
67	for (ln = list->first; ln != NULL; ln = next) {
68		next = ln->next;
69		free(ln->datum);
70		free(ln);
71	}
72}
73
74/* Insert a new node with the datum before the given node. */
75void
76Lst_InsertBefore(List *list, ListNode *ln, void *datum)
77{
78	ListNode *newNode;
79
80	assert(datum != NULL);
81
82	newNode = LstNodeNew(ln->prev, ln, datum);
83
84	if (ln->prev != NULL)
85		ln->prev->next = newNode;
86	ln->prev = newNode;
87
88	if (ln == list->first)
89		list->first = newNode;
90}
91
92/* Add a piece of data at the start of the given list. */
93void
94Lst_Prepend(List *list, void *datum)
95{
96	ListNode *ln;
97
98	assert(datum != NULL);
99
100	ln = LstNodeNew(NULL, list->first, datum);
101
102	if (list->first == NULL) {
103		list->first = ln;
104		list->last = ln;
105	} else {
106		list->first->prev = ln;
107		list->first = ln;
108	}
109}
110
111/* Add a piece of data at the end of the given list. */
112void
113Lst_Append(List *list, void *datum)
114{
115	ListNode *ln;
116
117	assert(datum != NULL);
118
119	ln = LstNodeNew(list->last, NULL, datum);
120
121	if (list->last == NULL) {
122		list->first = ln;
123		list->last = ln;
124	} else {
125		list->last->next = ln;
126		list->last = ln;
127	}
128}
129
130/*
131 * Remove the given node from the given list.
132 * The datum stored in the node must be freed by the caller, if necessary.
133 */
134void
135Lst_Remove(List *list, ListNode *ln)
136{
137	/* unlink it from its neighbors */
138	if (ln->next != NULL)
139		ln->next->prev = ln->prev;
140	if (ln->prev != NULL)
141		ln->prev->next = ln->next;
142
143	/* unlink it from the list */
144	if (list->first == ln)
145		list->first = ln->next;
146	if (list->last == ln)
147		list->last = ln->prev;
148
149	free(ln);
150}
151
152/* Replace the datum in the given node with the new datum. */
153void
154LstNode_Set(ListNode *ln, void *datum)
155{
156	assert(datum != NULL);
157
158	ln->datum = datum;
159}
160
161/*
162 * Replace the datum in the given node with NULL.
163 * Having NULL values in a list is unusual though.
164 */
165void
166LstNode_SetNull(ListNode *ln)
167{
168	ln->datum = NULL;
169}
170
171/*
172 * Return the first node that contains the given datum, or NULL.
173 *
174 * Time complexity: O(length(list))
175 */
176ListNode *
177Lst_FindDatum(List *list, const void *datum)
178{
179	ListNode *ln;
180
181	assert(datum != NULL);
182
183	for (ln = list->first; ln != NULL; ln = ln->next)
184		if (ln->datum == datum)
185			return ln;
186
187	return NULL;
188}
189
190/*
191 * Move all nodes from src to the end of dst.
192 * The source list becomes indeterminate.
193 */
194void
195Lst_MoveAll(List *dst, List *src)
196{
197	if (src->first != NULL) {
198		src->first->prev = dst->last;
199		if (dst->last != NULL)
200			dst->last->next = src->first;
201		else
202			dst->first = src->first;
203
204		dst->last = src->last;
205	}
206#ifdef CLEANUP
207	src->first = NULL;
208	src->last = NULL;
209#endif
210}
211
212/* Copy the element data from src to the start of dst. */
213void
214Lst_PrependAll(List *dst, List *src)
215{
216	ListNode *ln;
217
218	for (ln = src->last; ln != NULL; ln = ln->prev)
219		Lst_Prepend(dst, ln->datum);
220}
221
222/* Copy the element data from src to the end of dst. */
223void
224Lst_AppendAll(List *dst, List *src)
225{
226	ListNode *ln;
227
228	for (ln = src->first; ln != NULL; ln = ln->next)
229		Lst_Append(dst, ln->datum);
230}
231
232/* Remove and return the datum at the head of the given list. */
233void *
234Lst_Dequeue(List *list)
235{
236	void *datum = list->first->datum;
237	Lst_Remove(list, list->first);
238	assert(datum != NULL);	/* since NULL would mean end of the list */
239	return datum;
240}
241
242void
243Vector_Init(Vector *v, size_t itemSize)
244{
245	v->len = 0;
246	v->cap = 10;
247	v->itemSize = itemSize;
248	v->items = bmake_malloc(v->cap * v->itemSize);
249}
250
251/*
252 * Add space for a new item to the vector and return a pointer to that space.
253 * The returned data is valid until the next modifying operation.
254 */
255void *
256Vector_Push(Vector *v)
257{
258	if (v->len >= v->cap) {
259		v->cap *= 2;
260		v->items = bmake_realloc(v->items, v->cap * v->itemSize);
261	}
262	v->len++;
263	return Vector_Get(v, v->len - 1);
264}
265
266/*
267 * Remove the last item from the vector, return the pointer to it.
268 * The returned data is valid until the next modifying operation.
269 */
270void *
271Vector_Pop(Vector *v)
272{
273	assert(v->len > 0);
274	v->len--;
275	return Vector_Get(v, v->len);
276}
277