1 /* $NetBSD: lst.c,v 1.107 2023/12/29 20:43:58 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.107 2023/12/29 20:43:58 rillig Exp $"); 38 39 static ListNode * 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 void 52 Lst_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 62 void 63 Lst_DoneCall(List *list, LstFreeProc freeProc) 64 { 65 ListNode *ln, *next; 66 67 for (ln = list->first; ln != NULL; ln = next) { 68 next = ln->next; 69 freeProc(ln->datum); 70 free(ln); 71 } 72 } 73 74 /* Insert a new node with the datum before the given node. */ 75 void 76 Lst_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. */ 93 void 94 Lst_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. */ 112 void 113 Lst_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 */ 134 void 135 Lst_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. */ 153 void 154 LstNode_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 */ 165 void 166 LstNode_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 */ 176 ListNode * 177 Lst_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 */ 194 void 195 Lst_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. */ 213 void 214 Lst_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. */ 223 void 224 Lst_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. */ 233 void * 234 Lst_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 242 void 243 Vector_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 */ 255 void * 256 Vector_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 */ 270 void * 271 Vector_Pop(Vector *v) 272 { 273 assert(v->len > 0); 274 v->len--; 275 return Vector_Get(v, v->len); 276 } 277