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