1179185Sjb/* $NetBSD: lst.c,v 1.108 2024/04/27 17:33:46 rillig Exp $ */ 2179185Sjb 3179185Sjb/* 4179185Sjb * Copyright (c) 1988, 1989, 1990, 1993 5179185Sjb * The Regents of the University of California. All rights reserved. 6179185Sjb * 7179185Sjb * This code is derived from software contributed to Berkeley by 8179185Sjb * Adam de Boor. 9179185Sjb * 10179185Sjb * Redistribution and use in source and binary forms, with or without 11179185Sjb * modification, are permitted provided that the following conditions 12179185Sjb * are met: 13179185Sjb * 1. Redistributions of source code must retain the above copyright 14179185Sjb * notice, this list of conditions and the following disclaimer. 15179185Sjb * 2. Redistributions in binary form must reproduce the above copyright 16179185Sjb * notice, this list of conditions and the following disclaimer in the 17179185Sjb * documentation and/or other materials provided with the distribution. 18179185Sjb * 3. Neither the name of the University nor the names of its contributors 19179185Sjb * may be used to endorse or promote products derived from this software 20179185Sjb * without specific prior written permission. 21179185Sjb * 22179185Sjb * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 23179185Sjb * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 24179185Sjb * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 25179185Sjb * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 26179185Sjb * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27179185Sjb * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 28179185Sjb * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 29179185Sjb * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 30210688Srpaulo * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 31179185Sjb * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 32179185Sjb * SUCH DAMAGE. 33179185Sjb */ 34179185Sjb 35179185Sjb#include "make.h" 36179185Sjb 37179185SjbMAKE_RCSID("$NetBSD: lst.c,v 1.108 2024/04/27 17:33:46 rillig Exp $"); 38179185Sjb 39179185Sjbstatic ListNode * 40179185SjbLstNodeNew(ListNode *prev, ListNode *next, void *datum) 41179185Sjb{ 42179185Sjb ListNode *ln = bmake_malloc(sizeof *ln); 43179185Sjb 44179185Sjb ln->prev = prev; 45179185Sjb ln->next = next; 46179185Sjb ln->datum = datum; 47210688Srpaulo 48179185Sjb return ln; 49179185Sjb} 50179185Sjb 51179185Sjbvoid 52179185SjbLst_Done(List *list) 53179185Sjb{ 54179185Sjb ListNode *ln, *next; 55179185Sjb 56179185Sjb for (ln = list->first; ln != NULL; ln = next) { 57179185Sjb next = ln->next; 58179185Sjb free(ln); 59179185Sjb } 60179185Sjb} 61210688Srpaulo 62179185Sjbvoid 63210688SrpauloLst_DoneFree(List *list) 64179185Sjb{ 65210688Srpaulo ListNode *ln, *next; 66210688Srpaulo 67210688Srpaulo for (ln = list->first; ln != NULL; ln = next) { 68179185Sjb next = ln->next; 69179185Sjb free(ln->datum); 70210688Srpaulo free(ln); 71210688Srpaulo } 72210688Srpaulo} 73210688Srpaulo 74210688Srpaulo/* Insert a new node with the datum before the given node. */ 75179185Sjbvoid 76179185SjbLst_InsertBefore(List *list, ListNode *ln, void *datum) 77210688Srpaulo{ 78210688Srpaulo ListNode *newNode; 79179185Sjb 80179185Sjb assert(datum != NULL); 81179185Sjb 82224632Savg newNode = LstNodeNew(ln->prev, ln, datum); 83179185Sjb 84179185Sjb if (ln->prev != NULL) 85179185Sjb ln->prev->next = newNode; 86179185Sjb ln->prev = newNode; 87179185Sjb 88179185Sjb if (ln == list->first) 89179185Sjb list->first = newNode; 90179185Sjb} 91184697Srodrigc 92184697Srodrigc/* Add a piece of data at the start of the given list. */ 93179185Sjbvoid 94179185SjbLst_Prepend(List *list, void *datum) 95179185Sjb{ 96179185Sjb ListNode *ln; 97179185Sjb 98179185Sjb assert(datum != NULL); 99179185Sjb 100179185Sjb ln = LstNodeNew(NULL, list->first, datum); 101179185Sjb 102179185Sjb if (list->first == NULL) { 103179185Sjb list->first = ln; 104179185Sjb list->last = ln; 105179185Sjb } else { 106210688Srpaulo list->first->prev = ln; 107210688Srpaulo list->first = ln; 108179185Sjb } 109184697Srodrigc} 110179185Sjb 111179185Sjb/* Add a piece of data at the end of the given list. */ 112179185Sjbvoid 113179185SjbLst_Append(List *list, void *datum) 114179185Sjb{ 115179185Sjb ListNode *ln; 116184697Srodrigc 117184697Srodrigc assert(datum != NULL); 118184697Srodrigc 119179185Sjb ln = LstNodeNew(list->last, NULL, datum); 120179185Sjb 121179185Sjb if (list->last == NULL) { 122179185Sjb list->first = ln; 123179185Sjb list->last = ln; 124179185Sjb } else { 125179185Sjb list->last->next = ln; 126179185Sjb list->last = ln; 127179185Sjb } 128179185Sjb} 129179185Sjb 130179185Sjb/* 131210688Srpaulo * Remove the given node from the given list. 132210688Srpaulo * The datum stored in the node must be freed by the caller, if necessary. 133210688Srpaulo */ 134210688Srpaulovoid 135210688SrpauloLst_Remove(List *list, ListNode *ln) 136179185Sjb{ 137179185Sjb /* unlink it from its neighbors */ 138210688Srpaulo if (ln->next != NULL) 139210688Srpaulo ln->next->prev = ln->prev; 140210688Srpaulo if (ln->prev != NULL) 141210688Srpaulo ln->prev->next = ln->next; 142210688Srpaulo 143179185Sjb /* unlink it from the list */ 144179185Sjb if (list->first == ln) 145210688Srpaulo list->first = ln->next; 146179185Sjb if (list->last == ln) 147179185Sjb list->last = ln->prev; 148179185Sjb 149179185Sjb free(ln); 150179185Sjb} 151179185Sjb 152179185Sjb/* Replace the datum in the given node with the new datum. */ 153179185Sjbvoid 154179185SjbLstNode_Set(ListNode *ln, void *datum) 155179185Sjb{ 156179185Sjb assert(datum != NULL); 157179185Sjb 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